[thirdparty/squid.git] / lib / hash.c


/*
 * $Id$
 *
 * DEBUG: section 00    Hash Tables
 * AUTHOR: Harvest Derived
 *
 * SQUID Web Proxy Cache          http://www.squid-cache.org/
 * ----------------------------------------------------------
 *
 *  Squid is the result of efforts by numerous individuals from
 *  the Internet community; see the CONTRIBUTORS file for full
 *  details.   Many organizations have provided support for Squid's
 *  development; see the SPONSORS file for full details.  Squid is
 *  Copyrighted (C) 2001 by the Regents of the University of
 *  California; see the COPYRIGHT file for full details.  Squid
 *  incorporates software developed and/or copyrighted by other
 *  sources; see the CREDITS file for full details.
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA.
 *
 */

#include "squid.h"
#include "hash.h"
#include "profiler/Profiler.h"

#if HAVE_STDIO_H
#include <stdio.h>
#endif
#if HAVE_STDLIB_H
#include <stdlib.h>
#endif
#if HAVE_STRING_H
#include <string.h>
#endif
#if HAVE_UNISTD_H
#include <unistd.h>
#endif
#if HAVE_GNUMALLLOC_H
#include <gnumalloc.h>
#elif HAVE_MALLOC_H
#include <malloc.h>
#endif
#if HAVE_ASSERT_H
#include <assert.h>
#endif
#if HAVE_MATH_H
#include <math.h>
#endif

static void hash_next_bucket(hash_table * hid);

unsigned int
hash_string(const void *data, unsigned int size)
{
    const char *s = data;
    unsigned int n = 0;
    unsigned int j = 0;
    unsigned int i = 0;
    while (*s) {
        j++;
        n ^= 271 * (unsigned) *s++;
    }
    i = n ^ (j * 271);
    return i % size;
}

/* the following function(s) were adapted from
 *    usr/src/lib/libc/db/hash_func.c, 4.4 BSD lite */

/* Hash function from Chris Torek. */
unsigned int
hash4(const void *data, unsigned int size)
{
    const char *key = data;
    size_t loop;
    unsigned int h;
    size_t len;

#define HASH4a   h = (h << 5) - h + *key++;
#define HASH4b   h = (h << 5) + h + *key++;
#define HASH4 HASH4b

    h = 0;
    len = strlen(key);
    loop = len >> 3;
    switch (len & (8 - 1)) {
    case 0:
        break;
    case 7:
        HASH4;
        /* FALLTHROUGH */
    case 6:
        HASH4;
        /* FALLTHROUGH */
    case 5:
        HASH4;
        /* FALLTHROUGH */
    case 4:
        HASH4;
        /* FALLTHROUGH */
    case 3:
        HASH4;
        /* FALLTHROUGH */
    case 2:
        HASH4;
        /* FALLTHROUGH */
    case 1:
        HASH4;
    }
    while (loop--) {
        HASH4;
        HASH4;
        HASH4;
        HASH4;
        HASH4;
        HASH4;
        HASH4;
        HASH4;
    }
    return h % size;
}

/*
 *  hash_create - creates a new hash table, uses the cmp_func
 *  to compare keys.  Returns the identification for the hash table;
 *  otherwise returns a negative number on error.
 */
hash_table *
hash_create(HASHCMP * cmp_func, int hash_sz, HASHHASH * hash_func)
{
    hash_table *hid = xcalloc(1, sizeof(hash_table));
    if (!hash_sz)
        hid->size = (unsigned int) DEFAULT_HASH_SIZE;
    else
        hid->size = (unsigned int) hash_sz;
    /* allocate and null the buckets */
    hid->buckets = xcalloc(hid->size, sizeof(hash_link *));
    hid->cmp = cmp_func;
    hid->hash = hash_func;
    hid->next = NULL;
    hid->current_slot = 0;
    return hid;
}

/*
 *  hash_join - joins a hash_link under its key lnk->key
 *  into the hash table 'hid'.
 *
 *  It does not copy any data into the hash table, only links pointers.
 */
void
hash_join(hash_table * hid, hash_link * lnk)
{
    int i;
    i = hid->hash(lnk->key, hid->size);
    lnk->next = hid->buckets[i];
    hid->buckets[i] = lnk;
    hid->count++;
}

