diff options
Diffstat (limited to 'src/src/tree.c')
| -rw-r--r-- | src/src/tree.c | 345 |
1 files changed, 345 insertions, 0 deletions
diff --git a/src/src/tree.c b/src/src/tree.c new file mode 100644 index 000000000..12592c100 --- /dev/null +++ b/src/src/tree.c @@ -0,0 +1,345 @@ +/* $Cambridge: exim/src/src/tree.c,v 1.1 2004/10/07 10:39:01 ph10 Exp $ */ + +/************************************************* +* Exim - an Internet mail transport agent * +*************************************************/ + +/* Copyright (c) University of Cambridge 1995 - 2004 */ +/* See the file NOTICE for conditions of use and distribution. */ + +/* Functions for maintaining binary balanced trees and some associated +functions as well. */ + + +#include "exim.h" + + + + +/************************************************* +* Add entry to non-recipients tree * +*************************************************/ + +/* Duplicates are just discarded. + +Arguments: + s string to add + +Returns: nothing +*/ + +void +tree_add_nonrecipient(uschar *s) +{ +tree_node *node = store_get(sizeof(tree_node) + Ustrlen(s)); +Ustrcpy(node->name, s); +node->data.ptr = NULL; +if (!tree_insertnode(&tree_nonrecipients, node)) store_reset(node); +} + + + +/************************************************* +* Add entry to duplicates tree * +*************************************************/ + +/* Duplicates are just discarded. + +Argument: + s string to add + addr the address is is a duplicate of + +Returns: nothing +*/ + +void +tree_add_duplicate(uschar *s, address_item *addr) +{ +tree_node *node = store_get(sizeof(tree_node) + Ustrlen(s)); +Ustrcpy(node->name, s); +node->data.ptr = addr; +if (!tree_insertnode(&tree_duplicates, node)) store_reset(node); +} + + + +/************************************************* +* Add entry to unusable addresses tree * +*************************************************/ + +/* Duplicates are simply discarded. + +Argument: the host item +Returns: nothing +*/ + +void +tree_add_unusable(host_item *h) +{ +tree_node *node; +uschar s[256]; +sprintf(CS s, "T:%.200s:%s", h->name, h->address); +node = store_get(sizeof(tree_node) + Ustrlen(s)); +Ustrcpy(node->name, s); +node->data.val = h->why; +if (h->status == hstatus_unusable_expired) node->data.val += 256; +if (!tree_insertnode(&tree_unusable, node)) store_reset(node); +} + + + +/************************************************* +* Write a tree in re-readable form * +*************************************************/ + +/* This function writes out a tree in a form in which it can +easily be re-read. It is used for writing out the non-recipients +tree onto the spool, for retrieval at the next retry time. + +The format is as follows: + + . If the tree is empty, write one line containing XX. + + . Otherwise, each node is written, preceded by two letters + (Y/N) indicating whether it has left or right children. + + . The left subtree (if any) then follows, then the right subtree. + +First, there's an internal recursive subroutine. + +Arguments: + p current node + f FILE to write to + +Returns: nothing +*/ + +static void +write_tree(tree_node *p, FILE *f) +{ +fprintf(f, "%c%c %s\n", + (p->left == NULL)? 'N':'Y', (p->right == NULL)? 'N':'Y', p->name); +if (p->left != NULL) write_tree(p->left, f); +if (p->right != NULL) write_tree(p->right, f); +} + +/* This is the top-level function, with the same arguments. */ + +void +tree_write(tree_node *p, FILE *f) +{ +if (p == NULL) + { + fprintf(f, "XX\n"); + return; + } +write_tree(p, f); +} + + + + + +/*********************************************************** +* Binary Balanced Tree Management Routines * +***********************************************************/ + +/* This set of routines maintains a balanced binary tree using +the algorithm given in Knuth Vol 3 page 455. + +The routines make use of uschar * pointers as byte pointers, +so as to be able to do arithmetic on them, since ANSI Standard +C does not permit additions and subtractions on void pointers. */ + + +/************************************************* +* Flags and Parameters * +*************************************************/ + +#define tree_lbal 1 /* left subtree is longer */ +#define tree_rbal 2 /* right subtree is longer */ +#define tree_bmask 3 /* mask for flipping bits */ + + +/************************************************* +* Insert a new node into a tree * +*************************************************/ + +/* The node->name field must (obviously) be set, but the other +fields need not be initialized. + +Arguments: + treebase pointer to the root of the tree + node the note to insert, with name field set + +Returns: TRUE if node inserted; FALSE if not (duplicate) +*/ + +int +tree_insertnode(tree_node **treebase, tree_node *node) +{ +tree_node *p = *treebase; +tree_node **q, *r, *s, **t; +int a; + +node->left = node->right = NULL; +node->balance = 0; + +/* Deal with an empty tree */ + +if (p == NULL) + { + *treebase = node; + return TRUE; + } + +/* The tree is not empty. While finding the insertion point, +q points to the pointer to p, and t points to the pointer to +the potential re-balancing point. */ + +q = treebase; +t = q; + +/* Loop to search tree for place to insert new node */ + +for (;;) + { + int c = Ustrcmp(node->name, p->name); + if (c == 0) return FALSE; /* Duplicate node encountered */ + + /* Deal with climbing down the tree, exiting from the loop + when we reach a leaf. */ + + q = (c > 0)? &(p->right) : &(p->left); + p = *q; + if (p == NULL) break; + + /* Save the address of the pointer to the last node en route + which has a non-zero balance factor. */ + + if (p->balance != 0) t = q; + } + +/* When the above loop completes, q points to the pointer to NULL; +that is the place at which the new node must be inserted. */ + +*q = node; + +/* Set up s as the potential re-balancing point, and r as the +next node after it along the route. */ + +s = *t; +r = (Ustrcmp(node->name, s->name) > 0)? s->right : s->left; + +/* Adjust balance factors along the route from s to node. */ + +p = r; + +while (p != node) + { + if (Ustrcmp(node->name, p->name) < 0) + { + p->balance = tree_lbal; + p = p->left; + } + else + { + p->balance = tree_rbal; + p = p->right; + } + } + +/* Now the World-Famous Balancing Act */ + +a = (Ustrcmp(node->name, s->name) < 0)? tree_lbal : tree_rbal; + +if (s->balance == 0) s->balance = (uschar)a; /* The tree has grown higher */ + else if (s->balance != (uschar)a) s->balance = 0; /* It's become more balanced */ +else /* It's got out of balance */ + { + /* Perform a single rotation */ + + if (r->balance == (uschar)a) + { + p = r; + if (a == tree_rbal) + { + s->right = r->left; + r->left = s; + } + else + { + s->left = r->right; + r->right = s; + } + s->balance = 0; + r->balance = 0; + } + + /* Perform a double rotation There was an occasion when the balancing + factors were screwed up by a bug in the code that reads a tree from + the spool. In case this ever happens again, check for changing p to NULL + and don't do it. It is better to have an unbalanced tree than a crash. */ + + else + { + if (a == tree_rbal) + { + if (r->left == NULL) return TRUE; /* Bail out if tree corrupt */ + p = r->left; + r->left = p->right; + p->right = r; + s->right = p->left; + p->left = s; + } + else + { + if (r->right == NULL) return TRUE; /* Bail out if tree corrupt */ + p = r->right; + r->right = p->left; + p->left = r; + s->left = p->right; + p->right = s; + } + + s->balance = (p->balance == (uschar)a)? (uschar)(a^tree_bmask) : 0; + r->balance = (p->balance == (uschar)(a^tree_bmask))? (uschar)a : 0; + p->balance = 0; + } + + /* Finishing touch */ + + *t = p; + } + +return TRUE; /* Successful insertion */ +} + + + +/************************************************* +* Search tree for node by name * +*************************************************/ + +/* +Arguments: + p root of tree + name key to search for + +Returns: pointer to node, or NULL if not found +*/ + +tree_node * +tree_search(tree_node *p, uschar *name) +{ +while (p != NULL) + { + int c = Ustrcmp(name, p->name); + if (c == 0) return p; + p = (c < 0)? p->left : p->right; + } +return NULL; +} + + +/* End of tree.c */ |