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