eb54829db58ada1b0ad095a6384b5990d7973840
[exim.git] / src / src / tree.c
1 /*************************************************
2 *     Exim - an Internet mail transport agent    *
3 *************************************************/
4
5 /* Copyright (c) The Exim Maintainers 2021 - 2023 */
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 it 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 */