Lines Matching refs:rbtree
2 * rbtree.c -- generic red black tree
45 #include <ldns/rbtree.h>
65 static void ldns_rbtree_rotate_left(ldns_rbtree_t *rbtree, ldns_rbnode_t *node);
67 static void ldns_rbtree_rotate_right(ldns_rbtree_t *rbtree, ldns_rbnode_t *node);
69 static void ldns_rbtree_insert_fixup(ldns_rbtree_t *rbtree, ldns_rbnode_t *node);
71 static void ldns_rbtree_delete_fixup(ldns_rbtree_t* rbtree, ldns_rbnode_t* child, ldns_rbnode_t* child_parent);
82 ldns_rbtree_t *rbtree;
85 rbtree = (ldns_rbtree_t *) LDNS_MALLOC(ldns_rbtree_t);
86 if (!rbtree) {
91 ldns_rbtree_init(rbtree, cmpf);
93 return rbtree;
97 ldns_rbtree_init(ldns_rbtree_t *rbtree, int (*cmpf)(const void *, const void *))
100 rbtree->root = LDNS_RBTREE_NULL;
101 rbtree->count = 0;
102 rbtree->cmp = cmpf;
106 ldns_rbtree_free(ldns_rbtree_t *rbtree)
108 LDNS_FREE(rbtree);
116 ldns_rbtree_rotate_left(ldns_rbtree_t *rbtree, ldns_rbnode_t *node)
132 rbtree->root = right;
143 ldns_rbtree_rotate_right(ldns_rbtree_t *rbtree, ldns_rbnode_t *node)
159 rbtree->root = left;
166 ldns_rbtree_insert_fixup(ldns_rbtree_t *rbtree, ldns_rbnode_t *node)
171 while (node != rbtree->root && node->parent->color == RED) {
191 ldns_rbtree_rotate_left(rbtree, node);
196 ldns_rbtree_rotate_right(rbtree, node->parent->parent);
216 ldns_rbtree_rotate_right(rbtree, node);
221 ldns_rbtree_rotate_left(rbtree, node->parent->parent);
225 rbtree->root->color = BLACK;
229 ldns_rbtree_insert_vref(ldns_rbnode_t *data, void *rbtree)
231 (void) ldns_rbtree_insert((ldns_rbtree_t *) rbtree,
242 ldns_rbtree_insert (ldns_rbtree_t *rbtree, ldns_rbnode_t *data)
248 ldns_rbnode_t *node = rbtree->root;
254 if ((r = rbtree->cmp(data->key, node->key)) == 0) {
270 rbtree->count++;
280 rbtree->root = data;
284 ldns_rbtree_insert_fixup(rbtree, data);
294 ldns_rbtree_search (ldns_rbtree_t *rbtree, const void *key)
298 if (ldns_rbtree_find_less_equal(rbtree, key, &node)) {
318 static void change_parent_ptr(ldns_rbtree_t* rbtree, ldns_rbnode_t* parent, ldns_rbnode_t* old, ldns_rbnode_t* new)
322 if(rbtree->root == old) rbtree->root = new;
336 ldns_rbtree_delete(ldns_rbtree_t *rbtree, const void *key)
340 if((to_delete = ldns_rbtree_search(rbtree, key)) == 0) return 0;
341 rbtree->count--;
360 change_parent_ptr(rbtree, to_delete->parent, to_delete, smright);
362 change_parent_ptr(rbtree, smright->parent, smright, to_delete);
391 change_parent_ptr(rbtree, to_delete->parent, to_delete, child);
403 else ldns_rbtree_delete_fixup(rbtree, child, to_delete->parent);
413 static void ldns_rbtree_delete_fixup(ldns_rbtree_t* rbtree, ldns_rbnode_t* child, ldns_rbnode_t* child_parent)
435 ldns_rbtree_rotate_right(rbtree, child_parent);
436 else ldns_rbtree_rotate_left(rbtree, child_parent);
480 ldns_rbtree_rotate_left(rbtree, sibling);
492 ldns_rbtree_rotate_right(rbtree, sibling);
504 ldns_rbtree_rotate_right(rbtree, child_parent);
509 ldns_rbtree_rotate_left(rbtree, child_parent);
514 ldns_rbtree_find_less_equal(ldns_rbtree_t *rbtree, const void *key, ldns_rbnode_t **result)
520 node = rbtree->root;
526 r = rbtree->cmp(key, node->key);
548 ldns_rbtree_first(const ldns_rbtree_t *rbtree)
550 ldns_rbnode_t *node = rbtree->root;
552 if (rbtree->root != LDNS_RBTREE_NULL) {
553 for (node = rbtree->root; node->left != LDNS_RBTREE_NULL; node = node->left);
559 ldns_rbtree_last(const ldns_rbtree_t *rbtree)
561 ldns_rbnode_t *node = rbtree->root;
563 if (rbtree->root != LDNS_RBTREE_NULL) {
564 for (node = rbtree->root; node->right != LDNS_RBTREE_NULL; node = node->right);