along with this program; if not, see <http://www.gnu.org/licenses/>.
*/
-#include "includes.h"
-#include "rb_tree.h"
+#include "replace.h"
+
+#include <talloc.h>
+
+#include "lib/util/debug.h"
+
+#include "common/logging.h"
+#include "common/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)
/* 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
+ we don't 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
+ since the entire tree will be completely destroyed we don't care
if it is inconsistent or unbalanced while freeing the
individual nodes
*/
/* setting a NULL node to black is a nop */
static inline void trbt_set_color(trbt_node_t *node, int color)
{
- if ( (node==NULL) && (color==TRBT_BLACK) ) {
+ if (node == NULL) {
return;
}
node->rb_color = color;
}
static inline void trbt_set_color_left(trbt_node_t *node, int color)
{
- if ( ((node==NULL)||(node->left==NULL)) && (color==TRBT_BLACK) ) {
+ if (node == NULL || node->left == NULL) {
return;
}
node->left->rb_color = color;
}
static inline void trbt_set_color_right(trbt_node_t *node, int color)
{
- if ( ((node==NULL)||(node->right==NULL)) && (color==TRBT_BLACK) ) {
+ if (node == NULL || node->right == NULL) {
return;
}
node->right->rb_color = color;
}
static void
-delete_node(trbt_node_t *node, BOOL from_destructor)
+delete_node(trbt_node_t *node, bool from_destructor)
{
trbt_node_t *parent, *child, dc;
trbt_node_t *temp = NULL;
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
+ This is because we don't represent the leaf-nodes as actual nodes
in this implementation.
*/
if (!child) {
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.
+ have occurred.
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.
*/
static int node_destructor(trbt_node_t *node)
{
- delete_node(node, True);
+ delete_node(node, true);
return 0;
}
while(node){
if(key==node->key32){
- delete_node(node, False);
+ delete_node(node, false);
return;
}
if(key<node->key32){
/* 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);
+ trbt_node_t *left = node->left;
+ trbt_node_t *right = node->right;
+
+ if (left) {
+ int ret;
+ ret = trbt_traversearray32_node(left, keylen, callback, param);
+ if (ret != 0) {
+ return ret;
+ }
}
/* this is the smallest node in this subtree
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);
+ if (right) {
+ int ret;
+
+ ret = trbt_traversearray32_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);
}
}
-#if 0
+#if TEST_RB_TREE
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 (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);
+ 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");
}
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)
{
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);
git.samba.org / vlendec / samba-autobuild / .git / blobdiff