1 | /* |
---|
2 | * ====================================================================== |
---|
3 | * Rappture::Lookup<valType> |
---|
4 | * Rappture::Lookup2<keyType,valType> |
---|
5 | * |
---|
6 | * AUTHOR: Michael McLennan, Purdue University |
---|
7 | * Copyright (c) 2004-2012 HUBzero Foundation, LLC |
---|
8 | * ---------------------------------------------------------------------- |
---|
9 | * See the file "license.terms" for information on usage and |
---|
10 | * redistribution of this file, and for a DISCLAIMER OF ALL WARRANTIES. |
---|
11 | * ====================================================================== |
---|
12 | * |
---|
13 | * This code is based on the Tcl_HashTable facility included in the |
---|
14 | * Tcl source release, which includes the following copyright: |
---|
15 | * |
---|
16 | * Copyright (c) 1987-1994 The Regents of the University of California. |
---|
17 | * Copyright (c) 1993-1996 Lucent Technologies. |
---|
18 | * Copyright (c) 1994-1998 Sun Microsystems, Inc. |
---|
19 | * Copyright (c) 1998-2000 by Scriptics Corporation. |
---|
20 | * |
---|
21 | * This software is copyrighted by the Regents of the University of |
---|
22 | * California, Sun Microsystems, Inc., Scriptics Corporation, |
---|
23 | * and other parties. The following terms apply to all files associated |
---|
24 | * with the software unless explicitly disclaimed in individual files. |
---|
25 | * |
---|
26 | * The authors hereby grant permission to use, copy, modify, distribute, |
---|
27 | * and license this software and its documentation for any purpose, provided |
---|
28 | * that existing copyright notices are retained in all copies and that this |
---|
29 | * notice is included verbatim in any distributions. No written agreement, |
---|
30 | * license, or royalty fee is required for any of the authorized uses. |
---|
31 | * Modifications to this software may be copyrighted by their authors |
---|
32 | * and need not follow the licensing terms described here, provided that |
---|
33 | * the new terms are clearly indicated on the first page of each file where |
---|
34 | * they apply. |
---|
35 | * |
---|
36 | * IN NO EVENT SHALL THE AUTHORS OR DISTRIBUTORS BE LIABLE TO ANY PARTY |
---|
37 | * FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES |
---|
38 | * ARISING OUT OF THE USE OF THIS SOFTWARE, ITS DOCUMENTATION, OR ANY |
---|
39 | * DERIVATIVES THEREOF, EVEN IF THE AUTHORS HAVE BEEN ADVISED OF THE |
---|
40 | * POSSIBILITY OF SUCH DAMAGE. |
---|
41 | * |
---|
42 | * THE AUTHORS AND DISTRIBUTORS SPECIFICALLY DISCLAIM ANY WARRANTIES, |
---|
43 | * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY, |
---|
44 | * FITNESS FOR A PARTICULAR PURPOSE, AND NON-INFRINGEMENT. THIS SOFTWARE |
---|
45 | * IS PROVIDED ON AN "AS IS" BASIS, AND THE AUTHORS AND DISTRIBUTORS HAVE |
---|
46 | * NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR |
---|
47 | * MODIFICATIONS. |
---|
48 | * |
---|
49 | * GOVERNMENT USE: If you are acquiring this software on behalf of the |
---|
50 | * U.S. government, the Government shall have only "Restricted Rights" |
---|
51 | * in the software and related documentation as defined in the Federal |
---|
52 | * Acquisition Regulations (FARs) in Clause 52.227.19 (c) (2). If you |
---|
53 | * are acquiring the software on behalf of the Department of Defense, the |
---|
54 | * software shall be classified as "Commercial Computer Software" and the |
---|
55 | * Government shall have only "Restricted Rights" as defined in Clause |
---|
56 | * 252.227-7013 (c) (1) of DFARs. Notwithstanding the foregoing, the |
---|
57 | * authors grant the U.S. Government and others acting in its behalf |
---|
58 | * permission to use and distribute the software in accordance with the |
---|
59 | * terms specified in this license. |
---|
60 | * ====================================================================== |
---|
61 | */ |
---|
62 | #ifndef RAPPTURE_DICTIONARY_H |
---|
63 | #define RAPPTURE_DICTIONARY_H |
---|
64 | |
---|
65 | #include "rappture.h" |
---|
66 | #include <stddef.h> |
---|
67 | |
---|
68 | #define RP_DICT_MIN_SIZE 4 |
---|
69 | |
---|
70 | namespace Rappture { |
---|
71 | |
---|
72 | class LookupCore; // foward declaration |
---|
73 | |
---|
74 | /** |
---|
75 | * Represents one entry within a lookup object, cast in terms |
---|
76 | * of void pointers and data sizes, so that the official, templated |
---|
77 | * version of the class can be lean and mean. |
---|
78 | */ |
---|
79 | struct LookupEntryCore { |
---|
80 | LookupEntryCore *nextPtr; // pointer to next entry in this bucket |
---|
81 | LookupCore *dictPtr; // pointer to lookup containing entry |
---|
82 | LookupEntryCore **bucketPtr; // pointer to bucket containing this entry |
---|
83 | |
---|
84 | void *valuePtr; // value within this hash entry |
---|
85 | |
---|
86 | union { |
---|
87 | void *ptrValue; // size of a pointer |
---|
88 | int words[1]; // multiple integer words for the key |
---|
89 | char string[4]; // first part of string value for key |
---|
90 | } key; // memory can be oversized if more |
---|
91 | // space is needed for words/string |
---|
92 | // MUST BE THE LAST FIELD IN THIS RECORD! |
---|
93 | }; |
---|
94 | |
---|
95 | /** |
---|
96 | * This is the functional core of a lookup object, cast in terms |
---|
97 | * of void pointers and data sizes, so that the official, templated |
---|
98 | * version of the class can be lean and mean. |
---|
99 | */ |
---|
100 | class LookupCore { |
---|
101 | public: |
---|
102 | LookupCore(size_t keySize); |
---|
103 | ~LookupCore(); |
---|
104 | |
---|
105 | LookupEntryCore* get(void* key, int* newEntryPtr); |
---|
106 | LookupEntryCore* find(void* key); |
---|
107 | LookupEntryCore* erase(LookupEntryCore* entryPtr); |
---|
108 | LookupEntryCore* next(LookupEntryCore* entryPtr, int& bucketNum); |
---|
109 | std::string stats(); |
---|
110 | |
---|
111 | private: |
---|
112 | /// Not allowed -- copy Lookup at higher level |
---|
113 | LookupCore(const LookupCore& dcore) { assert(0); } |
---|
114 | |
---|
115 | /// Not allowed -- copy Lookup at higher level |
---|
116 | LookupCore& operator=(const LookupCore& dcore) { assert(0); } |
---|
117 | |
---|
118 | // utility functions |
---|
119 | void _rebuildBuckets(); |
---|
120 | unsigned int _hashIndex(void* key); |
---|
121 | |
---|
122 | /// Size of the key in words, or 0 for (const char*) string keys. |
---|
123 | int _keySize; |
---|
124 | |
---|
125 | /// Pointer to array of hash buckets. |
---|
126 | LookupEntryCore **_buckets; |
---|
127 | |
---|
128 | /// Built-in storage for small hash tables. |
---|
129 | LookupEntryCore *_staticBuckets[RP_DICT_MIN_SIZE]; |
---|
130 | |
---|
131 | /// Total number of entries in the lookup. |
---|
132 | int _numEntries; |
---|
133 | |
---|
134 | /// Number of buckets currently allocated at _buckets. |
---|
135 | int _numBuckets; |
---|
136 | |
---|
137 | /// Enlarge table when numEntries gets to be this large. |
---|
138 | int _rebuildSize; |
---|
139 | |
---|
140 | /// Shift count used in hashing function. |
---|
141 | int _downShift; |
---|
142 | |
---|
143 | /// Mask value used in hashing function. |
---|
144 | int _mask; |
---|
145 | }; |
---|
146 | |
---|
147 | /** |
---|
148 | * This represents a single entry within a lookup object. It is |
---|
149 | * used to access values within the lookup, or as an iterator |
---|
150 | * that traverses the lookup. |
---|
151 | */ |
---|
152 | template <class KeyType, class ValType> |
---|
153 | class LookupEntry2 { |
---|
154 | public: |
---|
155 | LookupEntry2(LookupCore* corePtr, LookupEntryCore* entryPtr=NULL); |
---|
156 | LookupEntry2(const LookupEntry2& entry); |
---|
157 | LookupEntry2& operator=(const LookupEntry2& entry); |
---|
158 | ~LookupEntry2(); |
---|
159 | |
---|
160 | int isNull() const; |
---|
161 | KeyType& key(); |
---|
162 | ValType& value(); |
---|
163 | LookupEntry2& next(); |
---|
164 | LookupEntry2& erase(); |
---|
165 | |
---|
166 | private: |
---|
167 | LookupCore* _corePtr; |
---|
168 | LookupEntryCore* _entryPtr; |
---|
169 | int _bucketNum; |
---|
170 | }; |
---|
171 | |
---|
172 | template <class KeyType, class ValType> |
---|
173 | LookupEntry2<KeyType,ValType>::LookupEntry2(LookupCore* corePtr, |
---|
174 | LookupEntryCore* entryPtr) |
---|
175 | : _corePtr(corePtr), |
---|
176 | _entryPtr(entryPtr), |
---|
177 | _bucketNum(0) |
---|
178 | { |
---|
179 | } |
---|
180 | |
---|
181 | template <class KeyType, class ValType> |
---|
182 | LookupEntry2<KeyType,ValType>::LookupEntry2(const LookupEntry2 &entry) |
---|
183 | : _corePtr(entry._corePtr), |
---|
184 | _entryPtr(entry._entryPtr), |
---|
185 | _bucketNum(entry._bucketNum) |
---|
186 | { |
---|
187 | } |
---|
188 | |
---|
189 | template <class KeyType, class ValType> |
---|
190 | LookupEntry2<KeyType,ValType>& |
---|
191 | LookupEntry2<KeyType,ValType>::operator=(const LookupEntry2 &entry) |
---|
192 | { |
---|
193 | _corePtr = entry._corePtr; |
---|
194 | _entryPtr = entry._entryPtr; |
---|
195 | _bucketNum = entry._bucketNum; |
---|
196 | return *this; |
---|
197 | } |
---|
198 | |
---|
199 | template <class KeyType, class ValType> |
---|
200 | LookupEntry2<KeyType,ValType>::~LookupEntry2() |
---|
201 | { |
---|
202 | } |
---|
203 | |
---|
204 | template <class KeyType, class ValType> |
---|
205 | int |
---|
206 | LookupEntry2<KeyType,ValType>::isNull() const |
---|
207 | { |
---|
208 | return (_entryPtr == NULL); |
---|
209 | } |
---|
210 | |
---|
211 | template <class KeyType, class ValType> |
---|
212 | KeyType& |
---|
213 | LookupEntry2<KeyType,ValType>::key() |
---|
214 | { |
---|
215 | return *(KeyType*)(_entryPtr->key.string); |
---|
216 | } |
---|
217 | |
---|
218 | template <class KeyType, class ValType> |
---|
219 | ValType& |
---|
220 | LookupEntry2<KeyType,ValType>::value() |
---|
221 | { |
---|
222 | if (sizeof(ValType) > sizeof(_entryPtr->valuePtr)) { |
---|
223 | return *static_cast<ValType*>(_entryPtr->valuePtr); |
---|
224 | } |
---|
225 | return *(ValType*)(&_entryPtr->valuePtr); |
---|
226 | } |
---|
227 | |
---|
228 | template <class KeyType, class ValType> |
---|
229 | LookupEntry2<KeyType,ValType>& |
---|
230 | LookupEntry2<KeyType,ValType>::next() |
---|
231 | { |
---|
232 | _entryPtr = _corePtr->next(_entryPtr, _bucketNum); |
---|
233 | return *this; |
---|
234 | } |
---|
235 | |
---|
236 | template <class KeyType, class ValType> |
---|
237 | LookupEntry2<KeyType,ValType>& |
---|
238 | LookupEntry2<KeyType,ValType>::erase() |
---|
239 | { |
---|
240 | if (_entryPtr != NULL) { |
---|
241 | // delete the value |
---|
242 | if (_entryPtr->valuePtr |
---|
243 | && sizeof(ValType) > sizeof(_entryPtr->valuePtr)) { |
---|
244 | delete static_cast<ValType*>(_entryPtr->valuePtr); |
---|
245 | } |
---|
246 | // delete the slot |
---|
247 | _entryPtr = _corePtr->erase(_entryPtr); |
---|
248 | } |
---|
249 | |
---|
250 | if (_entryPtr == NULL) { |
---|
251 | // at the end of this bucket? then move on to next one |
---|
252 | _corePtr->next(_entryPtr, _bucketNum); |
---|
253 | } |
---|
254 | return *this; |
---|
255 | } |
---|
256 | |
---|
257 | /** |
---|
258 | * This is a lookup object or associative array. It is a hash |
---|
259 | * table that uniquely maps a key to a value. The memory for values |
---|
260 | * added to lookup is managed by the lookup. When a lookup |
---|
261 | * is deleted, its internal values are cleaned up automatically. |
---|
262 | */ |
---|
263 | template <class KeyType, class ValType> |
---|
264 | class Lookup2 { |
---|
265 | public: |
---|
266 | Lookup2(int size=-1); |
---|
267 | Lookup2(const Lookup2& dict); |
---|
268 | Lookup2& operator=(const Lookup2& dict); |
---|
269 | ~Lookup2(); |
---|
270 | |
---|
271 | LookupEntry2<KeyType,ValType> get(const KeyType& key, int* newEntryPtr); |
---|
272 | LookupEntry2<KeyType,ValType> find(const KeyType& key) const; |
---|
273 | ValType& operator[](const KeyType& key); |
---|
274 | LookupEntry2<KeyType,ValType> erase(const KeyType& key); |
---|
275 | void clear(); |
---|
276 | |
---|
277 | LookupEntry2<KeyType,ValType> first(); |
---|
278 | |
---|
279 | std::string stats(); |
---|
280 | |
---|
281 | private: |
---|
282 | LookupCore* _corePtr; |
---|
283 | }; |
---|
284 | |
---|
285 | template <class KeyType, class ValType> |
---|
286 | Lookup2<KeyType,ValType>::Lookup2(int size) |
---|
287 | { |
---|
288 | _corePtr = new LookupCore( (size >= 0) ? size : sizeof(KeyType) ); |
---|
289 | } |
---|
290 | |
---|
291 | template <class KeyType, class ValType> |
---|
292 | Lookup2<KeyType,ValType>::Lookup2(const Lookup2<KeyType,ValType>& dict) |
---|
293 | { |
---|
294 | _corePtr = new LookupCore(sizeof(KeyType)); |
---|
295 | |
---|
296 | LookupEntry2<KeyType,ValType> entry; |
---|
297 | for (entry=dict.first(); !entry.isNull(); entry.next()) { |
---|
298 | get(entry.key(), NULL).value() = entry.value(); |
---|
299 | } |
---|
300 | } |
---|
301 | |
---|
302 | template <class KeyType, class ValType> |
---|
303 | Lookup2<KeyType,ValType>& |
---|
304 | Lookup2<KeyType,ValType>::operator=(const Lookup2<KeyType,ValType>& dict) |
---|
305 | { |
---|
306 | #ifdef notdef |
---|
307 | /* How did this ever compile? --gah */ |
---|
308 | _corePtr->clear(); |
---|
309 | #endif |
---|
310 | |
---|
311 | LookupEntry2<KeyType,ValType> entry; |
---|
312 | for (entry=dict.first(); !entry.isNull(); entry.next()) { |
---|
313 | get(entry.key(), NULL).value() = entry.value(); |
---|
314 | } |
---|
315 | } |
---|
316 | |
---|
317 | template <class KeyType, class ValType> |
---|
318 | Lookup2<KeyType,ValType>::~Lookup2() |
---|
319 | { |
---|
320 | clear(); |
---|
321 | delete _corePtr; |
---|
322 | } |
---|
323 | |
---|
324 | template <class KeyType, class ValType> |
---|
325 | void |
---|
326 | Lookup2<KeyType,ValType>::clear() |
---|
327 | { |
---|
328 | LookupEntry2<KeyType,ValType> entry = first(); |
---|
329 | while (!entry.isNull()) { |
---|
330 | entry.erase(); |
---|
331 | } |
---|
332 | } |
---|
333 | |
---|
334 | template <class KeyType, class ValType> |
---|
335 | LookupEntry2<KeyType,ValType> |
---|
336 | Lookup2<KeyType,ValType>::get(const KeyType& key, int* newEntryPtr) |
---|
337 | { |
---|
338 | LookupEntryCore* entryPtr = _corePtr->get((void*)&key, newEntryPtr); |
---|
339 | if (entryPtr->valuePtr == NULL |
---|
340 | && sizeof(ValType) > sizeof(entryPtr->valuePtr)) { |
---|
341 | entryPtr->valuePtr = new ValType; |
---|
342 | } |
---|
343 | return LookupEntry2<KeyType,ValType>(_corePtr, entryPtr); |
---|
344 | } |
---|
345 | |
---|
346 | template <class KeyType, class ValType> |
---|
347 | ValType& |
---|
348 | Lookup2<KeyType,ValType>::operator[](const KeyType& key) |
---|
349 | { |
---|
350 | LookupEntry2<KeyType,ValType> entry = get(key, NULL); |
---|
351 | return entry.value(); |
---|
352 | } |
---|
353 | |
---|
354 | template <class KeyType, class ValType> |
---|
355 | LookupEntry2<KeyType,ValType> |
---|
356 | Lookup2<KeyType,ValType>::first() |
---|
357 | { |
---|
358 | LookupEntry2<KeyType,ValType> entry(_corePtr); |
---|
359 | return entry.next(); |
---|
360 | } |
---|
361 | |
---|
362 | template <class KeyType, class ValType> |
---|
363 | std::string |
---|
364 | Lookup2<KeyType,ValType>::stats() |
---|
365 | { |
---|
366 | return _corePtr->stats(); |
---|
367 | } |
---|
368 | |
---|
369 | template <class ValType> |
---|
370 | class LookupEntry : public LookupEntry2<const char*,ValType> { |
---|
371 | public: |
---|
372 | LookupEntry(LookupCore* corePtr, LookupEntryCore* entryPtr=NULL); |
---|
373 | LookupEntry(const LookupEntry2<const char*,ValType>& entry); |
---|
374 | }; |
---|
375 | |
---|
376 | template <class ValType> |
---|
377 | LookupEntry<ValType>::LookupEntry(LookupCore* corePtr, |
---|
378 | LookupEntryCore* entryPtr) |
---|
379 | : LookupEntry2<const char*,ValType>(corePtr, entryPtr) |
---|
380 | { |
---|
381 | } |
---|
382 | |
---|
383 | template <class ValType> |
---|
384 | LookupEntry<ValType>::LookupEntry( |
---|
385 | const LookupEntry2<const char*,ValType>& entry) |
---|
386 | : LookupEntry2<const char*,ValType>(entry) |
---|
387 | { |
---|
388 | } |
---|
389 | |
---|
390 | template <class ValType> |
---|
391 | class Lookup : public Lookup2<const char*,ValType> { |
---|
392 | public: |
---|
393 | Lookup(); |
---|
394 | }; |
---|
395 | |
---|
396 | template <class ValType> |
---|
397 | Lookup<ValType>::Lookup() |
---|
398 | : Lookup2<const char*,ValType>(0) |
---|
399 | { |
---|
400 | } |
---|
401 | |
---|
402 | } // namespace Rappture |
---|
403 | |
---|
404 | #endif |
---|