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