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