Annotation of parser3/src/include/pa_hash.h, revision 1.64.2.3
1.28 paf 1: /** @file
1.29 paf 2: Parser: hash class decl.
3:
1.62 paf 4: Copyright (c) 2001-2004 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.59 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.64.2.3! paf 20: static const char * const IDENT_HASH_H="$Date: 2005/07/27 10:39:40 $";
1.1 paf 21:
1.59 paf 22: #include "pa_memory.h"
1.1 paf 23: #include "pa_types.h"
1.59 paf 24:
25: const int HASH_ALLOCATES_COUNT=29;
1.1 paf 26:
1.61 paf 27: /** Zend comment: Generated on an Octa-ALPHA 300MHz CPU & 2.5GB RAM monster
28:
29: paf: HPUX ld could not handle static member: unsatisfied symbols
30: */
31: static uint Hash_allocates[HASH_ALLOCATES_COUNT]={
32: 5, 11, 19, 53, 107, 223, 463, 983, 1979, 3907, 7963,
33: 16229, 32531, 65407, 130987, 262237, 524521, 1048793,
34: 2097397, 4194103, 8388857, 16777447, 33554201, 67108961,
35: 134217487, 268435697, 536870683, 1073741621, 2147483399};
36:
1.29 paf 37: /**
1.59 paf 38: Simple hash.
1.29 paf 39:
1.59 paf 40: Automatically rehashed when almost is_full.
1.51 paf 41: Contains no 0 values.
42: get returning 0 means there were no such.
43: "put value 0" means "remove"
1.29 paf 44: */
1.59 paf 45: template<typename K, typename V> class Hash: public PA_Object {
1.1 paf 46: public:
47:
1.59 paf 48: typedef K key_type;
49: typedef V value_type;
1.3 paf 50:
1.59 paf 51: Hash() {
1.61 paf 52: allocated=Hash_allocates[allocates_index=0];
1.59 paf 53: threshold=allocated*THRESHOLD_PERCENT/100;
54: fpairs_count=fused_refs=0;
55: refs=new(UseGC) Pair*[allocated];
56: }
1.25 paf 57:
1.59 paf 58: Hash(const Hash& source) {
59: allocates_index=source.allocates_index;
60: allocated=source.allocated;
61: threshold=source.threshold;
62: fused_refs=source.fused_refs;
63: fpairs_count=source.fpairs_count;
64: refs=new(UseGC) Pair*[allocated];
65:
66: // clone & rehash
67: Pair **old_ref=source.refs;
68: for(int index=0; index<allocated; index++)
69: for(Pair *pair=*old_ref++; pair; ) {
70: Pair *next=pair->link;
1.45 paf 71:
1.59 paf 72: Pair **new_ref=&refs[index];
73: *new_ref=new Pair(pair->code, pair->key, pair->value, *new_ref);
1.38 paf 74:
1.59 paf 75: pair=next;
76: }
1.43 parser 77: }
78:
1.59 paf 79: /// put a [value] under the [key] @returns existed or not
80: bool put(K key, V value) {
81: if(!value) {
82: remove(key);
83: return false;
84: }
85: if(is_full())
86: expand();
87:
88: uint code=hash_code(key);
89: uint index=code%allocated;
90: Pair **ref=&refs[index];
91: for(Pair *pair=*ref; pair; pair=pair->link)
92: if(pair->code==code && pair->key==key) {
93: // found a pair with the same key
94: pair->value=value;
95: return true;
96: }
97:
98: // proper pair not found -- create&link_in new pair
99: if(!*ref) // root cell were fused_refs?
100: fused_refs++; // not, we'll use it and record the fact
101: *ref=new Pair(code, key, value, *ref);
102: fpairs_count++;
103: return false;
1.24 paf 104: }
1.10 paf 105:
1.63 paf 106: /// put a [value] under the [key] @returns existed or not
107: template<typename R, typename F> R maybe_put(K key, V value, F prevent) {
1.64.2.3! paf 108: if(!value) {
! 109: // they can come here from somewhere (true with maybe_maybe_append, keeping parallel)
! 110: remove(key);
! 111: // this has nothing to do with properties, doing no special property handling here
! 112: return 0;
! 113: }
1.64 paf 114:
1.63 paf 115: if(is_full())
116: expand();
117:
118: uint code=hash_code(key);
119: uint index=code%allocated;
120: Pair **ref=&refs[index];
121: for(Pair *pair=*ref; pair; pair=pair->link)
122: if(pair->code==code && pair->key==key) {
123: // found a pair with the same key
124:
125: // prevent-function intercepted put?
126: if(R result=prevent(pair->value))
127: return result;
128:
129: pair->value=value;
130: return reinterpret_cast<R>(1);
131: }
132:
133: // proper pair not found -- create&link_in new pair
134: if(!*ref) // root cell were fused_refs?
135: fused_refs++; // not, we'll use it and record the fact
136: *ref=new Pair(code, key, value, *ref);
137: fpairs_count++;
138: return 0;
139: }
140:
1.64.2.1 paf 141: /// put a [value] under the [key] @returns existed or not
142: template<typename R, typename F, typename I> R maybe_append(K key, V value, F prevent, I info) {
1.64.2.3! paf 143: if(!value) {
! 144: // they can come here from somewhere (true with maybe_maybe_append, keeping parallel)
! 145: remove(key);
! 146: // this has nothing to do with properties, doing no special property handling here
! 147: return 0;
! 148: }
1.64.2.1 paf 149:
150: if(is_full())
151: expand();
152:
153: uint code=hash_code(key);
154: uint index=code%allocated;
155: Pair **ref=&refs[index];
156: for(Pair *pair=*ref; pair; pair=pair->link)
157: if(pair->code==code && pair->key==key) {
158: // found a pair with the same key
159: pair->value=value;
160: return reinterpret_cast<R>(1);
161: }
162:
163: // proper pair not found
164: // prevent-function intercepted put?
165: if(R result=prevent(value, info))
1.64.2.2 paf 166: return result;
167:
168: //create&link_in new pair
169: if(!*ref) // root cell were fused_refs?
170: fused_refs++; // not, we'll use it and record the fact
171: *ref=new Pair(code, key, value, *ref);
172: fpairs_count++;
173: return 0;
174: }
175:
176: /// put a [value] under the [key] @returns existed or not
177: template<typename R, typename F1, typename F2, typename I>
178: R maybe_maybe_append(K key, V value, F1 prevent_replace, F2 prevent_append, I info)
179: {
1.64.2.3! paf 180: if(!value) {
! 181: // they can come here from Temp_value_element::dctor to restore some empty value
! 182: remove(key);
! 183: // this has nothing to do with properties, doing no special property handling here
! 184: return 0;
! 185: }
1.64.2.2 paf 186:
187: if(is_full())
188: expand();
189:
190: uint code=hash_code(key);
191: uint index=code%allocated;
192: Pair **ref=&refs[index];
193: for(Pair *pair=*ref; pair; pair=pair->link)
194: if(pair->code==code && pair->key==key) {
195: // found a pair with the same key
196:
197: // prevent-function intercepted put?
198: if(R result=prevent_replace(pair->value, info))
199: return result;
200:
201: pair->value=value;
202: return reinterpret_cast<R>(1);
203: }
204:
205: // proper pair not found
206: // prevent-function intercepted put?
207: if(R result=prevent_append(value, info))
1.64.2.1 paf 208: return result;
209:
210: //create&link_in new pair
211: if(!*ref) // root cell were fused_refs?
212: fused_refs++; // not, we'll use it and record the fact
213: *ref=new Pair(code, key, value, *ref);
214: fpairs_count++;
215: return 0;
216: }
217:
1.59 paf 218: /// remove the [key] @returns existed or not
219: bool remove(K key) {
220: uint code=hash_code(key);
221: uint index=code%allocated;
222: for(Pair **ref=&refs[index]; *ref; ref=&(*ref)->link)
223: if((*ref)->code==code && (*ref)->key==key) {
224: // found a pair with the same key
225: Pair *next=(*ref)->link;
226: delete *ref;
227: *ref=next;
228: --fpairs_count;
229: return true;
230: }
1.8 paf 231:
1.59 paf 232: return false;
233: }
1.48 paf 234:
1.59 paf 235: /// get associated [value] by the [key]
236: V get(K key) const {
237: uint code=hash_code(key);
238: uint index=code%allocated;
239: for(Pair *pair=refs[index]; pair; pair=pair->link)
240: if(pair->code==code && pair->key==key)
241: return pair->value;
242:
243: return V(0);
1.33 paf 244: }
1.64.2.3! paf 245:
1.51 paf 246: /// put a [value] under the [key] if that [key] existed @returns existed or not
1.63 paf 247: bool put_replaced(K key, V value) {
1.59 paf 248: if(!value) {
249: remove(key);
250: return false;
251: }
252: uint code=hash_code(key);
253: uint index=code%allocated;
254: for(Pair *pair=refs[index]; pair; pair=pair->link)
255: if(pair->code==code && pair->key==key) {
256: // found a pair with the same key, replacing
257: pair->value=value;
258: return true;
259: }
260:
261: // proper pair not found
262: return false;
1.64 paf 263: }
264:
265: /// put a [value] under the [key] if that [key] existed @returns existed or not
266: template<typename R, typename F> R maybe_put_replaced(K key, V value, F prevent) {
1.64.2.3! paf 267: if(!value) {
! 268: // they can come here from Temp_value_element::dctor to restore some empty value
! 269: remove(key);
! 270: // this has nothing to do with properties, doing no special property handling here
! 271: return 0;
! 272: }
1.64 paf 273:
274: uint code=hash_code(key);
275: uint index=code%allocated;
276: for(Pair *pair=refs[index]; pair; pair=pair->link)
277: if(pair->code==code && pair->key==key) {
278: // found a pair with the same key, replacing
279: // prevent-function intercepted put?
280: if(R result=prevent(pair->value))
281: return result;
282:
283: pair->value=value;
284: return reinterpret_cast<R>(1);
285: }
286:
287: // proper pair not found
288: return 0;
1.59 paf 289: }
1.18 paf 290:
1.51 paf 291: /// put a [value] under the [key] if that [key] NOT existed @returns existed or not
1.59 paf 292: bool put_dont_replace(K key, V value) {
293: if(!value) {
294: remove(key);
295: return false;
296: }
297: if(is_full())
298: expand();
299:
300: uint code=hash_code(key);
301: uint index=code%allocated;
302: Pair **ref=&refs[index];
303: for(Pair *pair=*ref; pair; pair=pair->link)
304: if(pair->code==code && pair->key==key) {
305: // found a pair with the same key, NOT replacing
306: return true;
307: }
308:
309: // proper pair not found -- create&link_in new pair
310: if(!*ref) // root cell were fused_refs?
311: fused_refs++; // not, we'll use it and record the fact
312: *ref=new Pair(code, key, value, *ref);
313: fpairs_count++;
314: return false;
315: }
1.18 paf 316:
1.59 paf 317: /** put all 'src' values if NO with same key existed
318: @todo optimize this.allocated==src.allocated case
319: */
320: void merge_dont_replace(const Hash& src) {
321: for(int i=0; i<src.allocated; i++)
322: for(Pair *pair=src.refs[i]; pair; pair=pair->link)
323: put_dont_replace(pair->key, pair->value);
1.36 paf 324: }
1.11 paf 325:
1.29 paf 326: /// number of elements in hash
1.59 paf 327: int count() const { return fpairs_count; }
1.25 paf 328:
1.59 paf 329: /// iterate over all pairs
330: template<typename I> void for_each(void callback(K, V, I), I info) const {
331: Pair **ref=refs;
332: for(int index=0; index<allocated; index++)
333: for(Pair *pair=*ref++; pair; pair=pair->link)
334: callback(pair->key, pair->value, info);
335: }
1.45 paf 336:
1.59 paf 337: /// iterate over all pairs
338: template<typename I> void for_each_ref(void callback(K, V&, I), I info) const {
339: Pair **ref=refs;
340: for(int index=0; index<allocated; index++)
341: for(Pair *pair=*ref++; pair; pair=pair->link)
342: callback(pair->key, pair->value, info);
343: }
1.38 paf 344:
1.59 paf 345: /// iterate over all pairs until condition becomes true, return that element
346: template<typename I> V first_that(bool callback(K, V, I), I info) const {
347: Pair **ref=refs;
348: for(int index=0; index<allocated; index++)
349: for(Pair *pair=*ref++; pair; pair=pair->link)
350: if(callback(pair->key, pair->value, info))
351: return pair->value;
352:
353: return V(0);
354: }
1.27 paf 355:
1.29 paf 356: /// remove all elements
1.59 paf 357: void clear() {
358: memset(refs, 0, sizeof(*refs)*allocated);
359: fpairs_count=fused_refs=0;
360: }
1.15 paf 361:
1.1 paf 362: private:
363:
1.39 paf 364: /// expand when these %% of allocated exausted
1.1 paf 365: enum {
366: THRESHOLD_PERCENT=75
367: };
1.9 paf 368:
1.61 paf 369: /// the index of [allocated] in [Hash_allocates]
1.19 paf 370: int allocates_index;
1.1 paf 371:
1.39 paf 372: /// number of allocated pairs
1.19 paf 373: int allocated;
1.1 paf 374:
1.59 paf 375: /// helper: expanding when fused_refs == threshold
1.1 paf 376: int threshold;
377:
1.39 paf 378: /// used pairs
1.59 paf 379: int fused_refs;
1.44 parser 380:
381: /// stored pairs total (including those by links)
1.59 paf 382: int fpairs_count;
1.1 paf 383:
1.39 paf 384: /// pair storage
1.59 paf 385: class Pair: public PA_Allocated {
386: public:
1.1 paf 387: uint code;
1.59 paf 388: K key;
389: V value;
1.1 paf 390: Pair *link;
1.2 paf 391:
1.59 paf 392: Pair(uint acode, K akey, V avalue, Pair *alink) :
1.1 paf 393: code(acode),
394: key(akey),
395: value(avalue),
1.2 paf 396: link(alink) {}
397: } **refs;
1.1 paf 398:
1.39 paf 399: /// filled to threshold: needs expanding
1.59 paf 400: bool is_full() { return fused_refs==threshold; }
1.5 paf 401:
1.39 paf 402: /// allocate larger buffer & rehash
1.59 paf 403: void expand() {
404: int old_allocated=allocated;
405: Pair **old_refs=refs;
406:
407: allocates_index=allocates_index+1<HASH_ALLOCATES_COUNT?allocates_index+1:HASH_ALLOCATES_COUNT-1;
408: // allocated bigger refs array
1.61 paf 409: allocated=Hash_allocates[allocates_index];
1.59 paf 410: threshold=allocated*THRESHOLD_PERCENT/100;
411: refs=new(UseGC) Pair*[allocated];
412:
413: // rehash
414: Pair **old_ref=old_refs;
415: for(int old_index=0; old_index<old_allocated; old_index++)
416: for(Pair *pair=*old_ref++; pair; ) {
417: Pair *next=pair->link;
418:
419: uint new_index=pair->code%allocated;
420: Pair **new_ref=&refs[new_index];
421: pair->link=*new_ref;
422: *new_ref=pair;
423:
424: pair=next;
425: }
426:
427: delete[] old_refs;
428: }
1.4 paf 429:
430: private: //disabled
431:
1.12 paf 432: Hash& operator = (const Hash&) { return *this; }
1.1 paf 433: };
1.59 paf 434:
435: /// useful generic hash function
436: inline void generic_hash_code(uint& result, char c) {
437: result=(result<<4)+c;
438: if(uint g=(result&0xF0000000)) {
439: result=result^(g>>24);
440: result=result^g;
441: }
442: }
443: /// useful generic hash function
444: inline void generic_hash_code(uint& result, const char* s) {
445: while(char c=*s++) {
446: result=(result<<4)+c;
447: if(uint g=(result&0xF0000000)) {
448: result=result^(g>>24);
449: result=result^g;
450: }
451: }
452: }
453:
454: /// useful generic hash function
455: inline void generic_hash_code(uint& result, const char* buf, size_t size) {
456: const char* end=buf+size;
457: while(buf<end) {
458: result=(result<<4)+*buf++;
459: if(uint g=(result&0xF0000000)) {
460: result=result^(g>>24);
461: result=result^g;
462: }
463: }
464: }
465:
466: /// simple hash code of int. used by EXIF mapping
467: inline uint hash_code(int self) {
468: uint result=0;
469: generic_hash_code(result, (const char*)&self, sizeof(self));
470: return result;
471: }
472:
473: /// Auto-object used to temporarily substituting/removing hash values
474: template <typename K, typename V>
1.55 paf 475: class Temp_hash_value {
1.59 paf 476: Hash<K, V>& fhash;
477: K fname;
478: V saved_value;
1.55 paf 479: public:
1.59 paf 480: Temp_hash_value(Hash<K, V>& ahash, K aname, V avalue) :
1.55 paf 481: fhash(ahash),
482: fname(aname),
483: saved_value(ahash.get(aname)) {
484: fhash.put(aname, avalue);
485: }
486: ~Temp_hash_value() {
487: fhash.put(fname, saved_value);
488: }
489: };
1.1 paf 490:
491: #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