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