1 /*************************************************
2 * Exim - an Internet mail transport agent *
3 *************************************************/
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. */
9 /* Functions for maintaining binary balanced trees and some associated
18 /*************************************************
19 * Add entry to non-recipients tree *
20 *************************************************/
22 /* Duplicates are just discarded.
31 tree_add_nonrecipient(const uschar *s)
33 rmark rpoint = store_mark();
34 tree_node * node = store_get(sizeof(tree_node) + Ustrlen(s), s);
35 Ustrcpy(node->name, s);
36 node->data.ptr = NULL;
37 if (!tree_insertnode(&tree_nonrecipients, node)) store_reset(rpoint);
42 /*************************************************
43 * Add entry to duplicates tree *
44 *************************************************/
46 /* Duplicates are just discarded.
50 addr the address is is a duplicate of
56 tree_add_duplicate(const uschar *s, address_item *addr)
58 rmark rpoint = store_mark();
59 tree_node * node = store_get(sizeof(tree_node) + Ustrlen(s), s);
60 Ustrcpy(node->name, s);
61 node->data.ptr = addr;
62 if (!tree_insertnode(&tree_duplicates, node)) store_reset(rpoint);
67 /*************************************************
68 * Add entry to unusable addresses tree *
69 *************************************************/
71 /* Duplicates are simply discarded.
73 Argument: the host item
78 tree_add_unusable(const host_item *h)
80 rmark rpoint = store_mark();
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) ? GET_TAINTED : GET_UNTAINTED);
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);
94 /*************************************************
95 * Write a tree in re-readable form *
96 *************************************************/
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.
102 The format is as follows:
104 . If the tree is empty, write one line containing XX.
106 . Otherwise, each node is written, preceded by two letters
107 (Y/N) indicating whether it has left or right children.
109 . The left subtree (if any) then follows, then the right subtree.
111 First, there's an internal recursive subroutine.
121 write_tree(tree_node *p, FILE *f)
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);
129 /* This is the top-level function, with the same arguments. */
132 tree_write(tree_node *p, FILE *f)
146 /***********************************************************
147 * Binary Balanced Tree Management Routines *
148 ***********************************************************/
150 /* This set of routines maintains a balanced binary tree using
151 the algorithm given in Knuth Vol 3 page 455.
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. */
158 /*************************************************
159 * Flags and Parameters *
160 *************************************************/
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 */
167 /*************************************************
168 * Insert a new node into a tree *
169 *************************************************/
171 /* The node->name field must (obviously) be set, but the other
172 fields need not be initialized.
175 treebase pointer to the root of the tree
176 node the note to insert, with name field set
178 Returns: TRUE if node inserted; FALSE if not (duplicate)
182 tree_insertnode(tree_node **treebase, tree_node *node)
184 tree_node *p = *treebase;
185 tree_node **q, *r, *s, **t;
188 node->left = node->right = NULL;
191 /* Deal with an empty tree */
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. */
206 /* Loop to search tree for place to insert new node */
210 int c = Ustrcmp(node->name, p->name);
211 if (c == 0) return FALSE; /* Duplicate node encountered */
213 /* Deal with climbing down the tree, exiting from the loop
214 when we reach a leaf. */
216 q = (c > 0)? &(p->right) : &(p->left);
218 if (p == NULL) break;
220 /* Save the address of the pointer to the last node en route
221 which has a non-zero balance factor. */
223 if (p->balance != 0) t = q;
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. */
231 /* Set up s as the potential re-balancing point, and r as the
232 next node after it along the route. */
235 r = (Ustrcmp(node->name, s->name) > 0)? s->right : s->left;
237 /* Adjust balance factors along the route from s to node. */
243 if (Ustrcmp(node->name, p->name) < 0)
245 p->balance = tree_lbal;
250 p->balance = tree_rbal;
255 /* Now the World-Famous Balancing Act */
257 a = (Ustrcmp(node->name, s->name) < 0)? tree_lbal : tree_rbal;
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 */
263 /* Perform a single rotation */
265 if (r->balance == (uschar)a)
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. */
291 if (r->left == NULL) return TRUE; /* Bail out if tree corrupt */
300 if (r->right == NULL) return TRUE; /* Bail out if tree corrupt */
308 s->balance = (p->balance == (uschar)a)? (uschar)(a^tree_bmask) : 0;
309 r->balance = (p->balance == (uschar)(a^tree_bmask))? (uschar)a : 0;
313 /* Finishing touch */
318 return TRUE; /* Successful insertion */
323 /*************************************************
324 * Search tree for node by name *
325 *************************************************/
330 name key to search for
332 Returns: pointer to node, or NULL if not found
336 tree_search(tree_node *p, const uschar *name)
340 int c = Ustrcmp(name, p->name);
341 if (c == 0) return p;
342 p = c < 0 ? p->left : p->right;
349 /*************************************************
350 * Walk tree recursively and execute function *
351 *************************************************/
356 f function to execute for each name-value-pair
357 ctx context data for f
361 tree_walk(tree_node *p, void (*f)(uschar*, uschar*, void*), void *ctx)
364 f(p->name, p->data.ptr, ctx);
365 tree_walk(p->left, f, ctx);
366 tree_walk(p->right, f, ctx);
371 /* Add a node to a tree, ignoring possibility of duplicates */
374 tree_add_var(uschar * name, uschar * val, void * ctx)
376 tree_node ** root = ctx;
377 tree_node * node = store_get(sizeof(tree_node) + Ustrlen(name), name);
378 Ustrcpy(node->name, name);
379 node->data.ptr = val;
380 (void) tree_insertnode(root, node);
383 /* Duplicate a tree */
386 tree_dup(tree_node ** dstp, tree_node * src)
388 tree_walk(src, tree_add_var, dstp);