src/src/tree.c

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