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$";

#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) (const char *a, const char *b);
  node_t node;
};

/*
 * dictionary_create(const char *name, int resolution,
 *                   int (*compare_cb)(const char *a, const char *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 (const char *name, int resolution, int (*compare_cb) (const char *a, const char *b))
{
  dictionary_tree_t *dtree = static_cast<dictionary_tree_t *> (smalloc (sizeof (dictionary_tree_t)));

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