From 3785c95a52d8dc551e444f2ab651da41cb5a3429 Mon Sep 17 00:00:00 2001 From: Joerg Sonnenberger Date: Thu, 26 Feb 2004 14:06:13 +0000 Subject: [PATCH] Remove unused and undocumented strhash files. Suggested by Chris Pressey --- include/Makefile | 4 +- include/strhash.h | 65 ------ lib/libc/stdlib/Makefile.inc | 4 +- lib/libc/stdlib/strhash.c | 407 ---------------------------------- lib/libcr/stdlib/Makefile.inc | 4 +- lib/libcr/stdlib/strhash.c | 407 ---------------------------------- 6 files changed, 6 insertions(+), 885 deletions(-) delete mode 100644 include/strhash.h delete mode 100644 lib/libc/stdlib/strhash.c delete mode 100644 lib/libcr/stdlib/strhash.c diff --git a/include/Makefile b/include/Makefile index 18acc909f3..ad3dc271ea 100644 --- a/include/Makefile +++ b/include/Makefile @@ -1,6 +1,6 @@ # @(#)Makefile 8.2 (Berkeley) 1/4/94 # $FreeBSD: src/include/Makefile,v 1.109.2.27 2003/01/24 05:12:29 sam Exp $ -# $DragonFly: src/include/Makefile,v 1.15 2004/02/03 05:51:51 dillon Exp $ +# $DragonFly: src/include/Makefile,v 1.16 2004/02/26 14:06:13 joerg Exp $ # # Doing a make install builds /usr/include # @@ -12,7 +12,7 @@ SUBDIR= arpa protocols rpc rpcsvc INCS= a.out.h ar.h assert.h bitstring.h complex.h cpio.h ctype.h db.h \ dirent.h disktab.h \ dlfcn.h elf.h elf-hints.h err.h fnmatch.h fstab.h \ - fts.h getopt.h glob.h grp.h strhash.h histedit.h ieeefp.h ifaddrs.h \ + fts.h getopt.h glob.h grp.h histedit.h ieeefp.h ifaddrs.h \ iso646.h inttypes.h \ langinfo.h libgen.h limits.h link.h locale.h malloc.h memory.h \ mpool.h ndbm.h netdb.h nl_types.h nlist.h objformat.h \ diff --git a/include/strhash.h b/include/strhash.h deleted file mode 100644 index fbca58a091..0000000000 --- a/include/strhash.h +++ /dev/null @@ -1,65 +0,0 @@ -#ifndef _STRHASH_H_INCLUDE -#define _STRHASH_H_INCLUDE - -/* $FreeBSD: src/include/strhash.h,v 1.3 1999/08/28 04:59:30 peter Exp $ */ -/* $DragonFly: src/include/Attic/strhash.h,v 1.2 2003/06/17 04:25:56 dillon Exp $ */ - -/* - * - * 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 167f98b537..7aafbd0bcb 100644 --- a/lib/libc/stdlib/Makefile.inc +++ b/lib/libc/stdlib/Makefile.inc @@ -1,6 +1,6 @@ # from @(#)Makefile.inc 8.3 (Berkeley) 2/4/95 # $FreeBSD: src/lib/libc/stdlib/Makefile.inc,v 1.19.2.4 2001/10/02 11:15:38 ru Exp $ -# $DragonFly: src/lib/libc/stdlib/Makefile.inc,v 1.5 2004/02/17 17:04:57 joerg Exp $ +# $DragonFly: src/lib/libc/stdlib/Makefile.inc,v 1.6 2004/02/26 14:06:13 joerg Exp $ # machine-independent stdlib sources .PATH: ${.CURDIR}/../libc/${MACHINE_ARCH}/stdlib ${.CURDIR}/../libc/stdlib @@ -8,7 +8,7 @@ MISRCS+=abort.c abs.c atexit.c atof.c atoi.c atol.c bsearch.c calloc.c div.c \ exit.c getenv.c getopt.c getopt_long.c getsubopt.c hcreate.c heapsort.c \ labs.c ldiv.c malloc.c merge.c putenv.c qsort.c radixsort.c rand.c \ - random.c reallocf.c realpath.c setenv.c strhash.c strtol.c strtoll.c \ + random.c reallocf.c realpath.c setenv.c strtol.c strtoll.c \ strtoq.c strtoul.c strtoull.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 54847a6064..0000000000 --- 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. - * - * $FreeBSD: src/lib/libc/stdlib/strhash.c,v 1.8 1999/09/05 17:42:45 peter Exp $ - * $DragonFly: src/lib/libc/stdlib/Attic/strhash.c,v 1.3 2003/09/06 08:10:46 asmodai Exp $ - */ - -/* - * 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 -#include -#include -#include -#include - -#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; -} diff --git a/lib/libcr/stdlib/Makefile.inc b/lib/libcr/stdlib/Makefile.inc index 4798f86f9c..b58f039a83 100644 --- a/lib/libcr/stdlib/Makefile.inc +++ b/lib/libcr/stdlib/Makefile.inc @@ -1,6 +1,6 @@ # from @(#)Makefile.inc 8.3 (Berkeley) 2/4/95 # $FreeBSD: src/lib/libc/stdlib/Makefile.inc,v 1.19.2.4 2001/10/02 11:15:38 ru Exp $ -# $DragonFly: src/lib/libcr/stdlib/Attic/Makefile.inc,v 1.4 2004/01/31 13:38:48 joerg Exp $ +# $DragonFly: src/lib/libcr/stdlib/Attic/Makefile.inc,v 1.5 2004/02/26 14:06:13 joerg Exp $ # machine-independent stdlib sources .PATH: ${.CURDIR}/../libcr/${MACHINE_ARCH}/stdlib ${.CURDIR}/../libcr/stdlib @@ -8,7 +8,7 @@ MISRCS+=abort.c abs.c atexit.c atof.c atoi.c atol.c bsearch.c calloc.c div.c \ exit.c getenv.c getopt.c getopt_long.c getsubopt.c hcreate.c \ heapsort.c labs.c ldiv.c malloc.c merge.c putenv.c qsort.c radixsort.c \ - rand.c random.c reallocf.c realpath.c setenv.c strhash.c strtol.c \ + rand.c random.c reallocf.c realpath.c setenv.c strtol.c \ strtoll.c strtoq.c strtoul.c strtoull.c strtouq.c system.c tdelete.c \ tfind.c tsearch.c twalk.c diff --git a/lib/libcr/stdlib/strhash.c b/lib/libcr/stdlib/strhash.c deleted file mode 100644 index 852767ee03..0000000000 --- a/lib/libcr/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. - * - * $FreeBSD: src/lib/libc/stdlib/strhash.c,v 1.8 1999/09/05 17:42:45 peter Exp $ - * $DragonFly: src/lib/libcr/stdlib/Attic/strhash.c,v 1.3 2003/12/08 13:56:35 eirikn Exp $ - */ - -/* - * 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 -#include -#include -#include -#include - -#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; -} -- 2.41.0