1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
|
#include "config.h"
#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 (v3 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/failtest\n");
printf("ccan/talloc\n");
return 0;
}
return 1;
}
|
