| 1 | /************************************************* |
| 2 | * Exim - an Internet mail transport agent * |
| 3 | *************************************************/ |
| 4 | |
| 5 | /* Copyright (c) University of Cambridge 1995 - 2015 */ |
| 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 | rmark rpoint = store_mark(); |
| 33 | tree_node *node = store_get(sizeof(tree_node) + Ustrlen(s), is_tainted(s)); |
| 34 | Ustrcpy(node->name, s); |
| 35 | node->data.ptr = NULL; |
| 36 | if (!tree_insertnode(&tree_nonrecipients, node)) store_reset(rpoint); |
| 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 | { |
| 57 | rmark rpoint = store_mark(); |
| 58 | tree_node *node = store_get(sizeof(tree_node) + Ustrlen(s), is_tainted(s)); |
| 59 | Ustrcpy(node->name, s); |
| 60 | node->data.ptr = addr; |
| 61 | if (!tree_insertnode(&tree_duplicates, node)) store_reset(rpoint); |
| 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 | rmark rpoint = store_mark(); |
| 80 | tree_node *node; |
| 81 | uschar s[256]; |
| 82 | sprintf(CS s, "T:%.200s:%s", h->name, h->address); |
| 83 | node = store_get(sizeof(tree_node) + Ustrlen(s), |
| 84 | is_tainted(h->name) || is_tainted(h->address)); |
| 85 | Ustrcpy(node->name, s); |
| 86 | node->data.val = h->why; |
| 87 | if (h->status == hstatus_unusable_expired) node->data.val += 256; |
| 88 | if (!tree_insertnode(&tree_unusable, node)) store_reset(rpoint); |
| 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 | { |
| 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); |
| 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 | { |
| 133 | if (p == NULL) |
| 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 | |
| 192 | if (p == NULL) |
| 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 | |
| 215 | q = (c > 0)? &(p->right) : &(p->left); |
| 216 | p = *q; |
| 217 | if (p == NULL) break; |
| 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; |
| 234 | r = (Ustrcmp(node->name, s->name) > 0)? s->right : s->left; |
| 235 | |
| 236 | /* Adjust balance factors along the route from s to node. */ |
| 237 | |
| 238 | p = r; |
| 239 | |
| 240 | while (p != node) |
| 241 | { |
| 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 | } |
| 252 | } |
| 253 | |
| 254 | /* Now the World-Famous Balancing Act */ |
| 255 | |
| 256 | a = (Ustrcmp(node->name, s->name) < 0)? tree_lbal : tree_rbal; |
| 257 | |
| 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 */ |
| 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 | { |
| 290 | if (r->left == NULL) return TRUE; /* Bail out if tree corrupt */ |
| 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 | { |
| 299 | if (r->right == NULL) return TRUE; /* Bail out if tree corrupt */ |
| 300 | p = r->right; |
| 301 | r->right = p->left; |
| 302 | p->left = r; |
| 303 | s->left = p->right; |
| 304 | p->right = s; |
| 305 | } |
| 306 | |
| 307 | s->balance = (p->balance == (uschar)a)? (uschar)(a^tree_bmask) : 0; |
| 308 | r->balance = (p->balance == (uschar)(a^tree_bmask))? (uschar)a : 0; |
| 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 * |
| 335 | tree_search(tree_node *p, const uschar *name) |
| 336 | { |
| 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 | } |
| 343 | return NULL; |
| 344 | } |
| 345 | |
| 346 | |
| 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 | { |
| 362 | if (!p) return; |
| 363 | f(p->name, p->data.ptr, ctx); |
| 364 | tree_walk(p->left, f, ctx); |
| 365 | tree_walk(p->right, f, ctx); |
| 366 | } |
| 367 | |
| 368 | |
| 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; |
| 376 | tree_node * node = store_get(sizeof(tree_node) + Ustrlen(name), is_tainted(name)); |
| 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 | |
| 392 | /* End of tree.c */ |