[thirdparty/dhcp.git] / omapip / hash.c

/* hash.c

   Routines for manipulating hash tables... */

/*
 * Copyright (c) 2004-2006 by Internet Systems Consortium, Inc. ("ISC")
 * Copyright (c) 1995-2003 by Internet Software Consortium
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT
 * OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 *
 *   Internet Systems Consortium, Inc.
 *   950 Charter Street
 *   Redwood City, CA 94063
 *   <info@isc.org>
 *   http://www.isc.org/
 *
 * This software has been written for Internet Systems Consortium
 * by Ted Lemon in cooperation with Vixie Enterprises and Nominum, Inc.
 * To learn more about Internet Systems Consortium, see
 * ``http://www.isc.org/''.  To learn more about Vixie Enterprises,
 * see ``http://www.vix.com''.   To learn more about Nominum, Inc., see
 * ``http://www.nominum.com''.
 */

#ifndef lint
static char copyright[] =
"$Id: hash.c,v 1.14 2007/05/19 18:47:15 dhankins Exp $ Copyright (c) 2004-2006 Internet Systems Consortium.  All rights reserved.\n";
#endif /* not lint */

#include "dhcpd.h"

#include <omapip/omapip_p.h>
#include <limits.h>
#include <ctype.h>

static unsigned
find_length(const void *key,
	    unsigned (*do_hash)(const void *, unsigned, unsigned))
{
	if (do_hash == do_case_hash || do_hash == do_string_hash)
		return strlen((const char *)key);
	if (do_hash == do_number_hash)
		return sizeof(unsigned);
	if (do_hash == do_ip4_hash)
		return 4;

	log_fatal("Impossible condition at %s:%d.", MDL);
	return 0; /* Silence compiler warnings. */
}

int new_hash_table (tp, count, file, line)
	struct hash_table **tp;
	unsigned count;
	const char *file;
	int line;
{
	struct hash_table *rval;
	unsigned extra;

	if (!tp) {
		log_error ("%s(%d): new_hash_table called with null pointer.",
			   file, line);
#if defined (POINTER_DEBUG)
		abort ();
#endif
		return 0;
	}
	if (*tp) {
		log_error ("%s(%d): non-null target for new_hash_table.",
			   file, line);
#if defined (POINTER_DEBUG)
		abort ();
#endif
	}

	/* There is one hash bucket in the structure.  Allocate extra
	 * memory beyond the end of the structure to fulfill the requested
	 * count ("count - 1").  Do not let there be less than one.
	 */
	if (count <= 1)
		extra = 0;
	else
		extra = count - 1;

	rval = dmalloc(sizeof(struct hash_table) +
		       (extra * sizeof(struct hash_bucket *)), file, line);
	if (!rval)
		return 0;
	rval -> hash_count = count;
	*tp = rval;
	return 1;
}

void free_hash_table (tp, file, line)
	struct hash_table **tp;
	const char *file;
	int line;
{
	int i;
	struct hash_bucket *hbc, *hbn = (struct hash_bucket *)0;
	struct hash_table *ptr = *tp;

#if defined (DEBUG_MEMORY_LEAKAGE) || \
		defined (DEBUG_MEMORY_LEAKAGE_ON_EXIT)
	for (i = 0; i < ptr -> hash_count; i++) {
	    for (hbc = ptr -> buckets [i]; hbc; hbc = hbn) {
		hbn = hbc -> next;
		if (ptr -> dereferencer && hbc -> value)
		    (*ptr -> dereferencer) (&hbc -> value, MDL);
	    }
	    for (hbc = ptr -> buckets [i]; hbc; hbc = hbn) {
		hbn = hbc -> next;
		free_hash_bucket (hbc, MDL);
	    }
	    ptr -> buckets [i] = (struct hash_bucket *)0;
	}
#endif

	dfree((void *)ptr, MDL);
	*tp = (struct hash_table *)0;
}

struct hash_bucket *free_hash_buckets;

#if defined (DEBUG_MEMORY_LEAKAGE_ON_EXIT)
struct hash_bucket *hash_bucket_hunks;

