1 /*

2 rbtree - simple balanced binary search tree (red-black tree) library.

3 Copyright (C) 2011-2014 John Tsiombikas <nuclear@member.fsf.org>

4

5 rbtree is free software, feel free to use, modify, and redistribute it, under

6 the terms of the 3-clause BSD license. See COPYING for details.

7 */

8 #ifndef RBTREE_H_

9 #define RBTREE_H_

10

11 struct rbtree;

12

13

14 struct rbnode {

15 void *key, *data;

16 int red;

17 struct rbnode *left, *right;

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

19 };

20

21

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

23 typedef void (*rb_free_func_t)(void*);

24

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

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

27

28 #define RB_KEY_ADDR (rb_cmp_func_t)(0)

29 #define RB_KEY_INT (rb_cmp_func_t)(1)

30 #define RB_KEY_STRING (rb_cmp_func_t)(3)

31

32

33 #ifdef __cplusplus

34 extern "C" {

35 #endif

36

37 struct rbtree *rb_create(rb_cmp_func_t cmp_func);

38 void rb_free(struct rbtree *rb);

39

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

41 void rb_destroy(struct rbtree *rb);

42

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

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

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

46 /* TODO add user deep copy function */

47

48 void rb_clear(struct rbtree *rb);

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

50

51 int rb_size(struct rbtree *rb);

52

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

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

55

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

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

58

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

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

61

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

63

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

65

66 void rb_begin(struct rbtree *rb);

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

68

69 void *rb_node_key(struct rbnode *node);

70 int rb_node_keyi(struct rbnode *node);

71 void *rb_node_data(struct rbnode *node);

72

73 #ifdef __cplusplus

74 }

75 #endif

76

77

78 #endif /* RBTREE_H_ */