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