![[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.72 ! misha 20: static const char * const IDENT_HASH_H="$Date: 2009-04-17 13:13:09 $";
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.71 misha 117: ~Hash() {
1.72 ! misha 118: Pair **ref=refs;
! 119: for(int index=0; index<allocated; index++)
! 120: for(Pair *pair=*ref++; pair;){
! 121: Pair *next=pair->link;
! 122: delete pair;
! 123: pair=next;
! 124: }
1.71 misha 125: delete[] refs;
126: }
127:
1.59 paf 128: /// put a [value] under the [key] @returns existed or not
129: bool put(K key, V value) {
130: if(!value) {
131: remove(key);
132: return false;
133: }
134: if(is_full())
135: expand();
136:
137: uint code=hash_code(key);
138: uint index=code%allocated;
139: Pair **ref=&refs[index];
140: for(Pair *pair=*ref; pair; pair=pair->link)
141: if(pair->code==code && pair->key==key) {
142: // found a pair with the same key
143: pair->value=value;
144: return true;
145: }
146:
147: // proper pair not found -- create&link_in new pair
148: if(!*ref) // root cell were fused_refs?
149: fused_refs++; // not, we'll use it and record the fact
150: *ref=new Pair(code, key, value, *ref);
151: fpairs_count++;
152: return false;
1.24 paf 153: }
1.10 paf 154:
1.63 paf 155: /// put a [value] under the [key] @returns existed or not
1.65 paf 156: template<typename R, typename F, typename I> R replace_maybe_append(K key, V value, F prevent, I info) {
157: if(!value) {
158: // they can come here from somewhere (true with maybe_replace_maybe_append, keeping parallel)
159: remove(key);
160: // this has nothing to do with properties, doing no special property handling here
161: return 0;
162: }
1.64 paf 163:
1.63 paf 164: if(is_full())
165: expand();
166:
167: uint code=hash_code(key);
168: uint index=code%allocated;
169: Pair **ref=&refs[index];
170: for(Pair *pair=*ref; pair; pair=pair->link)
171: if(pair->code==code && pair->key==key) {
172: // found a pair with the same key
1.65 paf 173: pair->value=value;
174: return reinterpret_cast<R>(1);
175: }
176:
177: // proper pair not found
178: // prevent-function intercepted append?
179: if(R result=prevent(value, info))
180: return result;
181:
182: //create&link_in new pair
183: if(!*ref) // root cell were fused_refs?
184: fused_refs++; // not, we'll use it and record the fact
185: *ref=new Pair(code, key, value, *ref);
186: fpairs_count++;
187: return 0;
188: }
1.63 paf 189:
1.65 paf 190: /// put a [value] under the [key] @returns existed or not
191: template<typename R, typename F1, typename F2, typename I>
192: R maybe_replace_maybe_append(K key, V value, F1 prevent_replace, F2 prevent_append, I info)
193: {
194: if(!value) {
195: // they can come here from Temp_value_element::dctor to restore some empty value
196: remove(key);
197: // this has nothing to do with properties, doing no special property handling here
198: return 0;
199: }
200:
201: if(is_full())
202: expand();
203:
204: uint code=hash_code(key);
205: uint index=code%allocated;
206: Pair **ref=&refs[index];
207: for(Pair *pair=*ref; pair; pair=pair->link)
208: if(pair->code==code && pair->key==key) {
209: // found a pair with the same key
210:
211: // prevent-function intercepted replace?
212: if(R result=prevent_replace(pair->value, info))
1.63 paf 213: return result;
214:
215: pair->value=value;
216: return reinterpret_cast<R>(1);
217: }
218:
1.65 paf 219: // proper pair not found
220: // prevent-function intercepted append?
221: if(R result=prevent_append(value, info))
222: return result;
223:
224: //create&link_in new pair
1.63 paf 225: if(!*ref) // root cell were fused_refs?
226: fused_refs++; // not, we'll use it and record the fact
227: *ref=new Pair(code, key, value, *ref);
228: fpairs_count++;
229: return 0;
230: }
231:
1.65 paf 232: /// put a [value] under the [key] @returns existed or not
233: template<typename R, typename F1, typename I>
234: R maybe_replace_never_append(K key, V value, F1 prevent_replace, I info)
235: {
236: if(!value) {
237: // they can come here from somewhere (true with maybe_replace_maybe_append, keeping parallel)
238: remove(key);
239: // this has nothing to do with properties, doing no special property handling here
240: return 0;
241: }
242:
243: if(is_full())
244: expand();
245:
246: uint code=hash_code(key);
247: uint index=code%allocated;
248: Pair **ref=&refs[index];
249: for(Pair *pair=*ref; pair; pair=pair->link)
250: if(pair->code==code && pair->key==key) {
251: // found a pair with the same key
252:
253: // prevent-function intercepted replace?
254: if(R result=prevent_replace(pair->value, info))
255: return result;
256:
257: pair->value=value;
258: return reinterpret_cast<R>(1);
259: }
260:
261: return 0;
262: }
263:
1.59 paf 264: /// remove the [key] @returns existed or not
265: bool remove(K key) {
266: uint code=hash_code(key);
267: uint index=code%allocated;
268: for(Pair **ref=&refs[index]; *ref; ref=&(*ref)->link)
269: if((*ref)->code==code && (*ref)->key==key) {
270: // found a pair with the same key
271: Pair *next=(*ref)->link;
272: delete *ref;
273: *ref=next;
274: --fpairs_count;
275: return true;
276: }
1.8 paf 277:
1.59 paf 278: return false;
279: }
1.48 paf 280:
1.70 misha 281: /// return true if key exists
1.69 misha 282: bool contains(K key){
1.67 misha 283: uint code=hash_code(key);
284: uint index=code%allocated;
1.70 misha 285: for(Pair *pair=refs[index]; pair; pair=pair->link){
286: if(pair->code==code && pair->key==key)
1.67 misha 287: return true;
288: }
289:
290: return false;
291: }
292:
1.59 paf 293: /// get associated [value] by the [key]
294: V get(K key) const {
295: uint code=hash_code(key);
296: uint index=code%allocated;
297: for(Pair *pair=refs[index]; pair; pair=pair->link)
298: if(pair->code==code && pair->key==key)
299: return pair->value;
300:
301: return V(0);
1.33 paf 302: }
1.70 misha 303:
304: /// get associated [value] by the [key] + [code] (faster)
305: V get_by_hash_code(uint code, K key) const {
306: uint index=code%allocated;
307: for(Pair *pair=refs[index]; pair; pair=pair->link)
308: if(pair->code==code && pair->key==key)
309: return pair->value;
310:
311: return V(0);
312: }
1.65 paf 313:
1.51 paf 314: /// put a [value] under the [key] if that [key] existed @returns existed or not
1.63 paf 315: bool put_replaced(K key, V value) {
1.59 paf 316: if(!value) {
317: remove(key);
318: return false;
319: }
320: uint code=hash_code(key);
321: uint index=code%allocated;
322: for(Pair *pair=refs[index]; pair; pair=pair->link)
323: if(pair->code==code && pair->key==key) {
324: // found a pair with the same key, replacing
325: pair->value=value;
326: return true;
327: }
328:
329: // proper pair not found
330: return false;
1.64 paf 331: }
332:
333: /// put a [value] under the [key] if that [key] existed @returns existed or not
334: template<typename R, typename F> R maybe_put_replaced(K key, V value, F prevent) {
1.65 paf 335: if(!value) {
336: // they can come here from Temp_value_element::dctor to restore some empty value
337: remove(key);
338: // this has nothing to do with properties, doing no special property handling here
339: return 0;
340: }
1.64 paf 341:
342: uint code=hash_code(key);
343: uint index=code%allocated;
344: for(Pair *pair=refs[index]; pair; pair=pair->link)
345: if(pair->code==code && pair->key==key) {
346: // found a pair with the same key, replacing
347: // prevent-function intercepted put?
348: if(R result=prevent(pair->value))
349: return result;
350:
351: pair->value=value;
352: return reinterpret_cast<R>(1);
353: }
354:
355: // proper pair not found
356: return 0;
1.59 paf 357: }
1.18 paf 358:
1.51 paf 359: /// put a [value] under the [key] if that [key] NOT existed @returns existed or not
1.59 paf 360: bool put_dont_replace(K key, V value) {
361: if(!value) {
362: remove(key);
363: return false;
364: }
365: if(is_full())
366: expand();
367:
368: uint code=hash_code(key);
369: uint index=code%allocated;
370: Pair **ref=&refs[index];
371: for(Pair *pair=*ref; pair; pair=pair->link)
372: if(pair->code==code && pair->key==key) {
373: // found a pair with the same key, NOT replacing
374: return true;
375: }
376:
377: // proper pair not found -- create&link_in new pair
378: if(!*ref) // root cell were fused_refs?
379: fused_refs++; // not, we'll use it and record the fact
380: *ref=new Pair(code, key, value, *ref);
381: fpairs_count++;
382: return false;
383: }
1.18 paf 384:
1.59 paf 385: /** put all 'src' values if NO with same key existed
386: @todo optimize this.allocated==src.allocated case
387: */
388: void merge_dont_replace(const Hash& src) {
389: for(int i=0; i<src.allocated; i++)
390: for(Pair *pair=src.refs[i]; pair; pair=pair->link)
391: put_dont_replace(pair->key, pair->value);
1.36 paf 392: }
1.11 paf 393:
1.29 paf 394: /// number of elements in hash
1.59 paf 395: int count() const { return fpairs_count; }
1.25 paf 396:
1.59 paf 397: /// iterate over all pairs
398: template<typename I> void for_each(void callback(K, V, I), I info) const {
399: Pair **ref=refs;
400: for(int index=0; index<allocated; index++)
401: for(Pair *pair=*ref++; pair; pair=pair->link)
402: callback(pair->key, pair->value, info);
403: }
1.45 paf 404:
1.59 paf 405: /// iterate over all pairs
406: template<typename I> void for_each_ref(void callback(K, V&, I), I info) const {
407: Pair **ref=refs;
408: for(int index=0; index<allocated; index++)
409: for(Pair *pair=*ref++; pair; pair=pair->link)
410: callback(pair->key, pair->value, info);
411: }
1.38 paf 412:
1.59 paf 413: /// iterate over all pairs until condition becomes true, return that element
414: template<typename I> V first_that(bool callback(K, V, I), I info) const {
415: Pair **ref=refs;
416: for(int index=0; index<allocated; index++)
417: for(Pair *pair=*ref++; pair; pair=pair->link)
418: if(callback(pair->key, pair->value, info))
419: return pair->value;
420:
421: return V(0);
422: }
1.27 paf 423:
1.29 paf 424: /// remove all elements
1.59 paf 425: void clear() {
426: memset(refs, 0, sizeof(*refs)*allocated);
427: fpairs_count=fused_refs=0;
428: }
1.15 paf 429:
1.1 paf 430: private:
431:
1.39 paf 432: /// expand when these %% of allocated exausted
1.1 paf 433: enum {
434: THRESHOLD_PERCENT=75
435: };
1.9 paf 436:
1.61 paf 437: /// the index of [allocated] in [Hash_allocates]
1.19 paf 438: int allocates_index;
1.1 paf 439:
1.39 paf 440: /// number of allocated pairs
1.19 paf 441: int allocated;
1.1 paf 442:
1.59 paf 443: /// helper: expanding when fused_refs == threshold
1.1 paf 444: int threshold;
445:
1.39 paf 446: /// used pairs
1.59 paf 447: int fused_refs;
1.44 parser 448:
449: /// stored pairs total (including those by links)
1.59 paf 450: int fpairs_count;
1.1 paf 451:
1.39 paf 452: /// pair storage
1.59 paf 453: class Pair: public PA_Allocated {
454: public:
1.1 paf 455: uint code;
1.59 paf 456: K key;
457: V value;
1.1 paf 458: Pair *link;
1.2 paf 459:
1.59 paf 460: Pair(uint acode, K akey, V avalue, Pair *alink) :
1.1 paf 461: code(acode),
462: key(akey),
463: value(avalue),
1.2 paf 464: link(alink) {}
465: } **refs;
1.1 paf 466:
1.39 paf 467: /// filled to threshold: needs expanding
1.59 paf 468: bool is_full() { return fused_refs==threshold; }
1.5 paf 469:
1.39 paf 470: /// allocate larger buffer & rehash
1.59 paf 471: void expand() {
472: int old_allocated=allocated;
473: Pair **old_refs=refs;
474:
475: allocates_index=allocates_index+1<HASH_ALLOCATES_COUNT?allocates_index+1:HASH_ALLOCATES_COUNT-1;
476: // allocated bigger refs array
1.61 paf 477: allocated=Hash_allocates[allocates_index];
1.59 paf 478: threshold=allocated*THRESHOLD_PERCENT/100;
479: refs=new(UseGC) Pair*[allocated];
480:
481: // rehash
482: Pair **old_ref=old_refs;
483: for(int old_index=0; old_index<old_allocated; old_index++)
484: for(Pair *pair=*old_ref++; pair; ) {
485: Pair *next=pair->link;
486:
487: uint new_index=pair->code%allocated;
488: Pair **new_ref=&refs[new_index];
489: pair->link=*new_ref;
490: *new_ref=pair;
491:
492: pair=next;
493: }
494:
495: delete[] old_refs;
496: }
1.4 paf 497:
498: private: //disabled
499:
1.12 paf 500: Hash& operator = (const Hash&) { return *this; }
1.1 paf 501: };
1.59 paf 502:
503: /// Auto-object used to temporarily substituting/removing hash values
504: template <typename K, typename V>
1.55 paf 505: class Temp_hash_value {
1.59 paf 506: Hash<K, V>& fhash;
507: K fname;
508: V saved_value;
1.55 paf 509: public:
1.59 paf 510: Temp_hash_value(Hash<K, V>& ahash, K aname, V avalue) :
1.55 paf 511: fhash(ahash),
512: fname(aname),
513: saved_value(ahash.get(aname)) {
514: fhash.put(aname, avalue);
515: }
516: ~Temp_hash_value() {
517: fhash.put(fname, saved_value);
518: }
519: };
1.1 paf 520:
521: #endif