![[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|
Return to pa_hash.h CVS log | Up to [parser3project] / parser3 / src / include |
1.28 paf 1: /** @file
1.29 paf 2: Parser: hash class decl.
3:
1.66 paf 4: Copyright (c) 2001-2005 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.73 ! misha 20: static const char * const IDENT_HASH_H="$Date: 2009-04-17 23:21:51 $";
1.1 paf 21:
1.59 paf 22: #include "pa_memory.h"
1.1 paf 23: #include "pa_types.h"
1.59 paf 24:
25: const int HASH_ALLOCATES_COUNT=29;
1.1 paf 26:
1.61 paf 27: /** Zend comment: Generated on an Octa-ALPHA 300MHz CPU & 2.5GB RAM monster
28:
29: paf: HPUX ld could not handle static member: unsatisfied symbols
30: */
31: static uint Hash_allocates[HASH_ALLOCATES_COUNT]={
32: 5, 11, 19, 53, 107, 223, 463, 983, 1979, 3907, 7963,
33: 16229, 32531, 65407, 130987, 262237, 524521, 1048793,
34: 2097397, 4194103, 8388857, 16777447, 33554201, 67108961,
35: 134217487, 268435697, 536870683, 1073741621, 2147483399};
36:
1.68 misha 37: /// useful generic hash function
38: inline void generic_hash_code(uint& result, char c) {
39: result=(result<<4)+c;
40: if(uint g=(result&0xF0000000)) {
41: result=result^(g>>24);
42: result=result^g;
43: }
44: }
45: /// useful generic hash function
46: inline void generic_hash_code(uint& result, const char* s) {
47: while(char c=*s++) {
48: result=(result<<4)+c;
49: if(uint g=(result&0xF0000000)) {
50: result=result^(g>>24);
51: result=result^g;
52: }
53: }
54: }
55:
56: /// useful generic hash function
57: inline void generic_hash_code(uint& result, const char* buf, size_t size) {
58: const char* end=buf+size;
59: while(buf<end) {
60: result=(result<<4)+*buf++;
61: if(uint g=(result&0xF0000000)) {
62: result=result^(g>>24);
63: result=result^g;
64: }
65: }
66: }
67:
68: /// simple hash code of int. used by EXIF mapping
69: inline uint hash_code(int self) {
70: uint result=0;
71: generic_hash_code(result, (const char*)&self, sizeof(self));
72: return result;
73: }
74:
1.29 paf 75: /**
1.59 paf 76: Simple hash.
1.29 paf 77:
1.59 paf 78: Automatically rehashed when almost is_full.
1.51 paf 79: Contains no 0 values.
80: get returning 0 means there were no such.
81: "put value 0" means "remove"
1.29 paf 82: */
1.59 paf 83: template<typename K, typename V> class Hash: public PA_Object {
1.1 paf 84: public:
85:
1.59 paf 86: typedef K key_type;
87: typedef V value_type;
1.3 paf 88:
1.59 paf 89: Hash() {
1.61 paf 90: allocated=Hash_allocates[allocates_index=0];
1.59 paf 91: threshold=allocated*THRESHOLD_PERCENT/100;
92: fpairs_count=fused_refs=0;
93: refs=new(UseGC) Pair*[allocated];
94: }
1.25 paf 95:
1.59 paf 96: Hash(const Hash& source) {
97: allocates_index=source.allocates_index;
98: allocated=source.allocated;
99: threshold=source.threshold;
100: fused_refs=source.fused_refs;
101: fpairs_count=source.fpairs_count;
102: refs=new(UseGC) Pair*[allocated];
103:
104: // clone & rehash
105: Pair **old_ref=source.refs;
106: for(int index=0; index<allocated; index++)
107: for(Pair *pair=*old_ref++; pair; ) {
108: Pair *next=pair->link;
1.45 paf 109:
1.59 paf 110: Pair **new_ref=&refs[index];
111: *new_ref=new Pair(pair->code, pair->key, pair->value, *new_ref);
1.38 paf 112:
1.59 paf 113: pair=next;
114: }
1.43 parser 115: }
116:
1.73 ! misha 117: #ifdef USE_DESTRUCTORS
1.71 misha 118: ~Hash() {
1.72 misha 119: Pair **ref=refs;
120: for(int index=0; index<allocated; index++)
121: for(Pair *pair=*ref++; pair;){
122: Pair *next=pair->link;
123: delete pair;
124: pair=next;
125: }
1.71 misha 126: delete[] refs;
127: }
1.73 ! misha 128: #endif
1.71 misha 129:
1.59 paf 130: /// put a [value] under the [key] @returns existed or not
131: bool put(K key, V value) {
132: if(!value) {
133: remove(key);
134: return false;
135: }
136: if(is_full())
137: expand();
138:
139: uint code=hash_code(key);
140: uint index=code%allocated;
141: Pair **ref=&refs[index];
142: for(Pair *pair=*ref; pair; pair=pair->link)
143: if(pair->code==code && pair->key==key) {
144: // found a pair with the same key
145: pair->value=value;
146: return true;
147: }
148:
149: // proper pair not found -- create&link_in new pair
150: if(!*ref) // root cell were fused_refs?
151: fused_refs++; // not, we'll use it and record the fact
152: *ref=new Pair(code, key, value, *ref);
153: fpairs_count++;
154: return false;
1.24 paf 155: }
1.10 paf 156:
1.63 paf 157: /// put a [value] under the [key] @returns existed or not
1.65 paf 158: template<typename R, typename F, typename I> R replace_maybe_append(K key, V value, F prevent, I info) {
159: if(!value) {
160: // they can come here from somewhere (true with maybe_replace_maybe_append, keeping parallel)
161: remove(key);
162: // this has nothing to do with properties, doing no special property handling here
163: return 0;
164: }
1.64 paf 165:
1.63 paf 166: if(is_full())
167: expand();
168:
169: uint code=hash_code(key);
170: uint index=code%allocated;
171: Pair **ref=&refs[index];
172: for(Pair *pair=*ref; pair; pair=pair->link)
173: if(pair->code==code && pair->key==key) {
174: // found a pair with the same key
1.65 paf 175: pair->value=value;
176: return reinterpret_cast<R>(1);
177: }
178:
179: // proper pair not found
180: // prevent-function intercepted append?
181: if(R result=prevent(value, info))
182: return result;
183:
184: //create&link_in new pair
185: if(!*ref) // root cell were fused_refs?
186: fused_refs++; // not, we'll use it and record the fact
187: *ref=new Pair(code, key, value, *ref);
188: fpairs_count++;
189: return 0;
190: }
1.63 paf 191:
1.65 paf 192: /// put a [value] under the [key] @returns existed or not
193: template<typename R, typename F1, typename F2, typename I>
194: R maybe_replace_maybe_append(K key, V value, F1 prevent_replace, F2 prevent_append, I info)
195: {
196: if(!value) {
197: // they can come here from Temp_value_element::dctor to restore some empty value
198: remove(key);
199: // this has nothing to do with properties, doing no special property handling here
200: return 0;
201: }
202:
203: if(is_full())
204: expand();
205:
206: uint code=hash_code(key);
207: uint index=code%allocated;
208: Pair **ref=&refs[index];
209: for(Pair *pair=*ref; pair; pair=pair->link)
210: if(pair->code==code && pair->key==key) {
211: // found a pair with the same key
212:
213: // prevent-function intercepted replace?
214: if(R result=prevent_replace(pair->value, info))
1.63 paf 215: return result;
216:
217: pair->value=value;
218: return reinterpret_cast<R>(1);
219: }
220:
1.65 paf 221: // proper pair not found
222: // prevent-function intercepted append?
223: if(R result=prevent_append(value, info))
224: return result;
225:
226: //create&link_in new pair
1.63 paf 227: if(!*ref) // root cell were fused_refs?
228: fused_refs++; // not, we'll use it and record the fact
229: *ref=new Pair(code, key, value, *ref);
230: fpairs_count++;
231: return 0;
232: }
233:
1.65 paf 234: /// put a [value] under the [key] @returns existed or not
235: template<typename R, typename F1, typename I>
236: R maybe_replace_never_append(K key, V value, F1 prevent_replace, I info)
237: {
238: if(!value) {
239: // they can come here from somewhere (true with maybe_replace_maybe_append, keeping parallel)
240: remove(key);
241: // this has nothing to do with properties, doing no special property handling here
242: return 0;
243: }
244:
245: if(is_full())
246: expand();
247:
248: uint code=hash_code(key);
249: uint index=code%allocated;
250: Pair **ref=&refs[index];
251: for(Pair *pair=*ref; pair; pair=pair->link)
252: if(pair->code==code && pair->key==key) {
253: // found a pair with the same key
254:
255: // prevent-function intercepted replace?
256: if(R result=prevent_replace(pair->value, info))
257: return result;
258:
259: pair->value=value;
260: return reinterpret_cast<R>(1);
261: }
262:
263: return 0;
264: }
265:
1.59 paf 266: /// remove the [key] @returns existed or not
267: bool remove(K key) {
268: uint code=hash_code(key);
269: uint index=code%allocated;
270: for(Pair **ref=&refs[index]; *ref; ref=&(*ref)->link)
271: if((*ref)->code==code && (*ref)->key==key) {
272: // found a pair with the same key
273: Pair *next=(*ref)->link;
274: delete *ref;
275: *ref=next;
276: --fpairs_count;
277: return true;
278: }
1.8 paf 279:
1.59 paf 280: return false;
281: }
1.48 paf 282:
1.70 misha 283: /// return true if key exists
1.69 misha 284: bool contains(K key){
1.67 misha 285: uint code=hash_code(key);
286: uint index=code%allocated;
1.70 misha 287: for(Pair *pair=refs[index]; pair; pair=pair->link){
288: if(pair->code==code && pair->key==key)
1.67 misha 289: return true;
290: }
291:
292: return false;
293: }
294:
1.59 paf 295: /// get associated [value] by the [key]
296: V get(K key) const {
297: uint code=hash_code(key);
298: uint index=code%allocated;
299: for(Pair *pair=refs[index]; pair; pair=pair->link)
300: if(pair->code==code && pair->key==key)
301: return pair->value;
302:
303: return V(0);
1.33 paf 304: }
1.70 misha 305:
306: /// get associated [value] by the [key] + [code] (faster)
307: V get_by_hash_code(uint code, K key) const {
308: uint index=code%allocated;
309: for(Pair *pair=refs[index]; pair; pair=pair->link)
310: if(pair->code==code && pair->key==key)
311: return pair->value;
312:
313: return V(0);
314: }
1.65 paf 315:
1.51 paf 316: /// put a [value] under the [key] if that [key] existed @returns existed or not
1.63 paf 317: bool put_replaced(K key, V value) {
1.59 paf 318: if(!value) {
319: remove(key);
320: return false;
321: }
322: uint code=hash_code(key);
323: uint index=code%allocated;
324: for(Pair *pair=refs[index]; pair; pair=pair->link)
325: if(pair->code==code && pair->key==key) {
326: // found a pair with the same key, replacing
327: pair->value=value;
328: return true;
329: }
330:
331: // proper pair not found
332: return false;
1.64 paf 333: }
334:
335: /// put a [value] under the [key] if that [key] existed @returns existed or not
336: template<typename R, typename F> R maybe_put_replaced(K key, V value, F prevent) {
1.65 paf 337: if(!value) {
338: // they can come here from Temp_value_element::dctor to restore some empty value
339: remove(key);
340: // this has nothing to do with properties, doing no special property handling here
341: return 0;
342: }
1.64 paf 343:
344: uint code=hash_code(key);
345: uint index=code%allocated;
346: for(Pair *pair=refs[index]; pair; pair=pair->link)
347: if(pair->code==code && pair->key==key) {
348: // found a pair with the same key, replacing
349: // prevent-function intercepted put?
350: if(R result=prevent(pair->value))
351: return result;
352:
353: pair->value=value;
354: return reinterpret_cast<R>(1);
355: }
356:
357: // proper pair not found
358: return 0;
1.59 paf 359: }
1.18 paf 360:
1.51 paf 361: /// put a [value] under the [key] if that [key] NOT existed @returns existed or not
1.59 paf 362: bool put_dont_replace(K key, V value) {
363: if(!value) {
364: remove(key);
365: return false;
366: }
367: if(is_full())
368: expand();
369:
370: uint code=hash_code(key);
371: uint index=code%allocated;
372: Pair **ref=&refs[index];
373: for(Pair *pair=*ref; pair; pair=pair->link)
374: if(pair->code==code && pair->key==key) {
375: // found a pair with the same key, NOT replacing
376: return true;
377: }
378:
379: // proper pair not found -- create&link_in new pair
380: if(!*ref) // root cell were fused_refs?
381: fused_refs++; // not, we'll use it and record the fact
382: *ref=new Pair(code, key, value, *ref);
383: fpairs_count++;
384: return false;
385: }
1.18 paf 386:
1.59 paf 387: /** put all 'src' values if NO with same key existed
388: @todo optimize this.allocated==src.allocated case
389: */
390: void merge_dont_replace(const Hash& src) {
391: for(int i=0; i<src.allocated; i++)
392: for(Pair *pair=src.refs[i]; pair; pair=pair->link)
393: put_dont_replace(pair->key, pair->value);
1.36 paf 394: }
1.11 paf 395:
1.29 paf 396: /// number of elements in hash
1.59 paf 397: int count() const { return fpairs_count; }
1.25 paf 398:
1.59 paf 399: /// iterate over all pairs
400: template<typename I> void for_each(void callback(K, V, I), I info) const {
401: Pair **ref=refs;
402: for(int index=0; index<allocated; index++)
403: for(Pair *pair=*ref++; pair; pair=pair->link)
404: callback(pair->key, pair->value, info);
405: }
1.45 paf 406:
1.59 paf 407: /// iterate over all pairs
408: template<typename I> void for_each_ref(void callback(K, V&, I), I info) const {
409: Pair **ref=refs;
410: for(int index=0; index<allocated; index++)
411: for(Pair *pair=*ref++; pair; pair=pair->link)
412: callback(pair->key, pair->value, info);
413: }
1.38 paf 414:
1.59 paf 415: /// iterate over all pairs until condition becomes true, return that element
416: template<typename I> V first_that(bool callback(K, V, I), I info) const {
417: Pair **ref=refs;
418: for(int index=0; index<allocated; index++)
419: for(Pair *pair=*ref++; pair; pair=pair->link)
420: if(callback(pair->key, pair->value, info))
421: return pair->value;
422:
423: return V(0);
424: }
1.27 paf 425:
1.29 paf 426: /// remove all elements
1.59 paf 427: void clear() {
428: memset(refs, 0, sizeof(*refs)*allocated);
429: fpairs_count=fused_refs=0;
430: }
1.15 paf 431:
1.1 paf 432: private:
433:
1.39 paf 434: /// expand when these %% of allocated exausted
1.1 paf 435: enum {
436: THRESHOLD_PERCENT=75
437: };
1.9 paf 438:
1.61 paf 439: /// the index of [allocated] in [Hash_allocates]
1.19 paf 440: int allocates_index;
1.1 paf 441:
1.39 paf 442: /// number of allocated pairs
1.19 paf 443: int allocated;
1.1 paf 444:
1.59 paf 445: /// helper: expanding when fused_refs == threshold
1.1 paf 446: int threshold;
447:
1.39 paf 448: /// used pairs
1.59 paf 449: int fused_refs;
1.44 parser 450:
451: /// stored pairs total (including those by links)
1.59 paf 452: int fpairs_count;
1.1 paf 453:
1.39 paf 454: /// pair storage
1.59 paf 455: class Pair: public PA_Allocated {
456: public:
1.1 paf 457: uint code;
1.59 paf 458: K key;
459: V value;
1.1 paf 460: Pair *link;
1.2 paf 461:
1.59 paf 462: Pair(uint acode, K akey, V avalue, Pair *alink) :
1.1 paf 463: code(acode),
464: key(akey),
465: value(avalue),
1.2 paf 466: link(alink) {}
467: } **refs;
1.1 paf 468:
1.39 paf 469: /// filled to threshold: needs expanding
1.59 paf 470: bool is_full() { return fused_refs==threshold; }
1.5 paf 471:
1.39 paf 472: /// allocate larger buffer & rehash
1.59 paf 473: void expand() {
474: int old_allocated=allocated;
475: Pair **old_refs=refs;
476:
477: allocates_index=allocates_index+1<HASH_ALLOCATES_COUNT?allocates_index+1:HASH_ALLOCATES_COUNT-1;
478: // allocated bigger refs array
1.61 paf 479: allocated=Hash_allocates[allocates_index];
1.59 paf 480: threshold=allocated*THRESHOLD_PERCENT/100;
481: refs=new(UseGC) Pair*[allocated];
482:
483: // rehash
484: Pair **old_ref=old_refs;
485: for(int old_index=0; old_index<old_allocated; old_index++)
486: for(Pair *pair=*old_ref++; pair; ) {
487: Pair *next=pair->link;
488:
489: uint new_index=pair->code%allocated;
490: Pair **new_ref=&refs[new_index];
491: pair->link=*new_ref;
492: *new_ref=pair;
493:
494: pair=next;
495: }
496:
497: delete[] old_refs;
498: }
1.4 paf 499:
500: private: //disabled
501:
1.12 paf 502: Hash& operator = (const Hash&) { return *this; }
1.1 paf 503: };
1.59 paf 504:
505: /// Auto-object used to temporarily substituting/removing hash values
506: template <typename K, typename V>
1.55 paf 507: class Temp_hash_value {
1.59 paf 508: Hash<K, V>& fhash;
509: K fname;
510: V saved_value;
1.55 paf 511: public:
1.59 paf 512: Temp_hash_value(Hash<K, V>& ahash, K aname, V avalue) :
1.55 paf 513: fhash(ahash),
514: fname(aname),
515: saved_value(ahash.get(aname)) {
516: fhash.put(aname, avalue);
517: }
518: ~Temp_hash_value() {
519: fhash.put(fname, saved_value);
520: }
521: };
1.1 paf 522:
523: #endif