home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / dmake40.zip / hash.c < prev    next >
C/C++ Source or Header  |  1994-10-23  |  2KB  |  62 lines
  1. /* RCS      -- $Header: /u5/dvadura/src/public/dmake/src/RCS/hash.c,v 1.1 1994/10/06 17:41:26 dvadura Exp $
  2. -- SYNOPSIS -- hashing function for hash tables.
  3. -- 
  4. -- DESCRIPTION
  5. --      Hash an identifier.  The hashing function works by computing the sum
  6. --      of each char and the previous hash value multiplied by 129.  Finally the
  7. --      length of the identifier is added in.  This way the hash depends on the
  8. --      chars as well as the length, and appears to be sufficiently unique,
  9. --      and is FAST to COMPUTE, unlike the previous hash function...
  10. -- 
  11. -- AUTHOR
  12. --      Dennis Vadura, dvadura@watdragon.uwaterloo.ca
  13. --      CS DEPT, University of Waterloo, Waterloo, Ont., Canada
  14. --
  15. -- COPYRIGHT
  16. --      Copyright (c) 1992,1994 by Dennis Vadura.  All rights reserved.
  17. -- 
  18. --      This program is free software; you can redistribute it and/or
  19. --      modify it under the terms of the GNU General Public License
  20. --      (version 1), as published by the Free Software Foundation, and
  21. --      found in the file 'LICENSE' included with this distribution.
  22. -- 
  23. --      This program is distributed in the hope that it will be useful,
  24. --      but WITHOUT ANY WARRANTY; without even the implied warrant of
  25. --      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  26. --      GNU General Public License for more details.
  27. -- 
  28. --      You should have received a copy of the GNU General Public License
  29. --      along with this program;  if not, write to the Free Software
  30. --      Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  31. --
  32. -- LOG
  33. --     $Log: hash.c,v $
  34.  * Revision 1.1  1994/10/06  17:41:26  dvadura
  35.  * dmake Release Version 4.0, Initial revision
  36.  *
  37. */
  38.  
  39. #include "extern.h"
  40.  
  41. PUBLIC uint16
  42. Hash( id, phv )/*
  43. =================
  44.       This function computes the identifier's hash value and returns the hash
  45.       value modulo the key size as well as the full hash value.  The reason
  46.       for returning both is so that hash table searches can be sped up.  You
  47.       compare hash keys instead and compare strings only for those whose 32-bit
  48.       hash keys match. (not many) */
  49.  
  50. char   *id;
  51. uint32 *phv;
  52. {
  53.    register char   *p    = id;
  54.    register uint32 hash  = (uint32) 0;
  55.  
  56.    while( *p ) hash = (hash << 7) + hash + (uint32) (*p++);
  57.    *phv = hash = hash + (uint32) (p-id);
  58.  
  59.    return( (uint16) (hash % HASH_TABLE_SIZE) );
  60. }
  61.  
  62.