#include "rb_tree.h"
#define NO_MEMORY_FATAL(p) do { if (!(p)) { \
- DEBUG(0,("Out of memory for %s at %s\n", #p, __location__)); \
+ DEBUG(DEBUG_CRIT,("Out of memory for %s at %s\n", #p, __location__)); \
exit(10); \
}} while (0)
+static void
+tree_destructor_traverse_node(TALLOC_CTX *mem_ctx, trbt_node_t *node)
+{
+ talloc_set_destructor(node, NULL);
+ if (node->left) {
+ tree_destructor_traverse_node(mem_ctx, node->left);
+ }
+ if (node->right) {
+ tree_destructor_traverse_node(mem_ctx, node->right);
+ }
+ talloc_steal(mem_ctx, node);
+}
+
+/*
+ destroy a tree and remove all its nodes
+ */
+static int tree_destructor(trbt_tree_t *tree)
+{
+ TALLOC_CTX *tmp_ctx;
+ trbt_node_t *node;
+
+ if (tree == NULL) {
+ return 0;
+ }
+
+ node=tree->root;
+ if (node == NULL) {
+ return 0;
+ }
+
+ /* traverse the tree and remove the node destructor and steal
+ the node to the temporary context.
+ we dont want to use the existing destructor for the node
+ since that will remove the nodes one by one from the tree.
+ since the entire tree will be completely destroyed we dont care
+ if it is inconsistent or unbalanced while freeing the
+ individual nodes
+ */
+ tmp_ctx = talloc_new(NULL);
+ tree_destructor_traverse_node(tmp_ctx, node);
+ talloc_free(tmp_ctx);
+
+ return 0;
+}
+
+
+/* create a red black tree */
trbt_tree_t *
-trbt_create(TALLOC_CTX *memctx)
+trbt_create(TALLOC_CTX *memctx, uint32_t flags)
{
trbt_tree_t *tree;
tree = talloc_zero(memctx, trbt_tree_t);
NO_MEMORY_FATAL(tree);
+ /* If the tree is freed, we must walk over all entries and steal the
+ node from the stored data pointer and release the node.
+ Note, when we free the tree we only free the tree and not any of
+ the data stored in the tree.
+ */
+ talloc_set_destructor(tree, tree_destructor);
+ tree->flags = flags;
+
return tree;
}
node->parent->right=node->right;
}
} else {
- tree->tree=node->right;
+ tree->root=node->right;
}
node->right->parent=node->parent;
node->parent=node->right;
node->parent->right=node->left;
}
} else {
- tree->tree=node->left;
+ tree->root=node->left;
}
node->left->parent=node->parent;
node->parent=node->left;
}
}
-static inline trbt_node_t *
-trbt_sibline(trbt_node_t *node)
-{
- if (node==node->parent->left) {
- return node->parent->right;
- } else {
- return node->parent->left;
- }
-}
-
static inline void
trbt_delete_case6(trbt_node_t *node)
{
}
static void
-delete_node(trbt_node_t *node)
+delete_node(trbt_node_t *node, BOOL from_destructor)
{
trbt_node_t *parent, *child, dc;
-
+ trbt_node_t *temp = NULL;
+
+ /* This node has two child nodes, then just copy the content
+ from the next smaller node with this node and delete the
+ predecessor instead.
+ The predecessor is guaranteed to have at most one child
+ node since its right arm must be NULL
+ (It must be NULL since we are its sucessor and we are above
+ it in the tree)
+ */
if (node->left != NULL && node->right != NULL) {
/* This node has two children, just copy the data */
/* find the predecessor */
- trbt_node_t *temp = node->left;
+ temp = node->left;
while (temp->right != NULL) {
temp = temp->right;
/* swap the predecessor data and key with the node to
be deleted.
*/
- talloc_free(node->data);
- node->data = talloc_steal(node, temp->data);
node->key32 = temp->key32;
+ node->data = temp->data;
+ /* now we let node hang off the new data */
+ talloc_steal(node->data, node);
+
temp->data = NULL;
temp->key32 = -1;
/* then delete the temp node.
- this node is guaranteed to have at least one leaf child */
- delete_node(temp);
- return;
+ this node is guaranteed to have at least one leaf
+ child */
+ delete_node(temp, from_destructor);
+ goto finished;
}
-
/* There is at most one child to this node to be deleted */
child = node->left;
if (node->right) {
child = node->right;
}
- /* we didnt have a proper child so create a dummy child */
+ /* If the node to be deleted did not have any child at all we
+ create a temporary dummy node for the child and mark it black.
+ Once the delete of the node is finished, we remove this dummy
+ node, which is simple to do since it is guaranteed that it will
+ still not have any children after the delete operation.
+ This is because we dont represent the leaf-nodes as actual nodes
+ in this implementation.
+ */
if (!child) {
child = &dc;
child->tree = node->tree;
} else {
parent->right = child;
}
-// } else {
-// node->tree->tree = child;
+ } else {
+ node->tree->root = child;
}
child->parent = node->parent;
+
if (node->rb_color == TRBT_BLACK) {
if (trbt_get_color(child) == TRBT_RED) {
child->rb_color = TRBT_BLACK;
}
}
+ /* If we had to create a temporary dummy node to represent a black
+ leaf child we now has to delete it.
+ This is simple since this dummy node originally had no children
+ and we are guaranteed that it will also not have any children
+ after the node has been deleted and any possible rotations
+ have occured.
+
+ The only special case is if this was the last node of the tree
+ in which case we have to reset the root to NULL as well.
+ Othervise it is enough to just unlink the child from its new
+ parent.
+ */
if (child == &dc) {
- if (child == child->parent->left) {
+ if (child->parent == NULL) {
+ node->tree->root = NULL;
+ } else if (child == child->parent->left) {
child->parent->left = NULL;
} else {
child->parent->right = NULL;
}
}
-// node->tree->tree->rb_color=TRBT_BLACK;
+finished:
+ if (!from_destructor) {
+ talloc_free(node);
+ }
+
+ /* if we came from a destructor and temp!=NULL this means we
+ did the node-swap but now the tree still contains the old
+ node which was freed in the destructor. Not good.
+ */
+ if (from_destructor && temp) {
+ temp->key32 = node->key32;
+ temp->rb_color = node->rb_color;
+
+ temp->data = node->data;
+ talloc_steal(temp->data, temp);
+
+ temp->parent = node->parent;
+ if (temp->parent) {
+ if (temp->parent->left == node) {
+ temp->parent->left = temp;
+ } else {
+ temp->parent->right = temp;
+ }
+ }
+
+ temp->left = node->left;
+ if (temp->left) {
+ temp->left->parent = temp;
+ }
+ temp->right = node->right;
+ if (temp->right) {
+ temp->right->parent = temp;
+ }
+
+ if (temp->tree->root == node) {
+ temp->tree->root = temp;
+ }
+ }
+
+ if ( (node->tree->flags & TRBT_AUTOFREE)
+ && (node->tree->root == NULL) ) {
+ talloc_free(node->tree);
+ }
- talloc_free(node);
return;
}
+/*
+ destroy a node and remove it from its tree
+ */
+static int node_destructor(trbt_node_t *node)
+{
+ delete_node(node, True);
+
+ return 0;
+}
+
static inline trbt_node_t *
trbt_create_node(trbt_tree_t *tree, trbt_node_t *parent, uint32_t key, void *data)
{
node->left=NULL;
node->right=NULL;
node->key32=key;
- node->data=talloc_steal(node, data);
+ node->data = data;
+
+ /* let this node hang off data so that it is removed when
+ data is freed
+ */
+ talloc_steal(data, node);
+ talloc_set_destructor(node, node_destructor);
return node;
}
/* insert a new node in the tree.
if there is already a node with a matching key in the tree
- we reurn an error
+ we replace it with the new data and return a pointer to the old data
+ in case the caller wants to take any special action
*/
-int
+void *
trbt_insert32(trbt_tree_t *tree, uint32_t key, void *data)
{
trbt_node_t *node;
- node=tree->tree;
+ node=tree->root;
/* is this the first node ?*/
if(!node){
node = trbt_create_node(tree, NULL, key, data);
- tree->tree=node;
- return 0;
+ tree->root=node;
+ return NULL;
}
/* it was not the new root so walk the tree until we find where to
* insert this new leaf.
*/
while(1){
- /* this node already exists, so just return an error */
+ /* this node already exists, replace data and return the
+ old data
+ */
if(key==node->key32){
- return -1;
+ void *old_data;
+
+ old_data = node->data;
+ node->data = data;
+ /* Let the node now be owned by the new data
+ so the node is freed when the enw data is released
+ */
+ talloc_steal(node->data, node);
+
+ return old_data;
}
if(key<node->key32) {
if(!node->left){
/* node will now point to the newly created node */
node->rb_color=TRBT_RED;
trbt_insert_case1(tree, node);
- return 0;
+ return NULL;
}
void *
{
trbt_node_t *node;
- node=tree->tree;
+ node=tree->root;
while(node){
if(key==node->key32){
return NULL;
}
+
+/* This deletes a node from the tree.
+ Note that this does not release the data that the node points to
+*/
void
trbt_delete32(trbt_tree_t *tree, uint32_t key)
{
trbt_node_t *node;
- node=tree->tree;
+ node=tree->root;
while(node){
if(key==node->key32){
- delete_node(node);
+ delete_node(node, False);
return;
}
if(key<node->key32){
}
+void
+trbt_insert32_callback(trbt_tree_t *tree, uint32_t key, void *(*callback)(void *param, void *data), void *param)
+{
+ trbt_node_t *node;
-# if 0
+ node=tree->root;
+
+ /* is this the first node ?*/
+ if(!node){
+ node = trbt_create_node(tree, NULL, key,
+ callback(param, NULL));
+
+ tree->root=node;
+ return;
+ }
+
+ /* it was not the new root so walk the tree until we find where to
+ * insert this new leaf.
+ */
+ while(1){
+ /* this node already exists, replace it
+ */
+ if(key==node->key32){
+ node->data = callback(param, node->data);
+ talloc_steal(node->data, node);
+
+ return;
+ }
+ if(key<node->key32) {
+ if(!node->left){
+ /* new node to the left */
+ trbt_node_t *new_node;
+
+ new_node = trbt_create_node(tree, node, key,
+ callback(param, NULL));
+ node->left=new_node;
+ node=new_node;
+
+ break;
+ }
+ node=node->left;
+ continue;
+ }
+ if(key>node->key32) {
+ if(!node->right){
+ /* new node to the right */
+ trbt_node_t *new_node;
+
+ new_node = trbt_create_node(tree, node, key,
+ callback(param, NULL));
+ node->right=new_node;
+ node=new_node;
+ break;
+ }
+ node=node->right;
+ continue;
+ }
+ }
+
+ /* node will now point to the newly created node */
+ node->rb_color=TRBT_RED;
+ trbt_insert_case1(tree, node);
+ return;
+}
+
+
+struct trbt_array_param {
+ void *(*callback)(void *param, void *data);
+ void *param;
+ uint32_t keylen;
+ uint32_t *key;
+ trbt_tree_t *tree;
+};
+static void *array_insert_callback(void *p, void *data)
+{
+ struct trbt_array_param *param = (struct trbt_array_param *)p;
+ trbt_tree_t *tree = NULL;
+
+
+ /* if keylen has reached 0 we are done and can call the users
+ callback function with the users parameters
+ */
+ if (param->keylen == 0) {
+ return param->callback(param->param, data);
+ }
+
+
+ /* keylen is not zero yes so we must create/process more subtrees */
+ /* if data is NULL this means we did not yet have a subtree here
+ and we must create one.
+ */
+ if (data == NULL) {
+ /* create a new subtree and hang it off our current tree
+ set it to autofree so that the tree is freed when
+ the last node in it has been released.
+ */
+ tree = trbt_create(param->tree, TRBT_AUTOFREE);
+ } else {
+ /* we already have a subtree for this path */
+ tree = (trbt_tree_t *)data;
+ }
+
+ trbt_insertarray32_callback(tree, param->keylen, param->key, param->callback, param->param);
+
+ /* now return either the old tree we got in *data or the new tree
+ we created to our caller so he can update his pointer in his
+ tree to point to our subtree
+ */
+ return tree;
+}
+
+
+
+/* insert into the tree using an array of uint32 as a key */
+void
+trbt_insertarray32_callback(trbt_tree_t *tree, uint32_t keylen, uint32_t *key, void *(*cb)(void *param, void *data), void *pm)
+{
+ struct trbt_array_param tap;
+
+ /* keylen-1 and key[1] since the call to insert32 will consume the
+ first part of the key.
+ */
+ tap.callback= cb;
+ tap.param = pm;
+ tap.keylen = keylen-1;
+ tap.key = &key[1];
+ tap.tree = tree;
+
+ trbt_insert32_callback(tree, key[0], array_insert_callback, &tap);
+}
+
+/* lookup the tree using an array of uint32 as a key */
+void *
+trbt_lookuparray32(trbt_tree_t *tree, uint32_t keylen, uint32_t *key)
+{
+ /* if keylen is 1 we can do a regular lookup and return this to the
+ user
+ */
+ if (keylen == 1) {
+ return trbt_lookup32(tree, key[0]);
+ }
+
+ /* we need to lookup the next subtree */
+ tree = trbt_lookup32(tree, key[0]);
+ if (tree == NULL) {
+ /* the key does not exist, return NULL */
+ return NULL;
+ }
+
+ /* now lookup the next part of the key in our new tree */
+ return trbt_lookuparray32(tree, keylen-1, &key[1]);
+}
+
+
+/* traverse a tree starting at node */
+static void
+trbt_traversearray32_node(trbt_node_t *node, uint32_t keylen,
+ void (*callback)(void *param, void *data),
+ void *param)
+{
+ if (node->left) {
+ trbt_traversearray32_node(node->left, keylen, callback, param);
+ }
+
+ /* this is the smallest node in this subtree
+ if keylen is 0 this means we can just call the callback
+ otherwise we must pull the next subtree and traverse that one as well
+ */
+ if (keylen == 0) {
+ callback(param, node->data);
+ } else {
+ trbt_traversearray32(node->data, keylen, callback, param);
+ }
+
+ if (node->right) {
+ trbt_traversearray32_node(node->right, keylen, callback, param);
+ }
+}
+
+
+/* traverse the tree using an array of uint32 as a key */
+void
+trbt_traversearray32(trbt_tree_t *tree, uint32_t keylen,
+ void (*callback)(void *param, void *data),
+ void *param)
+{
+ trbt_node_t *node;
+
+ if (tree == NULL) {
+ return;
+ }
+
+ node=tree->root;
+ if (node == NULL) {
+ return;
+ }
+
+ trbt_traversearray32_node(node, keylen-1, callback, param);
+}
+
+
+/* this function will return the first node in a tree where
+ the key is an array of uint32_t
+*/
+void *
+trbt_findfirstarray32(trbt_tree_t *tree, uint32_t keylen)
+{
+ trbt_node_t *node;
+
+ if (keylen < 1) {
+ return NULL;
+ }
+
+ if (tree == NULL) {
+ return NULL;
+ }
+
+ node=tree->root;
+ if (node == NULL) {
+ return NULL;
+ }
+
+ while (node->left) {
+ node = node->left;
+ }
+
+ /* we found our node so return the data */
+ if (keylen == 1) {
+ return node->data;
+ }
+
+ /* we are still traversing subtrees so find the first node in the
+ next level of trees
+ */
+ return trbt_findfirstarray32(node->data, keylen-1);
+}
+
+
+#if 0
static void printtree(trbt_node_t *node, int levels)
{
int i;
printtree(node->left, levels+1);
for(i=0;i<levels;i++)printf(" ");
- printf("key:%d COLOR:%s\n",node->key32,node->rb_color==TRBT_BLACK?"BLACK":"RED");
+ printf("key:%d COLOR:%s (node:0x%08x parent:0x%08x left:0x%08x right:0x%08x)\n",node->key32,node->rb_color==TRBT_BLACK?"BLACK":"RED",(int)node,(int)node->parent, (int)node->left,(int)node->right);
printtree(node->right, levels+1);
printf("\n");
void print_tree(trbt_tree_t *tree)
{
- if(tree->tree==NULL){
+ if(tree->root==NULL){
printf("tree is empty\n");
return;
}
printf("---\n");
- printtree(tree->tree->left, 1);
- printf("root node key:%d COLOR:%s\n",tree->tree->key32,tree->tree->rb_color==TRBT_BLACK?"BLACK":"RED");
- printtree(tree->tree->right, 1);
+ printtree(tree->root->left, 1);
+ printf("root node key:%d COLOR:%s (node:0x%08x left:0x%08x right:0x%08x)\n",tree->root->key32,tree->root->rb_color==TRBT_BLACK?"BLACK":"RED",(int)tree->root,(int)tree->root->left,(int)tree->root->right);
+ printtree(tree->root->right, 1);
printf("===\n");
}
+#endif
-
+# if 0
void
test_tree(void)
{
int cnt=0;
tree=trbt_create(talloc_new(NULL));
+#if 0
+ for(i=0;i<10;i++){
+ printf("adding node %i\n",i);
+ trbt_insert32(tree, i, NULL);
+ print_tree(tree);
+ }
+ printf("deleting node %i\n",3);
+ trbt_delete32(tree, 3);
+ print_tree(tree);
+ for(i=0;i<10;i++){
+ printf("deleting node %i\n",i);
+ trbt_delete32(tree, i);
+ print_tree(tree);
+ }
+exit(0);
+#endif
while(++cnt){
int i;
printf("iteration : %d\n",cnt);
git.samba.org / sahlberg / ctdb.git / blobdiff