#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;
}
}
}
-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
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;
}
}
}
- talloc_free(node);
+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);
+ }
+
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;
}
void *old_data;
old_data = node->data;
- node->data = talloc_steal(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;
}
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)
{
while(node){
if(key==node->key32){
- delete_node(node);
+ delete_node(node, False);
return;
}
if(key<node->key32){
* insert this new leaf.
*/
while(1){
- /* this node already exists, replace data and return the
- old data
+ /* this node already exists, replace it
*/
if(key==node->key32){
- node->data = talloc_steal(node,
- callback(param, node->data));
+ node->data = callback(param, node->data);
+ talloc_steal(node->data, node);
return;
}
}
-
struct trbt_array_param {
void *(*callback)(void *param, void *data);
void *param;
and we must create one.
*/
if (data == NULL) {
- /* create a new subtree and hang it off our current tree */
- tree = trbt_create(param->tree);
+ /* 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_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)
}
-/* delete a node from the tree using an array of uint32 as a key */
-void
-trbt_deletearray32(trbt_tree_t *tree, uint32_t keylen, uint32_t *key)
+/* 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)
{
- trbt_tree_t *next_tree;
+ if (node->left) {
+ trbt_traversearray32_node(node->left, keylen, callback, param);
+ }
- /* if we have reached the leaftree we can just delete the node
- if it exists
+ /* 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 == 1) {
- trbt_delete32(tree, key[0]);
- return;
+ 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;
- /* find the next subtree and recurse into it if it exists */
- next_tree = trbt_lookup32(tree, key[0]);
- if (next_tree == NULL) {
+ if (tree == NULL) {
return;
}
- trbt_deletearray32(next_tree, keylen-1, &key[1]);
+ node=tree->root;
+ if (node == NULL) {
+ return;
+ }
+
+ trbt_traversearray32_node(node, keylen-1, callback, param);
+}
- /* when we returned from recursing into the the subtree,
- that subtree might have become empty in which case we can delete it
- as well
- */
- if (next_tree->root == NULL) {
- trbt_delete32(tree, key[0]);
+/* 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
+
+#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)
{
git.samba.org / sahlberg / ctdb.git / blobdiff