![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to VHashAssoc.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv10no / cmd / cfront / ooptcfront / demo|
Return to VHashAssoc.c CVS log | Up to [Research Unix] / researchv10no / cmd / cfront / ooptcfront / demo |
1.1 root 1: #include "check.h"
2:
3: // This may look like C code, but it is really -*- C++ -*-
4: /*
5: Copyright (C) 1988 Free Software Foundation
6: written by Doug Lea ([email protected])
7:
8: This file is part of GNU CC.
9:
10: GNU CC is distributed in the hope that it will be useful,
11: but WITHOUT ANY WARRANTY. No author or distributor
12: accepts responsibility to anyone for the consequences of using it
13: or for whether it serves any particular purpose or works at all,
14: unless he says so in writing. Refer to the GNU CC General Public
15: License for full details.
16:
17: Everyone is granted permission to copy, modify and redistribute
18: GNU CC, but only under the conditions described in the
19: GNU CC General Public License. A copy of this license is
20: supposed to have been given to you along with GNU CC so you
21: can know your rights and responsibilities. It should be in a
22: file named COPYING. Among other things, the copyright notice
23: and this notice must be preserved on all copies.
24: */
25:
26: /* GNU hash tables converted to demonstrate PT */
27:
28: template <class T, class U> class VHashAssocNode
29: {
30: public:
31: T key;
32: U cont;
33: char status;
34: };
35:
36:
37: template <class T, class U> class VHashAssocTrav ;
38:
39:
40: template <class T, class U> class VHashAssoc
41: {
42: friend class VHashAssocTrav<T,U> ;
43:
44: VHashAssocNode<T,U> * tab;
45: int size;
46: int cnt;
47:
48: public:
49: static unsigned int (*key_hash_function)(T &);
50: int (* key_key_equality_function )(T&, T&);
51:
52: unsigned int key_hash(T& a);
53: int key_key_eq(T&a, T& b);
54:
55: VHashAssoc(int sz);
56: VHashAssoc(VHashAssoc& a);
57: ~VHashAssoc();
58:
59: VHashAssoc& operator = (VHashAssoc& a);
60:
61: int count();
62: int empty();
63: int full();
64: int capacity();
65:
66: void clear();
67: void resize(int newsize);
68:
69: U& operator [] (T& k);
70: int contains(T& key);
71: int del(T& key);
72:
73:
74: void apply(void f(U& v));
75: void error(const char* msg);
76: };
77:
78: template <class T, class U> class VHashAssocTrav
79: {
80: VHashAssoc<T,U>* h;
81: int pos;
82:
83:
84: public:
85: VHashAssocTrav(VHashAssoc<T,U>& l);
86: ~VHashAssocTrav();
87: int null();
88: int valid();
89: operator void* ();
90: int operator ! ();
91: void advance();
92: void reset();
93: void reset(VHashAssoc<T,U>& l);
94: T& key();
95: U& get();
96: };
97:
98: template <class T, class U> unsigned int VHashAssoc<T,U>::key_hash(T& a)
99: {
100: return (*VHashAssoc<T,U>::key_hash_function)(a);
101: }
102:
103: template <class T, class U> int VHashAssoc<T,U>::key_key_eq(T&a, T& b)
104: {
105: return (*VHashAssoc<T,U>::key_key_equality_function)(a, b);
106: }
107:
108:
109: template <class T, class U> VHashAssoc<T,U>::~VHashAssoc()
110: {
111: delete [size] tab;
112: }
113:
114: template <class T, class U> VHashAssoc<T,U>::count()
115: {
116: return cnt;
117: }
118:
119: template <class T, class U> VHashAssoc<T,U>::empty()
120: {
121: return cnt == 0;
122: }
123:
124: template <class T, class U> VHashAssoc<T,U>::full()
125: {
126: return cnt == size;
127: }
128:
129: template <class T, class U> VHashAssoc<T,U>::capacity()
130: {
131: return size;
132: }
133:
134: template <class T, class U> VHashAssocTrav<T,U>::VHashAssocTrav(VHashAssoc<T,U>& a)
135: {
136: h = &a;
137: reset();
138: }
139:
140: template <class T, class U> void VHashAssocTrav<T,U>::reset(VHashAssoc<T,U>& a)
141: {
142: h = &a;
143: reset();
144: }
145:
146:
147: template <class T, class U> VHashAssocTrav<T,U>::~VHashAssocTrav() {}
148:
149: template <class T, class U> VHashAssocTrav<T,U>::null()
150: {
151: return pos < 0;
152: }
153:
154: template <class T, class U> VHashAssocTrav<T,U>::valid()
155: {
156: return pos >= 0;
157: }
158:
159: template <class T, class U> VHashAssocTrav<T,U>::operator void* ()
160: {
161: return (pos < 0)? 0 : this;
162: }
163:
164: template <class T, class U> VHashAssocTrav<T,U>::operator ! ()
165: {
166: return (pos < 0);
167: }
168:
169:
170: template <class T, class U> T & VHashAssocTrav<T,U>::key()
171: {
172: if (pos < 0)
173: h->error("operation on null traverser");
174: return h->tab[pos].key;
175: }
176:
177: template <class T, class U> U & VHashAssocTrav<T,U>::get()
178: {
179: if (pos < 0)
180: h->error("operation on null traverser");
181: return h->tab[pos].cont;
182: }
183:
184: enum {EMPTYCELL, VALIDCELL, DELETEDCELL } ;
185:
186:
187: // error handling
188:
189:
190:
191: template <class T, class U>void VHashAssoc<T,U>::error(const char* msg)
192: {
193: // (*VHashAssoc_error_handler)(msg);
194: }
195:
196: template <class T, class U>VHashAssoc<T,U>::VHashAssoc(int sz)
197: {
198: tab = new VHashAssocNode<T,U>[size = sz];
199: for (int i = 0; i < size; ++i) tab[i].status = EMPTYCELL;
200: cnt = 0;
201: }
202:
203: template <class T, class U>VHashAssoc<T,U>::VHashAssoc(VHashAssoc<T,U>& a)
204: {
205: tab = new VHashAssocNode<T,U>[size = a.size];
206: for (int i = 0; i < size; ++i) tab[i].status = EMPTYCELL;
207: cnt = 0;
208: for (VHashAssocTrav<T,U> p(a); p; p.advance())
209: (*this)[p.key()] = p.get();
210: }
211:
212: template <class T, class U> VHashAssoc<T,U>& VHashAssoc<T,U>::operator =
213: (VHashAssoc<T,U>& a)
214: {
215: if (a.tab != tab)
216: {
217: clear();
218: delete [size] tab;
219: tab = new VHashAssocNode<T,U>[size = a.size];
220: for (int i = 0; i < size; ++i) tab[i].status = EMPTYCELL;
221: cnt = 0;
222: for (VHashAssocTrav<T,U> p(a); p; p.advance())
223: (*this)[p.key()] = p.get();
224: }
225: return *this;
226: }
227:
228: /*
229: * hashing method: double hash based on high bits of hash fct,
230: * followed by linear probe. Can't do too much better if Assoc
231: * sizes not constrained to be prime.
232: */
233:
234:
235: static inline doublehashinc(unsigned int h, int s)
236: {
237: return ((h / s) % s) >> 1;
238: }
239:
240:
241: template <class T, class U>U& VHashAssoc<T,U>::operator [](T & key)
242: {
243: int bestspot = -1;
244: unsigned int hashval = key_hash(key);
245: int h = hashval % size;
246: for (int i = 0; i <= size; ++i)
247: {
248: if (tab[h].status == EMPTYCELL)
249: {
250: if (bestspot < 0) bestspot = h;
251: tab[bestspot].key = key;
252: tab[bestspot].status = VALIDCELL;
253: ++cnt;
254: return tab[bestspot].cont;
255: }
256: else if (tab[h].status == DELETEDCELL)
257: {
258: if (bestspot < 0) bestspot = h;
259: }
260: else if (key_key_eq(tab[h].key, key))
261: return tab[h].cont;
262: if (i == 0)
263: h = (h + doublehashinc(hashval, size)) % size;
264: else if (++h >= size)
265: h -= size;
266: }
267: error("cannot add to full Assoc table");
268: return tab[0].cont ; // suppress warning message
269: }
270:
271:
272: template <class T, class U>int VHashAssoc<T,U>::contains(T & key)
273: {
274: unsigned int hashval = key_hash(key);
275: int h = hashval % size;
276: for (int i = 0; i <= size; ++i)
277: {
278: if (tab[h].status == EMPTYCELL)
279: return 0;
280: else if (tab[h].status == VALIDCELL && key_key_eq(tab[h].key, key))
281: return 1;
282: if (i == 0)
283: h = (h + doublehashinc(hashval, size)) % size;
284: else if (++h >= size)
285: h -= size;
286: }
287: return 0;
288: }
289:
290: template <class T, class U>int VHashAssoc<T,U>::del(T & key)
291: {
292: unsigned int hashval = key_hash(key);
293: int h = hashval % size;
294: for (int i = 0; i <= size; ++i)
295: {
296: if (tab[h].status == EMPTYCELL)
297: return 0;
298: else if (tab[h].status == VALIDCELL && key_key_eq(tab[h].key, key))
299: {
300: tab[h].status = DELETEDCELL;
301: --cnt;
302: return 1;
303: }
304: if (i == 0)
305: h = (h + doublehashinc(hashval, size)) % size;
306: else if (++h >= size)
307: h -= size;
308: }
309: return 0;
310: }
311:
312: /*
313: template <class T, class U>void VHashAssoc<T,U>::apply(UProcedure f)
314: {
315: for (int i = 0; i < size; ++i)
316: if (tab[i].status == VALIDCELL)
317: (*f)(tab[i].cont);
318: }
319: */
320:
321: template <class T, class U>void VHashAssoc<T,U>::clear()
322: {
323: for (int i = 0; i < size; ++i)
324: tab[i].status = EMPTYCELL;
325: cnt = 0;
326: }
327:
328: template <class T, class U>void VHashAssoc<T,U>::resize(int newsize)
329: {
330: if (newsize < cnt)
331: error("requested resize too small");
332: VHashAssocNode<T,U>* oldtab = tab;
333: int oldsize = size;
334: tab = new VHashAssocNode<T,U>[size = newsize];
335: for (int i = 0; i < size; ++i)
336: tab[i].status = EMPTYCELL;
337: cnt = 0;
338: for (i = 0; i < oldsize; ++i)
339: if (oldtab[i].status == VALIDCELL)
340: (*this)[oldtab[i].key] = oldtab[i].cont;
341: delete [oldsize] oldtab;
342: }
343:
344: template <class T, class U>void VHashAssocTrav<T,U>::reset()
345: {
346: for (pos = 0; pos < h->size; ++pos)
347: if (h->tab[pos].status == VALIDCELL)
348: return;
349: pos = -1;
350: }
351:
352: template <class T, class U>void VHashAssocTrav<T,U>::advance()
353: {
354: if (pos < 0)
355: return;
356: for (pos++; pos < h->size; ++pos)
357: if (h->tab[pos].status == VALIDCELL)
358: return;
359: pos = -1;
360: }
361:
362:
363: const int size = 100 ;
364:
365:
366: unsigned int f(int & i) { return i ; }
367:
368: unsigned int f1(char & i) { return (int)i ; }
369:
370: int g(int& k1, int& k2){
371: return (k1 == k2) ;
372: }
373:
374: int g1(char & k1, char & k2){
375: return (k1 == k2) ;
376: }
377:
378:
379:
380:
381: VHashAssoc<int, int> foo(2*size) ;
382:
383:
384: main () {
385:
386:
387: start_test(__FILE__) ;
388:
389: foo.key_hash_function = f ;
390: foo.key_key_equality_function= g ;
391: // populate the hash
392: for (int i = 0 ; ! foo.full() ; i++)
393: foo[i] = i ;
394:
395: for (i = 0 ; i < size ; i++) {
396: check(foo.contains(i)) ;
397: check(foo[i] == i) ;
398: }
399:
400: foo.resize(size * 4) ;
401:
402: // repeat the tests, resizing should not have impacted it any
403: for (i = 0 ; i < size ; i++) {
404: check(foo.contains(i)) ;
405: check(foo[i] == i) ;
406: check (foo.del(i)) ;
407: check(!foo.contains(i)) ;
408: }
409: {
410: // try another one
411: VHashAssoc<char, char *> foo(2*size) ;
412: foo.key_hash_function = f1 ;
413: foo.key_key_equality_function= g1 ;
414: // populate the hash
415: for (char i = 0 ; ! foo.full() ; i++) {
416: char *p = new char ;
417: *p = i ;
418: foo[i] = p ;
419: }
420:
421: for (i = 0 ; i < size ; i++) {
422: check(foo.contains(i)) ;
423: check(*(foo[i]) == i) ;
424: }
425:
426: foo.resize(size * 4) ;
427:
428: // repeat the tests, resizing should not have impacted it any
429: for (i = 0 ; i < size ; i++) {
430: check(foo.contains(i)) ;
431: check(*(foo[i]) == i) ;
432: check (foo.del(i)) ;
433: check(!foo.contains(i)) ;
434: }
435: }
436:
437: end_test() ;
438:
439: }
440:
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.