ermyth/src/dictionary.C

/*
 * dictionary.C: Dictionary-backed trees.
 * Rights to this code are documented in doc/pod/license.pod.
 *
 * Copyright © 2005-2007 Atheme Project (http://www.atheme.org)           
 */

static char const rcsid[] = "$Id: dictionary.C,v 1.4 2007-08-28 17:08:12 pippijn Exp $";

#include "atheme.h"

list_t dictionarylist;

struct dictionary_tree_t
{
  object_t parent;

  int resolution;
  list_t *hashv;                /* dynamically allocated by dictionary_create() */
  int (*compare_cb) (char const * const a, char const * const b);
  node_t node;
};

/*
 * This generates a hash value, based on chongo's hash algo,
 * located at http://www.isthe.com/chongo/tech/comp/fnv/
 *
 * The difference between FNV and Atheme's hash algorithm is
 * that FNV uses a random key for toasting, we just use
 * 16 instead.
 */
static unsigned int
shash (const unsigned char *p)
{
  unsigned int hval = HASHINIT;

  if (!p)
    return (0);
  for (; *p != '\0'; ++p)
    {
      hval += (hval << 1) + (hval << 4) + (hval << 7) + (hval << 8) + (hval << 24);
      hval ^= (ToLower (*p) ^ 16);
    }

  return ((hval >> HASHBITS) ^ (hval & ((1 << HASHBITS) - 1)) % HASHSIZE);
}

/*
 * dictionary_create(char const * const name, int resolution,
 *                   int (*compare_cb)(char const * const a, char const * const b)
 *
 * DTree object factory.
 *
 * Inputs:
 *     - name of dictionary tree
 *     - resolution of dictionary tree
 *     - function to use for comparing two entries in the dtree
 *
 * Outputs:
 *     - on success, a new DTree object.
 *
 * Side Effects:
 *     - if services runs out of memory and cannot allocate the object,
 *       the program will abort.
 */
dictionary_tree_t *
dictionary_create (char const * const name, int resolution, int (*compare_cb) (char const * const a, char const * const b))
{
  dictionary_tree_t *dtree = static_cast<dictionary_tree_t *> (malloc (sizeof (dictionary_tree_t)));

  object_init (&dtree->parent, name, NULL);
  dtree->resolution = resolution;
  dtree->hashv = static_cast<list_t *> (malloc (sizeof (list_t) * resolution));
  dtree->compare_cb = compare_cb;
  memset (dtree->hashv, '\0', sizeof (list_t) * resolution);
  node_add (dtree, &dtree->node, &dictionarylist);

  return dtree;
}

/*
 * dictionary_destroy(dictionary_tree_t *dtree,
 *     void (*destroy_cb)(dictionary_elem_t *delem, void *privdata),
 *     void *privdata);
 *
 * Recursively destroys all nodes in a dictionary tree.
 *
 * Inputs:
 *     - dictionary tree object
 *     - optional iteration callback
 *     - optional opaque/private data to pass to callback
 *
 * Outputs:
 *     - nothing
 *
 * Side Effects:
 *     - on success, a dtree and optionally it's children are destroyed.
 *
 * Notes:
 *     - if this is called without a callback, the objects bound to the
 *       DTree will not be destroyed.
 *
 * Bugs:
 *     - this function assumes that the given dtree reference is valid.
 */
void
dictionary_destroy (dictionary_tree_t *dtree, void (*destroy_cb) (dictionary_elem_t *delem, void *privdata), void *privdata)
{
  node_t *n, *tn;
  int i;

  for (i = 0; i < dtree->resolution; i++)
    {
      LIST_FOREACH_SAFE (n, tn, dtree->hashv[i].head)
      {
        /* delem_t is a subclass of node_t. */
        dictionary_elem_t *delem = (dictionary_elem_t *) n;

        if (destroy_cb != NULL)
          (*destroy_cb) (delem, privdata);

        node_del (&delem->node, &dtree->hashv[i]);

        free (delem->key);
        free (delem);
      }
    }

  node_del (&dtree->node, &dictionarylist);

  free (dtree->hashv);
  free (dtree);
}

