From 0f92fa224c8c05b6cce0155dca7f0696987fd6e2 Mon Sep 17 00:00:00 2001 From: Ronnie Sahlberg Date: Wed, 2 Nov 2011 13:33:28 +1100 Subject: RB_TREE: Add mechanism to abort a traverse This patch changes the callback signature for traversal functions to allow a client to abort a traverse before it finishes. Updates to all callers and examples as well as rb-test tool. (This used to be ctdb commit 8ab0c63ad36cfbbb1e5fed46a1f4c47b1fdb581f) --- ctdb/common/rb_tree.c | 53 ++++++++++++++++++++++++++++++++++----------------- ctdb/common/rb_tree.h | 9 +++++++-- 2 files changed, 43 insertions(+), 19 deletions(-) (limited to 'ctdb/common') diff --git a/ctdb/common/rb_tree.c b/ctdb/common/rb_tree.c index b2c2ee83d50..8458c510bea 100644 --- a/ctdb/common/rb_tree.c +++ b/ctdb/common/rb_tree.c @@ -916,13 +916,17 @@ trbt_lookuparray32(trbt_tree_t *tree, uint32_t keylen, uint32_t *key) /* traverse a tree starting at node */ -static void +static int trbt_traversearray32_node(trbt_node_t *node, uint32_t keylen, - void (*callback)(void *param, void *data), + int (*callback)(void *param, void *data), void *param) { if (node->left) { - trbt_traversearray32_node(node->left, keylen, callback, param); + int ret; + ret = trbt_traversearray32_node(node->left, keylen, callback, param); + if (ret != 0) { + return ret; + } } /* this is the smallest node in this subtree @@ -930,35 +934,52 @@ trbt_traversearray32_node(trbt_node_t *node, uint32_t keylen, otherwise we must pull the next subtree and traverse that one as well */ if (keylen == 0) { - callback(param, node->data); + int ret; + + ret = callback(param, node->data); + if (ret != 0) { + return ret; + } } else { - trbt_traversearray32(node->data, keylen, callback, param); + int ret; + + ret = trbt_traversearray32(node->data, keylen, callback, param); + if (ret != 0) { + return ret; + } } if (node->right) { - trbt_traversearray32_node(node->right, keylen, callback, param); + int ret; + + ret = trbt_traversearray32_node(node->right, keylen, callback, param); + if (ret != 0) { + return ret; + } } + + return 0; } /* traverse the tree using an array of uint32 as a key */ -void +int trbt_traversearray32(trbt_tree_t *tree, uint32_t keylen, - void (*callback)(void *param, void *data), + int (*callback)(void *param, void *data), void *param) { trbt_node_t *node; if (tree == NULL) { - return; + return 0; } node=tree->root; if (node == NULL) { - return; + return 0; } - trbt_traversearray32_node(node, keylen-1, callback, param); + return trbt_traversearray32_node(node, keylen-1, callback, param); } @@ -999,7 +1020,7 @@ trbt_findfirstarray32(trbt_tree_t *tree, uint32_t keylen) } -#if 0 +#if TEST_RB_TREE static void printtree(trbt_node_t *node, int levels) { int i; @@ -1007,7 +1028,7 @@ static void printtree(trbt_node_t *node, int levels) printtree(node->left, levels+1); for(i=0;ikey32,node->rb_color==TRBT_BLACK?"BLACK":"RED",(int)node,(int)node->parent, (int)node->left,(int)node->right); + printf("key:%d COLOR:%s (node:%p parent:%p left:%p right:%p)\n",node->key32,node->rb_color==TRBT_BLACK?"BLACK":"RED", node, node->parent, node->left, node->right); printtree(node->right, levels+1); printf("\n"); @@ -1021,13 +1042,11 @@ void print_tree(trbt_tree_t *tree) } printf("---\n"); 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); + printf("root node key:%d COLOR:%s (node:%p left:%p right:%p)\n",tree->root->key32,tree->root->rb_color==TRBT_BLACK?"BLACK":"RED", tree->root, tree->root->left, tree->root->right); printtree(tree->root->right, 1); printf("===\n"); } -#endif -# if 0 void test_tree(void) { @@ -1037,7 +1056,7 @@ test_tree(void) int NUM=15; int cnt=0; - tree=trbt_create(talloc_new(NULL)); + tree=trbt_create(talloc_new(NULL), 0); #if 0 for(i=0;i<10;i++){ printf("adding node %i\n",i); diff --git a/ctdb/common/rb_tree.h b/ctdb/common/rb_tree.h index eef0bc5227a..4f2ab22d36d 100644 --- a/ctdb/common/rb_tree.h +++ b/ctdb/common/rb_tree.h @@ -74,8 +74,13 @@ void trbt_insertarray32_callback(trbt_tree_t *tree, uint32_t keylen, uint32_t *k and return a pointer to data or NULL */ void *trbt_lookuparray32(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); +/* Traverse a tree with a key based on an array of uint32 + returns 0 if traverse completed + !0 if the traverse was aborted + + If the callback returns !0 the traverse will be aborted +*/ +int trbt_traversearray32(trbt_tree_t *tree, uint32_t keylen, int (*callback)(void *param, void *data), void *param); /* Lookup the first node in the tree with a key based on an array of uint32 and return a pointer to data or NULL */ -- cgit