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