nuclear@68: #ifndef RBTREE_H_
nuclear@68: #define RBTREE_H_
nuclear@68: 
nuclear@86: #include <stdlib.h>	/* for size_t */
nuclear@86: 
nuclear@68: struct rbtree;
nuclear@68: struct rbnode;
nuclear@68: 
nuclear@68: 
nuclear@68: typedef void *(*rb_alloc_func_t)(size_t);
nuclear@68: typedef void (*rb_free_func_t)(void*);
nuclear@68: 
nuclear@68: typedef int (*rb_cmp_func_t)(void*, void*);
nuclear@68: typedef void (*rb_del_func_t)(struct rbnode*, void*);
nuclear@68: 
nuclear@68: 
nuclear@68: struct rbtree {
nuclear@68: 	struct rbnode *root;
nuclear@68: 
nuclear@68: 	rb_alloc_func_t alloc;
nuclear@68: 	rb_free_func_t free;
nuclear@68: 
nuclear@68: 	rb_cmp_func_t cmp;
nuclear@68: 	rb_del_func_t del;
nuclear@68: 	void *del_cls;
nuclear@68: 
nuclear@68: 	struct rbnode *rstack, *iter;
nuclear@68: };
nuclear@68: 
nuclear@68: 
nuclear@68: struct rbnode {
nuclear@68: 	void *key, *data;
nuclear@68: 	int red;
nuclear@68: 	struct rbnode *left, *right;
nuclear@68: 	struct rbnode *next;	/* for iterator stack */
nuclear@68: };
nuclear@68: 
nuclear@68: #define RB_KEY_ADDR		(rb_cmp_func_t)(0)
nuclear@68: #define RB_KEY_INT		(rb_cmp_func_t)(1)
nuclear@68: #define RB_KEY_STRING	(rb_cmp_func_t)(3)
nuclear@68: 
nuclear@68: 
nuclear@68: #ifdef __cplusplus
nuclear@68: extern "C" {
nuclear@68: #endif
nuclear@68: 
nuclear@68: struct rbtree *rb_create(rb_cmp_func_t cmp_func);
nuclear@68: void rb_free(struct rbtree *rb);
nuclear@68: 
nuclear@68: int rb_init(struct rbtree *rb, rb_cmp_func_t cmp_func);
nuclear@68: void rb_destroy(struct rbtree *rb);
nuclear@68: 
nuclear@69: void rb_clear(struct rbtree *tree);
nuclear@69: int rb_copy(struct rbtree *dest, struct rbtree *src);
nuclear@69: 
nuclear@68: void rb_set_allocator(struct rbtree *rb, rb_alloc_func_t alloc, rb_free_func_t free);
nuclear@68: void rb_set_compare_func(struct rbtree *rb, rb_cmp_func_t func);
nuclear@68: void rb_set_delete_func(struct rbtree *rb, rb_del_func_t func, void *cls);
nuclear@68: 
nuclear@68: int rb_size(struct rbtree *rb);
nuclear@68: 
nuclear@68: int rb_insert(struct rbtree *rb, void *key, void *data);
nuclear@68: int rb_inserti(struct rbtree *rb, int key, void *data);
nuclear@68: 
nuclear@68: int rb_delete(struct rbtree *rb, void *key);
nuclear@68: int rb_deletei(struct rbtree *rb, int key);
nuclear@68: 
nuclear@68: void *rb_find(struct rbtree *rb, void *key);
nuclear@68: void *rb_findi(struct rbtree *rb, int key);
nuclear@68: 
nuclear@68: void rb_foreach(struct rbtree *rb, void (*func)(struct rbnode*, void*), void *cls);
nuclear@68: 
nuclear@68: struct rbnode *rb_root(struct rbtree *rb);
nuclear@68: 
nuclear@68: void rb_begin(struct rbtree *rb);
nuclear@68: struct rbnode *rb_next(struct rbtree *rb);
nuclear@68: 
nuclear@68: void *rb_node_key(struct rbnode *node);
nuclear@68: int rb_node_keyi(struct rbnode *node);
nuclear@68: void *rb_node_data(struct rbnode *node);
nuclear@68: 
nuclear@69: 
nuclear@69: void rb_dbg_print_tree(struct rbtree *tree);
nuclear@69: 
nuclear@68: #ifdef __cplusplus
nuclear@68: }
nuclear@68: #endif
nuclear@68: 
nuclear@68: 
nuclear@68: #endif	/* RBTREE_H_ */