1 /*************************************************************
2  *                          USAGE                            *
3  *************************************************************
4  *
5  * NOTE: duplicates are not supported
6  *
7  * custom compare function
8  * extern int my_compare_fn(const void *, const void *);
9  * int my_compare_fn(const void *a, const void *b) {
10  *   if ((mydatastruct *) a < (mydatastruct *) b)
11  *     return -1;
12  *   else if ((mydatastruct *) a > (mydatastruct *) b)
13  *     return 1;
14  *   else if ((mydatastruct *) a == (mydatastruct *) b)
15  *     return 0;
16  * }
17  *
18  * create and initialize tree:
19  * struct RB_TREE *mytree = rbtree_create(my_compare_fn, item_size);
20  *
21  * insert items to tree:
22  * struct mydatastruct data = <some data>;
23  * if (rbtree_insert(mytree, &data) == 0)
24  * 	 G_warning("could not insert data");
25  *
26  * find item in tree:
27  * struct mydatastruct data = <some data>;
28  * if (rbtree_find(mytree, &data) == 0)
29  * 	 G_message("data not found");
30  *
31  * delete item from tree:
32  * struct mydatastruct data = <some data>;
33  * if (rbtree_remove(mytree, &data) == 0)
34  * 	  G_warning("could not find data in tree");
35  *
36  * traverse tree (get all items in tree in ascending order):
37  * struct RB_TRAV trav;
38  * rbtree_init_trav(&trav, tree);
39  * while ((data = rbtree_traverse(&trav)) != NULL) {
40  *   if (my_compare_fn(data, threshold_data) == 0) break;
41  * 	   <do something with data>;
42  *  }
43  *
44  * get a selection of items: all data > data1 and < data2
45  * start in tree where data is last smaller or first larger compared to data1
46  * struct RB_TRAV trav;
47  * rbtree_init_trav(&trav, tree);
48  * data = rbtree_traverse_start(&trav, &data1);
49  * 	 <do something with data>;
50  * while ((data = rbtree_traverse(&trav)) != NULL) {
51  *	 if (data > data2) break;
52  *   <do something with data>;
53  * }
54  *
55  * destroy tree:
56  * rbtree_destroy(mytree);
57  *
58  * debug the whole tree with
59  * rbtree_debug(mytree, mytree->root);
60  *
61  *************************************************************/
62 
63 #ifndef GRASS_RBTREE_H
64 #define GRASS_RBTREE_H
65 
66 #include <stddef.h>
67 
68 /* maximum RB Tree height */
69 #define RBTREE_MAX_HEIGHT 64        /* should be more than enough */
70 
71 /* routine to compare data items
72  * return -1 if rb_a < rb_b
73  * return  0 if rb_a == rb_b
74  * return  1 if rb_a > rb_b
75  */
76 typedef int rb_compare_fn(const void *rb_a, const void *rb_b);
77 
78 struct RB_NODE
79 {
80     unsigned char red;              /* 0 = black, 1 = red */
81     void *data;                     /* any kind of data */
82     struct RB_NODE *link[2];        /* link to children: link[0] for smaller, link[1] for larger */
83 };
84 
85 struct RB_TREE
86 {
87     struct RB_NODE *root;           /* root node */
88     size_t datasize;                /* item size */
89     size_t count;                   /* number of items in tree. */
90     rb_compare_fn *rb_compare;      /* function to compare data */
91 };
92 
93 struct RB_TRAV
94 {
95     struct RB_TREE *tree;           /* tree being traversed */
96     struct RB_NODE *curr_node;      /* current node */
97     struct RB_NODE *up[RBTREE_MAX_HEIGHT];  /* stack of parent nodes */
98     int top;                        /* index for stack */
99     int first;                      /* little helper flag */
100 };
101 
102 #include <grass/defs/rbtree.h>
103 
104 #endif
105