home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Source Code 1993 July / THE_SOURCE_CODE_CD_ROM.iso / gnu / cperf-2.1 / src / hashtable.c < prev    next >
Encoding:
C/C++ Source or Header  |  1989-11-11  |  3.9 KB  |  133 lines
  1. /* Hash table for checking keyword links.  Implemented using double hashing.
  2.    Copyright (C) 1989 Free Software Foundation, Inc.
  3.    written by Douglas C. Schmidt (schmidt@ics.uci.edu)
  4.  
  5. This file is part of GNU GPERF.
  6.  
  7. GNU GPERF is free software; you can redistribute it and/or modify
  8. it under the terms of the GNU General Public License as published by
  9. the Free Software Foundation; either version 1, or (at your option)
  10. any later version.
  11.  
  12. GNU GPERF is distributed in the hope that it will be useful,
  13. but WITHOUT ANY WARRANTY; without even the implied warranty of
  14. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15. GNU General Public License for more details.
  16.  
  17. You should have received a copy of the GNU General Public License
  18. along with GNU GPERF; see the file COPYING.  If not, write to
  19. the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
  20.  
  21. #include <stdio.h>
  22. #include "hashtable.h"
  23. #include "options.h"
  24.  
  25. #ifdef GATHER_STATISTICS
  26. /* Find out how well our double hashing is working! */
  27. static collisions = 0;
  28. #endif
  29.  
  30. /* Locally visible hash table. */
  31. static HASH_TABLE hash_table;
  32.  
  33. /* Basically the algorithm from the Dragon book. */
  34.  
  35. static unsigned
  36. hash_pjw (str)
  37.      char *str;
  38. {
  39.   char    *temp;
  40.   unsigned g, h = 0;
  41.    
  42.   for (temp = str; *temp; temp++) 
  43.     {
  44.       h = (h << 4) + (*temp * 13);
  45.       if (g = h & 0xf0000000) 
  46.         {
  47.           h ^= (g >> 24);
  48.           h ^= g;
  49.         }
  50.     }
  51.  
  52.   return h;
  53. }
  54.  
  55. /* The size of the hash table is always the smallest power of 2 >= the size
  56.    indicated by the user.  This allows several optimizations, including
  57.    the use of double hashing and elimination of the mod instruction.
  58.    Note that the size had better be larger than the number of items
  59.    in the hash table, else there's trouble!!!  Note that the memory
  60.    for the hash table is allocated *outside* the intialization routine.
  61.    This compromises information hiding somewhat, but greatly reduces
  62.    memory fragmentation, since we can now use alloca! */
  63.  
  64. void
  65. hash_table_init (table, s)
  66.      LIST_NODE **table;
  67.      int s;
  68. {
  69.   hash_table.size  = s;
  70.   hash_table.table = table;
  71.   bzero ((char *) hash_table.table, hash_table.size * sizeof *hash_table.table);
  72. }
  73.  
  74. /* Frees the dynamically allocated table.  Note that since we don't
  75.    really need this space anymore, and since it is potentially quite
  76.    big it is best to return it when we are done. */
  77.  
  78. void
  79. hash_table_destroy ()
  80. { 
  81.   if (OPTION_ENABLED (option, DEBUG))
  82.     {
  83.       int i;
  84.  
  85.       fprintf (stderr, "\ndumping the hash table\ntotal elements = %d, bytes = %d\n",
  86.                hash_table.size, hash_table.size * sizeof *hash_table.table);
  87.     
  88.       for (i = hash_table.size - 1; i >= 0; i--)
  89.         if (hash_table.table[i])
  90.           fprintf (stderr, "location[%d] has charset \"%s\" and keyword \"%s\"\n",
  91.                    i, hash_table.table[i]->char_set, hash_table.table[i]->key);
  92.  
  93. #ifdef GATHER_STATISTICS
  94.       fprintf (stderr, "\ntotal collisions during hashing = %d\n", collisions);
  95. #endif
  96.       fprintf (stderr, "end dumping hash table\n\n");
  97.     }
  98. }
  99.  
  100. /* If the ITEM is already in the hash table return the item found
  101.    in the table.  Otherwise inserts the ITEM, and returns FALSE.
  102.    Uses double hashing. */
  103.  
  104. LIST_NODE *
  105. retrieve (item, ignore_length)
  106.      LIST_NODE *item;
  107.      int        ignore_length;
  108. {
  109.   unsigned hash_val  = hash_pjw (item->char_set);
  110.   int      probe     = hash_val & hash_table.size - 1;
  111.   int      increment = (hash_val ^ item->length | 1) & hash_table.size - 1;
  112.   
  113.   while (hash_table.table[probe]
  114.          && (strcmp (hash_table.table[probe]->char_set, item->char_set)
  115.              || (!ignore_length && hash_table.table[probe]->length != item->length)))
  116.     {
  117. #ifdef GATHER_STATISTICS
  118.       collisions++;
  119. #endif
  120.       probe = probe + increment & hash_table.size - 1;
  121.     }
  122.  
  123.   if (hash_table.table[probe])
  124.     return hash_table.table[probe];
  125.   else
  126.     {
  127.       hash_table.table[probe] = item;
  128.       return 0;
  129.     }
  130. }
  131.  
  132.  
  133.