/*
 *  hash_lookup - locates the item under the key 'k' in the hash table
 *  'hid'.  Returns a pointer to the hash bucket on success; otherwise
 *  returns NULL.
 */
hash_link *
hash_lookup(hash_table * hid, const void *k)
{
    hash_link *walker;
    int b;
    PROF_start(hash_lookup);
    assert(k != NULL);
    b = hid->hash(k, hid->size);
    for (walker = hid->buckets[b]; walker != NULL; walker = walker->next) {
        if ((hid->cmp) (k, walker->key) == 0) {
            PROF_stop(hash_lookup);
            return (walker);
        }
        assert(walker != walker->next);
    }
    PROF_stop(hash_lookup);
    return NULL;
}

static void
hash_next_bucket(hash_table * hid)
{
    while (hid->next == NULL && ++hid->current_slot < hid->size)
        hid->next = hid->buckets[hid->current_slot];
}

/*
 *  hash_first - initializes the hash table for the hash_next()
 *  function.
 */
void
hash_first(hash_table * hid)
{
    assert(NULL == hid->next);
    hid->current_slot = 0;
    hid->next = hid->buckets[hid->current_slot];
    if (NULL == hid->next)
        hash_next_bucket(hid);
}

/*
 *  hash_next - returns the next item in the hash table 'hid'.
 *  Otherwise, returns NULL on error or end of list.
 *
 *  MUST call hash_first() before hash_next().
 */
hash_link *
hash_next(hash_table * hid)
{
    hash_link *this = hid->next;
    if (NULL == this)
        return NULL;
    hid->next = this->next;
    if (NULL == hid->next)
        hash_next_bucket(hid);
    return this;
}

/*
 *  hash_last - resets hash traversal state to NULL
 *
 */
void
hash_last(hash_table * hid)
{
    assert(hid != NULL);
    hid->next = NULL;
    hid->current_slot = 0;
}

/*
 *  hash_remove_link - deletes the given hash_link node from the
 *  hash table 'hid'.  Does not free the item, only removes it
 *  from the list.
 *
 *  An assertion is triggered if the hash_link is not found in the
 *  list.
 */
void
hash_remove_link(hash_table * hid, hash_link * hl)
{
    hash_link **P;
    int i;
    assert(hl != NULL);
    i = hid->hash(hl->key, hid->size);
    for (P = &hid->buckets[i]; *P; P = &(*P)->next) {
        if (*P != hl)
            continue;
        *P = hl->next;
        if (hid->next == hl) {
            hid->next = hl->next;
            if (NULL == hid->next)
                hash_next_bucket(hid);
        }
        hid->count--;
        return;
    }
    assert(0);
}

/*
 *  hash_get_bucket - returns the head item of the bucket
 *  in the hash table 'hid'. Otherwise, returns NULL on error.
 */
hash_link *
hash_get_bucket(hash_table * hid, unsigned int bucket)
{
    if (bucket >= hid->size)
        return NULL;
    return (hid->buckets[bucket]);
}

void
hashFreeItems(hash_table * hid, HASHFREE * free_func)
{
    hash_link *l;
    hash_link **list;
    int i = 0;
    int j;
    list = xcalloc(hid->count, sizeof(hash_link *));
    hash_first(hid);
    while ((l = hash_next(hid)) && i < hid->count) {
        *(list + i) = l;
        i++;
    }
    for (j = 0; j < i; j++)
        free_func(*(list + j));
    xfree(list);
}

void
hashFreeMemory(hash_table * hid)
{
    if (hid == NULL)
        return;
    if (hid->buckets)
        xfree(hid->buckets);
    xfree(hid);
}

static int hash_primes[] = {
    103,
    229,
    467,
    977,
    1979,
    4019,
    6037,
    7951,
    12149,
    16231,
    33493,
    65357
};

int
hashPrime(int n)
{
    int I = sizeof(hash_primes) / sizeof(int);
    int i;
    int best_prime = hash_primes[0];
    double min = fabs(log((double) n) - log((double) hash_primes[0]));
    double d;
    for (i = 0; i < I; i++) {
        d = fabs(log((double) n) - log((double) hash_primes[i]));
        if (d > min)
            continue;
        min = d;
        best_prime = hash_primes[i];
    }
    return best_prime;
}

/*
 * return the key of a hash_link as a const string
 */
const char *
hashKeyStr(hash_link * hl)
{
    return (const char *) hl->key;
}


