Modules |
Files |
Inheritance Tree |
Inheritance Graph |
Name Index |
Config
File: Synopsis/Parser/C++/occ/hash.cc
1| /*
2| Copyright (C) 1997-2000 Shigeru Chiba, University of Tsukuba.
3|
4| Permission to use, copy, distribute and modify this software and
5| its documentation for any purpose is hereby granted without fee,
6| provided that the above copyright notice appear in all copies and that
7| both that copyright notice and this permission notice appear in
8| supporting documentation.
9|
10| Shigeru Chiba makes no representations about the suitability of this
11| software for any purpose. It is provided "as is" without express or
12| implied warranty.
13| */
14| /*
15| Copyright (c) 1995, 1996 Xerox Corporation.
16| All Rights Reserved.
17|
18| Use and copying of this software and preparation of derivative works
19| based upon this software are permitted. Any copy of this software or
20| of any derivative work must include the above copyright notice of
21| Xerox Corporation, this paragraph and the one after it. Any
22| distribution of this software or derivative works must comply with all
23| applicable United States export control laws.
24|
25| This software is made available AS IS, and XEROX CORPORATION DISCLAIMS
26| ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING WITHOUT LIMITATION THE
27| IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
28| PURPOSE, AND NOTWITHSTANDING ANY OTHER PROVISION CONTAINED HEREIN, ANY
29| LIABILITY FOR DAMAGES RESULTING FROM THE SOFTWARE OR ITS USE IS
30| EXPRESSLY DISCLAIMED, WHETHER ARISING IN CONTRACT, TORT (INCLUDING
31| NEGLIGENCE) OR STRICT LIABILITY, EVEN IF XEROX CORPORATION IS ADVISED
32| OF THE POSSIBILITY OF SUCH DAMAGES.
33| */
34|
35| #include <iostream>
36| #include <cstring>
37| #include "types.h"
38| #include "hash.h"
39| #include "ptree-core.h"
40| #ifndef DONT_GC
41| #include "gc.h"
42| #endif
43|
44| struct HashTableEntry {
45| char* key;
46| HashValue value;
47| };
48|
49| // class HashTable
50|
51| HashTable::HashTable()
52| {
53| Size = 251;
54| Prime2 = 127;
55| MakeTable();
56| }
57|
58| void HashTable::MakeTable()
59| {
60| entries = new (GC) HashTableEntry[Size];
61| for(int i = 0; i < Size; ++i)
62| entries[i].key = nil;
63| }
64|
65| BigHashTable::BigHashTable() : HashTable(0)
66| {
67| Size = 2053;
68| Prime2 = 1021;
69| MakeTable();
70| }
71|
72| bool HashTable::IsEmpty()
73| {
74| for(int i = 0; i < Size; ++i)
75| if(entries[i].key != nil && entries[i].key != (char*)-1)
76| return FALSE;
77|
78| return TRUE;
79| }
80|
81| void HashTable::Dump(std::ostream& out)
82| {
83| out << '{';
84| for(int i = 0; i < Size; ++i)
85| if(entries[i].key != nil && entries[i].key != (char*)-1)
86| // out << entries[i].key <<
87| out << entries[i].key << '(' << i << "), ";
88|
89| out << '}';
90| }
91|
92| char* HashTable::KeyString(char* key) {
93| char* str = new (GC) char[strlen(key) + 1];
94| strcpy(str, key);
95| return str;
96| }
97|
98| char* HashTable::KeyString(char* key, int len) {
99| char* str = new (GC) char[len + 1];
100| memmove(str, key, len);
101| str[len] = '\0';
102| return str;
103| }
104|
105| bool HashTable::Lookup(char* key, HashValue* value)
106| {
107| int i;
108| return Lookup2(key, value, &i);
109| }
110|
111| bool HashTable::Lookup(char* key, int len, HashValue* value)
112| {
113| int i;
114| return Lookup2(key, len, value, &i);
115| }
116|
117| bool HashTable::Lookup2(char* key, HashValue* value, int* index)
118| {
119| unsigned int p = StringToInt(key);
120| for(int i = 0; i < Size; ++i){
121| int j = HashFunc(p, i);
122| if(entries[j].key == nil){
123| return FALSE;
124| }
125| else if(entries[j].key != (char*)-1
126| && strcmp(entries[j].key, key) == 0){
127| *value = entries[j].value;
128| *index = j;
129| return TRUE;
130| }
131| }
132|
133| return FALSE;
134| }
135|
136| bool HashTable::Lookup2(char* key, int len, HashValue* value, int* index)
137| {
138| unsigned int p = StringToInt(key, len);
139| for(int i = 0; i < Size; ++i){
140| int j = HashFunc(p, i);
141| if(entries[j].key == nil){
142| return FALSE;
143| }
144| else if(entries[j].key != (char*)-1
145| && strncmp(entries[j].key, key, len) == 0
146| && entries[j].key[len] == '\0'){
147| *value = entries[j].value;
148| *index = j;
149| return TRUE;
150| }
151| }
152|
153| return FALSE;
154| }
155|
156| /*
157| LookupEntries() is used to find multiple entries recorded with the
158| same key. It returns the entry found with the nth (>= 0) hash key.
159| After this function completes, nth is increamented for the next try.
160| The next entry can be found if nth is passed to LookupEntries() as is.
161| */
162| bool HashTable::LookupEntries(char* key, int len, HashValue* value,
163| int& nth)
164| {
165| unsigned int p = StringToInt(key, len);
166| for(int i = nth; i < Size; ++i){
167| int j = HashFunc(p, i);
168| if(entries[j].key == nil){
169| return FALSE;
170| }
171| else if(entries[j].key != (char*)-1
172| && strncmp(entries[j].key, key, len) == 0
173| && entries[j].key[len] == '\0'){
174| *value = entries[j].value;
175| nth = i + 1;
176| return TRUE;
177| }
178| }
179|
180| return FALSE;
181| }
182|
183| /*
184| A naive implementation to calculate a prime number.
185| This function returns the first prime number being greater
186| than or equal to 'number'.
187| */
188| uint HashTable::NextPrimeNumber(uint number)
189| {
190| if(number < 2)
191| return 2;
192|
193| for(;;){
194| uint half = number / 2;
195| bool prime = TRUE;
196| for(uint i = 2; i <= half && prime; ++i)
197| if(number % i == 0)
198| prime = FALSE;
199|
200| if(prime)
201| return number;
202|
203| ++number;
204| }
205| }
206|
207| /*
208| WARNING! When an hashtable is expanded, the elements change of position!
209| This means that the index returned by some HashTable methods is safely valid
210| until the next insertion of a new element. So don't store such an index for
211| a long period!
212|
213| Post condition : new Size >= old Size + 2 * increment
214| */
215| bool HashTable::GrowTable(int increment)
216| {
217| HashTable bigger(0);
218|
219| MopWarningMessage2("The hash table is full. ", "Expanded...");
220|
221| bigger.Prime2 = (int)NextPrimeNumber(Prime2 + increment);
222| bigger.Size = (int)NextPrimeNumber(2 * bigger.Prime2);
223| bigger.MakeTable();
224|
225| bool done = TRUE;
226| for(int i = 0; done && i < Size; ++i) {
227| char *key = this->entries[i].key;
228| if (key != nil && key != (char*)-1)
229| done = bool(bigger.AddDupEntry(key, strlen(key), entries[i].value)
230| >= 0);
231| }
232|
233| if(done){
234| entries = bigger.entries;
235| Size = bigger.Size;
236| Prime2 = bigger.Prime2;
237| }
238|
239| return done;
240| }
241|
242| // AddEntry adds a new entry to the hash table.
243| // If succeeding, this returns an index of the added entry, otherwise -1.
244| // Because `key' is duplicated, you can delete `key' later on.
245|
246| int HashTable::AddEntry(char* key, HashValue value, int* index)
247| {
248| unsigned int p = StringToInt(key);
249| for(int i = 0; i < Size; ++i){
250| int j = HashFunc(p, i);
251| if(entries[j].key == nil || entries[j].key == (char*)-1){
252| entries[j].key = KeyString(key);
253| entries[j].value = value;
254| if(index != nil)
255| *index = j;
256|
257| return j;
258| }
259| else if(strcmp(entries[j].key, key) == 0){
260| if(index != nil)
261| *index = j;
262|
263| return -1;
264| }
265| }
266|
267| if(GrowTable(1000))
268| return AddEntry(key, value, index);
269|
270| std::cerr << "HashTable overflow (key: " << key << ")\nPanic...\n";
271| if(index != nil)
272| *index = 0; //
273|
274| return -1;
275| }
276|
277| int HashTable::AddEntry(bool check_duplication,
278| char* key, int len, HashValue value, int* index)
279| {
280| int i;
281| unsigned int p = StringToInt(key, len);
282| for(i = 0; i < Size; ++i){
283| int j = HashFunc(p, i);
284| if(entries[j].key == nil || entries[j].key == (char*)-1){
285| entries[j].key = KeyString(key, len);
286| entries[j].value = value;
287| if(index != nil)
288| *index = j;
289|
290| return j;
291| }
292| else if(check_duplication
293| && strncmp(entries[j].key, key, len) == 0
294| && entries[j].key[len] == '\0'){
295| if(index != nil)
296| *index = j;
297|
298| return -1;
299| }
300| }
301|
302| if(GrowTable(1000))
303| return AddEntry(check_duplication, key, len, value, index);
304|
305| std::cerr << "HashTable overflow (key: ";
306| for(i = 0; i < len; ++i)
307| std::cerr << key[i];
308|
309| std::cerr << ")\nPanic...\n";
310| if(index != nil)
311| *index = 0; //
312|
313| return -1;
314| }
315|
316| HashValue HashTable::Peek(int index)
317| {
318| return entries[index].value;
319| }
320|
321| void HashTable::ReplaceValue(int index, HashValue val)
322| {
323| if(0 <= index && index < Size)
324| entries[index].value = val;
325| else
326| std::cerr << "HashTable: invalid index (" << index << ")\n";
327| }
328|
329| bool HashTable::RemoveEntry(char* key)
330| {
331| HashValue u;
332| int index;
333|
334| if(!Lookup2(key, &u, &index))
335| return FALSE; //
336| else{
337| entries[index].key = (char*)-1;
338| return TRUE;
339| }
340| }
341|
342| bool HashTable::RemoveEntry(char* key, int len)
343| {
344| HashValue u;
345| int index;
346|
347| if(!Lookup2(key, len, &u, &index))
348| return FALSE; //
349| else{
350| entries[index].key = (char*)-1;
351| return TRUE;
352| }
353| }
354|
355| unsigned int HashTable::StringToInt(char* key)
356| {
357| if(key == nil)
358| return 0;
359|
360| unsigned int p = 0;
361| unsigned int i, j;
362| for(i = j = 0; key[i] != '\0'; ++i, ++j){
363| if(j >= sizeof(unsigned int) * 8 - 7)
364| j = 0;
365|
366| p += key[i] << j;
367| }
368|
369| return p;
370| }
371|
372| unsigned int HashTable::StringToInt(char* key, int len)
373| {
374| if(key == nil)
375| return 0;
376|
377| unsigned int p = 0;
378| int i;
379| unsigned int j;
380| for(i = j = 0; i < len; ++i, ++j){
381| if(j >= sizeof(unsigned int) * 8 - 7)
382| j = 0;
383|
384| p += key[i] << j;
385| }
386|
387| return p;
388| }
389|
390| int HashTable::HashFunc(unsigned int p, int n)
391| {
392| return((p + (unsigned int)n * (p % Prime2 + 1)) % Size);
393| }
394|
395|
396| #ifdef TEST
397|
398| #include <stdio.h>
399|
400| int main()
401| {
402| char b
403| int
404| HashTable
405|
406| while(gets(buf) != NULL){
407| unsigned int k = t.StringToInt(buf);
408| printf("key %s (%d): %d\n", buf, k, t.HashFunc(k, 0));
409| printf("key %s (%d): %d\n", buf, k, t.HashFunc(k, 1));
410|
411| printf("add %d, ", t.AddEntry(buf, 1));
412| printf("lookup %d", t.Lookup(buf, v));
413| printf("(%d)\n", v);
414| }
415| }
416|
417| #endif /* TEST */