src/src/tree.c

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