hash-table.cc revision 58551
158551Skris/* Hash table for checking keyword links. Implemented using double hashing. 258551Skris Copyright (C) 1989-1998 Free Software Foundation, Inc. 358551Skris written by Douglas C. Schmidt (schmidt@ics.uci.edu) 458551Skris 558551SkrisThis file is part of GNU GPERF. 658551Skris 758551SkrisGNU GPERF is free software; you can redistribute it and/or modify 858551Skrisit under the terms of the GNU General Public License as published by 958551Skristhe Free Software Foundation; either version 1, or (at your option) 1058551Skrisany later version. 1158551Skris 1258551SkrisGNU GPERF is distributed in the hope that it will be useful, 1358551Skrisbut WITHOUT ANY WARRANTY; without even the implied warranty of 1458551SkrisMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 1558551SkrisGNU General Public License for more details. 1658551Skris 1758551SkrisYou should have received a copy of the GNU General Public License 1858551Skrisalong with GNU GPERF; see the file COPYING. If not, write to the Free 1958551SkrisSoftware Foundation, 59 Temple Place - Suite 330, Boston, MA 02111, USA. */ 2058551Skris 2158551Skris#include "hash-table.h" 2258551Skris 2358551Skris#include <stdio.h> 2458551Skris#include <string.h> /* declares memset(), strcmp() */ 2558551Skris#include <hash.h> 2658551Skris#include "options.h" 2758551Skris#include "trace.h" 2858551Skris 2958551Skris#define NIL(TYPE) (TYPE *)0 3058551Skris 3158551Skris/* The size of the hash table is always the smallest power of 2 >= the size 3258551Skris indicated by the user. This allows several optimizations, including 3358551Skris the use of double hashing and elimination of the mod instruction. 3458551Skris Note that the size had better be larger than the number of items 3558551Skris in the hash table, else there's trouble!!! Note that the memory 3658551Skris for the hash table is allocated *outside* the intialization routine. 3758551Skris This compromises information hiding somewhat, but greatly reduces 3858551Skris memory fragmentation, since we can now use alloca! */ 3958551Skris 4058551SkrisHash_Table::Hash_Table (List_Node **table_ptr, int s): 4158551Skris table (table_ptr), size (s), collisions (0) 4258551Skris{ 4358551Skris T (Trace t ("Hash_Table::Hash_Table");) 4458551Skris memset ((char *) table, 0, size * sizeof (*table)); 4558551Skris} 4658551Skris 4758551SkrisHash_Table::~Hash_Table (void) 4858551Skris{ 4958551Skris T (Trace t ("Hash_Table::~Hash_Table");) 5058551Skris if (option[DEBUG]) 5158551Skris { 5258551Skris int field_width = option.get_max_keysig_size (); 5358551Skris 5458551Skris fprintf (stderr, 5558551Skris "\ndumping the hash table\n" 5658551Skris "total available table slots = %d, total bytes = %d, total collisions = %d\n" 5758551Skris "location, %*s, keyword\n", 5858551Skris size, size * (int) sizeof (*table), collisions, 5958551Skris field_width, "keysig"); 6058551Skris 6158551Skris for (int i = size - 1; i >= 0; i--) 6258551Skris if (table[i]) 6358551Skris fprintf (stderr, "%8d, %*s, %s\n", 6458551Skris i, field_width, table[i]->char_set, table[i]->key); 6558551Skris 6658551Skris fprintf (stderr, "\nend dumping hash table\n\n"); 6758551Skris } 6858551Skris} 6958551Skris 7058551Skris/* If the ITEM is already in the hash table return the item found 7158551Skris in the table. Otherwise inserts the ITEM, and returns FALSE. 7258551Skris Uses double hashing. */ 7358551Skris 7458551SkrisList_Node * 7558551SkrisHash_Table::operator() (List_Node *item, int ignore_length) 7658551Skris{ 7758551Skris T (Trace t ("Hash_Table::operator()");) 7858551Skris unsigned hash_val = hashpjw (item->char_set); 7958551Skris int probe = hash_val & size - 1; 8058551Skris int increment = (hash_val ^ item->length | 1) & size - 1; 8158551Skris 8258551Skris while (table[probe] 8358551Skris && (strcmp (table[probe]->char_set, item->char_set) 8458551Skris || (!ignore_length && table[probe]->length != item->length))) 8558551Skris { 8658551Skris collisions++; 8758551Skris probe = probe + increment & size - 1; 8858551Skris } 8958551Skris 9058551Skris return table[probe] ? table[probe] : (table[probe] = item, NIL (List_Node)); 9158551Skris} 92