vendor/unbound/1.6.1

1 files changed, 56 insertions, 50 deletions

diff --git a/util/rbtree.c b/util/rbtree.c
index ee5446f6cb567..f031c9a13fafc 100644
--- a/util/rbtree.c
+++ b/util/rbtree.c
@@ -50,7 +50,7 @@
 #define	RED	1
 
 /** the NULL node, global alloc */
-rbnode_t	rbtree_null_node = {
+rbnode_type	rbtree_null_node = {
 	RBTREE_NULL,		/* Parent.  */
 	RBTREE_NULL,		/* Left.  */
 	RBTREE_NULL,		/* Right.  */
@@ -59,13 +59,14 @@ rbnode_t	rbtree_null_node = {
 };
 
 /** rotate subtree left (to preserve redblack property) */
-static void rbtree_rotate_left(rbtree_t *rbtree, rbnode_t *node);
+static void rbtree_rotate_left(rbtree_type *rbtree, rbnode_type *node);
 /** rotate subtree right (to preserve redblack property) */
-static void rbtree_rotate_right(rbtree_t *rbtree, rbnode_t *node);
+static void rbtree_rotate_right(rbtree_type *rbtree, rbnode_type *node);
 /** Fixup node colours when insert happened */
-static void rbtree_insert_fixup(rbtree_t *rbtree, rbnode_t *node);
+static void rbtree_insert_fixup(rbtree_type *rbtree, rbnode_type *node);
 /** Fixup node colours when delete happened */
-static void rbtree_delete_fixup(rbtree_t* rbtree, rbnode_t* child, rbnode_t* child_parent);
+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.
@@ -73,13 +74,13 @@ static void rbtree_delete_fixup(rbtree_t* rbtree, rbnode_t* child, rbnode_t* chi
  * Return NULL on failure.
  *
  */
-rbtree_t *
+rbtree_type *
 rbtree_create (int (*cmpf)(const void *, const void *))
 {
-	rbtree_t *rbtree;
+	rbtree_type *rbtree;
 
 	/* Allocate memory for it */
-	rbtree = (rbtree_t *) malloc(sizeof(rbtree_t));
+	rbtree = (rbtree_type *) malloc(sizeof(rbtree_type));
 	if (!rbtree) {
 		return NULL;
 	}
@@ -91,7 +92,7 @@ rbtree_create (int (*cmpf)(const void *, const void *))
 }
 
 void 
-rbtree_init(rbtree_t *rbtree, int (*cmpf)(const void *, const void *))
+rbtree_init(rbtree_type *rbtree, int (*cmpf)(const void *, const void *))
 {
 	/* Initialize it */
 	rbtree->root = RBTREE_NULL;
@@ -104,9 +105,9 @@ rbtree_init(rbtree_t *rbtree, int (*cmpf)(const void *, const void *))
  *
  */
 static void
-rbtree_rotate_left(rbtree_t *rbtree, rbnode_t *node)
+rbtree_rotate_left(rbtree_type *rbtree, rbnode_type *node)
 {
-	rbnode_t *right = node->right;
+	rbnode_type *right = node->right;
 	node->right = right->left;
 	if (right->left != RBTREE_NULL)
 		right->left->parent = node;
@@ -131,9 +132,9 @@ rbtree_rotate_left(rbtree_t *rbtree, rbnode_t *node)
  *
  */
 static void
-rbtree_rotate_right(rbtree_t *rbtree, rbnode_t *node)
+rbtree_rotate_right(rbtree_type *rbtree, rbnode_type *node)
 {
-	rbnode_t *left = node->left;
+	rbnode_type *left = node->left;
 	node->left = left->right;
 	if (left->right != RBTREE_NULL)
 		left->right->parent = node;
@@ -154,9 +155,9 @@ rbtree_rotate_right(rbtree_t *rbtree, rbnode_t *node)
 }
 
 static void
-rbtree_insert_fixup(rbtree_t *rbtree, rbnode_t *node)
+rbtree_insert_fixup(rbtree_type *rbtree, rbnode_type *node)
 {
-	rbnode_t	*uncle;
+	rbnode_type	*uncle;
 
 	/* While not at the root and need fixing... */
 	while (node != rbtree->root && node->parent->color == RED) {
@@ -223,15 +224,15 @@ rbtree_insert_fixup(rbtree_t *rbtree, rbnode_t *node)
  * Returns NULL on failure or the pointer to the newly added node
  * otherwise.
  */
-rbnode_t *
-rbtree_insert (rbtree_t *rbtree, rbnode_t *data)
+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_t	*node = rbtree->root;
-	rbnode_t	*parent = RBTREE_NULL;
+	rbnode_type	*node = rbtree->root;
+	rbnode_type	*parent = RBTREE_NULL;
 
 	fptr_ok(fptr_whitelist_rbtree_cmp(rbtree->cmp));
 	/* Lets find the new parent... */
@@ -276,10 +277,10 @@ rbtree_insert (rbtree_t *rbtree, rbnode_t *data)
  * Searches the red black tree, returns the data if key is found or NULL otherwise.
  *
  */
-rbnode_t *
-rbtree_search (rbtree_t *rbtree, const void *key)
+rbnode_type *
+rbtree_search (rbtree_type *rbtree, const void *key)
 {
-	rbnode_t *node;
+	rbnode_type *node;
 
 	if (rbtree_find_less_equal(rbtree, key, &node)) {
 		return node;
@@ -295,13 +296,14 @@ static void swap_int8(uint8_t* x, uint8_t* y)
 }
 
 /** helpers for delete: swap node pointers */
-static void swap_np(rbnode_t** x, rbnode_t** y) 
+static void swap_np(rbnode_type** x, rbnode_type** y) 
 {
-	rbnode_t* t = *x; *x = *y; *y = t; 
+	rbnode_type* t = *x; *x = *y; *y = t; 
 }
 
 /** Update parent pointers of child trees of 'parent' */
-static void change_parent_ptr(rbtree_t* rbtree, rbnode_t* parent, rbnode_t* old, rbnode_t* new)
+static void change_parent_ptr(rbtree_type* rbtree, rbnode_type* parent,
+	rbnode_type* old, rbnode_type* new)
 {
 	if(parent == RBTREE_NULL)
 	{
@@ -315,18 +317,19 @@ static void change_parent_ptr(rbtree_t* rbtree, rbnode_t* parent, rbnode_t* old,
 	if(parent->right == old) parent->right = new;
 }
 /** Update parent pointer of a node 'child' */
-static void change_child_ptr(rbnode_t* child, rbnode_t* old, rbnode_t* new)
+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_t* 
-rbtree_delete(rbtree_t *rbtree, const void *key)
+rbnode_type* 
+rbtree_delete(rbtree_type *rbtree, const void *key)
 {
-	rbnode_t *to_delete;
-	rbnode_t *child;
+	rbnode_type *to_delete;
+	rbnode_type *child;
 	if((to_delete = rbtree_search(rbtree, key)) == 0) return 0;
 	rbtree->count--;
 
@@ -334,11 +337,11 @@ rbtree_delete(rbtree_t *rbtree, const void *key)
 	if(to_delete->left != RBTREE_NULL && to_delete->right != RBTREE_NULL)
 	{
 		/* swap with smallest from right subtree (or largest from left) */
-		rbnode_t *smright = to_delete->right;
+		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_t is first part of user data struct
+		 * 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 */
 
@@ -400,9 +403,10 @@ rbtree_delete(rbtree_t *rbtree, const void *key)
 	return to_delete;
 }
 
-static void rbtree_delete_fixup(rbtree_t* rbtree, rbnode_t* child, rbnode_t* child_parent)
+static void rbtree_delete_fixup(rbtree_type* rbtree, rbnode_type* child,
+	rbnode_type* child_parent)
 {
-	rbnode_t* sibling;
+	rbnode_type* sibling;
 	int go_up = 1;
 
 	/* determine sibling to the node that is one-black short */
@@ -504,10 +508,11 @@ static void rbtree_delete_fixup(rbtree_t* rbtree, rbnode_t* child, rbnode_t* chi
 }
 
 int
-rbtree_find_less_equal(rbtree_t *rbtree, const void *key, rbnode_t **result)
+rbtree_find_less_equal(rbtree_type *rbtree, const void *key,
+	rbnode_type **result)
 {
 	int r;
-	rbnode_t *node;
+	rbnode_type *node;
 
 	log_assert(result);
 	
@@ -540,19 +545,19 @@ rbtree_find_less_equal(rbtree_t *rbtree, const void *key, rbnode_t **result)
  * Finds the first element in the red black tree
  *
  */
-rbnode_t *
-rbtree_first (rbtree_t *rbtree)
+rbnode_type *
+rbtree_first (rbtree_type *rbtree)
 {
-	rbnode_t *node;
+	rbnode_type *node;
 
 	for (node = rbtree->root; node->left != RBTREE_NULL; node = node->left);
 	return node;
 }
 
-rbnode_t *
-rbtree_last (rbtree_t *rbtree)
+rbnode_type *
+rbtree_last (rbtree_type *rbtree)
 {
-	rbnode_t *node;
+	rbnode_type *node;
 
 	for (node = rbtree->root; node->right != RBTREE_NULL; node = node->right);
 	return node;
@@ -562,10 +567,10 @@ rbtree_last (rbtree_t *rbtree)
  * Returns the next node...
  *
  */
-rbnode_t *
-rbtree_next (rbnode_t *node)
+rbnode_type *
+rbtree_next (rbnode_type *node)
 {
-	rbnode_t *parent;
+	rbnode_type *parent;
 
 	if (node->right != RBTREE_NULL) {
 		/* One right, then keep on going left... */
@@ -581,10 +586,10 @@ rbtree_next (rbnode_t *node)
 	return node;
 }
 
-rbnode_t *
-rbtree_previous(rbnode_t *node)
+rbnode_type *
+rbtree_previous(rbnode_type *node)
 {
-	rbnode_t *parent;
+	rbnode_type *parent;
 
 	if (node->left != RBTREE_NULL) {
 		/* One left, then keep on going right... */
@@ -602,7 +607,7 @@ rbtree_previous(rbnode_t *node)
 
 /** recursive descent traverse */
 static void 
-traverse_post(void (*func)(rbnode_t*, void*), void* arg, rbnode_t* node)
+traverse_post(void (*func)(rbnode_type*, void*), void* arg, rbnode_type* node)
 {
 	if(!node || node == RBTREE_NULL)
 		return;
@@ -614,7 +619,8 @@ traverse_post(void (*func)(rbnode_t*, void*), void* arg, rbnode_t* node)
 }
 
 void 
-traverse_postorder(rbtree_t* tree, void (*func)(rbnode_t*, void*), void* arg)
+traverse_postorder(rbtree_type* tree, void (*func)(rbnode_type*, void*),
+	void* arg)
 {
 	traverse_post(func, arg, tree->root);
 }