Annotation of parser3/src/include/pa_hash.h, revision 1.59
1.28 paf 1: /** @file
1.29 paf 2: Parser: hash class decl.
3:
1.59 ! 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.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.59 ! paf 20: static const char* IDENT_HASH_H="$Date: 2003/06/27 08:36:59 $";
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.29 paf 27: /**
1.59 ! paf 28: Simple hash.
1.29 paf 29:
1.59 ! 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.59 ! paf 35: template<typename K, typename V> class Hash: public PA_Object {
1.1 paf 36: public:
37:
1.59 ! paf 38: typedef K key_type;
! 39: typedef V value_type;
1.3 paf 40:
1.59 ! paf 41: Hash() {
! 42: allocated=allocates[allocates_index=0];
! 43: threshold=allocated*THRESHOLD_PERCENT/100;
! 44: fpairs_count=fused_refs=0;
! 45: refs=new(UseGC) Pair*[allocated];
! 46: }
1.25 paf 47:
1.59 ! paf 48: Hash(const Hash& source) {
! 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;
! 54: refs=new(UseGC) Pair*[allocated];
! 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;
1.45 paf 61:
1.59 ! paf 62: Pair **new_ref=&refs[index];
! 63: *new_ref=new Pair(pair->code, pair->key, pair->value, *new_ref);
1.38 paf 64:
1.59 ! paf 65: pair=next;
! 66: }
1.43 parser 67: }
68:
1.59 ! paf 69: /// put a [value] under the [key] @returns existed or not
! 70: bool put(K key, V value) {
! 71: if(!value) {
! 72: remove(key);
! 73: return false;
! 74: }
! 75: if(is_full())
! 76: expand();
! 77:
! 78: uint code=hash_code(key);
! 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;
1.24 paf 94: }
1.10 paf 95:
1.59 ! paf 96: /// remove the [key] @returns existed or not
! 97: bool remove(K key) {
! 98: uint code=hash_code(key);
! 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: }
1.8 paf 109:
1.59 ! paf 110: return false;
! 111: }
1.48 paf 112:
1.59 ! paf 113: /// get associated [value] by the [key]
! 114: V get(K key) const {
! 115: uint code=hash_code(key);
! 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:
! 121: return V(0);
1.33 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.59 ! paf 125: bool put_replace(K key, V value) {
! 126: if(!value) {
! 127: remove(key);
! 128: return false;
! 129: }
! 130: uint code=hash_code(key);
! 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.59 ! paf 144: bool put_dont_replace(K key, V value) {
! 145: if(!value) {
! 146: remove(key);
! 147: return false;
! 148: }
! 149: if(is_full())
! 150: expand();
! 151:
! 152: uint code=hash_code(key);
! 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.59 ! paf 169: /** put all 'src' values if NO with same key existed
! 170: @todo optimize this.allocated==src.allocated case
! 171: */
! 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.59 ! paf 179: int count() const { return fpairs_count; }
1.25 paf 180:
1.59 ! 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.59 ! paf 189: /// iterate over all pairs
! 190: template<typename I> void for_each_ref(void callback(K, V&, I), I info) const {
! 191: Pair **ref=refs;
! 192: for(int index=0; index<allocated; index++)
! 193: for(Pair *pair=*ref++; pair; pair=pair->link)
! 194: callback(pair->key, pair->value, info);
! 195: }
1.38 paf 196:
1.59 ! paf 197: /// iterate over all pairs until condition becomes true, return that element
! 198: template<typename I> V first_that(bool callback(K, V, I), I info) const {
! 199: Pair **ref=refs;
! 200: for(int index=0; index<allocated; index++)
! 201: for(Pair *pair=*ref++; pair; pair=pair->link)
! 202: if(callback(pair->key, pair->value, info))
! 203: return pair->value;
! 204:
! 205: return V(0);
! 206: }
1.27 paf 207:
1.29 paf 208: /// remove all elements
1.59 ! paf 209: void clear() {
! 210: memset(refs, 0, sizeof(*refs)*allocated);
! 211: fpairs_count=fused_refs=0;
! 212: }
1.15 paf 213:
1.1 paf 214: private:
215:
1.39 paf 216: /// expand when these %% of allocated exausted
1.1 paf 217: enum {
218: THRESHOLD_PERCENT=75
219: };
1.9 paf 220:
1.39 paf 221: /// the index of [allocated] in [allocates]
1.19 paf 222: int allocates_index;
1.1 paf 223:
1.39 paf 224: /// possible [allocates]. prime numbers
1.19 paf 225: static uint allocates[];
1.59 ! paf 226:
1.39 paf 227: /// number of allocated pairs
1.19 paf 228: int allocated;
1.1 paf 229:
1.59 ! paf 230: /// helper: expanding when fused_refs == threshold
1.1 paf 231: int threshold;
232:
1.39 paf 233: /// used pairs
1.59 ! paf 234: int fused_refs;
1.44 parser 235:
236: /// stored pairs total (including those by links)
1.59 ! paf 237: int fpairs_count;
1.1 paf 238:
1.39 paf 239: /// pair storage
1.59 ! paf 240: class Pair: public PA_Allocated {
! 241: public:
1.1 paf 242: uint code;
1.59 ! paf 243: K key;
! 244: V value;
1.1 paf 245: Pair *link;
1.2 paf 246:
1.59 ! paf 247: Pair(uint acode, K akey, V avalue, Pair *alink) :
1.1 paf 248: code(acode),
249: key(akey),
250: value(avalue),
1.2 paf 251: link(alink) {}
252: } **refs;
1.1 paf 253:
1.39 paf 254: /// filled to threshold: needs expanding
1.59 ! paf 255: bool is_full() { return fused_refs==threshold; }
1.5 paf 256:
1.39 paf 257: /// allocate larger buffer & rehash
1.59 ! paf 258: void expand() {
! 259: int old_allocated=allocated;
! 260: Pair **old_refs=refs;
! 261:
! 262: allocates_index=allocates_index+1<HASH_ALLOCATES_COUNT?allocates_index+1:HASH_ALLOCATES_COUNT-1;
! 263: // allocated bigger refs array
! 264: allocated=allocates[allocates_index];
! 265: threshold=allocated*THRESHOLD_PERCENT/100;
! 266: refs=new(UseGC) Pair*[allocated];
! 267:
! 268: // rehash
! 269: Pair **old_ref=old_refs;
! 270: for(int old_index=0; old_index<old_allocated; old_index++)
! 271: for(Pair *pair=*old_ref++; pair; ) {
! 272: Pair *next=pair->link;
! 273:
! 274: uint new_index=pair->code%allocated;
! 275: Pair **new_ref=&refs[new_index];
! 276: pair->link=*new_ref;
! 277: *new_ref=pair;
! 278:
! 279: pair=next;
! 280: }
! 281:
! 282: delete[] old_refs;
! 283: }
1.4 paf 284:
285: private: //disabled
286:
1.12 paf 287: Hash& operator = (const Hash&) { return *this; }
1.1 paf 288: };
1.49 paf 289:
1.59 ! paf 290: /* Zend comment: Generated on an Octa-ALPHA 300MHz CPU & 2.5GB RAM monster */
! 291: template<typename K, typename V>
! 292: uint Hash<K, V>::allocates[HASH_ALLOCATES_COUNT]={
! 293: 5, 11, 19, 53, 107, 223, 463, 983, 1979, 3907, 7963,
! 294: 16229, 32531, 65407, 130987, 262237, 524521, 1048793,
! 295: 2097397, 4194103, 8388857, 16777447, 33554201, 67108961,
! 296: 134217487, 268435697, 536870683, 1073741621, 2147483399};
! 297:
! 298: /// useful generic hash function
! 299: inline void generic_hash_code(uint& result, char c) {
! 300: result=(result<<4)+c;
! 301: if(uint g=(result&0xF0000000)) {
! 302: result=result^(g>>24);
! 303: result=result^g;
! 304: }
! 305: }
! 306: /// useful generic hash function
! 307: inline void generic_hash_code(uint& result, const char* s) {
! 308: while(char c=*s++) {
! 309: result=(result<<4)+c;
! 310: if(uint g=(result&0xF0000000)) {
! 311: result=result^(g>>24);
! 312: result=result^g;
! 313: }
! 314: }
! 315: }
! 316:
! 317: /// useful generic hash function
! 318: inline void generic_hash_code(uint& result, const char* buf, size_t size) {
! 319: const char* end=buf+size;
! 320: while(buf<end) {
! 321: result=(result<<4)+*buf++;
! 322: if(uint g=(result&0xF0000000)) {
! 323: result=result^(g>>24);
! 324: result=result^g;
! 325: }
! 326: }
! 327: }
! 328:
! 329: /// simple hash code of int. used by EXIF mapping
! 330: inline uint hash_code(int self) {
! 331: uint result=0;
! 332: generic_hash_code(result, (const char*)&self, sizeof(self));
! 333: return result;
! 334: }
! 335:
! 336: /// Auto-object used to temporarily substituting/removing hash values
! 337: template <typename K, typename V>
1.55 paf 338: class Temp_hash_value {
1.59 ! paf 339: Hash<K, V>& fhash;
! 340: K fname;
! 341: V saved_value;
1.55 paf 342: public:
1.59 ! paf 343: Temp_hash_value(Hash<K, V>& ahash, K aname, V avalue) :
1.55 paf 344: fhash(ahash),
345: fname(aname),
346: saved_value(ahash.get(aname)) {
347: fhash.put(aname, avalue);
348: }
349: ~Temp_hash_value() {
350: fhash.put(fname, saved_value);
351: }
352: };
1.1 paf 353:
354: #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