home *** CD-ROM | disk | FTP | other *** search
/ io Programmo 40 / IOPROG_40.ISO / SOFT / NETFrameworkSDK.exe / comsdk.cab / samples1.exe / smc / hash.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  2000-06-23  |  9.0 KB  |  392 lines
  1. /*****************************************************************************/
  2.  
  3. #include "smcpch.h"
  4. #pragma hdrstop
  5.  
  6. /*****************************************************************************/
  7.  
  8. #include "alloc.h"
  9. #include "scan.h"
  10.  
  11. /*****************************************************************************/
  12.  
  13. #define MEASURE_HASH_STATS  0
  14.  
  15. /*****************************************************************************/
  16.  
  17. bool                hashTab::hashMemAllocInit(Compiler comp, norls_allocator*alloc)
  18. {
  19.     if  (alloc)
  20.     {
  21.         hashMemAlloc = alloc;
  22.         return false;
  23.     }
  24.  
  25.     hashMemAlloc = &hashMemAllocPriv;
  26.  
  27.     return  hashMemAllocPriv.nraInit(comp, OS_page_size);
  28. }
  29.  
  30. void                hashTab::hashMemAllocDone()
  31. {
  32. }
  33.  
  34. void                hashTab::hashMemAllocFree()
  35. {
  36.     if  (hashMemAlloc == &hashMemAllocPriv)
  37.         hashMemAllocPriv.nraFree();
  38. }
  39.  
  40. /*****************************************************************************/
  41.  
  42. void                hashTab::hashDone()
  43. {
  44.     hashMemAllocDone();
  45. }
  46.  
  47. void                hashTab::hashFree()
  48. {
  49.     hashMemAllocFree();
  50. }
  51.  
  52. /*****************************************************************************/
  53.  
  54. #if MEASURE_HASH_STATS
  55.  
  56. unsigned            identCount;
  57.  
  58. unsigned            lookupCnt;
  59. unsigned            lookupTest;
  60. unsigned            lookupMatch;
  61.  
  62. void                dispHashTabStats()
  63. {
  64.     if  (identCount)
  65.         printf("A total of %6u identifiers in hash table\n", identCount);
  66.  
  67.     if  (!lookupCnt)
  68.         return;
  69.  
  70.     printf("Average of %8.4f checks of bucket check  / lookup\n", (float)lookupTest /lookupCnt);
  71.     printf("Average of %8.4f compares of identifiers / lookup\n", (float)lookupMatch/lookupCnt);
  72. }
  73.  
  74. #endif
  75.  
  76. /*****************************************************************************/
  77.  
  78. Ident               hashTab::hashName(const   char *  name,
  79.                                       unsigned        hval,
  80.                                       unsigned        nlen,
  81.                                       bool            wide)
  82. {
  83.     Ident    *  lastPtr;
  84.     unsigned    hash;
  85.     Ident       id;
  86.     size_t      sz;
  87.  
  88.     assert(nlen == strlen(name));
  89.     assert(hval == hashComputeHashVal(name));
  90.  
  91.     /* Mask the appropriate bits from the hash value */
  92.  
  93.     hash = hval & hashMask;
  94.  
  95.     /* Search the hash table for an existing match */
  96.  
  97.     lastPtr = &hashTable[hash];
  98.  
  99.     for (;;)
  100.     {
  101.         id = *lastPtr;
  102.         if  (!id)
  103.             break;
  104.  
  105.         /* Check whether the hash value matches */
  106.  
  107.         if  (id->idHash == hval && id->idNlen == nlen)
  108.         {
  109.  
  110. #if 1
  111.  
  112.             unsigned        ints = nlen / sizeof(int);
  113.  
  114.             const char *    ptr1 = id->idName;
  115.             const char *    ptr2 = name;
  116.  
  117.             while (ints)
  118.             {
  119.                 if  (*(unsigned *)ptr1 != *(unsigned *)ptr2)
  120.                     goto NEXT;
  121.  
  122.                 ptr1 += sizeof(unsigned);
  123.                 ptr2 += sizeof(unsigned);
  124.  
  125.                 ints -= 1;
  126.             }
  127.  
  128.             ints = nlen % sizeof(int);
  129.  
  130.             while (ints)
  131.             {
  132.                 if  (*ptr1 != *ptr2)
  133.                     goto NEXT;
  134.  
  135.                 ptr1++;
  136.                 ptr2++;
  137.                 ints--;
  138.             }
  139.  
  140.             return  id;
  141.  
  142. #else
  143.  
  144.             if  (!memcmp(id->idName, name, nlen+1))
  145.                 return  id;
  146.  
  147. #endif
  148.  
  149.         }
  150.  
  151.     NEXT:
  152.  
  153.         lastPtr = &id->idNext;
  154.     }
  155.  
  156. #if MGDDATA
  157.  
  158.     id = new Ident;
  159.  
  160.     id->idName = new managed char[nlen+1]; UNIMPL(!"need to copy string");
  161.  
  162. #else
  163.  
  164.     /* Figure out the size to allocate */
  165.  
  166.     sz  = sizeof(*id);
  167.  
  168.     /* Include space for name string + terminating null and round the size */
  169.  
  170.     sz +=   sizeof(int) + nlen;
  171.     sz &= ~(sizeof(int) - 1);
  172.  
  173.     /* Allocate space for the identifier */
  174.  
  175.     id = (Ident)hashMemAlloc->nraAlloc(sz);
  176.  
  177.     /* Copy the name string */
  178.  
  179.     memcpy(id->idName, name, nlen+1);
  180.  
  181. #endif
  182.  
  183.     /* Insert the identifier into the hash list */
  184.  
  185.     *lastPtr = id;
  186.  
  187.     /* Fill in the identifier record */
  188.  
  189.     id->idNext   = NULL;
  190.     id->idToken  = 0;
  191.     id->idFlags  = 0;
  192.     id->idSymDef = NULL;
  193.  
  194.     id->idHash   = hval;
  195.     id->idNlen   = nlen;
  196.     id->idOwner  = hashOwner;
  197.  
  198.     /* Remember whether the name has any wide characters in it */
  199.  
  200.     if  (wide) id->idFlags |= IDF_WIDE_CHARS;
  201.  
  202. #if MEASURE_HASH_STATS
  203.     identCount++;
  204. #endif
  205.  
  206.     return  id;
  207. }
  208.  
  209. /*****************************************************************************
  210.  *
  211.  *  Look for the given name in the hash table (if 'hval' is non-zero, it must
  212.  *  be equal to the hash value for the identifier). If the identifier is not
  213.  *  found it is added if 'add' is non-zero, otherwise NULL is returned.
  214.  */
  215.  
  216. Ident               hashTab::lookupName(const char *    name,
  217.                                         size_t          nlen,
  218.                                         unsigned        hval,
  219.                                         bool            add)
  220. {
  221.     Ident           id;
  222.     unsigned        hash;
  223.  
  224.     assert(nlen == strlen(name));
  225.     assert(hval == hashComputeHashVal(name) || hval == 0);
  226.  
  227.     /* Make sure we have a proper hash value */
  228.  
  229.     if  (hval == 0)
  230.     {
  231.         hval = hashComputeHashVal(name);
  232.     }
  233.     else
  234.     {
  235.         assert(hval == hashComputeHashVal(name));
  236.     }
  237.  
  238.     /* Mask the appropriate bits from the hash value */
  239.  
  240.     hash = hval & hashMask;
  241.  
  242.     /* Search the hash table for an existing match */
  243.  
  244. #if MEASURE_HASH_STATS
  245.     lookupCnt++;
  246. #endif
  247.  
  248.     for (id = hashTable[hash]; id; id = id->idNext)
  249.     {
  250.         /* Check whether the hash value and identifier lengths match */
  251.  
  252. #if MEASURE_HASH_STATS
  253.         lookupTest++;
  254. #endif
  255.  
  256.         if  (id->idHash == hval)
  257.         {
  258.  
  259. #if MEASURE_HASH_STATS
  260.             lookupMatch++;
  261. #endif
  262.  
  263.             if  (!memcmp(id->idName, name, nlen+1))
  264.                 return  id;
  265.         }
  266.     }
  267.  
  268.     assert(id == 0);
  269.  
  270.     /* Identifier not found - are we supposed to add it? */
  271.  
  272.     if  (add)
  273.     {
  274.         /* Add the identifier to the hash table */
  275.  
  276.         id = hashName(name, hval, nlen, hashHasWideChars(name));
  277.     }
  278.  
  279.     return  id;
  280. }
  281.  
  282. /*****************************************************************************/
  283. #ifndef __SMC__
  284.  
  285. const    char * hashTab::hashKwdNames[tkKwdCount];
  286. unsigned char   hashTab::hashKwdNlens[tkKwdCount];
  287.  
  288. #endif
  289. /*****************************************************************************/
  290.  
  291. bool            hashTab::hashInit(Compiler          comp,
  292.                                   unsigned          count,
  293.                                   unsigned          owner,
  294.                                   norls_allocator * alloc)
  295. {
  296.     size_t      hashBytes;
  297.  
  298.     assert(count);
  299.  
  300.     /* Start up the memory allocation subsystem */
  301.  
  302.     if  (hashMemAllocInit(comp, alloc))
  303.         return true;
  304.  
  305.     /* Save the owner id */
  306.  
  307.     hashOwner = owner;
  308.  
  309.     /* Copy the keyword table into the hash table */
  310.  
  311.     assert(sizeof(hashKwdNtab) == sizeof(hashKwdNames));
  312.     memcpy(&hashKwdNames, &hashKwdNtab, sizeof(hashKwdNames));
  313.  
  314.     /* Don't have any spellings yet */
  315.  
  316.     hashIdCnt = 0;
  317.  
  318.     /* Allocate the hash bucket table */
  319.  
  320.     hashCount = count;
  321.     hashMask  = count - 1;
  322.     hashBytes = count * sizeof(*hashTable);
  323.     hashTable = (Ident*)comp->cmpAllocBlock(hashBytes);
  324.  
  325.     memset(hashTable, 0, hashBytes);
  326.  
  327.     /* Initialize the hash function logic */
  328.  
  329.     hashFuncInit(20886);
  330.  
  331.     /* Hash all the keywords, if this is the global hash table */
  332.  
  333.     if  (owner == 0)
  334.     {
  335.         unsigned    kwdNo;
  336.  
  337.         assert(tkKwdCount >= tkID);
  338.  
  339. #ifdef  DEBUG
  340.         memset(tokenToIdTab, 0, sizeof(tokenToIdTab));
  341. #endif
  342.  
  343.         for (kwdNo = 0; kwdNo < tkID; kwdNo++)
  344.         {
  345.             Ident       kwid;
  346.  
  347.             kwdDsc      kdsc = hashKwdDescs[kwdNo];
  348.             const char *name = hashKwdNames[kwdNo];
  349. //          const char *norg = name;
  350.             size_t      nlen;
  351.  
  352.             /* Ignore this entry if it's not 'real' */
  353.  
  354.             if  (!name)
  355.                 continue;
  356.  
  357.             /* Is this a non-keyword? */
  358.  
  359. //          if  (*name == '@')
  360. //              name++;
  361.  
  362.             /* Record the keyword length (this is used by the lister) */
  363.  
  364.             hashKwdNlens[kwdNo] = nlen = strlen(name);
  365.  
  366.             /* Hash the keyword */
  367.  
  368.             tokenToIdTab[kdsc.kdValue] = kwid = hashString(name);
  369.             if  (!kwid)
  370.                 return  true;
  371.  
  372.             /* Don't mark it if it's not a "real" keyword */
  373.  
  374. //          if  (norg != name)
  375. //              continue;
  376.  
  377.             /* Mark this identifier as a keyword */
  378.  
  379.             kwid->idToken = kdsc.kdValue;
  380.  
  381.             /* Make sure we really have a keyword */
  382.  
  383.             assert(kwid->idToken != tkNone);
  384.             assert(kwid->idToken != tkID);
  385.         }
  386.     }
  387.  
  388.     return false;
  389. }
  390.  
  391. /*****************************************************************************/
  392.