dmake/hash.c

   1 /* RCS  $Id: hash.c,v 1.2 2006-09-25 09:39:55 vg Exp $
   2 --
   3 -- SYNOPSIS
   4 --      Hashing function for hash tables.
   5 --
   6 -- DESCRIPTION
   7 --      Hash an identifier.  The hashing function works by computing the sum
   8 --      of each char and the previous hash value multiplied by 129.  Finally the
   9 --      length of the identifier is added in.  This way the hash depends on the
  10 --      chars as well as the length, and appears to be sufficiently unique,
  11 --      and is FAST to COMPUTE, unlike the previous hash function...
  12 --
  13 -- AUTHOR
  14 --      Dennis Vadura, dvadura@dmake.wticorp.com
  15 --
  16 -- WWW
  17 --      http://dmake.wticorp.com/
  18 --
  19 -- COPYRIGHT
  20 --      Copyright (c) 1996,1997 by WTI Corp.  All rights reserved.
  21 --
  22 --      This program is NOT free software; you can redistribute it and/or
  23 --      modify it under the terms of the Software License Agreement Provided
  24 --      in the file <distribution-root>/readme/license.txt.
  25 --
  26 -- LOG
  27 --      Use cvs log to obtain detailed change logs.
  28 */
  29
  30 #include "extern.h"
  31
  32 PUBLIC uint16
  33 Hash( id, phv )/*
  34 =================
  35       This function computes the identifier's hash value and returns the hash
  36       value modulo the key size as well as the full hash value.  The reason
  37       for returning both is so that hash table searches can be sped up.  You
  38       compare hash keys instead and compare strings only for those whose 32-bit
  39       hash keys match. (not many) */
  40
  41 char   *id;  /* value */
  42 uint32 *phv; /* key */
  43 {
  44    register char   *p    = id;
  45    register uint32 hash  = (uint32) 0;
  46
  47    while( *p ) hash = (hash << 7) + hash + (uint32) (*p++);
  48    *phv = hash = hash + (uint32) (p-id);
  49
  50    /* return an index (for Macs[]) where all keys with the same remainder
  51     * after integer division with HASH_TABLE_SIZE are stored. */
  52    return( (uint16) (hash % HASH_TABLE_SIZE) );
  53 }
  54