home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 2 / Apprentice-Release2.iso / Source Code / Think Class Libraries / CDictionary 1.0 / CDictionary.c next >
Encoding:
C/C++ Source or Header  |  1994-11-30  |  7.7 KB  |  306 lines  |  [TEXT/KAHL]
  1. /********************************************************************
  2. CDictionary.c
  3.  
  4.     see header for information
  5.     
  6. SUPERCLASS = CCollection
  7. ********************************************************************/
  8.  
  9.  
  10. #include "CDictionary.h"
  11. #include "CDataFile.h"
  12. #include "CApplication.h"
  13. #include "CError.h"
  14. #include "TBUtilities.h"
  15.  
  16. #define kMintableSize    64L        /* minimum table size */
  17.  
  18. /*    macro to calculate address of a bucket in the hash table 
  19.     can't use C arrays because entry size is determined
  20.     at runtime */
  21.     
  22. #define ASSOCIATION( bucketNum)    \
  23.         ((tAssociationPtr) (*table + ((Int32)bucketNum * slotSize)))
  24.         
  25. #define EMPTY    ((void*) 0L)
  26. #define DELETED ((void*) -1L)
  27. #define VACANT( assocPtr)    \
  28.             ((assocPtr->value == EMPTY)||(assocPtr->value == DELETED))
  29. #define NOT_FOUND        (-1L)
  30.  
  31. extern CApplication *gApplication;
  32. extern CError        *gError;
  33.  
  34.  
  35. /********************************************************************/
  36. Boolean CDictionary::IDictionary( Int16 keySize, MapProc map, CompareProc compare,
  37.                     Int32 initialSize)
  38. /*
  39.     initialize a Dictionary, return false if no error.
  40. */
  41. {
  42.     Int32    sizeNeeded;
  43.     register Int16    power2;
  44.     register Int32 bits;
  45.     
  46.     CCollection::ICollection();
  47.     
  48.     /* get initial table size */
  49.     
  50.     this->map = map;
  51.     this->compare = compare;
  52.     this->keySize = keySize;
  53.     this->slotSize = keySize + sizeof( CObject*);
  54.     
  55.     /* tableSize must be power of 2 >= kMinTableSize */
  56.     initialSize = MAX( initialSize, kMintableSize);
  57.     
  58.     /* find greatest power of 2 <= initialSize */
  59.     power2 = 0; bits = initialSize;
  60.     while (bits >>= 1) power2++;
  61.     
  62.     /* if initialSize was power of 2 use it, else get next highest */
  63.     tableSize = initialSize == 1 << power2 ? initialSize : 1 << (power2 + 1);
  64.     slotsLeft = tableSize;
  65.  
  66.     /* calculate size of hash table and allocate the memory */
  67.     
  68.     sizeNeeded = tableSize * (Int32) slotSize;
  69.     
  70.     gApplication->RequestMemory( FALSE, TRUE);
  71.     table = NewHandleClear( sizeNeeded);
  72.     gApplication->RequestMemory( FALSE, FALSE);
  73.     
  74.     if (!table) return TRUE;
  75.     MoveHHi( table);
  76.     
  77.     return FALSE;
  78.  
  79. }    /* CDictionary::IDictionary */        
  80. /********************************************************************/
  81. void CDictionary::Add( void *key, CObject *value)
  82. {
  83.       Int32 hash, curr;
  84.                 
  85.     /* always leave at least one empty slot as sentinel */
  86.     
  87.     if (slotsLeft <= 1) MoreSlots();
  88.         
  89.     /*    map key to value and do simple mod to get table index */
  90.     curr = hash = map( key) & (tableSize -1);
  91.     
  92.     while( !VACANT(ASSOCIATION(curr)))
  93.     {
  94.         /*    if the key is already present then replace its
  95.             value and return */
  96.         if(compare( key, (void*) ASSOCIATION(curr)->key) )
  97.         {
  98.             ASSOCIATION(curr)->value = value;
  99.             return;
  100.         }
  101.         if (++curr == tableSize) curr = 0; /* linear probing with wraparound */
  102.     }
  103.     /* curr now points to a vacant slot */
  104.         
  105.     ASSOCIATION(curr)->value = value;
  106.     BlockMove( key, ASSOCIATION(curr)->key, keySize);
  107.     numItems++;
  108.     slotsLeft--;
  109.     
  110. }    /* CDictionary::Add */        
  111. /********************************************************************/
  112. /* iterator for dictionary to add */
  113. static void DICT_AddAssoc( tAssociationPtr anAssoc, Int32 targetDict)
  114. {
  115.     ((CDictionary*) targetDict)->Add( anAssoc->key, anAssoc->value);
  116.  
  117. }    /* DICT_AddAssoc */
  118.  
  119.  
  120. void CDictionary::AddAll( CDictionary *aDictionary)
  121. {
  122.     aDictionary->DoForEach1( DICT_AddAssoc, (Int32)this);
  123.  
  124. }    /* CDictionary::AddAll */        
  125. /********************************************************************/
  126. void CDictionary::Remove( void *key)
  127. {
  128.     Int32 index = _lookup( key);
  129.     
  130.     if (index != NOT_FOUND)
  131.     {
  132.         ASSOCIATION( index)->value = DELETED;
  133.         numItems--;
  134.     }
  135.  
  136. }    /* CDictionary::Remove */        
  137. /********************************************************************/    
  138. Boolean CDictionary::IncludesKey( void *key)
  139. {
  140.     return (_lookup( key) != NOT_FOUND);
  141.  
  142. }    /* CDictionary::IncludesKey */        
  143. /********************************************************************/
  144. Boolean CDictionary::IncludesValue( CObject *anObject)
  145. {
  146.     Int32    i;
  147.     tAssociationPtr assoc;
  148.     
  149.     for (i = 0; i < tableSize; i++)
  150.     {
  151.         assoc = ASSOCIATION(i);
  152.         if (!VACANT( assoc))
  153.         {
  154.             if (anObject == assoc->value)
  155.                 return TRUE;
  156.         }
  157.     }
  158.     return FALSE;
  159.  
  160. }    /* CDictionary::IncludesValue */        
  161. /********************************************************************/    
  162. void CDictionary::DoForEach( DictIterator actionProc)
  163. {
  164.     Int32    i;
  165.     tAssociationPtr assoc;
  166.     SignedByte    hState;
  167.     
  168.     /* since we pass the iterator a pointer to our data,
  169.         it is safer to lock the table down so the pointer
  170.         remains valid */
  171.     
  172.     MoveHHi( table);
  173.     hState = HGetState( table);
  174.     HLock( table);
  175.     for (i = 0; i < tableSize; i++)
  176.     {
  177.         assoc = ASSOCIATION(i);
  178.         if (!VACANT( assoc))
  179.             actionProc( assoc);
  180.     }
  181.     HSetState( table, hState);
  182.  
  183. }    /* CDictionary::DoForEach */        
  184. /********************************************************************/
  185. void CDictionary::DoForEach1( DictIterator1 actionProc, Int32 aParam)
  186. {
  187.     Int32    i;
  188.     tAssociationPtr assoc;
  189.     SignedByte    hState;
  190.     
  191.     MoveHHi( table);
  192.     hState = HGetState( table);
  193.     HLock( table);
  194.     for (i = 0; i < tableSize; i++)
  195.     {
  196.         assoc = ASSOCIATION(i);
  197.         if (!VACANT( assoc))
  198.             actionProc( assoc, aParam);
  199.     }
  200.     HSetState( table, hState);
  201.  
  202. }    /* CDictionary::DoForEach1 */        
  203. /********************************************************************/    
  204. CObject *CDictionary::Lookup( void *key)
  205. {
  206.     Int32 index = _lookup( key);
  207.     
  208.     return( index == NOT_FOUND? NIL : ASSOCIATION( index)->value);
  209.  
  210. }    /* CDictionary::Lookup */
  211. /********************************************************************/    
  212. Int32 CDictionary::_lookup( void *key)
  213. /*
  214.     private routine to lookup a key in the hash table.
  215.     Given a key, either returns its index (a positive long),
  216.     or NOT_FOUND.
  217. */
  218. {    register Int32  curr;
  219.  
  220.     curr = map( key) & (tableSize -1);
  221.     
  222.     while(ASSOCIATION(curr)->value != EMPTY && 
  223.         (ASSOCIATION(curr)->value == DELETED ? 1:!compare( key,ASSOCIATION(curr)->key)))
  224.     {
  225.         if (++curr == tableSize) curr = 0;
  226.     }
  227.     return (ASSOCIATION(curr)->value == EMPTY ? NOT_FOUND : curr);
  228.  
  229. }    /* CDictionary::_lookup */    
  230. /********************************************************************/        
  231. CObject *CDictionary::Copy( void)
  232. {
  233.     CDictionary *newDict = (CDictionary *) inherited::Copy();
  234.     Handle tableCopy = table;
  235.     
  236.     newDict->table = NIL;
  237.     HandToHand( &tableCopy);
  238.     if (!gError->CheckOSError( MemError()))
  239.     {
  240.         newDict->Dispose();
  241.         return NIL;
  242.     }
  243.     MoveHHi( tableCopy);
  244.     newDict->table = tableCopy;
  245.     newDict->itsFile = NIL;
  246.     return newDict;
  247.  
  248. }    /* CDictionary::Copy */
  249. /********************************************************************/        
  250. void CDictionary::MoreSlots( void)
  251. /*
  252.     called when we need to grow the table.
  253. */
  254. {    CDictionary *tmpDict;
  255.     Int32 newSize;
  256.     
  257.     tmpDict = (CDictionary*) Copy();/* make temporary copy of dictionary */
  258.     if (tmpDict)
  259.     {
  260.         tableSize <<= 1;
  261.         newSize = tableSize * slotSize;
  262.         DisposHandle( table);
  263.         gApplication->RequestMemory( FALSE, TRUE);
  264.         table = NewHandleClear( newSize);
  265.         gApplication->RequestMemory( FALSE, FALSE);
  266.         if (!table) gError->SevereMacError( memFullErr);
  267.         MoveHHi( table);
  268.         
  269.         numItems = 0;
  270.         slotsLeft = tableSize;
  271.         AddAll( tmpDict);
  272.         tmpDict->Dispose();
  273.     }
  274.     else gError->SevereMacError( memFullErr);
  275.  
  276. }    /* CDictionary::MoreSlots */        
  277. /********************************************************************/
  278. void CDictionary::Dispose( void)
  279. {
  280.     if (table) DisposHandle( table);
  281.     inherited::Dispose();
  282.  
  283. }    /* CDictionary::Dispose */        
  284. /********************************************************************/
  285. void CDictionary::DisposeAll( void)
  286. {
  287.     DisposeItems();
  288.     Dispose();
  289.  
  290. }    /* CDictionary::DisposeAll */        
  291. /********************************************************************/
  292. /* iterator for disposing items */
  293. static void DICT_DisposeItems( tAssociationPtr anAssoc)
  294. {
  295.     if (anAssoc->value) anAssoc->value->Dispose();
  296.  
  297. }    /* DICT_DisposeItems */
  298.  
  299. void CDictionary::DisposeItems( void)
  300. {
  301.     DoForEach( DICT_DisposeItems);
  302.     numItems = 0;
  303.  
  304. }    /* CDictionary::DisposeItems */        
  305. /********************************************************************/    
  306.