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


/*
 * $Id: hash.c,v 1.2 1998/08/17 23:26:28 wessels Exp $
 *
 * DEBUG: section 0     Hash Tables
 * AUTHOR: Harvest Derived
 *
 * SQUID Internet Object Cache  http://squid.nlanr.net/Squid/
 * ----------------------------------------------------------
 *
 *  Squid is the result of efforts by numerous individuals from the
 *  Internet community.  Development is led by Duane Wessels of the
 *  National Laboratory for Applied Network Research and funded by the
 *  National Science Foundation.  Squid is Copyrighted (C) 1998 by
 *  Duane Wessels and the University of California San Diego.  Please
 *  see the COPYRIGHT file for full details.  Squid incorporates
 *  software developed and/or copyrighted by other sources.  Please 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 "config.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 && !defined(_SQUID_FREEBSD_) && !defined(_SQUID_NEXT_)
#include <malloc.h>
#endif
#if HAVE_ASSERT_H
#include <assert.h>
#endif

#include "hash.h"
#include "util.h"

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.
 */
void *
hash_lookup(hash_table * hid, const void *k)
{
    hash_link *walker;
    int b;
    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)
	    return (walker);
	assert(walker != walker->next);
    }
    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().
 */
void *
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_remove_link - deletes the given hash_link node from the 
 *  hash table 'hid'.  Does not free the item, only removes it
 *  from the list.
 *
 *  On success, it returns 0 and deletes the link; otherwise, 
 *  returns non-zero on error.
 */
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)
{
    assert(hid);
    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(n) - log(hash_primes[0]));
    double d;
    for (i = 0; i < I; i++) {
	d = fabs(log(n) - log(hash_primes[i]));
	if (d > min)
	    continue;
	min = d;
	best_prime = hash_primes[i];
    }
    return best_prime;
}


