Annotation of parser3/src/include/pa_hash.h, revision 1.57.4.1
1.28 paf 1: /** @file
1.29 paf 2: Parser: hash class decl.
3:
1.53 paf 4: Copyright (c) 2001, 2002 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:
9: #ifndef PA_HASH_H
10: #define PA_HASH_H
1.56 paf 11:
1.57.4.1! paf 12: static const char* IDENT_HASH_H="$Date: 2002/08/01 11:41:15 $";
1.1 paf 13:
1.14 paf 14: #include "pa_pool.h"
1.1 paf 15: #include "pa_types.h"
16: #include "pa_string.h"
17:
1.29 paf 18: /**
19: Pooled hash.
20:
21: Automatically rehashed when almost full.
1.51 paf 22: Contains no 0 values.
23: get returning 0 means there were no such.
24: "put value 0" means "remove"
1.29 paf 25: */
1.23 paf 26: class Hash : public Pooled {
1.1 paf 27: public:
28:
1.29 paf 29: typedef String Key; ///< hash Key type. longing for templates
1.30 paf 30: typedef void Val; ///< hash Val type. longing for templates
1.3 paf 31:
1.31 paf 32: /// for_each iterator function type
33: typedef void (*For_each_func)(const Key& key, Val *value, void *info);
1.25 paf 34:
1.45 paf 35: /// for_each iterator function type
36: typedef void (*For_each_func_refed)(const Key& key, Val *& value, void *info);
37:
1.38 paf 38: /// first_that iterator function type
1.42 parser 39: typedef void *(*First_that_func)(const Key& key, Val *value, void *info);
1.38 paf 40:
1.8 paf 41: public:
42:
1.35 paf 43: Hash(Pool& apool) : Pooled(apool) {
1.43 parser 44: construct_new();
45: }
46:
47: Hash(const Hash& source) : Pooled(source.pool()){
48: construct_copy(source);
1.24 paf 49: }
1.10 paf 50:
1.29 paf 51: /// useful generic hash function
1.19 paf 52: static uint generic_code(uint aresult, const char *start, uint allocated);
1.8 paf 53:
1.51 paf 54: /// put a [value] under the [key] @returns existed or not
1.40 parser 55: bool put(const Key& key, Val *value);
1.48 paf 56:
1.57.4.1! paf 57: /// put a [value] under the [key] @returns existed or not
! 58: bool put_case_insensitive(const Key& key, Val *value);
! 59:
1.51 paf 60: /// remove the [key] @returns existed or not
61: bool remove(const Key& key);
1.33 paf 62: /*
63: /// dirty hack to allow constant items storage. I long for Hash<const Val*>
1.40 parser 64: bool put(const Key& key, const Val *value) {
1.33 paf 65: return put(key, const_cast<Val *>(value));
66: }
67: */
1.29 paf 68: /// get associated [value] by the [key]
1.40 parser 69: Val *get(const Key& key) const;
1.17 paf 70:
1.57.4.1! paf 71: /// get associated [value] by they [key], ignoring case
! 72: Val *get_case_insensitive(const Key& key) const;
! 73:
1.51 paf 74: /// put a [value] under the [key] if that [key] existed @returns existed or not
1.40 parser 75: bool put_replace(const Key& key, Val *value);
1.18 paf 76:
1.51 paf 77: /// put a [value] under the [key] if that [key] NOT existed @returns existed or not
1.40 parser 78: bool put_dont_replace(const Key& key, Val *value);
1.18 paf 79:
1.57.4.1! paf 80: /// put a [value] under the [key_lower] if that [key] NOT existed, ignoring case @returns existed or not
! 81: bool put_dont_replace_case_insensitive(const Key& key, Val *value);
! 82:
1.29 paf 83: /// put all 'src' values if NO with same key existed
1.40 parser 84: void merge_dont_replace(const Hash& src);
1.11 paf 85:
1.30 paf 86: void put(const Key& key, int value) { put(key, reinterpret_cast<Val *>(value)); }
1.36 paf 87: void put(const Key& key, const String *value) {
88: put(key, static_cast<Val *>(const_cast<String *>(value)));
89: }
1.11 paf 90:
1.29 paf 91: //@{
92: /// handy get, longing for Hash<int>, Hash<String *>
1.32 paf 93: int get_int(const Key& key) const { return reinterpret_cast<int>(get(key)); }
94: const String *get_string(const Key& key) const { return static_cast<String *>(get(key)); }
1.29 paf 95: //@}
1.10 paf 96:
1.29 paf 97: /// number of elements in hash
1.44 parser 98: int size() const { return count; }
1.25 paf 99:
1.29 paf 100: /// iterate over all not zero elements
1.36 paf 101: void for_each(For_each_func func, void *info=0) const;
1.45 paf 102:
103: /// iterate over all not zero elements, passing references
104: void for_each(For_each_func_refed func, void *info=0) const;
1.38 paf 105:
106: /// iterate over all elements until condition
1.42 parser 107: void *first_that(First_that_func func, void *info=0) const;
1.27 paf 108:
1.29 paf 109: /// remove all elements
1.27 paf 110: void clear();
1.19 paf 111:
1.15 paf 112: protected:
113:
1.43 parser 114: void construct_new();
115: void construct_copy(const Hash& source);
1.15 paf 116:
1.1 paf 117: private:
118:
1.39 paf 119: /// expand when these %% of allocated exausted
1.1 paf 120: enum {
121: THRESHOLD_PERCENT=75
122: };
1.9 paf 123:
1.39 paf 124: /// the index of [allocated] in [allocates]
1.19 paf 125: int allocates_index;
1.1 paf 126:
1.39 paf 127: /// possible [allocates]. prime numbers
1.19 paf 128: static uint allocates[];
129: static int allocates_count;
1.1 paf 130:
1.39 paf 131: /// number of allocated pairs
1.19 paf 132: int allocated;
1.1 paf 133:
1.39 paf 134: /// helper: expanding when used == threshold
1.1 paf 135: int threshold;
136:
1.39 paf 137: /// used pairs
1.1 paf 138: int used;
1.44 parser 139:
140: /// stored pairs total (including those by links)
141: int count;
1.1 paf 142:
1.39 paf 143: /// pair storage
1.1 paf 144: class Pair {
1.46 paf 145: friend class Hash;
1.2 paf 146:
1.1 paf 147: uint code;
1.47 paf 148: const Key& key;
1.30 paf 149: Val *value;
1.1 paf 150: Pair *link;
1.2 paf 151:
1.19 paf 152: void *operator new(size_t allocated, Pool& apool);
1.2 paf 153:
1.30 paf 154: Pair(uint acode, const Key& akey, Val *avalue, Pair *alink) :
1.1 paf 155: code(acode),
156: key(akey),
157: value(avalue),
1.2 paf 158: link(alink) {}
159: } **refs;
1.1 paf 160:
1.39 paf 161: /// filled to threshold: needs expanding
1.5 paf 162: bool full() { return used==threshold; }
163:
1.39 paf 164: /// allocate larger buffer & rehash
1.1 paf 165: void expand();
1.57.4.1! paf 166:
! 167: private: // internals
! 168:
! 169: /// get associated [value] by they [key], ignoring case
! 170: Val *get_case_insensitive_internal(const Key& key_lower) const;
! 171:
! 172:
1.4 paf 173:
174: private: //disabled
175:
1.12 paf 176: Hash& operator = (const Hash&) { return *this; }
1.1 paf 177: };
1.49 paf 178:
1.55 paf 179: /// Auto-object used for temporarily substituting/removing hash values
180: class Temp_hash_value {
181: Hash& fhash;
182: const Hash::Key& fname;
183: Hash::Val *saved_value;
184: public:
185: Temp_hash_value(Hash& ahash, const Hash::Key& aname, Hash::Val *avalue) :
186: fhash(ahash),
187: fname(aname),
188: saved_value(ahash.get(aname)) {
189: fhash.put(aname, avalue);
190: }
191: ~Temp_hash_value() {
192: fhash.put(fname, saved_value);
193: }
194: };
1.1 paf 195:
196: #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