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