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