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