791ac79b87f6bf831e2ba4f993408cdc39405d71
[exim.git] / src / src / tree.c
1 /* $Cambridge: exim/src/src/tree.c,v 1.2 2005/01/04 10:00:42 ph10 Exp $ */
2
3 /*************************************************
4 *     Exim - an Internet mail transport agent    *
5 *************************************************/
6
7 /* Copyright (c) University of Cambridge 1995 - 2005 */
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 */