]>
Commit | Line | Data |
---|---|---|
a4bf26dd EM |
1 | /* |
2 | * charybdis: an advanced ircd. | |
3 | * rb_dictionary.h: Dictionary-based storage. | |
4 | * | |
5 | * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> | |
6 | * Copyright (c) 2007 Jilles Tjoelker <jilles -at- stack.nl> | |
7 | * | |
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. | |
11 | * | |
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. | |
23 | */ | |
24 | ||
25 | #ifndef __RB_DICTIONARY_H__ | |
26 | #define __RB_DICTIONARY_H__ | |
27 | ||
2a9257c6 EM |
28 | #include "librb-config.h" |
29 | ||
4177311e EM |
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; | |
33 | ||
34 | struct rb_dictionary; | |
a4bf26dd EM |
35 | |
36 | typedef int (*DCF)(/* const void *a, const void *b */); | |
37 | ||
4177311e | 38 | struct rb_dictionary_element |
a4bf26dd | 39 | { |
4177311e | 40 | rb_dictionary_element *left, *right, *prev, *next; |
a4bf26dd EM |
41 | void *data; |
42 | const void *key; | |
43 | int position; | |
44 | }; | |
45 | ||
4177311e | 46 | struct rb_dictionary_iter |
a4bf26dd | 47 | { |
4177311e | 48 | rb_dictionary_element *cur, *next; |
a4bf26dd EM |
49 | }; |
50 | ||
51 | /* | |
52 | * this is a convenience macro for inlining iteration of dictionaries. | |
53 | */ | |
56f84ded | 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))) |
a4bf26dd EM |
55 | |
56 | /* | |
57 | * rb_dictionary_create_named() creates a new dictionary tree which has a name. | |
58 | * name is the name, compare_cb is the comparator. | |
59 | */ | |
4177311e | 60 | extern rb_dictionary *rb_dictionary_create(const char *name, DCF compare_cb); |
a4bf26dd EM |
61 | |
62 | /* | |
63 | * rb_dictionary_set_comparator_func() resets the comparator used for lookups and | |
64 | * insertions in the DTree structure. | |
65 | */ | |
4177311e | 66 | extern void rb_dictionary_set_comparator_func(rb_dictionary *dict, |
a4bf26dd EM |
67 | DCF compare_cb); |
68 | ||
69 | /* | |
70 | * rb_dictionary_get_comparator_func() returns the comparator used for lookups and | |
71 | * insertions in the DTree structure. | |
72 | */ | |
4177311e | 73 | extern DCF rb_dictionary_get_comparator_func(rb_dictionary *dict); |
a4bf26dd EM |
74 | |
75 | /* | |
76 | * rb_dictionary_get_linear_index() returns the linear index of an object in the | |
77 | * DTree structure. | |
78 | */ | |
4177311e | 79 | extern int rb_dictionary_get_linear_index(rb_dictionary *dict, const void *key); |
a4bf26dd EM |
80 | |
81 | /* | |
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. | |
84 | */ | |
4177311e EM |
85 | extern void rb_dictionary_destroy(rb_dictionary *dtree, |
86 | void (*destroy_cb)(rb_dictionary_element *delem, void *privdata), | |
a4bf26dd EM |
87 | void *privdata); |
88 | ||
89 | /* | |
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. | |
92 | * | |
93 | * To shortcircuit iteration, return non-zero from the callback function. | |
94 | */ | |
4177311e EM |
95 | extern void rb_dictionary_foreach(rb_dictionary *dtree, |
96 | int (*foreach_cb)(rb_dictionary_element *delem, void *privdata), | |
a4bf26dd EM |
97 | void *privdata); |
98 | ||
99 | /* | |
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. | |
102 | * | |
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. | |
105 | */ | |
4177311e EM |
106 | extern void *rb_dictionary_search(rb_dictionary *dtree, |
107 | void *(*foreach_cb)(rb_dictionary_element *delem, void *privdata), | |
a4bf26dd EM |
108 | void *privdata); |
109 | ||
110 | /* | |
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). | |
115 | */ | |
4177311e EM |
116 | extern void rb_dictionary_foreach_start(rb_dictionary *dtree, |
117 | rb_dictionary_iter *state); | |
a4bf26dd EM |
118 | |
119 | /* | |
120 | * rb_dictionary_foreach_cur() returns the current element of the iteration, | |
121 | * or NULL if there are no more elements. | |
122 | */ | |
4177311e EM |
123 | extern void *rb_dictionary_foreach_cur(rb_dictionary *dtree, |
124 | rb_dictionary_iter *state); | |
a4bf26dd EM |
125 | |
126 | /* | |
127 | * rb_dictionary_foreach_next() moves to the next element. | |
128 | */ | |
4177311e EM |
129 | extern void rb_dictionary_foreach_next(rb_dictionary *dtree, |
130 | rb_dictionary_iter *state); | |
a4bf26dd EM |
131 | |
132 | /* | |
133 | * rb_dictionary_add() adds a key->value entry to the dictionary tree. | |
134 | */ | |
4177311e | 135 | extern rb_dictionary_element *rb_dictionary_add(rb_dictionary *dtree, const void *key, void *data); |
a4bf26dd EM |
136 | |
137 | /* | |
4177311e | 138 | * rb_dictionary_find() returns a rb_dictionary_element container from a dtree for key 'key'. |
a4bf26dd | 139 | */ |
4177311e | 140 | extern rb_dictionary_element *rb_dictionary_find(rb_dictionary *dtree, const void *key); |
a4bf26dd EM |
141 | |
142 | /* | |
143 | * rb_dictionary_find() returns data from a dtree for key 'key'. | |
144 | */ | |
4177311e | 145 | extern void *rb_dictionary_retrieve(rb_dictionary *dtree, const void *key); |
a4bf26dd EM |
146 | |
147 | /* | |
148 | * rb_dictionary_delete() deletes a key->value entry from the dictionary tree. | |
149 | */ | |
4177311e | 150 | extern void *rb_dictionary_delete(rb_dictionary *dtree, const void *key); |
a4bf26dd EM |
151 | |
152 | /* | |
153 | * rb_dictionary_size() returns the number of elements in a dictionary tree. | |
154 | */ | |
4177311e | 155 | extern unsigned int rb_dictionary_size(rb_dictionary *dtree); |
a4bf26dd | 156 | |
4177311e | 157 | void rb_dictionary_stats(rb_dictionary *dict, void (*cb)(const char *line, void *privdata), void *privdata); |
a4bf26dd EM |
158 | void rb_dictionary_stats_walk(void (*cb)(const char *line, void *privdata), void *privdata); |
159 | ||
e0dc28c5 AC |
160 | #ifndef _WIN32 |
161 | ||
a4bf26dd EM |
162 | #define RB_POINTER_TO_INT(x) ((int32_t) (long) (x)) |
163 | #define RB_INT_TO_POINTER(x) ((void *) (long) (int32_t) (x)) | |
164 | ||
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)) | |
167 | ||
e0dc28c5 AC |
168 | #else |
169 | ||
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)) | |
172 | ||
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)) | |
175 | ||
e0dc28c5 AC |
176 | #endif |
177 | ||
a4bf26dd EM |
178 | static inline int rb_int32cmp(const void *a, const void *b) |
179 | { | |
180 | return RB_POINTER_TO_INT(b) - RB_POINTER_TO_INT(a); | |
181 | } | |
182 | ||
183 | static inline int rb_uint32cmp(const void *a, const void *b) | |
184 | { | |
185 | return RB_POINTER_TO_UINT(b) - RB_POINTER_TO_UINT(a); | |
186 | } | |
187 | ||
188 | #endif |