SPDX: Mass-update to GPL-2.0-or-later

[exim.git] / src / src / tree.c

diff --git a/src/src/tree.c b/src/src/tree.c
index b5918a6a36528032b5d860ff7890546f4153c97a..13fc28cc2414df21d1f1c80128b5c14b08641433 100644 (file)
--- a/src/src/tree.c
+++ b/src/src/tree.c
@@ -2,8 +2,10 @@
 *     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. */
+/* SPDX-License-Identifier: GPL-2.0-or-later */
 
 /* Functions for maintaining binary balanced trees and some associated
 functions as well. */
@@ -12,7 +14,6 @@ functions as well. */
 #include "exim.h"
 
 
-#ifndef MACRO_PREDEF
 
 
 /*************************************************
@@ -28,12 +29,13 @@ Returns:  nothing
 */
 
 void
-tree_add_nonrecipient(uschar *s)
+tree_add_nonrecipient(const uschar *s)
 {
-tree_node *node = store_get(sizeof(tree_node) + Ustrlen(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(node);
+if (!tree_insertnode(&tree_nonrecipients, node)) store_reset(rpoint);
 }
 
 
@@ -52,12 +54,13 @@ Returns:  nothing
 */
 
 void
-tree_add_duplicate(uschar *s, address_item *addr)
+tree_add_duplicate(const uschar *s, address_item *addr)
 {
-tree_node *node = store_get(sizeof(tree_node) + Ustrlen(s));
+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(node);
+if (!tree_insertnode(&tree_duplicates, node)) store_reset(rpoint);
 }
 
 
@@ -73,16 +76,18 @@ Returns:     nothing
 */
 
 void
-tree_add_unusable(host_item *h)
+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));
+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(node);
+if (!tree_insertnode(&tree_unusable, node)) store_reset(rpoint);
 }
 
 
@@ -116,9 +121,10 @@ Returns:     nothing
 static void
 write_tree(tree_node *p, FILE *f)
 {
-fprintf(f, "%c%c %s\n", p->left ? 'Y':'N', p->right ? 'Y':'N', p->name);
-if (p->left) write_tree(p->left, f);
-if (p->right) write_tree(p->right, 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. */
@@ -126,7 +132,7 @@ if (p->right) write_tree(p->right, f);
 void
 tree_write(tree_node *p, FILE *f)
 {
-if (!p)
+if (p == NULL)
   {
   fprintf(f, "XX\n");
   return;
@@ -135,7 +141,6 @@ write_tree(p, f);
 }
 
 
-#endif
 
 
 
@@ -186,7 +191,7 @@ node->balance = 0;
 
 /* Deal with an empty tree */
 
-if (!p)
+if (p == NULL)
   {
   *treebase = node;
   return TRUE;
@@ -209,9 +214,9 @@ for (;;)
   /* Deal with climbing down the tree, exiting from the loop
   when we reach a leaf. */
 
-  q = c > 0 ? &p->right : &p->left;
+  q = (c > 0)? &(p->right) : &(p->left);
   p = *q;
-  if (!p) break;
+  if (p == NULL) break;
 
   /* Save the address of the pointer to the last node en route
   which has a non-zero balance factor. */
@@ -228,13 +233,14 @@ that is the place at which the new node must be inserted. */
 next node after it along the route. */
 
 s = *t;
-r = Ustrcmp(node->name, s->name) > 0 ? s->right : s->left;
+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;
@@ -245,16 +251,15 @@ while (p != node)
     p->balance = tree_rbal;
     p = p->right;
     }
+  }
 
 /* Now the World-Famous Balancing Act */
 
-a = Ustrcmp(node->name, s->name) < 0 ? tree_lbal : tree_rbal;
+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 */
+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 */
 
@@ -284,7 +289,7 @@ else                                                /* It's got out of balance */
     {
     if (a == tree_rbal)
       {
-      if (!r->left) return TRUE;   /* Bail out if tree corrupt */
+      if (r->left == NULL) return TRUE;   /* Bail out if tree corrupt */
       p = r->left;
       r->left = p->right;
       p->right = r;
@@ -293,7 +298,7 @@ else                                                /* It's got out of balance */
       }
     else
       {
-      if (!r->right) return TRUE;  /* Bail out if tree corrupt */
+      if (r->right == NULL) return TRUE;  /* Bail out if tree corrupt */
       p = r->right;
       r->right = p->left;
       p->left = r;
@@ -301,8 +306,8 @@ else                                                /* It's got out of balance */
       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;
+    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;
     }
 
@@ -331,15 +336,16 @@ Returns:    pointer to node, or NULL if not found
 tree_node *
 tree_search(tree_node *p, const uschar *name)
 {
-int c;
-for ( ; p; p = c < 0 ? p->left : p->right)
-  if ((c = Ustrcmp(name, p->name)) == 0)
-    return p;
+while (p)
+  {
+  int c = Ustrcmp(name, p->name);
+  if (c == 0) return p;
+  p = c < 0 ? p->left : p->right;
+  }
 return NULL;
 }
 
 
-#ifndef MACRO_PREDEF
 
 /*************************************************
 *   Walk tree recursively and execute function   *
@@ -361,6 +367,28 @@ tree_walk(p->left, f, ctx);
 tree_walk(p->right, f, ctx);
 }
 
-#endif
+
+
+/* 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 */