contrib/gperf/src/hash-table.cc

   1 /* Hash table for checking keyword links.  Implemented using double hashing.
   2    Copyright (C) 1989-1998, 2000, 2002 Free Software Foundation, Inc.
   3    Written by Douglas C. Schmidt <schmidt@ics.uci.edu>
   4    and Bruno Haible <bruno@clisp.org>.
   5
   6    This file is part of GNU GPERF.
   7
   8    GNU GPERF is free software; you can redistribute it and/or modify
   9    it under the terms of the GNU General Public License as published by
  10    the Free Software Foundation; either version 2, or (at your option)
  11    any later version.
  12
  13    GNU GPERF is distributed in the hope that it will be useful,
  14    but WITHOUT ANY WARRANTY; without even the implied warranty of
  15    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16    GNU General Public License for more details.
  17
  18    You should have received a copy of the GNU General Public License
  19    along with this program; see the file COPYING.
  20    If not, write to the Free Software Foundation, Inc.,
  21    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
  22
  23 /* Specification. */
  24 #include "hash-table.h"
  25
  26 #include <stdio.h>
  27 #include <string.h> /* declares memset(), strcmp() */
  28 #include <hash.h>
  29 #include "options.h"
  30
  31 /* We use a hash table with double hashing.  This is the simplest kind of
  32    hash table, given that we always only insert and never remove entries
  33    from the hash table.  */
  34
  35 /* To make double hashing efficient, there need to be enough spare entries.  */
  36 static const int size_factor = 10;
  37
  38 /* We make the size of the hash table a power of 2.  This allows for two
  39    optimizations: It eliminates the modulo instruction, and allows for an
  40    easy secondary hashing function.  */
  41
  42 /* Constructor.  */
  43 Hash_Table::Hash_Table (unsigned int size, bool ignore_length)
  44   : _ignore_length (ignore_length),
  45     _collisions (0)
  46 {
  47   /* There need to be enough spare entries.  */
  48   size = size * size_factor;
  49
  50   /* Find smallest power of 2 that is >= size.  */
  51   unsigned int shift = 0;
  52   if ((size >> 16) > 0)
  53     {
  54       size = size >> 16;
  55       shift += 16;
  56     }
  57   if ((size >> 8) > 0)
  58     {
  59       size = size >> 8;
  60       shift += 8;
  61     }
  62   if ((size >> 4) > 0)
  63     {
  64       size = size >> 4;
  65       shift += 4;
  66     }
  67   if ((size >> 2) > 0)
  68     {
  69       size = size >> 2;
  70       shift += 2;
  71     }
  72   if ((size >> 1) > 0)
  73     {
  74       size = size >> 1;
  75       shift += 1;
  76     }
  77   _log_size = shift;
  78   _size = 1 << shift;
  79
  80   /* Allocate table.  */
  81   _table = new KeywordExt*[_size];
  82   memset (_table, 0, _size * sizeof (*_table));
  83 }
  84
  85 /* Destructor.  */
  86 Hash_Table::~Hash_Table ()
  87 {
  88   delete[] _table;
  89 }
  90
  91 /* Print the table's contents.  */
  92 void
  93 Hash_Table::dump () const
  94 {
  95   int field_width;
  96
  97   field_width = 0;
  98   {
  99     for (int i = _size - 1; i >= 0; i--)
 100       if (_table[i])
 101         if (field_width < _table[i]->_selchars_length)
 102           field_width = _table[i]->_selchars_length;
 103   }
 104
 105   fprintf (stderr,
 106            "\ndumping the hash table\n"
 107            "total available table slots = %d, total bytes = %d, total collisions = %d\n"
 108            "location, %*s, keyword\n",
 109            _size, _size * static_cast<unsigned int>(sizeof (*_table)),
 110            _collisions, field_width, "keysig");
 111
 112   for (int i = _size - 1; i >= 0; i--)
 113     if (_table[i])
 114       {
 115         fprintf (stderr, "%8d, ", i);
 116         if (field_width > _table[i]->_selchars_length)
 117           fprintf (stderr, "%*s", field_width - _table[i]->_selchars_length, "");
 118         for (int j = 0; j < _table[i]->_selchars_length; j++)
 119           putc (_table[i]->_selchars[j], stderr);
 120         fprintf (stderr, ", %.*s\n",
 121                  _table[i]->_allchars_length, _table[i]->_allchars);
 122       }
 123
 124   fprintf (stderr, "\nend dumping hash table\n\n");
 125 }
 126
 127 /* Compares two items.  */
 128 inline bool
 129 Hash_Table::equal (KeywordExt *item1, KeywordExt *item2) const
 130 {
 131   return item1->_selchars_length == item2->_selchars_length
 132          && memcmp (item1->_selchars, item2->_selchars,
 133                     item2->_selchars_length * sizeof (unsigned int))
 134             == 0
 135          && (_ignore_length
 136              || item1->_allchars_length == item2->_allchars_length);
 137 }
 138
 139 /* Attempts to insert ITEM in the table.  If there is already an equal
 140    entry in it, returns it.  Otherwise inserts ITEM and returns NULL.  */
 141 KeywordExt *
 142 Hash_Table::insert (KeywordExt *item)
 143 {
 144   unsigned hash_val =
 145     hashpjw (reinterpret_cast<const unsigned char *>(item->_selchars),
 146              item->_selchars_length * sizeof (unsigned int));
 147   unsigned int probe = hash_val & (_size - 1);
 148   unsigned int increment =
 149     (((hash_val >> _log_size)
 150       ^ (_ignore_length ? 0 : item->_allchars_length))
 151      << 1) + 1;
 152   /* Note that because _size is a power of 2 and increment is odd,
 153      we have gcd(increment,_size) = 1, which guarantees that we'll find
 154      an empty entry during the loop.  */
 155
 156   while (_table[probe] != NULL)
 157     {
 158       if (equal (_table[probe], item))
 159         return _table[probe];
 160
 161       _collisions++;
 162       probe = (probe + increment) & (_size - 1);
 163     }
 164
 165   _table[probe] = item;
 166   return NULL;
 167 }