2 * charybdis: an advanced ircd.
3 * irc_radixtree.h: Dictionary-based storage.
5 * Copyright (c) 2007-2016 William Pitcock <nenolod -at- dereferenced.org>
6 * Copyright (c) 2007-2016 Jilles Tjoelker <jilles -at- stack.nl>
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions are
12 * 1. Redistributions of source code must retain the above copyright notice,
13 * this list of conditions and the following disclaimer.
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.
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.
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.
35 #ifndef __irc_radixtree_H__
36 #define __irc_radixtree_H__
38 struct irc_radixtree
;/* defined in ircd/irc_radixtree.c */
40 struct irc_radixtree_leaf
; /* defined in ircd/irc_radixtree.c */
43 * struct irc_radixtree_iteration_state, private.
45 struct irc_radixtree_iteration_state
47 struct irc_radixtree_leaf
*cur
, *next
;
53 * this is a convenience macro for inlining iteration of dictionaries.
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)))
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)))
62 * irc_radixtree_create() creates a new patricia tree of the defined resolution.
63 * compare_cb is the canonizing function.
66 extern struct irc_radixtree
*irc_radixtree_create(const char *name
, void (*canonize_cb
)(char *key
));
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.
73 extern void irc_radixtree_shutdown(void);
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.
79 extern void irc_radixtree_destroy(struct irc_radixtree
*dtree
, void (*destroy_cb
)(const char *key
, void *data
, void *privdata
), void *privdata
);
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.
85 * To shortcircuit iteration, return non-zero from the callback function.
87 extern void irc_radixtree_foreach(struct irc_radixtree
*dtree
, int (*foreach_cb
)(const char *key
, void *data
, void *privdata
), void *privdata
);
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.
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.
96 extern void *irc_radixtree_search(struct irc_radixtree
*dtree
, void *(*foreach_cb
)(const char *key
, void *data
, void *privdata
), void *privdata
);
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).
104 extern void irc_radixtree_foreach_start(struct irc_radixtree
*dtree
, struct irc_radixtree_iteration_state
*state
);
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.
113 extern void irc_radixtree_foreach_start_from(struct irc_radixtree
*dtree
, struct irc_radixtree_iteration_state
*state
, const char *key
);
116 * irc_radixtree_foreach_cur() returns the current element of the iteration,
117 * or NULL if there are no more elements.
119 extern void *irc_radixtree_foreach_cur(struct irc_radixtree
*dtree
, struct irc_radixtree_iteration_state
*state
);
122 * irc_radixtree_foreach_next() moves to the next element.
124 extern void irc_radixtree_foreach_next(struct irc_radixtree
*dtree
, struct irc_radixtree_iteration_state
*state
);
127 * irc_radixtree_add() adds a key->value entry to the patricia tree.
129 extern int irc_radixtree_add(struct irc_radixtree
*dtree
, const char *key
, void *data
);
132 * irc_radixtree_find() returns data from a dtree for key 'key'.
134 extern void *irc_radixtree_retrieve(struct irc_radixtree
*dtree
, const char *key
);
137 * irc_radixtree_delete() deletes a key->value entry from the patricia tree.
139 extern void *irc_radixtree_delete(struct irc_radixtree
*dtree
, const char *key
);
141 /* Low-level functions */
142 struct irc_radixtree_leaf
*irc_radixtree_elem_add(struct irc_radixtree
*dtree
, const char *key
, void *data
);
143 struct irc_radixtree_leaf
*irc_radixtree_elem_find(struct irc_radixtree
*dtree
, const char *key
, int fuzzy
);
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
);
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
);
151 void irc_radixtree_stats_walk(void (*cb
)(const char *line
, void *privdata
), void *privdata
);
153 void irc_radixtree_strcasecanon(char *key
);
154 void irc_radixtree_irccasecanon(char *key
);