diff options
author | peter <peter@FreeBSD.org> | 2003-10-28 22:36:54 +0000 |
---|---|---|
committer | peter <peter@FreeBSD.org> | 2003-10-28 22:36:54 +0000 |
commit | ef64cc476e3caf97ef427ede66aff6b71cbd48b6 (patch) | |
tree | f4c66c1edef89ac64167daf322bf99e58ae6c07b | |
parent | 67cd4eebae31c6c9fada91f9e0cf697578cd17d3 (diff) | |
download | FreeBSD-src-ef64cc476e3caf97ef427ede66aff6b71cbd48b6.zip FreeBSD-src-ef64cc476e3caf97ef427ede66aff6b71cbd48b6.tar.gz |
Don peril sensitive (ie: bikeshed sensitive) sunglasses and quietly
send strhash(3) off to sleep with the fishes. Nothing in our tree uses it.
It has no documentation. It is nonstandard and in spite of the filename
strhash.c and strhash.h, it lives in application namespace by providing
compulsory global symbols hash_create()/hash_destroy()/hash_search()/
hash_traverse()/hash_purge()/hash_stats() regardless of whether you
#include <strhash.h> or not. If it turns out that there is a huge
application for this after all, I can repocopy it somewhere safer and
we can revive it elsewhere. But please, not in libc!
-rw-r--r-- | include/strhash.h | 64 | ||||
-rw-r--r-- | lib/libc/stdlib/Makefile.inc | 2 | ||||
-rw-r--r-- | lib/libc/stdlib/strhash.c | 407 |
3 files changed, 1 insertions, 472 deletions
diff --git a/include/strhash.h b/include/strhash.h deleted file mode 100644 index e0922f0..0000000 --- a/include/strhash.h +++ /dev/null @@ -1,64 +0,0 @@ -#ifndef _STRHASH_H_INCLUDE -#define _STRHASH_H_INCLUDE - -/* $FreeBSD$ */ - -/* - * - * Copyright 1990 - * Terry Jones & Jordan Hubbard - * - * PCS Computer Systeme, GmbH. - * Munich, West Germany - * - * - * All rights reserved. - * - * This is unsupported software and is subject to change without notice. - * the author makes no representations about the suitability of this software - * for any purpose. It is supplied "as is" without express or implied - * warranty. - * - * Permission to use, copy, modify, and distribute this software and its - * documentation for any purpose and without fee is hereby granted, provided - * that the above copyright notice appear in all copies and that both that - * copyright notice and this permission notice appear in supporting - * documentation, and that the name of the author not be used in - * advertising or publicity pertaining to distribution of the software - * without specific, written prior permission. - * - */ - -/* - * This is the definition file for hash.c. The plunderer from down-under - * did the code, I just helped define the spec. That's why his name gets - * to go first. - */ - -#define HASH_SZ 97 - -typedef struct _node { - char *key; - void *data; - struct _node *next; -} hash_node; - -typedef struct { - int size; - hash_node **buckets; -} hash_table; - -hash_table *hash_create(int size); -void hash_destroy(hash_table *table, char *key, - void (*nukefunc)(char *k, void *d)); -void *hash_search(hash_table *table, char *key, void *datum, - void (*replace_func)(void *d)); -void hash_traverse(hash_table *table, - int (*func)(char *k, void *d, void *arg), void *arg); -void hash_purge(hash_table *table, void (*purge_func)(char *k, void *d)); - -#ifdef HASH_STATS -extern void hash_stats(); -#endif - -#endif /* _STRHASH_H_INCLUDE */ diff --git a/lib/libc/stdlib/Makefile.inc b/lib/libc/stdlib/Makefile.inc index 3292657..c85c2f9 100644 --- a/lib/libc/stdlib/Makefile.inc +++ b/lib/libc/stdlib/Makefile.inc @@ -9,7 +9,7 @@ MISRCS+=_Exit.c abort.c abs.c atexit.c atof.c atoi.c atol.c atoll.c \ getsubopt.c grantpt.c hcreate.c heapsort.c imaxabs.c imaxdiv.c \ insque.c labs.c ldiv.c llabs.c lldiv.c lsearch.c malloc.c merge.c \ putenv.c qsort.c qsort_r.c radixsort.c rand.c random.c reallocf.c \ - realpath.c remque.c setenv.c strfmon.c strhash.c strtoimax.c \ + realpath.c remque.c setenv.c strfmon.c strtoimax.c \ strtol.c strtoll.c strtoq.c strtoul.c strtoull.c strtoumax.c strtouq.c \ system.c tdelete.c tfind.c tsearch.c twalk.c diff --git a/lib/libc/stdlib/strhash.c b/lib/libc/stdlib/strhash.c deleted file mode 100644 index ab9d756..0000000 --- a/lib/libc/stdlib/strhash.c +++ /dev/null @@ -1,407 +0,0 @@ -/* - * - * Copyright 1990 - * Terry Jones & Jordan Hubbard - * - * PCS Computer Systeme, GmbH. - * Munich, West Germany - * - * - * All rights reserved. - * - * This is unsupported software and is subject to change without notice. - * the author makes no representations about the suitability of this software - * for any purpose. It is supplied "as is" without express or implied - * warranty. - * - * Permission to use, copy, modify, and distribute this software and its - * documentation for any purpose and without fee is hereby granted, provided - * that the above copyright notice appear in all copies and that both that - * copyright notice and this permission notice appear in supporting - * documentation, and that the name of the author not be used in - * advertising or publicity pertaining to distribution of the software - * without specific, written prior permission. - * - */ - -/* - * This is a fairly simple open addressing hash scheme. - * Terry did all the code, I just did the spec. - * Thanks again, you crazy Aussie.. - * - */ - -/* - * $Log: strhash.c,v $ - * Revision 2.0 90/03/26 01:44:26 jkh - * pre-beta check-in - * - * Revision 1.8 90/03/09 19:22:35 jkh - * Fixed bogus comment. - * - * Revision 1.7 90/03/09 19:01:08 jkh - * Added comments, GPL. - * - * Revision 1.6 90/03/08 17:55:58 terry - * Rearranged hash_purge to be a tiny bit more efficient. - * Added verbose option to hash_stats. - * - * Revision 1.5 90/03/08 17:19:54 terry - * Added hash_purge. Added arg to hash_traverse. Changed all - * void * to Generic. - * - * Revision 1.4 90/03/08 12:02:35 terry - * Fixed problems with allocation that I screwed up last night. - * Changed bucket lists to be singly linked. Thanks to JKH, my hero. - * - * Revision 1.3 90/03/07 21:33:33 terry - * Cleaned up a few decls to keep gcc -Wall quiet. - * - * Revision 1.2 90/03/07 21:14:53 terry - * Comments. Added HASH_STATS define. Removed hash_find() - * and new_node(). - * - * Revision 1.1 90/03/07 20:49:45 terry - * Initial revision - * - * - */ - -#include <sys/cdefs.h> -__FBSDID("$FreeBSD$"); - -#include <stdio.h> -#include <stdlib.h> -#include <string.h> -#include <sys/types.h> -#include <strhash.h> - -#define HASH_NULL (hash_table *)0 -#define NODE_NULL (hash_node *)0 -#define GENERIC_NULL (void *)0 - -#define HASH_SZ 97 - - -static int _hash(int size, char *key); -static hash_node *list_find(caddr_t key, hash_node *head); - - -/* - * hash_create() - * - * Malloc room for a new hash table and then room for its - * bucket pointers. Then set all the buckets to - * point to 0. Return the address of the new table. - */ -hash_table * -hash_create(int size) -{ - int i; - hash_table *new = (hash_table *)malloc(sizeof(hash_table)); - - if (!new || size < 0){ - return HASH_NULL; - } - - if (size == 0){ - size = HASH_SZ; - } - - if (!(new->buckets = (hash_node **)malloc(size * sizeof(hash_node *)))){ - return HASH_NULL; - } - - for (i = 0; i < size; i++){ - new->buckets[i] = NODE_NULL; - } - new->size = size; - - return new; -} - - -/* - * list_find() - * - * Find the key in the linked list pointed to by head. - */ -static hash_node * -list_find(caddr_t key, hash_node *head) -{ - while (head){ - if (!strcmp(head->key, key)){ - return head; - } - head = head->next; - } - return NODE_NULL; -} - - -/* - * _hash() - * - * Compute the hash value for the given key. - */ -static int -_hash(int size, char *key) -{ - unsigned int h = 0x0; - - while (*key){ - h = (h << 1) ^ (h ^ (unsigned char) *key++); - } - - h %= size; - return h; -} - -/* - * hash_destroy() - * - * Find the key and (if it's there) remove it entirely. - * The function (*nukefunc)() is in charge of disposing - * of the storage help by the data associated with the node. - */ -void -hash_destroy(hash_table *table, char *key, void (*nukefunc)()) -{ - int bucket = _hash(table->size, key); - hash_node *found = table->buckets[bucket]; - hash_node *to_free = NODE_NULL; - - if (!found) { - return; - } - - if (!strcmp(found->key, key)) { - /* - * It was the head of the list. - */ - table->buckets[bucket] = found->next; - to_free = found; - } - else { - /* - * Walk the list, looking one ahead. - */ - while (found->next) { - if (!strcmp(found->next->key, key)) { - to_free = found->next; - found->next = found->next->next; - break; - } - found = found->next; - } - - if (!to_free){ - return; - } - } - - if (nukefunc) - (*nukefunc)(to_free->key, to_free->data); - free(to_free); - return; -} - - -/* - * hash_search() - * - * Search the table for the given key. Then: - * - * 1) If you find it and there is no replacement function, just - * return what you found. (This is a simple search). - * 2) If you find it and there is a replacement function, run - * the function on the data you found, and replace the old - * data with whatever is passed in datum. Return 0. - * 3) If you don't find it and there is some datum, insert a - * new item into the table. Insertions go at the front of - * the bucket. Return 0. - * 4) Otherwise just return 0. - * - */ -void * -hash_search(hash_table *table, caddr_t key, void *datum, - void (*replace_func)()) -{ - int bucket = _hash(table->size, key); - hash_node *found = list_find(key, table->buckets[bucket]); - - if (found){ - if (!replace_func){ - return found->data; - } - else{ - (*replace_func)(found->data); - found->data = datum; - } - } - else{ - if (datum){ - - static int assign_key(); - - hash_node *new = (hash_node *)malloc(sizeof(hash_node)); - - if (!new || !assign_key(key, new)){ - return GENERIC_NULL; - } - new->data = datum; - new->next = table->buckets[bucket]; - table->buckets[bucket] = new; - return new; - } - } - return GENERIC_NULL; -} - - -/* - * assign_key() - * - * Set the key value of a node to be 'key'. Get some space from - * malloc and copy it in etc. Return 1 if all is well, 0 otherwise. - */ -static int -assign_key(char *key, hash_node *node) -{ - if (!node || !key){ - return 0; - } - - if (!(node->key = (char *)malloc(strlen(key) + 1))){ - return 0; - } - - node->key[0] = '\0'; - strcat(node->key, key); - return 1; -} - -/* - * hash_traverse() - * - * Traverse the hash table and run the function func on the - * data found at each node and the argument we're passed for it. - */ -void -hash_traverse(hash_table *table, int (*func)(), void *arg) -{ - int i; - int size = table->size; - - if (!func) - return; - - for (i = 0; i < size; i++) { - hash_node *n = table->buckets[i]; - while (n) { - if ((*func)(n->key, n->data, arg) == 0) - return; - n = n->next; - } - } - return; -} - -/* - * hash_purge() - * - * Run through the entire hash table. Call purge_func - * on the data found at each node, and then free the node. - * Set all the bucket pointers to 0. - */ -void -hash_purge(hash_table *table, void (*purge_func)(char *p1, void *p2)) -{ - int i; - int size = table->size; - - for (i = 0; i < size; i++) { - hash_node *n = table->buckets[i]; - if (n) { - do { - hash_node *to_free = n; - if (purge_func) { - (*purge_func)(n->key, n->data); - } - n = n->next; - free(to_free); - } while (n); - table->buckets[i] = NODE_NULL; - } - } -} - -#undef min -#define min(a, b) (a) < (b) ? (a) : (b) - -/* - * hash_stats() - * - * Print statistics about the current table allocation to stdout. - */ -void -hash_stats(hash_table *table, int verbose) -{ - int i; - int total_elements = 0; - int non_empty_buckets = 0; - int max_count = 0; - int max_repeats = 0; - int *counts; - int size = table->size; - - if (!(counts = (int *)malloc(size * sizeof(int)))){ - fprintf(stderr, "malloc returns 0\n"); - exit(1); - } - - for (i = 0; i < size; i++){ - int x = 0; - hash_node *n = table->buckets[i]; - counts[i] = 0; - while (n){ - if (!x){ - x = 1; - non_empty_buckets++; - if (verbose){ - printf("bucket %2d: ", i); - } - } - if (verbose){ - printf(" %s", n->key); - } - counts[i]++; - n = n->next; - } - - total_elements += counts[i]; - if (counts[i] > max_count){ - max_count = counts[i]; - max_repeats = 1; - } - else if (counts[i] == max_count){ - max_repeats++; - } - - if (counts[i] && verbose){ - printf(" (%d)\n", counts[i]); - } - } - - printf("\n"); - printf("%d element%s in storage.\n", total_elements, total_elements == 1 ? "" : "s"); - - if (total_elements){ - printf("%d of %d (%.2f%%) buckets are in use\n", non_empty_buckets, size, - (double)100 * (double)non_empty_buckets / (double)(size)); - printf("the maximum number of elements in a bucket is %d (%d times)\n", max_count, max_repeats); - printf("average per bucket is %f\n", (double)total_elements / (double)non_empty_buckets); - printf("optimal would be %f\n", (double)total_elements / (double)(min(size, total_elements))); - } - return; -} |