]>
Commit | Line | Data |
---|---|---|
8e6ba6f9 AC |
1 | /* |
2 | * charybdis: an advanced ircd. | |
3 | * irc_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 __irc_radixtree_H__ | |
36 | #define __irc_radixtree_H__ | |
37 | ||
38 | struct irc_radixtree;/* defined in ircd/irc_radixtree.c */ | |
39 | ||
40 | struct irc_radixtree_leaf; /* defined in ircd/irc_radixtree.c */ | |
41 | ||
42 | /* | |
43 | * struct irc_radixtree_iteration_state, private. | |
44 | */ | |
45 | struct irc_radixtree_iteration_state | |
46 | { | |
47 | struct irc_radixtree_leaf *cur, *next; | |
48 | void *pspare[4]; | |
49 | int ispare[4]; | |
50 | }; | |
51 | ||
52 | /* | |
53 | * this is a convenience macro for inlining iteration of dictionaries. | |
54 | */ | |
55 | #define IRC_RADIXTREE_FOREACH(element, state, dict) \ | |
56 | for (irc_radixtree_foreach_start((dict), (state)); (element = irc_radixtree_foreach_cur((dict), (state))); irc_radixtree_foreach_next((dict), (state))) | |
57 | ||
0d9a72de AC |
58 | #define IRC_RADIXTREE_FOREACH_FROM(element, state, dict, key) \ |
59 | for (irc_radixtree_foreach_start_from((dict), (state), (key)); (element = irc_radixtree_foreach_cur((dict), (state))); irc_radixtree_foreach_next((dict), (state))) | |
60 | ||
8e6ba6f9 AC |
61 | /* |
62 | * irc_radixtree_create() creates a new patricia tree of the defined resolution. | |
63 | * compare_cb is the canonizing function. | |
64 | */ | |
65 | ||
325cc939 | 66 | extern struct irc_radixtree *irc_radixtree_create(const char *name, void (*canonize_cb)(char *key)); |
8e6ba6f9 AC |
67 | |
68 | /* | |
69 | * irc_radixtree_shutdown() deallocates all heaps used in patricia trees. This is | |
70 | * useful on embedded devices with little memory, and/or when you know you won't need | |
71 | * any more patricia trees. | |
72 | */ | |
73 | extern void irc_radixtree_shutdown(void); | |
74 | ||
75 | /* | |
76 | * irc_radixtree_destroy() destroys all entries in a dtree, and also optionally calls | |
77 | * a defined callback function to destroy any data attached to it. | |
78 | */ | |
79 | extern void irc_radixtree_destroy(struct irc_radixtree *dtree, void (*destroy_cb)(const char *key, void *data, void *privdata), void *privdata); | |
80 | ||
81 | /* | |
82 | * irc_radixtree_foreach() iterates all entries in a dtree, and also optionally calls | |
83 | * a defined callback function to use any data attached to it. | |
84 | * | |
85 | * To shortcircuit iteration, return non-zero from the callback function. | |
86 | */ | |
87 | extern void irc_radixtree_foreach(struct irc_radixtree *dtree, int (*foreach_cb)(const char *key, void *data, void *privdata), void *privdata); | |
88 | ||
89 | /* | |
90 | * irc_radixtree_search() iterates all entries in a dtree, and also optionally calls | |
91 | * a defined callback function to use any data attached to it. | |
92 | * | |
93 | * When the object is found, a non-NULL is returned from the callback, which results | |
94 | * in that object being returned to the user. | |
95 | */ | |
96 | extern void *irc_radixtree_search(struct irc_radixtree *dtree, void *(*foreach_cb)(const char *key, void *data, void *privdata), void *privdata); | |
97 | ||
98 | /* | |
99 | * irc_radixtree_foreach_start() begins an iteration over all items | |
100 | * keeping state in the given struct. If there is only one iteration | |
101 | * in progress at a time, it is permitted to remove the current element | |
102 | * of the iteration (but not any other element). | |
103 | */ | |
104 | extern void irc_radixtree_foreach_start(struct irc_radixtree *dtree, struct irc_radixtree_iteration_state *state); | |
105 | ||
0d9a72de AC |
106 | /* |
107 | * irc_radixtree_foreach_start_from() begins an iteration over all items, | |
108 | * starting with the item specified by `key`. If there is only one iteration | |
109 | * in progress at a time, it is permitted to remove the current element | |
110 | * of the iteration (but not any other element). | |
111 | * Use NULL as a key to have it start at the beginning. | |
112 | */ | |
113 | extern void irc_radixtree_foreach_start_from(struct irc_radixtree *dtree, struct irc_radixtree_iteration_state *state, const char *key); | |
114 | ||
8e6ba6f9 AC |
115 | /* |
116 | * irc_radixtree_foreach_cur() returns the current element of the iteration, | |
117 | * or NULL if there are no more elements. | |
118 | */ | |
119 | extern void *irc_radixtree_foreach_cur(struct irc_radixtree *dtree, struct irc_radixtree_iteration_state *state); | |
120 | ||
121 | /* | |
122 | * irc_radixtree_foreach_next() moves to the next element. | |
123 | */ | |
124 | extern void irc_radixtree_foreach_next(struct irc_radixtree *dtree, struct irc_radixtree_iteration_state *state); | |
125 | ||
126 | /* | |
127 | * irc_radixtree_add() adds a key->value entry to the patricia tree. | |
128 | */ | |
129 | extern int irc_radixtree_add(struct irc_radixtree *dtree, const char *key, void *data); | |
130 | ||
131 | /* | |
132 | * irc_radixtree_find() returns data from a dtree for key 'key'. | |
133 | */ | |
134 | extern void *irc_radixtree_retrieve(struct irc_radixtree *dtree, const char *key); | |
135 | ||
136 | /* | |
137 | * irc_radixtree_delete() deletes a key->value entry from the patricia tree. | |
138 | */ | |
139 | extern void *irc_radixtree_delete(struct irc_radixtree *dtree, const char *key); | |
140 | ||
141 | /* Low-level functions */ | |
142 | struct irc_radixtree_leaf *irc_radixtree_elem_add(struct irc_radixtree *dtree, const char *key, void *data); | |
704697b6 | 143 | struct irc_radixtree_leaf *irc_radixtree_elem_find(struct irc_radixtree *dtree, const char *key, int fuzzy); |
8e6ba6f9 AC |
144 | void irc_radixtree_elem_delete(struct irc_radixtree *dtree, struct irc_radixtree_leaf *elem); |
145 | const char *irc_radixtree_elem_get_key(struct irc_radixtree_leaf *elem); | |
146 | void irc_radixtree_elem_set_data(struct irc_radixtree_leaf *elem, void *data); | |
147 | void *irc_radixtree_elem_get_data(struct irc_radixtree_leaf *elem); | |
148 | ||
149 | unsigned int irc_radixtree_size(struct irc_radixtree *dict); | |
150 | void irc_radixtree_stats(struct irc_radixtree *dict, void (*cb)(const char *line, void *privdata), void *privdata); | |
325cc939 | 151 | void irc_radixtree_stats_walk(void (*cb)(const char *line, void *privdata), void *privdata); |
8e6ba6f9 | 152 | |
db891ac3 AC |
153 | void irc_radixtree_strcasecanon(char *key); |
154 | void irc_radixtree_irccasecanon(char *key); | |
155 | ||
8e6ba6f9 | 156 | #endif |