#ifdef 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	/*
e530de6c	3	* $Id: hash.c,v 1.2 1998/08/17 23:26:28 wessels Exp $
f52a7d75	4	*
	5	* DEBUG: section 0 Hash Tables
	6	* AUTHOR: Harvest Derived
	7	*
	8	* SQUID Internet Object Cache http://squid.nlanr.net/Squid/
	9	* ----------------------------------------------------------
	10	*
	11	* Squid is the result of efforts by numerous individuals from the
	12	* Internet community. Development is led by Duane Wessels of the
	13	* National Laboratory for Applied Network Research and funded by the
	14	* National Science Foundation. Squid is Copyrighted (C) 1998 by
	15	* Duane Wessels and the University of California San Diego. Please
	16	* see the COPYRIGHT file for full details. Squid incorporates
	17	* software developed and/or copyrighted by other sources. Please see
	18	* the CREDITS file for full details.
	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.
	24	*
	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.
	29	*
	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
	36	#include "config.h"
	37
	38	#if HAVE_STDIO_H
	39	#include <stdio.h>
	40	#endif
	41	#if HAVE_STDLIB_H
	42	#include <stdlib.h>
	43	#endif
	44	#if HAVE_STRING_H
	45	#include <string.h>
	46	#endif
	47	#if HAVE_UNISTD_H
	48	#include <unistd.h>
	49	#endif
	50	#if HAVE_GNUMALLLOC_H
	51	#include <gnumalloc.h>
	52	#elif HAVE_MALLOC_H && !defined(_SQUID_FREEBSD_) && !defined(_SQUID_NEXT_)
	53	#include <malloc.h>
	54	#endif
	55	#if HAVE_ASSERT_H
	56	#include <assert.h>
	57	#endif
	58
	59	#include "hash.h"
	60	#include "util.h"
	61
	62	static void hash_next_bucket(hash_table * hid);
	63
	64	unsigned int
	65	hash_string(const void *data, unsigned int size)
	66	{
	67	const char *s = data;
68	unsigned int n = 0;
69	unsigned int j = 0;
70	unsigned int i = 0;
71	while (*s) {
72	j++;
73	n ^= 271 * (unsigned) *s++;
74	}
75	i = n ^ (j * 271);
76	return i % size;
77	}
78
79	/* the following function(s) were adapted from
80	* usr/src/lib/libc/db/hash_func.c, 4.4 BSD lite */
81
82	/* Hash function from Chris Torek. */
83	unsigned int
84	hash4(const void *data, unsigned int size)
85	{
86	const char *key = data;
87	size_t loop;
88	unsigned int h;
89	size_t len;
90
91	#define HASH4a h = (h << 5) - h + *key++;
92	#define HASH4b h = (h << 5) + h + *key++;
93	#define HASH4 HASH4b
94
95	h = 0;
96	len = strlen(key);
97	loop = len >> 3;
98	switch (len & (8 - 1)) {
99	case 0:
100	break;
101	case 7:
102	HASH4;
103	/* FALLTHROUGH */
104	case 6:
105	HASH4;
106	/* FALLTHROUGH */
107	case 5:
108	HASH4;
109	/* FALLTHROUGH */
110	case 4:
111	HASH4;
112	/* FALLTHROUGH */
113	case 3:
114	HASH4;
115	/* FALLTHROUGH */
116	case 2:
117	HASH4;
118	/* FALLTHROUGH */
119	case 1:
120	HASH4;
121	}
122	while (loop--) {
123	HASH4;
124	HASH4;
125	HASH4;
126	HASH4;
127	HASH4;
128	HASH4;
129	HASH4;
130	HASH4;
131	}
132	return h % size;
133	}
134
135	/*
136	* hash_create - creates a new hash table, uses the cmp_func
137	* to compare keys. Returns the identification for the hash table;
138	* otherwise returns a negative number on error.
139	*/
140	hash_table *
141	hash_create(HASHCMP * cmp_func, int hash_sz, HASHHASH * hash_func)
142	{
143	hash_table *hid = xcalloc(1, sizeof(hash_table));
144	if (!hash_sz)
145	hid->size = (unsigned int) DEFAULT_HASH_SIZE;
146	else
147	hid->size = (unsigned int) hash_sz;
148	/* allocate and null the buckets */
149	hid->buckets = xcalloc(hid->size, sizeof(hash_link *));
150	hid->cmp = cmp_func;
151	hid->hash = hash_func;
152	hid->next = NULL;
153	hid->current_slot = 0;
154	return hid;
155	}
156
157	/*
158	* hash_join - joins a hash_link under its key lnk->key
159	* into the hash table 'hid'.
160	*
161	* It does not copy any data into the hash table, only links pointers.
162	*/
163	void
164	hash_join(hash_table * hid, hash_link * lnk)
165	{
166	int i;
167	i = hid->hash(lnk->key, hid->size);
168	lnk->next = hid->buckets[i];
169	hid->buckets[i] = lnk;
170	hid->count++;
171	}
172
173	/*
174	* hash_lookup - locates the item under the key 'k' in the hash table
175	* 'hid'. Returns a pointer to the hash bucket on success; otherwise
176	* returns NULL.
177	*/
178	void *
179	hash_lookup(hash_table * hid, const void *k)
180	{
181	hash_link *walker;
182	int b;
183	assert(k != NULL);
184	b = hid->hash(k, hid->size);
185	for (walker = hid->buckets[b]; walker != NULL; walker = walker->next) {
186	if ((hid->cmp) (k, walker->key) == 0)
187	return (walker);
188	assert(walker != walker->next);
189	}
190	return NULL;
191	}
192
193	static void
194	hash_next_bucket(hash_table * hid)
195	{
196	while (hid->next == NULL && ++hid->current_slot < hid->size)
197	hid->next = hid->buckets[hid->current_slot];
198	}
199
200	/*
201	* hash_first - initializes the hash table for the hash_next()
202	* function.
203	*/
204	void
205	hash_first(hash_table * hid)
206	{
207	assert(NULL == hid->next);
208	hid->current_slot = 0;
209	hid->next = hid->buckets[hid->current_slot];
210	if (NULL == hid->next)
211	hash_next_bucket(hid);
212	}
213
214	/*
215	* hash_next - returns the next item in the hash table 'hid'.
216	* Otherwise, returns NULL on error or end of list.
217	*
218	* MUST call hash_first() before hash_next().
219	*/
220	void *
221	hash_next(hash_table * hid)
222	{
223	hash_link *this = hid->next;
224	if (NULL == this)
225	return NULL;
226	hid->next = this->next;
227	if (NULL == hid->next)
228	hash_next_bucket(hid);
229	return this;
230	}
231
232	/*
233	* hash_remove_link - deletes the given hash_link node from the
234	* hash table 'hid'. Does not free the item, only removes it
235	* from the list.
236	*
237	* On success, it returns 0 and deletes the link; otherwise,
238	* returns non-zero on error.
239	*/
240	void
241	hash_remove_link(hash_table * hid, hash_link * hl)
242	{
243	hash_link **P;
244	int i;
245	assert(hl != NULL);
246	i = hid->hash(hl->key, hid->size);
247	for (P = &hid->buckets[i]; P; P = &(P)->next) {
248	if (*P != hl)
249	continue;
250	*P = hl->next;
251	if (hid->next == hl) {
252	hid->next = hl->next;
253	if (NULL == hid->next)
254	hash_next_bucket(hid);
255	}
256	hid->count--;
257	return;
258	}
e530de6c	259	assert(0);
f52a7d75	260	}
	261
	262	/*
	263	* hash_get_bucket - returns the head item of the bucket
	264	* in the hash table 'hid'. Otherwise, returns NULL on error.
	265	*/
	266	hash_link *
	267	hash_get_bucket(hash_table * hid, unsigned int bucket)
	268	{
	269	if (bucket >= hid->size)
	270	return NULL;
	271	return (hid->buckets[bucket]);
	272	}
	273
	274	void
	275	hashFreeItems(hash_table * hid, HASHFREE * free_func)
	276	{
	277	hash_link *l;
	278	hash_link **list;
	279	int i = 0;
	280	int j;
	281	list = xcalloc(hid->count, sizeof(hash_link *));
	282	hash_first(hid);
	283	while ((l = hash_next(hid)) && i < hid->count) {
	284	*(list + i) = l;
	285	i++;
	286	}
	287	for (j = 0; j < i; j++)
	288	free_func(*(list + j));
	289	xfree(list);
	290	}
	291
	292	void
	293	hashFreeMemory(hash_table * hid)
	294	{
	295	assert(hid);
	296	if (hid->buckets);
	297	xfree(hid->buckets);
	298	xfree(hid);
	299	}
	300
	301	static int hash_primes[] =
	302	{
	303	103,
	304	229,
	305	467,
	306	977,
	307	1979,
	308	4019,
	309	6037,
	310	7951,
	311	12149,
	312	16231,
	313	33493,
	314	65357
	315	};
	316
	317	int
	318	hashPrime(int n)
	319	{
	320	int I = sizeof(hash_primes) / sizeof(int);
	321	int i;
	322	int best_prime = hash_primes[0];
	323	double min = fabs(log(n) - log(hash_primes[0]));
324	double d;
325	for (i = 0; i < I; i++) {
326	d = fabs(log(n) - log(hash_primes[i]));
327	if (d > min)
328	continue;
329	min = d;
330	best_prime = hash_primes[i];
331	}
332	return best_prime;
333	}
334
335
336	#ifdef USE_HASH_DRIVER
337	/*
338	* hash-driver - Run with a big file as stdin to insert each line into the
339	* hash table, then prints the whole hash table, then deletes a random item,
340	* and prints the table again...
341	*/
342	int
343	main(void)
344	{
345	hash_table *hid;
346	int i;
347	LOCAL_ARRAY(char, buf, BUFSIZ);
348	LOCAL_ARRAY(char, todelete, BUFSIZ);
349	hash_link *walker = NULL;
350
351	todelete[0] = '\0';
352	printf("init\n");
353
354	printf("creating hash table\n");
355	if ((hid = hash_create((HASHCMP *) strcmp, 229, hash4)) < 0) {
356	printf("hash_create error.\n");
357	exit(1);
358	}
359	printf("done creating hash table: %d\n", hid);
360
361	while (fgets(buf, BUFSIZ, stdin)) {
362	buf[strlen(buf) - 1] = '\0';
363	printf("Inserting '%s' for item %p to hash table: %d\n",
364	buf, buf, hid);
365	hash_insert(hid, xstrdup(buf), (void *) 0x12345678);
366	if (random() % 17 == 0)
367	strcpy(todelete, buf);
368	}
369
370	printf("walking hash table...\n");
371	for (i = 0, walker = hash_first(hid); walker; walker = hash_next(hid)) {
372	printf("item %5d: key: '%s' item: %p\n", i++, walker->key,
373	walker->item);
374	}
375	printf("done walking hash table...\n");
376
377	if (todelete[0]) {
378	printf("deleting %s from %d\n", todelete, hid);
379	if (hash_delete(hid, todelete))
380	printf("hash_delete error\n");
381	}
382	printf("walking hash table...\n");
383	for (i = 0, walker = hash_first(hid); walker; walker = hash_next(hid)) {
384	printf("item %5d: key: '%s' item: %p\n", i++, walker->key,
385	walker->item);
386	}
387	printf("done walking hash table...\n");
388
389
390	printf("driver finished.\n");
391	exit(0);
392	}
393	#endif