#if USE_HASH_DRIVER
/*
 *  hash-driver - Run with a big file as stdin to insert each line into the
 *  hash table, then prints the whole hash table, then deletes a random item,
 *  and prints the table again...
 */
int
main(void)
{
    hash_table *hid;
    int i;
    LOCAL_ARRAY(char, buf, BUFSIZ);
    LOCAL_ARRAY(char, todelete, BUFSIZ);
    hash_link *walker = NULL;

    todelete[0] = '\0';
    printf("init\n");

    printf("creating hash table\n");
    if ((hid = hash_create((HASHCMP *) strcmp, 229, hash4)) < 0) {
        printf("hash_create error.\n");
        exit(1);
    }
    printf("done creating hash table: %d\n", hid);

    while (fgets(buf, BUFSIZ, stdin)) {
        buf[strlen(buf) - 1] = '\0';
        printf("Inserting '%s' for item %p to hash table: %d\n",
               buf, buf, hid);
        hash_insert(hid, xstrdup(buf), (void *) 0x12345678);
        if (random() % 17 == 0)
            strcpy(todelete, buf);
    }

    printf("walking hash table...\n");
    for (i = 0, walker = hash_first(hid); walker; walker = hash_next(hid)) {
        printf("item %5d: key: '%s' item: %p\n", i++, walker->key,
               walker->item);
    }
    printf("done walking hash table...\n");

    if (todelete[0]) {
        printf("deleting %s from %d\n", todelete, hid);
        if (hash_delete(hid, todelete))
            printf("hash_delete error\n");
    }
    printf("walking hash table...\n");
    for (i = 0, walker = hash_first(hid); walker; walker = hash_next(hid)) {
        printf("item %5d: key: '%s' item: %p\n", i++, walker->key,
               walker->item);
    }
    printf("done walking hash table...\n");


    printf("driver finished.\n");
    exit(0);
}
#endif
Commit	Line	Data
f52a7d75	1
f52a7d75	2	/*
262a0e14	3	* $Id$
f52a7d75	4	*
b510f3a1	5	* DEBUG: section 00 Hash Tables
f52a7d75	6	* AUTHOR: Harvest Derived
f52a7d75	7	*
2b6662ba	8	* SQUID Web Proxy Cache http://www.squid-cache.org/
f52a7d75	9	* ----------------------------------------------------------
f52a7d75	10	*
2b6662ba	11	* Squid is the result of efforts by numerous individuals from
	12	* the Internet community; see the CONTRIBUTORS file for full
	13	* details. Many organizations have provided support for Squid's
	14	* development; see the SPONSORS file for full details. Squid is
	15	* Copyrighted (C) 2001 by the Regents of the University of
	16	* California; see the COPYRIGHT file for full details. Squid
	17	* incorporates software developed and/or copyrighted by other
	18	* sources; see the CREDITS file for full details.
f52a7d75	19	*
	20	* This program is free software; you can redistribute it and/or modify
	21	* it under the terms of the GNU General Public License as published by
	22	* the Free Software Foundation; either version 2 of the License, or
	23	* (at your option) any later version.
26ac0430	24	*
f52a7d75	25	* This program is distributed in the hope that it will be useful,
	26	* but WITHOUT ANY WARRANTY; without even the implied warranty of
	27	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	28	* GNU General Public License for more details.
26ac0430	29	*
f52a7d75	30	* You should have received a copy of the GNU General Public License
	31	* along with this program; if not, write to the Free Software
	32	* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA.
	33	*
	34	*/
	35
f7f3304a	36	#include "squid.h"
25f98340 AJ	37	#include "hash.h"
25f98340 AJ	38	#include "profiler/Profiler.h"
f52a7d75	39
	40	#if HAVE_STDIO_H
	41	#include <stdio.h>
	42	#endif
	43	#if HAVE_STDLIB_H
	44	#include <stdlib.h>
	45	#endif
	46	#if HAVE_STRING_H
	47	#include <string.h>
	48	#endif
	49	#if HAVE_UNISTD_H
	50	#include <unistd.h>
	51	#endif
	52	#if HAVE_GNUMALLLOC_H
	53	#include <gnumalloc.h>
482aa790	54	#elif HAVE_MALLOC_H
f52a7d75	55	#include <malloc.h>
	56	#endif
	57	#if HAVE_ASSERT_H
	58	#include <assert.h>
	59	#endif
