Annotation of parser3/src/include/pa_hash.h, revision 1.98
1.28 paf 1: /** @file
1.29 paf 2: Parser: hash class decl.
3:
1.96 moko 4: Copyright (c) 2001-2017 Art. Lebedev Studio (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.98 ! moko 20: #define IDENT_PA_HASH_H "$Id: pa_hash.h,v 1.97 2017/02/15 17:05:21 moko Exp $"
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
1.79 misha 92: #undef HASH_NEW_PAIR
1.88 moko 93: #undef HASH_ORDER_CLEAR
1.79 misha 94: #undef HASH_FOR_EACH
1.75 misha 95:
96: #define HASH OrderedHash
97: #define HASH_STRING OrderedHashString
1.79 misha 98: #define HASH_NEW_PAIR(code, key, value) *ref=new Pair(code, key, value, *ref, this->last); this->last=&((*ref)->next)
1.88 moko 99: #define HASH_ORDER_CLEAR() first=0; last=&first
1.79 misha 100:
101: #define HASH_FOR_EACH \
102: for(Pair *pair=this->first; pair; pair=pair->next)
1.75 misha 103:
104: #else
105:
106: #define HASH Hash
107: #define HASH_STRING HashString
1.79 misha 108: #define HASH_NEW_PAIR(code, key, value) *ref=new Pair(code, key, value, *ref)
1.88 moko 109: #define HASH_ORDER_CLEAR()
1.79 misha 110:
111: #define HASH_FOR_EACH \
112: Pair **ref=this->refs; \
113: for(int index=0; index<this->allocated; index++) \
114: for(Pair *pair=*ref++; pair; pair=pair->link)
1.75 misha 115:
116: #endif
117:
118: template<typename K, typename V> class HASH: public PA_Object {
1.91 moko 119: protected:
120: class Pair;
1.1 paf 121: public:
1.59 paf 122: typedef K key_type;
123: typedef V value_type;
1.3 paf 124:
1.75 misha 125: HASH() {
1.61 paf 126: allocated=Hash_allocates[allocates_index=0];
1.59 paf 127: fpairs_count=fused_refs=0;
1.87 moko 128: refs=new Pair*[allocated];
1.88 moko 129: HASH_ORDER_CLEAR();
1.59 paf 130: }
1.25 paf 131:
1.75 misha 132: HASH(const HASH& source) {
1.59 paf 133: allocates_index=source.allocates_index;
134: allocated=source.allocated;
135: fused_refs=source.fused_refs;
136: fpairs_count=source.fpairs_count;
1.87 moko 137: refs=new Pair*[allocated];
1.81 moko 138: // clone & rehash
1.75 misha 139: #ifdef HASH_ORDER
1.88 moko 140: HASH_ORDER_CLEAR();
1.81 moko 141: for(Pair *pair=source.first; pair; pair=pair->next)
142: {
143: uint index=pair->code%allocated;
144: Pair **ref=&refs[index];
145: HASH_NEW_PAIR(pair->code, pair->key, pair->value);
146: }
147: #else
148: for(int i=0; i<source.allocated; i++)
149: for(Pair *pair=source.refs[i]; pair; pair=pair->link)
150: {
151: Pair **ref=&refs[i];
1.79 misha 152: HASH_NEW_PAIR(pair->code, pair->key, pair->value);
1.59 paf 153: }
1.81 moko 154: #endif
1.43 parser 155: }
156:
1.73 misha 157: #ifdef USE_DESTRUCTORS
1.75 misha 158: ~HASH() {
1.72 misha 159: Pair **ref=refs;
160: for(int index=0; index<allocated; index++)
161: for(Pair *pair=*ref++; pair;){
162: Pair *next=pair->link;
163: delete pair;
164: pair=next;
165: }
1.71 misha 166: delete[] refs;
167: }
1.73 misha 168: #endif
1.71 misha 169:
1.59 paf 170: /// put a [value] under the [key] @returns existed or not
171: bool put(K key, V value) {
172: if(!value) {
173: remove(key);
174: return false;
175: }
176: if(is_full())
177: expand();
178:
179: uint code=hash_code(key);
180: uint index=code%allocated;
181: Pair **ref=&refs[index];
182: for(Pair *pair=*ref; pair; pair=pair->link)
183: if(pair->code==code && pair->key==key) {
184: // found a pair with the same key
185: pair->value=value;
186: return true;
187: }
188:
189: // proper pair not found -- create&link_in new pair
190: if(!*ref) // root cell were fused_refs?
191: fused_refs++; // not, we'll use it and record the fact
1.79 misha 192: HASH_NEW_PAIR(code, key, value);
1.59 paf 193: fpairs_count++;
194: return false;
1.24 paf 195: }
1.10 paf 196:
1.59 paf 197: /// remove the [key] @returns existed or not
198: bool remove(K key) {
199: uint code=hash_code(key);
200: uint index=code%allocated;
1.75 misha 201: for(Pair **ref=&refs[index]; *ref; ref=&(*ref)->link){
202: Pair *pair=*ref;
203: if(pair->code==code && pair->key==key) {
1.59 paf 204: // found a pair with the same key
1.75 misha 205: Pair *next=pair->link;
206: #ifdef HASH_ORDER
207: *(pair->prev)=pair->next;
208: if(pair->next)
209: pair->next->prev=pair->prev;
210: else
211: last=pair->prev;
212: #endif
1.59 paf 213: *ref=next;
214: --fpairs_count;
215: return true;
216: }
1.75 misha 217: }
1.8 paf 218:
1.59 paf 219: return false;
220: }
1.48 paf 221:
1.70 misha 222: /// return true if key exists
1.69 misha 223: bool contains(K key){
1.67 misha 224: uint code=hash_code(key);
225: uint index=code%allocated;
1.70 misha 226: for(Pair *pair=refs[index]; pair; pair=pair->link){
227: if(pair->code==code && pair->key==key)
1.67 misha 228: return true;
229: }
230:
231: return false;
232: }
233:
1.59 paf 234: /// get associated [value] by the [key]
235: V get(K key) const {
236: uint code=hash_code(key);
237: uint index=code%allocated;
238: for(Pair *pair=refs[index]; pair; pair=pair->link)
239: if(pair->code==code && pair->key==key)
240: return pair->value;
241:
242: return V(0);
1.33 paf 243: }
1.70 misha 244:
1.82 misha 245: #ifdef HASH_ORDER
1.86 misha 246: String::Body first_key() const {
1.92 moko 247: #ifdef HASH_CODE_CACHING
1.86 misha 248: return (first) ? String::Body(first->key, first->code) : String::Body();
1.92 moko 249: #else
250: return (first) ? first->key : String::Body();
251: #endif
1.86 misha 252: }
253:
1.82 misha 254: V first_value() const {
255: return (first) ? first->value : V(0);
256: }
257:
1.97 moko 258: inline Pair* last_pair() const {
259: return (fpairs_count) ? (Pair*)((char *)last - offsetof(Pair, next)) : NULL;
260: }
261:
1.86 misha 262: String::Body last_key() const {
1.97 moko 263: if(Pair* pair = last_pair()) {
1.92 moko 264: #ifdef HASH_CODE_CACHING
1.86 misha 265: return String::Body(pair->key, pair->code);
1.92 moko 266: #else
267: return pair->key;
268: #endif
1.86 misha 269: } else {
270: return String::Body();
271: }
272: }
273:
1.82 misha 274: V last_value() const {
1.97 moko 275: if(Pair* pair = last_pair())
276: return pair->value;
277: return NULL;
1.82 misha 278: }
1.88 moko 279:
280: void order_clear() {
281: HASH_ORDER_CLEAR();
282: }
283:
284: void order_next(Pair* pair) {
285: pair->prev=last;
286: pair->next=0;
287: *last=pair;
288: last=&(pair->next);
289: }
1.92 moko 290: #endif //HASH_ORDER
1.82 misha 291:
1.51 paf 292: /// put a [value] under the [key] if that [key] existed @returns existed or not
1.63 paf 293: bool put_replaced(K key, V value) {
1.59 paf 294: if(!value) {
295: remove(key);
296: return false;
297: }
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: // found a pair with the same key, replacing
303: pair->value=value;
304: return true;
305: }
306:
307: // proper pair not found
308: return false;
1.64 paf 309: }
310:
1.51 paf 311: /// put a [value] under the [key] if that [key] NOT existed @returns existed or not
1.59 paf 312: bool put_dont_replace(K key, V value) {
313: if(!value) {
314: remove(key);
315: return false;
316: }
317: if(is_full())
318: expand();
319:
320: uint code=hash_code(key);
321: uint index=code%allocated;
322: Pair **ref=&refs[index];
323: for(Pair *pair=*ref; pair; pair=pair->link)
324: if(pair->code==code && pair->key==key) {
325: // found a pair with the same key, NOT replacing
326: return true;
327: }
328:
329: // proper pair not found -- create&link_in new pair
330: if(!*ref) // root cell were fused_refs?
331: fused_refs++; // not, we'll use it and record the fact
1.79 misha 332: HASH_NEW_PAIR(code, key, value);
1.59 paf 333: fpairs_count++;
334: return false;
335: }
1.18 paf 336:
1.79 misha 337: /// put all 'src' values if NO with same key existed
1.75 misha 338: void merge_dont_replace(const HASH& src) {
1.79 misha 339: #ifdef HASH_ORDER
340: for(Pair *pair=src.first; pair; pair=pair->next)
341: #else
1.59 paf 342: for(int i=0; i<src.allocated; i++)
343: for(Pair *pair=src.refs[i]; pair; pair=pair->link)
1.79 misha 344: #endif
1.59 paf 345: put_dont_replace(pair->key, pair->value);
1.36 paf 346: }
1.11 paf 347:
1.29 paf 348: /// number of elements in hash
1.59 paf 349: int count() const { return fpairs_count; }
1.25 paf 350:
1.59 paf 351: /// iterate over all pairs
352: template<typename I> void for_each(void callback(K, V, I), I info) const {
1.79 misha 353: HASH_FOR_EACH
1.76 misha 354: callback(pair->key, pair->value, info);
1.59 paf 355: }
1.45 paf 356:
1.59 paf 357: /// iterate over all pairs
358: template<typename I> void for_each_ref(void callback(K, V&, I), I info) const {
1.79 misha 359: HASH_FOR_EACH
1.76 misha 360: callback(pair->key, pair->value, info);
1.59 paf 361: }
1.38 paf 362:
1.59 paf 363: /// iterate over all pairs until condition becomes true, return that element
364: template<typename I> V first_that(bool callback(K, V, I), I info) const {
1.79 misha 365: HASH_FOR_EACH
1.75 misha 366: if(callback(pair->key, pair->value, info))
367: return pair->value;
1.59 paf 368: return V(0);
369: }
1.27 paf 370:
1.29 paf 371: /// remove all elements
1.59 paf 372: void clear() {
373: memset(refs, 0, sizeof(*refs)*allocated);
1.88 moko 374: fpairs_count=fused_refs=0;
375: HASH_ORDER_CLEAR();
1.59 paf 376: }
1.15 paf 377:
1.74 misha 378: protected:
1.1 paf 379:
1.61 paf 380: /// the index of [allocated] in [Hash_allocates]
1.19 paf 381: int allocates_index;
1.1 paf 382:
1.39 paf 383: /// number of allocated pairs
1.19 paf 384: int allocated;
1.1 paf 385:
1.39 paf 386: /// used pairs
1.59 paf 387: int fused_refs;
1.44 parser 388:
389: /// stored pairs total (including those by links)
1.59 paf 390: int fpairs_count;
1.1 paf 391:
1.39 paf 392: /// pair storage
1.59 paf 393: class Pair: public PA_Allocated {
394: public:
1.1 paf 395: uint code;
1.59 paf 396: K key;
397: V value;
1.1 paf 398: Pair *link;
1.75 misha 399: #ifdef HASH_ORDER
400: Pair **prev;
401: Pair *next;
402:
403: Pair(uint acode, K akey, V avalue, Pair *alink, Pair **aprev) : code(acode), key(akey), value(avalue), link(alink),
404: prev(aprev), next(0) { *aprev=this; }
405: #else
406: Pair(uint acode, K akey, V avalue, Pair *alink) : code(acode), key(akey), value(avalue), link(alink) {}
407: #endif
1.2 paf 408: } **refs;
1.1 paf 409:
1.75 misha 410: #ifdef HASH_ORDER
411: Pair *first;
412: Pair **last;
413: #endif
414:
1.83 moko 415: /// filled to threshold (THRESHOLD_PERCENT=75), needs expanding
416: bool is_full() { return fused_refs + allocated/4 >= allocated; }
1.5 paf 417:
1.39 paf 418: /// allocate larger buffer & rehash
1.59 paf 419: void expand() {
420: int old_allocated=allocated;
421: Pair **old_refs=refs;
422:
1.83 moko 423: if (allocates_index<HASH_ALLOCATES_COUNT-1) allocates_index++;
1.59 paf 424: // allocated bigger refs array
1.61 paf 425: allocated=Hash_allocates[allocates_index];
1.87 moko 426: refs=new Pair*[allocated];
1.59 paf 427:
428: // rehash
429: Pair **old_ref=old_refs;
430: for(int old_index=0; old_index<old_allocated; old_index++)
431: for(Pair *pair=*old_ref++; pair; ) {
432: Pair *next=pair->link;
433:
434: uint new_index=pair->code%allocated;
435: Pair **new_ref=&refs[new_index];
436: pair->link=*new_ref;
437: *new_ref=pair;
438:
439: pair=next;
440: }
441:
442: delete[] old_refs;
443: }
1.4 paf 444:
445: private: //disabled
446:
1.75 misha 447: HASH& operator = (const HASH&) { return *this; }
1.1 paf 448: };
1.59 paf 449:
1.74 misha 450: /**
1.75 misha 451: Simple String::body hash.
452: Allows hash code caching
1.74 misha 453: */
454:
455: #ifdef HASH_CODE_CACHING
456:
1.75 misha 457: template<typename V> class HASH_STRING: public HASH<const CORD,V> {
1.74 misha 458: public:
459:
1.75 misha 460: typedef typename HASH<const CORD,V>::Pair Pair;
1.74 misha 461: typedef const String::Body &K;
462:
463: typedef K key_type;
464:
465: /// put a [value] under the [key] @returns existed or not
466: bool put(K str, V value) {
467: if(!value) {
468: remove(str);
469: return false;
470: }
471: if(this->is_full())
472: this->expand();
473:
474: CORD key=str.get_cord();
475:
476: uint code=str.get_hash_code();
477: uint index=code%this->allocated;
478: Pair **ref=&this->refs[index];
479: for(Pair *pair=*ref; pair; pair=pair->link)
480: if(pair->code==code && CORD_cmp(pair->key,key)==0) {
481: // found a pair with the same key
482: pair->value=value;
483: return true;
484: }
485:
486: // proper pair not found -- create&link_in new pair
487: if(!*ref) // root cell were fused_refs?
488: this->fused_refs++; // not, we'll use it and record the fact
1.79 misha 489: HASH_NEW_PAIR(code, key, value);
1.74 misha 490: this->fpairs_count++;
491: return false;
492: }
493:
494: /// remove the [key] @returns existed or not
495: bool remove(K str) {
496: CORD key=str.get_cord();
497: uint code=str.get_hash_code();
498: uint index=code%this->allocated;
1.75 misha 499: for(Pair **ref=&this->refs[index]; *ref; ref=&(*ref)->link){
500: Pair *pair=*ref;
501: if(pair->code==code && CORD_cmp(pair->key,key)==0) {
1.74 misha 502: // found a pair with the same key
1.75 misha 503: Pair *next=pair->link;
504: #ifdef HASH_ORDER
505: *(pair->prev)=pair->next;
506: if(pair->next)
507: pair->next->prev=pair->prev;
508: else
509: this->last=pair->prev;
510: #endif
1.74 misha 511: *ref=next;
512: --this->fpairs_count;
513: return true;
514: }
1.75 misha 515: }
1.74 misha 516:
517: return false;
518: }
519:
520: /// return true if key exists
521: bool contains(K str){
522: CORD key=str.get_cord();
523: uint code=str.get_hash_code();
524: uint index=code%this->allocated;
525: for(Pair *pair=this->refs[index]; pair; pair=pair->link){
526: if(pair->code==code && CORD_cmp(pair->key,key)==0)
527: return true;
528: }
529:
530: return false;
531: }
532:
533: /// get associated [value] by the [key]
534: V get(K str) const {
535: CORD key=str.get_cord();
536: uint code=str.get_hash_code();
537: uint index=code%this->allocated;
538: for(Pair *pair=this->refs[index]; pair; pair=pair->link)
539: if(pair->code==code && CORD_cmp(pair->key,key)==0)
540: return pair->value;
541:
542: return V(0);
543: }
544:
1.93 moko 545: /// get associated [value] by the [key], optimized
546: V get(const char *key) const {
547: uint code=0;
548: if(key && *key){
549: generic_hash_code(code, key);
550: } else {
551: key=0;
552: }
553: uint index=code%this->allocated;
554: for(Pair *pair=this->refs[index]; pair; pair=pair->link)
555: if(pair->code==code && CORD_cmp(pair->key,(CORD)key)==0)
556: return pair->value;
557:
558: return V(0);
559: }
560:
1.74 misha 561: /// put a [value] under the [key] if that [key] existed @returns existed or not
562: bool put_replaced(K str, V value) {
563: if(!value) {
564: remove(str);
565: return false;
566: }
567:
568: CORD key=str.get_cord();
569: uint code=str.get_hash_code();
570: uint index=code%this->allocated;
571: for(Pair *pair=this->refs[index]; pair; pair=pair->link)
572: if(pair->code==code && CORD_cmp(pair->key,key)==0) {
573: // found a pair with the same key, replacing
574: pair->value=value;
575: return true;
576: }
577:
578: // proper pair not found
579: return false;
580: }
581:
582: /// put a [value] under the [key] if that [key] NOT existed @returns existed or not
583: bool put_dont_replace(K str, V value) {
584: if(!value) {
585: remove(str);
586: return false;
587: }
588: if(this->is_full())
589: this->expand();
590:
591: CORD key=str.get_cord();
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, NOT replacing
598: return true;
599: }
600:
601: // proper pair not found -- create&link_in new pair
602: if(!*ref) // root cell were fused_refs?
603: this->fused_refs++; // not, we'll use it and record the fact
1.79 misha 604: HASH_NEW_PAIR(code, key, value);
1.74 misha 605: this->fpairs_count++;
606: return false;
607: }
608:
1.79 misha 609: /// put all 'src' values if NO with same key existed
610: void merge_dont_replace(const HASH_STRING& src) {
1.76 misha 611: #ifdef HASH_ORDER
1.79 misha 612: for(Pair *pair=src.first; pair; pair=pair->next)
1.76 misha 613: #else
1.79 misha 614: for(int i=0; i<src.allocated; i++)
615: for(Pair *pair=src.refs[i]; pair; pair=pair->link)
1.76 misha 616: #endif
1.79 misha 617: put_dont_replace(String::Body(pair->key, pair->code), pair->value);
618: }
619:
620: /// iterate over all pairs
621: template<typename I> void for_each(void callback(K, V, I), I info) const {
622: HASH_FOR_EACH
623: callback(String::Body(pair->key, pair->code), pair->value, info);
1.74 misha 624: }
625:
626: /// iterate over all pairs
627: template<typename I> void for_each_ref(void callback(K, V&, I), I info) const {
1.79 misha 628: HASH_FOR_EACH
629: callback(String::Body(pair->key, pair->code), pair->value, info);
1.74 misha 630: }
631:
632: /// iterate over all pairs until condition becomes true, return that element
633: template<typename I> V first_that(bool callback(K, V, I), I info) const {
1.79 misha 634: HASH_FOR_EACH
1.75 misha 635: if(callback(String::Body(pair->key, pair->code), pair->value, info))
636: return pair->value;
1.74 misha 637: return V(0);
638: }
1.80 misha 639:
1.92 moko 640: #else //HASH_CODE_CACHING
641:
642: template<typename V> class HASH_STRING: public HASH<const String::Body,V>{
643: public:
644: typedef typename HASH<const String::Body,V>::Pair Pair;
645:
646: #endif //HASH_CODE_CACHING
647:
1.80 misha 648: /// simple hash iterator
649: class Iterator {
650: const HASH_STRING<V>& fhash;
651: Pair *fcurrent;
1.90 moko 652: #ifndef HASH_ORDER
1.89 moko 653: int i;
1.90 moko 654: #endif
1.80 misha 655: public:
1.92 moko 656: #ifdef HASH_ORDER
1.80 misha 657: Iterator(const HASH_STRING<V>& ahash): fhash(ahash) {
658: fcurrent=fhash.first;
1.92 moko 659: }
660:
661: void next() {
662: fcurrent=fcurrent->next;
663: }
1.89 moko 664: #else
1.92 moko 665: Iterator(const HASH_STRING<V>& ahash): fhash(ahash) {
1.89 moko 666: fcurrent=0;
667: for(i=0; i<fhash.allocated; i++)
668: if (fcurrent=fhash.refs[i])
669: break;
1.80 misha 670: }
671:
672: void next() {
1.89 moko 673: if(fcurrent=fcurrent->link)
674: return;
675: for(i++; i<fhash.allocated; i++)
676: if (fcurrent=fhash.refs[i])
677: break;
1.92 moko 678: }
1.89 moko 679: #endif
1.92 moko 680:
681: operator bool () {
1.97 moko 682: return fcurrent != NULL;
1.80 misha 683: }
684:
685: String::Body key(){
1.92 moko 686: #ifdef HASH_CODE_CACHING
1.80 misha 687: return String::Body(fcurrent->key, fcurrent->code);
1.92 moko 688: #else
689: return fcurrent->key;
690: #endif
1.80 misha 691: }
692:
693: V value(){
694: return fcurrent->value;
695: }
1.88 moko 696:
697: Pair *pair(){
698: return fcurrent;
699: }
1.80 misha 700: };
1.92 moko 701:
1.97 moko 702: #ifdef HASH_ORDER
703: /// simple reverse hash iterator
704: class ReverseIterator {
705: const HASH_STRING<V>& fhash;
706: Pair *fcurrent;
707: public:
708: ReverseIterator(const HASH_STRING<V>& ahash): fhash(ahash) {
709: fcurrent=fhash.last_pair();
710: }
711:
712: void prev() {
713: fcurrent=(fcurrent->prev == &fhash.first) ? NULL : (Pair*)((char *)fcurrent->prev - offsetof(Pair, next));
714: }
715:
716: operator bool () {
717: return fcurrent != NULL;
718: }
719:
720: String::Body key(){
1.98 ! moko 721: #ifdef HASH_CODE_CACHING
1.97 moko 722: return String::Body(fcurrent->key, fcurrent->code);
1.98 ! moko 723: #else
! 724: return fcurrent->key;
! 725: #endif
1.97 moko 726: }
727:
728: V value(){
729: return fcurrent->value;
730: }
731:
732: Pair *pair(){
733: return fcurrent;
734: }
735: };
736: #endif
737:
1.74 misha 738: };
739:
1.75 misha 740: #ifndef HASH_ORDER
1.74 misha 741: /// Auto-object used to temporarily substituting/removing string hash values
1.85 moko 742: template <typename H, typename V>
1.55 paf 743: class Temp_hash_value {
1.85 moko 744: H *fhash;
745: String::Body fname;
1.59 paf 746: V saved_value;
1.55 paf 747: public:
1.85 moko 748: Temp_hash_value(H *ahash, String::Body aname, V avalue) : fhash(ahash), fname(aname) {
749: if(fhash){
750: saved_value=fhash->get(aname);
751: fhash->put(aname, avalue);
752: }
1.55 paf 753: }
1.85 moko 754: ~Temp_hash_value() {
755: if(fhash)
756: fhash->put(fname, saved_value);
1.55 paf 757: }
758: };
1.75 misha 759: #endif
1.1 paf 760:
1.75 misha 761: #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