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