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