![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to ghash.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / mpd / src / contrib / libpdel / util|
Return to ghash.c CVS log | Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / mpd / src / contrib / libpdel / util |
1.1 misho 1:
2: /*
3: * Copyright (c) 2001-2002 Packet Design, LLC.
4: * All rights reserved.
5: *
6: * Subject to the following obligations and disclaimer of warranty,
7: * use and redistribution of this software, in source or object code
8: * forms, with or without modifications are expressly permitted by
9: * Packet Design; provided, however, that:
10: *
11: * (i) Any and all reproductions of the source or object code
12: * must include the copyright notice above and the following
13: * disclaimer of warranties; and
14: * (ii) No rights are granted, in any manner or form, to use
15: * Packet Design trademarks, including the mark "PACKET DESIGN"
16: * on advertising, endorsements, or otherwise except as such
17: * appears in the above copyright notice or in the software.
18: *
19: * THIS SOFTWARE IS BEING PROVIDED BY PACKET DESIGN "AS IS", AND
20: * TO THE MAXIMUM EXTENT PERMITTED BY LAW, PACKET DESIGN MAKES NO
21: * REPRESENTATIONS OR WARRANTIES, EXPRESS OR IMPLIED, REGARDING
22: * THIS SOFTWARE, INCLUDING WITHOUT LIMITATION, ANY AND ALL IMPLIED
23: * WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE,
24: * OR NON-INFRINGEMENT. PACKET DESIGN DOES NOT WARRANT, GUARANTEE,
25: * OR MAKE ANY REPRESENTATIONS REGARDING THE USE OF, OR THE RESULTS
26: * OF THE USE OF THIS SOFTWARE IN TERMS OF ITS CORRECTNESS, ACCURACY,
27: * RELIABILITY OR OTHERWISE. IN NO EVENT SHALL PACKET DESIGN BE
28: * LIABLE FOR ANY DAMAGES RESULTING FROM OR ARISING OUT OF ANY USE
29: * OF THIS SOFTWARE, INCLUDING WITHOUT LIMITATION, ANY DIRECT,
30: * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, PUNITIVE, OR CONSEQUENTIAL
31: * DAMAGES, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES, LOSS OF
32: * USE, DATA OR PROFITS, HOWEVER CAUSED AND UNDER ANY THEORY OF
33: * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
34: * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
35: * THE USE OF THIS SOFTWARE, EVEN IF PACKET DESIGN IS ADVISED OF
36: * THE POSSIBILITY OF SUCH DAMAGE.
37: *
38: * Author: Archie Cobbs <archie@freebsd.org>
39: */
40:
41: #include <sys/types.h>
42: #include <sys/param.h>
43: #include <netinet/in.h>
44:
45: #ifndef _KERNEL
46: #include <stdio.h>
47: #include <stdlib.h>
48: #include <stdarg.h>
49: #include <syslog.h>
50: #include <errno.h>
51: #include <assert.h>
52: #include <string.h>
53: #include <err.h>
54: #else
55: #include <sys/systm.h>
56: #include <sys/syslog.h>
57: #endif
58:
59: #include "structs/structs.h"
60: #include "structs/type/array.h"
61:
62: #include "util/ghash.h"
63: #include "util/typed_mem.h"
64:
65: #define MIN_BUCKETS 31
66: #define DEFAULT_MAX_LOAD 75 /* 75% full */
67: #define MIN_LOAD_FACTOR 20 /* 1/20 of current size */
68:
69: struct gent {
70: const void *item; /* this item */
71: struct gent *next; /* next item in bucket */
72: };
73:
74: struct ghash {
75: void *arg;
76: ghash_hash_t *hash;
77: ghash_equal_t *equal;
78: ghash_add_t *add;
79: ghash_del_t *del;
80: u_int maxload; /* maximum load factor in % */
81: u_int mods; /* modification counter */
82: u_int size; /* number of items in table */
83: u_int maxsize; /* when we need to increase */
84: u_int minsize; /* when we need to decrease */
85: u_int nbuckets; /* number of buckets in table */
86: u_int iter_count; /* number outstanding iter's */
87: struct gent **buckets; /* hash bucket array */
88: struct { /* typed memory alloc types */
89: const char *g;
90: char g_buf[TYPED_MEM_TYPELEN];
91: const char *gent;
92: char gent_buf[TYPED_MEM_TYPELEN];
93: const char *iter;
94: char iter_buf[TYPED_MEM_TYPELEN];
95: const char *buckets;
96: char buckets_buf[TYPED_MEM_TYPELEN];
97: } mtype;
98: u_char locked;
99: };
100:
101: /*
102: * Internal functions
103: */
104:
105: static ghash_equal_t ghash_default_equal;
106: static ghash_hash_t ghash_default_hash;
107: static ghash_add_t ghash_default_add;
108: static ghash_del_t ghash_default_del;
109:
110: static void ghash_rehash(struct ghash *g, u_int new_nbuckets);
111:
112: /* Update maxsize and minsize after nbuckets changes */
113: #define UPDATE_SIZES(g) \
114: do { \
115: (g)->maxsize = ((g)->nbuckets * (g)->maxload) / 100; \
116: if ((g)->maxsize == 0) \
117: (g)->maxsize = 1; \
118: (g)->minsize = (g)->nbuckets / MIN_LOAD_FACTOR; \
119: } while (0)
120:
121: /*
122: * Create a new hash table.
123: */
124: struct ghash *
125: ghash_create(void *arg, u_int isize, u_int maxload, const char *mtype,
126: ghash_hash_t *hash, ghash_equal_t *equal, ghash_add_t *add,
127: ghash_del_t *del)
128: {
129: struct ghash *g;
130:
131: /* Apply defaults and sanity check */
132: if (isize < MIN_BUCKETS)
133: isize = MIN_BUCKETS;
134: if (maxload == 0)
135: maxload = DEFAULT_MAX_LOAD;
136:
137: /* Create new hash table object */
138: if ((g = MALLOC(mtype, sizeof(*g))) == NULL)
139: return (NULL);
140: memset(g, 0, sizeof(*g));
141: g->arg = arg;
142: g->hash = hash != NULL ? hash : ghash_default_hash;
143: g->equal = equal != NULL ? equal : ghash_default_equal;
144: g->add = add != NULL ? add : ghash_default_add;
145: g->del = del != NULL ? del: ghash_default_del;
146: g->nbuckets = isize;
147: g->maxload = maxload;
148: UPDATE_SIZES(g);
149:
150: /* Create memory subtypes */
151: if (mtype != NULL) {
152: snprintf(g->mtype.g_buf, sizeof(g->mtype.g_buf), "%s", mtype);
153: g->mtype.g = g->mtype.g_buf;
154: snprintf(g->mtype.gent_buf, sizeof(g->mtype.gent_buf),
155: "%s.gent", mtype);
156: g->mtype.gent = g->mtype.gent_buf;
157: snprintf(g->mtype.iter_buf, sizeof(g->mtype.iter_buf),
158: "%s.iter", mtype);
159: g->mtype.iter = g->mtype.iter_buf;
160: snprintf(g->mtype.buckets_buf, sizeof(g->mtype.buckets_buf),
161: "%s.buckets", mtype);
162: g->mtype.buckets = g->mtype.buckets_buf;
163: }
164:
165: /* Allocate initial bucket array */
166: if ((g->buckets = MALLOC(g->mtype.buckets,
167: g->nbuckets * sizeof(*g->buckets))) == NULL) {
168: FREE(g->mtype.g, g);
169: return (NULL);
170: }
171: memset(g->buckets, 0, g->nbuckets * sizeof(*g->buckets));
172:
173: /* Done */
174: return (g);
175: }
176:
177: /*
178: * Destroy a hash table.
179: */
180: void
181: ghash_destroy(struct ghash **gp)
182: {
183: struct ghash *const g = *gp;
184: u_int i;
185:
186: if (g == NULL)
187: return;
188: assert(!g->locked);
189: assert(g->iter_count == 0);
190: g->locked = 1;
191: for (i = 0; i < g->nbuckets; i++) {
192: while (g->buckets[i] != NULL) {
193: struct gent *const e = g->buckets[i];
194: const void *const item = e->item;
195:
196: g->buckets[i] = e->next;
197: FREE(g->mtype.gent, e);
198: g->size--;
199: (*g->del)(g, (void *)item);
200: }
201: }
202: FREE(g->mtype.buckets, g->buckets);
203: FREE(g->mtype.g, g);
204: *gp = NULL;
205: }
206:
207: /*
208: * Get the argument supplied to ghash_create().
209: */
210: void *
211: ghash_arg(struct ghash *g)
212: {
213: return (g->arg);
214: }
215:
216: /*
217: * Return number of items in the table.
218: */
219: u_int
220: ghash_size(struct ghash *g)
221: {
222: return (g->size);
223: }
224:
225: /*
226: * Get an item.
227: *
228: * Returns the item, or NULL if the item does not exist.
229: */
230: void *
231: ghash_get(struct ghash *g, const void *item)
232: {
233: struct gent *e;
234:
235: if (item == NULL)
236: return (NULL);
237: for (e = g->buckets[(*g->hash)(g, item) % g->nbuckets];
238: e != NULL; e = e->next) {
239: if (item == e->item || (*g->equal)(g, item, e->item))
240: return ((void *)e->item);
241: }
242: return (NULL);
243: }
244:
245: /*
246: * Put an item.
247: *
248: * Returns 0 if the item is new, 1 if it replaces an existing
249: * item, and -1 if there was an error.
250: */
251: int
252: ghash_put(struct ghash *g, const void *item)
253: {
254: struct gent **start;
255: struct gent *e;
256:
257: /* Sanity check */
258: if (item == NULL) {
259: errno = EINVAL;
260: return (-1);
261: }
262:
263: /* Lock hash table */
264: if (g->locked) {
265: errno = EBUSY;
266: return (-1);
267: }
268: g->locked = 1;
269:
270: /* Find item's bucket */
271: start = &g->buckets[(*g->hash)(g, item) % g->nbuckets];
272:
273: /* See if item already exists, and replace it if so */
274: for (e = *start; e != NULL; e = e->next) {
275: if ((*g->equal)(g, item, e->item)) {
276: (*g->del)(g, (void *)e->item);
277: e->item = item;
278: (*g->add)(g, (void *)e->item);
279: g->mods++;
280: g->locked = 0;
281: return (1);
282: }
283: }
284:
285: /* Expand table if necessary */
286: if (g->size + 1 > g->maxsize) {
287: ghash_rehash(g, (g->nbuckets * 2) - 1);
288: start = &g->buckets[(*g->hash)(g, item) % g->nbuckets];
289: }
290: g->mods++;
291:
292: /* Add new item */
293: if ((e = MALLOC(g->mtype.gent, sizeof(*e))) == NULL) {
294: g->locked = 0;
295: return (-1);
296: }
297: (*g->add)(g, (void *)item);
298: e->item = item;
299: e->next = *start;
300: *start = e;
301: g->size++;
302:
303: /* Unlock tree and return */
304: g->locked = 0;
305: return (0);
306: }
307:
308: /*
309: * Remove an item.
310: *
311: * Returns 1 if the item was found and removed, 0 if not found.
312: */
313: int
314: ghash_remove(struct ghash *g, const void *item)
315: {
316: struct gent **ep;
317: int found = 0;
318:
319: /* Sanity check */
320: if (item == NULL)
321: return (0);
322:
323: /* Lock hash table */
324: if (g->locked) {
325: errno = EBUSY;
326: return (-1);
327: }
328: g->locked = 1;
329:
330: /* Find item */
331: for (ep = &g->buckets[(*g->hash)(g, item) % g->nbuckets];
332: *ep != NULL; ep = &(*ep)->next) {
333: struct gent *const e = *ep;
334:
335: if ((*g->equal)(g, item, e->item)) {
336: const void *const oitem = e->item;
337:
338: *ep = e->next;
339: FREE(g->mtype.gent, e);
340: g->size--;
341: (*g->del)(g, (void *)oitem);
342: found = 1;
343: break;
344: }
345: }
346: if (!found) {
347: g->locked = 0;
348: return (0);
349: }
350: g->mods++;
351:
352: /* Shrink table if desired */
353: if (g->size < g->minsize && g->size > MIN_BUCKETS) {
354: u_int new_size;
355:
356: new_size = (g->size * g->maxload) / 200;
357: if (new_size > MIN_BUCKETS)
358: new_size = MIN_BUCKETS;
359: ghash_rehash(g, new_size);
360: }
361:
362: /* Unlock tree and return */
363: g->locked = 0;
364: return (1);
365: }
366:
367: /**********************************************************************
368: ITERATOR METHODS
369: **********************************************************************/
370:
371: struct ghash_iter {
372: struct ghash *g; /* hash table we're iterating over */
373: u_int mods; /* guard against changes to table */
374: u_int bucket; /* current bucket we're traversing */
375: u_int count; /* number of items returned so far */
376: struct gent **ep; /* points to previous rtn'd by next() */
377: };
378:
379: struct ghash_iter *
380: ghash_iter_create(struct ghash *g)
381: {
382: struct ghash_iter *iter;
383:
384: if (g == NULL) {
385: errno = EINVAL;
386: return (NULL);
387: }
388: if ((iter = MALLOC(g->mtype.iter, sizeof(*iter))) == NULL)
389: return (NULL);
390: memset(iter, 0, sizeof(*iter));
391: iter->g = g;
392: iter->mods = g->mods;
393: g->iter_count++;
394: return (iter);
395: }
396:
397: void
398: ghash_iter_destroy(struct ghash_iter **iterp)
399: {
400: struct ghash_iter *const iter = *iterp;
401:
402: if (iter == NULL)
403: return;
404: iter->g->iter_count--;
405: FREE(iter->g->mtype.iter, iter);
406: *iterp = NULL;
407: }
408:
409: int
410: ghash_iter_has_next(struct ghash_iter *iter)
411: {
412: struct ghash *const g = iter->g;
413:
414: if (iter->mods != g->mods)
415: return (1); /* force a call to next() */
416: return (iter->count < g->size);
417: }
418:
419: /*
420: * Return next element in an iteration.
421: */
422: void *
423: ghash_iter_next(struct ghash_iter *iter)
424: {
425: struct ghash *const g = iter->g;
426:
427: /* Sanity checks */
428: if (iter->mods != g->mods || iter->count >= g->size) {
429: errno = EINVAL;
430: return (NULL);
431: }
432:
433: /* Advance pointer to next element */
434: if (iter->count++ == 0)
435: iter->ep = &g->buckets[0]; /* initialize pointer */
436: else {
437: assert(*iter->ep != NULL);
438: iter->ep = &(*iter->ep)->next;
439: }
440: while (*iter->ep == NULL) {
441: iter->ep = &g->buckets[++iter->bucket];
442: assert(iter->bucket < g->nbuckets);
443: }
444:
445: /* Update item count and return next item */
446: return ((void *)(*iter->ep)->item);
447: }
448:
449: /*
450: * Remove previously returned element in an iteration.
451: */
452: int
453: ghash_iter_remove(struct ghash_iter *iter)
454: {
455: struct ghash *const g = iter->g;
456: const void *item;
457: struct gent *e;
458:
459: /* Sanity checks */
460: if (iter->count == 0 || iter->mods != g->mods) {
461: errno = EINVAL;
462: return (-1);
463: }
464:
465: /* Lock hash table */
466: if (g->locked) {
467: errno = EBUSY;
468: return (-1);
469: }
470: g->locked = 1;
471:
472: /* Remove element */
473: e = *iter->ep;
474: item = e->item;
475: *iter->ep = e->next;
476: FREE(g->mtype.gent, e);
477: g->size--;
478: iter->count--;
479: g->mods++;
480: iter->mods++;
481: (*g->del)(g, (void *)item);
482:
483: /* Shrink table if desired */
484: if (g->size < g->minsize && g->size > MIN_BUCKETS) {
485: u_int new_size;
486:
487: new_size = (g->size * g->maxload) / 200;
488: if (new_size > MIN_BUCKETS)
489: new_size = MIN_BUCKETS;
490: ghash_rehash(g, new_size);
491: }
492: g->locked = 0;
493: return (0);
494: }
495:
496: /*
497: * Get an array of hash table contents, optionally sorted.
498: */
499: int
500: ghash_dump(struct ghash *g, void ***listp, const char *mtype)
501: {
502: struct gent *e;
503: void **list;
504: u_int num;
505: u_int i;
506:
507: /* Get items in a list */
508: if ((list = MALLOC(mtype, g->size * sizeof(*list))) == NULL)
509: return (-1);
510: for (num = i = 0; i < g->nbuckets; i++) {
511: for (e = g->buckets[i]; e != NULL; e = e->next)
512: list[num++] = (void *)e->item;
513: }
514: assert(num == g->size);
515:
516: /* Done */
517: *listp = list;
518: return (num);
519: }
520:
521: /*
522: * Start a hash table walk.
523: */
524: void
525: ghash_walk_init(struct ghash *g, struct ghash_walk *walk)
526: {
527: memset(walk, 0, sizeof(*walk));
528: walk->mods = g->mods;
529: }
530:
531: /*
532: * Get the next item in the hash table walk.
533: */
534: void *
535: ghash_walk_next(struct ghash *g, struct ghash_walk *walk)
536: {
537: void *item;
538:
539: /* Check for modifications */
540: if (g->mods != walk->mods) {
541: errno = EINVAL;
542: return (NULL);
543: }
544:
545: /* Go to next bucket if needed */
546: if (walk->e == NULL) {
547: while (walk->bucket < g->nbuckets
548: && g->buckets[walk->bucket] == NULL)
549: walk->bucket++;
550: if (walk->bucket == g->nbuckets) {
551: errno = ENOENT;
552: return (NULL);
553: }
554: walk->e = g->buckets[walk->bucket++];
555: }
556:
557: /* Get item to return */
558: item = (void *)walk->e->item;
559:
560: /* Point at next item for next time */
561: walk->e = walk->e->next;
562:
563: /* Return item */
564: return (item);
565: }
566:
567: /**********************************************************************
568: DEFAULT CALLBACKS
569: **********************************************************************/
570:
571: static int
572: ghash_default_equal(struct ghash *g, const void *item1, const void *item2)
573: {
574: return (item1 == item2);
575: }
576:
577: static u_int32_t
578: ghash_default_hash(struct ghash *g, const void *item)
579: {
580: return ((u_int32_t)(u_long)item);
581: }
582:
583: static void
584: ghash_default_add(struct ghash *g, void *item)
585: {
586: return;
587: }
588:
589: static void
590: ghash_default_del(struct ghash *g, void *item)
591: {
592: return;
593: }
594:
595: /**********************************************************************
596: HELPER METHODS
597: **********************************************************************/
598:
599: /*
600: * Resize the hash bucket array.
601: */
602: static void
603: ghash_rehash(struct ghash *g, u_int new_nbuckets)
604: {
605: struct gent **new_buckets;
606: u_int i;
607:
608: /* Get new bucket array */
609: assert(new_nbuckets > 0);
610: if ((new_buckets = MALLOC(g->mtype.buckets,
611: new_nbuckets * sizeof(*new_buckets))) == NULL)
612: return; /* can't do it */
613: memset(new_buckets, 0, new_nbuckets * sizeof(*new_buckets));
614:
615: /* Move all entries over to new array */
616: for (i = 0; i < g->nbuckets; i++) {
617: while (g->buckets[i] != NULL) {
618: struct gent *const e = g->buckets[i];
619: const u_int new_bucket
620: = (*g->hash)(g, e->item) % new_nbuckets;
621:
622: g->buckets[i] = e->next;
623: e->next = new_buckets[new_bucket];
624: new_buckets[new_bucket] = e;
625: }
626: }
627: g->nbuckets = new_nbuckets;
628: FREE(g->mtype.buckets, g->buckets);
629: g->buckets = new_buckets;
630:
631: /* Update new upper and lower size limits */
632: UPDATE_SIZES(g);
633: }
634:
635: #ifdef GHASH_TEST
636:
637: /**********************************************************************
638: TEST ROUTINE
639: **********************************************************************/
640:
641: #define MAX_ARGS 32
642: #define WS " \t\r\n\v\f"
643:
644: static ghash_equal_t ghash_test_equal;
645: static ghash_hash_t ghash_test_hash;
646: static ghash_add_t ghash_test_add;
647: static ghash_del_t ghash_test_del;
648:
649: static int ghash_test_sort(const void *p1, const void *p2);
650:
651: int
652: main(int ac, char **av)
653: {
654: char buf[1024];
655: struct ghash *g;
656:
657: if ((g = ghash_create(NULL, 3, 0, "ghash", ghash_test_hash,
658: ghash_test_equal, ghash_test_add, ghash_test_del)) == NULL)
659: err(1, "ghash_create");
660:
661: while (1) {
662: char *args[MAX_ARGS];
663: char *tokctx;
664: char *s;
665:
666: /* Prompt */
667: printf("Current size is %d items (%d buckets)\n",
668: ghash_size(g), g->nbuckets);
669: getline:
670: printf("> ");
671: if (fgets(buf, sizeof(buf), stdin) == NULL)
672: break;
673:
674: /* Parse line */
675: for (ac = 0, s = strtok_r(buf, WS, &tokctx);
676: ac < MAX_ARGS && s != NULL;
677: ac++, s = strtok_r(NULL, WS, &tokctx)) {
678: if ((args[ac] = STRDUP(NULL, s)) == NULL)
679: err(1, "strdup");
680: }
681: if (ac == 0)
682: goto getline;
683:
684: /* Do cmd */
685: if (strcmp(args[0], "put") == 0) {
686: if (ac != 2)
687: err(1, "usage: put <token>");
688: printf("Putting \"%s\"...\n", args[1]);
689: if (ghash_put(g, args[1]) == -1)
690: err(1, "ghash_put");
691: printf("Done\n");
692: } else if (strcmp(args[0], "get") == 0) {
693: const char *s;
694:
695: if (ac != 2)
696: err(1, "usage: get <token>");
697: if ((s = ghash_get(g, args[1])) == NULL)
698: printf("\"%s\" was not found\n", args[1]);
699: else
700: printf("Found \"%s\"\n", s);
701: } else if (strcmp(args[0], "del") == 0) {
702: int rtn;
703:
704: if (ac != 2)
705: err(1, "usage: del <token>");
706: if ((rtn = ghash_remove(g, args[1])) == -1)
707: err(1, "ghash_remove");
708: if (rtn)
709: printf("Removed \"%s\"\n", args[1]);
710: else
711: printf("\"%s\" was not found\n", args[1]);
712: } else if (strcmp(args[0], "dump") == 0) {
713: struct ghash_iter *iter;
714:
715: if ((iter = ghash_iter_create(g)) == NULL)
716: err(1, "ghash_iter_create");
717: printf("Iterating contents...\n");
718: while (ghash_iter_has_next(iter)) {
719: const char *s = ghash_iter_next(iter);
720:
721: if (s == NULL)
722: err(1, "ghash_iter_next");
723: printf("\t\"%s\"\n", s);
724: }
725: ghash_iter_destroy(&iter);
726: printf("Done\n");
727: } else if (strcmp(args[0], "sort") == 0) {
728: void **list;
729: int i, num;
730:
731: if ((num = ghash_dump(g, &list, TYPED_MEM_TEMP)) == -1)
732: err(1, "ghash_get_sorted");
733: printf("Sorting contents...\n");
734: qsort(list, num, sizeof(*list), ghash_test_sort);
735: for (i = 0; i < num; i++)
736: printf("\t\"%s\"\n", (const char *)list[i]);
737: FREE(TYPED_MEM_TEMP, list);
738: printf("Done\n");
739: } else {
740: printf("Commands:\n"
741: "\tget <token>\n"
742: "\tput <token>\n"
743: "\tdel <token>\n"
744: "\tdump\n"
745: "\tsort\n");
746: }
747: }
748: if (ferror(stdin))
749: err(1, "stdin");
750: printf("\n");
751: ghash_destroy(&g);
752: typed_mem_dump(stdout);
753: return (0);
754: }
755:
756: static int
757: ghash_test_equal(struct ghash *g, const void *item1, const void *item2)
758: {
759: return (strcmp((const char *)item1, (const char *)item2) == 0);
760: }
761:
762: static int
763: ghash_test_sort(const void *p1, const void *p2)
764: {
765: const char *s1 = *((const char **)p1);
766: const char *s2 = *((const char **)p2);
767:
768: return (strcmp(s1, s2));
769: }
770:
771: static u_int32_t
772: ghash_test_hash(struct ghash *g, const void *item)
773: {
774: const char *s = item;
775: u_int32_t hash;
776:
777: for (hash = 0; *s != '\0'; s++)
778: hash = (hash * 31) + (u_char)*s;
779: return (hash);
780: }
781:
782: static void
783: ghash_test_add(struct ghash *g, void *item)
784: {
785: printf("-> adding \"%s\"\n", (char *)item);
786: }
787:
788: static void
789: ghash_test_del(struct ghash *g, void *item)
790: {
791: printf("-> deleting \"%s\"\n", (char *)item);
792: }
793:
794: #endif /* GHASH_TEST */