]>
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 | ||
58 | /* | |
59 | * irc_radixtree_create() creates a new patricia tree of the defined resolution. | |
60 | * compare_cb is the canonizing function. | |
61 | */ | |
62 | ||
325cc939 | 63 | extern struct irc_radixtree *irc_radixtree_create(const char *name, void (*canonize_cb)(char *key)); |
8e6ba6f9 AC |
64 | |
65 | /* | |
66 | * irc_radixtree_shutdown() deallocates all heaps used in patricia trees. This is | |
67 | * useful on embedded devices with little memory, and/or when you know you won't need | |
68 | * any more patricia trees. | |
69 | */ | |
70 | extern void irc_radixtree_shutdown(void); | |
71 | ||
72 | /* | |
73 | * irc_radixtree_destroy() destroys all entries in a dtree, and also optionally calls | |
74 | * a defined callback function to destroy any data attached to it. | |
75 | */ | |
76 | extern void irc_radixtree_destroy(struct irc_radixtree *dtree, void (*destroy_cb)(const char *key, void *data, void *privdata), void *privdata); | |
77 | ||
78 | /* | |
79 | * irc_radixtree_foreach() iterates all entries in a dtree, and also optionally calls | |
80 | * a defined callback function to use any data attached to it. | |
81 | * | |
82 | * To shortcircuit iteration, return non-zero from the callback function. | |
83 | */ | |
84 | extern void irc_radixtree_foreach(struct irc_radixtree *dtree, int (*foreach_cb)(const char *key, void *data, void *privdata), void *privdata); | |
85 | ||
86 | /* | |
87 | * irc_radixtree_search() iterates all entries in a dtree, and also optionally calls | |
88 | * a defined callback function to use any data attached to it. | |
89 | * | |
90 | * When the object is found, a non-NULL is returned from the callback, which results | |
91 | * in that object being returned to the user. | |
92 | */ | |
93 | extern void *irc_radixtree_search(struct irc_radixtree *dtree, void *(*foreach_cb)(const char *key, void *data, void *privdata), void *privdata); | |
94 | ||
95 | /* | |
96 | * irc_radixtree_foreach_start() begins an iteration over all items | |
97 | * keeping state in the given struct. If there is only one iteration | |
98 | * in progress at a time, it is permitted to remove the current element | |
99 | * of the iteration (but not any other element). | |
100 | */ | |
101 | extern void irc_radixtree_foreach_start(struct irc_radixtree *dtree, struct irc_radixtree_iteration_state *state); | |
102 | ||
103 | /* | |
104 | * irc_radixtree_foreach_cur() returns the current element of the iteration, | |
105 | * or NULL if there are no more elements. | |
106 | */ | |
107 | extern void *irc_radixtree_foreach_cur(struct irc_radixtree *dtree, struct irc_radixtree_iteration_state *state); | |
108 | ||
109 | /* | |
110 | * irc_radixtree_foreach_next() moves to the next element. | |
111 | */ | |
112 | extern void irc_radixtree_foreach_next(struct irc_radixtree *dtree, struct irc_radixtree_iteration_state *state); | |
113 | ||
114 | /* | |
115 | * irc_radixtree_add() adds a key->value entry to the patricia tree. | |
116 | */ | |
117 | extern int irc_radixtree_add(struct irc_radixtree *dtree, const char *key, void *data); | |
118 | ||
119 | /* | |
120 | * irc_radixtree_find() returns data from a dtree for key 'key'. | |
121 | */ | |
122 | extern void *irc_radixtree_retrieve(struct irc_radixtree *dtree, const char *key); | |
123 | ||
124 | /* | |
125 | * irc_radixtree_delete() deletes a key->value entry from the patricia tree. | |
126 | */ | |
127 | extern void *irc_radixtree_delete(struct irc_radixtree *dtree, const char *key); | |
128 | ||
129 | /* Low-level functions */ | |
130 | struct irc_radixtree_leaf *irc_radixtree_elem_add(struct irc_radixtree *dtree, const char *key, void *data); | |
131 | struct irc_radixtree_leaf *irc_radixtree_elem_find(struct irc_radixtree *dtree, const char *key); | |
132 | void irc_radixtree_elem_delete(struct irc_radixtree *dtree, struct irc_radixtree_leaf *elem); | |
133 | const char *irc_radixtree_elem_get_key(struct irc_radixtree_leaf *elem); | |
134 | void irc_radixtree_elem_set_data(struct irc_radixtree_leaf *elem, void *data); | |
135 | void *irc_radixtree_elem_get_data(struct irc_radixtree_leaf *elem); | |
136 | ||
137 | unsigned int irc_radixtree_size(struct irc_radixtree *dict); | |
138 | void irc_radixtree_stats(struct irc_radixtree *dict, void (*cb)(const char *line, void *privdata), void *privdata); | |
325cc939 | 139 | void irc_radixtree_stats_walk(void (*cb)(const char *line, void *privdata), void *privdata); |
8e6ba6f9 AC |
140 | |
141 | #endif |