void relinquish_hash_bucket_hunks ()
{
	struct hash_bucket *c, *n, **p;

	/* Account for all the hash buckets on the free list. */
	p = &free_hash_buckets;
	for (c = free_hash_buckets; c; c = c -> next) {
		for (n = hash_bucket_hunks; n; n = n -> next) {
			if (c > n && c < n + 127) {
				*p = c -> next;
				n -> len++;
				break;
			}
		}
		/* If we didn't delete the hash bucket from the free list,
		   advance the pointer. */
		if (!n)
			p = &c -> next;
	}
		
	for (c = hash_bucket_hunks; c; c = n) {
		n = c -> next;
		if (c -> len != 126) {
			log_info ("hashbucket %lx hash_buckets %d free %u",
				  (unsigned long)c, 127, c -> len);
		}
		dfree (c, MDL);
	}
}
#endif

struct hash_bucket *new_hash_bucket (file, line)
	const char *file;
	int line;
{
	struct hash_bucket *rval;
	int i = 0;
	if (!free_hash_buckets) {
		rval = dmalloc (127 * sizeof (struct hash_bucket),
				file, line);
		if (!rval)
			return rval;
# if defined (DEBUG_MEMORY_LEAKAGE_ON_EXIT)
		rval -> next = hash_bucket_hunks;
		hash_bucket_hunks = rval;
		hash_bucket_hunks -> len = 0;
		i++;
		rval++;
#endif
		for (; i < 127; i++) {
			rval -> next = free_hash_buckets;
			free_hash_buckets = rval;
			rval++;
		}
	}
	rval = free_hash_buckets;
	free_hash_buckets = rval -> next;
	return rval;
}

void free_hash_bucket (ptr, file, line)
	struct hash_bucket *ptr;
	const char *file;
	int line;
{
	struct hash_bucket *hp;
#if defined (DEBUG_MALLOC_POOL)
	for (hp = free_hash_buckets; hp; hp = hp -> next) {
		if (hp == ptr) {
			log_error ("hash bucket freed twice!");
			abort ();
		}
	}
#endif
	ptr -> next = free_hash_buckets;
	free_hash_buckets = ptr;
}

int new_hash(struct hash_table **rp,
	     hash_reference referencer,
	     hash_dereference dereferencer,
	     unsigned hsize,
	     unsigned (*hasher)(const void *, unsigned, unsigned),
	     const char *file, int line)
{
	if (hsize == 0)
		hsize = DEFAULT_HASH_SIZE;

	if (!new_hash_table (rp, hsize, file, line))
		return 0;

	memset ((*rp)->buckets, 0, hsize * sizeof(struct hash_bucket *));

	(*rp)->referencer = referencer;
	(*rp)->dereferencer = dereferencer;
	(*rp)->do_hash = hasher;

	if (hasher == do_case_hash)
		(*rp)->cmp = casecmp;
	else
		(*rp)->cmp = memcmp;

	return 1;
}

unsigned
do_case_hash(const void *name, unsigned len, unsigned size)
{
	register unsigned accum = 0;
	register const unsigned char *s = name;
	int i = len;
	register unsigned c;

	while (i--) {
		/* Make the hash case-insensitive. */
		c = *s++;
		if (isascii(c))
			c = tolower(c);

		/* Add the character in... */
		accum = (accum << 1) + c;

		/* Add carry back in... */
		while (accum > 65535) {
			accum = (accum & 65535) + (accum >> 16);
		}

	}
	return accum % size;
}

unsigned
do_string_hash(const void *name, unsigned len, unsigned size)
{
	register unsigned accum = 0;
	register const unsigned char *s = (const unsigned char *)name;
	int i = len;

	while (i--) {
		/* Add the character in... */
		accum = (accum << 1) + *s++;

		/* Add carry back in... */
		while (accum > 65535) {
			accum = (accum & 65535) + (accum >> 16);
		}
	}
	return accum % size;
}

/* Client identifiers are generally 32-bits of ordinary
 * non-randomness followed by 24-bits of unordinary randomness.
 * So, end-align in 24-bit chunks, and xor any preceding data
 * just to mix it up a little.
 */
unsigned
do_id_hash(const void *name, unsigned len, unsigned size)
{
	register unsigned accum = 0;
	register const unsigned char *s = (const unsigned char *)name;
	const unsigned char *end = s + len;

	if (len == 0)
		return 0;

	/* The switch indexes our starting position into the do/while loop,
	 * taking up the remainder after hashing in all the other bytes in
	 * threes.
	 */
	switch (len % 3) {
		do {
	      case 0:
			accum ^= *s++ << 16;
	      case 2:
			accum ^= *s++ << 8;
	      case 1:
			accum ^= *s++;
		} while (s < end);

		break;
	}

	return accum % size;
}

unsigned
do_number_hash(const void *key, unsigned len, unsigned size)
{
	register unsigned number = *((const unsigned *)key);

	return number % size;
}

