/src/unbound/util/rbtree.c

Source (jump to first uncovered line)
/*
 * rbtree.c -- generic red black tree
 *
 * Copyright (c) 2001-2007, NLnet Labs. All rights reserved.
 * 
 * This software is open source.
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 
 * Redistributions of source code must retain the above copyright notice,
 * this list of conditions and the following disclaimer.
 * 
 * Redistributions in binary form must reproduce the above copyright notice,
 * this list of conditions and the following disclaimer in the documentation
 * and/or other materials provided with the distribution.
 * 
 * Neither the name of the NLNET LABS nor the names of its contributors may
 * be used to endorse or promote products derived from this software without
 * specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 */

/**
 * \file
 * Implementation of a redblack tree.
 */

#include "config.h"
#include "log.h"
#include "fptr_wlist.h"
#include "util/rbtree.h"

/** Node colour black */
#define BLACK 0
/** Node colour red */
#define RED 1

/** the NULL node, global alloc */
rbnode_type rbtree_null_node = {
  RBTREE_NULL,    /* Parent.  */
  RBTREE_NULL,    /* Left.  */
  RBTREE_NULL,    /* Right.  */
  NULL,     /* Key.  */
  BLACK     /* Color.  */
};

/** rotate subtree left (to preserve redblack property) */
static void rbtree_rotate_left(rbtree_type *rbtree, rbnode_type *node);
/** rotate subtree right (to preserve redblack property) */
static void rbtree_rotate_right(rbtree_type *rbtree, rbnode_type *node);
/** Fixup node colours when insert happened */
static void rbtree_insert_fixup(rbtree_type *rbtree, rbnode_type *node);
/** Fixup node colours when delete happened */
static void rbtree_delete_fixup(rbtree_type* rbtree, rbnode_type* child,
  rbnode_type* child_parent);

/*
 * Creates a new red black tree, initializes and returns a pointer to it.
 *
 * Return NULL on failure.
 *
 */
rbtree_type *
rbtree_create (int (*cmpf)(const void *, const void *))
{
  rbtree_type *rbtree;

  /* Allocate memory for it */
  rbtree = (rbtree_type *) malloc(sizeof(rbtree_type));
  if (!rbtree) {
    return NULL;
  }

  /* Initialize it */
  rbtree_init(rbtree, cmpf);

  return rbtree;
}

void 
rbtree_init(rbtree_type *rbtree, int (*cmpf)(const void *, const void *))
{
  /* Initialize it */
  rbtree->root = RBTREE_NULL;
  rbtree->count = 0;
  rbtree->cmp = cmpf;
}

/*
 * Rotates the node to the left.
 *
 */
static void
rbtree_rotate_left(rbtree_type *rbtree, rbnode_type *node)
{
  rbnode_type *right = node->right;
  node->right = right->left;
  if (right->left != RBTREE_NULL)
    right->left->parent = node;

  right->parent = node->parent;

  if (node->parent != RBTREE_NULL) {
    if (node == node->parent->left) {
      node->parent->left = right;
    } else  {
      node->parent->right = right;
    }
  } else {
    rbtree->root = right;
  }
  right->left = node;
  node->parent = right;
}

/*
 * Rotates the node to the right.
 *
 */
static void
rbtree_rotate_right(rbtree_type *rbtree, rbnode_type *node)
{
  rbnode_type *left = node->left;
  node->left = left->right;
  if (left->right != RBTREE_NULL)
    left->right->parent = node;

  left->parent = node->parent;

  if (node->parent != RBTREE_NULL) {
    if (node == node->parent->right) {
      node->parent->right = left;
    } else  {
      node->parent->left = left;
    }
  } else {
    rbtree->root = left;
  }
  left->right = node;
  node->parent = left;
}

static void
rbtree_insert_fixup(rbtree_type *rbtree, rbnode_type *node)
{
  rbnode_type *uncle;

  /* While not at the root and need fixing... */
  while (node != rbtree->root && node->parent->color == RED) {
    /* If our parent is left child of our grandparent... */
    if (node->parent == node->parent->parent->left) {
      uncle = node->parent->parent->right;

      /* If our uncle is red... */
      if (uncle->color == RED) {
        /* Paint the parent and the uncle black... */
        node->parent->color = BLACK;
        uncle->color = BLACK;

        /* And the grandparent red... */
        node->parent->parent->color = RED;

        /* And continue fixing the grandparent */
        node = node->parent->parent;
      } else {       /* Our uncle is black... */
        /* Are we the right child? */
        if (node == node->parent->right) {
          node = node->parent;
          rbtree_rotate_left(rbtree, node);
        }
        /* Now we're the left child, repaint and rotate... */
        node->parent->color = BLACK;
        node->parent->parent->color = RED;
        rbtree_rotate_right(rbtree, node->parent->parent);
      }
    } else {
      uncle = node->parent->parent->left;

      /* If our uncle is red... */
      if (uncle->color == RED) {
        /* Paint the parent and the uncle black... */
        node->parent->color = BLACK;
        uncle->color = BLACK;

        /* And the grandparent red... */
        node->parent->parent->color = RED;

        /* And continue fixing the grandparent */
        node = node->parent->parent;
      } else {       /* Our uncle is black... */
        /* Are we the right child? */
        if (node == node->parent->left) {
          node = node->parent;
          rbtree_rotate_right(rbtree, node);
        }
        /* Now we're the right child, repaint and rotate... */
        node->parent->color = BLACK;
        node->parent->parent->color = RED;
        rbtree_rotate_left(rbtree, node->parent->parent);
      }
    }
  }
  rbtree->root->color = BLACK;
}


