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.  */
36static 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.  */
43Hash_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.  */
86Hash_Table::~Hash_Table ()
87{
88  delete[] _table;
89}
90
91/* Print the table's contents.  */
92void
93Hash_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.  */
128inline bool
129Hash_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.  */
141KeywordExt *
142Hash_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}
168