Annotation of embedaddon/libpdel/util/ghash.c, revision 1.1
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 */
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[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 / libpdel / util