/*
 * Inserts a node into a red black tree.
 *
 * Returns NULL on failure or the pointer to the newly added node
 * otherwise.
 */
rbnode_type *
rbtree_insert (rbtree_type *rbtree, rbnode_type *data)
{
  /* XXX Not necessary, but keeps compiler quiet... */
  int r = 0;

  /* We start at the root of the tree */
  rbnode_type *node = rbtree->root;
  rbnode_type *parent = RBTREE_NULL;

  fptr_ok(fptr_whitelist_rbtree_cmp(rbtree->cmp));
  /* Lets find the new parent... */
  while (node != RBTREE_NULL) {
    /* Compare two keys, do we have a duplicate? */
    if ((r = rbtree->cmp(data->key, node->key)) == 0) {
      return NULL;
    }
    parent = node;

    if (r < 0) {
      node = node->left;
    } else {
      node = node->right;
    }
  }

  /* Initialize the new node */
  data->parent = parent;
  data->left = data->right = RBTREE_NULL;
  data->color = RED;
  rbtree->count++;

  /* Insert it into the tree... */
  if (parent != RBTREE_NULL) {
    if (r < 0) {
      parent->left = data;
    } else {
      parent->right = data;
    }
  } else {
    rbtree->root = data;
  }

  /* Fix up the red-black properties... */
  rbtree_insert_fixup(rbtree, data);

  return data;
}

/*
 * Searches the red black tree, returns the data if key is found or NULL otherwise.
 *
 */
rbnode_type *
rbtree_search (rbtree_type *rbtree, const void *key)
{
  rbnode_type *node;

  if (rbtree_find_less_equal(rbtree, key, &node)) {
    return node;
  } else {
    return NULL;
  }
}

/** helpers for delete: swap node colours */
static void swap_int8(uint8_t* x, uint8_t* y) 
{ 
  uint8_t t = *x; *x = *y; *y = t; 
}

/** helpers for delete: swap node pointers */
static void swap_np(rbnode_type** x, rbnode_type** y) 
{
  rbnode_type* t = *x; *x = *y; *y = t; 
}

/** Update parent pointers of child trees of 'parent' */
static void change_parent_ptr(rbtree_type* rbtree, rbnode_type* parent,
  rbnode_type* old, rbnode_type* new)
{
  if(parent == RBTREE_NULL)
  {
    log_assert(rbtree->root == old);
    if(rbtree->root == old) rbtree->root = new;
    return;
  }
  log_assert(parent->left == old || parent->right == old
    || parent->left == new || parent->right == new);
  if(parent->left == old) parent->left = new;
  if(parent->right == old) parent->right = new;
}
/** Update parent pointer of a node 'child' */
static void change_child_ptr(rbnode_type* child, rbnode_type* old,
  rbnode_type* new)
{
  if(child == RBTREE_NULL) return;
  log_assert(child->parent == old || child->parent == new);
  if(child->parent == old) child->parent = new;
}