unsigned
do_ip4_hash(const void *key, unsigned len, unsigned size)
{
	u_int32_t number;

	memcpy(&number, key, 4);

	number = ntohl(number);

	return number % size;
}

unsigned char *
hash_report(struct hash_table *table)
{
	static unsigned char retbuf[sizeof("Contents/Size (%): "
					   "2147483647/2147483647 "
					   "(2147483647%). "
					   "Min/max: 2147483647/2147483647")];
	unsigned curlen, pct, contents=0, minlen=UINT_MAX, maxlen=0;
	unsigned i;
	struct hash_bucket *bp;

	if (table->hash_count == 0)
		return "Invalid hash table.";

	for (i = 0 ; i < table->hash_count ; i++) {
		curlen = 0;

		bp = table->buckets[i];
		while (bp != NULL) {
			curlen++;
			bp = bp->next;
		}

		if (curlen < minlen)
			minlen = curlen;
		if (curlen > maxlen)
			maxlen = curlen;

		contents += curlen;
	}

	if (contents >= (UINT_MAX / 100))
		pct = contents / ((table->hash_count / 100) + 1);
	else
		pct = (contents * 100) / table->hash_count;

	if (contents > 2147483647 ||
	    table->hash_count > 2147483647 ||
	    pct > 2147483647 ||
	    minlen > 2147483647 ||
	    maxlen > 2147483647)
		return "Report out of range for display.";

	sprintf(retbuf, "Contents/Size (%%): %u/%u (%u%%). Min/max: %u/%u",
		contents, table->hash_count, pct, minlen, maxlen);

	return retbuf;
}

void add_hash (table, key, len, pointer, file, line)
	struct hash_table *table;
	unsigned len;
	const void *key;
	hashed_object_t *pointer;
	const char *file;
	int line;
{
	int hashno;
	struct hash_bucket *bp;
	void *foo;

	if (!table)
		return;

	if (!len)
		len = find_length(key, table->do_hash);

	hashno = (*table->do_hash)(key, len, table->hash_count);
	bp = new_hash_bucket (file, line);

	if (!bp) {
		log_error ("Can't add entry to hash table: no memory.");
		return;
	}
	bp -> name = key;
	if (table -> referencer) {
		foo = &bp -> value;
		(*(table -> referencer)) (foo, pointer, file, line);
	} else
		bp -> value = pointer;
	bp -> next = table -> buckets [hashno];
	bp -> len = len;
	table -> buckets [hashno] = bp;
}

void delete_hash_entry (table, key, len, file, line)
	struct hash_table *table;
	unsigned len;
	const void *key;
	const char *file;
	int line;
{
	int hashno;
	struct hash_bucket *bp, *pbp = (struct hash_bucket *)0;
	void *foo;

	if (!table)
		return;

	if (!len)
		len = find_length(key, table->do_hash);

	hashno = (*table->do_hash)(key, len, table->hash_count);

	/* Go through the list looking for an entry that matches;
	   if we find it, delete it. */
	for (bp = table -> buckets [hashno]; bp; bp = bp -> next) {
		if ((!bp -> len &&
		     !strcmp ((const char *)bp->name, key)) ||
		    (bp -> len == len &&
		     !(table -> cmp)(bp->name, key, len))) {
			if (pbp) {
				pbp -> next = bp -> next;
			} else {
				table -> buckets [hashno] = bp -> next;
			}
			if (bp -> value && table -> dereferencer) {
				foo = &bp -> value;
				(*(table -> dereferencer)) (foo, file, line);
			}
			free_hash_bucket (bp, file, line);
			break;
		}
		pbp = bp;	/* jwg, 9/6/96 - nice catch! */
	}
}

int hash_lookup (vp, table, key, len, file, line)
	hashed_object_t **vp;
	struct hash_table *table;
	const void *key;
	unsigned len;
	const char *file;
	int line;
{
	int hashno;
	struct hash_bucket *bp;

	if (!table)
		return 0;
	if (!len)
		len = find_length(key, table->do_hash);

	if (*vp != NULL) {
		log_fatal("Internal inconsistency: storage value has not been "
			  "initialized to zero (from %s:%d).", file, line);
	}

	hashno = (*table->do_hash)(key, len, table->hash_count);

	for (bp = table -> buckets [hashno]; bp; bp = bp -> next) {
		if (len == bp -> len
		    && !(*table->cmp)(bp->name, key, len)) {
			if (table -> referencer)
				(*table -> referencer) (vp, bp -> value,
							file, line);
			else
				*vp = bp -> value;
			return 1;
		}
	}
	return 0;
}

