1 files changed, 393 insertions, 0 deletions
diff --git a/src/tree.c b/src/tree.c
new file mode 100644
index 0000000..bb8ad44
--- /dev/null
+++ b/src/tree.c
@@ -0,0 +1,393 @@
+/*************************************************
+*     Exim - an Internet mail transport agent    *
+*************************************************/
+
+/* Copyright (c) The Exim Maintainers 2021 - 2022 */
+/* Copyright (c) University of Cambridge 1995 - 2015 */
+/* 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(const uschar *s)
+{
+rmark rpoint = store_mark();
+tree_node * node = store_get(sizeof(tree_node) + Ustrlen(s), s);
+Ustrcpy(node->name, s);
+node->data.ptr = NULL;
+if (!tree_insertnode(&tree_nonrecipients, node)) store_reset(rpoint);
+}
+
+
+
+/*************************************************
+*        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(const uschar *s, address_item *addr)
+{
+rmark rpoint = store_mark();
+tree_node * node = store_get(sizeof(tree_node) + Ustrlen(s), s);
+Ustrcpy(node->name, s);
+node->data.ptr = addr;
+if (!tree_insertnode(&tree_duplicates, node)) store_reset(rpoint);
+}
+
+
+
+/*************************************************
+*    Add entry to unusable addresses tree        *
+*************************************************/
+
+/* Duplicates are simply discarded.
+
+Argument:    the host item
+Returns:     nothing
+*/
+
+void
+tree_add_unusable(const host_item *h)
+{
+rmark rpoint = store_mark();
+tree_node *node;
+uschar s[256];
+sprintf(CS s, "T:%.200s:%s", h->name, h->address);
+node = store_get(sizeof(tree_node) + Ustrlen(s),
+	    is_tainted(h->name) || is_tainted(h->address) ? GET_TAINTED : GET_UNTAINTED);
+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(rpoint);
+}
+
+
+
+/*************************************************
+*        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, const uschar *name)
+{
+while (p)
+  {
+  int c = Ustrcmp(name, p->name);
+  if (c == 0) return p;
+  p = c < 0 ? p->left : p->right;
+  }
+return NULL;
+}
+
+
+
+/*************************************************
+*   Walk tree recursively and execute function   *
+*************************************************/
+
+/*
+Arguments:
+  p       root of the tree
+  f       function to execute for each name-value-pair
+  ctx     context data for f
+*/
+
+void
+tree_walk(tree_node *p, void (*f)(uschar*, uschar*, void*), void *ctx)
+{
+if (!p) return;
+f(p->name, p->data.ptr, ctx);
+tree_walk(p->left, f, ctx);
+tree_walk(p->right, f, ctx);
+}
+
+
+
+/* Add a node to a tree, ignoring possibility of duplicates */
+
+static void
+tree_add_var(uschar * name, uschar * val, void * ctx)
+{
+tree_node ** root = ctx;
+tree_node * node = store_get(sizeof(tree_node) + Ustrlen(name), name);
+Ustrcpy(node->name, name);
+node->data.ptr = val;
+(void) tree_insertnode(root, node);
+}
+
+/* Duplicate a tree */
+
+void
+tree_dup(tree_node ** dstp, tree_node * src)
+{
+tree_walk(src, tree_add_var, dstp);
+}
+
+
+
+/* End of tree.c */