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