rbnode_type* 
rbtree_delete(rbtree_type *rbtree, const void *key)
{
  rbnode_type *to_delete;
  rbnode_type *child;
  if((to_delete = rbtree_search(rbtree, key)) == 0) return 0;
  rbtree->count--;

  /* make sure we have at most one non-leaf child */
  if(to_delete->left != RBTREE_NULL && to_delete->right != RBTREE_NULL)
  {
    /* swap with smallest from right subtree (or largest from left) */
    rbnode_type *smright = to_delete->right;
    while(smright->left != RBTREE_NULL)
      smright = smright->left;
    /* swap the smright and to_delete elements in the tree,
     * but the rbnode_type is first part of user data struct
     * so cannot just swap the keys and data pointers. Instead
     * readjust the pointers left,right,parent */

    /* swap colors - colors are tied to the position in the tree */
    swap_int8(&to_delete->color, &smright->color);

    /* swap child pointers in parents of smright/to_delete */
    change_parent_ptr(rbtree, to_delete->parent, to_delete, smright);
    if(to_delete->right != smright)
      change_parent_ptr(rbtree, smright->parent, smright, to_delete);

    /* swap parent pointers in children of smright/to_delete */
    change_child_ptr(smright->left, smright, to_delete);
    change_child_ptr(smright->left, smright, to_delete);
    change_child_ptr(smright->right, smright, to_delete);
    change_child_ptr(smright->right, smright, to_delete);
    change_child_ptr(to_delete->left, to_delete, smright);
    if(to_delete->right != smright)
      change_child_ptr(to_delete->right, to_delete, smright);
    if(to_delete->right == smright)
    {
      /* set up so after swap they work */
      to_delete->right = to_delete;
      smright->parent = smright;
    }

    /* swap pointers in to_delete/smright nodes */
    swap_np(&to_delete->parent, &smright->parent);
    swap_np(&to_delete->left, &smright->left);
    swap_np(&to_delete->right, &smright->right);

    /* now delete to_delete (which is at the location where the smright previously was) */
  }
  log_assert(to_delete->left == RBTREE_NULL || to_delete->right == RBTREE_NULL);

  if(to_delete->left != RBTREE_NULL) child = to_delete->left;
  else child = to_delete->right;

  /* unlink to_delete from the tree, replace to_delete with child */
  change_parent_ptr(rbtree, to_delete->parent, to_delete, child);
  change_child_ptr(child, to_delete, to_delete->parent);

  if(to_delete->color == RED)
  {
    /* if node is red then the child (black) can be swapped in */
  }
  else if(child->color == RED)
  {
    /* change child to BLACK, removing a RED node is no problem */
    if(child!=RBTREE_NULL) child->color = BLACK;
  }
  else rbtree_delete_fixup(rbtree, child, to_delete->parent);

  /* unlink completely */
  to_delete->parent = RBTREE_NULL;
  to_delete->left = RBTREE_NULL;
  to_delete->right = RBTREE_NULL;
  to_delete->color = BLACK;
  return to_delete;
}

static void rbtree_delete_fixup(rbtree_type* rbtree, rbnode_type* child,
  rbnode_type* child_parent)
{
  rbnode_type* sibling;
  int go_up = 1;

  /* determine sibling to the node that is one-black short */
  if(child_parent->right == child) sibling = child_parent->left;
  else sibling = child_parent->right;

  while(go_up)
  {
    if(child_parent == RBTREE_NULL)
    {
      /* removed parent==black from root, every path, so ok */
      return;
    }

    if(sibling->color == RED)
    { /* rotate to get a black sibling */
      child_parent->color = RED;
      sibling->color = BLACK;
      if(child_parent->right == child)
        rbtree_rotate_right(rbtree, child_parent);
      else  rbtree_rotate_left(rbtree, child_parent);
      /* new sibling after rotation */
      if(child_parent->right == child) sibling = child_parent->left;
      else sibling = child_parent->right;
    }

    if(child_parent->color == BLACK 
      && sibling->color == BLACK
      && sibling->left->color == BLACK
      && sibling->right->color == BLACK)
    { /* fixup local with recolor of sibling */
      if(sibling != RBTREE_NULL)
        sibling->color = RED;

      child = child_parent;
      child_parent = child_parent->parent;
      /* prepare to go up, new sibling */
      if(child_parent->right == child) sibling = child_parent->left;
      else sibling = child_parent->right;
    }
    else go_up = 0;
  }

  if(child_parent->color == RED
    && sibling->color == BLACK
    && sibling->left->color == BLACK
    && sibling->right->color == BLACK) 
  {
    /* move red to sibling to rebalance */
    if(sibling != RBTREE_NULL)
      sibling->color = RED;
    child_parent->color = BLACK;
    return;
  }
  log_assert(sibling != RBTREE_NULL);

  /* get a new sibling, by rotating at sibling. See which child
     of sibling is red */
  if(child_parent->right == child
    && sibling->color == BLACK
    && sibling->right->color == RED
    && sibling->left->color == BLACK)
  {
    sibling->color = RED;
    sibling->right->color = BLACK;
    rbtree_rotate_left(rbtree, sibling);
    /* new sibling after rotation */
    if(child_parent->right == child) sibling = child_parent->left;
    else sibling = child_parent->right;
  }
  else if(child_parent->left == child
    && sibling->color == BLACK
    && sibling->left->color == RED
    && sibling->right->color == BLACK)
  {
    sibling->color = RED;
    sibling->left->color = BLACK;
    rbtree_rotate_right(rbtree, sibling);
    /* new sibling after rotation */
    if(child_parent->right == child) sibling = child_parent->left;
    else sibling = child_parent->right;
  }

  /* now we have a black sibling with a red child. rotate and exchange colors. */
  sibling->color = child_parent->color;
  child_parent->color = BLACK;
  if(child_parent->right == child)
  {
    log_assert(sibling->left->color == RED);
    sibling->left->color = BLACK;
    rbtree_rotate_right(rbtree, child_parent);
  }
  else
  {
    log_assert(sibling->right->color == RED);
    sibling->right->color = BLACK;
    rbtree_rotate_left(rbtree, child_parent);
  }
}

