1/* 2 * rbtree.h -- generic red-black tree 3 * 4 * Copyright (c) 2001-2006, 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_type and the 18 * user data (poor man's inheritance). 19 */ 20typedef struct rbnode rbnode_type; 21struct rbnode { 22 rbnode_type *parent; 23 rbnode_type *left; 24 rbnode_type *right; 25 const void *key; 26 uint8_t color; 27} ATTR_PACKED; 28 29#define RBTREE_NULL &rbtree_null_node 30extern rbnode_type rbtree_null_node; 31 32typedef struct rbtree rbtree_type; 33struct rbtree { 34 region_type *region; 35 36 /* The root of the red-black tree */ 37 rbnode_type *root; 38 39 /* The number of the nodes in the tree */ 40 size_t count; 41 42 /* Current node for walks... */ 43 rbnode_type *_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} ATTR_PACKED; 48 49/* rbtree.c */ 50rbtree_type *rbtree_create(region_type *region, int (*cmpf)(const void *, const void *)); 51rbnode_type *rbtree_insert(rbtree_type *rbtree, rbnode_type *data); 52/* returns node that is now unlinked from the tree. User to delete it. 53 * returns 0 if node not present */ 54rbnode_type *rbtree_delete(rbtree_type *rbtree, const void *key); 55rbnode_type *rbtree_search(rbtree_type *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. */ 58int rbtree_find_less_equal(rbtree_type *rbtree, const void *key, rbnode_type **result); 59rbnode_type *rbtree_first(rbtree_type *rbtree); 60rbnode_type *rbtree_last(rbtree_type *rbtree); 61rbnode_type *rbtree_next(rbnode_type *rbtree); 62rbnode_type *rbtree_previous(rbnode_type *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_type 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_type*)node != RBTREE_NULL; \ 74 node = (type)rbtree_next((rbnode_type*)node)) 75 76#endif /* RBTREE_H */ 77