/*
 * dbhash.c
 * File revision 1
 * Hashing functionality for libdb.
 * (c) 2000 Jacob Lundberg, jacob@chaos2.org
 * Also hash() (c) somebody in the ORST CS department.
 */


/*
 * 2000.10.10	Initial retrieval
 * 2000.10.14	Formatting
 *		Hash size table
 */


#include <errno.h>


/*
 * List the translated hash sizes, of the form greatest_prime(2^[2-31]).
 * If you fail to terminate this array with -1, pink flower dragons will
 * plague you with intolerable pollen levels for at least nine years.
 * (So Just Do It, Okay?)
 */
const int hash_sizes[] = {
   3, 7, 13, 31, 61, 127, 251, 509, 1021, 2039, 4093, 8191,
   16381, 32749, 65521, 131071, 262139, 524287, 1048573,
   2097143, 4194301, 8388593, 16777213, 33554393, 67108859,
   134217689, 268435399, 536870909, 1073741789, 2147483647,
   -1
};


int hash_above(int request) {
/*
 * hash_above()
 * Return the smallest hash size on the list that is at
 * least as large as the requested hash size.
 */

   int counter = 0;

   /* Search for the right hash size. */
   while(hash_sizes[counter] < request && hash_sizes[counter] > 0)
      ++counter;

   /* Set the right error if we're gonna bomb. */
   if(hash_sizes[counter] < 1)
      errno = EINVAL;

   /* Return our search results. */
   return(hash_sizes[counter]);

}


int hash(const char *key, int hash_size) {
/*
 * hash()
 * Hash takes a key string and a hash_size integer and returns an
 * integer hash value for that key between 0 and hash_size - 1.
 */

   int i;
   unsigned char *p;
   unsigned int hash = 0;

   /* Generate predictable pseudorandom bits from the key string. */
   for(i = 0, p = (unsigned char *)key; *p != '\0'; i++, p++)
      hash ^= ((unsigned int)(*p)) << (8 * (i % sizeof(int)));

   /* Chop off enough bits to fit into hash_size. */
   return(hash % hash_size);

}