int hash_foreach (struct hash_table *table, hash_foreach_func func)
{
	int i;
	struct hash_bucket *bp, *next;
	int count = 0;

	if (!table)
		return 0;

	for (i = 0; i < table -> hash_count; i++) {
		bp = table -> buckets [i];
		while (bp) {
			next = bp -> next;
			if ((*func)(bp->name, bp->len, bp->value)
							!= ISC_R_SUCCESS)
				return count;
			bp = next;
			count++;
		}
	}
	return count;
}

int casecmp (const void *v1, const void *v2, size_t len)
{
	size_t i;
	const char *s = v1;
	const char *t = v2;
	
	for (i = 0; i < len; i++)
	{
		int c1, c2;
		if (isascii(s[i]))
			c1 = tolower(s[i]);
		else
			c1 = s[i];

		if (isascii(t[i]))
			c2 = tolower(t[i]);
		else
			c2 = t[i];

		if (c1 < c2)
			return -1;
		if (c1 > c2)
			return 1;
	}
	return 0;
}
Commit	Line	Data
d7837182 TL	1	/* hash.c
	2
	3	Routines for manipulating hash tables... */
	4
	5	/*
88cd8aca	6	* Copyright (c) 2004-2006 by Internet Systems Consortium, Inc. ("ISC")
98311e4b	7	* Copyright (c) 1995-2003 by Internet Software Consortium
d7837182	8	*
98311e4b DH	9	* Permission to use, copy, modify, and distribute this software for any
	10	* purpose with or without fee is hereby granted, provided that the above
	11	* copyright notice and this permission notice appear in all copies.
d7837182	12	*
98311e4b DH	13	* THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES
	14	* WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
	15	* MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR
	16	* ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
	17	* WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
	18	* ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT
	19	* OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
d7837182	20	*
98311e4b DH	21	* Internet Systems Consortium, Inc.
	22	* 950 Charter Street
	23	* Redwood City, CA 94063
	24	* <info@isc.org>
	25	* http://www.isc.org/
49733f31	26	*
98311e4b	27	* This software has been written for Internet Systems Consortium
49733f31	28	* by Ted Lemon in cooperation with Vixie Enterprises and Nominum, Inc.
98311e4b	29	* To learn more about Internet Systems Consortium, see
49733f31 TL	30	* ``http://www.isc.org/''. To learn more about Vixie Enterprises,
	31	* see ``http://www.vix.com''. To learn more about Nominum, Inc., see
	32	* ``http://www.nominum.com''.
d7837182 TL	33	*/
	34
	35	#ifndef lint
	36	static char copyright[] =