e880cefa	60	#if HAVE_MATH_H
	61	#include <math.h>
	62	#endif
f52a7d75	63
f52a7d75	64	static void hash_next_bucket(hash_table * hid);
	65
	66	unsigned int
	67	hash_string(const void *data, unsigned int size)
	68	{
	69	const char *s = data;
	70	unsigned int n = 0;
	71	unsigned int j = 0;
	72	unsigned int i = 0;
	73	while (*s) {
26ac0430 AJ	74	j++;
26ac0430 AJ	75	n ^= 271 * (unsigned) *s++;
f52a7d75	76	}
	77	i = n ^ (j * 271);
	78	return i % size;
	79	}
	80
	81	/* the following function(s) were adapted from
	82	* usr/src/lib/libc/db/hash_func.c, 4.4 BSD lite */
	83
	84	/* Hash function from Chris Torek. */
	85	unsigned int
	86	hash4(const void *data, unsigned int size)
	87	{
	88	const char *key = data;
	89	size_t loop;
	90	unsigned int h;
	91	size_t len;
	92
	93	#define HASH4a h = (h << 5) - h + *key++;
	94	#define HASH4b h = (h << 5) + h + *key++;
	95	#define HASH4 HASH4b
	96
	97	h = 0;
	98	len = strlen(key);
	99	loop = len >> 3;
	100	switch (len & (8 - 1)) {
	101	case 0:
26ac0430	102	break;
f52a7d75	103	case 7:
26ac0430 AJ	104	HASH4;
26ac0430 AJ	105	/* FALLTHROUGH */
f52a7d75	106	case 6:
26ac0430 AJ	107	HASH4;
26ac0430 AJ	108	/* FALLTHROUGH */
f52a7d75	109	case 5:
26ac0430 AJ	110	HASH4;
26ac0430 AJ	111	/* FALLTHROUGH */
f52a7d75	112	case 4:
26ac0430 AJ	113	HASH4;
26ac0430 AJ	114	/* FALLTHROUGH */
f52a7d75	115	case 3:
26ac0430 AJ	116	HASH4;
26ac0430 AJ	117	/* FALLTHROUGH */
f52a7d75	118	case 2:
26ac0430 AJ	119	HASH4;
26ac0430 AJ	120	/* FALLTHROUGH */
f52a7d75	121	case 1:
26ac0430	122	HASH4;
f52a7d75	123	}
f52a7d75	124	while (loop--) {
26ac0430 AJ	125	HASH4;
	126	HASH4;
	127	HASH4;
	128	HASH4;
	129	HASH4;
	130	HASH4;
	131	HASH4;
	132	HASH4;
f52a7d75	133	}
	134	return h % size;
	135	}
	136
	137	/*
	138	* hash_create - creates a new hash table, uses the cmp_func
	139	* to compare keys. Returns the identification for the hash table;
	140	* otherwise returns a negative number on error.
	141	*/
	142	hash_table *
	143	hash_create(HASHCMP * cmp_func, int hash_sz, HASHHASH * hash_func)
	144	{
	145	hash_table *hid = xcalloc(1, sizeof(hash_table));
	146	if (!hash_sz)
26ac0430	147	hid->size = (unsigned int) DEFAULT_HASH_SIZE;
f52a7d75	148	else
26ac0430	149	hid->size = (unsigned int) hash_sz;
f52a7d75	150	/* allocate and null the buckets */
	151	hid->buckets = xcalloc(hid->size, sizeof(hash_link *));
	152	hid->cmp = cmp_func;
	153	hid->hash = hash_func;
	154	hid->next = NULL;
	155	hid->current_slot = 0;
	156	return hid;
	157	}
	158
	159	/*
	160	* hash_join - joins a hash_link under its key lnk->key
26ac0430	161	* into the hash table 'hid'.
f52a7d75	162	*
	163	* It does not copy any data into the hash table, only links pointers.
	164	*/
	165	void
	166	hash_join(hash_table * hid, hash_link * lnk)
	167	{
	168	int i;
	169	i = hid->hash(lnk->key, hid->size);
	170	lnk->next = hid->buckets[i];
	171	hid->buckets[i] = lnk;
	172	hid->count++;
	173	}
	174
	175	/*
	176	* hash_lookup - locates the item under the key 'k' in the hash table
	177	* 'hid'. Returns a pointer to the hash bucket on success; otherwise
	178	* returns NULL.
	179	*/
