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.3 2007-07-21 13:23:21 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.4
Committed:	Tue Aug 28 17:08:12 2007 UTC (16 years, 9 months ago) by pippijn
Content type:	text/plain
Branch:	MAIN
Changes since 1.3:	+43 -19 lines
Log Message:	- changed name - updated the example config to the new system - added more documentation - enhanced documentation generators - added a link to the pdf to the website - added an RSS feed generator - transitioned hooks to c++ callbacks - did various merges with upstream along the way - added const where appropriate - removed the old block allocator - fixed most memory leaks - transitioned some dictionaries to std::map - transitioned some lists to std::vector - made some free functions members where appropriate - renamed string to dynstr and added a static string ststr - use NOW instead of time (NULL) if possible - completely reworked database backends, crypto handlers and protocol handlers to use an object factory - removed the old module system. ermyth does not do any dynamic loading anymore - fixed most of the build system - reworked how protocol commands work
#	User	Rev	Content
1	pippijn	1.1	/*
2			* dictionary.C: Dictionary-backed trees.
3	pippijn	1.2	* Rights to this code are documented in doc/pod/license.pod.
4	pippijn	1.1	*
5	pippijn	1.4	* Copyright © 2005-2007 Atheme Project (http://www.atheme.org)
6	pippijn	1.1	*/
7
8	pippijn	1.4	static char const rcsid[] = "$Id: dictionary.C,v 1.3 2007-07-21 13:23:21 pippijn Exp $";
9	pippijn	1.1
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	pippijn	1.4	int (compare_cb) (char const const a, char const * const b);
21	pippijn	1.1	node_t node;
22			};
23
24			/*
25	pippijn	1.4	* 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	pippijn	1.1	*
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	pippijn	1.4	dictionary_create (char const * const name, int resolution, int (compare_cb) (char const const a, char const * const b))
68	pippijn	1.1	{
69	pippijn	1.4	dictionary_tree_t dtree = static_cast<dictionary_tree_t > (malloc (sizeof (dictionary_tree_t)));
70	pippijn	1.1
71			object_init (&dtree->parent, name, NULL);
72			dtree->resolution = resolution;
73	pippijn	1.4	dtree->hashv = static_cast<list_t > (malloc (sizeof (list_t) resolution));
74	pippijn	1.1	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	pippijn	1.4	* dictionary_find(dictionary_tree_t dtree, char const const key)
329	pippijn	1.1	*
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	pippijn	1.4	dictionary_find (dictionary_tree_t dtree, char const const key)
345	pippijn	1.1	{
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	pippijn	1.4	* dictionary_add(dictionary_tree_t dtree, char const const key, void *data)
368	pippijn	1.1	*
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	pippijn	1.4	dictionary_add (dictionary_tree_t dtree, char const const key, void *data)
385	pippijn	1.1	{
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	pippijn	1.4	delem = static_cast<dictionary_elem_t *> (malloc (sizeof (dictionary_elem_t)));
400	pippijn	1.1	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	pippijn	1.4	* dictionary_delete(dictionary_tree_t dtree, char const const key)
410	pippijn	1.1	*
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	pippijn	1.4	dictionary_delete (dictionary_tree_t dtree, char const const key)
429	pippijn	1.1	{
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	pippijn	1.4	* dictionary_retrieve(dictionary_tree_t dtree, char const const key)
454	pippijn	1.1	*
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	pippijn	1.4	dictionary_retrieve (dictionary_tree_t dtree, char const const key)
470	pippijn	1.1	{
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	pippijn	1.4	* dictionary_stats(void (stats_cb)(char const const line, void privdata), void privdata)
483	pippijn	1.1	*
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	pippijn	1.4	dictionary_stats (void (stats_cb) (char const const line, void privdata), void privdata)
498	pippijn	1.1	{
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			*/