/*
 * dictionary_foreach(dictionary_tree_t *dtree,
 *     void (*destroy_cb)(dictionary_elem_t *delem, void *privdata),
 *     void *privdata);
 *
 * Iterates over all entries in a DTree.
 *
 * Inputs:
 *     - dictionary tree object
 *     - optional iteration callback
 *     - optional opaque/private data to pass to callback
 *
 * Outputs:
 *     - nothing
 *
 * Side Effects:
 *     - on success, a dtree is iterated
 *
 * Bugs:
 *     - this function assumes that the given dtree reference is valid.
 */
void
dictionary_foreach (dictionary_tree_t *dtree, int (*foreach_cb) (dictionary_elem_t *delem, void *privdata), void *privdata)
{
  node_t *n, *tn;
  int i, ret = 0;

  for (i = 0; i < dtree->resolution && ret == 0; i++)
    {
      LIST_FOREACH_SAFE (n, tn, dtree->hashv[i].head)
      {
        /* delem_t is a subclass of node_t. */
        dictionary_elem_t *delem = (dictionary_elem_t *) n;

        if (foreach_cb != NULL)
          ret = (*foreach_cb) (delem, privdata);
      }
    }
}

/*
 * dictionary_foreach(dictionary_tree_t *dtree,
 *     void (*destroy_cb)(dictionary_elem_t *delem, void *privdata),
 *     void *privdata);
 *
 * Searches all entries in a DTree using a custom callback.
 *
 * Inputs:
 *     - dictionary tree object
 *     - optional iteration callback
 *     - optional opaque/private data to pass to callback
 *
 * Outputs:
 *     - on success, the requested object
 *     - on failure, NULL.
 *
 * Side Effects:
 *     - a dtree is iterated until the requested conditions are met
 *
 * Bugs:
 *     - this function assumes that the given dtree reference is valid.
 */
void *
dictionary_search (dictionary_tree_t *dtree, void *(*foreach_cb) (dictionary_elem_t *delem, void *privdata), void *privdata)
{
  node_t *n, *tn;
  int i;
  void *ret = NULL;

  for (i = 0; i < dtree->resolution && ret == NULL; i++)
    {
      LIST_FOREACH_SAFE (n, tn, dtree->hashv[i].head)
      {
        /* delem_t is a subclass of node_t. */
        dictionary_elem_t *delem = (dictionary_elem_t *) n;

        if (foreach_cb != NULL)
          ret = (*foreach_cb) (delem, privdata);
      }
    }

  return ret;
}

/*
 * dictionary_foreach_start(dictionary_tree_t *dtree,
 *     dictionary_iteration_state_t *state);
 *
 * Initializes a static DTree iterator.
 *
 * Inputs:
 *     - dictionary tree object
 *     - static DTree iterator
 *
 * Outputs:
 *     - nothing
 *
 * Side Effects:
 *     - the static iterator, &state, is initialized.
 *
 * Bugs:
 *     - this function assumes that the given dtree reference is valid.
 */
void
dictionary_foreach_start (dictionary_tree_t *dtree, dictionary_iteration_state_t *state)
{
  state->bucket = 0;
  state->cur = NULL;
  state->next = NULL;
  /* find first item */
  while (state->bucket < dtree->resolution)
    {
      state->cur = (dictionary_elem_t *) dtree->hashv[state->bucket].head;
      if (state->cur != NULL)
        break;
      state->bucket++;
    }
  if (state->cur == NULL)
    return;
  /* make state->cur point to first item and state->next point to
   * second item */
  state->next = state->cur;
  dictionary_foreach_next (dtree, state);
}

/*
 * dictionary_foreach_cur(dictionary_tree_t *dtree,
 *     dictionary_iteration_state_t *state);
 *
 * Returns the data from the current node being iterated by the
 * static iterator.
 *
 * Inputs:
 *     - dictionary tree object
 *     - static DTree iterator
 *
 * Outputs:
 *     - reference to data in the current dtree node being iterated
 *
 * Side Effects:
 *     - none
 *
 * Bugs:
 *     - this function assumes that the given dtree reference is valid.
 */
