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. */
Hash_Table(unsigned int size,bool ignore_length)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. */
~Hash_Table()86 Hash_Table::~Hash_Table ()
87 {
88 delete[] _table;
89 }
90
91 /* Print the table's contents. */
92 void
dump() const93 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
equal(KeywordExt * item1,KeywordExt * item2) const129 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 *
insert(KeywordExt * item)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 }
168