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>.
6 This file is part of GNU GPERF.
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)
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.
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. */
24 #include "hash-table.h"
27 #include <string.h> /* declares memset(), strcmp() */
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. */
35 /* To make double hashing efficient, there need to be enough spare entries. */
36 static const int size_factor = 10;
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. */
43 Hash_Table::Hash_Table (unsigned int size, bool ignore_length)
44 : _ignore_length (ignore_length),
47 /* There need to be enough spare entries. */
48 size = size * size_factor;
50 /* Find smallest power of 2 that is >= size. */
51 unsigned int shift = 0;
81 _table = new KeywordExt*[_size];
82 memset (_table, 0, _size * sizeof (*_table));
86 Hash_Table::~Hash_Table ()
91 /* Print the table's contents. */
93 Hash_Table::dump () const
99 for (int i = _size - 1; i >= 0; i--)
101 if (field_width < _table[i]->_selchars_length)
102 field_width = _table[i]->_selchars_length;
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");
112 for (int i = _size - 1; i >= 0; i--)
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);
124 fprintf (stderr, "\nend dumping hash table\n\n");
127 /* Compares two items. */
129 Hash_Table::equal (KeywordExt *item1, KeywordExt *item2) const
131 return item1->_selchars_length == item2->_selchars_length
132 && memcmp (item1->_selchars, item2->_selchars,
133 item2->_selchars_length * sizeof (unsigned int))
136 || item1->_allchars_length == item2->_allchars_length);
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. */
142 Hash_Table::insert (KeywordExt *item)
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))
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. */
156 while (_table[probe] != NULL)
158 if (equal (_table[probe], item))
159 return _table[probe];
162 probe = (probe + increment) & (_size - 1);
165 _table[probe] = item;