rbtree: new module from Ronnie.

[ccan] / ccan / rbtree / _info

diff --git a/ccan/rbtree/_info b/ccan/rbtree/_info
new file mode 100644 (file)
index 0000000..4f0b0bc
--- /dev/null
+++ b/ccan/rbtree/_info
@@ -0,0 +1,107 @@
+#include <stdio.h>
+#include <string.h>
+
+/**
+ * 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 <ronniesahlberg@gmail.com>
+ *
+ * Example:
+ *     #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;
+ *     }
+ */
+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;
+}