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