git.ozlabs.org Git - ccan/blob - ccan/rbtree/_info

   1 #include "config.h"
   2 #include <stdio.h>
   3 #include <string.h>
   4
   5 /**
   6  * rbtree - talloc-aware Red Black Tree
   7  *
   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
  14  * node from the tree.
  15  *
  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
  19  * time.
  20  *
  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
  26  * uint32_t.
  27  *
  28  * This code originates from ctdb, where talloc based trees keyed are
  29  *  used in several places.
  30  *
  31  * License: GPL (v3 or any later version)
  32  * Author: Ronnie Sahlberg <ronniesahlberg@gmail.com>
  33  *
  34  * Example:
  35  *      #include <stdio.h>
  36  *      #include <ccan/talloc/talloc.h>
  37  *      #include <ccan/rbtree/rbtree.h>
  38  *
  39  *      static void printtree(trbt_node_t *node, int levels)
  40  *      {
  41  *              int i;
  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);
  48  *      }
  49  *
  50  *      static void print_tree(trbt_tree_t *tree)
  51  *      {
  52  *              if(tree->root==NULL){
  53  *                      printf("tree is empty\n");
  54  *                      return;
  55  *              }
  56  *              printf("---\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);
  61  *              printf("===\n");
  62  *      }
  63  *
  64  *      int main(int argc, char *argv[])
  65  *      {
  66  *              TALLOC_CTX *mem_ctx;
  67  *              TALLOC_CTX *val;
  68  *              int i;
  69  *
  70  *              trbt_tree_t *tree;
  71  *
  72  *              printf("Example of tree keyed by UINT32\n");
  73  *              mem_ctx = talloc_new(NULL);
  74  *
  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);
  81  *              }
  82  *              // show what the tree looks like
  83  *              print_tree(tree);
  84  *
  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");
  89  *              talloc_free(val);
  90  *              printf("Item is automagically removed from the tree\n");
  91  *              print_tree(tree);
  92  *
  93  *              talloc_free(mem_ctx);
  94  *              return 0;
  95  *      }
  96  */
  97 int main(int argc, char *argv[])
  98 {
  99         if (argc != 2)
 100                 return 1;
 101
 102         if (strcmp(argv[1], "depends") == 0) {
 103                 printf("ccan/failtest\n");
 104                 printf("ccan/talloc\n");
 105                 return 0;
 106         }
 107
 108         return 1;
 109 }