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 This program 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 3 of the License, or 11 (at your option) any later version. 12 13 This program 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. If not, see <http://www.gnu.org/licenses/>. */ 20 21/* Specification. */ 22#include "hash-table.h" 23 24#include <stdio.h> 25#include <string.h> /* declares memset(), strcmp() */ 26#include <hash.h> 27#include "options.h" 28 29/* We use a hash table with double hashing. This is the simplest kind of 30 hash table, given that we always only insert and never remove entries 31 from the hash table. */ 32 33/* To make double hashing efficient, there need to be enough spare entries. */ 34static const int size_factor = 10; 35 36/* We make the size of the hash table a power of 2. This allows for two 37 optimizations: It eliminates the modulo instruction, and allows for an 38 easy secondary hashing function. */ 39 40/* Constructor. */ 41Hash_Table::Hash_Table (unsigned int size, bool ignore_length) 42 : _ignore_length (ignore_length), 43 _collisions (0) 44{ 45 /* There need to be enough spare entries. */ 46 size = size * size_factor; 47 48 /* Find smallest power of 2 that is >= size. */ 49 unsigned int shift = 0; 50 if ((size >> 16) > 0) 51 { 52 size = size >> 16; 53 shift += 16; 54 } 55 if ((size >> 8) > 0) 56 { 57 size = size >> 8; 58 shift += 8; 59 } 60 if ((size >> 4) > 0) 61 { 62 size = size >> 4; 63 shift += 4; 64 } 65 if ((size >> 2) > 0) 66 { 67 size = size >> 2; 68 shift += 2; 69 } 70 if ((size >> 1) > 0) 71 { 72 size = size >> 1; 73 shift += 1; 74 } 75 _log_size = shift; 76 _size = 1 << shift; 77 78 /* Allocate table. */ 79 _table = new KeywordExt*[_size]; 80 memset (_table, 0, _size * sizeof (*_table)); 81} 82 83/* Destructor. */ 84Hash_Table::~Hash_Table () 85{ 86 delete[] _table; 87} 88 89/* Print the table's contents. */ 90void 91Hash_Table::dump () const 92{ 93 int field_width; 94 95 field_width = 0; 96 { 97 for (int i = _size - 1; i >= 0; i--) 98 if (_table[i]) 99 if (field_width < _table[i]->_selchars_length) 100 field_width = _table[i]->_selchars_length; 101 } 102 103 fprintf (stderr, 104 "\ndumping the hash table\n" 105 "total available table slots = %d, total bytes = %d, total collisions = %d\n" 106 "location, %*s, keyword\n", 107 _size, _size * static_cast<unsigned int>(sizeof (*_table)), 108 _collisions, field_width, "keysig"); 109 110 for (int i = _size - 1; i >= 0; i--) 111 if (_table[i]) 112 { 113 fprintf (stderr, "%8d, ", i); 114 if (field_width > _table[i]->_selchars_length) 115 fprintf (stderr, "%*s", field_width - _table[i]->_selchars_length, ""); 116 for (int j = 0; j < _table[i]->_selchars_length; j++) 117 putc (_table[i]->_selchars[j], stderr); 118 fprintf (stderr, ", %.*s\n", 119 _table[i]->_allchars_length, _table[i]->_allchars); 120 } 121 122 fprintf (stderr, "\nend dumping hash table\n\n"); 123} 124 125/* Compares two items. */ 126inline bool 127Hash_Table::equal (KeywordExt *item1, KeywordExt *item2) const 128{ 129 return item1->_selchars_length == item2->_selchars_length 130 && memcmp (item1->_selchars, item2->_selchars, 131 item2->_selchars_length * sizeof (unsigned int)) 132 == 0 133 && (_ignore_length 134 || item1->_allchars_length == item2->_allchars_length); 135} 136 137/* Attempts to insert ITEM in the table. If there is already an equal 138 entry in it, returns it. Otherwise inserts ITEM and returns NULL. */ 139KeywordExt * 140Hash_Table::insert (KeywordExt *item) 141{ 142 unsigned hash_val = 143 hashpjw (reinterpret_cast<const unsigned char *>(item->_selchars), 144 item->_selchars_length * sizeof (unsigned int)); 145 unsigned int probe = hash_val & (_size - 1); 146 unsigned int increment = 147 (((hash_val >> _log_size) 148 ^ (_ignore_length ? 0 : item->_allchars_length)) 149 << 1) + 1; 150 /* Note that because _size is a power of 2 and increment is odd, 151 we have gcd(increment,_size) = 1, which guarantees that we'll find 152 an empty entry during the loop. */ 153 154 while (_table[probe] != NULL) 155 { 156 if (equal (_table[probe], item)) 157 return _table[probe]; 158 159 _collisions++; 160 probe = (probe + increment) & (_size - 1); 161 } 162 163 _table[probe] = item; 164 return NULL; 165} 166