GRASS GIS 8 Programmer's Manual  8.2.2dev(2023)-3d2c704037
rbtree.h
Go to the documentation of this file.
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
Definition: rbtree.h:78
int first
Definition: rbtree.h:99
rb_compare_fn * rb_compare
Definition: rbtree.h:90
int top
Definition: rbtree.h:98
Definition: rbtree.h:93
struct RB_TREE * tree
Definition: rbtree.h:95
Definition: rbtree.h:85
size_t count
Definition: rbtree.h:89
struct RB_NODE * link[2]
Definition: rbtree.h:82
unsigned char red
Definition: rbtree.h:80
struct RB_NODE * curr_node
Definition: rbtree.h:96
size_t datasize
Definition: rbtree.h:88
int rb_compare_fn(const void *rb_a, const void *rb_b)
Definition: rbtree.h:76
#define RBTREE_MAX_HEIGHT
Definition: rbtree.h:69
void * data
Definition: rbtree.h:81
struct RB_NODE * root
Definition: rbtree.h:87