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)))
59 * irc_radixtree_create() creates a new patricia tree of the defined resolution.
60 * compare_cb is the canonizing function.
63 extern struct irc_radixtree
*irc_radixtree_create(const char *name
, void (*canonize_cb
)(char *key
));
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.
70 extern void irc_radixtree_shutdown(void);
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.
76 extern void irc_radixtree_destroy(struct irc_radixtree
*dtree
, void (*destroy_cb
)(const char *key
, void *data
, void *privdata
), void *privdata
);
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.
82 * To shortcircuit iteration, return non-zero from the callback function.
84 extern void irc_radixtree_foreach(struct irc_radixtree
*dtree
, int (*foreach_cb
)(const char *key
, void *data
, void *privdata
), void *privdata
);
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.
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.
93 extern void *irc_radixtree_search(struct irc_radixtree
*dtree
, void *(*foreach_cb
)(const char *key
, void *data
, void *privdata
), void *privdata
);
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).
101 extern void irc_radixtree_foreach_start(struct irc_radixtree
*dtree
, struct irc_radixtree_iteration_state
*state
);
104 * irc_radixtree_foreach_cur() returns the current element of the iteration,
105 * or NULL if there are no more elements.
107 extern void *irc_radixtree_foreach_cur(struct irc_radixtree
*dtree
, struct irc_radixtree_iteration_state
*state
);
110 * irc_radixtree_foreach_next() moves to the next element.
112 extern void irc_radixtree_foreach_next(struct irc_radixtree
*dtree
, struct irc_radixtree_iteration_state
*state
);
115 * irc_radixtree_add() adds a key->value entry to the patricia tree.
117 extern int irc_radixtree_add(struct irc_radixtree
*dtree
, const char *key
, void *data
);
120 * irc_radixtree_find() returns data from a dtree for key 'key'.
122 extern void *irc_radixtree_retrieve(struct irc_radixtree
*dtree
, const char *key
);
125 * irc_radixtree_delete() deletes a key->value entry from the patricia tree.
127 extern void *irc_radixtree_delete(struct irc_radixtree
*dtree
, const char *key
);
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
);
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
);
139 void irc_radixtree_stats_walk(void (*cb
)(const char *line
, void *privdata
), void *privdata
);
141 void irc_radixtree_strcasecanon(char *key
);
142 void irc_radixtree_irccasecanon(char *key
);