2 * charybdis: an advanced ircd.
3 * rb_dictionary.h: Dictionary-based storage.
5 * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk>
6 * Copyright (c) 2007 Jilles Tjoelker <jilles -at- stack.nl>
8 * Permission to use, copy, modify, and/or distribute this software for any
9 * purpose with or without fee is hereby granted, provided that the above
10 * copyright notice and this permission notice is present in all copies.
12 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
13 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
14 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
15 * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT,
16 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
17 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
18 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
19 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
20 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
21 * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
22 * POSSIBILITY OF SUCH DAMAGE.
25 #ifndef __RB_DICTIONARY_H__
26 #define __RB_DICTIONARY_H__
28 #include "librb-config.h"
30 typedef struct rb_dictionary rb_dictionary
;
31 typedef struct rb_dictionary_element rb_dictionary_element
;
32 typedef struct rb_dictionary_iter rb_dictionary_iter
;
36 typedef int (*DCF
)(/* const void *a, const void *b */);
38 struct rb_dictionary_element
40 rb_dictionary_element
*left
, *right
, *prev
, *next
;
46 struct rb_dictionary_iter
48 rb_dictionary_element
*cur
, *next
;
52 * this is a convenience macro for inlining iteration of dictionaries.
54 #define RB_DICTIONARY_FOREACH(element, state, dict) for (rb_dictionary_foreach_start((dict), (state)); (element = rb_dictionary_foreach_cur((dict), (state))); rb_dictionary_foreach_next((dict), (state)))
57 * rb_dictionary_create_named() creates a new dictionary tree which has a name.
58 * name is the name, compare_cb is the comparator.
60 extern rb_dictionary
*rb_dictionary_create(const char *name
, DCF compare_cb
);
63 * rb_dictionary_set_comparator_func() resets the comparator used for lookups and
64 * insertions in the DTree structure.
66 extern void rb_dictionary_set_comparator_func(rb_dictionary
*dict
,
70 * rb_dictionary_get_comparator_func() returns the comparator used for lookups and
71 * insertions in the DTree structure.
73 extern DCF
rb_dictionary_get_comparator_func(rb_dictionary
*dict
);
76 * rb_dictionary_get_linear_index() returns the linear index of an object in the
79 extern int rb_dictionary_get_linear_index(rb_dictionary
*dict
, const void *key
);
82 * rb_dictionary_destroy() destroys all entries in a dtree, and also optionally calls
83 * a defined callback function to destroy any data attached to it.
85 extern void rb_dictionary_destroy(rb_dictionary
*dtree
,
86 void (*destroy_cb
)(rb_dictionary_element
*delem
, void *privdata
),
90 * rb_dictionary_foreach() iterates all entries in a dtree, and also optionally calls
91 * a defined callback function to use any data attached to it.
93 * To shortcircuit iteration, return non-zero from the callback function.
95 extern void rb_dictionary_foreach(rb_dictionary
*dtree
,
96 int (*foreach_cb
)(rb_dictionary_element
*delem
, void *privdata
),
100 * rb_dictionary_search() iterates all entries in a dtree, and also optionally calls
101 * a defined callback function to use any data attached to it.
103 * When the object is found, a non-NULL is returned from the callback, which results
104 * in that object being returned to the user.
106 extern void *rb_dictionary_search(rb_dictionary
*dtree
,
107 void *(*foreach_cb
)(rb_dictionary_element
*delem
, void *privdata
),
111 * rb_dictionary_foreach_start() begins an iteration over all items
112 * keeping state in the given struct. 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).
116 extern void rb_dictionary_foreach_start(rb_dictionary
*dtree
,
117 rb_dictionary_iter
*state
);
120 * rb_dictionary_foreach_cur() returns the current element of the iteration,
121 * or NULL if there are no more elements.
123 extern void *rb_dictionary_foreach_cur(rb_dictionary
*dtree
,
124 rb_dictionary_iter
*state
);
127 * rb_dictionary_foreach_next() moves to the next element.
129 extern void rb_dictionary_foreach_next(rb_dictionary
*dtree
,
130 rb_dictionary_iter
*state
);
133 * rb_dictionary_add() adds a key->value entry to the dictionary tree.
135 extern rb_dictionary_element
*rb_dictionary_add(rb_dictionary
*dtree
, const void *key
, void *data
);
138 * rb_dictionary_find() returns a rb_dictionary_element container from a dtree for key 'key'.
140 extern rb_dictionary_element
*rb_dictionary_find(rb_dictionary
*dtree
, const void *key
);
143 * rb_dictionary_find() returns data from a dtree for key 'key'.
145 extern void *rb_dictionary_retrieve(rb_dictionary
*dtree
, const void *key
);
148 * rb_dictionary_delete() deletes a key->value entry from the dictionary tree.
150 extern void *rb_dictionary_delete(rb_dictionary
*dtree
, const void *key
);
153 * rb_dictionary_size() returns the number of elements in a dictionary tree.
155 extern unsigned int rb_dictionary_size(rb_dictionary
*dtree
);
157 void rb_dictionary_stats(rb_dictionary
*dict
, void (*cb
)(const char *line
, void *privdata
), void *privdata
);
158 void rb_dictionary_stats_walk(void (*cb
)(const char *line
, void *privdata
), void *privdata
);
162 #define RB_POINTER_TO_INT(x) ((int32_t) (long) (x))
163 #define RB_INT_TO_POINTER(x) ((void *) (long) (int32_t) (x))
165 #define RB_POINTER_TO_UINT(x) ((uint32_t) (unsigned long) (x))
166 #define RB_UINT_TO_POINTER(x) ((void *) (unsigned long) (uint32_t) (x))
170 #define RB_POINTER_TO_INT(x) ((int32_t) (unsigned long long) (x))
171 #define RB_INT_TO_POINTER(x) ((void *) (unsigned long long) (int32_t) (x))
173 #define RB_POINTER_TO_UINT(x) ((uint32_t) (unsigned long long) (x))
174 #define RB_UINT_TO_POINTER(x) ((void *) (unsigned long long) (uint32_t) (x))
178 static inline int rb_int32cmp(const void *a
, const void *b
)
180 return RB_POINTER_TO_INT(b
) - RB_POINTER_TO_INT(a
);
183 static inline int rb_uint32cmp(const void *a
, const void *b
)
185 return RB_POINTER_TO_UINT(b
) - RB_POINTER_TO_UINT(a
);