1 /* 2 * rbtree.h -- generic red-black tree 3 * 4 * Copyright (c) 2001-2011, NLnet Labs. All rights reserved. 5 * 6 * See LICENSE for the license. 7 * 8 */ 9 10 #ifndef _RBTREE_H_ 11 #define _RBTREE_H_ 12 13 #include "region-allocator.h" 14 15 /* 16 * This structure must be the first member of the data structure in 17 * the rbtree. This allows easy casting between an rbnode_t and the 18 * user data (poor man's inheritance). 19 */ 20 typedef struct rbnode_t rbnode_t; 21 struct rbnode_t { 22 rbnode_t *parent; 23 rbnode_t *left; 24 rbnode_t *right; 25 const void *key; 26 uint8_t color; 27 }; 28 29 #define RBTREE_NULL &rbtree_null_node 30 extern rbnode_t rbtree_null_node; 31 32 typedef struct rbtree_t rbtree_t; 33 struct rbtree_t { 34 region_type *region; 35 36 /* The root of the red-black tree */ 37 rbnode_t *root; 38 39 /* The number of the nodes in the tree */ 40 size_t count; 41 42 /* Current node for walks... */ 43 rbnode_t *_node; 44 45 /* Key compare function. <0,0,>0 like strcmp. Return 0 on two NULL ptrs. */ 46 int (*cmp) (const void *, const void *); 47 }; 48 49 /* rbtree.c */ 50 rbtree_t *rbtree_create(region_type *region, int (*cmpf)(const void *, const void *)); 51 rbnode_t *rbtree_insert(rbtree_t *rbtree, rbnode_t *data); 52 /* returns node that is now unlinked from the tree. User to delete it. 53 * returns 0 if node not present */ 54 rbnode_t *rbtree_delete(rbtree_t *rbtree, const void *key); 55 rbnode_t *rbtree_search(rbtree_t *rbtree, const void *key); 56 /* returns true if exact match in result. Else result points to <= element, 57 or NULL if key is smaller than the smallest key. */ 58 int rbtree_find_less_equal(rbtree_t *rbtree, const void *key, rbnode_t **result); 59 rbnode_t *rbtree_first(rbtree_t *rbtree); 60 rbnode_t *rbtree_last(rbtree_t *rbtree); 61 rbnode_t *rbtree_next(rbnode_t *rbtree); 62 rbnode_t *rbtree_previous(rbnode_t *rbtree); 63 64 #define RBTREE_WALK(rbtree, k, d) \ 65 for((rbtree)->_node = rbtree_first(rbtree);\ 66 (rbtree)->_node != RBTREE_NULL && ((k) = (rbtree)->_node->key) && \ 67 ((d) = (void *) (rbtree)->_node); (rbtree)->_node = rbtree_next((rbtree)->_node)) 68 69 /* call with node=variable of struct* with rbnode_t as first element. 70 with type is the type of a pointer to that struct. */ 71 #define RBTREE_FOR(node, type, rbtree) \ 72 for(node=(type)rbtree_first(rbtree); \ 73 (rbnode_t*)node != RBTREE_NULL; \ 74 node = (type)rbtree_next((rbnode_t*)node)) 75 76 #endif /* _RBTREE_H_ */ 77