| rev |
line source |
|
nuclear@17
|
1 /*
|
|
nuclear@17
|
2 rbtree - simple balanced binary search tree (red-black tree) library.
|
|
nuclear@17
|
3 Copyright (C) 2011-2014 John Tsiombikas <nuclear@member.fsf.org>
|
|
nuclear@17
|
4
|
|
nuclear@17
|
5 rbtree is free software, feel free to use, modify, and redistribute it, under
|
|
nuclear@17
|
6 the terms of the 3-clause BSD license. See COPYING for details.
|
|
nuclear@17
|
7 */
|
|
nuclear@17
|
8 #ifndef RBTREE_H_
|
|
nuclear@17
|
9 #define RBTREE_H_
|
|
nuclear@17
|
10
|
|
nuclear@17
|
11 struct rbtree;
|
|
nuclear@17
|
12
|
|
nuclear@17
|
13
|
|
nuclear@17
|
14 struct rbnode {
|
|
nuclear@17
|
15 void *key, *data;
|
|
nuclear@17
|
16 int red;
|
|
nuclear@17
|
17 struct rbnode *left, *right;
|
|
nuclear@17
|
18 struct rbnode *next; /* for iterator stack */
|
|
nuclear@17
|
19 };
|
|
nuclear@17
|
20
|
|
nuclear@17
|
21
|
|
nuclear@17
|
22 typedef void *(*rb_alloc_func_t)(size_t);
|
|
nuclear@17
|
23 typedef void (*rb_free_func_t)(void*);
|
|
nuclear@17
|
24
|
|
nuclear@17
|
25 typedef int (*rb_cmp_func_t)(const void*, const void*);
|
|
nuclear@17
|
26 typedef void (*rb_del_func_t)(struct rbnode*, void*);
|
|
nuclear@17
|
27
|
|
nuclear@17
|
28 #define RB_KEY_ADDR (rb_cmp_func_t)(0)
|
|
nuclear@17
|
29 #define RB_KEY_INT (rb_cmp_func_t)(1)
|
|
nuclear@17
|
30 #define RB_KEY_STRING (rb_cmp_func_t)(3)
|
|
nuclear@17
|
31
|
|
nuclear@17
|
32
|
|
nuclear@17
|
33 #ifdef __cplusplus
|
|
nuclear@17
|
34 extern "C" {
|
|
nuclear@17
|
35 #endif
|
|
nuclear@17
|
36
|
|
nuclear@17
|
37 struct rbtree *rb_create(rb_cmp_func_t cmp_func);
|
|
nuclear@17
|
38 void rb_free(struct rbtree *rb);
|
|
nuclear@17
|
39
|
|
nuclear@17
|
40 int rb_init(struct rbtree *rb, rb_cmp_func_t cmp_func);
|
|
nuclear@17
|
41 void rb_destroy(struct rbtree *rb);
|
|
nuclear@17
|
42
|
|
nuclear@17
|
43 void rb_set_allocator(struct rbtree *rb, rb_alloc_func_t alloc, rb_free_func_t free);
|
|
nuclear@17
|
44 void rb_set_compare_func(struct rbtree *rb, rb_cmp_func_t func);
|
|
nuclear@17
|
45 void rb_set_delete_func(struct rbtree *rb, rb_del_func_t func, void *cls);
|
|
nuclear@17
|
46 /* TODO add user deep copy function */
|
|
nuclear@17
|
47
|
|
nuclear@17
|
48 void rb_clear(struct rbtree *rb);
|
|
nuclear@17
|
49 int rb_copy(struct rbtree *dest, struct rbtree *src);
|
|
nuclear@17
|
50
|
|
nuclear@17
|
51 int rb_size(struct rbtree *rb);
|
|
nuclear@17
|
52
|
|
nuclear@17
|
53 int rb_insert(struct rbtree *rb, void *key, void *data);
|
|
nuclear@17
|
54 int rb_inserti(struct rbtree *rb, int key, void *data);
|
|
nuclear@17
|
55
|
|
nuclear@17
|
56 int rb_delete(struct rbtree *rb, void *key);
|
|
nuclear@17
|
57 int rb_deletei(struct rbtree *rb, int key);
|
|
nuclear@17
|
58
|
|
nuclear@17
|
59 struct rbnode *rb_find(struct rbtree *rb, void *key);
|
|
nuclear@17
|
60 struct rbnode *rb_findi(struct rbtree *rb, int key);
|
|
nuclear@17
|
61
|
|
nuclear@17
|
62 void rb_foreach(struct rbtree *rb, void (*func)(struct rbnode*, void*), void *cls);
|
|
nuclear@17
|
63
|
|
nuclear@17
|
64 struct rbnode *rb_root(struct rbtree *rb);
|
|
nuclear@17
|
65
|
|
nuclear@17
|
66 void rb_begin(struct rbtree *rb);
|
|
nuclear@17
|
67 struct rbnode *rb_next(struct rbtree *rb);
|
|
nuclear@17
|
68
|
|
nuclear@17
|
69 void *rb_node_key(struct rbnode *node);
|
|
nuclear@17
|
70 int rb_node_keyi(struct rbnode *node);
|
|
nuclear@17
|
71 void *rb_node_data(struct rbnode *node);
|
|
nuclear@17
|
72
|
|
nuclear@17
|
73 #ifdef __cplusplus
|
|
nuclear@17
|
74 }
|
|
nuclear@17
|
75 #endif
|
|
nuclear@17
|
76
|
|
nuclear@17
|
77
|
|
nuclear@17
|
78 #endif /* RBTREE_H_ */
|
