6 * rbtree - talloc-aware Red Black Tree
8 * This is an implementation of a red-black tree based on talloc.
9 * Talloc objects that are stored in the tree have nice properties
10 * such as when the object is talloc_free()d, the object is also
11 * automatically removed from the tree. This is done by making the
12 * nodes of the tree child objects of the talloc object stored in the
13 * tree, so that destructors are called to automatically remove the
16 * The object stored in the tree does NOT become a child object of the
17 * tree itself, so the same object can be stored under several keys at
18 * the same time, and even in several different trees at the same
21 * The example below is a trivial example program that shows how to
22 * use trees that are keyed by a uint32_t. The rb_tree code also contains
23 * support for managing trees that are keyed by an array of uint32. It
24 * is trivial to expand this to "key as string". Just pad the string with
25 * 0 to be a multiple of uint32_t and then chop it up as an array of
28 * This code originates from ctdb, where talloc based trees keyed are
29 * used in several places.
31 * License: GPL (v3 or any later version)
32 * Author: Ronnie Sahlberg <ronniesahlberg@gmail.com>
36 * #include <ccan/talloc/talloc.h>
37 * #include <ccan/rbtree/rbtree.h>
39 * static void printtree(trbt_node_t *node, int levels)
42 * if(node==NULL)return;
43 * printtree(node->left, levels+1);
44 * for(i=0;i<levels;i++)printf(" ");
45 * printf("key:%d COLOR:%s\n",
46 * node->key32, node->rb_color==TRBT_BLACK?"BLACK":"RED");
47 * printtree(node->right, levels+1);
50 * static void print_tree(trbt_tree_t *tree)
52 * if(tree->root==NULL){
53 * printf("tree is empty\n");
57 * printtree(tree->root->left, 1);
58 * printf("key:%d COLOR:%s\n", tree->root->key32,
59 * tree->root->rb_color==TRBT_BLACK?"BLACK":"RED");
60 * printtree(tree->root->right, 1);
64 * int main(int argc, char *argv[])
66 * TALLOC_CTX *mem_ctx;
72 * printf("Example of tree keyed by UINT32\n");
73 * mem_ctx = talloc_new(NULL);
75 * // create a tree and store some talloc objects there
76 * tree=trbt_create(mem_ctx, 0);
77 * for (i=0; i<10; i++) {
78 * val = talloc_asprintf(mem_ctx,
79 * "Value string for key %d", i);
80 * trbt_insert32(tree, i, val);
82 * // show what the tree looks like
85 * printf("Lookup item with key 7\n");
86 * val = trbt_lookup32(tree, 7);
87 * printf("Item with key:7 has value:%s\n", (char *)val);
88 * printf("Talloc_free this item\n");
90 * printf("Item is automagically removed from the tree\n");
93 * talloc_free(mem_ctx);
97 int main(int argc, char *argv[])
102 if (strcmp(argv[1], "depends") == 0) {
103 printf("ccan/failtest\n");
104 printf("ccan/talloc\n");