void *
dictionary_foreach_cur (dictionary_tree_t *dtree, dictionary_iteration_state_t *state)
{
  return state->cur != NULL ? state->cur->node.data : NULL;
}

/*
 * dictionary_foreach_next(dictionary_tree_t *dtree,
 *     dictionary_iteration_state_t *state);
 *
 * Advances a static DTree iterator.
 *
 * Inputs:
 *     - dictionary tree object
 *     - static DTree iterator
 *
 * Outputs:
 *     - nothing
 *
 * Side Effects:
 *     - the static iterator, &state, is advanced to a new DTree node.
 *
 * Bugs:
 *     - this function assumes that the given dtree reference is valid.
 */
void
dictionary_foreach_next (dictionary_tree_t *dtree, dictionary_iteration_state_t *state)
{
  if (state->cur == NULL)
    {
      slog (LG_DEBUG, "dictionary_foreach_next(): called again after iteration finished on dtree<%p>", dtree);
      return;
    }
  state->cur = state->next;
  if (state->next == NULL)
    return;
  state->next = (dictionary_elem_t *) state->next->node.next;
  if (state->next != NULL)
    return;
  while (++state->bucket < dtree->resolution)
    {
      state->next = (dictionary_elem_t *) dtree->hashv[state->bucket].head;
      if (state->next != NULL)
        return;
    }
}

/*
 * dictionary_find(dictionary_tree_t *dtree, char const * const key)
 *
 * Looks up a DTree node by name.
 *
 * Inputs:
 *     - dictionary tree object
 *     - name of node to lookup
 *
 * Outputs:
 *     - on success, the dtree node requested
 *     - on failure, NULL
 *
 * Side Effects:
 *     - none
 */
dictionary_elem_t *
dictionary_find (dictionary_tree_t *dtree, char const * const key)
{
  node_t *n;
  int i;

  if (dtree == NULL || key == NULL)
    return NULL;

  i = shash ((const unsigned char *) key) % dtree->resolution;

  LIST_FOREACH (n, dtree->hashv[i].head)
  {
    /* delem_t is a subclass of node_t. */
    dictionary_elem_t *delem = (dictionary_elem_t *) n;

    if (!dtree->compare_cb (key, delem->key))
      return delem;
  }

  return NULL;
}

/*
 * dictionary_add(dictionary_tree_t *dtree, char const * const key, void *data)
 *
 * Creates a new DTree node and binds data to it.
 *
 * Inputs:
 *     - dictionary tree object
 *     - name for new DTree node
 *     - data to bind to the new DTree node
 *
 * Outputs:
 *     - on success, a new DTree node
 *     - on failure, NULL
 *
 * Side Effects:
 *     - data is inserted into the DTree.
 */
dictionary_elem_t *
dictionary_add (dictionary_tree_t *dtree, char const * const key, void *data)
{
  dictionary_elem_t *delem;
  int i;

  if (dtree == NULL || key == NULL || data == NULL)
    return NULL;

  if (dictionary_find (dtree, key) != NULL)
    {
      slog (LG_DEBUG, "dictionary_add(): entry already exists in dtree<%p> for key '%s'!", dtree, key);
      return NULL;
    }

  i = shash ((const unsigned char *) key) % dtree->resolution;
  delem = static_cast<dictionary_elem_t *> (malloc (sizeof (dictionary_elem_t)));
  memset (delem, '\0', sizeof (dictionary_elem_t));

  delem->key = sstrdup (key);
  node_add (data, &delem->node, &dtree->hashv[i]);

  return delem;
}

/*
 * dictionary_delete(dictionary_tree_t *dtree, char const * const key)
 *
 * Deletes data from a dictionary tree.
 *
 * Inputs:
 *     - dictionary tree object
 *     - name of DTree node to delete
 *
 * Outputs:
 *     - on success, the remaining data that needs to be freed
 *     - on failure, NULL
 *
 * Side Effects:
 *     - data is removed from the DTree.
 *
 * Notes:
 *     - the returned data needs to be freed/released manually!
 */
