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