fe5b0fdd	37	"$Id: hash.c,v 1.14 2007/05/19 18:47:15 dhankins Exp $ Copyright (c) 2004-2006 Internet Systems Consortium. All rights reserved.\n";
d7837182 TL	38	#endif /* not lint */
d7837182 TL	39
fe5b0fdd DH	40	#include "dhcpd.h"
fe5b0fdd DH	41
c62871ba	42	#include <omapip/omapip_p.h>
fe5b0fdd	43	#include <limits.h>
7d9784f6	44	#include <ctype.h>
d7837182	45
fe5b0fdd	46	static unsigned
f7fdb216 DH	47	find_length(const void *key,
	48	unsigned (do_hash)(const void , unsigned, unsigned))
	49	{
	50	if (do_hash == do_case_hash \|\| do_hash == do_string_hash)
	51	return strlen((const char *)key);
	52	if (do_hash == do_number_hash)
	53	return sizeof(unsigned);
	54	if (do_hash == do_ip4_hash)
	55	return 4;
	56
	57	log_fatal("Impossible condition at %s:%d.", MDL);
d19e2cf7	58	return 0; /* Silence compiler warnings. */
f7fdb216	59	}
c62871ba	60
98311e4b DH	61	int new_hash_table (tp, count, file, line)
98311e4b DH	62	struct hash_table **tp;
f7fdb216	63	unsigned count;
c62871ba DN	64	const char *file;
	65	int line;
	66	{
98311e4b	67	struct hash_table *rval;
272ef1bc	68	unsigned extra;
98311e4b DH	69
	70	if (!tp) {
	71	log_error ("%s(%d): new_hash_table called with null pointer.",
	72	file, line);
	73	#if defined (POINTER_DEBUG)
	74	abort ();
	75	#endif
	76	return 0;
	77	}
	78	if (*tp) {
	79	log_error ("%s(%d): non-null target for new_hash_table.",
	80	file, line);
	81	#if defined (POINTER_DEBUG)
	82	abort ();
	83	#endif
	84	}
272ef1bc SK	85
	86	/* There is one hash bucket in the structure. Allocate extra
	87	* memory beyond the end of the structure to fulfill the requested
	88	* count ("count - 1"). Do not let there be less than one.
	89	*/
	90	if (count <= 1)
	91	extra = 0;
	92	else
	93	extra = count - 1;
	94
	95	rval = dmalloc(sizeof(struct hash_table) +
	96	(extra * sizeof(struct hash_bucket *)), file, line);
98311e4b DH	97	if (!rval)
98311e4b DH	98	return 0;
c62871ba	99	rval -> hash_count = count;
98311e4b DH	100	*tp = rval;
98311e4b DH	101	return 1;
c62871ba DN	102	}
c62871ba DN	103
98311e4b DH	104	void free_hash_table (tp, file, line)
98311e4b DH	105	struct hash_table **tp;
c62871ba DN	106	const char *file;
	107	int line;
	108	{
d758ad8c TL	109	int i;
d758ad8c TL	110	struct hash_bucket hbc, hbn = (struct hash_bucket *)0;
98311e4b	111	struct hash_table ptr = tp;
d758ad8c TL	112
	113	#if defined (DEBUG_MEMORY_LEAKAGE) \|\| \
	114	defined (DEBUG_MEMORY_LEAKAGE_ON_EXIT)
	115	for (i = 0; i < ptr -> hash_count; i++) {
	116	for (hbc = ptr -> buckets [i]; hbc; hbc = hbn) {
	117	hbn = hbc -> next;
	118	if (ptr -> dereferencer && hbc -> value)
	119	(*ptr -> dereferencer) (&hbc -> value, MDL);
	120	}
	121	for (hbc = ptr -> buckets [i]; hbc; hbc = hbn) {
	122	hbn = hbc -> next;
	123	free_hash_bucket (hbc, MDL);
	124	}
	125	ptr -> buckets [i] = (struct hash_bucket *)0;
	126	}
	127	#endif
	128
fe5b0fdd	129	dfree((void *)ptr, MDL);
98311e4b	130	tp = (struct hash_table )0;
c62871ba DN	131	}
	132
	133	struct hash_bucket *free_hash_buckets;
	134
d758ad8c TL	135	#if defined (DEBUG_MEMORY_LEAKAGE_ON_EXIT)
	136	struct hash_bucket *hash_bucket_hunks;
	137
	138	void relinquish_hash_bucket_hunks ()
	139	{
	140	struct hash_bucket c, n, **p;
	141
	142	/* Account for all the hash buckets on the free list. */
	143	p = &free_hash_buckets;
	144	for (c = free_hash_buckets; c; c = c -> next) {
	145	for (n = hash_bucket_hunks; n; n = n -> next) {
	146	if (c > n && c < n + 127) {
	147	*p = c -> next;
	148	n -> len++;
	149	break;
	150	}
	151	}
	152	/* If we didn't delete the hash bucket from the free list,
	153	advance the pointer. */
	154	if (!n)
	155	p = &c -> next;
	156	}
	157
	158	for (c = hash_bucket_hunks; c; c = n) {
	159	n = c -> next;
	160	if (c -> len != 126) {
	161	log_info ("hashbucket %lx hash_buckets %d free %u",
	162	(unsigned long)c, 127, c -> len);
	163	}
	164	dfree (c, MDL);
	165	}
	166	}
	167	#endif
	168
c62871ba DN	169	struct hash_bucket *new_hash_bucket (file, line)
	170	const char *file;
	171	int line;
	172	{
	173	struct hash_bucket *rval;
d758ad8c	174	int i = 0;
c62871ba DN	175	if (!free_hash_buckets) {
	176	rval = dmalloc (127 * sizeof (struct hash_bucket),
	177	file, line);
	178	if (!rval)
	179	return rval;
d758ad8c TL	180	# if defined (DEBUG_MEMORY_LEAKAGE_ON_EXIT)
	181	rval -> next = hash_bucket_hunks;
	182	hash_bucket_hunks = rval;
	183	hash_bucket_hunks -> len = 0;
	184	i++;
	185	rval++;
	186	#endif
	187	for (; i < 127; i++) {
c62871ba DN	188	rval -> next = free_hash_buckets;
	189	free_hash_buckets = rval;
	190	rval++;
	191	}
	192	}
	193	rval = free_hash_buckets;
	194	free_hash_buckets = rval -> next;
	195	return rval;
	196	}
	197
	198	void free_hash_bucket (ptr, file, line)
	199	struct hash_bucket *ptr;
	200	const char *file;
	201	int line;
	202	{
d758ad8c TL	203	struct hash_bucket *hp;
	204	#if defined (DEBUG_MALLOC_POOL)
	205	for (hp = free_hash_buckets; hp; hp = hp -> next) {
	206	if (hp == ptr) {
	207	log_error ("hash bucket freed twice!");
	208	abort ();
	209	}
	210	}
	211	#endif
c62871ba DN	212	ptr -> next = free_hash_buckets;
	213	free_hash_buckets = ptr;
	214	}
