Branch data Line data Source code
1 : : // $Id: Dict.h 6219 2008-10-01 05:39:07Z vern $
2 : : //
3 : : // See the file "COPYING" in the main distribution directory for copyright.
4 : :
5 : : #ifndef dict_h
6 : : #define dict_h
7 : :
8 : : #include "List.h"
9 : : #include "Hash.h"
10 : :
11 : : class Dictionary;
12 : : class DictEntry;
13 : : class IterCookie;
14 : :
15 : 529340 : declare(PList,DictEntry);
16 : 49134 : declare(PList,IterCookie);
17 : :
18 : : // Default number of hash buckets in dictionary. The dictionary will
19 : : // increase the size of the hash table as needed.
20 : : #define DEFAULT_DICT_SIZE 16
21 : :
22 : : // Type indicating whether the dictionary should keep track of the order
23 : : // of insertions.
24 : : typedef enum { ORDERED, UNORDERED } dict_order;
25 : :
26 : : // Type for function to be called when deleting elements.
27 : : typedef void (*dict_delete_func)(void*);
28 : :
29 : : // A dict_delete_func that just calls delete.
30 : : extern void generic_delete_func(void*);
31 : :
32 : : class Dictionary {
33 : : public:
34 : : Dictionary(dict_order ordering = UNORDERED,
35 : : int initial_size = DEFAULT_DICT_SIZE);
36 : : virtual ~Dictionary();
37 : :
38 : : // Member functions for looking up a key, inserting/changing its
39 : : // contents, and deleting it. These come in two flavors: one
40 : : // which takes a HashKey, and the other which takes a raw key,
41 : : // its size, and its (unmodulated) hash.
42 : 191810 : void* Lookup(const HashKey* key) const
43 : 191810 : { return Lookup(key->Key(), key->Size(), key->Hash()); }
44 : : void* Lookup(const void* key, int key_size, hash_t hash) const;
45 : :
46 : : // Returns previous value, or 0 if none.
47 : 45428 : void* Insert(HashKey* key, void* val)
48 : : {
49 : 45428 : return Insert(key->TakeKey(), key->Size(), key->Hash(), val, 0);
50 : : }
51 : : // If copy_key is true, then the key is copied, otherwise it's assumed
52 : : // that it's a heap pointer that now belongs to the Dictionary to
53 : : // manage as needed.
54 : : void* Insert(void* key, int key_size, hash_t hash, void* val,
55 : : int copy_key);
56 : :
57 : : // Removes the given element. Returns a pointer to the element in
58 : : // case it needs to be deleted. Returns 0 if no such element exists.
59 : : // If dontdelete is true, the key's bytes will not be deleted.
60 : 938 : void* Remove(const HashKey* key)
61 : 938 : { return Remove(key->Key(), key->Size(), key->Hash()); }
62 : : void* Remove(const void* key, int key_size, hash_t hash,
63 : : bool dont_delete = false);
64 : :
65 : : // Number of entries.
66 : 98332 : int Length() const
67 [ + + ]: 98332 : { return tbl2 ? num_entries + num_entries2 : num_entries; }
68 : :
69 : : // Largest it's ever been.
70 : 0 : int MaxLength() const
71 : : {
72 : : return tbl2 ?
73 [ # # ]: 0 : max_num_entries + max_num_entries2 : max_num_entries;
74 : : }
75 : :
76 : : // True if the dictionary is ordered, false otherwise.
77 : : int IsOrdered() const { return order != 0; }
78 : :
79 : : // If the dictionary is ordered then returns the n'th entry's value;
80 : : // the second method also returns the key. The first entry inserted
81 : : // corresponds to n=0.
82 : : //
83 : : // Returns nil if the dictionary is not ordered or if "n" is out
84 : : // of range.
85 : 0 : void* NthEntry(int n) const
86 : : {
87 : : const void* key;
88 : : int key_len;
89 : 0 : return NthEntry(n, key, key_len);
90 : : }
91 : : void* NthEntry(int n, const void*& key, int& key_len) const;
92 : :
93 : : // To iterate through the dictionary, first call InitForIteration()
94 : : // to get an "iteration cookie". The cookie can then be handed
95 : : // to NextEntry() to get the next entry in the iteration and update
96 : : // the cookie. If NextEntry() indicates no more entries, it will
97 : : // also delete the cookie, or the cookie can be manually deleted
98 : : // prior to this if no longer needed.
99 : : //
100 : : // Unexpected results will occur if the elements of
101 : : // the dictionary are changed between calls to NextEntry() without
102 : : // first calling InitForIteration().
103 : : //
104 : : // If return_hash is true, a HashKey for the entry is returned in h,
105 : : // which should be delete'd when no longer needed.
106 : : IterCookie* InitForIteration() const;
107 : : void* NextEntry(HashKey*& h, IterCookie*& cookie, int return_hash) const;
108 : : void* NextEntry(const void*& key, int& key_len, IterCookie*& cookie)
109 : : const;
110 : : void StopIteration(IterCookie* cookie) const;
111 : :
112 : 14752 : void SetDeleteFunc(dict_delete_func f) { delete_func = f; }
113 : :
114 : : // With a robust cookie, it is safe to change the dictionary while
115 : : // iterating. This means that (i) we will eventually visit all
116 : : // unmodified entries as well as all entries added during iteration,
117 : : // and (ii) we won't visit any still-unseen entries which are getting
118 : : // removed. (We don't get this for free, so only use it if
119 : : // necessary.)
120 : 7834 : void MakeRobustCookie(IterCookie* cookie)
121 : 7834 : { cookies.append(cookie); }
122 : :
123 : : unsigned int MemoryAllocation() const;
124 : :
125 : : private:
126 : : void Init(int size);
127 : : void Init2(int size); // initialize second table for resizing
128 : :
129 : : // Internal version of Insert().
130 : : void* Insert(DictEntry* entry, int copy_key);
131 : :
132 : : void* DoRemove(DictEntry* entry, hash_t h,
133 : : PList(DictEntry)* chain, int chain_offset);
134 : :
135 : : int NextPrime(int n) const;
136 : : int IsPrime(int n) const;
137 : : void StartChangeSize(int new_size);
138 : : void FinishChangeSize(void);
139 : : void MoveChains(void);
140 : :
141 : : // The following get and set the "density" threshold - if the
142 : : // average hash chain length exceeds this threshold, the
143 : : // table will be resized. The default value is 3.0.
144 : 55 : double DensityThresh() const { return den_thresh; }
145 : :
146 : 17252 : void SetDensityThresh(double thresh)
147 : : {
148 : 17252 : den_thresh = thresh;
149 : 17252 : thresh_entries = int(thresh * double(num_buckets));
150 : 17252 : }
151 : :
152 : : // Same for the second table, when resizing.
153 : 55 : void SetDensityThresh2(double thresh)
154 : : {
155 : 55 : den_thresh2 = thresh;
156 : 55 : thresh_entries2 = int(thresh * double(num_buckets2));
157 : 55 : }
158 : :
159 : : // Normally we only have tbl.
160 : : // When we're resizing, we'll have tbl (old) and tbl2 (new)
161 : : // tbl_next_ind keeps track of how much we've moved to tbl2
162 : : // (it's the next index we're going to move).
163 : : PList(DictEntry)** tbl;
164 : : int num_buckets;
165 : : int num_entries;
166 : : int max_num_entries;
167 : : double den_thresh;
168 : : int thresh_entries;
169 : :
170 : : // Resizing table (replicates tbl above).
171 : : PList(DictEntry)** tbl2;
172 : : int num_buckets2;
173 : : int num_entries2;
174 : : int max_num_entries2;
175 : : double den_thresh2;
176 : : int thresh_entries2;
177 : :
178 : : hash_t tbl_next_ind;
179 : :
180 : : PList(DictEntry)* order;
181 : : dict_delete_func delete_func;
182 : :
183 : : PList(IterCookie) cookies;
184 : : };
185 : :
186 : :
187 : : #define PDict(type) type ## PDict
188 : : #define PDictdeclare(type) \
189 : : class PDict(type) : public Dictionary { \
190 : : public: \
191 : : PDict(type)(dict_order ordering = UNORDERED, \
192 : : int initial_size = DEFAULT_DICT_SIZE) : \
193 : : Dictionary(ordering, initial_size) {} \
194 : : type* Lookup(const char* key) const \
195 : : { \
196 : : HashKey h(key); \
197 : : return (type*) Dictionary::Lookup(&h); \
198 : : } \
199 : : type* Lookup(const HashKey* key) const \
200 : : { return (type*) Dictionary::Lookup(key); } \
201 : : type* Insert(const char* key, type* val) \
202 : : { \
203 : : HashKey h(key); \
204 : : return (type*) Dictionary::Insert(&h, (void*) val); \
205 : : } \
206 : : type* Insert(HashKey* key, type* val) \
207 : : { return (type*) Dictionary::Insert(key, (void*) val); }\
208 : : type* NthEntry(int n) const \
209 : : { return (type*) Dictionary::NthEntry(n); } \
210 : : type* NthEntry(int n, const char*& key) const \
211 : : { \
212 : : int key_len; \
213 : : return (type*) Dictionary::NthEntry(n, (const void*&) key,\
214 : : key_len); \
215 : : } \
216 : : type* NextEntry(IterCookie*& cookie) const \
217 : : { \
218 : : HashKey* h; \
219 : : return (type*) Dictionary::NextEntry(h, cookie, 0); \
220 : : } \
221 : : type* NextEntry(HashKey*& h, IterCookie*& cookie) const \
222 : : { return (type*) Dictionary::NextEntry(h, cookie, 1); } \
223 : : type* RemoveEntry(const HashKey* key) \
224 : : { return (type*) Remove(key->Key(), key->Size(), \
225 : : key->Hash()); } \
226 : : }
227 : :
228 : : #endif
|
