Line data    Source code

       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     1976977 : 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     1976977 :    register char   *p    = id;
      45     1976977 :    register uint32 hash  = (uint32) 0;
      46             : 
      47     1976977 :    while( *p ) hash = (hash << 7) + hash + (uint32) (*p++);
      48     1976977 :    *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     1976977 :    return( (uint16) (hash % HASH_TABLE_SIZE) );
      53             : }
      54             :