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