089fb364	215
f7fdb216 DH	216	int new_hash(struct hash_table **rp,
	217	hash_reference referencer,
	218	hash_dereference dereferencer,
	219	unsigned hsize,
	220	unsigned (hasher)(const void , unsigned, unsigned),
	221	const char *file, int line)
d7837182	222	{
f7fdb216 DH	223	if (hsize == 0)
	224	hsize = DEFAULT_HASH_SIZE;
	225
	226	if (!new_hash_table (rp, hsize, file, line))
98311e4b	227	return 0;
f7fdb216 DH	228
	229	memset ((rp)->buckets, 0, hsize sizeof(struct hash_bucket *));
	230
	231	(*rp)->referencer = referencer;
	232	(*rp)->dereferencer = dereferencer;
	233	(*rp)->do_hash = hasher;
	234
	235	if (hasher == do_case_hash)
	236	(*rp)->cmp = casecmp;
	237	else
	238	(*rp)->cmp = memcmp;
	239
98311e4b	240	return 1;
d7837182 TL	241	}
d7837182 TL	242
f7fdb216 DH	243	unsigned
f7fdb216 DH	244	do_case_hash(const void *name, unsigned len, unsigned size)
d7837182	245	{
f7fdb216 DH	246	register unsigned accum = 0;
f7fdb216 DH	247	register const unsigned char *s = name;
d7837182	248	int i = len;
7d9784f6 TL	249	register unsigned c;
	250
	251	while (i--) {
	252	/* Make the hash case-insensitive. */
	253	c = *s++;
f7fdb216 DH	254	if (isascii(c))
f7fdb216 DH	255	c = tolower(c);
7d9784f6 TL	256
7d9784f6 TL	257	/* Add the character in... */
d5ef2946 TL	258	accum = (accum << 1) + c;
d5ef2946 TL	259
7d9784f6	260	/* Add carry back in... */
d5ef2946 TL	261	while (accum > 65535) {
d5ef2946 TL	262	accum = (accum & 65535) + (accum >> 16);
7d9784f6	263	}
f7fdb216	264
7d9784f6 TL	265	}
	266	return accum % size;
	267	}
	268
f7fdb216 DH	269	unsigned
f7fdb216 DH	270	do_string_hash(const void *name, unsigned len, unsigned size)
7d9784f6	271	{
f7fdb216	272	register unsigned accum = 0;
7d9784f6 TL	273	register const unsigned char s = (const unsigned char )name;
	274	int i = len;
	275
34bef96b TL	276	while (i--) {
34bef96b TL	277	/* Add the character in... */
d5ef2946 TL	278	accum = (accum << 1) + *s++;
d5ef2946 TL	279
34bef96b	280	/* Add carry back in... */
d5ef2946 TL	281	while (accum > 65535) {
d5ef2946 TL	282	accum = (accum & 65535) + (accum >> 16);
d7837182 TL	283	}
	284	}
	285	return accum % size;
	286	}
	287
6708d944 DH	288	/* Client identifiers are generally 32-bits of ordinary
	289	* non-randomness followed by 24-bits of unordinary randomness.
	290	* So, end-align in 24-bit chunks, and xor any preceding data
	291	* just to mix it up a little.
	292	*/
	293	unsigned
	294	do_id_hash(const void *name, unsigned len, unsigned size)
	295	{
	296	register unsigned accum = 0;
	297	register const unsigned char s = (const unsigned char )name;
	298	const unsigned char *end = s + len;
	299
	300	if (len == 0)
	301	return 0;
	302
	303	/* The switch indexes our starting position into the do/while loop,
	304	* taking up the remainder after hashing in all the other bytes in
	305	* threes.
	306	*/
	307	switch (len % 3) {
	308	do {
	309	case 0:
	310	accum ^= *s++ << 16;
	311	case 2:
	312	accum ^= *s++ << 8;
	313	case 1:
	314	accum ^= *s++;
	315	} while (s < end);
	316
	317	break;
	318	}
	319
	320	return accum % size;
	321	}
	322
