add helpers to traverse a tree where the key is an array of uint32

(This used to be ctdb commit d328c66827cafff6356e96df2a782930274fe139)

4 files changed, 71 insertions, 6 deletions

diff --git a/ctdb/common/rb_tree.c b/ctdb/common/rb_tree.c
index 17388f9562..36dc6397b2 100644
--- a/ctdb/common/rb_tree.c
+++ b/ctdb/common/rb_tree.c
@@ -832,6 +832,56 @@ 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)
+{
+	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);
+}
+		
+
+
 # if 0
 static void printtree(trbt_node_t *node, int levels)
 {
diff --git a/ctdb/common/rb_tree.h b/ctdb/common/rb_tree.h
index f94a4b6a27..9c470aee96 100644
--- a/ctdb/common/rb_tree.h
+++ b/ctdb/common/rb_tree.h
@@ -74,3 +74,6 @@ 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);
diff --git a/ctdb/server/ctdb_takeover.c b/ctdb/server/ctdb_takeover.c
index 743d240c61..d6f1762020 100644
--- a/ctdb/server/ctdb_takeover.c
+++ b/ctdb/server/ctdb_takeover.c
@@ -923,7 +923,6 @@ int32_t ctdb_control_get_public_ips(struct ctdb_context *ctdb,
 
 
 
-
 /*
   list of tcp connections to kill
  */
diff --git a/ctdb/tests/rb_test.c b/ctdb/tests/rb_test.c
index 04ae7d2cf1..693a3f344e 100644
--- a/ctdb/tests/rb_test.c
+++ b/ctdb/tests/rb_test.c
@@ -42,6 +42,13 @@ void *callback(void *param, void *d)
 
 	return data;
 }
+
+void traverse(void *param, void *d)
+{
+	uint32_t *data = (uint32_t *)d;
+
+	printf("traverse data:%d\n",*data);
+}
 	
 				
 /*
@@ -63,10 +70,10 @@ int main(int argc, const char *argv[])
 	int i;
 	trbt_tree_t *tree;
 	uint32_t *data;
-	uint32_t key1[3] = {0,0,0};
-	uint32_t key2[3] = {0,0,1};
-	uint32_t key3[3] = {0,1,0};
-	uint32_t key4[3] = {2,0,0};
+	uint32_t key1[3] = {0,10,20};
+	uint32_t key2[3] = {0,10,21};
+	uint32_t key3[3] = {0,11,20};
+	uint32_t key4[3] = {2,10,20};
 
 	pc = poptGetContext(argv[0], argc, argv, popt_options, POPT_CONTEXT_KEEP_FIRST);
 
@@ -114,6 +121,7 @@ int main(int argc, const char *argv[])
 	trbt_insertarray32_callback(tree, 3, key3, callback, NULL);
 	trbt_insertarray32_callback(tree, 3, key2, callback, NULL);
 	trbt_insertarray32_callback(tree, 3, key1, callback, NULL);
+
 	data = trbt_lookuparray32(tree, 3, key1);
 	printf("key1 dataptr:0x%08x == %d\n",(int)data,data?*data:-1);
 	data = trbt_lookuparray32(tree, 3, key2);
@@ -122,7 +130,8 @@ int main(int argc, const char *argv[])
 	printf("key3 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);
 	data = trbt_lookuparray32(tree, 3, key1);
@@ -133,6 +142,7 @@ int main(int argc, const char *argv[])
 	printf("key3 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 key2\n");
 	trbt_deletearray32(tree, 3, key2);
@@ -144,6 +154,7 @@ int main(int argc, const char *argv[])
 	printf("key3 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 key3\n");
 	trbt_deletearray32(tree, 3, key3);
@@ -155,6 +166,7 @@ int main(int argc, const char *argv[])
 	printf("key3 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 key1\n");
 	trbt_deletearray32(tree, 3, key1);
@@ -166,6 +178,7 @@ int main(int argc, const char *argv[])
 	printf("key3 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);
 	
 
 	return 0;