Annotation of parser3/src/include/pa_hash.h, revision 1.58.2.18.2.8
1.28 paf 1: /** @file
1.29 paf 2: Parser: hash class decl.
3:
1.58.2.10 paf 4: Copyright (c) 2001-2003 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.58.2.2 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.58.2.18.2.8! (paf 20:: static const char* IDENT_HASH_H="$Date: 2003/03/27 14:05:40 $";
1.1 paf 21:
1.58.2.18.2.1 (paf 22:: #include "pa_memory.h"
1.1 paf 23: #include "pa_types.h"
24:
1.58.2.18.2.8! (paf 25:: const int HASH_ALLOCATES_COUNT=29;
! 26::
1.29 paf 27: /**
1.58.2.2 paf 28: Simple hash.
1.29 paf 29:
1.58.2.2 paf 30: Automatically rehashed when almost is_full.
1.51 paf 31: Contains no 0 values.
32: get returning 0 means there were no such.
33: "put value 0" means "remove"
1.29 paf 34: */
1.58.2.2 paf 35: template<typename K, typename V> class Hash: public PA_Object {
1.1 paf 36: public:
37:
1.58.2.6 paf 38: typedef K key_type;
39: typedef V value_type;
1.8 paf 40:
1.58.2.1 paf 41: Hash() {
1.58.2.2 paf 42: allocated=allocates[allocates_index=0];
43: threshold=allocated*THRESHOLD_PERCENT/100;
44: fpairs_count=fused_refs=0;
1.58.2.18.2.7 (paf 45:: refs=new(UseGC) Pair*[allocated];
1.43 parser 46: }
47:
1.58.2.1 paf 48: Hash(const Hash& source) {
1.58.2.2 paf 49: allocates_index=source.allocates_index;
50: allocated=source.allocated;
51: threshold=source.threshold;
52: fused_refs=source.fused_refs;
53: fpairs_count=source.fpairs_count;
1.58.2.18.2.7 (paf 54:: refs=new(UseGC) Pair*[allocated];
1.58.2.17 paf 55:
56: // clone & rehash
57: Pair **old_ref=source.refs;
58: for(int index=0; index<allocated; index++)
59: for(Pair *pair=*old_ref++; pair; ) {
60: Pair *next=pair->link;
61:
62: Pair **new_ref=&refs[index];
63: *new_ref=new Pair(pair->code, pair->key, pair->value, *new_ref);
64:
65: pair=next;
66: }
1.58.2.2 paf 67: }
1.10 paf 68:
1.51 paf 69: /// put a [value] under the [key] @returns existed or not
1.58.2.8 paf 70: bool put(K key, V value) {
1.58.2.18 paf 71: if(!value) {
72: remove(key);
73: return false;
74: }
1.58.2.2 paf 75: if(is_full())
76: expand();
77:
1.58.2.7 paf 78: uint code=hash_code(key);
1.58.2.2 paf 79: uint index=code%allocated;
80: Pair **ref=&refs[index];
81: for(Pair *pair=*ref; pair; pair=pair->link)
82: if(pair->code==code && pair->key==key) {
83: // found a pair with the same key
84: pair->value=value;
85: return true;
86: }
87:
88: // proper pair not found -- create&link_in new pair
89: if(!*ref) // root cell were fused_refs?
90: fused_refs++; // not, we'll use it and record the fact
91: *ref=new Pair(code, key, value, *ref);
92: fpairs_count++;
93: return false;
94: }
1.48 paf 95:
1.51 paf 96: /// remove the [key] @returns existed or not
1.58.2.8 paf 97: bool remove(K key) {
1.58.2.7 paf 98: uint code=hash_code(key);
1.58.2.2 paf 99: uint index=code%allocated;
100: for(Pair **ref=&refs[index]; *ref; ref=&(*ref)->link)
101: if((*ref)->code==code && (*ref)->key==key) {
102: // found a pair with the same key
103: Pair *next=(*ref)->link;
104: delete *ref;
105: *ref=next;
106: --fpairs_count;
107: return true;
108: }
109:
110: return false;
1.33 paf 111: }
1.58.2.2 paf 112:
1.29 paf 113: /// get associated [value] by the [key]
1.58.2.8 paf 114: V get(K key) const {
1.58.2.7 paf 115: uint code=hash_code(key);
1.58.2.2 paf 116: uint index=code%allocated;
117: for(Pair *pair=refs[index]; pair; pair=pair->link)
118: if(pair->code==code && pair->key==key)
119: return pair->value;
120:
1.58.2.12 paf 121: return V(0);
1.58.2.2 paf 122: }
1.17 paf 123:
1.51 paf 124: /// put a [value] under the [key] if that [key] existed @returns existed or not
1.58.2.8 paf 125: bool put_replace(K key, V value) {
1.58.2.18 paf 126: if(!value) {
127: remove(key);
128: return false;
129: }
1.58.2.7 paf 130: uint code=hash_code(key);
1.58.2.2 paf 131: uint index=code%allocated;
132: for(Pair *pair=refs[index]; pair; pair=pair->link)
133: if(pair->code==code && pair->key==key) {
134: // found a pair with the same key, replacing
135: pair->value=value;
136: return true;
137: }
138:
139: // proper pair not found
140: return false;
141: }
1.18 paf 142:
1.51 paf 143: /// put a [value] under the [key] if that [key] NOT existed @returns existed or not
1.58.2.8 paf 144: bool put_dont_replace(K key, V value) {
1.58.2.18 paf 145: if(!value) {
146: remove(key);
147: return false;
148: }
1.58.2.2 paf 149: if(is_full())
150: expand();
151:
1.58.2.7 paf 152: uint code=hash_code(key);
1.58.2.2 paf 153: uint index=code%allocated;
154: Pair **ref=&refs[index];
155: for(Pair *pair=*ref; pair; pair=pair->link)
156: if(pair->code==code && pair->key==key) {
157: // found a pair with the same key, NOT replacing
158: return true;
159: }
160:
161: // proper pair not found -- create&link_in new pair
162: if(!*ref) // root cell were fused_refs?
163: fused_refs++; // not, we'll use it and record the fact
164: *ref=new Pair(code, key, value, *ref);
165: fpairs_count++;
166: return false;
167: }
1.18 paf 168:
1.58.2.17 paf 169: /** put all 'src' values if NO with same key existed
170: @todo optimize this.allocated==src.allocated case
171: */
1.58.2.2 paf 172: void merge_dont_replace(const Hash& src) {
173: for(int i=0; i<src.allocated; i++)
174: for(Pair *pair=src.refs[i]; pair; pair=pair->link)
175: put_dont_replace(pair->key, pair->value);
1.36 paf 176: }
1.11 paf 177:
1.29 paf 178: /// number of elements in hash
1.58.2.2 paf 179: int count() const { return fpairs_count; }
1.25 paf 180:
1.58.2.2 paf 181: /// iterate over all pairs
182: template<typename I> void for_each(void callback(K, V, I), I info) const {
183: Pair **ref=refs;
184: for(int index=0; index<allocated; index++)
185: for(Pair *pair=*ref++; pair; pair=pair->link)
186: callback(pair->key, pair->value, info);
187: }
1.45 paf 188:
1.58.2.2 paf 189: /// iterate over all pairs until condition becomes true, return that element
1.58.2.9 paf 190: template<typename I> V first_that(bool callback(K, V, I), I info) const {
1.58.2.2 paf 191: Pair **ref=refs;
192: for(int index=0; index<allocated; index++)
193: for(Pair *pair=*ref++; pair; pair=pair->link)
194: if(callback(pair->key, pair->value, info))
1.58.2.14 paf 195: return pair->value;
1.58.2.2 paf 196:
1.58.2.13 paf 197: return V(0);
1.58.2.2 paf 198: }
1.27 paf 199:
1.29 paf 200: /// remove all elements
1.58.2.2 paf 201: void clear() {
1.58.2.18.2.5 (paf 202:: memset(refs, 0, sizeof(*refs)*allocated);
1.58.2.2 paf 203: fpairs_count=fused_refs=0;
204: }
1.15 paf 205:
1.1 paf 206: private:
207:
1.39 paf 208: /// expand when these %% of allocated exausted
1.1 paf 209: enum {
210: THRESHOLD_PERCENT=75
211: };
1.9 paf 212:
1.39 paf 213: /// the index of [allocated] in [allocates]
1.19 paf 214: int allocates_index;
1.1 paf 215:
1.39 paf 216: /// possible [allocates]. prime numbers
1.58.2.3 paf 217: static uint allocates[];
218:
1.39 paf 219: /// number of allocated pairs
1.19 paf 220: int allocated;
1.1 paf 221:
1.58.2.2 paf 222: /// helper: expanding when fused_refs == threshold
1.1 paf 223: int threshold;
224:
1.39 paf 225: /// used pairs
1.58.2.2 paf 226: int fused_refs;
1.44 parser 227:
228: /// stored pairs total (including those by links)
1.58.2.2 paf 229: int fpairs_count;
1.1 paf 230:
1.39 paf 231: /// pair storage
1.58.2.2 paf 232: class Pair: public PA_Allocated {
1.58.2.4 paf 233: public:
1.1 paf 234: uint code;
1.58.2.8 paf 235: K key;
1.58.2.2 paf 236: V value;
1.1 paf 237: Pair *link;
1.2 paf 238:
1.58.2.8 paf 239: Pair(uint acode, K akey, V avalue, Pair *alink) :
1.1 paf 240: code(acode),
241: key(akey),
242: value(avalue),
1.2 paf 243: link(alink) {}
244: } **refs;
1.1 paf 245:
1.39 paf 246: /// filled to threshold: needs expanding
1.58.2.2 paf 247: bool is_full() { return fused_refs==threshold; }
1.5 paf 248:
1.39 paf 249: /// allocate larger buffer & rehash
1.58.2.2 paf 250: void expand() {
251: int old_allocated=allocated;
252: Pair **old_refs=refs;
253:
1.58.2.18.2.8! (paf 254:: allocates_index=allocates_index+1<HASH_ALLOCATES_COUNT?allocates_index+1:HASH_ALLOCATES_COUNT-1;
1.58.2.17 paf 255: // allocated bigger refs array
1.58.2.2 paf 256: allocated=allocates[allocates_index];
257: threshold=allocated*THRESHOLD_PERCENT/100;
1.58.2.18.2.4 (paf 258:: refs=new(UseGC) Pair*[allocated];
1.58.2.2 paf 259:
260: // rehash
261: Pair **old_ref=old_refs;
262: for(int old_index=0; old_index<old_allocated; old_index++)
263: for(Pair *pair=*old_ref++; pair; ) {
264: Pair *next=pair->link;
265:
266: uint new_index=pair->code%allocated;
267: Pair **new_ref=&refs[new_index];
268: pair->link=*new_ref;
269: *new_ref=pair;
270:
271: pair=next;
272: }
273:
1.58.2.18.2.4 (paf 274:: delete[] old_refs;
1.58.2.2 paf 275: }
1.4 paf 276:
277: private: //disabled
278:
1.12 paf 279: Hash& operator = (const Hash&) { return *this; }
1.1 paf 280: };
1.58.2.3 paf 281:
282: /* Zend comment: Generated on an Octa-ALPHA 300MHz CPU & 2.5GB RAM monster */
283: template<typename K, typename V>
1.58.2.18.2.8! (paf 284:: uint Hash<K, V>::allocates[HASH_ALLOCATES_COUNT]={
1.58.2.3 paf 285: 5, 11, 19, 53, 107, 223, 463, 983, 1979, 3907, 7963,
286: 16229, 32531, 65407, 130987, 262237, 524521, 1048793,
287: 2097397, 4194103, 8388857, 16777447, 33554201, 67108961,
288: 134217487, 268435697, 536870683, 1073741621, 2147483399};
1.58.2.5 paf 289:
1.58.2.18.2.6 (paf 290:: /// useful generic hash function
291:: inline void generic_hash_code(uint& result, char c) {
292:: result=(result<<4)+c;
293:: if(uint g=(result&0xF0000000)) {
294:: result=result^(g>>24);
295:: result=result^g;
296:: }
297:: }
1.58.2.5 paf 298: /// useful generic hash function
1.58.2.18.2.2 (paf 299:: inline void generic_hash_code(uint& result, const char* s) {
300:: while(char c=*s++) {
301:: result=(result<<4)+c;
302:: if(uint g=(result&0xF0000000)) {
303:: result=result^(g>>24);
304:: result=result^g;
305:: }
306:: }
307:: }
308::
309:: /// useful generic hash function
310:: inline void generic_hash_code(uint& result, const char* buf, size_t size) {
1.58.2.18.2.3 (paf 311:: const char* end=buf+size;
1.58.2.18.2.2 (paf 312:: while(buf<end) {
313:: result=(result<<4)+*buf++;
314:: if(uint g=(result&0xF0000000)) {
1.58.2.5 paf 315: result=result^(g>>24);
316: result=result^g;
317: }
318: }
1.58.2.15 paf 319: }
320:
321: /// simple hash code of int. used by EXIF mapping
322: inline uint hash_code(int self) {
1.58.2.18.2.2 (paf 323:: uint result=0;
324:: generic_hash_code(result, (const char*)&self, sizeof(self));
325:: return result;
1.58.2.5 paf 326: }
1.49 paf 327:
1.58.2.2 paf 328: /// Auto-object used to temporarily substituting/removing hash values
329: template <typename K, typename V>
1.55 paf 330: class Temp_hash_value {
1.58.2.11 paf 331: Hash<K, V>& fhash;
1.58.2.8 paf 332: K fname;
1.58.2.2 paf 333: V saved_value;
1.55 paf 334: public:
1.58.2.8 paf 335: Temp_hash_value(Hash<K, V>& ahash, K aname, V avalue) :
1.55 paf 336: fhash(ahash),
337: fname(aname),
338: saved_value(ahash.get(aname)) {
339: fhash.put(aname, avalue);
340: }
341: ~Temp_hash_value() {
342: fhash.put(fname, saved_value);
343: }
344: };
1.1 paf 345:
346: #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