nuclear@6: /* nuclear@6: rbtree - simple balanced binary search tree (red-black tree) library. nuclear@6: Copyright (C) 2011-2014 John Tsiombikas nuclear@6: nuclear@6: rbtree is free software, feel free to use, modify, and redistribute it, under nuclear@6: the terms of the 3-clause BSD license. See COPYING for details. nuclear@6: */ nuclear@6: #ifndef RBTREE_H_ nuclear@6: #define RBTREE_H_ nuclear@6: nuclear@6: struct rbtree; nuclear@6: nuclear@6: nuclear@6: struct rbnode { nuclear@6: void *key, *data; nuclear@6: int red; nuclear@6: struct rbnode *left, *right; nuclear@6: struct rbnode *next; /* for iterator stack */ nuclear@6: }; nuclear@6: nuclear@6: nuclear@6: typedef void *(*rb_alloc_func_t)(size_t); nuclear@6: typedef void (*rb_free_func_t)(void*); nuclear@6: nuclear@6: typedef int (*rb_cmp_func_t)(const void*, const void*); nuclear@6: typedef void (*rb_del_func_t)(struct rbnode*, void*); nuclear@6: nuclear@6: #define RB_KEY_ADDR (rb_cmp_func_t)(0) nuclear@6: #define RB_KEY_INT (rb_cmp_func_t)(1) nuclear@6: #define RB_KEY_STRING (rb_cmp_func_t)(3) nuclear@6: nuclear@6: nuclear@6: #ifdef __cplusplus nuclear@6: extern "C" { nuclear@6: #endif nuclear@6: nuclear@6: struct rbtree *rb_create(rb_cmp_func_t cmp_func); nuclear@6: void rb_free(struct rbtree *rb); nuclear@6: nuclear@6: int rb_init(struct rbtree *rb, rb_cmp_func_t cmp_func); nuclear@6: void rb_destroy(struct rbtree *rb); nuclear@6: nuclear@6: void rb_set_allocator(struct rbtree *rb, rb_alloc_func_t alloc, rb_free_func_t free); nuclear@6: void rb_set_compare_func(struct rbtree *rb, rb_cmp_func_t func); nuclear@6: void rb_set_delete_func(struct rbtree *rb, rb_del_func_t func, void *cls); nuclear@6: /* TODO add user deep copy function */ nuclear@6: nuclear@6: void rb_clear(struct rbtree *rb); nuclear@6: int rb_copy(struct rbtree *dest, struct rbtree *src); nuclear@6: nuclear@6: int rb_size(struct rbtree *rb); nuclear@6: nuclear@6: int rb_insert(struct rbtree *rb, void *key, void *data); nuclear@6: int rb_inserti(struct rbtree *rb, int key, void *data); nuclear@6: nuclear@6: int rb_delete(struct rbtree *rb, void *key); nuclear@6: int rb_deletei(struct rbtree *rb, int key); nuclear@6: nuclear@6: struct rbnode *rb_find(struct rbtree *rb, void *key); nuclear@6: struct rbnode *rb_findi(struct rbtree *rb, int key); nuclear@6: nuclear@6: void rb_foreach(struct rbtree *rb, void (*func)(struct rbnode*, void*), void *cls); nuclear@6: nuclear@6: struct rbnode *rb_root(struct rbtree *rb); nuclear@6: nuclear@6: void rb_begin(struct rbtree *rb); nuclear@6: struct rbnode *rb_next(struct rbtree *rb); nuclear@6: nuclear@6: void *rb_node_key(struct rbnode *node); nuclear@6: int rb_node_keyi(struct rbnode *node); nuclear@6: void *rb_node_data(struct rbnode *node); nuclear@6: nuclear@6: #ifdef __cplusplus nuclear@6: } nuclear@6: #endif nuclear@6: nuclear@6: nuclear@6: #endif /* RBTREE_H_ */