hash-table.cc revision 67065 
1/* Hash table for checking keyword links.  Implemented using double hashing.
2   Copyright (C) 1989-1998, 2000 Free Software Foundation, Inc.
3   written by Douglas C. Schmidt (schmidt@ics.uci.edu)
4
5This file is part of GNU GPERF.
6
7GNU GPERF is free software; you can redistribute it and/or modify
8it under the terms of the GNU General Public License as published by
9the Free Software Foundation; either version 1, or (at your option)
10any later version.
11
12GNU GPERF is distributed in the hope that it will be useful,
13but WITHOUT ANY WARRANTY; without even the implied warranty of
14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15GNU General Public License for more details.
16
17You should have received a copy of the GNU General Public License
18along with GNU GPERF; see the file COPYING.  If not, write to the Free
19Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111, USA.  */
20
21#include "hash-table.h"
22
23#include <stdio.h>
24#include <string.h> /* declares memset(), strcmp() */
25#include <hash.h>
26#include "options.h"
27#include "trace.h"
28
29/* The size of the hash table is always the smallest power of 2 >= the size
30   indicated by the user.  This allows several optimizations, including
31   the use of double hashing and elimination of the mod instruction.
32   Note that the size had better be larger than the number of items
33   in the hash table, else there's trouble!!!  Note that the memory
34   for the hash table is allocated *outside* the intialization routine.
35   This compromises information hiding somewhat, but greatly reduces
36   memory fragmentation, since we can now use alloca! */
37
38Hash_Table::Hash_Table (List_Node **table_ptr, int s, int ignore_len):
39     table (table_ptr), size (s), collisions (0), ignore_length (ignore_len)
40{
41  T (Trace t ("Hash_Table::Hash_Table");)
42  memset ((char *) table, 0, size * sizeof (*table));
43}
44
45Hash_Table::~Hash_Table (void)
46{
47  T (Trace t ("Hash_Table::~Hash_Table");)
48  if (option[DEBUG])
49    {
50      int field_width = option.get_max_keysig_size ();
51
52      fprintf (stderr,
53               "\ndumping the hash table\n"
54               "total available table slots = %d, total bytes = %d, total collisions = %d\n"
55               "location, %*s, keyword\n",
56               size, size * (int) sizeof (*table), collisions,
57               field_width, "keysig");
58
59      for (int i = size - 1; i >= 0; i--)
60        if (table[i])
61          fprintf (stderr, "%8d, %*.*s, %.*s\n",
62                   i,
63                   field_width, table[i]->char_set_length, table[i]->char_set,
64                   table[i]->key_length, table[i]->key);
65
66      fprintf (stderr, "\nend dumping hash table\n\n");
67    }
68}
69
70/* If the ITEM is already in the hash table return the item found
71   in the table.  Otherwise inserts the ITEM, and returns FALSE.
72   Uses double hashing. */
73
74List_Node *
75Hash_Table::insert (List_Node *item)
76{
77  T (Trace t ("Hash_Table::operator()");)
78  unsigned hash_val  = hashpjw (item->char_set, item->char_set_length);
79  int      probe     = hash_val & (size - 1);
80  int      increment = ((hash_val ^ item->key_length) | 1) & (size - 1);
81
82  while (table[probe])
83    {
84      if (table[probe]->char_set_length == item->char_set_length
85          && memcmp (table[probe]->char_set, item->char_set, item->char_set_length) == 0
86          && (ignore_length || table[probe]->key_length == item->key_length))
87        return table[probe];
88
89      collisions++;
90      probe = (probe + increment) & (size - 1);
91    }
92
93  table[probe] = item;
94  return (List_Node *) 0;
95}
96