src/src/tree.c

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