text: /* hash.c
  
     Routines for manipulating hash tables... */
  
  /*
   * Copyright (c) 2009-2010,2014 by Internet Systems Consortium, Inc. ("ISC")
   * Copyright (c) 2004-2007 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>
   *   https://www.isc.org/
   *
   */
  
  #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_debug("Unexpected hash function at %s:%d.", MDL);
  	/*
  	 * If we get a hash function we don't specifically expect
  	 * return a length of 0, this covers the case where a client
  	 * id has a length of 0.
  	 */
  	return 0;
  }
  
  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;
  {
  	struct hash_table *ptr = *tp;
  
  #if defined (DEBUG_MEMORY_LEAKAGE) || \
  		defined (DEBUG_MEMORY_LEAKAGE_ON_EXIT)
  	int i;
  	struct hash_bucket *hbc, *hbn = (struct hash_bucket *)0;
  
  	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;
  {
  #if defined (DEBUG_MALLOC_POOL)
  	struct hash_bucket *hp;
  
  	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 handles our starting conditions, then we hash the
  	 * remaining bytes in groups of 3
  	 */
  	   
  	switch (len % 3) {
  	case 0:
  		break;
  	case 2:
  		accum ^= *s++ << 8;
  	case 1:
  		accum ^= *s++;
  		break;
  	}
  
  	while (s < end) {
  		accum ^= *s++ << 16;
  		accum ^= *s++ << 8;
  		accum ^= *s++;
  	}
  
  	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 == NULL)
  		return (unsigned char *) "No table.";
  
  	if (table->hash_count == 0)
  		return (unsigned char *) "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 (unsigned char *) "Report out of range for display.";
  
  	sprintf((char *)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 unsigned char *s = v1;
  	const unsigned 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;
  }
  