f7fdb216 DH	323	unsigned
	324	do_number_hash(const void *key, unsigned len, unsigned size)
	325	{
	326	register unsigned number = ((const unsigned )key);
	327
	328	return number % size;
	329	}
	330
	331	unsigned
	332	do_ip4_hash(const void *key, unsigned len, unsigned size)
	333	{
	334	u_int32_t number;
	335
	336	memcpy(&number, key, 4);
	337
	338	number = ntohl(number);
	339
	340	return number % size;
	341	}
	342
6708d944 DH	343	unsigned char *
	344	hash_report(struct hash_table *table)
	345	{
	346	static unsigned char retbuf[sizeof("Contents/Size (%): "
	347	"2147483647/2147483647 "
	348	"(2147483647%). "
	349	"Min/max: 2147483647/2147483647")];
	350	unsigned curlen, pct, contents=0, minlen=UINT_MAX, maxlen=0;
	351	unsigned i;
	352	struct hash_bucket *bp;
	353
	354	if (table->hash_count == 0)
	355	return "Invalid hash table.";
	356
	357	for (i = 0 ; i < table->hash_count ; i++) {
	358	curlen = 0;
	359
	360	bp = table->buckets[i];
	361	while (bp != NULL) {
	362	curlen++;
	363	bp = bp->next;
	364	}
	365
	366	if (curlen < minlen)
	367	minlen = curlen;
	368	if (curlen > maxlen)
	369	maxlen = curlen;
	370
	371	contents += curlen;
	372	}
	373
	374	if (contents >= (UINT_MAX / 100))
	375	pct = contents / ((table->hash_count / 100) + 1);
	376	else
	377	pct = (contents * 100) / table->hash_count;
	378
	379	if (contents > 2147483647 \|\|
	380	table->hash_count > 2147483647 \|\|
	381	pct > 2147483647 \|\|
	382	minlen > 2147483647 \|\|
	383	maxlen > 2147483647)
	384	return "Report out of range for display.";
	385
	386	sprintf(retbuf, "Contents/Size (%%): %u/%u (%u%%). Min/max: %u/%u",
	387	contents, table->hash_count, pct, minlen, maxlen);
	388
	389	return retbuf;
	390	}
	391
f7fdb216	392	void add_hash (table, key, len, pointer, file, line)
d7837182	393	struct hash_table *table;
b1b7b521	394	unsigned len;
f7fdb216	395	const void *key;
20916cae TL	396	hashed_object_t *pointer;
	397	const char *file;
	398	int line;
d7837182	399	{
a0330332 TL	400	int hashno;
a0330332 TL	401	struct hash_bucket *bp;
0cae26a7	402	void *foo;
a0330332 TL	403
	404	if (!table)
	405	return;
	406
48036271	407	if (!len)
f7fdb216	408	len = find_length(key, table->do_hash);
48036271	409
f7fdb216	410	hashno = (*table->do_hash)(key, len, table->hash_count);
20916cae	411	bp = new_hash_bucket (file, line);
a0330332	412
d7837182	413	if (!bp) {
f7fdb216	414	log_error ("Can't add entry to hash table: no memory.");
d7837182 TL	415	return;
d7837182 TL	416	}
f7fdb216	417	bp -> name = key;
0cae26a7 TL	418	if (table -> referencer) {
0cae26a7 TL	419	foo = &bp -> value;
20916cae	420	(*(table -> referencer)) (foo, pointer, file, line);
0cae26a7 TL	421	} else
0cae26a7 TL	422	bp -> value = pointer;
d7837182	423	bp -> next = table -> buckets [hashno];
97ca1699	424	bp -> len = len;
d7837182 TL	425	table -> buckets [hashno] = bp;
	426	}
	427
