src/tree.c

   1 /*************************************************
   2 *     Exim - an Internet mail transport agent    *
   3 *************************************************/
   4
   5 /* Copyright (c) University of Cambridge 1995 - 2015 */
   6 /* See the file NOTICE for conditions of use and distribution. */
   7
   8 /* Functions for maintaining binary balanced trees and some associated
   9 functions as well. */
  10
  11
  12 #include "exim.h"
  13
  14
  15
  16
  17 /*************************************************
  18 *        Add entry to non-recipients tree        *
  19 *************************************************/
  20
  21 /* Duplicates are just discarded.
  22
  23 Arguments:
  24   s       string to add
  25
  26 Returns:  nothing
  27 */
  28
  29 void
  30 tree_add_nonrecipient(uschar *s)
  31 {
  32 tree_node *node = store_get(sizeof(tree_node) + Ustrlen(s));
  33 Ustrcpy(node->name, s);
  34 node->data.ptr = NULL;
  35 if (!tree_insertnode(&tree_nonrecipients, node)) store_reset(node);
  36 }
  37
  38
  39
  40 /*************************************************
  41 *        Add entry to duplicates tree            *
  42 *************************************************/
  43
  44 /* Duplicates are just discarded.
  45
  46 Argument:
  47   s       string to add
  48   addr    the address is is a duplicate of
  49
  50 Returns:  nothing
  51 */
  52
  53 void
  54 tree_add_duplicate(uschar *s, address_item *addr)
  55 {
  56 tree_node *node = store_get(sizeof(tree_node) + Ustrlen(s));
  57 Ustrcpy(node->name, s);
  58 node->data.ptr = addr;
  59 if (!tree_insertnode(&tree_duplicates, node)) store_reset(node);
  60 }
  61
  62
  63
  64 /*************************************************
  65 *    Add entry to unusable addresses tree        *
  66 *************************************************/
  67
  68 /* Duplicates are simply discarded.
  69
  70 Argument:    the host item
  71 Returns:     nothing
  72 */
  73
  74 void
  75 tree_add_unusable(host_item *h)
  76 {
  77 tree_node *node;
  78 uschar s[256];
  79 sprintf(CS s, "T:%.200s:%s", h->name, h->address);
  80 node = store_get(sizeof(tree_node) + Ustrlen(s));
  81 Ustrcpy(node->name, s);
  82 node->data.val = h->why;
  83 if (h->status == hstatus_unusable_expired) node->data.val += 256;
  84 if (!tree_insertnode(&tree_unusable, node)) store_reset(node);
  85 }
  86
  87
  88
  89 /*************************************************
  90 *        Write a tree in re-readable form        *
  91 *************************************************/
  92
  93 /* This function writes out a tree in a form in which it can
  94 easily be re-read. It is used for writing out the non-recipients
  95 tree onto the spool, for retrieval at the next retry time.
  96
  97 The format is as follows:
  98
  99    . If the tree is empty, write one line containing XX.
 100
 101    . Otherwise, each node is written, preceded by two letters
 102      (Y/N) indicating whether it has left or right children.
 103
 104    . The left subtree (if any) then follows, then the right subtree.
 105
 106 First, there's an internal recursive subroutine.
 107
 108 Arguments:
 109   p          current node
 110   f          FILE to write to
 111
 112 Returns:     nothing
 113 */
 114
 115 static void
 116 write_tree(tree_node *p, FILE *f)
 117 {
 118 fprintf(f, "%c%c %s\n",
 119   (p->left == NULL)? 'N':'Y', (p->right == NULL)? 'N':'Y', p->name);
 120 if (p->left != NULL) write_tree(p->left, f);
 121 if (p->right != NULL) write_tree(p->right, f);
 122 }
 123
 124 /* This is the top-level function, with the same arguments. */
 125
 126 void
 127 tree_write(tree_node *p, FILE *f)
 128 {
 129 if (p == NULL)
 130   {
 131   fprintf(f, "XX\n");
 132   return;
 133   }
 134 write_tree(p, f);
 135 }
 136
 137
 138
 139
 140
 141 /***********************************************************
 142 *          Binary Balanced Tree Management Routines        *
 143 ***********************************************************/
 144
 145 /* This set of routines maintains a balanced binary tree using
 146 the algorithm given in Knuth Vol 3 page 455.
 147
 148 The routines make use of uschar * pointers as byte pointers,
 149 so as to be able to do arithmetic on them, since ANSI Standard
 150 C does not permit additions and subtractions on void pointers. */
 151
 152
 153 /*************************************************
 154 *              Flags and Parameters              *
 155 *************************************************/
 156
 157 #define tree_lbal      1         /* left subtree is longer */
 158 #define tree_rbal      2         /* right subtree is longer */
 159 #define tree_bmask     3         /* mask for flipping bits */
 160
 161
 162 /*************************************************
 163 *         Insert a new node into a tree          *
 164 *************************************************/
 165
 166 /* The node->name field must (obviously) be set, but the other
 167 fields need not be initialized.
 168
 169 Arguments:
 170   treebase   pointer to the root of the tree
 171   node       the note to insert, with name field set
 172
 173 Returns:     TRUE if node inserted; FALSE if not (duplicate)
 174 */
 175
 176 int
 177 tree_insertnode(tree_node **treebase, tree_node *node)
 178 {
 179 tree_node *p = *treebase;
 180 tree_node **q, *r, *s, **t;
 181 int a;
 182
 183 node->left = node->right = NULL;
 184 node->balance = 0;
 185
 186 /* Deal with an empty tree */
 187
 188 if (p == NULL)
 189   {
 190   *treebase = node;
 191   return TRUE;
 192   }
 193
 194 /* The tree is not empty. While finding the insertion point,
 195 q points to the pointer to p, and t points to the pointer to
 196 the potential re-balancing point. */
 197
 198 q = treebase;
 199 t = q;
 200
 201 /* Loop to search tree for place to insert new node */
 202
 203 for (;;)
 204   {
 205   int c = Ustrcmp(node->name, p->name);
 206   if (c == 0) return FALSE;              /* Duplicate node encountered */
 207
 208   /* Deal with climbing down the tree, exiting from the loop
 209   when we reach a leaf. */
 210
 211   q = (c > 0)? &(p->right) : &(p->left);
 212   p = *q;
 213   if (p == NULL) break;
 214
 215   /* Save the address of the pointer to the last node en route
 216   which has a non-zero balance factor. */
 217
 218   if (p->balance != 0) t = q;
 219   }
 220
 221 /* When the above loop completes, q points to the pointer to NULL;
 222 that is the place at which the new node must be inserted. */
 223
 224 *q = node;
 225
 226 /* Set up s as the potential re-balancing point, and r as the
 227 next node after it along the route. */
 228
 229 s = *t;
 230 r = (Ustrcmp(node->name, s->name) > 0)? s->right : s->left;
 231
 232 /* Adjust balance factors along the route from s to node. */
 233
 234 p = r;
 235
 236 while (p != node)
 237   {
 238   if (Ustrcmp(node->name, p->name) < 0)
 239     {
 240     p->balance = tree_lbal;
 241     p = p->left;
 242     }
 243   else
 244     {
 245     p->balance = tree_rbal;
 246     p = p->right;
 247     }
 248   }
 249
 250 /* Now the World-Famous Balancing Act */
 251
 252 a = (Ustrcmp(node->name, s->name) < 0)? tree_lbal : tree_rbal;
 253
 254 if (s->balance == 0) s->balance = (uschar)a;        /* The tree has grown higher */
 255   else if (s->balance != (uschar)a) s->balance = 0; /* It's become more balanced */
 256 else                                              /* It's got out of balance */
 257   {
 258   /* Perform a single rotation */
 259
 260   if (r->balance == (uschar)a)
 261     {
 262     p = r;
 263     if (a == tree_rbal)
 264       {
 265       s->right = r->left;
 266       r->left = s;
 267       }
 268     else
 269       {
 270       s->left = r->right;
 271       r->right = s;
 272       }
 273     s->balance = 0;
 274     r->balance = 0;
 275     }
 276
 277   /* Perform a double rotation There was an occasion when the balancing
 278   factors were screwed up by a bug in the code that reads a tree from
 279   the spool. In case this ever happens again, check for changing p to NULL
 280   and don't do it. It is better to have an unbalanced tree than a crash. */
 281
 282   else
 283     {
 284     if (a == tree_rbal)
 285       {
 286       if (r->left == NULL) return TRUE;   /* Bail out if tree corrupt */
 287       p = r->left;
 288       r->left = p->right;
 289       p->right = r;
 290       s->right = p->left;
 291       p->left = s;
 292       }
 293     else
 294       {
 295       if (r->right == NULL) return TRUE;  /* Bail out if tree corrupt */
 296       p = r->right;
 297       r->right = p->left;
 298       p->left = r;
 299       s->left = p->right;
 300       p->right = s;
 301       }
 302
 303     s->balance = (p->balance == (uschar)a)? (uschar)(a^tree_bmask) : 0;
 304     r->balance = (p->balance == (uschar)(a^tree_bmask))? (uschar)a : 0;
 305     p->balance = 0;
 306     }
 307
 308   /* Finishing touch */
 309
 310   *t = p;
 311   }
 312
 313 return TRUE;     /* Successful insertion */
 314 }
 315
 316
 317
 318 /*************************************************
 319 *          Search tree for node by name          *
 320 *************************************************/
 321
 322 /*
 323 Arguments:
 324   p         root of tree
 325   name      key to search for
 326
 327 Returns:    pointer to node, or NULL if not found
 328 */
 329
 330 tree_node *
 331 tree_search(tree_node *p, const uschar *name)
 332 {
 333 while (p != NULL)
 334   {
 335   int c = Ustrcmp(name, p->name);
 336   if (c == 0) return p;
 337   p = (c < 0)? p->left : p->right;
 338   }
 339 return NULL;
 340 }
 341
 342
 343
 344 /*************************************************
 345 *   Walk tree recursively and execute function   *
 346 *************************************************/
 347
 348 /*
 349 Arguments:
 350   p       root of the tree
 351   f       function to execute for each name-value-pair
 352   ctx     context data for f
 353 */
 354
 355 void
 356 tree_walk(tree_node *p, void (*f)(uschar*, uschar*, void*), void *ctx)
 357 {
 358 if (p == NULL) return;
 359 f(p->name, p->data.ptr, ctx);
 360 if (p->left != NULL) tree_walk(p->left, f, ctx);
 361 if (p->right != NULL) tree_walk(p->right, f, ctx);
 362 }
 363
 364
 365 /* End of tree.c */