4a8b20e8	180	hash_link *
f52a7d75	181	hash_lookup(hash_table * hid, const void *k)
	182	{
	183	hash_link *walker;
	184	int b;
88bfe092	185	PROF_start(hash_lookup);
f52a7d75	186	assert(k != NULL);
	187	b = hid->hash(k, hid->size);
	188	for (walker = hid->buckets[b]; walker != NULL; walker = walker->next) {
26ac0430 AJ	189	if ((hid->cmp) (k, walker->key) == 0) {
	190	PROF_stop(hash_lookup);
	191	return (walker);
	192	}
	193	assert(walker != walker->next);
f52a7d75	194	}
88bfe092	195	PROF_stop(hash_lookup);
f52a7d75	196	return NULL;
	197	}
	198
	199	static void
	200	hash_next_bucket(hash_table * hid)
	201	{
	202	while (hid->next == NULL && ++hid->current_slot < hid->size)
26ac0430	203	hid->next = hid->buckets[hid->current_slot];
f52a7d75	204	}
	205
	206	/*
	207	* hash_first - initializes the hash table for the hash_next()
	208	* function.
	209	*/
	210	void
	211	hash_first(hash_table * hid)
	212	{
	213	assert(NULL == hid->next);
	214	hid->current_slot = 0;
	215	hid->next = hid->buckets[hid->current_slot];
	216	if (NULL == hid->next)
26ac0430	217	hash_next_bucket(hid);
f52a7d75	218	}
	219
	220	/*
	221	* hash_next - returns the next item in the hash table 'hid'.
26ac0430	222	* Otherwise, returns NULL on error or end of list.
f52a7d75	223	*
	224	* MUST call hash_first() before hash_next().
	225	*/
4a8b20e8	226	hash_link *
f52a7d75	227	hash_next(hash_table * hid)
	228	{
	229	hash_link *this = hid->next;
	230	if (NULL == this)
26ac0430	231	return NULL;
f52a7d75	232	hid->next = this->next;
f52a7d75	233	if (NULL == hid->next)
26ac0430	234	hash_next_bucket(hid);
f52a7d75	235	return this;
	236	}
	237
2c4f7ab2	238	/*
	239	* hash_last - resets hash traversal state to NULL
	240	*
	241	*/
	242	void
ab96e65c	243	hash_last(hash_table * hid)
2c4f7ab2	244	{
137a13ea	245	assert(hid != NULL);
2c4f7ab2	246	hid->next = NULL;
	247	hid->current_slot = 0;
	248	}
	249
f52a7d75	250	/*
26ac0430	251	* hash_remove_link - deletes the given hash_link node from the
f52a7d75	252	* hash table 'hid'. Does not free the item, only removes it
	253	* from the list.
	254	*
4fba1a24	255	* An assertion is triggered if the hash_link is not found in the
4fba1a24	256	* list.
f52a7d75	257	*/
	258	void
	259	hash_remove_link(hash_table * hid, hash_link * hl)
	260	{
	261	hash_link **P;
	262	int i;
	263	assert(hl != NULL);
	264	i = hid->hash(hl->key, hid->size);
	265	for (P = &hid->buckets[i]; P; P = &(P)->next) {
26ac0430 AJ	266	if (*P != hl)
	267	continue;
	268	*P = hl->next;
	269	if (hid->next == hl) {
	270	hid->next = hl->next;
	271	if (NULL == hid->next)
	272	hash_next_bucket(hid);
	273	}
	274	hid->count--;
	275	return;
f52a7d75	276	}
e530de6c	277	assert(0);
f52a7d75	278	}
	279
	280	/*
26ac0430	281	* hash_get_bucket - returns the head item of the bucket
f52a7d75	282	* in the hash table 'hid'. Otherwise, returns NULL on error.
	283	*/
	284	hash_link *
	285	hash_get_bucket(hash_table * hid, unsigned int bucket)
	286	{
	287	if (bucket >= hid->size)
26ac0430	288	return NULL;
f52a7d75	289	return (hid->buckets[bucket]);
	290	}
	291
	292	void
	293	hashFreeItems(hash_table * hid, HASHFREE * free_func)
	294	{
	295	hash_link *l;
	296	hash_link **list;
	297	int i = 0;
	298	int j;
	299	list = xcalloc(hid->count, sizeof(hash_link *));
	300	hash_first(hid);
	301	while ((l = hash_next(hid)) && i < hid->count) {
26ac0430 AJ	302	*(list + i) = l;
26ac0430 AJ	303	i++;
f52a7d75	304	}
f52a7d75	305	for (j = 0; j < i; j++)
26ac0430	306	free_func(*(list + j));
f52a7d75	307	xfree(list);
	308	}
	309
	310	void
	311	hashFreeMemory(hash_table * hid)
	312	{
04f7fd38	313	if (hid == NULL)
928b6c10	314	return;
efacbef0	315	if (hid->buckets)
26ac0430	316	xfree(hid->buckets);
f52a7d75	317	xfree(hid);
	318	}
	319
