Browse Source Download (without any required ccan dependencies)
rbtree
talloc-aware Red Black Tree
Ronnie Sahlberg <ronniesahlberg@gmail.com>
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.
#include <stdio.h>
#include <ccan/talloc/talloc.h>
#include <ccan/rbtree/rbtree.h>
static void printtree(trbt_node_t *node, int levels)
{
int i;
if(node==NULL)return;
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");
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;
}
GPL (v3 or any later version)