int
rbtree_find_less_equal(rbtree_type *rbtree, const void *key,
  rbnode_type **result)
{
  int r;
  rbnode_type *node;

  log_assert(result);
  
  /* We start at root... */
  node = rbtree->root;

  *result = NULL;
  fptr_ok(fptr_whitelist_rbtree_cmp(rbtree->cmp));

  /* While there are children... */
  while (node != RBTREE_NULL) {
    r = rbtree->cmp(key, node->key);
    if (r == 0) {
      /* Exact match */
      *result = node;
      return 1;
    } 
    if (r < 0) {
      node = node->left;
    } else {
      /* Temporary match */
      *result = node;
      node = node->right;
    }
  }
  return 0;
}

/*
 * Finds the first element in the red black tree
 *
 */
rbnode_type *
rbtree_first (rbtree_type *rbtree)
{
  rbnode_type *node;

  for (node = rbtree->root; node->left != RBTREE_NULL; node = node->left);
  return node;
}

rbnode_type *
rbtree_last (rbtree_type *rbtree)
{
  rbnode_type *node;

  for (node = rbtree->root; node->right != RBTREE_NULL; node = node->right);
  return node;
}

/*
 * Returns the next node...
 *
 */
rbnode_type *
rbtree_next (rbnode_type *node)
{
  rbnode_type *parent;

  if (node->right != RBTREE_NULL) {
    /* One right, then keep on going left... */
    for (node = node->right; node->left != RBTREE_NULL; node = node->left);
  } else {
    parent = node->parent;
    while (parent != RBTREE_NULL && node == parent->right) {
      node = parent;
      parent = parent->parent;
    }
    node = parent;
  }
  return node;
}

rbnode_type *
rbtree_previous(rbnode_type *node)
{
  rbnode_type *parent;

  if (node->left != RBTREE_NULL) {
    /* One left, then keep on going right... */
    for (node = node->left; node->right != RBTREE_NULL; node = node->right);
  } else {
    parent = node->parent;
    while (parent != RBTREE_NULL && node == parent->left) {
      node = parent;
      parent = parent->parent;
    }
    node = parent;
  }
  return node;
}

/** recursive descent traverse */
static void 
traverse_post(void (*func)(rbnode_type*, void*), void* arg, rbnode_type* node)
{
  if(!node || node == RBTREE_NULL)
    return;
  /* recurse */
  traverse_post(func, arg, node->left);
  traverse_post(func, arg, node->right);
  /* call user func */
  (*func)(node, arg);
}

void 
traverse_postorder(rbtree_type* tree, void (*func)(rbnode_type*, void*),
  void* arg)
{
  traverse_post(func, arg, tree->root);
}

Coverage Report

Created: 2023-06-07 06:25

