/build/ldns-VHZYR1/ldns-1.9.2/rbtree.c
Go to the documentation of this file.
/*
* rbtree.c -- generic red black tree
*
* Taken from Unbound, modified for ldns
*
* Copyright (c) 2001-2008, 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.
*
*/
#include <ldns/config.h>
#include <ldns/rbtree.h>
#include <ldns/util.h>
#include <stdlib.h>
#define BLACK 0
#define RED 1
ldns_rbnode_t ldns_rbtree_null_node = {
LDNS_RBTREE_NULL, /* Parent. */
LDNS_RBTREE_NULL, /* Left. */
LDNS_RBTREE_NULL, /* Right. */
NULL, /* Key. */
NULL, /* Data. */
BLACK /* Color. */
};
static void ldns_rbtree_rotate_left(ldns_rbtree_t *rbtree, ldns_rbnode_t *node);
static void ldns_rbtree_rotate_right(ldns_rbtree_t *rbtree, ldns_rbnode_t *node);
static void ldns_rbtree_insert_fixup(ldns_rbtree_t *rbtree, ldns_rbnode_t *node);
static void ldns_rbtree_delete_fixup(ldns_rbtree_t* rbtree, ldns_rbnode_t* child, ldns_rbnode_t* child_parent);
/*
* Creates a new red black tree, initializes and returns a pointer to it.
*
* Return NULL on failure.
*
*/
ldns_rbtree_t *
ldns_rbtree_create (int (*cmpf)(const void *, const void *))
{
ldns_rbtree_t *rbtree;
/* Allocate memory for it */
rbtree = (ldns_rbtree_t *) LDNS_MALLOC(ldns_rbtree_t);
if (!rbtree) {
return NULL;
}
/* Initialize it */
ldns_rbtree_init(rbtree, cmpf);
return rbtree;
}
void
ldns_rbtree_init(ldns_rbtree_t *rbtree, int (*cmpf)(const void *, const void *))
{
/* Initialize it */
rbtree->root = LDNS_RBTREE_NULL;
rbtree->count = 0;
rbtree->cmp = cmpf;
}
void
ldns_rbtree_free(ldns_rbtree_t *rbtree)
{
LDNS_FREE(rbtree);
}
/*
* Rotates the node to the left.
*
*/
static void
ldns_rbtree_rotate_left(ldns_rbtree_t *rbtree, ldns_rbnode_t *node)
{
ldns_rbnode_t *right = node->right;
node->right = right->left;
if (right->left != LDNS_RBTREE_NULL)
right->left->parent = node;
right->parent = node->parent;
if (node->parent != LDNS_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
ldns_rbtree_rotate_right(ldns_rbtree_t *rbtree, ldns_rbnode_t *node)
{
ldns_rbnode_t *left = node->left;
node->left = left->right;
if (left->right != LDNS_RBTREE_NULL)
left->right->parent = node;
left->parent = node->parent;
if (node->parent != LDNS_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
ldns_rbtree_insert_fixup(ldns_rbtree_t *rbtree, ldns_rbnode_t *node)
{
ldns_rbnode_t *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;
ldns_rbtree_rotate_left(rbtree, node);
}
/* Now we're the left child, repaint and rotate... */
node->parent->color = BLACK;
node->parent->parent->color = RED;
ldns_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;
ldns_rbtree_rotate_right(rbtree, node);
}
/* Now we're the right child, repaint and rotate... */
node->parent->color = BLACK;
node->parent->parent->color = RED;
ldns_rbtree_rotate_left(rbtree, node->parent->parent);
}
}
}
rbtree->root->color = BLACK;
}
void
ldns_rbtree_insert_vref(ldns_rbnode_t *data, void *rbtree)
{
(void) ldns_rbtree_insert((ldns_rbtree_t *) rbtree,
data);
}
/*
* Inserts a node into a red black tree.
*
* Returns NULL on failure or the pointer to the newly added node
* otherwise.
*/
ldns_rbnode_t *
ldns_rbtree_insert (ldns_rbtree_t *rbtree, ldns_rbnode_t *data)
{
/* XXX Not necessary, but keeps compiler quiet... */
int r = 0;
/* We start at the root of the tree */
ldns_rbnode_t *node = rbtree->root;
ldns_rbnode_t *parent = LDNS_RBTREE_NULL;
/* Lets find the new parent... */
while (node != LDNS_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 = LDNS_RBTREE_NULL;
data->color = RED;
rbtree->count++;
/* Insert it into the tree... */
if (parent != LDNS_RBTREE_NULL) {
if (r < 0) {
parent->left = data;
} else {
parent->right = data;
}
} else {
rbtree->root = data;
}
/* Fix up the red-black properties... */
ldns_rbtree_insert_fixup(rbtree, data);
return data;
}
/*
* Searches the red black tree, returns the data if key is found or NULL otherwise.
*
*/
ldns_rbnode_t *
ldns_rbtree_search (ldns_rbtree_t *rbtree, const void *key)
{
ldns_rbnode_t *node;
if (ldns_rbtree_find_less_equal(rbtree, key, &node)) {
return node;
} else {
return NULL;
}
}
static void swap_int8(uint8_t* x, uint8_t* y)
{
uint8_t t = *x; *x = *y; *y = t;
}
static void swap_np(ldns_rbnode_t** x, ldns_rbnode_t** y)
{
ldns_rbnode_t* t = *x; *x = *y; *y = t;
}
static void change_parent_ptr(ldns_rbtree_t* rbtree, ldns_rbnode_t* parent, ldns_rbnode_t* old, ldns_rbnode_t* new)
{
if(parent == LDNS_RBTREE_NULL)
{
if(rbtree->root == old) rbtree->root = new;
return;
}
if(parent->left == old) parent->left = new;
if(parent->right == old) parent->right = new;
}
static void change_child_ptr(ldns_rbnode_t* child, ldns_rbnode_t* old, ldns_rbnode_t* new)
{
if(child == LDNS_RBTREE_NULL) return;
if(child->parent == old) child->parent = new;
}
ldns_rbnode_t*
ldns_rbtree_delete(ldns_rbtree_t *rbtree, const void *key)
{
ldns_rbnode_t *to_delete;
ldns_rbnode_t *child;
if((to_delete = ldns_rbtree_search(rbtree, key)) == 0) return 0;
rbtree->count--;
/* make sure we have at most one non-leaf child */
if(to_delete->left != LDNS_RBTREE_NULL &&
to_delete->right != LDNS_RBTREE_NULL)
{
/* swap with smallest from right subtree (or largest from left) */
ldns_rbnode_t *smright = to_delete->right;
while(smright->left != LDNS_RBTREE_NULL)
smright = smright->left;
/* swap the smright and to_delete elements in the tree,
* but the ldns_rbnode_t 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) */
}
if(to_delete->left != LDNS_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!=LDNS_RBTREE_NULL) child->color = BLACK;
}
else ldns_rbtree_delete_fixup(rbtree, child, to_delete->parent);
/* unlink completely */
to_delete->parent = LDNS_RBTREE_NULL;
to_delete->left = LDNS_RBTREE_NULL;
to_delete->right = LDNS_RBTREE_NULL;
to_delete->color = BLACK;
return to_delete;
}
static void ldns_rbtree_delete_fixup(ldns_rbtree_t* rbtree, ldns_rbnode_t* child, ldns_rbnode_t* child_parent)
{
ldns_rbnode_t* 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 == LDNS_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)
ldns_rbtree_rotate_right(rbtree, child_parent);
else ldns_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 != LDNS_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 != LDNS_RBTREE_NULL)
sibling->color = RED;
child_parent->color = BLACK;
return;
}
/* 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;
ldns_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;
ldns_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)
{
sibling->left->color = BLACK;
ldns_rbtree_rotate_right(rbtree, child_parent);
}
else
{
sibling->right->color = BLACK;
ldns_rbtree_rotate_left(rbtree, child_parent);
}
}
int
ldns_rbtree_find_less_equal(ldns_rbtree_t *rbtree, const void *key, ldns_rbnode_t **result)
{
int r;
ldns_rbnode_t *node;
/* We start at root... */
node = rbtree->root;
*result = NULL;
/* While there are children... */
while (node != LDNS_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
*
*/
ldns_rbnode_t *
ldns_rbtree_first(const ldns_rbtree_t *rbtree)
{
ldns_rbnode_t *node = rbtree->root;
if (rbtree->root != LDNS_RBTREE_NULL) {
for (node = rbtree->root; node->left != LDNS_RBTREE_NULL; node = node->left);
}
return node;
}
ldns_rbnode_t *
ldns_rbtree_last(const ldns_rbtree_t *rbtree)
{
ldns_rbnode_t *node = rbtree->root;
if (rbtree->root != LDNS_RBTREE_NULL) {
for (node = rbtree->root; node->right != LDNS_RBTREE_NULL; node = node->right);
}
return node;
}
/*
* Returns the next node...
*
*/
ldns_rbnode_t *
ldns_rbtree_next(ldns_rbnode_t *node)
{
ldns_rbnode_t *parent;
if (node->right != LDNS_RBTREE_NULL) {
/* One right, then keep on going left... */
for (node = node->right;
node->left != LDNS_RBTREE_NULL;
node = node->left);
} else {
parent = node->parent;
while (parent != LDNS_RBTREE_NULL && node == parent->right) {
node = parent;
parent = parent->parent;
}
node = parent;
}
return node;
}
ldns_rbnode_t *
ldns_rbtree_previous(ldns_rbnode_t *node)
{
ldns_rbnode_t *parent;
if (node->left != LDNS_RBTREE_NULL) {
/* One left, then keep on going right... */
for (node = node->left;
node->right != LDNS_RBTREE_NULL;
node = node->right);
} else {
parent = node->parent;
while (parent != LDNS_RBTREE_NULL && node == parent->left) {
node = parent;
parent = parent->parent;
}
node = parent;
}
return node;
}
ldns_rbtree_t *
ldns_rbtree_split(ldns_rbtree_t *tree,
size_t elements)
{
ldns_rbtree_t *new_tree;
ldns_rbnode_t *cur_node;
ldns_rbnode_t *move_node;
size_t count = 0;
new_tree = ldns_rbtree_create(tree->cmp);
cur_node = ldns_rbtree_first(tree);
while (count < elements && cur_node != LDNS_RBTREE_NULL) {
move_node = ldns_rbtree_delete(tree, cur_node->key);
(void)ldns_rbtree_insert(new_tree, move_node);
cur_node = ldns_rbtree_first(tree);
count++;
}
return new_tree;
}
/*
* add all node from the second tree to the first (removing them from the
* second), and fix up nsec(3)s if present
*/
void
ldns_rbtree_join(ldns_rbtree_t *tree1, ldns_rbtree_t *tree2)
{
ldns_traverse_postorder(tree2, ldns_rbtree_insert_vref, tree1);
}
static void
traverse_post(void (*func)(ldns_rbnode_t*, void*), void* arg,
ldns_rbnode_t* node)
{
if(!node || node == LDNS_RBTREE_NULL)
return;
/* recurse */
traverse_post(func, arg, node->left);
traverse_post(func, arg, node->right);
/* call user func */
(*func)(node, arg);
}
void
ldns_traverse_postorder(ldns_rbtree_t* tree,
void (*func)(ldns_rbnode_t*, void*), void* arg)
{
traverse_post(func, arg, tree->root);
}
config.h
ldns_rbtree_search
ldns_rbnode_t * ldns_rbtree_search(ldns_rbtree_t *rbtree, const void *key)
Find key in tree.
Definition rbtree.c:294
ldns_traverse_postorder
void ldns_traverse_postorder(ldns_rbtree_t *tree, void(*func)(ldns_rbnode_t *, void *), void *arg)
Call function for all elements in the redblack tree, such that leaf elements are called before parent...
Definition rbtree.c:666
ldns_rbtree_previous
ldns_rbnode_t * ldns_rbtree_previous(ldns_rbnode_t *node)
Returns previous smaller node in the tree.
Definition rbtree.c:595
ldns_rbtree_free
void ldns_rbtree_free(ldns_rbtree_t *rbtree)
Free the complete tree (but not its keys).
Definition rbtree.c:106
ldns_rbtree_next
ldns_rbnode_t * ldns_rbtree_next(ldns_rbnode_t *node)
Returns next larger node in the tree.
Definition rbtree.c:574
ldns_rbtree_first
ldns_rbnode_t * ldns_rbtree_first(const ldns_rbtree_t *rbtree)
Returns first (smallest) node in the tree.
Definition rbtree.c:548
BLACK
#define BLACK
Node colour black.
Definition rbtree.c:50
ldns_rbtree_insert_vref
void ldns_rbtree_insert_vref(ldns_rbnode_t *data, void *rbtree)
Insert data into the tree (reversed arguments, for use as callback).
Definition rbtree.c:229
RED
#define RED
Node colour red.
Definition rbtree.c:52
ldns_rbtree_split
ldns_rbtree_t * ldns_rbtree_split(ldns_rbtree_t *tree, size_t elements)
split off elements number of elements from the start of the name tree and return a new tree
Definition rbtree.c:620
ldns_rbtree_find_less_equal
int ldns_rbtree_find_less_equal(ldns_rbtree_t *rbtree, const void *key, ldns_rbnode_t **result)
Find, but match does not have to be exact.
Definition rbtree.c:514
ldns_rbtree_insert
ldns_rbnode_t * ldns_rbtree_insert(ldns_rbtree_t *rbtree, ldns_rbnode_t *data)
Insert data into the tree.
Definition rbtree.c:242
ldns_rbtree_join
void ldns_rbtree_join(ldns_rbtree_t *tree1, ldns_rbtree_t *tree2)
add all node from the second tree to the first (removing them from the second), and fix up nsec(3)s i...
Definition rbtree.c:646
ldns_rbtree_init
void ldns_rbtree_init(ldns_rbtree_t *rbtree, int(*cmpf)(const void *, const void *))
Init a new tree (malloced by caller) with given key compare function.
Definition rbtree.c:97
ldns_rbtree_create
ldns_rbtree_t * ldns_rbtree_create(int(*cmpf)(const void *, const void *))
Create new tree (malloced) with given key compare function.
Definition rbtree.c:80
ldns_rbtree_delete
ldns_rbnode_t * ldns_rbtree_delete(ldns_rbtree_t *rbtree, const void *key)
Delete element from tree.
Definition rbtree.c:336
ldns_rbtree_last
ldns_rbnode_t * ldns_rbtree_last(const ldns_rbtree_t *rbtree)
Returns last (largest) node in the tree.
Definition rbtree.c:559
ldns_rbtree_insert_vref
void ldns_rbtree_insert_vref(ldns_rbnode_t *data, void *rbtree)
Insert data into the tree (reversed arguments, for use as callback).
Definition rbtree.c:229
ldns_rbtree_null_node
ldns_rbnode_t ldns_rbtree_null_node
the global empty node
Definition rbtree.c:55
LDNS_RBTREE_NULL
#define LDNS_RBTREE_NULL
The nullpointer, points to empty node.
Definition rbtree.h:76
ldns_rbnode_t
The rbnode_t struct definition.
Definition rbtree.h:60
ldns_rbnode_t::right
ldns_rbnode_t * right
right node (larger items)
Definition rbtree.h:66
ldns_rbnode_t::parent
ldns_rbnode_t * parent
parent in rbtree, RBTREE_NULL for root
Definition rbtree.h:62
ldns_rbnode_t::key
const void * key
pointer to sorting key
Definition rbtree.h:68
ldns_rbnode_t::left
ldns_rbnode_t * left
left node (smaller items)
Definition rbtree.h:64
ldns_rbnode_t::color
uint8_t color
colour of this node
Definition rbtree.h:72
ldns_rbtree_t
definition for tree struct
Definition rbtree.h:83
ldns_rbtree_t::count
size_t count
The number of the nodes in the tree.
Definition rbtree.h:88
ldns_rbtree_t::root
ldns_rbnode_t * root
The root of the red-black tree.
Definition rbtree.h:85
ldns_rbtree_t::cmp
int(* cmp)(const void *, const void *)
Key compare function.
Definition rbtree.h:94
util.h
LDNS_FREE
#define LDNS_FREE(ptr)
Definition util.h:60
LDNS_MALLOC
#define LDNS_MALLOC(type)
Memory management macros.
Definition util.h:49