home *** CD-ROM | disk | FTP | other *** search
/ Info-Mac 3 / Info_Mac_1994-01.iso / Development / Source / Arashi 1.1 Source / For your think c folder / Juri's Class Library / CStringDictionary.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-06-29  |  5.8 KB  |  261 lines  |  [TEXT/KAHL]
  1. /*/
  2.      Project Arashi: CStringDictionary.c
  3.      Major release: Version 1.1, 7/22/92
  4.  
  5.      Last modification: Tuesday, June 29, 1993, 2:16
  6.      Created: Friday, December 4, 1992, 11:45
  7.  
  8.      Copyright © 1992-1993, Juri Munkki
  9. /*/
  10.  
  11. /*
  12. **    See include file for more details on how this class works.
  13. */
  14. #include "CStringDictionary.h"
  15. #include <RamFiles.h>
  16.  
  17. /*
  18. **    Given a counted string of length len, HashString
  19. **    will return a value from 0 to HASHTABLESIZE-1.
  20. **    This value can be used as the hashing value for
  21. **    that string.
  22. */ 
  23. short    HashString(
  24.     unsigned char     *string,
  25.     short            len)
  26. {    
  27.     if(len>0)
  28.     {    return (string[0]+string[len-1]+string[len>>1]) & (HASHTABLESIZE - 1);
  29.     }
  30.     else
  31.         return 0;
  32. }
  33. /*
  34. **    Initialize a CStringDictionary. The directory will be empty.
  35. */
  36. void    CStringDictionary::IStringDictionary()
  37. {
  38.     int        i;
  39.     
  40.     dictCount = 0;                    //    Dictionary is empty.
  41.     logicalDictSize = 0;
  42.     realDictSize = 0;
  43.     dictionary = (DictEntry **)NewHandle(0);
  44.     
  45.     logicalWordListSize = 0;        //    Dictionary words are listed separately.
  46.     realWordListSize = 0;
  47.     wordList = (unsigned char **)NewHandle(0);
  48.         
  49.     for(i=0;i<HASHTABLESIZE;i++)    //    Hash table is empty.
  50.     {    hashTable[i] = -1;
  51.     }
  52.  
  53.     IBaseObject();
  54. }
  55.  
  56. /*
  57. **    Return count of items in dictionary.
  58. */
  59. short    CStringDictionary::GetDictionarySize()
  60. {
  61.     return dictCount;
  62. }
  63.  
  64. /*
  65. **    Copy the string for entry index to theEntry
  66. */
  67. void    CStringDictionary::GetIndEntry(
  68.     short        index,
  69.     StringPtr    theEntry)
  70. {
  71.     DictEntry    *thisEntry;
  72.     StringPtr    entryString;
  73.     short        i;
  74.     
  75.     if(index >= 0 && index < dictCount)
  76.     {
  77.         thisEntry = index + (DictEntry *) *dictionary;
  78.         entryString = thisEntry->nameOffset + *wordList;
  79.         
  80.         i = 1+entryString[0];
  81.         while(i--)
  82.         {    theEntry[i] = entryString[i]; 
  83.         }
  84.     }
  85. }
  86.  
  87. /*
  88. **    Add a dictionary entry regardless
  89. **    of wether it already is there or not. Normally you would
  90. **    first look for a dictionary entry before calling this
  91. **    routine. Call this routine if you are absolutely sure
  92. **    that the entry isn't already in the dictionary.
  93. **
  94. **    NOTE: A negative return value signifies and error.
  95. */
  96. tokentype    CStringDictionary::AddDictEntry(
  97.     unsigned char    *entry,
  98.     short            len)
  99. {
  100.     long            where;
  101.     tokentype        entryIndex = 0;
  102.     long            theErr = noErr;
  103.     short            hashed;
  104.     short            state;
  105.     DictEntry        *entryP;
  106.     
  107.     if(len<0) len = *entry;
  108.     if(len>255) len = 255;
  109.  
  110.     state = HGetState((Handle) this);    //    Lock the object for a while.
  111.     HLock((Handle)this);
  112.     
  113.     //    Increase the dictionary size, if memory allows.
  114.     if(IncreaseByClump(    (Handle)dictionary,
  115.                         &realDictSize,
  116.                         &logicalDictSize,
  117.                         sizeof(DictEntry),
  118.                         DICTIONARYCLUMPSIZE) == noErr)
  119.     {
  120.         where = logicalWordListSize;    //    New word is written at this offset.
  121.         
  122.         //    Increase the word list size, if memory allows.
  123.         if(IncreaseByClump(    (Handle)wordList,
  124.                             &realWordListSize,
  125.                             &logicalWordListSize,
  126.                             len+1,
  127.                             WORDCLUMPSIZE) == noErr)
  128.         {    BlockMove(entry+1,1+where+*wordList,len);    //    Write the word.
  129.             (*wordList)[where] = len;                    //    Store the length
  130.             entryIndex = dictCount++;                    //    Get a new token value (or index).
  131.             entryP = entryIndex + *dictionary;            //    A pointer to the entry.
  132.             
  133.             hashed = HashString(entry+1,len);            //    Hash the entry by adding it
  134.             entryP->hashLink = hashTable[hashed];        //    in front of all other entries
  135.             entryP->nameOffset = where;                    //    in the linked list of words
  136.             hashTable[hashed] = entryIndex;                //    hashing to the same entry.
  137.         }
  138.         else
  139.         {    logicalDictSize -= sizeof(DictEntry);        //    Memory was full or handle locked.
  140.             theErr = memFullErr;                        //    Assume that memory was full...
  141.         }
  142.     }
  143.     else
  144.     {    theErr = memFullErr;                            //    Memory was full or handle locked.
  145.     }
  146.  
  147.     HSetState((Handle)this,state);            //    Restore the object lock state.
  148.     return theErr ? theErr : entryIndex;    //    Return an error or the entry.
  149. }
  150.  
  151. /*
  152. **    Look for an entry and return it if found. Return
  153. **    -1 if the entry is not found.
  154. */
  155. tokentype    CStringDictionary::SearchForEntry(
  156.     unsigned char    *entry,
  157.     short            len)
  158. {
  159.     short            hashWalk;
  160.     DictEntry        *thisEntry;
  161.     unsigned char    *p1,*p2;
  162.     
  163.     if(len<0) len = *entry;
  164.     if(len>255) len = 255;
  165.     
  166.     hashWalk = hashTable[HashString(entry+1,len)];    //    Find linked list head.
  167.     while(hashWalk >= 0)                            //    While there are items in the list.
  168.     {    p1 = entry+1;
  169.         thisEntry = hashWalk + *dictionary;
  170.         p2 = thisEntry->nameOffset + *wordList;        //    Compare the entries:
  171.         
  172.         if(len == *p2++)                            //    Compare length.
  173.         {    int    i;
  174.         
  175.             i = len;
  176.             while((i > 0) & (*p1++ == *p2++))        //    Compare characters.
  177.                 i--;
  178.         
  179.             if(i == 0)
  180.                 return hashWalk;                    //    Found! Return index.
  181.             else
  182.                 hashWalk = thisEntry->hashLink;        //    Not found, look at next entry.
  183.         }
  184.         else
  185.         {    hashWalk = thisEntry->hashLink;            //    Not found, look at next entry.
  186.         }
  187.     }
  188.  
  189.     return -1;        //    Return -1 when entry was not found.
  190. }
  191.  
  192. /*
  193. **    Look for an entry and if doesn't exist, create it.
  194. **    This routine only returns an error if there is a
  195. **    problem with memory management.
  196. */
  197. tokentype    CStringDictionary::FindEntry(
  198.     unsigned char     *entry,
  199.     short            len)
  200. {
  201.     tokentype    theToken;
  202.     
  203.     theToken = SearchForEntry(entry,len);
  204.     if (theToken >= 0) 
  205.         return theToken;
  206.     else
  207.         return AddDictEntry(entry,len);
  208. }
  209.  
  210. /*
  211. **    Unlock and dispose storage.
  212. */
  213. void    CStringDictionary::Dispose()
  214. {
  215.     ForceUnlock();
  216.     DisposHandle(wordList);
  217.     DisposHandle(dictionary);
  218.  
  219.     inherited::Dispose();
  220. }
  221.  
  222. /*
  223. **    Lock everything.
  224. */
  225. void    CStringDictionary::Lock()
  226. {
  227.     if(!lockCounter)
  228.     {    HLock(wordList);
  229.         HLock(dictionary);
  230.     }
  231.     inherited::Lock();
  232.  
  233. }
  234. /*
  235. **    Unlock everything.
  236. */
  237. void    CStringDictionary::Unlock()
  238. {
  239.     if(lockCounter == 1)
  240.     {    HUnlock(wordList);
  241.         HUnlock(dictionary);
  242.     }
  243.     inherited::Unlock();
  244. }
  245.  
  246. /*
  247. **    Read the dictionary string from a STR# resource.
  248. */
  249. void    CStringDictionary::ReadFromStringList(
  250.     short strListID)
  251. {
  252.     Str255    theString;
  253.     short    stringCount,i;
  254.     
  255.     stringCount = **(short **)GetResource('STR#',strListID);
  256.     for(i=1;i<=stringCount;i++)
  257.     {    GetIndString(theString,strListID,i);
  258.         AddDictEntry(theString, *theString);
  259.     }
  260. }
  261.