source: trunk/src/core/RpDict.cc @ 20

Last change on this file since 20 was 20, checked in by dkearney, 17 years ago

initial submission of the Rappture Core components and language bindings

File size: 16.7 KB
Line 
1/*
2#ifndef _RpDICT_H
3    #include "../include/RpDict.h"
4#endif
5*/
6
7/**************************************************************************/
8
9
10// public RpDict member functions
11
12
13/**************************************************************************
14 *
15 * int RpDict::size()
16 *  retrieve the size of the structure
17 *
18 * Results:
19 *  Returns size of the hash table
20 *
21 * Side Effects:
22 *  none.
23 *
24 *
25 *************************************************************************/
26
27template <typename KeyType, typename ValType>
28const int
29RpDict<KeyType,ValType>::size() const
30{
31    return numEntries;
32}
33
34
35/**************************************************************************
36 *
37 * RpDict::set()
38 *  checks to make sure the table exists.
39 *  places a key/value pair into the hash table
40 *
41 * Results:
42 *  Returns a reference to the RpDict object allowing the user to chain
43 *  together different commands such as
44 *      rpdict_obj.set(key).find(a).erase(a);
45 *
46 * Side Effects:
47 *  if successful, the hash table will have a new entry
48 *
49 *
50 *************************************************************************/
51template <typename KeyType, typename ValType>
52RpDict<KeyType,ValType>&
53RpDict<KeyType,ValType>::set(   KeyType& key,
54                                ValType& value,
55                                int* newPtr)
56{
57    RpDictEntry<KeyType,ValType> *hPtr;
58    unsigned int hash;
59    int index;
60
61    assert(&key);
62    assert(&value);
63   
64    // take care of the case where we are creating a NULL key entry.
65    if (&key) {
66        hash = (unsigned int) hashFxn(&key);
67    }
68    else {
69        hash = 0;
70    }
71
72    index = randomIndex(hash);
73
74    /*
75     * Search all of the entries in the appropriate bucket.
76     */
77    for (hPtr = buckets[index]; hPtr != NULL; hPtr = hPtr->nextPtr) {
78        if (hash != (unsigned int) hPtr->hash) {
79            continue;
80        }
81        // if element already exists in hash, it should not be re-entered
82        if (key == *(hPtr->getKey())){
83
84            // adjust the new flag if it was provided
85            if (newPtr) {
86                *newPtr = 0;
87            }
88
89            // adjust the value if it was provided
90            // memory management is left as an exercize for the caller
91            if (&value) {
92                hPtr->setValue(value);
93            }
94           
95            // return a reference to the dictionary object
96            return *this;
97        }
98    }
99
100    /*
101     * Entry not found.  Add a new one to the bucket.
102     */
103
104    if (newPtr) {
105        *newPtr = 1;
106    }
107
108    hPtr = new RpDictEntry<KeyType,ValType>(key,value);
109    // hPtr->setValue(value);
110    //
111    // this is just a pointer that was allocated on the heap
112    // it wont stick with the RpDictEntry after the fxn exits...
113    // need to fix still.
114    hPtr->tablePtr = this;
115    hPtr->hash = hash;
116    hPtr->nextPtr = buckets[index];
117    buckets[index] = hPtr;
118    numEntries++;
119
120    /*
121     * If the table has exceeded a decent size, rebuild it with many
122     * more buckets.
123     */
124
125    if (numEntries >= rebuildSize) {
126        RebuildTable();
127    }
128
129    // return a reference to the original object
130    return *this;
131}
132
133
134/* 
135 *----------------------------------------------------------------------
136 * 
137 *  RpDict::find(const char *key)
138 * 
139 *  Given a hash table find the entry with a matching key.
140 * 
141 * Results:
142 *  The return value is a token for the matching entry in the
143 *  hash table, or NULL if there was no matching entry.
144 * 
145 * Side effects:
146 *  None.
147 *         
148 *----------------------------------------------------------------------
149 */     
150       
151template <typename KeyType, typename ValType>
152RpDictEntry<KeyType,ValType>&
153RpDict<KeyType,ValType>::find(KeyType& key)
154{       
155    RpDictEntry<KeyType,ValType> *hPtr;
156    unsigned int hash;
157    int index;
158
159    assert(&key);
160
161    // take care of the case where we are creating a NULL key entry.
162    if (&key) {
163        hash = (unsigned int) hashFxn(&key);
164    }
165    else {
166        hash = 0;
167    }
168
169    index = randomIndex(hash);
170
171    /*
172     * Search all of the entries in the appropriate bucket.
173     */
174
175    for (hPtr = buckets[index]; hPtr != NULL; hPtr = hPtr->nextPtr) {
176        if (hash != (unsigned int) hPtr->hash) {
177            continue;
178        }
179        if (key == *(hPtr->getKey())) {
180            // return a reference to the found object
181            return *hPtr;
182        }
183    }
184
185    // return a reference to the null object
186    // find is not supposed to return a const, but i dont want the user
187    // changing this entry's data members... what to do?
188    return *nullEntry;
189
190}
191
192
193
194/**************************************************************************
195 *
196 * virtual RpDict& RpDictIterator::getTable()
197 *  send the search iterator to the beginning of the hash table
198 *
199 * Results:
200 *  returns pointer to the first hash entry of the hash table.
201 *
202 * Side Effects:
203 *  moves iterator to the beginning of the hash table.
204 *
205 *
206 *************************************************************************/
207/*
208template <typename KeyType,typename ValType>
209RpDict<KeyType,ValType>&
210RpDictIterator<KeyType,ValType>::getTable()
211{
212    return tablePtr;
213}
214*/
215
216/**************************************************************************
217 *
218 * virtual RpDictEntry& RpDict::first()
219 *  send the search iterator to the beginning of the hash table
220 *
221 * Results:
222 *  returns pointer to the first hash entry of the hash table.
223 *
224 * Side Effects:
225 *  moves iterator to the beginning of the hash table.
226 *
227 *
228 *************************************************************************/
229template <typename KeyType,typename ValType>
230RpDictEntry<KeyType,ValType>*
231RpDictIterator<KeyType,ValType>::first()
232{
233    srchNextIndex = 0;
234    srchNextEntryPtr = NULL;
235    return next();
236}
237
238/**************************************************************************
239 *
240 * Tcl_HashEntry * RpDict::next()
241 *  send the search iterator to the next entry of the hash table
242 *
243 * Results:
244 *  returns pointer to the next hash entry of the hash table.
245 *  if iterator is at the end of the hash table, NULL is returned
246 *  and the iterator is left at the end of the hash table.
247 *
248 * Side Effects:
249 *  moves iterator to the next entry of the hash table if it exists.
250 *
251 *
252 *************************************************************************/
253
254template <typename KeyType,typename ValType>
255RpDictEntry<KeyType,ValType>*
256RpDictIterator<KeyType,ValType>::next()
257{
258    RpDictEntry<KeyType,ValType>* hPtr;
259
260    while (srchNextEntryPtr == NULL) {
261        if (srchNextIndex >= tablePtr.numBuckets) {
262            return NULL;
263        }
264        srchNextEntryPtr = tablePtr.buckets[srchNextIndex];
265        srchNextIndex++;
266    }
267    hPtr = srchNextEntryPtr;
268    srchNextEntryPtr = hPtr->nextPtr;
269
270    return hPtr;
271}
272
273/**************************************************************************
274 *
275 * RpDict & clear()
276 *  iterate through the table and call erase on each element
277 *
278 * Results:
279 *  empty hash table
280 *
281 * Side Effects:
282 *  every element of the hash table will be erased.
283 *
284 *
285 *************************************************************************/
286template <typename KeyType, typename ValType>
287RpDict<KeyType,ValType>&
288RpDict<KeyType,ValType>::clear()
289{
290    RpDictEntry<KeyType,ValType> *hPtr;
291    RpDictIterator<KeyType,ValType> iter((RpDict&)*this);
292
293    hPtr = iter.first();
294
295    while (hPtr) {
296        hPtr->erase();
297        hPtr = iter.next();
298    }
299
300    return *this;
301}
302
303/**************************************************************************
304 *
305 * RpDict & getNullEntry()
306 *  get the nullEntry hash entry for initialization of references
307 * 
308 *
309 * Results:
310 *  nullEntry RpDictEntry related to this dictionary is returned
311 *
312 * Side Effects:
313 *  none
314 *
315 *
316 *************************************************************************/
317template <typename KeyType, typename ValType>
318RpDictEntry<KeyType,ValType>&
319RpDict<KeyType,ValType>::getNullEntry()
320{
321    return *nullEntry;
322}
323
324
325/*
326 *----------------------------------------------------------------------
327 *
328 * void RpDictEntry::erase()
329 *
330 *  Remove a single entry from a hash table.
331 *
332 * Results:
333 *  None.
334 *
335 * Side effects:
336 *  The entry given by entryPtr is deleted from its table and
337 *  should never again be used by the caller.  It is up to the
338 *  caller to free the clientData field of the entry, if that
339 *  is relevant.
340 *
341 *----------------------------------------------------------------------
342 */
343
344template <typename KeyType, typename ValType>
345void 
346RpDictEntry<KeyType,ValType>::erase()
347{   
348    RpDictEntry<KeyType,ValType> *prevPtr;
349    RpDictEntry<KeyType,ValType> **bucketPtr;
350    int index = 0;
351
352    // check to see if the object is associated with a table
353    // if object is not associated with a table, there is no
354    // need to try to remove it from the table.
355    if (tablePtr) {
356
357        index = tablePtr->randomIndex(hash);
358   
359        // calculate which bucket the entry should be in.
360        bucketPtr = &(tablePtr->buckets[index]);
361
362        // remove the entry from the buckets
363        //
364        // if entry is the first entry in the bucket
365        // move the bucket to point to the next entry
366        if ((*bucketPtr)->key == this->key) {
367            *bucketPtr = nextPtr;
368        }
369        else {
370            // if the entry is not the first entry in the bucket
371            // search for the entry
372            for (prevPtr = *bucketPtr; ; prevPtr = prevPtr->nextPtr) {
373
374                // printf("malformed bucket chain in RpDictEntry::erase()");
375                assert(prevPtr != NULL);
376
377                if (prevPtr->nextPtr == this) {
378                    prevPtr->nextPtr = nextPtr;
379                    break;
380                }
381            } // end for loop
382        } // end else
383
384        // update our table's information
385        tablePtr->numEntries--;
386
387    } // end if tablePtr
388
389    // invalidate the object
390    nextPtr = NULL;
391    tablePtr = NULL;
392    hash = 0;
393    // clientData = NULL;
394    // key = NULL;
395   
396    // delete the object.
397    // printf("delete %x\n", (unsigned) this);
398    delete this;
399   
400}
401
402
403/*
404 *----------------------------------------------------------------------
405 *
406 * const char* RpDictEntry::getKey() const
407 *
408 *  retrieve the key of the current object
409 *
410 * Results:
411 *  the key is returned to the caller
412 *
413 * Side effects:
414 *  None.
415 *
416 *----------------------------------------------------------------------
417 */
418
419template <typename KeyType, typename ValType>
420const KeyType*
421RpDictEntry<KeyType,ValType>::getKey() const
422{   
423    return (const KeyType*) &key;
424}
425
426/*
427 *----------------------------------------------------------------------
428 *
429 * const char* RpDictEntry::getValue() const
430 *
431 *  retrieve the value of the current object
432 *
433 * Results:
434 *  the value is returned to the caller
435 *
436 * Side effects:
437 *  None.
438 *
439 *----------------------------------------------------------------------
440 */
441
442template <typename KeyType, typename ValType>
443const ValType*
444RpDictEntry<KeyType,ValType>::getValue() const
445{   
446    return (const ValType*) &clientData;
447}
448
449/*
450 *----------------------------------------------------------------------
451 *
452 * const void* RpDictEntry::setValue()
453 *
454 *  retrieve the value of the current object
455 *
456 * Results:
457 *  the value is returned to the caller
458 *
459 * Side effects:
460 *  None.
461 *
462 *----------------------------------------------------------------------
463 */
464
465template <typename KeyType, typename ValType>
466const ValType*
467RpDictEntry<KeyType,ValType>::setValue(const ValType& value)
468{   
469    clientData = value;
470    return (const ValType*) &clientData;
471}
472
473template <typename KeyType, typename ValType>
474RpDictEntry<KeyType,ValType>::operator int() const
475{
476
477    if (!tablePtr && hash == 0)
478        return 0;
479    else
480        return 1;
481
482//    return (key);
483}
484
485
486/*************************************************************************/
487/*************************************************************************/
488
489// private member functions
490
491/*
492 *----------------------------------------------------------------------
493 *
494 * RebuildTable --
495 *
496 *  This procedure is invoked when the ratio of entries to hash
497 *  buckets becomes too large.  It creates a new table with a
498 *  larger bucket array and moves all of the entries into the
499 *  new table.
500 *
501 * Results:
502 *  None.
503 *
504 * Side effects:
505 *  Memory gets reallocated and entries get re-hashed to new
506 *  buckets.
507 *
508 *----------------------------------------------------------------------
509 */
510
511template <typename KeyType, typename ValType>
512void
513RpDict<KeyType,ValType>::RebuildTable()
514{
515    int oldSize=0, count=0, index=0;
516    RpDictEntry<KeyType,ValType> **oldBuckets;
517    RpDictEntry<KeyType,ValType> **oldChainPtr, **newChainPtr;
518    RpDictEntry<KeyType,ValType> *hPtr;
519   
520    void *key;
521
522    oldSize = numBuckets;
523    oldBuckets = buckets;
524
525    /*
526     * Allocate and initialize the new bucket array, and set up
527     * hashing constants for new array size.
528     */
529
530
531    numBuckets *= 4;
532
533    buckets = (RpDictEntry<KeyType,ValType> **) malloc((unsigned)
534        (numBuckets * sizeof(RpDictEntry<KeyType,ValType> *)));
535
536    for (count = numBuckets, newChainPtr = buckets;
537        count > 0;
538        count--, newChainPtr++) {
539
540        *newChainPtr = NULL;
541    }
542
543    rebuildSize *= 4;
544    downShift -= 2;
545    mask = (mask << 2) + 3;
546
547    /*
548     * Rehash all of the existing entries into the new bucket array.
549     */
550
551    for (oldChainPtr = oldBuckets; oldSize > 0; oldSize--, oldChainPtr++) {
552        for (hPtr = *oldChainPtr; hPtr != NULL; hPtr = *oldChainPtr) {
553            *oldChainPtr = hPtr->nextPtr;
554
555            key = (void *) hPtr->getKey();
556
557            index = randomIndex(hPtr->hash);
558
559            hPtr->nextPtr = buckets[index];
560            buckets[index] = hPtr;
561        }
562    }
563
564    /*
565     * Free up the old bucket array, if it was dynamically allocated.
566     */
567
568    if (oldBuckets != staticBuckets) {
569        free((char *) oldBuckets);
570    }
571}
572
573/*
574 *----------------------------------------------------------------------
575 *
576 * hashFxn --
577 *
578 *  Compute a one-word summary of a text string, which can be
579 *  used to generate a hash index.
580 *
581 * Results:
582 *  The return value is a one-word summary of the information in
583 *  string.
584 *
585 * Side effects:
586 *  None.
587 *
588 *----------------------------------------------------------------------
589 */
590
591template <typename KeyType, typename ValType>
592unsigned int
593RpDict<KeyType,ValType>::hashFxn(const void *keyPtr) const
594{
595    const char *stopAddr = (const char *) keyPtr + sizeof(&keyPtr) - 1 ;
596    const char *str = (const char *) keyPtr;
597    unsigned int result;
598    int c;
599
600    result = 0;
601
602    while (str != stopAddr) {
603        c = *str;
604        result += (result<<3) + c;
605        str++;
606    }
607   
608    return result;
609}
610
611/*
612 * I tried a zillion different hash functions and asked many other
613 * people for advice.  Many people had their own favorite functions,
614 * all different, but no-one had much idea why they were good ones.
615 * I chose the one below (multiply by 9 and add new character)
616 * because of the following reasons:
617 *
618 * 1. Multiplying by 10 is perfect for keys that are decimal strings,
619 *    and multiplying by 9 is just about as good.
620 * 2. Times-9 is (shift-left-3) plus (old).  This means that each
621 *    character's bits hang around in the low-order bits of the
622 *    hash value for ever, plus they spread fairly rapidly up to
623 *    the high-order bits to fill out the hash value.  This seems
624 *    works well both for decimal and non-decimal strings.
625 */
626
627
628template <typename KeyType, typename ValType>
629unsigned int
630RpDict<KeyType,ValType>::hashFxn(std::string* keyPtr) const
631{
632    const char *str = (const char *) (keyPtr->c_str());
633    unsigned int result;
634    int c;
635
636    result = 0;
637
638    while (1) {
639        c = *str;
640        if (c == 0) {
641            break;
642        }
643        result += (result<<3) + c;
644        str++;
645    }
646   
647    return result;
648}
649
650template <typename KeyType, typename ValType>
651unsigned int
652RpDict<KeyType,ValType>::hashFxn(char* keyPtr) const
653{
654    const char *str = (const char *) (keyPtr);
655    unsigned int result;
656    int c;
657
658    result = 0;
659
660    while (1) {
661        c = *str;
662        if (c == 0) {
663            break;
664        }
665        result += (result<<3) + c;
666        str++;
667    }
668   
669    return result;
670}
671
672/*
673 * ---------------------------------------------------------------------
674 *
675 * int RpDict::randomIndex(hash)
676 *
677 * The following macro takes a preliminary integer hash value and
678 * produces an index into a hash tables bucket list.  The idea is
679 * to make it so that preliminary values that are arbitrarily similar
680 * will end up in different buckets.  The hash function was taken
681 * from a random-number generator.
682 *
683 * ---------------------------------------------------------------------
684 */
685
686template <typename KeyType, typename ValType>
687int
688RpDict<KeyType,ValType>::randomIndex(unsigned int hash)
689{
690    return (((((long) (hash))*1103515245) >> downShift) & mask);
691}
692
693
Note: See TracBrowser for help on using the repository browser.