ViewVC Help
View File | Revision Log | Show Annotations | Download File
/cvs/ermyth/src/dictionary.C
(Generate patch)

Comparing ermyth/src/dictionary.C (file contents):
Revision 1.3 by pippijn, Sat Jul 21 13:23:21 2007 UTC vs.
Revision 1.4 by pippijn, Tue Aug 28 17:08:12 2007 UTC

1/* 1/*
2 * dictionary.C: Dictionary-backed trees. 2 * dictionary.C: Dictionary-backed trees.
3 * Rights to this code are documented in doc/pod/license.pod. 3 * Rights to this code are documented in doc/pod/license.pod.
4 * 4 *
5 * Copyright © 2005-2007 Atheme Project (http://www.atheme.org) 5 * Copyright © 2005-2007 Atheme Project (http://www.atheme.org)
6 */ 6 */
7 7
8static char const rcsid[] = "$Id: dictionary.C,v 1.3 2007/07/21 13:23:21 pippijn Exp $"; 8static char const rcsid[] = "$Id: dictionary.C,v 1.4 2007/08/28 17:08:12 pippijn Exp $";
9 9
10#include "atheme.h" 10#include "atheme.h"
11 11
12list_t dictionarylist; 12list_t dictionarylist;
13 13
… …
15{ 15{
16 object_t parent; 16 object_t parent;
17 17
18 int resolution; 18 int resolution;
19 list_t *hashv; /* dynamically allocated by dictionary_create() */ 19 list_t *hashv; /* dynamically allocated by dictionary_create() */
20 int (*compare_cb) (const char *a, const char *b); 20 int (*compare_cb) (char const * const a, char const * const b);
21 node_t node; 21 node_t node;
22}; 22};
23 23
24/* 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 */
32static unsigned int
33shash (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/*
25 * dictionary_create(const char *name, int resolution, 49 * dictionary_create(char const * const name, int resolution,
26 * int (*compare_cb)(const char *a, const char *b) 50 * int (*compare_cb)(char const * const a, char const * const b)
27 * 51 *
28 * DTree object factory. 52 * DTree object factory.
29 * 53 *
30 * Inputs: 54 * Inputs:
31 * - name of dictionary tree 55 * - name of dictionary tree
… …
38 * Side Effects: 62 * Side Effects:
39 * - if services runs out of memory and cannot allocate the object, 63 * - if services runs out of memory and cannot allocate the object,
40 * the program will abort. 64 * the program will abort.
41 */ 65 */
42dictionary_tree_t * 66dictionary_tree_t *
43dictionary_create (const char *name, int resolution, int (*compare_cb) (const char *a, const char *b)) 67dictionary_create (char const * const name, int resolution, int (*compare_cb) (char const * const a, char const * const b))
44{ 68{
45 dictionary_tree_t *dtree = static_cast<dictionary_tree_t *> (smalloc (sizeof (dictionary_tree_t))); 69 dictionary_tree_t *dtree = static_cast<dictionary_tree_t *> (malloc (sizeof (dictionary_tree_t)));
46 70
47 object_init (&dtree->parent, name, NULL); 71 object_init (&dtree->parent, name, NULL);
48 dtree->resolution = resolution; 72 dtree->resolution = resolution;
49 dtree->hashv = static_cast<list_t *> (smalloc (sizeof (list_t) * resolution)); 73 dtree->hashv = static_cast<list_t *> (malloc (sizeof (list_t) * resolution));
50 dtree->compare_cb = compare_cb; 74 dtree->compare_cb = compare_cb;
51 memset (dtree->hashv, '\0', sizeof (list_t) * resolution); 75 memset (dtree->hashv, '\0', sizeof (list_t) * resolution);
52 node_add (dtree, &dtree->node, &dictionarylist); 76 node_add (dtree, &dtree->node, &dictionarylist);
53 77
54 return dtree; 78 return dtree;
… …
299 return; 323 return;
300 } 324 }
301} 325}
302 326
303/* 327/*
304 * dictionary_find(dictionary_tree_t *dtree, const char *key) 328 * dictionary_find(dictionary_tree_t *dtree, char const * const key)
305 * 329 *
306 * Looks up a DTree node by name. 330 * Looks up a DTree node by name.
307 * 331 *
308 * Inputs: 332 * Inputs:
309 * - dictionary tree object 333 * - dictionary tree object
… …
315 * 339 *
316 * Side Effects: 340 * Side Effects:
317 * - none 341 * - none
318 */ 342 */
319dictionary_elem_t * 343dictionary_elem_t *
320dictionary_find (dictionary_tree_t *dtree, const char *key) 344dictionary_find (dictionary_tree_t *dtree, char const * const key)
321{ 345{
322 node_t *n; 346 node_t *n;
323 int i; 347 int i;
324 348
325 if (dtree == NULL || key == NULL) 349 if (dtree == NULL || key == NULL)
… …
338 362
339 return NULL; 363 return NULL;
340} 364}
341 365
342/* 366/*
343 * dictionary_add(dictionary_tree_t *dtree, const char *key, void *data) 367 * dictionary_add(dictionary_tree_t *dtree, char const * const key, void *data)
344 * 368 *
345 * Creates a new DTree node and binds data to it. 369 * Creates a new DTree node and binds data to it.
346 * 370 *
347 * Inputs: 371 * Inputs:
348 * - dictionary tree object 372 * - dictionary tree object
… …
355 * 379 *
356 * Side Effects: 380 * Side Effects:
357 * - data is inserted into the DTree. 381 * - data is inserted into the DTree.
358 */ 382 */
359dictionary_elem_t * 383dictionary_elem_t *
360dictionary_add (dictionary_tree_t *dtree, const char *key, void *data) 384dictionary_add (dictionary_tree_t *dtree, char const * const key, void *data)
361{ 385{
362 dictionary_elem_t *delem; 386 dictionary_elem_t *delem;
363 int i; 387 int i;
364 388
365 if (dtree == NULL || key == NULL || data == NULL) 389 if (dtree == NULL || key == NULL || data == NULL)
… …
370 slog (LG_DEBUG, "dictionary_add(): entry already exists in dtree<%p> for key '%s'!", dtree, key); 394 slog (LG_DEBUG, "dictionary_add(): entry already exists in dtree<%p> for key '%s'!", dtree, key);
371 return NULL; 395 return NULL;
372 } 396 }
373 397
374 i = shash ((const unsigned char *) key) % dtree->resolution; 398 i = shash ((const unsigned char *) key) % dtree->resolution;
375 delem = static_cast<dictionary_elem_t *> (smalloc (sizeof (dictionary_elem_t))); 399 delem = static_cast<dictionary_elem_t *> (malloc (sizeof (dictionary_elem_t)));
376 memset (delem, '\0', sizeof (dictionary_elem_t)); 400 memset (delem, '\0', sizeof (dictionary_elem_t));
377 401
378 delem->key = sstrdup (key); 402 delem->key = sstrdup (key);
379 node_add (data, &delem->node, &dtree->hashv[i]); 403 node_add (data, &delem->node, &dtree->hashv[i]);
380 404
381 return delem; 405 return delem;
382} 406}
383 407
384/* 408/*
385 * dictionary_delete(dictionary_tree_t *dtree, const char *key) 409 * dictionary_delete(dictionary_tree_t *dtree, char const * const key)
386 * 410 *
387 * Deletes data from a dictionary tree. 411 * Deletes data from a dictionary tree.
388 * 412 *
389 * Inputs: 413 * Inputs:
390 * - dictionary tree object 414 * - dictionary tree object
… …
399 * 423 *
400 * Notes: 424 * Notes:
401 * - the returned data needs to be freed/released manually! 425 * - the returned data needs to be freed/released manually!
402 */ 426 */
403void * 427void *
404dictionary_delete (dictionary_tree_t *dtree, const char *key) 428dictionary_delete (dictionary_tree_t *dtree, char const * const key)
405{ 429{
406 dictionary_elem_t *delem = dictionary_find (dtree, key); 430 dictionary_elem_t *delem = dictionary_find (dtree, key);
407 void *data; 431 void *data;
408 int i; 432 int i;
409 433
… …
424 448
425 return data; 449 return data;
426} 450}
427 451
428/* 452/*
429 * dictionary_retrieve(dictionary_tree_t *dtree, const char *key) 453 * dictionary_retrieve(dictionary_tree_t *dtree, char const * const key)
430 * 454 *
431 * Retrieves data from a dictionary tree. 455 * Retrieves data from a dictionary tree.
432 * 456 *
433 * Inputs: 457 * Inputs:
434 * - dictionary tree object 458 * - dictionary tree object
… …
440 * 464 *
441 * Side Effects: 465 * Side Effects:
442 * - none 466 * - none
443 */ 467 */
444void * 468void *
445dictionary_retrieve (dictionary_tree_t *dtree, const char *key) 469dictionary_retrieve (dictionary_tree_t *dtree, char const * const key)
446{ 470{
447 dictionary_elem_t *delem = dictionary_find (dtree, key); 471 dictionary_elem_t *delem = dictionary_find (dtree, key);
448 472
449 if (delem != NULL) 473 if (delem != NULL)
450 return delem->node.data; 474 return delem->node.data;
… …
453} 477}
454 478
455#define MAXCOUNT 10 479#define MAXCOUNT 10
456 480
457/* 481/*
458 * dictionary_stats(void (*stats_cb)(const char *line, void *privdata), void *privdata) 482 * dictionary_stats(void (*stats_cb)(char const * const line, void *privdata), void *privdata)
459 * 483 *
460 * Displays statistics about all of the registered DTrees. 484 * Displays statistics about all of the registered DTrees.
461 * 485 *
462 * Inputs: 486 * Inputs:
463 * - callback function 487 * - callback function
… …
468 * 492 *
469 * Side Effects: 493 * Side Effects:
470 * - data is passed to the callback function about the dtree system. 494 * - data is passed to the callback function about the dtree system.
471 */ 495 */
472void 496void
473dictionary_stats (void (*stats_cb) (const char *line, void *privdata), void *privdata) 497dictionary_stats (void (*stats_cb) (char const * const line, void *privdata), void *privdata)
474{ 498{
475 node_t *n; 499 node_t *n;
476 dictionary_tree_t *dtree; 500 dictionary_tree_t *dtree;
477 char buf[120]; 501 char buf[120];
478 int i, count1, totalcount, maxdepth; 502 int i, count1, totalcount, maxdepth;

Diff Legend

– Removed lines
+ Added lines
< Changed lines
> Changed lines