]>
Commit | Line | Data |
---|---|---|
1 | /* | |
2 | * charybdis: an advanced ircd. | |
3 | * rb_radixtree.h: Dictionary-based storage. | |
4 | * | |
5 | * Copyright (c) 2007-2016 William Pitcock <nenolod -at- dereferenced.org> | |
6 | * Copyright (c) 2007-2016 Jilles Tjoelker <jilles -at- stack.nl> | |
7 | * | |
8 | * Redistribution and use in source and binary forms, with or without | |
9 | * modification, are permitted provided that the following conditions are | |
10 | * met: | |
11 | * | |
12 | * 1. Redistributions of source code must retain the above copyright notice, | |
13 | * this list of conditions and the following disclaimer. | |
14 | * | |
15 | * 2. Redistributions in binary form must reproduce the above copyright | |
16 | * notice, this list of conditions and the following disclaimer in the | |
17 | * documentation and/or other materials provided with the distribution. | |
18 | * | |
19 | * 3. The name of the author may not be used to endorse or promote products | |
20 | * derived from this software without specific prior written permission. | |
21 | * | |
22 | * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR | |
23 | * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED | |
24 | * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE | |
25 | * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, | |
26 | * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES | |
27 | * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR | |
28 | * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) | |
29 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, | |
30 | * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING | |
31 | * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE | |
32 | * POSSIBILITY OF SUCH DAMAGE. | |
33 | */ | |
34 | ||
35 | #ifndef __rb_radixtree_H__ | |
36 | #define __rb_radixtree_H__ | |
37 | ||
38 | struct rb_radixtree; /* defined in src/rb_radixtree.c */ | |
39 | ||
40 | struct rb_radixtree_leaf; /* defined in src/rb_radixtree.c */ | |
41 | ||
42 | typedef struct rb_radixtree rb_radixtree; | |
43 | typedef struct rb_radixtree_leaf rb_radixtree_leaf; | |
44 | typedef struct rb_radixtree_iteration_state rb_radixtree_iteration_state; | |
45 | ||
46 | /* | |
47 | * struct rb_radixtree_iteration_state, private. | |
48 | */ | |
49 | struct rb_radixtree_iteration_state | |
50 | { | |
51 | rb_radixtree_leaf *cur, *next; | |
52 | void *pspare[4]; | |
53 | int ispare[4]; | |
54 | }; | |
55 | ||
56 | /* | |
57 | * this is a convenience macro for inlining iteration of dictionaries. | |
58 | */ | |
59 | #define RB_RADIXTREE_FOREACH(element, state, dict) \ | |
60 | for (rb_radixtree_foreach_start((dict), (state)); (element = rb_radixtree_foreach_cur((dict), (state))); rb_radixtree_foreach_next((dict), (state))) | |
61 | ||
62 | #define RB_RADIXTREE_FOREACH_FROM(element, state, dict, key) \ | |
63 | for (rb_radixtree_foreach_start_from((dict), (state), (key)); (element = rb_radixtree_foreach_cur((dict), (state))); rb_radixtree_foreach_next((dict), (state))) | |
64 | ||
65 | /* | |
66 | * rb_radixtree_create() creates a new patricia tree of the defined resolution. | |
67 | * compare_cb is the canonizing function. | |
68 | */ | |
69 | ||
70 | extern rb_radixtree *rb_radixtree_create(const char *name, void (*canonize_cb)(char *key)); | |
71 | ||
72 | /* | |
73 | * rb_radixtree_shutdown() deallocates all heaps used in patricia trees. This is | |
74 | * useful on embedded devices with little memory, and/or when you know you won't need | |
75 | * any more patricia trees. | |
76 | */ | |
77 | extern void rb_radixtree_shutdown(void); | |
78 | ||
79 | /* | |
80 | * rb_radixtree_destroy() destroys all entries in a dtree, and also optionally calls | |
81 | * a defined callback function to destroy any data attached to it. | |
82 | */ | |
83 | extern void rb_radixtree_destroy(rb_radixtree *dtree, void (*destroy_cb)(const char *key, void *data, void *privdata), void *privdata); | |
84 | ||
85 | /* | |
86 | * rb_radixtree_foreach() iterates all entries in a dtree, and also optionally calls | |
87 | * a defined callback function to use any data attached to it. | |
88 | * | |
89 | * To shortcircuit iteration, return non-zero from the callback function. | |
90 | */ | |
91 | extern void rb_radixtree_foreach(rb_radixtree *dtree, int (*foreach_cb)(const char *key, void *data, void *privdata), void *privdata); | |
92 | ||
93 | /* | |
94 | * rb_radixtree_search() iterates all entries in a dtree, and also optionally calls | |
95 | * a defined callback function to use any data attached to it. | |
96 | * | |
97 | * When the object is found, a non-NULL is returned from the callback, which results | |
98 | * in that object being returned to the user. | |
99 | */ | |
100 | extern void *rb_radixtree_search(rb_radixtree *dtree, void *(*foreach_cb)(const char *key, void *data, void *privdata), void *privdata); | |
101 | ||
102 | /* | |
103 | * rb_radixtree_foreach_start() begins an iteration over all items | |
104 | * keeping state in the given struct. If there is only one iteration | |
105 | * in progress at a time, it is permitted to remove the current element | |
106 | * of the iteration (but not any other element). | |
107 | */ | |
108 | extern void rb_radixtree_foreach_start(rb_radixtree *dtree, rb_radixtree_iteration_state *state); | |
109 | ||
110 | /* | |
111 | * rb_radixtree_foreach_start_from() begins an iteration over all items, | |
112 | * starting with the item specified by `key`. If there is only one iteration | |
113 | * in progress at a time, it is permitted to remove the current element | |
114 | * of the iteration (but not any other element). | |
115 | * Use NULL as a key to have it start at the beginning. | |
116 | */ | |
117 | extern void rb_radixtree_foreach_start_from(rb_radixtree *dtree, rb_radixtree_iteration_state *state, const char *key); | |
118 | ||
119 | /* | |
120 | * rb_radixtree_foreach_cur() returns the current element of the iteration, | |
121 | * or NULL if there are no more elements. | |
122 | */ | |
123 | extern void *rb_radixtree_foreach_cur(rb_radixtree *dtree, rb_radixtree_iteration_state *state); | |
124 | ||
125 | /* | |
126 | * rb_radixtree_foreach_next() moves to the next element. | |
127 | */ | |
128 | extern void rb_radixtree_foreach_next(rb_radixtree *dtree, rb_radixtree_iteration_state *state); | |
129 | ||
130 | /* | |
131 | * rb_radixtree_add() adds a key->value entry to the patricia tree. | |
132 | */ | |
133 | extern int rb_radixtree_add(rb_radixtree *dtree, const char *key, void *data); | |
134 | ||
135 | /* | |
136 | * rb_radixtree_find() returns data from a dtree for key 'key'. | |
137 | */ | |
138 | extern void *rb_radixtree_retrieve(rb_radixtree *dtree, const char *key); | |
139 | ||
140 | /* | |
141 | * rb_radixtree_delete() deletes a key->value entry from the patricia tree. | |
142 | */ | |
143 | extern void *rb_radixtree_delete(rb_radixtree *dtree, const char *key); | |
144 | ||
145 | /* Low-level functions */ | |
146 | rb_radixtree_leaf *rb_radixtree_elem_add(rb_radixtree *dtree, const char *key, void *data); | |
147 | rb_radixtree_leaf *rb_radixtree_elem_find(rb_radixtree *dtree, const char *key, int fuzzy); | |
148 | void rb_radixtree_elem_delete(rb_radixtree *dtree, rb_radixtree_leaf *elem); | |
149 | const char *rb_radixtree_elem_get_key(rb_radixtree_leaf *elem); | |
150 | void rb_radixtree_elem_set_data(rb_radixtree_leaf *elem, void *data); | |
151 | void *rb_radixtree_elem_get_data(rb_radixtree_leaf *elem); | |
152 | ||
153 | unsigned int rb_radixtree_size(rb_radixtree *dict); | |
154 | void rb_radixtree_stats(rb_radixtree *dict, void (*cb)(const char *line, void *privdata), void *privdata); | |
155 | void rb_radixtree_stats_walk(void (*cb)(const char *line, void *privdata), void *privdata); | |
156 | ||
157 | #endif |