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