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