From b581c2380721e6bd2079a80adcb28b0ed0f3552c Mon Sep 17 00:00:00 2001 From: Rusty Russell Date: Mon, 8 Nov 2010 22:00:04 +1030 Subject: [PATCH] rbtree: new module from Ronnie. --- ccan/rbtree/_info | 107 +++++ ccan/rbtree/rbtree.c | 999 +++++++++++++++++++++++++++++++++++++++++ ccan/rbtree/rbtree.h | 86 ++++ ccan/rbtree/test/run.c | 24 + 4 files changed, 1216 insertions(+) create mode 100644 ccan/rbtree/_info create mode 100644 ccan/rbtree/rbtree.c create mode 100644 ccan/rbtree/rbtree.h create mode 100644 ccan/rbtree/test/run.c diff --git a/ccan/rbtree/_info b/ccan/rbtree/_info new file mode 100644 index 00000000..4f0b0bc1 --- /dev/null +++ b/ccan/rbtree/_info @@ -0,0 +1,107 @@ +#include +#include + +/** + * rbtree - talloc-aware Red Black Tree + * + * This is an implementation of a red-black tree based on talloc. + * Talloc objects that are stored in the tree have nice properties + * such as when the object is talloc_free()d, the object is also + * automatically removed from the tree. This is done by making the + * nodes of the tree child objects of the talloc object stored in the + * tree, so that destructors are called to automatically remove the + * node from the tree. + * + * The object stored in the tree does NOT become a child object of the + * tree itself, so the same object can be stored under several keys at + * the same time, and even in several different trees at the same + * time. + * + * The example below is a trivial example program that shows how to + * use trees that are keyed by a uint32_t. The rb_tree code also contains + * support for managing trees that are keyed by an array of uint32. It + * is trivial to expand this to "key as string". Just pad the string with + * 0 to be a multiple of uint32_t and then chop it up as an array of + * uint32_t. + * + * This code originates from ctdb, where talloc based trees keyed are + * used in several places. + * + * License: GPL (3 or any later version) + * Author: Ronnie Sahlberg + * + * Example: + * #include + * #include + * #include + * + * static void printtree(trbt_node_t *node, int levels) + * { + * int i; + * if(node==NULL)return; + * printtree(node->left, levels+1); + * for(i=0;ikey32, node->rb_color==TRBT_BLACK?"BLACK":"RED"); + * printtree(node->right, levels+1); + * } + * + * static void print_tree(trbt_tree_t *tree) + * { + * if(tree->root==NULL){ + * printf("tree is empty\n"); + * return; + * } + * printf("---\n"); + * printtree(tree->root->left, 1); + * printf("key:%d COLOR:%s\n", tree->root->key32, + * tree->root->rb_color==TRBT_BLACK?"BLACK":"RED"); + * printtree(tree->root->right, 1); + * printf("===\n"); + * } + * + * int main(int argc, char *argv[]) + * { + * TALLOC_CTX *mem_ctx; + * TALLOC_CTX *val; + * int i; + * + * trbt_tree_t *tree; + * + * printf("Example of tree keyed by UINT32\n"); + * mem_ctx = talloc_new(NULL); + * + * // create a tree and store some talloc objects there + * tree=trbt_create(mem_ctx, 0); + * for (i=0; i<10; i++) { + * val = talloc_asprintf(mem_ctx, + * "Value string for key %d", i); + * trbt_insert32(tree, i, val); + * } + * // show what the tree looks like + * print_tree(tree); + * + * printf("Lookup item with key 7\n"); + * val = trbt_lookup32(tree, 7); + * printf("Item with key:7 has value:%s\n", (char *)val); + * printf("Talloc_free this item\n"); + * talloc_free(val); + * printf("Item is automagically removed from the tree\n"); + * print_tree(tree); + * + * talloc_free(mem_ctx); + * return 0; + * } + */ +int main(int argc, char *argv[]) +{ + if (argc != 2) + return 1; + + if (strcmp(argv[1], "depends") == 0) { + printf("ccan/talloc\n"); + return 0; + } + + return 1; +} diff --git a/ccan/rbtree/rbtree.c b/ccan/rbtree/rbtree.c new file mode 100644 index 00000000..a6a7d38b --- /dev/null +++ b/ccan/rbtree/rbtree.c @@ -0,0 +1,999 @@ +/* + a talloc based red-black tree + + Copyright (C) Ronnie Sahlberg 2007 + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, see . +*/ +#include + +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, uint32_t flags) +{ + trbt_tree_t *tree; + + tree = talloc_zero(memctx, trbt_tree_t); + if (tree == NULL) { + fprintf(stderr, "Failed to allocate memory for rb tree\n"); + return NULL; + } + + /* 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_parent(trbt_node_t *node) +{ + return node->parent; +} + +static inline trbt_node_t * +trbt_grandparent(trbt_node_t *node) +{ + trbt_node_t *parent; + + parent=trbt_parent(node); + if(parent){ + return parent->parent; + } + return NULL; +} + +static inline trbt_node_t * +trbt_uncle(trbt_node_t *node) +{ + trbt_node_t *parent, *grandparent; + + parent=trbt_parent(node); + if(!parent){ + return NULL; + } + grandparent=trbt_parent(parent); + if(!grandparent){ + return NULL; + } + if(parent==grandparent->left){ + return grandparent->right; + } + return grandparent->left; +} + + +static inline void trbt_insert_case1(trbt_tree_t *tree, trbt_node_t *node); +static inline void trbt_insert_case2(trbt_tree_t *tree, trbt_node_t *node); + +static inline void +trbt_rotate_left(trbt_node_t *node) +{ + trbt_tree_t *tree = node->tree; + + if(node->parent){ + if(node->parent->left==node){ + node->parent->left=node->right; + } else { + node->parent->right=node->right; + } + } else { + tree->root=node->right; + } + node->right->parent=node->parent; + node->parent=node->right; + node->right=node->right->left; + if(node->right){ + node->right->parent=node; + } + node->parent->left=node; +} + +static inline void +trbt_rotate_right(trbt_node_t *node) +{ + trbt_tree_t *tree = node->tree; + + if(node->parent){ + if(node->parent->left==node){ + node->parent->left=node->left; + } else { + node->parent->right=node->left; + } + } else { + tree->root=node->left; + } + node->left->parent=node->parent; + node->parent=node->left; + node->left=node->left->right; + if(node->left){ + node->left->parent=node; + } + node->parent->right=node; +} + +/* NULL nodes are black by definition */ +static inline int trbt_get_color(trbt_node_t *node) +{ + if (node==NULL) { + return TRBT_BLACK; + } + return node->rb_color; +} +static inline int trbt_get_color_left(trbt_node_t *node) +{ + if (node==NULL) { + return TRBT_BLACK; + } + if (node->left==NULL) { + return TRBT_BLACK; + } + return node->left->rb_color; +} +static inline int trbt_get_color_right(trbt_node_t *node) +{ + if (node==NULL) { + return TRBT_BLACK; + } + if (node->right==NULL) { + return TRBT_BLACK; + } + return node->right->rb_color; +} +/* 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) ) { + 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) ) { + 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) ) { + return; + } + node->right->rb_color = color; +} + +static inline void +trbt_insert_case5(trbt_node_t *node) +{ + trbt_node_t *grandparent; + trbt_node_t *parent; + + parent=trbt_parent(node); + grandparent=trbt_parent(parent); + parent->rb_color=TRBT_BLACK; + grandparent->rb_color=TRBT_RED; + if( (node==parent->left) && (parent==grandparent->left) ){ + trbt_rotate_right(grandparent); + } else { + trbt_rotate_left(grandparent); + } +} + +static inline void +trbt_insert_case4(trbt_node_t *node) +{ + trbt_node_t *grandparent; + trbt_node_t *parent; + + parent=trbt_parent(node); + grandparent=trbt_parent(parent); + if(!grandparent){ + return; + } + if( (node==parent->right) && (parent==grandparent->left) ){ + trbt_rotate_left(parent); + node=node->left; + } else if( (node==parent->left) && (parent==grandparent->right) ){ + trbt_rotate_right(parent); + node=node->right; + } + trbt_insert_case5(node); +} + +static inline void +trbt_insert_case3(trbt_tree_t *tree, trbt_node_t *node) +{ + trbt_node_t *grandparent; + trbt_node_t *parent; + trbt_node_t *uncle; + + uncle=trbt_uncle(node); + if(uncle && (uncle->rb_color==TRBT_RED)){ + parent=trbt_parent(node); + parent->rb_color=TRBT_BLACK; + uncle->rb_color=TRBT_BLACK; + grandparent=trbt_grandparent(node); + grandparent->rb_color=TRBT_RED; + trbt_insert_case1(tree, grandparent); + } else { + trbt_insert_case4(node); + } +} + +static inline void +trbt_insert_case2(trbt_tree_t *tree, trbt_node_t *node) +{ + trbt_node_t *parent; + + parent=trbt_parent(node); + /* parent is always non-NULL here */ + if(parent->rb_color==TRBT_BLACK){ + return; + } + trbt_insert_case3(tree, node); +} + +static inline void +trbt_insert_case1(trbt_tree_t *tree, trbt_node_t *node) +{ + trbt_node_t *parent; + + parent=trbt_parent(node); + if(!parent){ + node->rb_color=TRBT_BLACK; + return; + } + trbt_insert_case2(tree, node); +} + +static inline trbt_node_t * +trbt_sibling(trbt_node_t *node) +{ + trbt_node_t *parent; + + parent=trbt_parent(node); + if(!parent){ + return NULL; + } + + if (node == parent->left) { + return parent->right; + } else { + return parent->left; + } +} + +static inline void +trbt_delete_case6(trbt_node_t *node) +{ + trbt_node_t *sibling, *parent; + + sibling = trbt_sibling(node); + parent = trbt_parent(node); + + trbt_set_color(sibling, parent->rb_color); + trbt_set_color(parent, TRBT_BLACK); + if (node == parent->left) { + trbt_set_color_right(sibling, TRBT_BLACK); + trbt_rotate_left(parent); + } else { + trbt_set_color_left(sibling, TRBT_BLACK); + trbt_rotate_right(parent); + } +} + + +static inline void +trbt_delete_case5(trbt_node_t *node) +{ + trbt_node_t *parent, *sibling; + + parent = trbt_parent(node); + sibling = trbt_sibling(node); + if ( (node == parent->left) + &&(trbt_get_color(sibling) == TRBT_BLACK) + &&(trbt_get_color_left(sibling) == TRBT_RED) + &&(trbt_get_color_right(sibling) == TRBT_BLACK) ){ + trbt_set_color(sibling, TRBT_RED); + trbt_set_color_left(sibling, TRBT_BLACK); + trbt_rotate_right(sibling); + trbt_delete_case6(node); + return; + } + if ( (node == parent->right) + &&(trbt_get_color(sibling) == TRBT_BLACK) + &&(trbt_get_color_right(sibling) == TRBT_RED) + &&(trbt_get_color_left(sibling) == TRBT_BLACK) ){ + trbt_set_color(sibling, TRBT_RED); + trbt_set_color_right(sibling, TRBT_BLACK); + trbt_rotate_left(sibling); + trbt_delete_case6(node); + return; + } + + trbt_delete_case6(node); +} + +static inline void +trbt_delete_case4(trbt_node_t *node) +{ + trbt_node_t *sibling; + + sibling = trbt_sibling(node); + if ( (trbt_get_color(node->parent) == TRBT_RED) + &&(trbt_get_color(sibling) == TRBT_BLACK) + &&(trbt_get_color_left(sibling) == TRBT_BLACK) + &&(trbt_get_color_right(sibling) == TRBT_BLACK) ){ + trbt_set_color(sibling, TRBT_RED); + trbt_set_color(node->parent, TRBT_BLACK); + } else { + trbt_delete_case5(node); + } +} + +static void trbt_delete_case1(trbt_node_t *node); + +static inline void +trbt_delete_case3(trbt_node_t *node) +{ + trbt_node_t *sibling; + + sibling = trbt_sibling(node); + if ( (trbt_get_color(node->parent) == TRBT_BLACK) + &&(trbt_get_color(sibling) == TRBT_BLACK) + &&(trbt_get_color_left(sibling) == TRBT_BLACK) + &&(trbt_get_color_right(sibling) == TRBT_BLACK) ){ + trbt_set_color(sibling, TRBT_RED); + trbt_delete_case1(node->parent); + } else { + trbt_delete_case4(node); + } +} + +static inline void +trbt_delete_case2(trbt_node_t *node) +{ + trbt_node_t *sibling; + + sibling = trbt_sibling(node); + if (trbt_get_color(sibling) == TRBT_RED) { + trbt_set_color(node->parent, TRBT_RED); + trbt_set_color(sibling, TRBT_BLACK); + if (node == node->parent->left) { + trbt_rotate_left(node->parent); + } else { + trbt_rotate_right(node->parent); + } + } + trbt_delete_case3(node); +} + +static void +trbt_delete_case1(trbt_node_t *node) +{ + if (!node->parent) { + return; + } else { + trbt_delete_case2(node); + } +} + +static void +delete_node(trbt_node_t *node, int 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 + predecessor instead. + The predecessor is guaranteed to have at most one child + node since its right arm must be NULL + (It must be NULL since we are its sucessor and we are above + it in the tree) + */ + if (node->left != NULL && node->right != NULL) { + /* This node has two children, just copy the data */ + /* find the predecessor */ + temp = node->left; + + while (temp->right != NULL) { + temp = temp->right; + } + + /* swap the predecessor data and key with the node to + be deleted. + */ + 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, from_destructor); + goto finished; + } + + + /* There is at most one child to this node to be deleted */ + child = node->left; + if (node->right) { + child = node->right; + } + + /* If the node to be deleted did not have any child at all we + create a temporary dummy node for the child and mark it black. + 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 + in this implementation. + */ + if (!child) { + child = &dc; + child->tree = node->tree; + child->left=NULL; + child->right=NULL; + child->rb_color=TRBT_BLACK; + child->data=NULL; + } + + /* replace node with child */ + parent = trbt_parent(node); + if (parent) { + if (parent->left == node) { + parent->left = child; + } else { + parent->right = child; + } + } else { + node->tree->root = child; + } + child->parent = node->parent; + + + if (node->rb_color == TRBT_BLACK) { + if (trbt_get_color(child) == TRBT_RED) { + child->rb_color = TRBT_BLACK; + } else { + trbt_delete_case1(child); + } + } + + /* If we had to create a temporary dummy node to represent a black + leaf child we now has to delete it. + 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. + + 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. + Othervise it is enough to just unlink the child from its new + parent. + */ + if (child == &dc) { + if (child->parent == NULL) { + node->tree->root = NULL; + } else if (child == child->parent->left) { + child->parent->left = NULL; + } else { + child->parent->right = NULL; + } + } + +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, 1); + + return 0; +} + +static inline trbt_node_t * +trbt_create_node(trbt_tree_t *tree, trbt_node_t *parent, uint32_t key, void *data) +{ + trbt_node_t *node; + + node=talloc_zero(tree, trbt_node_t); + if (node == NULL) { + fprintf(stderr, "Failed to allocate memory for rb node\n"); + return NULL; + } + + node->tree=tree; + node->rb_color=TRBT_BLACK; + node->parent=parent; + node->left=NULL; + node->right=NULL; + node->key32=key; + 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; +} + +/* insert a new node in the tree. + if there is already a node with a matching key in the tree + we replace it with the new data and return a pointer to the old data + in case the caller wants to take any special action + */ +void * +trbt_insert32(trbt_tree_t *tree, uint32_t key, void *data) +{ + trbt_node_t *node; + + node=tree->root; + + /* is this the first node ?*/ + if(!node){ + node = trbt_create_node(tree, NULL, key, data); + + tree->root=node; + return NULL; + } + + /* it was not the new root so walk the tree until we find where to + * insert this new leaf. + */ + while(1){ + /* this node already exists, replace data and return the + old data + */ + if(key==node->key32){ + void *old_data; + + old_data = 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; + } + if(keykey32) { + if(!node->left){ + /* new node to the left */ + trbt_node_t *new_node; + + new_node = trbt_create_node(tree, node, key, data); + node->left=new_node; + node=new_node; + + break; + } + node=node->left; + continue; + } + if(key>node->key32) { + if(!node->right){ + /* new node to the right */ + trbt_node_t *new_node; + + new_node = trbt_create_node(tree, node, key, data); + node->right=new_node; + node=new_node; + break; + } + node=node->right; + continue; + } + } + + /* node will now point to the newly created node */ + node->rb_color=TRBT_RED; + trbt_insert_case1(tree, node); + return NULL; +} + +void * +trbt_lookup32(trbt_tree_t *tree, uint32_t key) +{ + trbt_node_t *node; + + node=tree->root; + + while(node){ + if(key==node->key32){ + return node->data; + } + if(keykey32){ + node=node->left; + continue; + } + if(key>node->key32){ + node=node->right; + continue; + } + } + 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) +{ + trbt_node_t *node; + + node=tree->root; + + while(node){ + if(key==node->key32){ + delete_node(node, 0); + return; + } + if(keykey32){ + node=node->left; + continue; + } + if(key>node->key32){ + node=node->right; + continue; + } + } +} + + +void +trbt_insert32_callback(trbt_tree_t *tree, uint32_t key, void *(*callback)(void *param, void *data), void *param) +{ + trbt_node_t *node; + + node=tree->root; + + /* is this the first node ?*/ + if(!node){ + node = trbt_create_node(tree, NULL, key, + callback(param, NULL)); + + tree->root=node; + return; + } + + /* it was not the new root so walk the tree until we find where to + * insert this new leaf. + */ + while(1){ + /* this node already exists, replace it + */ + if(key==node->key32){ + node->data = callback(param, node->data); + talloc_steal(node->data, node); + + return; + } + if(keykey32) { + if(!node->left){ + /* new node to the left */ + trbt_node_t *new_node; + + new_node = trbt_create_node(tree, node, key, + callback(param, NULL)); + node->left=new_node; + node=new_node; + + break; + } + node=node->left; + continue; + } + if(key>node->key32) { + if(!node->right){ + /* new node to the right */ + trbt_node_t *new_node; + + new_node = trbt_create_node(tree, node, key, + callback(param, NULL)); + node->right=new_node; + node=new_node; + break; + } + node=node->right; + continue; + } + } + + /* node will now point to the newly created node */ + node->rb_color=TRBT_RED; + trbt_insert_case1(tree, node); + return; +} + + +struct trbt_array_param { + void *(*callback)(void *param, void *data); + void *param; + uint32_t keylen; + uint32_t *key; + trbt_tree_t *tree; +}; +static void *array_insert_callback(void *p, void *data) +{ + struct trbt_array_param *param = (struct trbt_array_param *)p; + trbt_tree_t *tree = NULL; + + + /* if keylen has reached 0 we are done and can call the users + callback function with the users parameters + */ + if (param->keylen == 0) { + return param->callback(param->param, data); + } + + + /* keylen is not zero yes so we must create/process more subtrees */ + /* if data is NULL this means we did not yet have a subtree here + and we must create one. + */ + if (data == NULL) { + /* 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_insertarray32_callback(tree, param->keylen, param->key, param->callback, param->param); + + /* now return either the old tree we got in *data or the new tree + we created to our caller so he can update his pointer in his + tree to point to our subtree + */ + return tree; +} + + + +/* insert into the tree using an array of uint32 as a key */ +void +trbt_insertarray32_callback(trbt_tree_t *tree, uint32_t keylen, uint32_t *key, void *(*cb)(void *param, void *data), void *pm) +{ + struct trbt_array_param tap; + + /* keylen-1 and key[1] since the call to insert32 will consume the + first part of the key. + */ + tap.callback= cb; + tap.param = pm; + tap.keylen = keylen-1; + tap.key = &key[1]; + tap.tree = tree; + + 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) +{ + /* if keylen is 1 we can do a regular lookup and return this to the + user + */ + if (keylen == 1) { + return trbt_lookup32(tree, key[0]); + } + + /* we need to lookup the next subtree */ + tree = trbt_lookup32(tree, key[0]); + if (tree == NULL) { + /* the key does not exist, return NULL */ + return NULL; + } + + /* now lookup the next part of the key in our new tree */ + return trbt_lookuparray32(tree, keylen-1, &key[1]); +} + + +/* 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); +} + + +/* 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); +} + + diff --git a/ccan/rbtree/rbtree.h b/ccan/rbtree/rbtree.h new file mode 100644 index 00000000..e19c1f7b --- /dev/null +++ b/ccan/rbtree/rbtree.h @@ -0,0 +1,86 @@ +/* + a talloc based red-black tree + + Copyright (C) Ronnie Sahlberg 2007 + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, see . +*/ +#ifndef CCAN_RBTREE_H +#define CCAN_RBTREE_H +#include +#include + +#define TRBT_RED 0x00 +#define TRBT_BLACK 0x01 +typedef struct trbt_node { + struct trbt_tree *tree; + struct trbt_node *parent; + struct trbt_node *left; + struct trbt_node *right; + uint32_t rb_color; + uint32_t key32; + void *data; +} trbt_node_t; + +typedef struct trbt_tree { + 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, 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); + +/* Insert a new node into the tree. If there was already a node with this + key the pointer to the previous data is returned. + The tree will talloc_steal() the data inserted into the tree . +*/ +void *trbt_insert32(trbt_tree_t *tree, uint32_t key, void *data); + +/* Insert a new node into the tree. + If this is a new node: + callback is called with data==NULL and param=param + the returned value from the callback is talloc_stolen and inserted in the + tree. + If a node already exists for this key then: + callback is called with data==existing data and param=param + the returned calue is talloc_stolen and inserted in the tree +*/ +void trbt_insert32_callback(trbt_tree_t *tree, uint32_t key, void *(*callback)(void *param, void *data), void *param); + +/* Delete a node from the tree and free all data associated with it */ +void trbt_delete32(trbt_tree_t *tree, uint32_t key); + + +/* insert into the tree with a key based on an array of uint32 */ +void trbt_insertarray32_callback(trbt_tree_t *tree, uint32_t keylen, uint32_t *key, void *(*callback)(void *param, void *data), void *param); + +/* Lookup a node in the tree with a key based on an array of uint32 + 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); + +/* Lookup the first node in the tree with a key based on an array of uint32 + and return a pointer to data or NULL */ +void *trbt_findfirstarray32(trbt_tree_t *tree, uint32_t keylen); + +#endif /* CCAN_RBTREE_H */ diff --git a/ccan/rbtree/test/run.c b/ccan/rbtree/test/run.c new file mode 100644 index 00000000..67ffd72d --- /dev/null +++ b/ccan/rbtree/test/run.c @@ -0,0 +1,24 @@ +#include +#include + +int main(void) +{ + /* This is how many tests you plan to run */ + plan_tests(3); + + /* Simple thing we expect to succeed */ + ok1(some_test()) + /* Same, with an explicit description of the test. */ + ok(some_test(), "%s with no args should return 1", "some_test") + /* How to print out messages for debugging. */ + diag("Address of some_test is %p", &some_test) + /* Conditional tests must be explicitly skipped. */ +#if HAVE_SOME_FEATURE + ok1(test_some_feature()) +#else + skip(1, "Don't have SOME_FEATURE") +#endif + + /* This exits depending on whether all tests passed */ + return exit_status(); +} -- 2.39.2