Line	Count	Source (jump to first uncovered line)
1		/*
2		* rbtree.c -- generic red black tree
3		*
4		* Copyright (c) 2001-2007, NLnet Labs. All rights reserved.
5		*
6		* This software is open source.
7		*
8		* Redistribution and use in source and binary forms, with or without
9		* modification, are permitted provided that the following conditions
10		* are met:
11		*
12		* Redistributions of source code must retain the above copyright notice,
13		* this list of conditions and the following disclaimer.
14		*
15		* Redistributions in binary form must reproduce the above copyright notice,
16		* this list of conditions and the following disclaimer in the documentation
17		* and/or other materials provided with the distribution.
18		*
19		* Neither the name of the NLNET LABS nor the names of its contributors may
20		* be used to endorse or promote products derived from this software without
21		* specific prior written permission.
22		*
23		* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
24		* "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
25		* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
26		* A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
27		* HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
28		* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
29		* TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
30		* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
31		* LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
32		* NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
33		* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
34		*
35		*/
36
37		/**
38		* \file
39		* Implementation of a redblack tree.
40		*/
41
42		#include "config.h"
43		#include "log.h"
44		#include "fptr_wlist.h"
45		#include "util/rbtree.h"
46
47		/** Node colour black */
48	0	#define BLACK 0
49		/** Node colour red */
50	0	#define RED 1
51
52		/** the NULL node, global alloc */
53		rbnode_type rbtree_null_node = {
54		RBTREE_NULL, /* Parent. */
55		RBTREE_NULL, /* Left. */
56		RBTREE_NULL, /* Right. */
57		NULL, /* Key. */
58		BLACK /* Color. */
59		};
60
61		/** rotate subtree left (to preserve redblack property) */
62		static void rbtree_rotate_left(rbtree_type rbtree, rbnode_type node);
63		/** rotate subtree right (to preserve redblack property) */
64		static void rbtree_rotate_right(rbtree_type rbtree, rbnode_type node);
65		/** Fixup node colours when insert happened */
66		static void rbtree_insert_fixup(rbtree_type rbtree, rbnode_type node);
67		/** Fixup node colours when delete happened */
68		static void rbtree_delete_fixup(rbtree_type* rbtree, rbnode_type* child,
69		rbnode_type* child_parent);
70
71		/*
72		* Creates a new red black tree, initializes and returns a pointer to it.
73		*
74		* Return NULL on failure.
75		*
76		*/
77		rbtree_type *
78		rbtree_create (int (cmpf)(const void , const void *))
79	4.66k	{
80	4.66k	rbtree_type *rbtree;
81
82		/* Allocate memory for it */
83	4.66k	rbtree = (rbtree_type *) malloc(sizeof(rbtree_type));
84	4.66k	if (!rbtree) {
85	0	return NULL;
86	0	}
87
88		/* Initialize it */
89	4.66k	rbtree_init(rbtree, cmpf);
90
91	4.66k	return rbtree;
92	4.66k	}
93
94		void
95		rbtree_init(rbtree_type rbtree, int (cmpf)(const void , const void ))
96	4.66k	{
97		/* Initialize it */
98	4.66k	rbtree->root = RBTREE_NULL;
99	4.66k	rbtree->count = 0;
100	4.66k	rbtree->cmp = cmpf;
101	4.66k	}
102
103		/*
104		* Rotates the node to the left.
105		*
106		*/
107		static void
108		rbtree_rotate_left(rbtree_type rbtree, rbnode_type node)
109	0	{
110	0	rbnode_type *right = node->right;
111	0	node->right = right->left;
112	0	if (right->left != RBTREE_NULL)
113	0	right->left->parent = node;
114
115	0	right->parent = node->parent;
116
117	0	if (node->parent != RBTREE_NULL) {
118	0	if (node == node->parent->left) {
119	0	node->parent->left = right;
120	0	} else {
121	0	node->parent->right = right;
122	0	}
123	0	} else {
124	0	rbtree->root = right;
125	0	}
126	0	right->left = node;
127	0	node->parent = right;
128	0	}
129
130		/*
131		* Rotates the node to the right.
132		*
133		*/
134		static void
135		rbtree_rotate_right(rbtree_type rbtree, rbnode_type node)
136	0	{
137	0	rbnode_type *left = node->left;
138	0	node->left = left->right;
139	0	if (left->right != RBTREE_NULL)
140	0	left->right->parent = node;
141
142	0	left->parent = node->parent;
143
144	0	if (node->parent != RBTREE_NULL) {
145	0	if (node == node->parent->right) {
146	0	node->parent->right = left;
147	0	} else {
148	0	node->parent->left = left;
149	0	}
150	0	} else {
151	0	rbtree->root = left;
152	0	}
153	0	left->right = node;
154	0	node->parent = left;
155	0	}
156
157		static void
158		rbtree_insert_fixup(rbtree_type rbtree, rbnode_type node)
159	0	{
160	0	rbnode_type *uncle;
161
162		/* While not at the root and need fixing... */
163	0	while (node != rbtree->root && node->parent->color == RED) {
164		/* If our parent is left child of our grandparent... */
165	0	if (node->parent == node->parent->parent->left) {
166	0	uncle = node->parent->parent->right;
167
168		/* If our uncle is red... */
169	0	if (uncle->color == RED) {
170		/* Paint the parent and the uncle black... */
171	0	node->parent->color = BLACK;
172	0	uncle->color = BLACK;
173
174		/* And the grandparent red... */
175	0	node->parent->parent->color = RED;
176
177		/* And continue fixing the grandparent */
178	0	node = node->parent->parent;
179	0	} else { /* Our uncle is black... */
180		/* Are we the right child? */
181	0	if (node == node->parent->right) {
182	0	node = node->parent;
183	0	rbtree_rotate_left(rbtree, node);
184	0	}
185		/* Now we're the left child, repaint and rotate... */
186	0	node->parent->color = BLACK;
187	0	node->parent->parent->color = RED;
188	0	rbtree_rotate_right(rbtree, node->parent->parent);
189	0	}
190	0	} else {
191	0	uncle = node->parent->parent->left;
192
193		/* If our uncle is red... */
194	0	if (uncle->color == RED) {
195		/* Paint the parent and the uncle black... */
196	0	node->parent->color = BLACK;
197	0	uncle->color = BLACK;
198
199		/* And the grandparent red... */
200	0	node->parent->parent->color = RED;
201
202		/* And continue fixing the grandparent */
203	0	node = node->parent->parent;
204	0	} else { /* Our uncle is black... */
205		/* Are we the right child? */
206	0	if (node == node->parent->left) {
207	0	node = node->parent;
208	0	rbtree_rotate_right(rbtree, node);
209	0	}
210		/* Now we're the right child, repaint and rotate... */
211	0	node->parent->color = BLACK;
212	0	node->parent->parent->color = RED;
213	0	rbtree_rotate_left(rbtree, node->parent->parent);
214	0	}
215	0	}
216	0	}
217	0	rbtree->root->color = BLACK;
218	0	}
219
220
221		/*
222		* Inserts a node into a red black tree.
223		*
224		* Returns NULL on failure or the pointer to the newly added node
225		* otherwise.
226		*/
227		rbnode_type *
228		rbtree_insert (rbtree_type rbtree, rbnode_type data)
229	0	{
230		/* XXX Not necessary, but keeps compiler quiet... */
231	0	int r = 0;
232
233		/* We start at the root of the tree */
234	0	rbnode_type *node = rbtree->root;
235	0	rbnode_type *parent = RBTREE_NULL;
236
237	0	fptr_ok(fptr_whitelist_rbtree_cmp(rbtree->cmp));
238		/* Lets find the new parent... */
239	0	while (node != RBTREE_NULL) {
240		/* Compare two keys, do we have a duplicate? */
241	0	if ((r = rbtree->cmp(data->key, node->key)) == 0) {
242	0	return NULL;
243	0	}
244	0	parent = node;
245
246	0	if (r < 0) {
247	0	node = node->left;
248	0	} else {
249	0	node = node->right;
250	0	}
251	0	}
252
253		/* Initialize the new node */
254	0	data->parent = parent;
255	0	data->left = data->right = RBTREE_NULL;
256	0	data->color = RED;
257	0	rbtree->count++;
258
259		/* Insert it into the tree... */
260	0	if (parent != RBTREE_NULL) {
261	0	if (r < 0) {
262	0	parent->left = data;
263	0	} else {
264	0	parent->right = data;
265	0	}
266	0	} else {
267	0	rbtree->root = data;
268	0	}
269
270		/* Fix up the red-black properties... */
271	0	rbtree_insert_fixup(rbtree, data);
272
273	0	return data;
274	0	}
275
276		/*
277		* Searches the red black tree, returns the data if key is found or NULL otherwise.
278		*
279		*/
280		rbnode_type *
281		rbtree_search (rbtree_type rbtree, const void key)
282	0	{
283	0	rbnode_type *node;
284
285	0	if (rbtree_find_less_equal(rbtree, key, &node)) {
286	0	return node;
287	0	} else {
288	0	return NULL;
289	0	}
290	0	}
291
292		/** helpers for delete: swap node colours */
293		static void swap_int8(uint8_t* x, uint8_t* y)
294	0	{
295	0	uint8_t t = x; x = y; y = t;
296	0	}
297
298		/** helpers for delete: swap node pointers */
299		static void swap_np(rbnode_type x, rbnode_type y)
300	0	{
301	0	rbnode_type* t = x; x = y; y = t;
302	0	}
303
304		/** Update parent pointers of child trees of 'parent' */
305		static void change_parent_ptr(rbtree_type* rbtree, rbnode_type* parent,
306		rbnode_type* old, rbnode_type* new)
307	0	{
308	0	if(parent == RBTREE_NULL)
309	0	{
310	0	log_assert(rbtree->root == old);
311	0	if(rbtree->root == old) rbtree->root = new;
312	0	return;
313	0	}
314	0	log_assert(parent->left == old \|\| parent->right == old
315	0	\|\| parent->left == new \|\| parent->right == new);
316	0	if(parent->left == old) parent->left = new;
317	0	if(parent->right == old) parent->right = new;
318	0	}
319		/** Update parent pointer of a node 'child' */
320		static void change_child_ptr(rbnode_type* child, rbnode_type* old,
321		rbnode_type* new)
322	0	{
323	0	if(child == RBTREE_NULL) return;
324	0	log_assert(child->parent == old \|\| child->parent == new);
325	0	if(child->parent == old) child->parent = new;
326	0	}
327
328		rbnode_type*
329		rbtree_delete(rbtree_type rbtree, const void key)
330	0	{
331	0	rbnode_type *to_delete;
332	0	rbnode_type *child;
333	0	if((to_delete = rbtree_search(rbtree, key)) == 0) return 0;
334	0	rbtree->count--;
335
336		/* make sure we have at most one non-leaf child */
337	0	if(to_delete->left != RBTREE_NULL && to_delete->right != RBTREE_NULL)
338	0	{
339		/* swap with smallest from right subtree (or largest from left) */
340	0	rbnode_type *smright = to_delete->right;
341	0	while(smright->left != RBTREE_NULL)
342	0	smright = smright->left;
343		/* swap the smright and to_delete elements in the tree,
344		* but the rbnode_type is first part of user data struct
345		* so cannot just swap the keys and data pointers. Instead
346		* readjust the pointers left,right,parent */
347
348		/* swap colors - colors are tied to the position in the tree */
349	0	swap_int8(&to_delete->color, &smright->color);
350
351		/* swap child pointers in parents of smright/to_delete */
352	0	change_parent_ptr(rbtree, to_delete->parent, to_delete, smright);
353	0	if(to_delete->right != smright)
354	0	change_parent_ptr(rbtree, smright->parent, smright, to_delete);
355
356		/* swap parent pointers in children of smright/to_delete */
357	0	change_child_ptr(smright->left, smright, to_delete);
358	0	change_child_ptr(smright->left, smright, to_delete);
359	0	change_child_ptr(smright->right, smright, to_delete);
360	0	change_child_ptr(smright->right, smright, to_delete);
361	0	change_child_ptr(to_delete->left, to_delete, smright);
362	0	if(to_delete->right != smright)
363	0	change_child_ptr(to_delete->right, to_delete, smright);
364	0	if(to_delete->right == smright)
365	0	{
366		/* set up so after swap they work */
367	0	to_delete->right = to_delete;
368	0	smright->parent = smright;
369	0	}
370
371		/* swap pointers in to_delete/smright nodes */
372	0	swap_np(&to_delete->parent, &smright->parent);
373	0	swap_np(&to_delete->left, &smright->left);
374	0	swap_np(&to_delete->right, &smright->right);
375
376		/* now delete to_delete (which is at the location where the smright previously was) */
377	0	}
378	0	log_assert(to_delete->left == RBTREE_NULL \|\| to_delete->right == RBTREE_NULL);
379
380	0	if(to_delete->left != RBTREE_NULL) child = to_delete->left;
381	0	else child = to_delete->right;
382
383		/* unlink to_delete from the tree, replace to_delete with child */
384	0	change_parent_ptr(rbtree, to_delete->parent, to_delete, child);
385	0	change_child_ptr(child, to_delete, to_delete->parent);
386
387	0	if(to_delete->color == RED)
388	0	{
389		/* if node is red then the child (black) can be swapped in */
390	0	}
391	0	else if(child->color == RED)
392	0	{
393		/* change child to BLACK, removing a RED node is no problem */
394	0	if(child!=RBTREE_NULL) child->color = BLACK;
395	0	}
396	0	else rbtree_delete_fixup(rbtree, child, to_delete->parent);
397
398		/* unlink completely */
399	0	to_delete->parent = RBTREE_NULL;
400	0	to_delete->left = RBTREE_NULL;
401	0	to_delete->right = RBTREE_NULL;
402	0	to_delete->color = BLACK;
403	0	return to_delete;
404	0	}
405
406		static void rbtree_delete_fixup(rbtree_type* rbtree, rbnode_type* child,
407		rbnode_type* child_parent)
408	0	{
409	0	rbnode_type* sibling;
410	0	int go_up = 1;
411
412		/* determine sibling to the node that is one-black short */
413	0	if(child_parent->right == child) sibling = child_parent->left;
414	0	else sibling = child_parent->right;
415
416	0	while(go_up)
417	0	{
418	0	if(child_parent == RBTREE_NULL)
419	0	{
420		/* removed parent==black from root, every path, so ok */
421	0	return;
422	0	}
423
424	0	if(sibling->color == RED)
425	0	{ /* rotate to get a black sibling */
426	0	child_parent->color = RED;
427	0	sibling->color = BLACK;
428	0	if(child_parent->right == child)
429	0	rbtree_rotate_right(rbtree, child_parent);
430	0	else rbtree_rotate_left(rbtree, child_parent);
431		/* new sibling after rotation */
432	0	if(child_parent->right == child) sibling = child_parent->left;
433	0	else sibling = child_parent->right;
434	0	}
435
436	0	if(child_parent->color == BLACK
437	0	&& sibling->color == BLACK
438	0	&& sibling->left->color == BLACK
439	0	&& sibling->right->color == BLACK)
440	0	{ /* fixup local with recolor of sibling */
441	0	if(sibling != RBTREE_NULL)
442	0	sibling->color = RED;
443
444	0	child = child_parent;
445	0	child_parent = child_parent->parent;
446		/* prepare to go up, new sibling */
447	0	if(child_parent->right == child) sibling = child_parent->left;
448	0	else sibling = child_parent->right;
449	0	}
450	0	else go_up = 0;
451	0	}
452
453	0	if(child_parent->color == RED
454	0	&& sibling->color == BLACK
455	0	&& sibling->left->color == BLACK
456	0	&& sibling->right->color == BLACK)
457	0	{
458		/* move red to sibling to rebalance */
459	0	if(sibling != RBTREE_NULL)
460	0	sibling->color = RED;
461	0	child_parent->color = BLACK;
462	0	return;
463	0	}
464	0	log_assert(sibling != RBTREE_NULL);
465
466		/* get a new sibling, by rotating at sibling. See which child
467		of sibling is red */
468	0	if(child_parent->right == child
469	0	&& sibling->color == BLACK
470	0	&& sibling->right->color == RED
471	0	&& sibling->left->color == BLACK)
472	0	{
473	0	sibling->color = RED;
474	0	sibling->right->color = BLACK;
475	0	rbtree_rotate_left(rbtree, sibling);
476		/* new sibling after rotation */
477	0	if(child_parent->right == child) sibling = child_parent->left;
478	0	else sibling = child_parent->right;
479	0	}
480	0	else if(child_parent->left == child
481	0	&& sibling->color == BLACK
482	0	&& sibling->left->color == RED
483	0	&& sibling->right->color == BLACK)
484	0	{
485	0	sibling->color = RED;
486	0	sibling->left->color = BLACK;
487	0	rbtree_rotate_right(rbtree, sibling);
488		/* new sibling after rotation */
489	0	if(child_parent->right == child) sibling = child_parent->left;
490	0	else sibling = child_parent->right;
491	0	}
492
493		/* now we have a black sibling with a red child. rotate and exchange colors. */
494	0	sibling->color = child_parent->color;
495	0	child_parent->color = BLACK;
496	0	if(child_parent->right == child)
497	0	{
498	0	log_assert(sibling->left->color == RED);
499	0	sibling->left->color = BLACK;
500	0	rbtree_rotate_right(rbtree, child_parent);
501	0	}
502	0	else
503	0	{
504	0	log_assert(sibling->right->color == RED);
505	0	sibling->right->color = BLACK;
506	0	rbtree_rotate_left(rbtree, child_parent);
507	0	}
508	0	}
509
510		int
511		rbtree_find_less_equal(rbtree_type rbtree, const void key,
512		rbnode_type **result)
513	0	{
514	0	int r;
515	0	rbnode_type *node;
516
517	0	log_assert(result);
518
519		/* We start at root... */
520	0	node = rbtree->root;
521
522	0	*result = NULL;
523	0	fptr_ok(fptr_whitelist_rbtree_cmp(rbtree->cmp));
524
525		/* While there are children... */
526	0	while (node != RBTREE_NULL) {
527	0	r = rbtree->cmp(key, node->key);
528	0	if (r == 0) {
529		/* Exact match */
530	0	*result = node;
531	0	return 1;
532	0	}
533	0	if (r < 0) {
534	0	node = node->left;
535	0	} else {
536		/* Temporary match */
537	0	*result = node;
538	0	node = node->right;
539	0	}
540	0	}
541	0	return 0;
542	0	}
543
544		/*
545		* Finds the first element in the red black tree
546		*
547		*/
548		rbnode_type *
549		rbtree_first (rbtree_type *rbtree)
550	0	{
551	0	rbnode_type *node;
552
553	0	for (node = rbtree->root; node->left != RBTREE_NULL; node = node->left);
554	0	return node;
555	0	}
556
557		rbnode_type *
558		rbtree_last (rbtree_type *rbtree)
559	0	{
560	0	rbnode_type *node;
561
562	0	for (node = rbtree->root; node->right != RBTREE_NULL; node = node->right);
563	0	return node;
564	0	}
565
566		/*
567		* Returns the next node...
568		*
569		*/
570		rbnode_type *
571		rbtree_next (rbnode_type *node)
572	0	{
573	0	rbnode_type *parent;
574
575	0	if (node->right != RBTREE_NULL) {
576		/* One right, then keep on going left... */
577	0	for (node = node->right; node->left != RBTREE_NULL; node = node->left);
578	0	} else {
579	0	parent = node->parent;
580	0	while (parent != RBTREE_NULL && node == parent->right) {
581	0	node = parent;
582	0	parent = parent->parent;
583	0	}
584	0	node = parent;
585	0	}
586	0	return node;
587	0	}
588
589		rbnode_type *
590		rbtree_previous(rbnode_type *node)
591	0	{
592	0	rbnode_type *parent;
593
594	0	if (node->left != RBTREE_NULL) {
595		/* One left, then keep on going right... */
596	0	for (node = node->left; node->right != RBTREE_NULL; node = node->right);
597	0	} else {
598	0	parent = node->parent;
599	0	while (parent != RBTREE_NULL && node == parent->left) {
600	0	node = parent;
601	0	parent = parent->parent;
602	0	}
603	0	node = parent;
604	0	}
605	0	return node;
606	0	}
607
608		/** recursive descent traverse */
609		static void
610		traverse_post(void (func)(rbnode_type, void), void arg, rbnode_type* node)
611	0	{
612	0	if(!node \|\| node == RBTREE_NULL)
613	0	return;
614		/* recurse */
615	0	traverse_post(func, arg, node->left);
616	0	traverse_post(func, arg, node->right);
617		/* call user func */
618	0	(*func)(node, arg);
619	0	}
620
621		void
622		traverse_postorder(rbtree_type* tree, void (func)(rbnode_type, void*),
623		void* arg)
624	0	{
625	0	traverse_post(func, arg, tree->root);
626	0	}