Annotation of parser3/src/include/pa_hash.h, revision 1.42
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.22 paf 6: Author: Alexander Petrosyan <paf@design.ru> (http://design.ru/paf)
1.1 paf 7:
1.42 ! parser 8: $Id: pa_hash.h,v 1.41 2001/05/17 10:22:24 parser 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: /**
21: Pooled hash.
22:
23: Automatically rehashed when almost full.
24: */
1.23 paf 25: class Hash : public Pooled {
1.1 paf 26: public:
27:
1.29 paf 28: typedef String Key; ///< hash Key type. longing for templates
1.30 paf 29: typedef void Val; ///< hash Val type. longing for templates
1.3 paf 30:
1.31 paf 31: /// for_each iterator function type
32: typedef void (*For_each_func)(const Key& key, Val *value, void *info);
1.25 paf 33:
1.38 paf 34: /// first_that iterator function type
1.42 ! parser 35: typedef void *(*First_that_func)(const Key& key, Val *value, void *info);
1.38 paf 36:
1.8 paf 37: public:
38:
1.35 paf 39: Hash(Pool& apool) : Pooled(apool) {
40: construct(apool);
1.24 paf 41: }
1.10 paf 42:
1.29 paf 43: /// useful generic hash function
1.19 paf 44: static uint generic_code(uint aresult, const char *start, uint allocated);
1.8 paf 45:
1.29 paf 46: /// put a [value] under the [key], return existed or not
1.40 parser 47: bool put(const Key& key, Val *value);
1.33 paf 48: /*
49: /// dirty hack to allow constant items storage. I long for Hash<const Val*>
1.40 parser 50: bool put(const Key& key, const Val *value) {
1.33 paf 51: return put(key, const_cast<Val *>(value));
52: }
53: */
1.29 paf 54: /// get associated [value] by the [key]
1.40 parser 55: Val *get(const Key& key) const;
1.17 paf 56:
1.29 paf 57: /// put a [value] under the [key] if that [key] existed, return existed or not
1.40 parser 58: bool put_replace(const Key& key, Val *value);
1.18 paf 59:
1.29 paf 60: /// put a [value] under the [key] if that [key] NOT existed, return existed or not
1.40 parser 61: bool put_dont_replace(const Key& key, Val *value);
1.18 paf 62:
1.29 paf 63: /// put all 'src' values if NO with same key existed
1.40 parser 64: void merge_dont_replace(const Hash& src);
1.11 paf 65:
1.30 paf 66: void put(const Key& key, int value) { put(key, reinterpret_cast<Val *>(value)); }
1.36 paf 67: void put(const Key& key, const String *value) {
68: put(key, static_cast<Val *>(const_cast<String *>(value)));
69: }
1.11 paf 70:
1.29 paf 71: //@{
72: /// handy get, longing for Hash<int>, Hash<String *>
1.32 paf 73: int get_int(const Key& key) const { return reinterpret_cast<int>(get(key)); }
74: const String *get_string(const Key& key) const { return static_cast<String *>(get(key)); }
1.29 paf 75: //@}
1.10 paf 76:
1.29 paf 77: /// number of elements in hash
1.37 paf 78: int size() const { return used; }
1.25 paf 79:
1.29 paf 80: /// iterate over all not zero elements
1.36 paf 81: void for_each(For_each_func func, void *info=0) const;
1.38 paf 82:
83: /// iterate over all elements until condition
1.42 ! parser 84: void *first_that(First_that_func func, void *info=0) const;
1.27 paf 85:
1.29 paf 86: /// remove all elements
1.27 paf 87: void clear();
1.19 paf 88:
1.15 paf 89: protected:
90:
1.35 paf 91: void construct(Pool& apool);
1.15 paf 92:
1.1 paf 93: private:
94:
1.39 paf 95: /// expand when these %% of allocated exausted
1.1 paf 96: enum {
97: THRESHOLD_PERCENT=75
98: };
1.9 paf 99:
1.39 paf 100: /// the index of [allocated] in [allocates]
1.19 paf 101: int allocates_index;
1.1 paf 102:
1.39 paf 103: /// possible [allocates]. prime numbers
1.19 paf 104: static uint allocates[];
105: static int allocates_count;
1.1 paf 106:
1.39 paf 107: /// number of allocated pairs
1.19 paf 108: int allocated;
1.1 paf 109:
1.39 paf 110: /// helper: expanding when used == threshold
1.1 paf 111: int threshold;
112:
1.39 paf 113: /// used pairs
1.1 paf 114: int used;
115:
1.39 paf 116: /// pair storage
1.1 paf 117: class Pair {
1.2 paf 118: friend Hash;
119:
1.1 paf 120: uint code;
1.15 paf 121: const Key key;
1.30 paf 122: Val *value;
1.1 paf 123: Pair *link;
1.2 paf 124:
1.19 paf 125: void *operator new(size_t allocated, Pool& apool);
1.2 paf 126:
1.30 paf 127: Pair(uint acode, const Key& akey, Val *avalue, Pair *alink) :
1.1 paf 128: code(acode),
129: key(akey),
130: value(avalue),
1.2 paf 131: link(alink) {}
132: } **refs;
1.1 paf 133:
1.39 paf 134: /// filled to threshold: needs expanding
1.5 paf 135: bool full() { return used==threshold; }
136:
1.39 paf 137: /// allocate larger buffer & rehash
1.1 paf 138: void expand();
1.4 paf 139:
140: private: //disabled
141:
1.11 paf 142: //Hash(Hash&) {}
1.12 paf 143: Hash& operator = (const Hash&) { return *this; }
1.1 paf 144: };
145:
146: #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