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 { 1.1.1.2 ! misho 70: void *item; /* this item */ 1.1 misho 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--; 1.1.1.2 ! misho 199: (*g->del)(g, item); 1.1 misho 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 * 1.1.1.2 ! misho 231: ghash_get(struct ghash *g, void *item) 1.1 misho 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 1.1.1.2 ! misho 252: ghash_put(struct ghash *g, void *item) 1.1 misho 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)) { 1.1.1.2 ! misho 336: void *const oitem = e->item; 1.1 misho 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; 1.1.1.2 ! misho 456: void *item; 1.1 misho 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: { 1.1.1.2 ! misho 574: (void)g; 1.1 misho 575: return (item1 == item2); 576: } 577: 578: static u_int32_t 579: ghash_default_hash(struct ghash *g, const void *item) 580: { 1.1.1.2 ! misho 581: (void)g; 1.1 misho 582: return ((u_int32_t)(u_long)item); 583: } 584: 585: static void 586: ghash_default_add(struct ghash *g, void *item) 587: { 1.1.1.2 ! misho 588: (void)g; ! 589: (void)item; 1.1 misho 590: return; 591: } 592: 593: static void 1.1.1.2 ! misho 594: ghash_default_del(struct ghash *g, const void *item) 1.1 misho 595: { 1.1.1.2 ! misho 596: (void)g; ! 597: (void)item; 1.1 misho 598: return; 599: } 600: 601: /********************************************************************** 602: HELPER METHODS 603: **********************************************************************/ 604: 605: /* 606: * Resize the hash bucket array. 607: */ 608: static void 609: ghash_rehash(struct ghash *g, u_int new_nbuckets) 610: { 611: struct gent **new_buckets; 612: u_int i; 613: 614: /* Get new bucket array */ 615: assert(new_nbuckets > 0); 616: if ((new_buckets = MALLOC(g->mtype.buckets, 617: new_nbuckets * sizeof(*new_buckets))) == NULL) 618: return; /* can't do it */ 619: memset(new_buckets, 0, new_nbuckets * sizeof(*new_buckets)); 620: 621: /* Move all entries over to new array */ 622: for (i = 0; i < g->nbuckets; i++) { 623: while (g->buckets[i] != NULL) { 624: struct gent *const e = g->buckets[i]; 625: const u_int new_bucket 626: = (*g->hash)(g, e->item) % new_nbuckets; 627: 628: g->buckets[i] = e->next; 629: e->next = new_buckets[new_bucket]; 630: new_buckets[new_bucket] = e; 631: } 632: } 633: g->nbuckets = new_nbuckets; 634: FREE(g->mtype.buckets, g->buckets); 635: g->buckets = new_buckets; 636: 637: /* Update new upper and lower size limits */ 638: UPDATE_SIZES(g); 639: } 640: 641: #ifdef GHASH_TEST 642: 643: /********************************************************************** 644: TEST ROUTINE 645: **********************************************************************/ 646: 647: #define MAX_ARGS 32 648: #define WS " \t\r\n\v\f" 649: 650: static ghash_equal_t ghash_test_equal; 651: static ghash_hash_t ghash_test_hash; 652: static ghash_add_t ghash_test_add; 653: static ghash_del_t ghash_test_del; 654: 655: static int ghash_test_sort(const void *p1, const void *p2); 656: 657: int 658: main(int ac, char **av) 659: { 660: char buf[1024]; 661: struct ghash *g; 662: 663: if ((g = ghash_create(NULL, 3, 0, "ghash", ghash_test_hash, 664: ghash_test_equal, ghash_test_add, ghash_test_del)) == NULL) 665: err(1, "ghash_create"); 666: 667: while (1) { 668: char *args[MAX_ARGS]; 669: char *tokctx; 670: char *s; 671: 672: /* Prompt */ 673: printf("Current size is %d items (%d buckets)\n", 674: ghash_size(g), g->nbuckets); 675: getline: 676: printf("> "); 677: if (fgets(buf, sizeof(buf), stdin) == NULL) 678: break; 679: 680: /* Parse line */ 681: for (ac = 0, s = strtok_r(buf, WS, &tokctx); 682: ac < MAX_ARGS && s != NULL; 683: ac++, s = strtok_r(NULL, WS, &tokctx)) { 684: if ((args[ac] = STRDUP(NULL, s)) == NULL) 685: err(1, "strdup"); 686: } 687: if (ac == 0) 688: goto getline; 689: 690: /* Do cmd */ 691: if (strcmp(args[0], "put") == 0) { 692: if (ac != 2) 693: err(1, "usage: put <token>"); 694: printf("Putting \"%s\"...\n", args[1]); 695: if (ghash_put(g, args[1]) == -1) 696: err(1, "ghash_put"); 697: printf("Done\n"); 698: } else if (strcmp(args[0], "get") == 0) { 699: const char *s; 700: 701: if (ac != 2) 702: err(1, "usage: get <token>"); 703: if ((s = ghash_get(g, args[1])) == NULL) 704: printf("\"%s\" was not found\n", args[1]); 705: else 706: printf("Found \"%s\"\n", s); 707: } else if (strcmp(args[0], "del") == 0) { 708: int rtn; 709: 710: if (ac != 2) 711: err(1, "usage: del <token>"); 712: if ((rtn = ghash_remove(g, args[1])) == -1) 713: err(1, "ghash_remove"); 714: if (rtn) 715: printf("Removed \"%s\"\n", args[1]); 716: else 717: printf("\"%s\" was not found\n", args[1]); 718: } else if (strcmp(args[0], "dump") == 0) { 719: struct ghash_iter *iter; 720: 721: if ((iter = ghash_iter_create(g)) == NULL) 722: err(1, "ghash_iter_create"); 723: printf("Iterating contents...\n"); 724: while (ghash_iter_has_next(iter)) { 725: const char *s = ghash_iter_next(iter); 726: 727: if (s == NULL) 728: err(1, "ghash_iter_next"); 729: printf("\t\"%s\"\n", s); 730: } 731: ghash_iter_destroy(&iter); 732: printf("Done\n"); 733: } else if (strcmp(args[0], "sort") == 0) { 734: void **list; 735: int i, num; 736: 737: if ((num = ghash_dump(g, &list, TYPED_MEM_TEMP)) == -1) 738: err(1, "ghash_get_sorted"); 739: printf("Sorting contents...\n"); 740: qsort(list, num, sizeof(*list), ghash_test_sort); 741: for (i = 0; i < num; i++) 742: printf("\t\"%s\"\n", (const char *)list[i]); 743: FREE(TYPED_MEM_TEMP, list); 744: printf("Done\n"); 745: } else { 746: printf("Commands:\n" 747: "\tget <token>\n" 748: "\tput <token>\n" 749: "\tdel <token>\n" 750: "\tdump\n" 751: "\tsort\n"); 752: } 753: } 754: if (ferror(stdin)) 755: err(1, "stdin"); 756: printf("\n"); 757: ghash_destroy(&g); 758: typed_mem_dump(stdout); 759: return (0); 760: } 761: 762: static int 763: ghash_test_equal(struct ghash *g, const void *item1, const void *item2) 764: { 765: return (strcmp((const char *)item1, (const char *)item2) == 0); 766: } 767: 768: static int 769: ghash_test_sort(const void *p1, const void *p2) 770: { 771: const char *s1 = *((const char **)p1); 772: const char *s2 = *((const char **)p2); 773: 774: return (strcmp(s1, s2)); 775: } 776: 777: static u_int32_t 778: ghash_test_hash(struct ghash *g, const void *item) 779: { 780: const char *s = item; 781: u_int32_t hash; 782: 783: for (hash = 0; *s != '\0'; s++) 784: hash = (hash * 31) + (u_char)*s; 785: return (hash); 786: } 787: 788: static void 789: ghash_test_add(struct ghash *g, void *item) 790: { 791: printf("-> adding \"%s\"\n", (char *)item); 792: } 793: 794: static void 1.1.1.2 ! misho 795: ghash_test_del(struct ghash *g, const void *item) 1.1 misho 796: { 797: printf("-> deleting \"%s\"\n", (char *)item); 798: } 799: 800: #endif /* GHASH_TEST */