Annotation of parser3/src/include/pa_hash.h, revision 1.76
1.28 paf 1: /** @file
1.29 paf 2: Parser: hash class decl.
3:
1.74 misha 4: Copyright (c) 2001-2009 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.76 ! misha 20: static const char * const IDENT_HASH_H="$Date: 2009-07-07 23:49:54 $";
1.1 paf 21:
1.59 paf 22: #include "pa_memory.h"
1.1 paf 23: #include "pa_types.h"
1.74 misha 24: #include "pa_string.h"
1.59 paf 25:
26: const int HASH_ALLOCATES_COUNT=29;
1.1 paf 27:
1.61 paf 28: /** Zend comment: Generated on an Octa-ALPHA 300MHz CPU & 2.5GB RAM monster
29:
30: paf: HPUX ld could not handle static member: unsatisfied symbols
31: */
32: static uint Hash_allocates[HASH_ALLOCATES_COUNT]={
33: 5, 11, 19, 53, 107, 223, 463, 983, 1979, 3907, 7963,
34: 16229, 32531, 65407, 130987, 262237, 524521, 1048793,
35: 2097397, 4194103, 8388857, 16777447, 33554201, 67108961,
36: 134217487, 268435697, 536870683, 1073741621, 2147483399};
37:
1.68 misha 38: /// useful generic hash function
39: inline void generic_hash_code(uint& result, char c) {
40: result=(result<<4)+c;
41: if(uint g=(result&0xF0000000)) {
42: result=result^(g>>24);
43: result=result^g;
44: }
45: }
46: /// useful generic hash function
47: inline void generic_hash_code(uint& result, const char* s) {
48: while(char c=*s++) {
49: result=(result<<4)+c;
50: if(uint g=(result&0xF0000000)) {
51: result=result^(g>>24);
52: result=result^g;
53: }
54: }
55: }
56:
57: /// useful generic hash function
58: inline void generic_hash_code(uint& result, const char* buf, size_t size) {
59: const char* end=buf+size;
60: while(buf<end) {
61: result=(result<<4)+*buf++;
62: if(uint g=(result&0xF0000000)) {
63: result=result^(g>>24);
64: result=result^g;
65: }
66: }
67: }
68:
69: /// simple hash code of int. used by EXIF mapping
70: inline uint hash_code(int self) {
71: uint result=0;
72: generic_hash_code(result, (const char*)&self, sizeof(self));
73: return result;
74: }
75:
1.75 misha 76: #endif // PA_HASH_H
77:
78: #ifndef PA_HASH_CLASS
79: #define PA_HASH_CLASS
1.29 paf 80: /**
1.59 paf 81: Simple hash.
1.29 paf 82:
1.59 paf 83: Automatically rehashed when almost is_full.
1.51 paf 84: Contains no 0 values.
85: get returning 0 means there were no such.
86: "put value 0" means "remove"
1.29 paf 87: */
1.75 misha 88: #ifdef HASH_ORDER
89:
90: #undef HASH
91: #undef HASH_STRING
92: #undef NEW_PAIR
93:
94: #define HASH OrderedHash
95: #define HASH_STRING OrderedHashString
96: #define NEW_PAIR(code, key, value) *ref=new Pair(code, key, value, *ref, this->last); this->last=&((*ref)->next)
97:
98: #else
99:
100: #define HASH Hash
101: #define HASH_STRING HashString
102: #define NEW_PAIR(code, key, value) *ref=new Pair(code, key, value, *ref)
103:
104: #endif
105:
106: template<typename K, typename V> class HASH: public PA_Object {
1.1 paf 107: public:
108:
1.59 paf 109: typedef K key_type;
110: typedef V value_type;
1.3 paf 111:
1.75 misha 112: HASH() {
1.61 paf 113: allocated=Hash_allocates[allocates_index=0];
1.59 paf 114: threshold=allocated*THRESHOLD_PERCENT/100;
115: fpairs_count=fused_refs=0;
116: refs=new(UseGC) Pair*[allocated];
1.75 misha 117: #ifdef HASH_ORDER
118: first=0;
119: last=&first;
120: #endif
1.59 paf 121: }
1.25 paf 122:
1.75 misha 123: HASH(const HASH& source) {
1.59 paf 124: allocates_index=source.allocates_index;
125: allocated=source.allocated;
126: threshold=source.threshold;
127: fused_refs=source.fused_refs;
128: fpairs_count=source.fpairs_count;
129: refs=new(UseGC) Pair*[allocated];
1.75 misha 130: #ifdef HASH_ORDER
131: first=0;
132: last=&first;
133: #endif
1.59 paf 134: // clone & rehash
135: Pair **old_ref=source.refs;
136: for(int index=0; index<allocated; index++)
137: for(Pair *pair=*old_ref++; pair; ) {
138: Pair *next=pair->link;
1.45 paf 139:
1.75 misha 140: Pair **ref=&refs[index];
141: NEW_PAIR(pair->code, pair->key, pair->value);
1.38 paf 142:
1.59 paf 143: pair=next;
144: }
1.43 parser 145: }
146:
1.73 misha 147: #ifdef USE_DESTRUCTORS
1.75 misha 148: ~HASH() {
1.72 misha 149: Pair **ref=refs;
150: for(int index=0; index<allocated; index++)
151: for(Pair *pair=*ref++; pair;){
152: Pair *next=pair->link;
153: delete pair;
154: pair=next;
155: }
1.71 misha 156: delete[] refs;
157: }
1.73 misha 158: #endif
1.71 misha 159:
1.59 paf 160: /// put a [value] under the [key] @returns existed or not
161: bool put(K key, V value) {
162: if(!value) {
163: remove(key);
164: return false;
165: }
166: if(is_full())
167: expand();
168:
169: uint code=hash_code(key);
170: uint index=code%allocated;
171: Pair **ref=&refs[index];
172: for(Pair *pair=*ref; pair; pair=pair->link)
173: if(pair->code==code && pair->key==key) {
174: // found a pair with the same key
175: pair->value=value;
176: return true;
177: }
178:
179: // proper pair not found -- create&link_in new pair
180: if(!*ref) // root cell were fused_refs?
181: fused_refs++; // not, we'll use it and record the fact
1.75 misha 182: NEW_PAIR(code, key, value);
1.59 paf 183: fpairs_count++;
184: return false;
1.24 paf 185: }
1.10 paf 186:
1.63 paf 187: /// put a [value] under the [key] @returns existed or not
1.65 paf 188: template<typename R, typename F, typename I> R replace_maybe_append(K key, V value, F prevent, I info) {
189: if(!value) {
190: // they can come here from somewhere (true with maybe_replace_maybe_append, keeping parallel)
191: remove(key);
192: // this has nothing to do with properties, doing no special property handling here
193: return 0;
194: }
1.64 paf 195:
1.63 paf 196: if(is_full())
197: expand();
198:
199: uint code=hash_code(key);
200: uint index=code%allocated;
201: Pair **ref=&refs[index];
202: for(Pair *pair=*ref; pair; pair=pair->link)
203: if(pair->code==code && pair->key==key) {
204: // found a pair with the same key
1.65 paf 205: pair->value=value;
206: return reinterpret_cast<R>(1);
207: }
208:
209: // proper pair not found
210: // prevent-function intercepted append?
211: if(R result=prevent(value, info))
212: return result;
213:
214: //create&link_in new pair
215: if(!*ref) // root cell were fused_refs?
216: fused_refs++; // not, we'll use it and record the fact
1.75 misha 217: NEW_PAIR(code, key, value);
1.65 paf 218: fpairs_count++;
219: return 0;
220: }
1.63 paf 221:
1.65 paf 222: /// put a [value] under the [key] @returns existed or not
223: template<typename R, typename F1, typename F2, typename I>
224: R maybe_replace_maybe_append(K key, V value, F1 prevent_replace, F2 prevent_append, I info)
225: {
226: if(!value) {
227: // they can come here from Temp_value_element::dctor to restore some empty value
228: remove(key);
229: // this has nothing to do with properties, doing no special property handling here
230: return 0;
231: }
232:
233: if(is_full())
234: expand();
235:
236: uint code=hash_code(key);
237: uint index=code%allocated;
238: Pair **ref=&refs[index];
239: for(Pair *pair=*ref; pair; pair=pair->link)
240: if(pair->code==code && pair->key==key) {
241: // found a pair with the same key
242:
243: // prevent-function intercepted replace?
244: if(R result=prevent_replace(pair->value, info))
1.63 paf 245: return result;
246:
247: pair->value=value;
248: return reinterpret_cast<R>(1);
249: }
250:
1.65 paf 251: // proper pair not found
252: // prevent-function intercepted append?
253: if(R result=prevent_append(value, info))
254: return result;
255:
256: //create&link_in new pair
1.63 paf 257: if(!*ref) // root cell were fused_refs?
258: fused_refs++; // not, we'll use it and record the fact
1.75 misha 259: NEW_PAIR(code, key, value);
1.63 paf 260: fpairs_count++;
261: return 0;
262: }
263:
1.65 paf 264: /// put a [value] under the [key] @returns existed or not
265: template<typename R, typename F1, typename I>
266: R maybe_replace_never_append(K key, V value, F1 prevent_replace, I info)
267: {
268: if(!value) {
269: // they can come here from somewhere (true with maybe_replace_maybe_append, keeping parallel)
270: remove(key);
271: // this has nothing to do with properties, doing no special property handling here
272: return 0;
273: }
274:
275: if(is_full())
276: expand();
277:
278: uint code=hash_code(key);
279: uint index=code%allocated;
280: Pair **ref=&refs[index];
281: for(Pair *pair=*ref; pair; pair=pair->link)
282: if(pair->code==code && pair->key==key) {
283: // found a pair with the same key
284:
285: // prevent-function intercepted replace?
286: if(R result=prevent_replace(pair->value, info))
287: return result;
288:
289: pair->value=value;
290: return reinterpret_cast<R>(1);
291: }
292:
293: return 0;
294: }
295:
1.59 paf 296: /// remove the [key] @returns existed or not
297: bool remove(K key) {
298: uint code=hash_code(key);
299: uint index=code%allocated;
1.75 misha 300: for(Pair **ref=&refs[index]; *ref; ref=&(*ref)->link){
301: Pair *pair=*ref;
302: if(pair->code==code && pair->key==key) {
1.59 paf 303: // found a pair with the same key
1.75 misha 304: Pair *next=pair->link;
305: #ifdef HASH_ORDER
306: *(pair->prev)=pair->next;
307: if(pair->next)
308: pair->next->prev=pair->prev;
309: else
310: last=pair->prev;
311: #endif
312: delete pair;
1.59 paf 313: *ref=next;
314: --fpairs_count;
315: return true;
316: }
1.75 misha 317: }
1.8 paf 318:
1.59 paf 319: return false;
320: }
1.48 paf 321:
1.70 misha 322: /// return true if key exists
1.69 misha 323: bool contains(K key){
1.67 misha 324: uint code=hash_code(key);
325: uint index=code%allocated;
1.70 misha 326: for(Pair *pair=refs[index]; pair; pair=pair->link){
327: if(pair->code==code && pair->key==key)
1.67 misha 328: return true;
329: }
330:
331: return false;
332: }
333:
1.59 paf 334: /// get associated [value] by the [key]
335: V get(K key) const {
336: uint code=hash_code(key);
337: uint index=code%allocated;
338: for(Pair *pair=refs[index]; pair; pair=pair->link)
339: if(pair->code==code && pair->key==key)
340: return pair->value;
341:
342: return V(0);
1.33 paf 343: }
1.70 misha 344:
1.51 paf 345: /// put a [value] under the [key] if that [key] existed @returns existed or not
1.63 paf 346: bool put_replaced(K key, V value) {
1.59 paf 347: if(!value) {
348: remove(key);
349: return false;
350: }
351: uint code=hash_code(key);
352: uint index=code%allocated;
353: for(Pair *pair=refs[index]; pair; pair=pair->link)
354: if(pair->code==code && pair->key==key) {
355: // found a pair with the same key, replacing
356: pair->value=value;
357: return true;
358: }
359:
360: // proper pair not found
361: return false;
1.64 paf 362: }
363:
364: /// put a [value] under the [key] if that [key] existed @returns existed or not
365: template<typename R, typename F> R maybe_put_replaced(K key, V value, F prevent) {
1.65 paf 366: if(!value) {
367: // they can come here from Temp_value_element::dctor to restore some empty value
368: remove(key);
369: // this has nothing to do with properties, doing no special property handling here
370: return 0;
371: }
1.64 paf 372:
373: uint code=hash_code(key);
374: uint index=code%allocated;
375: for(Pair *pair=refs[index]; pair; pair=pair->link)
376: if(pair->code==code && pair->key==key) {
377: // found a pair with the same key, replacing
378: // prevent-function intercepted put?
379: if(R result=prevent(pair->value))
380: return result;
381:
382: pair->value=value;
383: return reinterpret_cast<R>(1);
384: }
385:
386: // proper pair not found
387: return 0;
1.59 paf 388: }
1.18 paf 389:
1.51 paf 390: /// put a [value] under the [key] if that [key] NOT existed @returns existed or not
1.59 paf 391: bool put_dont_replace(K key, V value) {
392: if(!value) {
393: remove(key);
394: return false;
395: }
396: if(is_full())
397: expand();
398:
399: uint code=hash_code(key);
400: uint index=code%allocated;
401: Pair **ref=&refs[index];
402: for(Pair *pair=*ref; pair; pair=pair->link)
403: if(pair->code==code && pair->key==key) {
404: // found a pair with the same key, NOT replacing
405: return true;
406: }
407:
408: // proper pair not found -- create&link_in new pair
409: if(!*ref) // root cell were fused_refs?
410: fused_refs++; // not, we'll use it and record the fact
1.75 misha 411: NEW_PAIR(code, key, value);
1.59 paf 412: fpairs_count++;
413: return false;
414: }
1.18 paf 415:
1.59 paf 416: /** put all 'src' values if NO with same key existed
417: @todo optimize this.allocated==src.allocated case
418: */
1.75 misha 419: void merge_dont_replace(const HASH& src) {
1.59 paf 420: for(int i=0; i<src.allocated; i++)
421: for(Pair *pair=src.refs[i]; pair; pair=pair->link)
422: put_dont_replace(pair->key, pair->value);
1.36 paf 423: }
1.11 paf 424:
1.29 paf 425: /// number of elements in hash
1.59 paf 426: int count() const { return fpairs_count; }
1.25 paf 427:
1.59 paf 428: /// iterate over all pairs
429: template<typename I> void for_each(void callback(K, V, I), I info) const {
1.76 ! misha 430: #ifdef HASH_ORDER
! 431: for(Pair *pair=first; pair; pair=pair->next)
! 432: callback(pair->key, pair->value, info);
! 433: #else
1.59 paf 434: Pair **ref=refs;
435: for(int index=0; index<allocated; index++)
436: for(Pair *pair=*ref++; pair; pair=pair->link)
437: callback(pair->key, pair->value, info);
1.76 ! misha 438: #endif
1.59 paf 439: }
1.45 paf 440:
1.59 paf 441: /// iterate over all pairs
442: template<typename I> void for_each_ref(void callback(K, V&, I), I info) const {
1.76 ! misha 443: #ifdef HASH_ORDER
! 444: for(Pair *pair=first; pair; pair=pair->next)
! 445: callback(pair->key, pair->value, info);
! 446: #else
1.59 paf 447: Pair **ref=refs;
448: for(int index=0; index<allocated; index++)
449: for(Pair *pair=*ref++; pair; pair=pair->link)
450: callback(pair->key, pair->value, info);
1.76 ! misha 451: #endif
1.59 paf 452: }
1.38 paf 453:
1.59 paf 454: /// iterate over all pairs until condition becomes true, return that element
455: template<typename I> V first_that(bool callback(K, V, I), I info) const {
1.75 misha 456: #ifdef HASH_ORDER
457: for(Pair *pair=first; pair; pair=pair->next)
458: if(callback(pair->key, pair->value, info))
459: return pair->value;
460: #else
1.59 paf 461: Pair **ref=refs;
462: for(int index=0; index<allocated; index++)
463: for(Pair *pair=*ref++; pair; pair=pair->link)
464: if(callback(pair->key, pair->value, info))
465: return pair->value;
1.75 misha 466: #endif
1.59 paf 467: return V(0);
468: }
1.27 paf 469:
1.29 paf 470: /// remove all elements
1.59 paf 471: void clear() {
472: memset(refs, 0, sizeof(*refs)*allocated);
473: fpairs_count=fused_refs=0;
1.75 misha 474: #ifdef HASH_ORDER
475: first=0;
476: last=&first;
477: #endif
1.59 paf 478: }
1.15 paf 479:
1.74 misha 480: protected:
1.1 paf 481:
1.39 paf 482: /// expand when these %% of allocated exausted
1.1 paf 483: enum {
484: THRESHOLD_PERCENT=75
485: };
1.9 paf 486:
1.61 paf 487: /// the index of [allocated] in [Hash_allocates]
1.19 paf 488: int allocates_index;
1.1 paf 489:
1.39 paf 490: /// number of allocated pairs
1.19 paf 491: int allocated;
1.1 paf 492:
1.59 paf 493: /// helper: expanding when fused_refs == threshold
1.1 paf 494: int threshold;
495:
1.39 paf 496: /// used pairs
1.59 paf 497: int fused_refs;
1.44 parser 498:
499: /// stored pairs total (including those by links)
1.59 paf 500: int fpairs_count;
1.1 paf 501:
1.39 paf 502: /// pair storage
1.59 paf 503: class Pair: public PA_Allocated {
504: public:
1.1 paf 505: uint code;
1.59 paf 506: K key;
507: V value;
1.1 paf 508: Pair *link;
1.75 misha 509: #ifdef HASH_ORDER
510: Pair **prev;
511: Pair *next;
512:
513: Pair(uint acode, K akey, V avalue, Pair *alink, Pair **aprev) : code(acode), key(akey), value(avalue), link(alink),
514: prev(aprev), next(0) { *aprev=this; }
515: #else
516: Pair(uint acode, K akey, V avalue, Pair *alink) : code(acode), key(akey), value(avalue), link(alink) {}
517: #endif
1.2 paf 518: } **refs;
1.1 paf 519:
1.75 misha 520: #ifdef HASH_ORDER
521: Pair *first;
522: Pair **last;
523: #endif
524:
1.39 paf 525: /// filled to threshold: needs expanding
1.59 paf 526: bool is_full() { return fused_refs==threshold; }
1.5 paf 527:
1.39 paf 528: /// allocate larger buffer & rehash
1.59 paf 529: void expand() {
530: int old_allocated=allocated;
531: Pair **old_refs=refs;
532:
533: allocates_index=allocates_index+1<HASH_ALLOCATES_COUNT?allocates_index+1:HASH_ALLOCATES_COUNT-1;
534: // allocated bigger refs array
1.61 paf 535: allocated=Hash_allocates[allocates_index];
1.59 paf 536: threshold=allocated*THRESHOLD_PERCENT/100;
537: refs=new(UseGC) Pair*[allocated];
538:
539: // rehash
540: Pair **old_ref=old_refs;
541: for(int old_index=0; old_index<old_allocated; old_index++)
542: for(Pair *pair=*old_ref++; pair; ) {
543: Pair *next=pair->link;
544:
545: uint new_index=pair->code%allocated;
546: Pair **new_ref=&refs[new_index];
547: pair->link=*new_ref;
548: *new_ref=pair;
549:
550: pair=next;
551: }
552:
553: delete[] old_refs;
554: }
1.4 paf 555:
556: private: //disabled
557:
1.75 misha 558: HASH& operator = (const HASH&) { return *this; }
1.1 paf 559: };
1.59 paf 560:
1.74 misha 561: /**
1.75 misha 562: Simple String::body hash.
563: Allows hash code caching
1.74 misha 564: */
565:
566: #ifdef HASH_CODE_CACHING
567:
1.75 misha 568: template<typename V> class HASH_STRING: public HASH<const CORD,V> {
1.74 misha 569: public:
570:
1.75 misha 571: typedef typename HASH<const CORD,V>::Pair Pair;
1.74 misha 572: typedef const String::Body &K;
573:
574: typedef K key_type;
575:
576: /// put a [value] under the [key] @returns existed or not
577: bool put(K str, V value) {
578: if(!value) {
579: remove(str);
580: return false;
581: }
582: if(this->is_full())
583: this->expand();
584:
585: CORD key=str.get_cord();
586:
587: uint code=str.get_hash_code();
588: uint index=code%this->allocated;
589: Pair **ref=&this->refs[index];
590: for(Pair *pair=*ref; pair; pair=pair->link)
591: if(pair->code==code && CORD_cmp(pair->key,key)==0) {
592: // found a pair with the same key
593: pair->value=value;
594: return true;
595: }
596:
597: // proper pair not found -- create&link_in new pair
598: if(!*ref) // root cell were fused_refs?
599: this->fused_refs++; // not, we'll use it and record the fact
1.75 misha 600: NEW_PAIR(code, key, value);
1.74 misha 601: this->fpairs_count++;
602: return false;
603: }
604:
605: /// put a [value] under the [key] @returns existed or not
606: template<typename R, typename F, typename I> R replace_maybe_append(K str, V value, F prevent, I info) {
607: if(!value) {
608: // they can come here from somewhere (true with maybe_replace_maybe_append, keeping parallel)
609: remove(str);
610: // this has nothing to do with properties, doing no special property handling here
611: return 0;
612: }
613:
614: if(this->is_full())
615: this->expand();
616:
617: CORD key=str.get_cord();
618:
619: uint code=str.get_hash_code();
620: uint index=code%this->allocated;
621: Pair **ref=&this->refs[index];
622: for(Pair *pair=*ref; pair; pair=pair->link)
623: if(pair->code==code && CORD_cmp(pair->key,key)==0) {
624: // found a pair with the same key
625: pair->value=value;
626: return reinterpret_cast<R>(1);
627: }
628:
629: // proper pair not found
630: // prevent-function intercepted append?
631: if(R result=prevent(value, info))
632: return result;
633:
634: //create&link_in new pair
635: if(!*ref) // root cell were fused_refs?
636: this->fused_refs++; // not, we'll use it and record the fact
1.75 misha 637: NEW_PAIR(code, key, value);
1.74 misha 638: this->fpairs_count++;
639: return 0;
640: }
641:
642: /// put a [value] under the [key] @returns existed or not
643: template<typename R, typename F1, typename F2, typename I>
644: R maybe_replace_maybe_append(K str, V value, F1 prevent_replace, F2 prevent_append, I info) {
645: if(!value) {
646: // they can come here from Temp_value_element::dctor to restore some empty value
647: remove(str);
648: // this has nothing to do with properties, doing no special property handling here
649: return 0;
650: }
651:
652: if(this->is_full())
653: this->expand();
654:
655: CORD key=str.get_cord();
656:
657: uint code=str.get_hash_code();
658: uint index=code%this->allocated;
659: Pair **ref=&this->refs[index];
660: for(Pair *pair=*ref; pair; pair=pair->link)
661: if(pair->code==code && CORD_cmp(pair->key,key)==0) {
662: // found a pair with the same key
663:
664: // prevent-function intercepted replace?
665: if(R result=prevent_replace(pair->value, info))
666: return result;
667:
668: pair->value=value;
669: return reinterpret_cast<R>(1);
670: }
671:
672: // proper pair not found
673: // prevent-function intercepted append?
674: if(R result=prevent_append(value, info))
675: return result;
676:
677: //create&link_in new pair
678: if(!*ref) // root cell were fused_refs?
679: this->fused_refs++; // not, we'll use it and record the fact
1.75 misha 680: NEW_PAIR(code, key, value);
1.74 misha 681: this->fpairs_count++;
682: return 0;
683: }
684:
685: /// put a [value] under the [key] @returns existed or not
686: template<typename R, typename F1, typename I>
687: R maybe_replace_never_append(K str, V value, F1 prevent_replace, I info) {
688: if(!value) {
689: // they can come here from somewhere (true with maybe_replace_maybe_append, keeping parallel)
690: remove(str);
691: // this has nothing to do with properties, doing no special property handling here
692: return 0;
693: }
694:
695: if(this->is_full())
696: this->expand();
697:
698: CORD key=str.get_cord();
699:
700: uint code=str.get_hash_code();
701: uint index=code%this->allocated;
702: Pair **ref=&this->refs[index];
703: for(Pair *pair=*ref; pair; pair=pair->link)
704: if(pair->code==code && CORD_cmp(pair->key,key)==0) {
705: // found a pair with the same key
706:
707: // prevent-function intercepted replace?
708: if(R result=prevent_replace(pair->value, info))
709: return result;
710:
711: pair->value=value;
712: return reinterpret_cast<R>(1);
713: }
714:
715: return 0;
716:
717: }
718:
719: /// remove the [key] @returns existed or not
720: bool remove(K str) {
721: CORD key=str.get_cord();
722: uint code=str.get_hash_code();
723: uint index=code%this->allocated;
1.75 misha 724: for(Pair **ref=&this->refs[index]; *ref; ref=&(*ref)->link){
725: Pair *pair=*ref;
726: if(pair->code==code && CORD_cmp(pair->key,key)==0) {
1.74 misha 727: // found a pair with the same key
1.75 misha 728: Pair *next=pair->link;
729: #ifdef HASH_ORDER
730: *(pair->prev)=pair->next;
731: if(pair->next)
732: pair->next->prev=pair->prev;
733: else
734: this->last=pair->prev;
735: #endif
736: delete pair;
1.74 misha 737: *ref=next;
738: --this->fpairs_count;
739: return true;
740: }
1.75 misha 741: }
1.74 misha 742:
743: return false;
744: }
745:
746: /// return true if key exists
747: bool contains(K str){
748: CORD key=str.get_cord();
749: uint code=str.get_hash_code();
750: uint index=code%this->allocated;
751: for(Pair *pair=this->refs[index]; pair; pair=pair->link){
752: if(pair->code==code && CORD_cmp(pair->key,key)==0)
753: return true;
754: }
755:
756: return false;
757: }
758:
759: /// get associated [value] by the [key]
760: V get(K str) const {
761: CORD key=str.get_cord();
762: uint code=str.get_hash_code();
763: uint index=code%this->allocated;
764: for(Pair *pair=this->refs[index]; pair; pair=pair->link)
765: if(pair->code==code && CORD_cmp(pair->key,key)==0)
766: return pair->value;
767:
768: return V(0);
769: }
770:
771: /// put a [value] under the [key] if that [key] existed @returns existed or not
772: bool put_replaced(K str, V value) {
773: if(!value) {
774: remove(str);
775: return false;
776: }
777:
778: CORD key=str.get_cord();
779: uint code=str.get_hash_code();
780: uint index=code%this->allocated;
781: for(Pair *pair=this->refs[index]; pair; pair=pair->link)
782: if(pair->code==code && CORD_cmp(pair->key,key)==0) {
783: // found a pair with the same key, replacing
784: pair->value=value;
785: return true;
786: }
787:
788: // proper pair not found
789: return false;
790: }
791:
792: /// put a [value] under the [key] if that [key] existed @returns existed or not
793: template<typename R, typename F> R maybe_put_replaced(K str, V value, F prevent) {
794: if(!value) {
795: // they can come here from Temp_value_element::dctor to restore some empty value
796: remove(str);
797: // this has nothing to do with properties, doing no special property handling here
798: return 0;
799: }
800:
801: CORD key=str.get_cord();
802: uint code=str.get_hash_code();
803: uint index=code%this->allocated;
804: for(Pair *pair=this->refs[index]; pair; pair=pair->link)
805: if(pair->code==code && CORD_cmp(pair->key,key)==0) {
806: // found a pair with the same key, replacing
807: // prevent-function intercepted put?
808: if(R result=prevent(pair->value))
809: return result;
810:
811: pair->value=value;
812: return reinterpret_cast<R>(1);
813: }
814:
815: // proper pair not found
816: return 0;
817: }
818:
819: /// put a [value] under the [key] if that [key] NOT existed @returns existed or not
820: bool put_dont_replace(K str, V value) {
821: if(!value) {
822: remove(str);
823: return false;
824: }
825: if(this->is_full())
826: this->expand();
827:
828: CORD key=str.get_cord();
829: uint code=str.get_hash_code();
830: uint index=code%this->allocated;
831: Pair **ref=&this->refs[index];
832: for(Pair *pair=*ref; pair; pair=pair->link)
833: if(pair->code==code && CORD_cmp(pair->key,key)==0) {
834: // found a pair with the same key, NOT replacing
835: return true;
836: }
837:
838: // proper pair not found -- create&link_in new pair
839: if(!*ref) // root cell were fused_refs?
840: this->fused_refs++; // not, we'll use it and record the fact
1.75 misha 841: NEW_PAIR(code, key, value);
1.74 misha 842: this->fpairs_count++;
843: return false;
844: }
845:
846: /// iterate over all pairs
847: template<typename I> void for_each(void callback(K, V, I), I info) const {
1.76 ! misha 848: #ifdef HASH_ORDER
! 849: for(Pair *pair=first; pair; pair=pair->next)
! 850: callback(pair->key, pair->value, info);
! 851: #else
1.74 misha 852: Pair **ref=this->refs;
853: for(int index=0; index<this->allocated; index++)
854: for(Pair *pair=*ref++; pair; pair=pair->link)
855: callback(String::Body(pair->key, pair->code), pair->value, info);
1.76 ! misha 856: #endif
1.74 misha 857: }
858:
859: /// iterate over all pairs
860: template<typename I> void for_each_ref(void callback(K, V&, I), I info) const {
1.76 ! misha 861: #ifdef HASH_ORDER
! 862: for(Pair *pair=first; pair; pair=pair->next)
! 863: callback(pair->key, pair->value, info);
! 864: #else
1.74 misha 865: Pair **ref=this->refs;
866: for(int index=0; index<this->allocated; index++)
867: for(Pair *pair=*ref++; pair; pair=pair->link)
868: callback(String::Body(pair->key, pair->code), pair->value, info);
1.76 ! misha 869: #endif
1.74 misha 870: }
871:
872: /// iterate over all pairs until condition becomes true, return that element
873: template<typename I> V first_that(bool callback(K, V, I), I info) const {
1.75 misha 874: #ifdef HASH_ORDER
875: for(Pair *pair=this->first; pair; pair=pair->next)
876: if(callback(String::Body(pair->key, pair->code), pair->value, info))
877: return pair->value;
878: #else
1.74 misha 879: Pair **ref=this->refs;
880: for(int index=0; index<this->allocated; index++)
881: for(Pair *pair=*ref++; pair; pair=pair->link)
882: if(callback(String::Body(pair->key, pair->code), pair->value, info))
883: return pair->value;
1.75 misha 884: #endif
1.74 misha 885: return V(0);
886: }
887: };
888: #else
889:
1.75 misha 890: template<typename V> class HASH_STRING: public HASH<const String::Body,V>{};
1.74 misha 891:
892: #endif
893:
1.75 misha 894: #ifndef HASH_ORDER
1.74 misha 895: /// Auto-object used to temporarily substituting/removing string hash values
1.59 paf 896: template <typename K, typename V>
1.55 paf 897: class Temp_hash_value {
1.74 misha 898: HashString<V> &fhash;
1.59 paf 899: K fname;
900: V saved_value;
1.55 paf 901: public:
1.74 misha 902: Temp_hash_value(HashString<V>& ahash, K aname, V avalue) :
1.55 paf 903: fhash(ahash),
904: fname(aname),
905: saved_value(ahash.get(aname)) {
906: fhash.put(aname, avalue);
907: }
908: ~Temp_hash_value() {
909: fhash.put(fname, saved_value);
910: }
911: };
1.75 misha 912: #endif
1.1 paf 913:
1.75 misha 914: #endif //PA_HASH_CLASS
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