Listing 5 Hashing the Keys

/*>>>>>>>>>>>> Default hash function <<<<<<<<<<<<<<<*/
static int hash_function(key,keysize,maxhash,type)
void *key;        /* input -- key to be hashed */
int keysize;      /* input -- size of key */
int maxhash;      /* input -- max legal hash value */
enum AA_KEYTYPE type; /* input -- type of input key */
{
  int i;
  static shifts_initialized=FALSE;
  static BYTE svalues[]={0,24,3,21,5,19,7,17,9,15,11};
  static BYTE sconstants[AA_MAX_KEY_SIZE];
  register unsigned long count=0;
  register BYTE *kp=(BYTE *)key, *end;
  register BYTE *shifts=sconstants;

  /* on 1st call init shifts; empirically determined */
  if (!shifts_initialized) {
     for(i=0; i < AA_MAX_KEY_SIZE; i++)
        sconstants[i]=svalues[i % sizeof(svalues)];
     shifts_initialized=TRUE;
  }
  
  /* the loops are high runners; need to be fast */
  if (type == STRING_KEY)
     for ( ; *kp != (char) 0; kp++,shifts++)
        count ^= *kp << *shifts;
  else
     for (end=kp+keysize; kp < end; kp++,shifts++)
        count ^= *kp << *shifts;
  return (count % maxhash); /* return hash value */
}

/*>>> Find index for key; Use hash algorithm.  <<<*/
/*>>> Method: Linear Probe with Double Hashing <<<*/
static int hashindex (aa,key)
AA * aa;        /* input -- AA definition */
void *key;      /* input -- lookup key */
{
  int found=FALSE, index;
  void **ptr;
  BOOLEAN first_collision=TRUE;
  
  /* hash function determines where to start search */
  index=HASH_FUNCTION(aa, key, aa ->max_elements);
  
  do {  /* do until matching key or empty slot found */
     ptr=&aa->keys[index];  /* get key pointer */
     
     if (NULLKEY(*ptr))
        found=TRUE; /* empty slot */
     /* keys comparisons must consider the key type */
     else if (STRING_KEY_MATCH(aa->type,key,ptr))
        found=TRUE; /* string key found */
     else if (KEY_MATCH(aa->type,key,ptr,aa->key_size))
        found=TRUE; /* non-string key found */
     /* wrong key was found so collision occurred */
     else if (first_collision) {
        /* try double hash on first collision only */
        index=HASH_FUNCTION(aa,key,aa->max_elements-4);
        first_collision=FALSE;
     } else /* collision -- use linear search/probe */
        if (++index == aa->max_elements) /* if end */
          index=0;  /* restart search at beginning */
  } while (!found);
  
  return(index);  /* return key and data index */
}

/* End of File */