![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to hash.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv10no / cmd / cfront / xptcfront|
Return to hash.c CVS log | Up to [Research Unix] / researchv10no / cmd / cfront / xptcfront |
1.1 root 1: /* ident "@(#)ctrans:src/hash.c 1.2" */
2: /*
3: $Header: /usr2/odi/libmisc/RCS/hash.C,v 1.11 90/03/22 09:24:07 sam Exp $
4:
5: Copyright (c) 1989 by Object Design, Inc., Burlington, Mass.
6: All rights reserved.
7:
8: */
9:
10: #include <stdio.h>
11: #include "hash.h"
12: #include <osfcn.h>
13:
14: #define EMPTY 0
15: #define VALID 1
16: #define DELETED 2
17:
18: void default_Hash_error_handler(const char* msg)
19: {
20: fprintf(stderr, "Fatal Hash error: %s\n", msg) ;
21: exit(1) ;
22: }
23:
24: Error_Proc Hash_error_handler = default_Hash_error_handler ;
25:
26: Error_Proc set_Hash_error_handler(Error_Proc f)
27: {
28: Error_Proc old = Hash_error_handler ;
29: Hash_error_handler = f ;
30: return old ;
31: }
32:
33: void Hash::error(const char* msg)
34: {
35: (*Hash_error_handler)(msg) ;
36: }
37:
38: Hash::Hash(int sz= DEFAULT_INITIAL_HASH_SIZE)
39: {
40: tab = new HashTableEntry[size = sz] ;
41: for (int i = 0; i < size; ++i) tab[i].status = EMPTY ;
42: entry_count = 0 ;
43: }
44:
45: Hash::Hash(Hash& a)
46: {
47: tab = new HashTableEntry[size = a.size] ;
48:
49: key_hash_function = a.key_hash_function ;
50: key_key_equality_function = a.key_key_equality_function ;
51:
52: for (int i = 0; i < size; ++i) tab[i].status = EMPTY ;
53: entry_count = 0 ;
54: for (HashWalker p(a); p; p.advance())
55: (*this)[p.key()] = p.get() ;
56: }
57:
58: Hash& Hash::operator = (Hash& a)
59: {
60: if (a.tab != tab)
61: {
62: clear() ;
63: delete [size] tab ;
64: tab = new HashTableEntry[size = a.size] ;
65: for (int i = 0; i < size; ++i) tab[i].status = EMPTY ;
66: entry_count = 0 ;
67: for (HashWalker p(a); p; p.advance())
68: (*this)[p.key()] = p.get() ;
69: }
70: return *this ;
71: }
72:
73: /*
74: * hashing method: double hash based on high bits of hash fct,
75: * followed by linear probe. Can't do too much better if Assoc
76: * sizes not constrained to be prime.
77: */
78:
79:
80: static inline doublehashinc(unsigned int h, int s)
81: {
82: return ((h / s) % s) >> 1 ;
83: }
84:
85: // IWBNI we knew whether we were being called as an lvalue or rvalue.
86: // If the former, then we wouldn't have to scan through the whole
87: // table just to tell if we should rehash or not. Sigh.
88: int& Hash::operator [](int key)
89: {
90: unsigned int hashval = key_hash(key) ;
91: while (1)
92: {
93: int bestspot = -1 ;
94: int h = hashval % size ;
95: for (int i = 0; i <= size; ++i)
96: {
97: if (tab[h].status == EMPTY)
98: {
99: // resize if the hash table is more than 87.5% full
100: if (entry_count > ((size>>1)+(size>>2)+(size>>3)))
101: // resize and insert again
102: break ;
103: if (bestspot < 0) bestspot = h ;
104: tab[bestspot].key = key ;
105: tab[bestspot].status = VALID ;
106: ++entry_count ;
107: return tab[bestspot].cont ;
108: }
109: else if (tab[h].status == DELETED)
110: {
111: if (bestspot < 0) bestspot = h ;
112: }
113: else if (key_key_eq(tab[h].key, key))
114: return tab[h].cont ;
115: if (i == 0)
116: h = (h + doublehashinc(hashval, size)) % size ;
117: else if (++h >= size)
118: h -= size ;
119: }
120: resize(size << 1) ;
121: }
122: }
123:
124: /* This seems convoluted, but it does whatever you want without
125: redundant probing of the hash table. */
126:
127: void Hash::action (int key, int val, insert_action what,
128: int& found, int& old_val)
129: {
130: unsigned int hashval = key_hash(key) ;
131: while (1)
132: {
133: int bestspot = -1 ;
134: int h = hashval % size ;
135: for (int i = 0; i <= size; ++i)
136: {
137: if (tab[h].status == EMPTY)
138: {
139: // resize if the hash table is more than 87.5% full
140: if (entry_count > ((size>>1)+(size>>2)+(size>>3)))
141: // resize and insert again
142: break ;
143: if (bestspot < 0) bestspot = h ;
144: found = 0;
145: if(what != probe) {
146: tab[bestspot].key = key ;
147: tab[bestspot].status = VALID ;
148: ++entry_count ;
149: tab[bestspot].cont = val;
150: }
151: return;
152: }
153: else if (tab[h].status == DELETED)
154: {
155: if (bestspot < 0) bestspot = h ;
156: }
157: else if (key_key_eq(tab[h].key, key)) {
158: found = 1;
159: old_val = tab[h].cont;
160: if(what == replace)
161: tab[h].cont = val;
162: return;
163: }
164: if (i == 0)
165: h = (h + doublehashinc(hashval, size)) % size ;
166: else if (++h >= size)
167: h -= size ;
168: }
169: resize(size << 1) ;
170: }
171: }
172:
173: int Hash::contains(int key)
174: {
175: unsigned int hashval = key_hash(key) ;
176: int h = hashval % size ;
177: for (int i = 0; i <= size; ++i)
178: {
179: if (tab[h].status == EMPTY)
180: return 0 ;
181: else if (tab[h].status == VALID && key_key_eq(tab[h].key, key))
182: return 1 ;
183: if (i == 0)
184: h = (h + doublehashinc(hashval, size)) % size ;
185: else if (++h >= size)
186: h -= size ;
187: }
188: return 0 ;
189: }
190:
191: int Hash::del(int key)
192: {
193: unsigned int hashval = key_hash(key) ;
194: int h = hashval % size ;
195: for (int i = 0; i <= size; ++i)
196: {
197: if (tab[h].status == EMPTY)
198: return 0 ;
199: else if (tab[h].status == VALID && key_key_eq(tab[h].key, key))
200: {
201: tab[h].status = DELETED ;
202: --entry_count ;
203: return 1 ;
204: }
205: if (i == 0)
206: h = (h + doublehashinc(hashval, size)) % size ;
207: else if (++h >= size)
208: h -= size ;
209: }
210: return 0 ;
211: }
212:
213: void Hash::apply(intProc f)
214: {
215: for (int i = 0; i < size; ++i)
216: if (tab[i].status == VALID)
217: (*f)(tab[i].cont) ;
218: }
219:
220: void Hash::clear()
221: {
222: for (int i = 0; i < size; ++i)
223: tab[i].status = EMPTY ;
224: entry_count = 0 ;
225: }
226:
227: void Hash::resize(int newsize)
228: {
229: if (newsize < entry_count)
230: error("requested resize too small") ;
231: HashTableEntry* oldtab = tab ;
232: int oldsize = size ;
233: tab = new HashTableEntry[size = newsize] ;
234: for (int i = 0; i < size; ++i)
235: tab[i].status = EMPTY ;
236: entry_count = 0 ;
237: for (i = 0; i < oldsize; ++i)
238: if (oldtab[i].status == VALID)
239: (*this)[oldtab[i].key] = oldtab[i].cont ;
240: delete [oldsize] oldtab ;
241: }
242:
243: void HashWalker::reset()
244: {
245: for (pos = 0; pos < h->size; ++pos)
246: if (h->tab[pos].status == VALID)
247: return ;
248: pos = -1 ;
249: }
250:
251: void HashWalker::advance()
252: {
253: if (pos < 0)
254: return ;
255: for (pos++; pos < h->size; ++pos)
256: if (h->tab[pos].status == VALID)
257: return ;
258: pos = -1 ;
259: }
260:
261: /*
262: unsigned int foo(int bar) {return bar;}
263: int baz(int a, int b) {return a == b;}
264:
265: main()
266: {
267: Hash vh(10) ;
268: HashWalker vt(vh) ;
269: int i ;
270:
271: vh.key_hash_function = &foo ;
272: vh.key_key_equality_function = baz ;
273: printf("Capacity=%d \n", vh.capacity()) ;
274: for (i=0; i<500; i+= 5)
275: {
276: vh[i] = i * i ;
277: }
278: vt.reset() ;
279: while (vt.valid())
280: {
281: printf("key=%d, data=%d\t", vt.key(), vt.get());
282: vt.advance() ;
283: }
284: for (i=0; i<500; i+= 10)
285: {
286: vh.del (i) ;
287: printf("After delete: %d\n", vh[i]);
288: }
289: printf("\n-----------------\n") ;
290: vt.reset() ;
291: while (vt.valid())
292: {
293: printf("key=%d, data=%d\t", vt.key(), vt.get());
294: vt.advance() ;
295: }
296: }
297:
298: */
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.