Home | History | Annotate | Line # | Download | only in dist
rbtree.h revision 1.1 
      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_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