source: trunk/include/core/RpDict.h @ 19

Last change on this file since 19 was 19, checked in by dkearney, 16 years ago

initial submission of the Rappture Core components and language bindings

  • Property svn:executable set to *
File size: 9.7 KB
Line 
1#include <iostream>
2#include <cassert>
3#include <string>
4#include <stdlib.h>
5#include <errno.h>
6#include <malloc.h>
7
8#ifndef _RpDICT_H
9#define _RpDICT_H
10
11/**************************************************************************/
12
13
14/**************************************************************************/
15
16template <typename KeyType, typename ValType> class RpDict;
17template <typename KeyType, typename ValType> class RpDictEntry;
18
19/**************************************************************************/
20
21template <typename KeyType, typename ValType> class RpDictIterator
22{
23
24    public:
25
26        // public data members
27
28        // public member functions
29
30        // retrieve the table the iterator is iterating
31        // virtual RpDict<KeyType,ValType>& getTable();
32
33        // send the search iterator to the beginning of the hash table
34        virtual RpDictEntry<KeyType,ValType>* first();
35
36        // send the search iterator to the next element of the hash table
37        virtual RpDictEntry<KeyType,ValType>* next();
38/*
39        RpDictIterator(RpDict* table_Ptr)
40            : tablePtr( (RpDict&) *table_Ptr),
41              srchNextEntryPtr(NULL),
42              srchNextIndex(0)
43        {
44        }
45*/
46        RpDictIterator(RpDict<KeyType,ValType>& table_Ptr)
47            : tablePtr(table_Ptr),
48              srchNextIndex(0),
49              srchNextEntryPtr(NULL)
50        {
51        }
52
53        // copy constructor
54        RpDictIterator(RpDictIterator<KeyType,ValType>& iterRef)
55            : tablePtr(iterRef.tablePtr),
56              srchNextIndex(iterRef.srchNextIndex),
57              srchNextEntryPtr(iterRef.srchNextEntryPtr)
58        {
59        }
60
61        // destructor
62
63    private:
64
65        RpDict<KeyType,ValType>&
66            tablePtr;                   /* pointer to the table we want to
67                                         * iterate */
68        int srchNextIndex;              /* Index of next bucket to be
69                                         * enumerated after present one. */
70        RpDictEntry<KeyType,ValType>*
71            srchNextEntryPtr;           /* Next entry to be enumerated in the
72                                         * the current bucket. */
73
74};
75
76
77template <typename KeyType, typename ValType> class RpDictEntry
78{
79    public:
80
81        // public member functions
82
83        operator int() const;
84        // operator==(const RpDictEntry& entry) const;
85        //
86        //operator!=(const RpDictEntry& lhs, const RpDictEntry& rhs) const
87        //{
88        //    if (lhs.key != rhs.key)
89        //}
90        const KeyType* getKey() const;
91        const ValType* getValue() const;
92        // const void* setValue(const void* value);
93        const ValType* setValue(const ValType& value);
94
95        // erases this entry from its table
96        void erase();
97
98        // template <KeyType,ValType> friend class RpDict;
99        // template <KeyType,ValType> friend class RpDictIterator;
100
101        friend class RpDict<KeyType,ValType>;
102        friend class RpDictIterator<KeyType,ValType>;
103
104        // no_arg constructor
105        // use the key and clientData's default [no-arg] constructor
106        RpDictEntry()
107           : nextPtr (NULL),
108             tablePtr (NULL),
109             hash (0) // ,
110             // clientData (),
111             // key ()
112        {
113        }
114
115        // one-arg constructor
116        // maybe get rid of this one?
117        RpDictEntry(KeyType newKey)
118           : nextPtr    (NULL),
119             tablePtr   (NULL),
120             hash       (0),
121             clientData (NULL),
122             key        (newKey)
123        {
124        }
125
126        // two-arg constructor
127        RpDictEntry(KeyType newKey, ValType newVal)
128           : nextPtr    (NULL),
129             tablePtr   (NULL),
130             hash       (0),
131             clientData (newVal),
132             key        (newKey)
133        {
134        }
135
136/*
137        RpDictEntry(KeyType* newKey, ValType* newVal)
138           : nextPtr    (NULL),
139             tablePtr   (NULL),
140             hash       (0),
141             clientData (*newVal),
142             key        (*newKey)
143        {
144        }
145
146        RpDictEntry(KeyType newKey, RpDict* table)
147           : nextPtr    (NULL),
148             tablePtr   (table),
149             hash       (0),
150             // clientData (NULL),
151             key        (newKey)
152        {
153        }
154*/
155        // copy constructor
156        RpDictEntry (const RpDictEntry<KeyType,ValType>& entry)
157        {
158            nextPtr     = entry.nextPtr;
159            tablePtr    = entry.tablePtr;
160            hash        = entry.hash;
161            clientData  = (ValType) entry.getValue();
162            key         = (KeyType) entry.getKey();
163        }
164
165    private:
166
167        // private data members
168        RpDictEntry<KeyType,ValType>*
169            nextPtr;                /* Pointer to next entry in this
170                                     * hash bucket, or NULL for end of
171                                     * chain. */
172
173        RpDict<KeyType,ValType>
174            *tablePtr;              /* Pointer to table containing entry. */
175
176        unsigned int hash;          /* Hash value. */
177
178        ValType clientData;        /* Application stores something here
179                                     * with Tcl_SetHashValue. */
180
181        KeyType key;               /* entry key */
182
183
184
185       
186};
187
188
189template <typename KeyType, typename ValType> class RpDict
190{
191    public:
192
193       
194        // functionality for the user to access/adjust data members
195       
196        // checks table size
197        virtual const int size() const;
198
199        // insert new object into table
200        // returns 0 on success (object inserted or already exists)
201        // returns !0 on failure (object cannot be inserted or dne)
202        //
203        virtual RpDict<KeyType,ValType>&
204                        set(    KeyType& key,
205                                ValType& value,
206                                int *newPtr=NULL );   
207
208        // find an RpUnits object that should exist in RpUnitsTable
209        //
210        virtual RpDictEntry<KeyType,ValType>&
211                        find( KeyType& key );
212
213        virtual RpDictEntry<KeyType,ValType>& operator[]( KeyType& key)
214        {
215            return find(key);
216        }
217
218        // clear the entire table
219        // iterate through the table and call erase on each element
220        virtual RpDict<KeyType,ValType>& clear();
221
222        // get the nullEntry hash entry for initialization of references
223        virtual RpDictEntry<KeyType,ValType>& getNullEntry();
224
225        // template <KeyType, ValType> friend class RpDictEntry;
226        // template <KeyType, ValType> friend class RpDictIterator;
227
228        friend class RpDictEntry<KeyType, ValType>;
229        friend class RpDictIterator<KeyType, ValType>;
230
231        // default constructor
232        RpDict ()
233            : SMALL_RP_DICT_SIZE(4),
234              REBUILD_MULTIPLIER(3),
235              buckets(staticBuckets),
236              numBuckets(SMALL_RP_DICT_SIZE),
237              numEntries(0),
238              rebuildSize(SMALL_RP_DICT_SIZE*REBUILD_MULTIPLIER),
239              downShift(28),
240              mask(3)
241        {
242
243            staticBuckets[0] = staticBuckets[1] = 0;
244            staticBuckets[2] = staticBuckets[3] = 0;
245
246            // setup a dummy entry of NULL
247            nullEntry = new RpDictEntry<KeyType,ValType>();
248
249            // std::cout << "inside RpDict Constructor" << std::endl;
250
251        }
252       
253        // copy constructor
254        // RpDict (const RpDict& dict);
255
256        // assignment operator
257        // RpDict& operator=(const RpDict& dict);
258
259        // destructor
260        virtual ~RpDict()
261        {
262            // probably need to delete all the entries as well
263            delete nullEntry;
264        }
265        // make sure to go through the hash table and free all RpDictEntries
266        // because the space is malloc'd in RpDict::set()
267
268
269    private:
270        const int SMALL_RP_DICT_SIZE;
271        const int REBUILD_MULTIPLIER;
272       
273        RpDictEntry<KeyType,ValType>
274                    **buckets;        /* Pointer to bucket array.  Each
275                                       * element points to first entry in
276                                       * bucket's hash chain, or NULL. */
277        // RpDictEntry *staticBuckets[SMALL_RP_DICT_SIZE];
278        RpDictEntry<KeyType,ValType>
279                    *staticBuckets[4];
280                                      /* Bucket array used for small tables
281                                       * (to avoid mallocs and frees). */
282        int numBuckets;               /* Total number of buckets allocated
283                                       * at **bucketPtr. */
284        int numEntries;               /* Total number of entries present
285                                       * in table. */
286        int rebuildSize;              /* Enlarge table when numEntries gets
287                                       * to be this large. */
288        int downShift;                /* Shift count used in hashing
289                                       * function.  Designed to use high-
290                                       * order bits of randomized keys. */
291        int mask;                     /* Mask value used in hashing
292                                       * function. */
293        RpDictEntry<KeyType,ValType>
294                    *nullEntry;   /* if not const, compiler complains*/
295
296
297
298        // private member fxns
299
300        // static void RpDict::RebuildTable ();
301        void RebuildTable ();
302
303        unsigned int hashFxn(const void* keyPtr) const;
304        unsigned int hashFxn(std::string* keyPtr) const;
305        unsigned int hashFxn(char* keyPtr) const;
306
307        int randomIndex(unsigned int hash);
308};
309
310
311/*--------------------------------------------------------------------------*/
312/*--------------------------------------------------------------------------*/
313
314#include "../src/RpDict.cc"
315
316#endif
Note: See TracBrowser for help on using the repository browser.