![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to hash.h CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv10no / cmd / cfront / optcfront|
Return to hash.h CVS log | Up to [Research Unix] / researchv10no / cmd / cfront / optcfront |
1.1 root 1: /* ident "@(#)ctrans:src/hash.h 1.2" */
2: /* Compiler interface to hash tables from odi library.
3: $Source: /usr3/lang/benson/work/stripped_cfront/RCS/hash.h,v $ $RCSfile: hash.h,v $
4: $Revision: 1.1 $ $Date: 89/11/20 08:50:36 $
5: $Author: benson $ $Locker: $
6: $State: Exp $
7:
8: $Header: /usr2/odi/objectstore.src/libos/RCS/hash.H,v 1.4 89/09/26 09:37:31 benson Exp $
9:
10: Copyright (c) 1989 by Object Design, Inc., Burlington, Mass.
11: All rights reserved.
12:
13: */
14:
15: #ifndef _HASH_H
16: #define _HASH_H
17:
18: #include <string.h>
19:
20: typedef void (*Error_Proc) (const char*) ;
21:
22: extern void default_Hash_error_handler (const char*) ;
23: extern Error_Proc Hash_error_handler ;
24: extern Error_Proc set_Hash_error_handler (Error_Proc f) ;
25:
26: #ifndef _hash_typedefs
27: #define _hash_typedefs 1
28: typedef void (*intProc)(int) ;
29: #endif
30:
31: #define DEFAULT_INITIAL_HASH_SIZE 100
32:
33: struct HashTableEntry
34: {
35: int key ;
36: int cont ;
37: char status ;
38: } ;
39:
40: class HashWalker ;
41:
42: class Hash
43: {
44: friend class HashWalker ;
45:
46: HashTableEntry* tab ;
47: int size ;
48: int entry_count ;
49:
50: public:
51: unsigned int (*key_hash_function)(int) ;
52: int (*key_key_equality_function) (int, int) ;
53:
54: unsigned int key_hash(int a) ;
55: int key_key_eq(int a, int b);
56:
57: Hash(int sz) ;
58: Hash(Hash& a) ;
59: ~Hash() ;
60:
61: Hash& operator= (Hash& a) ;
62:
63: int count() ;
64: int empty() ;
65: int full() ;
66: int capacity() ;
67:
68: void clear() ;
69: void resize(int newsize) ;
70:
71: enum insert_action { probe, insert, replace };
72: void action (int key, int val, insert_action what,
73: int& found, int& old_val);
74: int& operator [] (int k) ;
75: int contains(int key) ;
76: int del(int key) ;
77:
78: void apply (intProc f) ;
79: void error(const char* msg) ;
80: } ;
81:
82: class HashWalker
83: {
84: Hash* h ;
85: int pos ;
86:
87: public:
88: HashWalker(Hash& l) ;
89: ~HashWalker() ;
90:
91: int null() ;
92: int valid() ;
93: operator void* () ;
94: int operator ! () ;
95: void advance() ;
96: void reset() ;
97: void reset(Hash& l) ;
98: const int& key() ;
99: int& get() ;
100: } ;
101:
102: inline unsigned int Hash::key_hash(int a)
103: {
104: #ifdef HASHFUNCTION
105: return HASHFUNCTION(a) ;
106: #else
107: return (*key_hash_function)(a) ;
108: #endif
109: }
110:
111: inline int Hash::key_key_eq(int a, int b)
112: {
113: #ifdef EQUALITYFUNCTION
114: return EQUALITYFUNCTION(a, b) ;
115: #else
116: return (*key_key_equality_function)(a, b) ;
117: #endif
118: }
119:
120:
121: inline Hash::~Hash()
122: {
123: delete [size] tab ;
124: }
125:
126: inline int Hash::count()
127: {
128: return entry_count ;
129: }
130:
131: inline int Hash::empty()
132: {
133: return entry_count == 0 ;
134: }
135:
136: inline int Hash::full()
137: {
138: return entry_count == size ;
139: }
140:
141: inline int Hash::capacity()
142: {
143: return size ;
144: }
145: inline HashWalker::HashWalker(Hash& a)
146: {
147: h = &a ;
148: reset() ;
149: }
150:
151: inline void HashWalker::reset(Hash& a)
152: {
153: h = &a ;
154: reset() ;
155: }
156:
157:
158: inline HashWalker::~HashWalker() {}
159:
160: inline int HashWalker::null()
161: {
162: return pos < 0 ;
163: }
164:
165: inline int HashWalker::valid()
166: {
167: return pos >= 0 ;
168: }
169:
170: inline HashWalker::operator void* ()
171: {
172: return (pos < 0)? 0 : this ;
173: }
174:
175: inline int HashWalker::operator ! ()
176: {
177: return (pos < 0) ;
178: }
179:
180:
181: inline const int& HashWalker::key()
182: {
183: if (pos < 0)
184: h->error("operation on null Walker") ;
185: return h->tab[pos].key ;
186: }
187:
188: inline int& HashWalker::get()
189: {
190: if (pos < 0)
191: h->error("operation on null Walker") ;
192: return h->tab[pos].cont ;
193: }
194:
195: inline int pointer_hasheq (int a, int b)
196: {
197: return a == b;
198: };
199:
200: inline unsigned int pointer_hash_fcn (int x)
201: {
202: unsigned X = (unsigned) x;
203: return ((X << 16) | (X >> 16)) ^ x;
204: }
205:
206: class pointer_hash : public Hash {
207: public:
208: pointer_hash (int sz = 0) : Hash (sz) {
209: key_hash_function = pointer_hash_fcn;
210: key_key_equality_function = pointer_hasheq;
211: }
212:
213: pointer_hash (pointer_hash& h) : Hash (h) {};
214: };
215:
216: inline int string_hasheq (int a, int b)
217: {
218: return !strcmp((char *)a, (char *) b);
219: };
220:
221: static unsigned int string_hash_fcn (int x)
222: {
223: char * str = (char *)x;
224: int l = strlen(str);
225:
226: if(x <= 4) return str[0];
227: else {
228: unsigned int * f4 = (unsigned int *) str;
229: if (l < 8) return ((*f4 << 16) | (*f4 >> 16)) ^ *f4;
230: else {
231: unsigned int * s4 = f4 ++;
232: return ((*f4 << 16) | (*f4 >> 16)) ^ *s4;
233: }
234: }
235: };
236:
237:
238: class string_hash : public Hash {
239: public:
240:
241: string_hash (int sz = 0) : Hash (sz) {
242: key_hash_function = string_hash_fcn;
243: key_key_equality_function = string_hasheq;
244: };
245:
246: string_hash (string_hash& h) : Hash (h) {};
247: };
248:
249: #endif
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.