]>
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 | ||
28 | struct Dictionary; /* defined in src/dictionary.c */ | |
29 | ||
30 | typedef int (*DCF)(/* const void *a, const void *b */); | |
31 | ||
32 | struct DictionaryElement | |
33 | { | |
34 | struct DictionaryElement *left, *right, *prev, *next; | |
35 | void *data; | |
36 | const void *key; | |
37 | int position; | |
38 | }; | |
39 | ||
40 | struct DictionaryIter | |
41 | { | |
42 | struct DictionaryElement *cur, *next; | |
43 | }; | |
44 | ||
45 | /* | |
46 | * this is a convenience macro for inlining iteration of dictionaries. | |
47 | */ | |
48 | #define 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))) | |
49 | ||
50 | /* | |
51 | * rb_dictionary_create_named() creates a new dictionary tree which has a name. | |
52 | * name is the name, compare_cb is the comparator. | |
53 | */ | |
54 | extern struct Dictionary *rb_dictionary_create(const char *name, DCF compare_cb); | |
55 | ||
56 | /* | |
57 | * rb_dictionary_set_comparator_func() resets the comparator used for lookups and | |
58 | * insertions in the DTree structure. | |
59 | */ | |
60 | extern void rb_dictionary_set_comparator_func(struct Dictionary *dict, | |
61 | DCF compare_cb); | |
62 | ||
63 | /* | |
64 | * rb_dictionary_get_comparator_func() returns the comparator used for lookups and | |
65 | * insertions in the DTree structure. | |
66 | */ | |
67 | extern DCF rb_dictionary_get_comparator_func(struct Dictionary *dict); | |
68 | ||
69 | /* | |
70 | * rb_dictionary_get_linear_index() returns the linear index of an object in the | |
71 | * DTree structure. | |
72 | */ | |
73 | extern int rb_dictionary_get_linear_index(struct Dictionary *dict, const void *key); | |
74 | ||
75 | /* | |
76 | * rb_dictionary_destroy() destroys all entries in a dtree, and also optionally calls | |
77 | * a defined callback function to destroy any data attached to it. | |
78 | */ | |
79 | extern void rb_dictionary_destroy(struct Dictionary *dtree, | |
80 | void (*destroy_cb)(struct DictionaryElement *delem, void *privdata), | |
81 | void *privdata); | |
82 | ||
83 | /* | |
84 | * rb_dictionary_foreach() iterates all entries in a dtree, and also optionally calls | |
85 | * a defined callback function to use any data attached to it. | |
86 | * | |
87 | * To shortcircuit iteration, return non-zero from the callback function. | |
88 | */ | |
89 | extern void rb_dictionary_foreach(struct Dictionary *dtree, | |
90 | int (*foreach_cb)(struct DictionaryElement *delem, void *privdata), | |
91 | void *privdata); | |
92 | ||
93 | /* | |
94 | * rb_dictionary_search() iterates all entries in a dtree, and also optionally calls | |
95 | * a defined callback function to use any data attached to it. | |
96 | * | |
97 | * When the object is found, a non-NULL is returned from the callback, which results | |
98 | * in that object being returned to the user. | |
99 | */ | |
100 | extern void *rb_dictionary_search(struct Dictionary *dtree, | |
101 | void *(*foreach_cb)(struct DictionaryElement *delem, void *privdata), | |
102 | void *privdata); | |
103 | ||
104 | /* | |
105 | * rb_dictionary_foreach_start() begins an iteration over all items | |
106 | * keeping state in the given struct. If there is only one iteration | |
107 | * in progress at a time, it is permitted to remove the current element | |
108 | * of the iteration (but not any other element). | |
109 | */ | |
110 | extern void rb_dictionary_foreach_start(struct Dictionary *dtree, | |
111 | struct DictionaryIter *state); | |
112 | ||
113 | /* | |
114 | * rb_dictionary_foreach_cur() returns the current element of the iteration, | |
115 | * or NULL if there are no more elements. | |
116 | */ | |
117 | extern void *rb_dictionary_foreach_cur(struct Dictionary *dtree, | |
118 | struct DictionaryIter *state); | |
119 | ||
120 | /* | |
121 | * rb_dictionary_foreach_next() moves to the next element. | |
122 | */ | |
123 | extern void rb_dictionary_foreach_next(struct Dictionary *dtree, | |
124 | struct DictionaryIter *state); | |
125 | ||
126 | /* | |
127 | * rb_dictionary_add() adds a key->value entry to the dictionary tree. | |
128 | */ | |
129 | extern struct DictionaryElement *rb_dictionary_add(struct Dictionary *dtree, const void *key, void *data); | |
130 | ||
131 | /* | |
132 | * rb_dictionary_find() returns a struct DictionaryElement container from a dtree for key 'key'. | |
133 | */ | |
134 | extern struct DictionaryElement *rb_dictionary_find(struct Dictionary *dtree, const void *key); | |
135 | ||
136 | /* | |
137 | * rb_dictionary_find() returns data from a dtree for key 'key'. | |
138 | */ | |
139 | extern void *rb_dictionary_retrieve(struct Dictionary *dtree, const void *key); | |
140 | ||
141 | /* | |
142 | * rb_dictionary_delete() deletes a key->value entry from the dictionary tree. | |
143 | */ | |
144 | extern void *rb_dictionary_delete(struct Dictionary *dtree, const void *key); | |
145 | ||
146 | /* | |
147 | * rb_dictionary_size() returns the number of elements in a dictionary tree. | |
148 | */ | |
149 | extern unsigned int rb_dictionary_size(struct Dictionary *dtree); | |
150 | ||
151 | void rb_dictionary_stats(struct Dictionary *dict, void (*cb)(const char *line, void *privdata), void *privdata); | |
152 | void rb_dictionary_stats_walk(void (*cb)(const char *line, void *privdata), void *privdata); | |
153 | ||
154 | #define RB_POINTER_TO_INT(x) ((int32_t) (long) (x)) | |
155 | #define RB_INT_TO_POINTER(x) ((void *) (long) (int32_t) (x)) | |
156 | ||
157 | #define RB_POINTER_TO_UINT(x) ((uint32_t) (unsigned long) (x)) | |
158 | #define RB_UINT_TO_POINTER(x) ((void *) (unsigned long) (uint32_t) (x)) | |
159 | ||
160 | static inline int rb_int32cmp(const void *a, const void *b) | |
161 | { | |
162 | return RB_POINTER_TO_INT(b) - RB_POINTER_TO_INT(a); | |
163 | } | |
164 | ||
165 | static inline int rb_uint32cmp(const void *a, const void *b) | |
166 | { | |
167 | return RB_POINTER_TO_UINT(b) - RB_POINTER_TO_UINT(a); | |
168 | } | |
169 | ||
170 | #endif |