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