Annotation of parser3/src/include/pa_hash.h, revision 1.58.2.8
1.28 paf 1: /** @file
1.29 paf 2: Parser: hash class decl.
3:
1.58 paf 4: Copyright (c) 2001, 2003 ArtLebedev Group (http://www.artlebedev.com)
1.29 paf 5:
1.54 paf 6: Author: Alexandr Petrosian <paf@design.ru> (http://paf.design.ru)
1.1 paf 7: */
8:
1.58.2.2 paf 9: /*
10: The prime numbers used from zend_hash.c,
11: the part of Zend scripting engine library,
12: Copyrighted (C) 1999-2000 Zend Technologies Ltd.
13: http://www.zend.com/license/0_92.txt
14: For more information about Zend please visit http://www.zend.com/
15: */
16:
1.1 paf 17: #ifndef PA_HASH_H
18: #define PA_HASH_H
1.56 paf 19:
1.58.2.8! paf 20: static const char* IDENT_HASH_H="$Date: 2003/01/27 15:07:47 $";
1.1 paf 21:
1.14 paf 22: #include "pa_pool.h"
1.1 paf 23: #include "pa_types.h"
24:
1.29 paf 25: /**
1.58.2.2 paf 26: Simple hash.
1.29 paf 27:
1.58.2.2 paf 28: Automatically rehashed when almost is_full.
1.51 paf 29: Contains no 0 values.
30: get returning 0 means there were no such.
31: "put value 0" means "remove"
1.29 paf 32: */
1.58.2.2 paf 33: template<typename K, typename V> class Hash: public PA_Object {
1.1 paf 34: public:
35:
1.58.2.6 paf 36: typedef K key_type;
37: typedef V value_type;
1.8 paf 38:
1.58.2.1 paf 39: Hash() {
1.58.2.2 paf 40: allocated=allocates[allocates_index=0];
41: threshold=allocated*THRESHOLD_PERCENT/100;
42: fpairs_count=fused_refs=0;
43: refs=static_cast<Pair **>(pa_calloc(sizeof(Pair *)*allocated));
1.43 parser 44: }
45:
1.58.2.1 paf 46: Hash(const Hash& source) {
1.58.2.2 paf 47: allocates_index=source.allocates_index;
48: allocated=source.allocated;
49: threshold=source.threshold;
50: fused_refs=source.fused_refs;
51: fpairs_count=source.fpairs_count;
52: refs=new Pair*[allocated];
53: memcpy(refs, source.refs, sizeof(Pair *)*allocated);
54: }
55: ~Hash() {
56: destroy_pairs();
57: delete refs;
1.24 paf 58: }
1.10 paf 59:
1.51 paf 60: /// put a [value] under the [key] @returns existed or not
1.58.2.8! paf 61: bool put(K key, V value) {
1.58.2.2 paf 62: if(is_full())
63: expand();
64:
1.58.2.7 paf 65: uint code=hash_code(key);
1.58.2.2 paf 66: uint index=code%allocated;
67: Pair **ref=&refs[index];
68: for(Pair *pair=*ref; pair; pair=pair->link)
69: if(pair->code==code && pair->key==key) {
70: // found a pair with the same key
71: pair->value=value;
72: return true;
73: }
74:
75: // proper pair not found -- create&link_in new pair
76: if(!*ref) // root cell were fused_refs?
77: fused_refs++; // not, we'll use it and record the fact
78: *ref=new Pair(code, key, value, *ref);
79: fpairs_count++;
80: return false;
81: }
1.48 paf 82:
1.51 paf 83: /// remove the [key] @returns existed or not
1.58.2.8! paf 84: bool remove(K key) {
1.58.2.7 paf 85: uint code=hash_code(key);
1.58.2.2 paf 86: uint index=code%allocated;
87: for(Pair **ref=&refs[index]; *ref; ref=&(*ref)->link)
88: if((*ref)->code==code && (*ref)->key==key) {
89: // found a pair with the same key
90: Pair *next=(*ref)->link;
91: delete *ref;
92: *ref=next;
93: --fpairs_count;
94: return true;
95: }
96:
97: return false;
1.33 paf 98: }
1.58.2.2 paf 99:
1.29 paf 100: /// get associated [value] by the [key]
1.58.2.8! paf 101: V get(K key) const {
1.58.2.7 paf 102: uint code=hash_code(key);
1.58.2.2 paf 103: uint index=code%allocated;
104: for(Pair *pair=refs[index]; pair; pair=pair->link)
105: if(pair->code==code && pair->key==key)
106: return pair->value;
107:
108: return 0;
109: }
1.17 paf 110:
1.51 paf 111: /// put a [value] under the [key] if that [key] existed @returns existed or not
1.58.2.8! paf 112: bool put_replace(K key, V value) {
1.58.2.7 paf 113: uint code=hash_code(key);
1.58.2.2 paf 114: uint index=code%allocated;
115: for(Pair *pair=refs[index]; pair; pair=pair->link)
116: if(pair->code==code && pair->key==key) {
117: // found a pair with the same key, replacing
118: pair->value=value;
119: return true;
120: }
121:
122: // proper pair not found
123: return false;
124: }
1.18 paf 125:
1.51 paf 126: /// put a [value] under the [key] if that [key] NOT existed @returns existed or not
1.58.2.8! paf 127: bool put_dont_replace(K key, V value) {
1.58.2.2 paf 128: if(is_full())
129: expand();
130:
1.58.2.7 paf 131: uint code=hash_code(key);
1.58.2.2 paf 132: uint index=code%allocated;
133: Pair **ref=&refs[index];
134: for(Pair *pair=*ref; pair; pair=pair->link)
135: if(pair->code==code && pair->key==key) {
136: // found a pair with the same key, NOT replacing
137: return true;
138: }
139:
140: // proper pair not found -- create&link_in new pair
141: if(!*ref) // root cell were fused_refs?
142: fused_refs++; // not, we'll use it and record the fact
143: *ref=new Pair(code, key, value, *ref);
144: fpairs_count++;
145: return false;
146: }
1.18 paf 147:
1.29 paf 148: /// put all 'src' values if NO with same key existed
1.58.2.2 paf 149: void merge_dont_replace(const Hash& src) {
150: for(int i=0; i<src.allocated; i++)
151: for(Pair *pair=src.refs[i]; pair; pair=pair->link)
152: put_dont_replace(pair->key, pair->value);
153: // MAY:optimize this.allocated==src.allocated case
1.36 paf 154: }
1.11 paf 155:
1.29 paf 156: /// number of elements in hash
1.58.2.2 paf 157: int count() const { return fpairs_count; }
1.25 paf 158:
1.58.2.2 paf 159: /// iterate over all pairs
160: template<typename I> void for_each(void callback(K, V, I), I info) const {
161: Pair **ref=refs;
162: for(int index=0; index<allocated; index++)
163: for(Pair *pair=*ref++; pair; pair=pair->link)
164: callback(pair->key, pair->value, info);
165: }
1.45 paf 166:
1.58.2.2 paf 167: /// iterate over all pairs, passing references
168: template<typename I> void for_each(void callback(K, V&, I), I info) const {
169: Pair **ref=refs;
170: for(int index=0; index<allocated; index++)
171: for(Pair *pair=*ref++; pair; pair=pair->link)
172: callback(pair->key, pair->value, info);
173: }
1.38 paf 174:
1.58.2.2 paf 175: /// iterate over all pairs until condition becomes true, return that element
176: template<typename I> V *first_that(bool callback(K, V, I), I info) const {
177: Pair **ref=refs;
178: for(int index=0; index<allocated; index++)
179: for(Pair *pair=*ref++; pair; pair=pair->link)
180: if(callback(pair->key, pair->value, info))
181: return &pair->value;
182:
183: return 0;
184: }
1.27 paf 185:
1.29 paf 186: /// remove all elements
1.58.2.2 paf 187: void clear() {
188: destroy_pairs(); memset(refs, 0, sizeof(*refs)*allocated);
189: fpairs_count=fused_refs=0;
190: }
1.15 paf 191:
1.1 paf 192: private:
193:
1.39 paf 194: /// expand when these %% of allocated exausted
1.1 paf 195: enum {
196: THRESHOLD_PERCENT=75
197: };
1.9 paf 198:
1.39 paf 199: /// the index of [allocated] in [allocates]
1.19 paf 200: int allocates_index;
1.1 paf 201:
1.39 paf 202: /// possible [allocates]. prime numbers
1.58.2.3 paf 203: static uint allocates[];
204:
205: static int allocates_count;
1.1 paf 206:
1.39 paf 207: /// number of allocated pairs
1.19 paf 208: int allocated;
1.1 paf 209:
1.58.2.2 paf 210: /// helper: expanding when fused_refs == threshold
1.1 paf 211: int threshold;
212:
1.39 paf 213: /// used pairs
1.58.2.2 paf 214: int fused_refs;
1.44 parser 215:
216: /// stored pairs total (including those by links)
1.58.2.2 paf 217: int fpairs_count;
1.1 paf 218:
1.39 paf 219: /// pair storage
1.58.2.2 paf 220: class Pair: public PA_Allocated {
1.58.2.4 paf 221: public:
1.1 paf 222: uint code;
1.58.2.8! paf 223: K key;
1.58.2.2 paf 224: V value;
1.1 paf 225: Pair *link;
1.2 paf 226:
1.58.2.8! paf 227: Pair(uint acode, K akey, V avalue, Pair *alink) :
1.1 paf 228: code(acode),
229: key(akey),
230: value(avalue),
1.2 paf 231: link(alink) {}
232: } **refs;
1.1 paf 233:
1.39 paf 234: /// filled to threshold: needs expanding
1.58.2.2 paf 235: bool is_full() { return fused_refs==threshold; }
1.5 paf 236:
1.39 paf 237: /// allocate larger buffer & rehash
1.58.2.2 paf 238: void expand() {
239: int old_allocated=allocated;
240: Pair **old_refs=refs;
241:
242: // allocated bigger refs array
243: allocates_index=allocates_index+1<allocates_count?allocates_index+1:allocates_count-1;
244: allocated=allocates[allocates_index];
245: threshold=allocated*THRESHOLD_PERCENT/100;
246: refs=static_cast<Pair **>(pa_calloc(sizeof(Pair *)*allocated));
247:
248: // rehash
249: Pair **old_ref=old_refs;
250: for(int old_index=0; old_index<old_allocated; old_index++)
251: for(Pair *pair=*old_ref++; pair; ) {
252: Pair *next=pair->link;
253:
254: uint new_index=pair->code%allocated;
255: Pair **new_ref=&refs[new_index];
256: pair->link=*new_ref;
257: *new_ref=pair;
258:
259: pair=next;
260: }
261:
262: delete old_refs;
263: }
264:
265: void destroy_pairs() {
266: Pair **ref=refs;
267: for(int index=0; index<allocated; index++) {
268: Pair *pair=*ref++;
269: while(pair) {
270: Pair *next=pair->link;
271: delete pair;
272: pair=next;
273: }
274: }
275: }
1.4 paf 276:
277: private: //disabled
278:
1.12 paf 279: Hash& operator = (const Hash&) { return *this; }
1.1 paf 280: };
1.58.2.3 paf 281:
282: /* Zend comment: Generated on an Octa-ALPHA 300MHz CPU & 2.5GB RAM monster */
283: template<typename K, typename V>
284: uint Hash<K, V>::allocates[]={
285: 5, 11, 19, 53, 107, 223, 463, 983, 1979, 3907, 7963,
286: 16229, 32531, 65407, 130987, 262237, 524521, 1048793,
287: 2097397, 4194103, 8388857, 16777447, 33554201, 67108961,
288: 134217487, 268435697, 536870683, 1073741621, 2147483399};
289:
290: template<typename K, typename V>
291: int Hash<K, V>::allocates_count=sizeof(allocates)/sizeof(uint);
1.58.2.5 paf 292:
293: /// useful generic hash function
294: inline uint generic_hash_code(uint aresult, const char *start, uint allocated) {
295: uint result=aresult, g;
296: const char *end=start+allocated;
297:
298: while (start<end) {
299: result=(result<<4)+*start++;
300: if ((g=(result&0xF0000000))) {
301: result=result^(g>>24);
302: result=result^g;
303: }
304: }
305: return result;
306: }
1.49 paf 307:
1.58.2.2 paf 308: /// Auto-object used to temporarily substituting/removing hash values
309: template <typename K, typename V>
1.55 paf 310: class Temp_hash_value {
311: Hash& fhash;
1.58.2.8! paf 312: K fname;
1.58.2.2 paf 313: V saved_value;
1.55 paf 314: public:
1.58.2.8! paf 315: Temp_hash_value(Hash<K, V>& ahash, K aname, V avalue) :
1.55 paf 316: fhash(ahash),
317: fname(aname),
318: saved_value(ahash.get(aname)) {
319: fhash.put(aname, avalue);
320: }
321: ~Temp_hash_value() {
322: fhash.put(fname, saved_value);
323: }
324: };
1.1 paf 325:
326: #endif
E-mail:
![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to pa_hash.h CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [parser3project] / parser3 / src / include