1 |
/* |
2 |
* dictionary.C: Dictionary-backed trees. |
3 |
* Rights to this code are documented in doc/pod/license.pod. |
4 |
* |
5 |
* Copyright © 2005-2007 Atheme Project (http://www.atheme.org) |
6 |
*/ |
7 |
|
8 |
static char const rcsid[] = "$Id: dictionary.C,v 1.4 2007-08-28 17:08:12 pippijn Exp $"; |
9 |
|
10 |
#include "atheme.h" |
11 |
|
12 |
list_t dictionarylist; |
13 |
|
14 |
struct dictionary_tree_t |
15 |
{ |
16 |
object_t parent; |
17 |
|
18 |
int resolution; |
19 |
list_t *hashv; /* dynamically allocated by dictionary_create() */ |
20 |
int (*compare_cb) (char const * const a, char const * const b); |
21 |
node_t node; |
22 |
}; |
23 |
|
24 |
/* |
25 |
* This generates a hash value, based on chongo's hash algo, |
26 |
* located at http://www.isthe.com/chongo/tech/comp/fnv/ |
27 |
* |
28 |
* The difference between FNV and Atheme's hash algorithm is |
29 |
* that FNV uses a random key for toasting, we just use |
30 |
* 16 instead. |
31 |
*/ |
32 |
static unsigned int |
33 |
shash (const unsigned char *p) |
34 |
{ |
35 |
unsigned int hval = HASHINIT; |
36 |
|
37 |
if (!p) |
38 |
return (0); |
39 |
for (; *p != '\0'; ++p) |
40 |
{ |
41 |
hval += (hval << 1) + (hval << 4) + (hval << 7) + (hval << 8) + (hval << 24); |
42 |
hval ^= (ToLower (*p) ^ 16); |
43 |
} |
44 |
|
45 |
return ((hval >> HASHBITS) ^ (hval & ((1 << HASHBITS) - 1)) % HASHSIZE); |
46 |
} |
47 |
|
48 |
/* |
49 |
* dictionary_create(char const * const name, int resolution, |
50 |
* int (*compare_cb)(char const * const a, char const * const b) |
51 |
* |
52 |
* DTree object factory. |
53 |
* |
54 |
* Inputs: |
55 |
* - name of dictionary tree |
56 |
* - resolution of dictionary tree |
57 |
* - function to use for comparing two entries in the dtree |
58 |
* |
59 |
* Outputs: |
60 |
* - on success, a new DTree object. |
61 |
* |
62 |
* Side Effects: |
63 |
* - if services runs out of memory and cannot allocate the object, |
64 |
* the program will abort. |
65 |
*/ |
66 |
dictionary_tree_t * |
67 |
dictionary_create (char const * const name, int resolution, int (*compare_cb) (char const * const a, char const * const b)) |
68 |
{ |
69 |
dictionary_tree_t *dtree = static_cast<dictionary_tree_t *> (malloc (sizeof (dictionary_tree_t))); |
70 |
|
71 |
object_init (&dtree->parent, name, NULL); |
72 |
dtree->resolution = resolution; |
73 |
dtree->hashv = static_cast<list_t *> (malloc (sizeof (list_t) * resolution)); |
74 |
dtree->compare_cb = compare_cb; |
75 |
memset (dtree->hashv, '\0', sizeof (list_t) * resolution); |
76 |
node_add (dtree, &dtree->node, &dictionarylist); |
77 |
|
78 |
return dtree; |
79 |
} |
80 |
|
81 |
/* |
82 |
* dictionary_destroy(dictionary_tree_t *dtree, |
83 |
* void (*destroy_cb)(dictionary_elem_t *delem, void *privdata), |
84 |
* void *privdata); |
85 |
* |
86 |
* Recursively destroys all nodes in a dictionary tree. |
87 |
* |
88 |
* Inputs: |
89 |
* - dictionary tree object |
90 |
* - optional iteration callback |
91 |
* - optional opaque/private data to pass to callback |
92 |
* |
93 |
* Outputs: |
94 |
* - nothing |
95 |
* |
96 |
* Side Effects: |
97 |
* - on success, a dtree and optionally it's children are destroyed. |
98 |
* |
99 |
* Notes: |
100 |
* - if this is called without a callback, the objects bound to the |
101 |
* DTree will not be destroyed. |
102 |
* |
103 |
* Bugs: |
104 |
* - this function assumes that the given dtree reference is valid. |
105 |
*/ |
106 |
void |
107 |
dictionary_destroy (dictionary_tree_t *dtree, void (*destroy_cb) (dictionary_elem_t *delem, void *privdata), void *privdata) |
108 |
{ |
109 |
node_t *n, *tn; |
110 |
int i; |
111 |
|
112 |
for (i = 0; i < dtree->resolution; i++) |
113 |
{ |
114 |
LIST_FOREACH_SAFE (n, tn, dtree->hashv[i].head) |
115 |
{ |
116 |
/* delem_t is a subclass of node_t. */ |
117 |
dictionary_elem_t *delem = (dictionary_elem_t *) n; |
118 |
|
119 |
if (destroy_cb != NULL) |
120 |
(*destroy_cb) (delem, privdata); |
121 |
|
122 |
node_del (&delem->node, &dtree->hashv[i]); |
123 |
|
124 |
free (delem->key); |
125 |
free (delem); |
126 |
} |
127 |
} |
128 |
|
129 |
node_del (&dtree->node, &dictionarylist); |
130 |
|
131 |
free (dtree->hashv); |
132 |
free (dtree); |
133 |
} |
134 |
|
135 |
/* |
136 |
* dictionary_foreach(dictionary_tree_t *dtree, |
137 |
* void (*destroy_cb)(dictionary_elem_t *delem, void *privdata), |
138 |
* void *privdata); |
139 |
* |
140 |
* Iterates over all entries in a DTree. |
141 |
* |
142 |
* Inputs: |
143 |
* - dictionary tree object |
144 |
* - optional iteration callback |
145 |
* - optional opaque/private data to pass to callback |
146 |
* |
147 |
* Outputs: |
148 |
* - nothing |
149 |
* |
150 |
* Side Effects: |
151 |
* - on success, a dtree is iterated |
152 |
* |
153 |
* Bugs: |
154 |
* - this function assumes that the given dtree reference is valid. |
155 |
*/ |
156 |
void |
157 |
dictionary_foreach (dictionary_tree_t *dtree, int (*foreach_cb) (dictionary_elem_t *delem, void *privdata), void *privdata) |
158 |
{ |
159 |
node_t *n, *tn; |
160 |
int i, ret = 0; |
161 |
|
162 |
for (i = 0; i < dtree->resolution && ret == 0; i++) |
163 |
{ |
164 |
LIST_FOREACH_SAFE (n, tn, dtree->hashv[i].head) |
165 |
{ |
166 |
/* delem_t is a subclass of node_t. */ |
167 |
dictionary_elem_t *delem = (dictionary_elem_t *) n; |
168 |
|
169 |
if (foreach_cb != NULL) |
170 |
ret = (*foreach_cb) (delem, privdata); |
171 |
} |
172 |
} |
173 |
} |
174 |
|
175 |
/* |
176 |
* dictionary_foreach(dictionary_tree_t *dtree, |
177 |
* void (*destroy_cb)(dictionary_elem_t *delem, void *privdata), |
178 |
* void *privdata); |
179 |
* |
180 |
* Searches all entries in a DTree using a custom callback. |
181 |
* |
182 |
* Inputs: |
183 |
* - dictionary tree object |
184 |
* - optional iteration callback |
185 |
* - optional opaque/private data to pass to callback |
186 |
* |
187 |
* Outputs: |
188 |
* - on success, the requested object |
189 |
* - on failure, NULL. |
190 |
* |
191 |
* Side Effects: |
192 |
* - a dtree is iterated until the requested conditions are met |
193 |
* |
194 |
* Bugs: |
195 |
* - this function assumes that the given dtree reference is valid. |
196 |
*/ |
197 |
void * |
198 |
dictionary_search (dictionary_tree_t *dtree, void *(*foreach_cb) (dictionary_elem_t *delem, void *privdata), void *privdata) |
199 |
{ |
200 |
node_t *n, *tn; |
201 |
int i; |
202 |
void *ret = NULL; |
203 |
|
204 |
for (i = 0; i < dtree->resolution && ret == NULL; i++) |
205 |
{ |
206 |
LIST_FOREACH_SAFE (n, tn, dtree->hashv[i].head) |
207 |
{ |
208 |
/* delem_t is a subclass of node_t. */ |
209 |
dictionary_elem_t *delem = (dictionary_elem_t *) n; |
210 |
|
211 |
if (foreach_cb != NULL) |
212 |
ret = (*foreach_cb) (delem, privdata); |
213 |
} |
214 |
} |
215 |
|
216 |
return ret; |
217 |
} |
218 |
|
219 |
/* |
220 |
* dictionary_foreach_start(dictionary_tree_t *dtree, |
221 |
* dictionary_iteration_state_t *state); |
222 |
* |
223 |
* Initializes a static DTree iterator. |
224 |
* |
225 |
* Inputs: |
226 |
* - dictionary tree object |
227 |
* - static DTree iterator |
228 |
* |
229 |
* Outputs: |
230 |
* - nothing |
231 |
* |
232 |
* Side Effects: |
233 |
* - the static iterator, &state, is initialized. |
234 |
* |
235 |
* Bugs: |
236 |
* - this function assumes that the given dtree reference is valid. |
237 |
*/ |
238 |
void |
239 |
dictionary_foreach_start (dictionary_tree_t *dtree, dictionary_iteration_state_t *state) |
240 |
{ |
241 |
state->bucket = 0; |
242 |
state->cur = NULL; |
243 |
state->next = NULL; |
244 |
/* find first item */ |
245 |
while (state->bucket < dtree->resolution) |
246 |
{ |
247 |
state->cur = (dictionary_elem_t *) dtree->hashv[state->bucket].head; |
248 |
if (state->cur != NULL) |
249 |
break; |
250 |
state->bucket++; |
251 |
} |
252 |
if (state->cur == NULL) |
253 |
return; |
254 |
/* make state->cur point to first item and state->next point to |
255 |
* second item */ |
256 |
state->next = state->cur; |
257 |
dictionary_foreach_next (dtree, state); |
258 |
} |
259 |
|
260 |
/* |
261 |
* dictionary_foreach_cur(dictionary_tree_t *dtree, |
262 |
* dictionary_iteration_state_t *state); |
263 |
* |
264 |
* Returns the data from the current node being iterated by the |
265 |
* static iterator. |
266 |
* |
267 |
* Inputs: |
268 |
* - dictionary tree object |
269 |
* - static DTree iterator |
270 |
* |
271 |
* Outputs: |
272 |
* - reference to data in the current dtree node being iterated |
273 |
* |
274 |
* Side Effects: |
275 |
* - none |
276 |
* |
277 |
* Bugs: |
278 |
* - this function assumes that the given dtree reference is valid. |
279 |
*/ |
280 |
void * |
281 |
dictionary_foreach_cur (dictionary_tree_t *dtree, dictionary_iteration_state_t *state) |
282 |
{ |
283 |
return state->cur != NULL ? state->cur->node.data : NULL; |
284 |
} |
285 |
|
286 |
/* |
287 |
* dictionary_foreach_next(dictionary_tree_t *dtree, |
288 |
* dictionary_iteration_state_t *state); |
289 |
* |
290 |
* Advances a static DTree iterator. |
291 |
* |
292 |
* Inputs: |
293 |
* - dictionary tree object |
294 |
* - static DTree iterator |
295 |
* |
296 |
* Outputs: |
297 |
* - nothing |
298 |
* |
299 |
* Side Effects: |
300 |
* - the static iterator, &state, is advanced to a new DTree node. |
301 |
* |
302 |
* Bugs: |
303 |
* - this function assumes that the given dtree reference is valid. |
304 |
*/ |
305 |
void |
306 |
dictionary_foreach_next (dictionary_tree_t *dtree, dictionary_iteration_state_t *state) |
307 |
{ |
308 |
if (state->cur == NULL) |
309 |
{ |
310 |
slog (LG_DEBUG, "dictionary_foreach_next(): called again after iteration finished on dtree<%p>", dtree); |
311 |
return; |
312 |
} |
313 |
state->cur = state->next; |
314 |
if (state->next == NULL) |
315 |
return; |
316 |
state->next = (dictionary_elem_t *) state->next->node.next; |
317 |
if (state->next != NULL) |
318 |
return; |
319 |
while (++state->bucket < dtree->resolution) |
320 |
{ |
321 |
state->next = (dictionary_elem_t *) dtree->hashv[state->bucket].head; |
322 |
if (state->next != NULL) |
323 |
return; |
324 |
} |
325 |
} |
326 |
|
327 |
/* |
328 |
* dictionary_find(dictionary_tree_t *dtree, char const * const key) |
329 |
* |
330 |
* Looks up a DTree node by name. |
331 |
* |
332 |
* Inputs: |
333 |
* - dictionary tree object |
334 |
* - name of node to lookup |
335 |
* |
336 |
* Outputs: |
337 |
* - on success, the dtree node requested |
338 |
* - on failure, NULL |
339 |
* |
340 |
* Side Effects: |
341 |
* - none |
342 |
*/ |
343 |
dictionary_elem_t * |
344 |
dictionary_find (dictionary_tree_t *dtree, char const * const key) |
345 |
{ |
346 |
node_t *n; |
347 |
int i; |
348 |
|
349 |
if (dtree == NULL || key == NULL) |
350 |
return NULL; |
351 |
|
352 |
i = shash ((const unsigned char *) key) % dtree->resolution; |
353 |
|
354 |
LIST_FOREACH (n, dtree->hashv[i].head) |
355 |
{ |
356 |
/* delem_t is a subclass of node_t. */ |
357 |
dictionary_elem_t *delem = (dictionary_elem_t *) n; |
358 |
|
359 |
if (!dtree->compare_cb (key, delem->key)) |
360 |
return delem; |
361 |
} |
362 |
|
363 |
return NULL; |
364 |
} |
365 |
|
366 |
/* |
367 |
* dictionary_add(dictionary_tree_t *dtree, char const * const key, void *data) |
368 |
* |
369 |
* Creates a new DTree node and binds data to it. |
370 |
* |
371 |
* Inputs: |
372 |
* - dictionary tree object |
373 |
* - name for new DTree node |
374 |
* - data to bind to the new DTree node |
375 |
* |
376 |
* Outputs: |
377 |
* - on success, a new DTree node |
378 |
* - on failure, NULL |
379 |
* |
380 |
* Side Effects: |
381 |
* - data is inserted into the DTree. |
382 |
*/ |
383 |
dictionary_elem_t * |
384 |
dictionary_add (dictionary_tree_t *dtree, char const * const key, void *data) |
385 |
{ |
386 |
dictionary_elem_t *delem; |
387 |
int i; |
388 |
|
389 |
if (dtree == NULL || key == NULL || data == NULL) |
390 |
return NULL; |
391 |
|
392 |
if (dictionary_find (dtree, key) != NULL) |
393 |
{ |
394 |
slog (LG_DEBUG, "dictionary_add(): entry already exists in dtree<%p> for key '%s'!", dtree, key); |
395 |
return NULL; |
396 |
} |
397 |
|
398 |
i = shash ((const unsigned char *) key) % dtree->resolution; |
399 |
delem = static_cast<dictionary_elem_t *> (malloc (sizeof (dictionary_elem_t))); |
400 |
memset (delem, '\0', sizeof (dictionary_elem_t)); |
401 |
|
402 |
delem->key = sstrdup (key); |
403 |
node_add (data, &delem->node, &dtree->hashv[i]); |
404 |
|
405 |
return delem; |
406 |
} |
407 |
|
408 |
/* |
409 |
* dictionary_delete(dictionary_tree_t *dtree, char const * const key) |
410 |
* |
411 |
* Deletes data from a dictionary tree. |
412 |
* |
413 |
* Inputs: |
414 |
* - dictionary tree object |
415 |
* - name of DTree node to delete |
416 |
* |
417 |
* Outputs: |
418 |
* - on success, the remaining data that needs to be freed |
419 |
* - on failure, NULL |
420 |
* |
421 |
* Side Effects: |
422 |
* - data is removed from the DTree. |
423 |
* |
424 |
* Notes: |
425 |
* - the returned data needs to be freed/released manually! |
426 |
*/ |
427 |
void * |
428 |
dictionary_delete (dictionary_tree_t *dtree, char const * const key) |
429 |
{ |
430 |
dictionary_elem_t *delem = dictionary_find (dtree, key); |
431 |
void *data; |
432 |
int i; |
433 |
|
434 |
if (delem == NULL) |
435 |
{ |
436 |
slog (LG_DEBUG, "dictionary_delete(): entry '%s' does not exist in dtree<%p>!", key, dtree); |
437 |
return NULL; |
438 |
} |
439 |
|
440 |
i = shash ((const unsigned char *) key) % dtree->resolution; |
441 |
|
442 |
data = delem->node.data; |
443 |
|
444 |
node_del (&delem->node, &dtree->hashv[i]); |
445 |
|
446 |
free (delem->key); |
447 |
free (delem); |
448 |
|
449 |
return data; |
450 |
} |
451 |
|
452 |
/* |
453 |
* dictionary_retrieve(dictionary_tree_t *dtree, char const * const key) |
454 |
* |
455 |
* Retrieves data from a dictionary tree. |
456 |
* |
457 |
* Inputs: |
458 |
* - dictionary tree object |
459 |
* - name of node to lookup |
460 |
* |
461 |
* Outputs: |
462 |
* - on success, the data bound to the DTree node. |
463 |
* - on failure, NULL |
464 |
* |
465 |
* Side Effects: |
466 |
* - none |
467 |
*/ |
468 |
void * |
469 |
dictionary_retrieve (dictionary_tree_t *dtree, char const * const key) |
470 |
{ |
471 |
dictionary_elem_t *delem = dictionary_find (dtree, key); |
472 |
|
473 |
if (delem != NULL) |
474 |
return delem->node.data; |
475 |
|
476 |
return NULL; |
477 |
} |
478 |
|
479 |
#define MAXCOUNT 10 |
480 |
|
481 |
/* |
482 |
* dictionary_stats(void (*stats_cb)(char const * const line, void *privdata), void *privdata) |
483 |
* |
484 |
* Displays statistics about all of the registered DTrees. |
485 |
* |
486 |
* Inputs: |
487 |
* - callback function |
488 |
* - optional opaque data |
489 |
* |
490 |
* Outputs: |
491 |
* - none |
492 |
* |
493 |
* Side Effects: |
494 |
* - data is passed to the callback function about the dtree system. |
495 |
*/ |
496 |
void |
497 |
dictionary_stats (void (*stats_cb) (char const * const line, void *privdata), void *privdata) |
498 |
{ |
499 |
node_t *n; |
500 |
dictionary_tree_t *dtree; |
501 |
char buf[120]; |
502 |
int i, count1, totalcount, maxdepth; |
503 |
int counts[MAXCOUNT + 1]; |
504 |
|
505 |
LIST_FOREACH (n, dictionarylist.head) |
506 |
{ |
507 |
dtree = static_cast<dictionary_tree_t *> (n->data); |
508 |
snprintf (buf, sizeof buf, "Hash statistics for %s", asobject (dtree)->name); |
509 |
stats_cb (buf, privdata); |
510 |
for (i = 0; i <= MAXCOUNT; i++) |
511 |
counts[i] = 0; |
512 |
totalcount = 0; |
513 |
maxdepth = 0; |
514 |
for (i = 0; i < dtree->resolution; i++) |
515 |
{ |
516 |
count1 = LIST_LENGTH (&dtree->hashv[i]); |
517 |
totalcount += count1; |
518 |
if (count1 > maxdepth) |
519 |
maxdepth = count1; |
520 |
if (count1 > MAXCOUNT) |
521 |
count1 = MAXCOUNT; |
522 |
counts[count1]++; |
523 |
} |
524 |
snprintf (buf, sizeof buf, "Size: %d Items: %d Max depth: %d", dtree->resolution, totalcount, maxdepth); |
525 |
stats_cb (buf, privdata); |
526 |
for (i = 0; i <= MAXCOUNT; i++) |
527 |
{ |
528 |
snprintf (buf, sizeof buf, "Nodes with %d%s entries: %d", i, i == MAXCOUNT ? " or more" : "", counts[i]); |
529 |
stats_cb (buf, privdata); |
530 |
} |
531 |
} |
532 |
} |
533 |
|
534 |
/* vim:cinoptions=>s,e0,n0,f0,{0,}0,^0,=s,ps,t0,c3,+s,(2s,us,)20,*30,gs,hs |
535 |
* vim:ts=8 |
536 |
* vim:sw=8 |
537 |
* vim:noexpandtab |
538 |
*/ |