1 /*************************************************
2 * Exim - an Internet mail transport agent *
3 *************************************************/
5 /* Copyright (c) University of Cambridge 1995 - 2015 */
6 /* See the file NOTICE for conditions of use and distribution. */
8 /* 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(uschar *s)
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);
41 /*************************************************
42 * Add entry to duplicates tree *
43 *************************************************/
45 /* Duplicates are just discarded.
49 addr the address is is a duplicate of
55 tree_add_duplicate(uschar *s, address_item *addr)
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);
65 /*************************************************
66 * Add entry to unusable addresses tree *
67 *************************************************/
69 /* Duplicates are simply discarded.
71 Argument: the host item
76 tree_add_unusable(host_item *h)
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);
90 /*************************************************
91 * Write a tree in re-readable form *
92 *************************************************/
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.
98 The format is as follows:
100 . If the tree is empty, write one line containing XX.
102 . Otherwise, each node is written, preceded by two letters
103 (Y/N) indicating whether it has left or right children.
105 . The left subtree (if any) then follows, then the right subtree.
107 First, there's an internal recursive subroutine.
117 write_tree(tree_node *p, FILE *f)
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);
124 /* This is the top-level function, with the same arguments. */
127 tree_write(tree_node *p, FILE *f)
142 /***********************************************************
143 * Binary Balanced Tree Management Routines *
144 ***********************************************************/
146 /* This set of routines maintains a balanced binary tree using
147 the algorithm given in Knuth Vol 3 page 455.
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. */
154 /*************************************************
155 * Flags and Parameters *
156 *************************************************/
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 */
163 /*************************************************
164 * Insert a new node into a tree *
165 *************************************************/
167 /* The node->name field must (obviously) be set, but the other
168 fields need not be initialized.
171 treebase pointer to the root of the tree
172 node the note to insert, with name field set
174 Returns: TRUE if node inserted; FALSE if not (duplicate)
178 tree_insertnode(tree_node **treebase, tree_node *node)
180 tree_node *p = *treebase;
181 tree_node **q, *r, *s, **t;
184 node->left = node->right = NULL;
187 /* Deal with an empty tree */
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. */
202 /* Loop to search tree for place to insert new node */
206 int c = Ustrcmp(node->name, p->name);
207 if (c == 0) return FALSE; /* Duplicate node encountered */
209 /* Deal with climbing down the tree, exiting from the loop
210 when we reach a leaf. */
212 q = c > 0 ? &p->right : &p->left;
216 /* Save the address of the pointer to the last node en route
217 which has a non-zero balance factor. */
219 if (p->balance != 0) t = q;
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. */
227 /* Set up s as the potential re-balancing point, and r as the
228 next node after it along the route. */
231 r = Ustrcmp(node->name, s->name) > 0 ? s->right : s->left;
233 /* Adjust balance factors along the route from s to node. */
238 if (Ustrcmp(node->name, p->name) < 0)
240 p->balance = tree_lbal;
245 p->balance = tree_rbal;
249 /* Now the World-Famous Balancing Act */
251 a = Ustrcmp(node->name, s->name) < 0 ? tree_lbal : tree_rbal;
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 */
259 /* Perform a single rotation */
261 if (r->balance == (uschar)a)
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. */
287 if (!r->left) return TRUE; /* Bail out if tree corrupt */
296 if (!r->right) return TRUE; /* Bail out if tree corrupt */
304 s->balance = p->balance == (uschar)a ? (uschar)(a^tree_bmask) : 0;
305 r->balance = p->balance == (uschar)(a^tree_bmask) ? (uschar)a : 0;
309 /* Finishing touch */
314 return TRUE; /* Successful insertion */
319 /*************************************************
320 * Search tree for node by name *
321 *************************************************/
326 name key to search for
328 Returns: pointer to node, or NULL if not found
332 tree_search(tree_node *p, const uschar *name)
335 for ( ; p; p = c < 0 ? p->left : p->right)
336 if ((c = Ustrcmp(name, p->name)) == 0)
344 /*************************************************
345 * Walk tree recursively and execute function *
346 *************************************************/
351 f function to execute for each name-value-pair
352 ctx context data for f
356 tree_walk(tree_node *p, void (*f)(uschar*, uschar*, void*), void *ctx)
359 f(p->name, p->data.ptr, ctx);
360 tree_walk(p->left, f, ctx);
361 tree_walk(p->right, f, ctx);