}} 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 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)
-{
- trbt_tree_t *next_tree;
-
- /* if we have reached the leaftree we can just delete the node
- if it exists
- */
- if (keylen == 1) {
- trbt_delete32(tree, key[0]);
- return;
- }
-
-
- /* find the next subtree and recurse into it if it exists */
- next_tree = trbt_lookup32(tree, key[0]);
- if (next_tree == NULL) {
- return;
- }
-
- trbt_deletearray32(next_tree, keylen-1, &key[1]);
-
-
- /* 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]);
- }
-}
-
-
-
/* traverse a tree starting at node */
static void
trbt_traversearray32_node(trbt_node_t *node, uint32_t keylen,
trbt_traversearray32_node(node, keylen-1, callback, param);
}
-
-# 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)
{
typedef struct _trbt_tree_t {
trbt_node_t *root;
+/* automatically free the tree when the last node has been deleted */
+#define TRBT_AUTOFREE 0x00000001
+ uint32_t flags;
} trbt_tree_t;
/* Create a RB tree */
-trbt_tree_t *trbt_create(TALLOC_CTX *memctx);
+trbt_tree_t *trbt_create(TALLOC_CTX *memctx, uint32_t flags);
/* Lookup a node in the tree and return a pointer to data or NULL */
void *trbt_lookup32(trbt_tree_t *tree, uint32_t key);
and return a pointer to data or NULL */
void *trbt_lookuparray32(trbt_tree_t *tree, uint32_t keylen, uint32_t *key);
-/* Delete a node in the tree with a key based on an array of uint32
- and return a pointer to data or NULL */
-void trbt_deletearray32(trbt_tree_t *tree, uint32_t keylen, uint32_t *key);
-
/* Traverse a tree with a key based on an array of uint32 */
void trbt_traversearray32(trbt_tree_t *tree, uint32_t keylen, void (*callback)(void *param, void *data), void *param);
ctdb_sys_send_tcp(killtcp->sending_fd, &con->dst,
&con->src, ack_seq, seq, 1);
- trbt_deletearray32(killtcp->connections, 4, key);
+ talloc_free(con);
}
return 0;
}
-/*
- destroy a killtcp connection structure
- */
-static int ctdb_killtcp_connection_destructor(struct ctdb_killtcp_con *con)
-{
- uint32_t key[4];
-
- key[0] = con->src.sin_addr.s_addr;
- key[1] = con->dst.sin_addr.s_addr;
- key[2] = con->src.sin_port;
- key[3] = con->dst.sin_port;
-
- trbt_deletearray32(con->killtcp->connections, 4, key);
-
- return 0;
-}
-
/* nothing fancy here, just unconditionally replace any existing
connection structure with the new one.
killtcp->ctdb = ctdb;
killtcp->capture_fd = -1;
killtcp->sending_fd = -1;
- killtcp->connections= trbt_create(killtcp);
+ killtcp->connections= trbt_create(killtcp, 0);
ctdb->killtcp = killtcp;
talloc_set_destructor(killtcp, ctdb_killtcp_destructor);
con->dst = *dst;
con->count = 0;
con->killtcp = killtcp;
- talloc_set_destructor(con, ctdb_killtcp_connection_destructor);
+
key[0] = con->src.sin_addr.s_addr;
key[1] = con->dst.sin_addr.s_addr;
/* We also need to set up some events to tickle all these connections
until they are all reset
*/
- event_add_timed(ctdb->ev, killtcp, timeval_zero(),
+ event_add_timed(ctdb->ev, killtcp, timeval_current_ofs(1, 0),
ctdb_tickle_sentenced_connections, killtcp);
}
(tp1.tv_sec + (tp1.tv_usec*1.0e-6));
}
-int num_records;
+int num_records=5;
-void *callback(void *param, void *d)
+void *callback(void *p, void *d)
{
uint32_t *data = (uint32_t *)d;
- if(!data){
- data = talloc(NULL, uint32_t);
- *data = 0;
+ if (d==NULL) {
+ data = (uint32_t *)p;
}
+
(*data)++;
return data;
void *random_add(void *p, void *d)
{
- if(d){
- talloc_free(d);
- }
return p;
}
uint32_t key2[3] = {0,10,21};
uint32_t key3[3] = {0,11,20};
uint32_t key4[3] = {2,10,20};
+ TALLOC_CTX *memctx;
+ uint32_t **u32array;
pc = poptGetContext(argv[0], argc, argv, popt_options, POPT_CONTEXT_KEEP_FIRST);
printf("testing trbt_insert32_callback for %d records\n", num_records);
- tree = trbt_create(NULL);
+ memctx = talloc_new(NULL);
+ u32array = talloc_array(memctx, uint32_t, num_records);
+ tree = trbt_create(memctx, 0);
for (i=0; i<num_records; i++) {
- trbt_insert32_callback(tree, i, callback, NULL);
+ u32array[i] = talloc(u32array, uint32_t);
+ *u32array[i] = 0;
+ trbt_insert32_callback(tree, i, callback, u32array[i]);
}
for (i=3; i<num_records; i++) {
trbt_insert32_callback(tree, i, callback, NULL);
data = trbt_lookup32(tree, i);
printf("key:%d data:%d\n", i, *data);
}
+// talloc_report_full(tree, stdout);
+// talloc_report_full(memctx, stdout);
+// print_tree(tree);
+
+ printf("deleting key 2\n");
+ talloc_free(u32array[2]);
+// talloc_report_full(tree, stdout);
+// talloc_report_full(memctx, stdout);
+// print_tree(tree);
+
+ printf("deleting key 1\n");
+ talloc_free(u32array[1]);
+// talloc_report_full(tree, stdout);
+// talloc_report_full(memctx, stdout);
+// print_tree(tree);
+
+ printf("freeing tree\n");
+ talloc_report_full(memctx, stdout);
+ talloc_free(memctx);
printf("testing trbt_insertarray32_callback\n");
- tree = trbt_create(NULL);
- trbt_insertarray32_callback(tree, 3, key1, callback, NULL);
- trbt_insertarray32_callback(tree, 3, key1, callback, NULL);
- trbt_insertarray32_callback(tree, 3, key2, callback, NULL);
- trbt_insertarray32_callback(tree, 3, key3, callback, NULL);
- trbt_insertarray32_callback(tree, 3, key2, callback, NULL);
- trbt_insertarray32_callback(tree, 3, key1, callback, NULL);
+ memctx = talloc_new(NULL);
+ tree = trbt_create(memctx, 0);
+ u32array = talloc_array(memctx, uint32_t, 4);
+ for (i=0;i<4;i++) {
+ u32array[i] = talloc(u32array, uint32_t);
+ *u32array[i] = 0;
+ }
+ trbt_insertarray32_callback(tree, 3, key1, callback, u32array[0]);
+ trbt_insertarray32_callback(tree, 3, key1, callback, u32array[0]);
+ trbt_insertarray32_callback(tree, 3, key2, callback, u32array[1]);
+ trbt_insertarray32_callback(tree, 3, key3, callback, u32array[2]);
+ trbt_insertarray32_callback(tree, 3, key2, callback, u32array[1]);
+ trbt_insertarray32_callback(tree, 3, key1, callback, u32array[0]);
data = trbt_lookuparray32(tree, 3, key1);
printf("key1 dataptr:0x%08x == %d\n",(int)data,data?*data:-1);
data = trbt_lookuparray32(tree, 3, key4);
printf("key4 dataptr:0x%08x == %d\n",(int)data,data?*data:-1);
trbt_traversearray32(tree, 3, traverse, NULL);
+
printf("\ndeleting key4\n");
- trbt_deletearray32(tree, 3, key4);
+ talloc_free(trbt_lookuparray32(tree, 3, key4));
data = trbt_lookuparray32(tree, 3, key1);
printf("key1 dataptr:0x%08x == %d\n",(int)data,data?*data:-1);
data = trbt_lookuparray32(tree, 3, key2);
trbt_traversearray32(tree, 3, traverse, NULL);
printf("\ndeleting key2\n");
- trbt_deletearray32(tree, 3, key2);
+ talloc_free(trbt_lookuparray32(tree, 3, key2));
data = trbt_lookuparray32(tree, 3, key1);
printf("key1 dataptr:0x%08x == %d\n",(int)data,data?*data:-1);
data = trbt_lookuparray32(tree, 3, key2);
trbt_traversearray32(tree, 3, traverse, NULL);
printf("\ndeleting key3\n");
- trbt_deletearray32(tree, 3, key3);
+ talloc_free(trbt_lookuparray32(tree, 3, key3));
data = trbt_lookuparray32(tree, 3, key1);
printf("key1 dataptr:0x%08x == %d\n",(int)data,data?*data:-1);
data = trbt_lookuparray32(tree, 3, key2);
trbt_traversearray32(tree, 3, traverse, NULL);
printf("\ndeleting key1\n");
- trbt_deletearray32(tree, 3, key1);
+ talloc_free(trbt_lookuparray32(tree, 3, key1));
data = trbt_lookuparray32(tree, 3, key1);
printf("key1 dataptr:0x%08x == %d\n",(int)data,data?*data:-1);
data = trbt_lookuparray32(tree, 3, key2);
data = trbt_lookuparray32(tree, 3, key4);
printf("key4 dataptr:0x%08x == %d\n",(int)data,data?*data:-1);
trbt_traversearray32(tree, 3, traverse, NULL);
+
+ talloc_free(tree);
+ talloc_free(memctx);
printf("\nrun random insert and delete for 60 seconds\n");
- tree = trbt_create(NULL);
+ memctx = talloc_new(NULL);
+ tree = trbt_create(memctx, 0);
i=0;
start_timer();
while(end_timer() < 60.0){
key[1]=random()%10;
key[2]=random()%10;
if (random()%2) {
- str=talloc_asprintf(tree, "%d.%d.%d", key[0],key[1],key[2]);
+ str=talloc_asprintf(memctx, "%d.%d.%d", key[0],key[1],key[2]);
trbt_insertarray32_callback(tree, 3, key, random_add, str);
} else {
- trbt_deletearray32(tree, 3, key);
+ talloc_free(trbt_lookuparray32(tree, 3, key));
}
if(i%1000==999)printf(".");fflush(stdout);
}
key[0]=i;
key[1]=j;
key[2]=k;
- trbt_deletearray32(tree, 3, key);
+ talloc_free(trbt_lookuparray32(tree, 3, key));
}
}
}
git.samba.org / metze / ctdb / wip.git / commitdiff