diff options
Diffstat (limited to 'external/unbound/util/rbtree.c')
| -rw-r--r-- | external/unbound/util/rbtree.c | 106 |
1 files changed, 56 insertions, 50 deletions
diff --git a/external/unbound/util/rbtree.c b/external/unbound/util/rbtree.c index ee5446f6c..f031c9a13 100644 --- a/external/unbound/util/rbtree.c +++ b/external/unbound/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); } |