void *
dictionary_delete (dictionary_tree_t *dtree, char const * const key)
{
  dictionary_elem_t *delem = dictionary_find (dtree, key);
  void *data;
  int i;

  if (delem == NULL)
    {
      slog (LG_DEBUG, "dictionary_delete(): entry '%s' does not exist in dtree<%p>!", key, dtree);
      return NULL;
    }

  i = shash ((const unsigned char *) key) % dtree->resolution;

  data = delem->node.data;

  node_del (&delem->node, &dtree->hashv[i]);

  free (delem->key);
  free (delem);

  return data;
}

/*
 * dictionary_retrieve(dictionary_tree_t *dtree, char const * const key)
 *
 * Retrieves data from a dictionary tree.
 *
 * Inputs:
 *     - dictionary tree object
 *     - name of node to lookup
 *
 * Outputs:
 *     - on success, the data bound to the DTree node.
 *     - on failure, NULL
 *
 * Side Effects:
 *     - none
 */
void *
dictionary_retrieve (dictionary_tree_t *dtree, char const * const key)
{
  dictionary_elem_t *delem = dictionary_find (dtree, key);

  if (delem != NULL)
    return delem->node.data;

  return NULL;
}

#define MAXCOUNT 10

/*
 * dictionary_stats(void (*stats_cb)(char const * const line, void *privdata), void *privdata)
 *
 * Displays statistics about all of the registered DTrees.
 *
 * Inputs:
 *     - callback function
 *     - optional opaque data
 *
 * Outputs:
 *     - none
 *
 * Side Effects:
 *     - data is passed to the callback function about the dtree system.
 */
void
dictionary_stats (void (*stats_cb) (char const * const line, void *privdata), void *privdata)
{
  node_t *n;
  dictionary_tree_t *dtree;
  char buf[120];
  int i, count1, totalcount, maxdepth;
  int counts[MAXCOUNT + 1];

  LIST_FOREACH (n, dictionarylist.head)
  {
    dtree = static_cast<dictionary_tree_t *> (n->data);
    snprintf (buf, sizeof buf, "Hash statistics for %s", asobject (dtree)->name);
    stats_cb (buf, privdata);
    for (i = 0; i <= MAXCOUNT; i++)
      counts[i] = 0;
    totalcount = 0;
    maxdepth = 0;
    for (i = 0; i < dtree->resolution; i++)
      {
        count1 = LIST_LENGTH (&dtree->hashv[i]);
        totalcount += count1;
        if (count1 > maxdepth)
          maxdepth = count1;
        if (count1 > MAXCOUNT)
          count1 = MAXCOUNT;
        counts[count1]++;
      }
    snprintf (buf, sizeof buf, "Size: %d  Items: %d  Max depth: %d", dtree->resolution, totalcount, maxdepth);
    stats_cb (buf, privdata);
    for (i = 0; i <= MAXCOUNT; i++)
      {
        snprintf (buf, sizeof buf, "Nodes with %d%s entries: %d", i, i == MAXCOUNT ? " or more" : "", counts[i]);
        stats_cb (buf, privdata);
      }
  }
}

/* vim:cinoptions=>s,e0,n0,f0,{0,}0,^0,=s,ps,t0,c3,+s,(2s,us,)20,*30,gs,hs
 * vim:ts=8
 * vim:sw=8
 * vim:noexpandtab
 */
Revision:	1.5
Committed:	Thu Aug 30 19:56:24 2007 UTC (16 years, 8 months ago) by pippijn
Content type:	text/plain
Branch:	MAIN
CVS Tags:	HEAD
Changes since 1.4:	+1 -1 lines
State:	*FILE REMOVED*
Log Message:	- put faultcodes into their own namespace - removed old files - limited header garbage in atheme.h - macros to inline bools for connection_t::is_* - put some connection_t functions into the connection_t class
#	Content
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	*/