26ac0430	320	static int hash_primes[] = {
f52a7d75	321	103,
	322	229,
	323	467,
	324	977,
	325	1979,
	326	4019,
	327	6037,
	328	7951,
	329	12149,
	330	16231,
	331	33493,
	332	65357
	333	};
	334
	335	int
	336	hashPrime(int n)
	337	{
	338	int I = sizeof(hash_primes) / sizeof(int);
	339	int i;
	340	int best_prime = hash_primes[0];
d87ebd78	341	double min = fabs(log((double) n) - log((double) hash_primes[0]));
f52a7d75	342	double d;
f52a7d75	343	for (i = 0; i < I; i++) {
26ac0430 AJ	344	d = fabs(log((double) n) - log((double) hash_primes[i]));
	345	if (d > min)
	346	continue;
	347	min = d;
	348	best_prime = hash_primes[i];
f52a7d75	349	}
	350	return best_prime;
	351	}
	352
186477c1	353	/*
	354	* return the key of a hash_link as a const string
	355	*/
	356	const char *
	357	hashKeyStr(hash_link * hl)
	358	{
	359	return (const char *) hl->key;
	360	}
	361
f52a7d75	362
32d002cb	363	#if USE_HASH_DRIVER
f52a7d75	364	/*
	365	* hash-driver - Run with a big file as stdin to insert each line into the
	366	* hash table, then prints the whole hash table, then deletes a random item,
	367	* and prints the table again...
	368	*/
	369	int
	370	main(void)
	371	{
	372	hash_table *hid;
	373	int i;
	374	LOCAL_ARRAY(char, buf, BUFSIZ);
	375	LOCAL_ARRAY(char, todelete, BUFSIZ);
	376	hash_link *walker = NULL;
	377
	378	todelete[0] = '\0';
	379	printf("init\n");
	380
	381	printf("creating hash table\n");
	382	if ((hid = hash_create((HASHCMP *) strcmp, 229, hash4)) < 0) {
26ac0430 AJ	383	printf("hash_create error.\n");
26ac0430 AJ	384	exit(1);
f52a7d75	385	}
	386	printf("done creating hash table: %d\n", hid);
	387
	388	while (fgets(buf, BUFSIZ, stdin)) {
26ac0430 AJ	389	buf[strlen(buf) - 1] = '\0';
	390	printf("Inserting '%s' for item %p to hash table: %d\n",
	391	buf, buf, hid);
	392	hash_insert(hid, xstrdup(buf), (void *) 0x12345678);
	393	if (random() % 17 == 0)
	394	strcpy(todelete, buf);
f52a7d75	395	}
	396
	397	printf("walking hash table...\n");
	398	for (i = 0, walker = hash_first(hid); walker; walker = hash_next(hid)) {
26ac0430 AJ	399	printf("item %5d: key: '%s' item: %p\n", i++, walker->key,
26ac0430 AJ	400	walker->item);
f52a7d75	401	}
	402	printf("done walking hash table...\n");
	403
	404	if (todelete[0]) {
26ac0430 AJ	405	printf("deleting %s from %d\n", todelete, hid);
	406	if (hash_delete(hid, todelete))
	407	printf("hash_delete error\n");
f52a7d75	408	}
	409	printf("walking hash table...\n");
	410	for (i = 0, walker = hash_first(hid); walker; walker = hash_next(hid)) {
26ac0430 AJ	411	printf("item %5d: key: '%s' item: %p\n", i++, walker->key,
26ac0430 AJ	412	walker->item);
f52a7d75	413	}
	414	printf("done walking hash table...\n");
	415
	416
	417	printf("driver finished.\n");
	418	exit(0);
	419	}
	420	#endif