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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
|
// $Id$
/* 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 "Hash_Table.h"
ACE_RCSID(src, Hash_Table, "$Id$")
#if defined (ACE_HAS_GPERF)
#include "ace/ACE.h"
// 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!!!
Hash_Table::Hash_Table (size_t s)
: size_ (ACE_POW (s)),
collisions_ (0)
{
if (this->size_ == 0)
this->size_ = 1;
ACE_NEW (this->table_,
List_Node*[this->size_]);
ACE_OS::memset ((char *) this->table_,
0,
this->size_ * sizeof *this->table_);
}
Hash_Table::~Hash_Table (void)
{
if (option[DEBUG])
{
u_int keysig_width = option.max_keysig_size () > ACE_OS::strlen ("keysig")
? option.max_keysig_size ()
: ACE_OS::strlen ("keysig");
ACE_DEBUG ((LM_DEBUG,
"\ndumping the hash table\ntotal available table slots = %d, total bytes = %d, total collisions = %d\n"
"location, %*s, keyword\n",
this->size_,
this->size_ * (int) sizeof *this->table_,
this->collisions_,
keysig_width,
"keysig"));
for (int i = this->size_ - 1; i >= 0; i--)
if (this->table_[i])
ACE_DEBUG ((LM_DEBUG,
"%8d, %*s, %s\n",
i,
keysig_width,
this->table_[i]->keysig,
this->table_[i]->key));
ACE_DEBUG ((LM_DEBUG,
"end dumping hash table\n\n"));
}
delete [] this->table_;
}
// 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::find (List_Node *item,
int ignore_length)
{
u_int hash_val = ACE::hash_pjw (item->keysig);
// The following works since the hash table size_ is always a power
// of 2...
size_t size = this->size_ - 1;
int probe;
int increment = (hash_val ^ (ignore_length == 0 ? item->length : 0) | 1) & size;
for (probe = hash_val & size;
this->table_[probe]
&& (ACE_OS::strcmp (this->table_[probe]->keysig, item->keysig) != 0
|| (ignore_length == 0 && this->table_[probe]->length != item->length));
probe = probe + increment & size)
this->collisions_++;
if (this->table_[probe])
return this->table_[probe];
else
{
this->table_[probe] = item;
return 0;
}
}
#endif /* ACE_HAS_GPERF */
|
