1 #ifndef RBTREE_H_

2 #define RBTREE_H_

3

4 struct rbtree;

5

6

7 struct rbnode {

8 void *key, *data;

9 int red;

10 struct rbnode *left, *right;

11 struct rbnode *next; /* for iterator stack */

12 };

13

14

15 typedef void *(*rb_alloc_func_t)(size_t);

16 typedef void (*rb_free_func_t)(void*);

17

18 typedef int (*rb_cmp_func_t)(const void*, const void*);

19 typedef void (*rb_del_func_t)(struct rbnode*, void*);

20

21 #define RB_KEY_ADDR (rb_cmp_func_t)(0)

22 #define RB_KEY_INT (rb_cmp_func_t)(1)

23 #define RB_KEY_STRING (rb_cmp_func_t)(3)

24

25

26 #ifdef __cplusplus

27 extern "C" {

28 #endif

29

30 struct rbtree *rb_create(rb_cmp_func_t cmp_func);

31 void rb_free(struct rbtree *rb);

32

33 int rb_init(struct rbtree *rb, rb_cmp_func_t cmp_func);

34 void rb_destroy(struct rbtree *rb);

35

36 void rb_set_allocator(struct rbtree *rb, rb_alloc_func_t alloc, rb_free_func_t free);

37 void rb_set_compare_func(struct rbtree *rb, rb_cmp_func_t func);

38 void rb_set_delete_func(struct rbtree *rb, rb_del_func_t func, void *cls);

39 /* TODO add user deep copy function */

40

41 void rb_clear(struct rbtree *rb);

42 int rb_copy(struct rbtree *dest, struct rbtree *src);

43

44 int rb_size(struct rbtree *rb);

45

46 int rb_insert(struct rbtree *rb, void *key, void *data);

47 int rb_inserti(struct rbtree *rb, int key, void *data);

48

49 int rb_delete(struct rbtree *rb, void *key);

50 int rb_deletei(struct rbtree *rb, int key);

51

52 struct rbnode *rb_find(struct rbtree *rb, void *key);

53 struct rbnode *rb_findi(struct rbtree *rb, int key);

54

55 void rb_foreach(struct rbtree *rb, void (*func)(struct rbnode*, void*), void *cls);

56

57 struct rbnode *rb_root(struct rbtree *rb);

58

59 void rb_begin(struct rbtree *rb);

60 struct rbnode *rb_next(struct rbtree *rb);

61

62 void *rb_node_key(struct rbnode *node);

63 int rb_node_keyi(struct rbnode *node);

64 void *rb_node_data(struct rbnode *node);

65

66 #ifdef __cplusplus

67 }

68 #endif

69

70

71 #endif /* RBTREE_H_ */