f7fdb216	428	void delete_hash_entry (table, key, len, file, line)
d7837182	429	struct hash_table *table;
b1b7b521	430	unsigned len;
f7fdb216	431	const void *key;
20916cae TL	432	const char *file;
20916cae TL	433	int line;
d7837182	434	{
a0330332	435	int hashno;
d7837182	436	struct hash_bucket bp, pbp = (struct hash_bucket *)0;
0cae26a7	437	void *foo;
d7837182	438
a0330332 TL	439	if (!table)
	440	return;
	441
48036271	442	if (!len)
f7fdb216	443	len = find_length(key, table->do_hash);
48036271	444
f7fdb216	445	hashno = (*table->do_hash)(key, len, table->hash_count);
a0330332	446
d7837182 TL	447	/* Go through the list looking for an entry that matches;
	448	if we find it, delete it. */
	449	for (bp = table -> buckets [hashno]; bp; bp = bp -> next) {
69858972	450	if ((!bp -> len &&
f7fdb216	451	!strcmp ((const char *)bp->name, key)) \|\|
d7837182	452	(bp -> len == len &&
f7fdb216	453	!(table -> cmp)(bp->name, key, len))) {
d7837182 TL	454	if (pbp) {
	455	pbp -> next = bp -> next;
	456	} else {
	457	table -> buckets [hashno] = bp -> next;
	458	}
d758ad8c	459	if (bp -> value && table -> dereferencer) {
0cae26a7	460	foo = &bp -> value;
20916cae	461	(*(table -> dereferencer)) (foo, file, line);
0cae26a7	462	}
20916cae	463	free_hash_bucket (bp, file, line);
d7837182 TL	464	break;
d7837182 TL	465	}
4c4c7907	466	pbp = bp; /* jwg, 9/6/96 - nice catch! */
d7837182 TL	467	}
	468	}
	469
f7fdb216	470	int hash_lookup (vp, table, key, len, file, line)
20916cae	471	hashed_object_t **vp;
d7837182	472	struct hash_table *table;
f7fdb216	473	const void *key;
b1b7b521	474	unsigned len;
20916cae TL	475	const char *file;
20916cae TL	476	int line;
d7837182	477	{
a0330332	478	int hashno;
d7837182 TL	479	struct hash_bucket *bp;
d7837182 TL	480
a0330332	481	if (!table)
20916cae	482	return 0;
48036271	483	if (!len)
f7fdb216	484	len = find_length(key, table->do_hash);
48036271	485
272ef1bc SK	486	if (*vp != NULL) {
	487	log_fatal("Internal inconsistency: storage value has not been "
	488	"initialized to zero (from %s:%d).", file, line);
	489	}
	490
f7fdb216	491	hashno = (*table->do_hash)(key, len, table->hash_count);
a0330332	492
48036271 TL	493	for (bp = table -> buckets [hashno]; bp; bp = bp -> next) {
48036271 TL	494	if (len == bp -> len
f7fdb216	495	&& !(*table->cmp)(bp->name, key, len)) {
20916cae TL	496	if (table -> referencer)
	497	(*table -> referencer) (vp, bp -> value,
	498	file, line);
	499	else
	500	*vp = bp -> value;
	501	return 1;
	502	}
d7837182	503	}
20916cae	504	return 0;
d7837182 TL	505	}
d7837182 TL	506
d0411fbd TL	507	int hash_foreach (struct hash_table *table, hash_foreach_func func)
	508	{
	509	int i;
	510	struct hash_bucket bp, next;
	511	int count = 0;
	512
	513	if (!table)
	514	return 0;
	515
	516	for (i = 0; i < table -> hash_count; i++) {
	517	bp = table -> buckets [i];
	518	while (bp) {
	519	next = bp -> next;
06e77c34 DH	520	if ((*func)(bp->name, bp->len, bp->value)
	521	!= ISC_R_SUCCESS)
	522	return count;
d0411fbd TL	523	bp = next;
	524	count++;
	525	}
	526	}
	527	return count;
	528	}
	529
d19e2cf7	530	int casecmp (const void v1, const void v2, size_t len)
7d9784f6	531	{
d19e2cf7	532	size_t i;
7d9784f6 TL	533	const char *s = v1;
	534	const char *t = v2;
	535
	536	for (i = 0; i < len; i++)
	537	{
	538	int c1, c2;
d19e2cf7 DH	539	if (isascii(s[i]))
d19e2cf7 DH	540	c1 = tolower(s[i]);
7d9784f6	541	else
d19e2cf7 DH	542	c1 = s[i];
	543
	544	if (isascii(t[i]))
	545	c2 = tolower(t[i]);
7d9784f6	546	else
d19e2cf7 DH	547	c2 = t[i];
d19e2cf7 DH	548
7d9784f6 TL	549	if (c1 < c2)
	550	return -1;
	551	if (c1 > c2)
	552	return 1;
	553	}
	554	return 0;
	555	}