1 |
pippijn |
1.1 |
/* |
2 |
|
|
* Copyright © 2006 William Pitcock <nenolod -at- nenolod.net> |
3 |
|
|
* Rights to this code are as defined in doc/LICENSE. |
4 |
|
|
* |
5 |
|
|
* A simple dictionary tree implementation. |
6 |
|
|
* See Knuth ACP, volume 1 for a more detailed explanation. |
7 |
|
|
* |
8 |
|
|
* $Id: dictionary.h 8413 2007-06-04 18:45:05Z pippijn $ |
9 |
|
|
*/ |
10 |
|
|
|
11 |
|
|
#ifndef _DICTIONARY_H |
12 |
|
|
#define _DICTIONARY_H |
13 |
|
|
|
14 |
|
|
struct dictionary_tree_t; /* defined in src/dictionary.c */ |
15 |
|
|
|
16 |
|
|
/* |
17 |
|
|
* dictionary_elem_t is a child of node_t, which adds a key field. |
18 |
|
|
* node_t access is done by ((node_t *) delem)->next|prev, |
19 |
|
|
* or through delem->node.(next|prev). |
20 |
|
|
*/ |
21 |
|
|
struct dictionary_elem_t |
22 |
|
|
{ |
23 |
|
|
node_t node; |
24 |
|
|
char *key; |
25 |
|
|
}; |
26 |
|
|
|
27 |
|
|
/* |
28 |
|
|
* dictionary_iteration_state_t, private. |
29 |
|
|
*/ |
30 |
|
|
struct dictionary_iteration_state_t |
31 |
|
|
{ |
32 |
|
|
int bucket; |
33 |
|
|
dictionary_elem_t *cur, *next; |
34 |
|
|
}; |
35 |
|
|
|
36 |
|
|
#define DICTIONARY_FOREACH(element, type, state, dict) \ |
37 |
|
|
for (dictionary_foreach_start ((dict), (state)); \ |
38 |
|
|
(element = static_cast<type *> (dictionary_foreach_cur ((dict), (state)))); \ |
39 |
|
|
dictionary_foreach_next ((dict), (state))) |
40 |
|
|
|
41 |
|
|
/* |
42 |
|
|
* dictionary_create() creates a new dictionary tree of the defined resolution. |
43 |
|
|
* name is only used for statistical purposes. |
44 |
|
|
* compare_cb is the comparison function, typically strcmp, strcasecmp or |
45 |
|
|
* irccasecmp. |
46 |
|
|
*/ |
47 |
|
|
E dictionary_tree_t *dictionary_create (const char *name, int resolution, int (*compare_cb) (const char *a, const char *b)); |
48 |
|
|
|
49 |
|
|
/* |
50 |
|
|
* dictionary_destroy() destroys all entries in a dtree, and also optionally calls |
51 |
|
|
* a defined callback function to destroy any data attached to it. |
52 |
|
|
*/ |
53 |
|
|
E void dictionary_destroy (dictionary_tree_t *dtree, void (*destroy_cb) (dictionary_elem_t *delem, void *privdata), void *privdata); |
54 |
|
|
|
55 |
|
|
/* |
56 |
|
|
* dictionary_foreach() iterates all entries in a dtree, and also optionally calls |
57 |
|
|
* a defined callback function to use any data attached to it. |
58 |
|
|
* |
59 |
|
|
* To shortcircuit iteration, return non-zero from the callback function. |
60 |
|
|
*/ |
61 |
|
|
E void dictionary_foreach (dictionary_tree_t *dtree, int (*foreach_cb) (dictionary_elem_t *delem, void *privdata), void *privdata); |
62 |
|
|
|
63 |
|
|
/* |
64 |
|
|
* dictionary_search() iterates all entries in a dtree, and also optionally calls |
65 |
|
|
* a defined callback function to use any data attached to it. |
66 |
|
|
* |
67 |
|
|
* When the object is found, a non-NULL is returned from the callback, which results |
68 |
|
|
* in that object being returned to the user. |
69 |
|
|
*/ |
70 |
|
|
E void *dictionary_search (dictionary_tree_t *dtree, void *(*foreach_cb) (dictionary_elem_t *delem, void *privdata), void *privdata); |
71 |
|
|
|
72 |
|
|
/* |
73 |
|
|
* dictionary_foreach_start() begins an iteration over all items |
74 |
|
|
* keeping state in the given struct. If there is only one iteration |
75 |
|
|
* in progress at a time, it is permitted to remove the current element |
76 |
|
|
* of the iteration (but not any other element). |
77 |
|
|
*/ |
78 |
|
|
E void dictionary_foreach_start (dictionary_tree_t *dtree, dictionary_iteration_state_t *state); |
79 |
|
|
|
80 |
|
|
/* |
81 |
|
|
* dictionary_foreach_cur() returns the current element of the iteration, |
82 |
|
|
* or NULL if there are no more elements. |
83 |
|
|
*/ |
84 |
|
|
E void *dictionary_foreach_cur (dictionary_tree_t *dtree, dictionary_iteration_state_t *state); |
85 |
|
|
|
86 |
|
|
/* |
87 |
|
|
* dictionary_foreach_next() moves to the next element. |
88 |
|
|
*/ |
89 |
|
|
E void dictionary_foreach_next (dictionary_tree_t *dtree, dictionary_iteration_state_t *state); |
90 |
|
|
|
91 |
|
|
/* |
92 |
|
|
* dictionary_add() adds a key->value entry to the dictionary tree. |
93 |
|
|
*/ |
94 |
|
|
E dictionary_elem_t *dictionary_add (dictionary_tree_t *dtree, const char *key, void *data); |
95 |
|
|
|
96 |
|
|
/* |
97 |
|
|
* dictionary_find() returns a dictionary_elem_t container from a dtree for key 'key'. |
98 |
|
|
*/ |
99 |
|
|
E dictionary_elem_t *dictionary_find (dictionary_tree_t *dtree, const char *key); |
100 |
|
|
|
101 |
|
|
/* |
102 |
|
|
* dictionary_retrieve() returns data from a dtree for key 'key'. |
103 |
|
|
*/ |
104 |
|
|
E void *dictionary_retrieve (dictionary_tree_t *dtree, const char *key); |
105 |
|
|
|
106 |
|
|
/* |
107 |
|
|
* dictionary_delete() deletes a key->value entry from the dictionary tree. |
108 |
|
|
*/ |
109 |
|
|
E void *dictionary_delete (dictionary_tree_t *dtree, const char *key); |
110 |
|
|
|
111 |
|
|
/* |
112 |
|
|
* dictionary_stats() outputs hash statistics for all dictionary trees. |
113 |
|
|
* The output consists of a number of lines, output one by one via the |
114 |
|
|
* given callback. |
115 |
|
|
*/ |
116 |
|
|
E void dictionary_stats (void (*stats_cb) (const char *line, void *privdata), void *privdata); |
117 |
|
|
|
118 |
|
|
#endif |