diff options
Diffstat (limited to 'usr.sbin/nsd/rbtree.c')
| -rw-r--r-- | usr.sbin/nsd/rbtree.c | 94 |
1 files changed, 47 insertions, 47 deletions
diff --git a/usr.sbin/nsd/rbtree.c b/usr.sbin/nsd/rbtree.c index bc3840e2d6b..5d8cd4cd57a 100644 --- a/usr.sbin/nsd/rbtree.c +++ b/usr.sbin/nsd/rbtree.c @@ -17,7 +17,7 @@ #define BLACK 0 #define RED 1 -rbnode_t rbtree_null_node = { +rbnode_type rbtree_null_node = { RBTREE_NULL, /* Parent. */ RBTREE_NULL, /* Left. */ RBTREE_NULL, /* Right. */ @@ -25,10 +25,10 @@ rbnode_t rbtree_null_node = { BLACK /* Color. */ }; -static void rbtree_rotate_left(rbtree_t *rbtree, rbnode_t *node); -static void rbtree_rotate_right(rbtree_t *rbtree, rbnode_t *node); -static void rbtree_insert_fixup(rbtree_t *rbtree, rbnode_t *node); -static void rbtree_delete_fixup(rbtree_t* rbtree, rbnode_t* child, rbnode_t* child_parent); +static void rbtree_rotate_left(rbtree_type *rbtree, rbnode_type *node); +static void rbtree_rotate_right(rbtree_type *rbtree, rbnode_type *node); +static void rbtree_insert_fixup(rbtree_type *rbtree, rbnode_type *node); +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. @@ -36,13 +36,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 (region_type *region, int (*cmpf)(const void *, const void *)) { - rbtree_t *rbtree; + rbtree_type *rbtree; /* Allocate memory for it */ - rbtree = (rbtree_t *) region_alloc(region, sizeof(rbtree_t)); + rbtree = (rbtree_type *) region_alloc(region, sizeof(rbtree_type)); if (!rbtree) { return NULL; } @@ -61,9 +61,9 @@ rbtree_create (region_type *region, 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; @@ -88,9 +88,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; @@ -111,9 +111,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) { @@ -180,15 +180,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; /* Lets find the new parent... */ while (node != RBTREE_NULL) { @@ -232,10 +232,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; @@ -250,12 +250,12 @@ static void swap_int8(uint8_t* x, uint8_t* y) uint8_t t = *x; *x = *y; *y = t; } -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; } -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) { @@ -268,18 +268,18 @@ static void change_parent_ptr(rbtree_t* rbtree, rbnode_t* parent, rbnode_t* old, if(parent->left == old) parent->left = new; if(parent->right == old) parent->right = new; } -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; 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--; @@ -287,11 +287,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 */ @@ -353,9 +353,9 @@ 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 */ @@ -457,10 +457,10 @@ 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; assert(result); @@ -492,19 +492,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; @@ -514,10 +514,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... */ @@ -533,10 +533,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... */ |