home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / dosdisas.zip / dccsrcoo.zip / symtab.cpp < prev    next >
C/C++ Source or Header  |  1997-04-09  |  19KB  |  586 lines
  1. /*$Log:    symtab.c,v $
  2.  * Revision 1.6  93/10/01  09:16:15  cifuente
  3.  * *$Log in comments
  4.  * 
  5.  * Revision 1.5  93/10/01  09:01:46  cifuente
  6.  * boolT type - for compilation under unix SVR4.2
  7.  */
  8.  
  9. /* * * * * * * * * * * * * * * * * * * * * * * * * * * *\
  10. *                                                       *
  11. *       S y m b o l   t a b l e   F u n c t i o n s     *
  12. *                                                       *
  13. \* * * * * * * * * * * * * * * * * * * * * * * * * * * */
  14.  
  15. /* This file implements a symbol table with a symbolic name, a symbol value
  16.     (word), and a procedure number. Two tables are maintained, to be able to
  17.     look up by name or by value. Pointers are used for the duplicated symbolic
  18.     name to save space. Both tables have the same structure.
  19.     The hash tables automatically expand when they get 90% full; they are
  20.     never compressed. Expanding the tables could take some time, since about
  21.     half of the entries have to be moved on average.
  22.     Linear probing is used, due to the difficulty of implementing (e.g.)
  23.     quadratic probing with a variable table size.
  24. */
  25.  
  26.  
  27. #include <stdio.h>
  28. #include <stdlib.h>
  29. #include <string.h>
  30. #include "dcc.h"
  31. #include "symtab.h"
  32.  
  33. #define TABLESIZE 16                /* Number of entries added each expansion */
  34.                                     /* Probably has to be a power of 2 */
  35. #define STRTABSIZE 256              /* Size string table is inc'd by */
  36. #define NIL ((word)-1)
  37.  
  38.  
  39.  
  40. static word numEntry;               /* Number of entries in this table */
  41. static word tableSize;              /* Size of the table (entries) */
  42. static SYMTABLE *symTab;            /* Pointer to the symbol hashed table */
  43. static SYMTABLE *valTab;            /* Pointer to the value  hashed table */
  44.  
  45. static  char *pStrTab;              /* Pointer to the current string table */
  46. static  int   strTabNext;           /* Next free index into pStrTab */
  47.  
  48. static  tableType curTableType; /* Which table is current */
  49. typedef struct _tableInfo
  50. {
  51.     SYMTABLE *symTab;
  52.     SYMTABLE *valTab;
  53.     word      numEntry;
  54.     word      tableSize;
  55. } TABLEINFO_TYPE;
  56.  
  57. TABLEINFO_TYPE tableInfo[NUM_TABLE_TYPES];   /* Array of info about tables */
  58.  
  59.  
  60. /* Local prototypes */
  61. static  void    expandSym(void);
  62.  
  63. /* Create a new symbol table. Returns "handle" */
  64. void createSymTables(void)
  65. {
  66.     /* Initilise the comment table */
  67.     /* NB - there is no symbol hashed comment table */
  68.  
  69.     numEntry  = 0;
  70.     tableSize = TABLESIZE;
  71.     valTab = (SYMTABLE*)allocMem(sizeof(SYMTABLE) * TABLESIZE);
  72.     memset(valTab, 0, sizeof(SYMTABLE) * TABLESIZE);
  73.  
  74.     tableInfo[Comment].symTab = 0;
  75.     tableInfo[Comment].valTab = valTab;
  76.     tableInfo[Comment].numEntry = numEntry;
  77.     tableInfo[Comment].tableSize = tableSize;
  78.     
  79.     /* Initialise the label table */
  80.     numEntry  = 0;
  81.     tableSize = TABLESIZE;
  82.     symTab = (SYMTABLE*)allocMem(sizeof(SYMTABLE) * TABLESIZE);
  83.     memset(symTab, 0, sizeof(SYMTABLE) * TABLESIZE);
  84.  
  85.     valTab = (SYMTABLE*)allocMem(sizeof(SYMTABLE) * TABLESIZE);
  86.     memset(valTab, 0, sizeof(SYMTABLE) * TABLESIZE);
  87.  
  88.     tableInfo[Label].symTab = symTab;
  89.     tableInfo[Label].valTab = valTab;
  90.     tableInfo[Label].numEntry = numEntry;
  91.     tableInfo[Label].tableSize = tableSize;
  92.     curTableType = Label;
  93.  
  94.     /* Now the string table */
  95.     strTabNext = 0;
  96.     pStrTab = (char *)allocMem(STRTABSIZE);
  97.  
  98.     tableInfo[Label].symTab = symTab;
  99.     tableInfo[Label].valTab = valTab;
  100.     tableInfo[Label].numEntry = numEntry;
  101.     tableInfo[Label].tableSize = tableSize;
  102.     curTableType = Label;
  103.  
  104. }
  105.  
  106. void
  107. selectTable(tableType tt)
  108. {
  109.     if (curTableType == tt) return; /* Nothing to do */
  110.  
  111.     symTab   = tableInfo[tt].symTab;
  112.     valTab   = tableInfo[tt].valTab;
  113.     numEntry = tableInfo[tt].numEntry;
  114.     tableSize= tableInfo[tt].tableSize;
  115.     curTableType = tt;
  116. }
  117.  
  118. void destroySymTables(void)
  119. {
  120.     selectTable(Label);
  121.     free(symTab);                   /* The symbol hashed label table */
  122.     free(valTab);                   /* And the value hashed label table */
  123.     selectTable(Comment);
  124.     free(valTab);                   /* And the value hashed comment table */
  125. }
  126.  
  127.  
  128. /* Hash the symbolic name */
  129. word symHash(char *name, word *pre)
  130. {
  131.     int i;
  132.     word h = 0;
  133.     char ch;
  134.  
  135.     for (i=0; i < (int)strlen(name); i++)
  136.     {
  137.         ch = name[i];
  138.         h = (h << 2) ^ ch;
  139.         h += (ch >> 2) + (ch << 5);
  140.     }
  141.  
  142.     *pre = h;                       /* Pre modulo hash value */
  143.     return h % tableSize;           /* Post modulo hash value */
  144. }
  145.  
  146. /* Hash the symOff and symProc fields */
  147. /* Note: for the time being, there no use is made of the symProc field */
  148. word
  149. valHash(dword symOff, PPROC symProc, word *pre)
  150. {
  151.     word h = 0;
  152.  
  153.     h = (word)(symOff ^ (symOff >> 8));
  154.  
  155.     *pre = h;                       /* Pre modulo hash value */
  156.     return h % tableSize;           /* Post modulo hash value */
  157. }
  158.  
  159.  
  160. void
  161. enterSym(char *symName, dword symOff, PPROC symProc, boolT bSymToo)
  162. {
  163.     word h, pre, j;
  164.  
  165.     if ((numEntry / 9 * 10) >= tableSize)
  166.     {
  167.         /* Table is full. Expand it */
  168.         expandSym();
  169.     }
  170.  
  171.     /* Enter it into the value hashed table first */
  172.     h = valHash(symOff, symProc, &pre);     /* Ideal spot for this entry */
  173.     if (valTab[h].symProc == 0)             /* Collision? */
  174.     {
  175.         /* No. Just insert here */
  176.         valTab[h].pSymName= symName;        /* Symbol name ptr */
  177.         valTab[h].symOff    = symOff;       /* Offset of the symbol */
  178.         valTab[h].symProc   = symProc;      /* Symbol's proc num */
  179.         valTab[h].preHash = pre;            /* Pre modulo hash value */
  180.         valTab[h].postHash= h;              /* Post modulo hash value */
  181.         valTab[h].nextOvf = NIL;            /* No overflow */
  182.         valTab[h].prevOvf = NIL;            /* No back link */
  183.     }
  184.     else
  185.     {
  186.         /* Linear probing, for now */
  187.         j = (h+1) % tableSize;
  188.         while (j != h)
  189.         {
  190.             if (valTab[j].symProc == 0)
  191.             {
  192.                 /* Insert here */
  193.                 valTab[j].pSymName= symName;    /* Symbol name ptr */
  194.                 valTab[j].symOff  = symOff;     /* Offset of the symbol */
  195.                 valTab[j].symProc = symProc;    /* Symbol's proc num */
  196.                 valTab[j].preHash = pre;        /* Pre modulo hash value */
  197.                 valTab[j].postHash= h;          /* Post modulo hash value */
  198.                 /* Insert after the primary entry in the table */
  199.                 valTab[j].nextOvf = valTab[h].nextOvf;
  200.                 valTab[h].nextOvf = j;
  201.                 valTab[j].prevOvf = h;          /* The backlink */
  202.                 break;
  203.             }
  204.             else
  205.             {
  206.                 /* Probe further */
  207.                 j = (j+1) % tableSize;
  208.             }
  209.         }
  210.         if (j == h)
  211.         {
  212.             printf("enterSym: val table overflow!\n");
  213.             exit(1);
  214.         }
  215.     }
  216.  
  217.     /* Now enter into the symbol hashed table as well, if reqd */
  218.     if (!bSymToo) return;
  219.     h = symHash(symName, &pre);             /* Ideal spot for this entry */
  220.     if (symTab[h].pSymName == 0)            /* Collision? */
  221.     {
  222.         /* No. Just insert here */
  223.         symTab[h].pSymName= symName;        /* Symbol name ptr */
  224.         symTab[h].symOff  = symOff;         /* Offset of the symbol */
  225.         symTab[h].symProc = symProc;        /* Symbol's proc num */
  226.         symTab[h].preHash = pre;            /* Pre modulo hash value */
  227.         symTab[h].postHash= h;              /* Post modulo hash value */
  228.         symTab[h].nextOvf = NIL;            /* No overflow */
  229.         symTab[h].prevOvf = NIL;            /* No back link */
  230.     }
  231.     else
  232.     {
  233.         /* Linear probing, for now */
  234.         j = (h+1) % tableSize;
  235.         while (j != h)
  236.         {
  237.             if (symTab[j].pSymName == 0)
  238.             {
  239.                 /* Insert here */
  240.                 symTab[j].pSymName= symName;    /* Symbol name ptr */
  241.                 symTab[j].symOff  = symOff;     /* Offset of the symbol */
  242.                 symTab[j].symProc = symProc;    /* Symbol's proc num */
  243.                 symTab[j].preHash = pre;        /* Pre modulo hash value */
  244.                 symTab[j].postHash= h;          /* Post modulo hash value */
  245.                 /* Insert after the primary entry in the table */
  246.                 symTab[j].nextOvf = symTab[h].nextOvf;
  247.                 symTab[h].nextOvf = j;
  248.                 symTab[j].prevOvf = h;          /* The backlink */
  249.                 break;
  250.             }
  251.             else
  252.             {
  253.                 /* Probe further */
  254.                 j = (j+1) % tableSize;
  255.             }
  256.         }
  257.         if (j == h)
  258.         {
  259.             printf("enterSym: sym table overflow!\n");
  260.             exit(1);
  261.         }
  262.     }
  263.  
  264. }
  265.  
  266.  
  267. boolT
  268. findSym(char *symName, word *pIndex)
  269. {
  270.     word h, j, pre;
  271.  
  272.     h = symHash(symName, &pre);
  273.     j = h;
  274.     do
  275.     {
  276.         if (symTab[j].pSymName == 0)
  277.         {
  278.             return FALSE;                   /* No entry at all */
  279.         }
  280.         if (strcmp(symName, symTab[j].pSymName) == 0)
  281.         {
  282.             *pIndex = j;
  283.             return TRUE;                    /* Symbol found */
  284.         }
  285.         j = symTab[j].nextOvf;              /* Follow the chain */
  286.     }
  287.     while (j != NIL);
  288.     return FALSE;                           /* End of chain */
  289. }
  290.  
  291. /* Find symbol by value */
  292. boolT
  293. findVal(dword symOff, PPROC symProc, word *pIndex)
  294. {
  295.     word h, j, pre;
  296.  
  297.     h = valHash(symOff, symProc, &pre);
  298.     j = h;
  299.     do
  300.     {
  301.         if (valTab[j].symProc == 0)
  302.         {
  303.             return FALSE;                   /* No entry at all */
  304.         }
  305.         if ((valTab[j].symOff == symOff)
  306.             /*&& (valTab[j].symProc == symProc)*/)
  307.         {
  308.             *pIndex = j;
  309.             return TRUE;                    /* Symbol found */
  310.         }
  311.         j = valTab[j].nextOvf;              /* Follow the chain */
  312.     }
  313.     while (j != NIL);
  314.     return FALSE;                           /* End of chain */
  315. }
  316.  
  317. word
  318. findBlankSym(char *symName)
  319. {
  320.     word h, j, pre;
  321.  
  322.     h = symHash(symName, &pre);
  323.     j = h;
  324.     do
  325.     {
  326.         if (symTab[j].pSymName == 0)
  327.         {
  328.             return j;                   /* Empty entry. Terminate probing */
  329.         }
  330.         j = (++j) % tableSize;              /* Linear probing */
  331.     }
  332.     while (j != h);
  333.     printf("Could not find blank entry in table! Num entries is %ld of %ld\n",
  334.         (long)numEntry, (long)tableSize);
  335.     return 0;
  336. }
  337.  
  338. /* Using the symbolic name, read the value */
  339. boolT
  340. readSym(char *symName, dword *pSymOff, PPROC *pSymProc)
  341. {
  342.     word i;
  343.  
  344.     if (!findSym(symName, &i))
  345.     {
  346.         return FALSE;
  347.     }
  348.     *pSymOff = symTab[i].symOff;
  349.     *pSymProc= symTab[i].symProc;
  350.     return TRUE;
  351. }
  352.  
  353. /* Using the value, read the symbolic name */
  354. boolT
  355. readVal(char *symName, dword symOff, PPROC symProc)
  356. {
  357.     word i;
  358.  
  359.     if (!findVal(symOff, symProc, &i))
  360.     {
  361.         return FALSE;
  362.     }
  363.     strcpy(symName, valTab[i].pSymName);
  364.     return TRUE;
  365. }
  366.  
  367.  
  368.  
  369. /*  A doubly linked list of entries belonging to the same hash bucket is
  370.     maintained, to prevent the need for many entries to be moved when deleting
  371.     an entry. It is implemented with indexes, and is not an open hashing system.
  372.     Symbols are deleted from both hash tables.
  373. */
  374.  
  375. /* Known limitation: strings are never deleted from the string table */
  376.  
  377. void
  378. deleteSym(char *symName)
  379. {
  380.     word i, j, back;
  381.     dword symOff;
  382.     PPROC symProc;
  383.  
  384.     /* Delete from symbol hashed table first */
  385.     if (!findSym(symName, &i))
  386.     {
  387.         printf("Could not delete non existant symbol name %s\n", symName);
  388.         exit(1);
  389.     }
  390.     symOff = symTab[i].symOff;              /* Remember these for valTab */
  391.     symProc= symTab[i].symProc;
  392.     j = symTab[i].nextOvf;                  /* Look at next overflowed entry */
  393.     
  394.     if (j == NIL)                           /* Any overflows? */
  395.     {
  396.         /* No, so we just wipe out this record. Must NIL the pointer of
  397.             the previous record, however */
  398.         symTab[symTab[i].prevOvf].nextOvf = NIL;
  399.         j = i;                              /* So we wipe out the current name */
  400.     }
  401.     else 
  402.     {
  403.         /* Yes, move this entry to this vacated spot. Note that the nextOvf
  404.             field will still point to the next record in the overflow chain,
  405.             but we need to preserve the backlink for adjusting the current
  406.             item's backlink */
  407.         back = symTab[j].prevOvf;
  408.         memcpy(&symTab[i], &symTab[j], sizeof(SYMTABLE));
  409.         symTab[i].prevOvf = back;
  410.     }
  411.     /* And now mark the vacated record as empty */
  412.     symTab[j].pSymName = 0;             /* Rub out the name */
  413.  
  414.     
  415.     /* Delete from value hashed table */
  416.     if (!findVal(symOff, symProc, &i))
  417.     {
  418.         printf("Could not delete non existant symbol off %04X proc %d\n",
  419.             symOff, symProc);
  420.         exit(1);
  421.     }
  422.     j = valTab[i].nextOvf;              /* Look at next overflowed entry */
  423.     
  424.     if (j == NIL)                       /* Any overflows? */
  425.     {
  426.         /* No, so we just wipe out this record. Must NIL the pointer of
  427.             the previous record, however */
  428.         valTab[valTab[i].prevOvf].nextOvf = NIL;
  429.         j = i;                          /* So we wipe out the current entry */
  430.     }
  431.     else 
  432.     {
  433.         /* Yes, move this entry to this vacated spot. Note that the nextOvf
  434.             field will still point to the next record in the overflow chain,
  435.             but we need to preserve the backlink for adjusting the current
  436.             item's backlink */
  437.         back = valTab[j].prevOvf;
  438.         memcpy(&valTab[i], &valTab[j], sizeof(SYMTABLE));
  439.         valTab[i].prevOvf = back;
  440.     }
  441.     /* And now mark the vacated record as empty */
  442.     valTab[j].symProc = 0;          /* Rub out the entry */
  443. }
  444.  
  445.  
  446. void
  447. deleteVal(dword symOff, PPROC symProc, boolT bSymToo)
  448. {
  449.     word i, j, back;
  450.     char *symName;
  451.  
  452.     /* Delete from value hashed table */
  453.     if (!findVal(symOff, symProc, &i))
  454.     {
  455.         printf("Could not delete non existant symbol off %04X proc %p\n",
  456.             symOff, symProc);
  457.         exit(1);
  458.     }
  459.     symName = symTab[i].pSymName;       /* Remember this for symTab */
  460.     j = valTab[i].nextOvf;              /* Look at next overflowed entry */
  461.     
  462.     if (j == NIL)                       /* Any overflows? */
  463.     {
  464.         /* No, so we just wipe out this record. Must NIL the pointer of
  465.             the previous record, however */
  466.         valTab[valTab[i].prevOvf].nextOvf = NIL;
  467.         j = i;                          /* So we wipe out the current entry */
  468.     }
  469.     else 
  470.     {
  471.         /* Yes, move this entry to this vacated spot. Note that the nextOvf
  472.             field will still point to the next record in the overflow chain,
  473.             but we need to preserve the backlink for adjusting the current
  474.             item's backlink */
  475.         back = valTab[j].prevOvf;
  476.         memcpy(&valTab[i], &valTab[j], sizeof(SYMTABLE));
  477.         valTab[i].prevOvf = back;
  478.     }
  479.     /* And now mark the vacated record as empty */
  480.     valTab[j].symProc = 0;          /* Rub out the entry */
  481.  
  482.     /* If requested, delete from symbol hashed table now */
  483.     if (!bSymToo) return;
  484.     if (!findSym(symName, &i))
  485.     {
  486.         printf("Could not delete non existant symbol name %s\n", symName);
  487.         exit(1);
  488.     }
  489.     j = symTab[i].nextOvf;                  /* Look at next overflowed entry */
  490.     
  491.     if (j == NIL)                           /* Any overflows? */
  492.     {
  493.         /* No, so we just wipe out this record. Must NIL the pointer of
  494.             the previous record, however */
  495.         symTab[symTab[i].prevOvf].nextOvf = NIL;
  496.         j = i;                              /* So we wipe out the current name */
  497.     }
  498.     else 
  499.     {
  500.         /* Yes, move this entry to this vacated spot. Note that the nextOvf
  501.             field will still point to the next record in the overflow chain,
  502.             but we need to preserve the backlink for adjusting the current
  503.             item's backlink */
  504.         back = symTab[j].prevOvf;
  505.         memcpy(&symTab[i], &symTab[j], sizeof(SYMTABLE));
  506.         symTab[i].prevOvf = back;
  507.     }
  508.     /* And now mark the vacated record as empty */
  509.     symTab[j].pSymName = 0;             /* Rub out the name */
  510.     
  511. }
  512.  
  513. static void
  514. expandSym(void)
  515. {
  516.     word i, j, n, newPost;
  517.  
  518.     printf("\nResizing table...\r");
  519.     /* We double the table size each time, so on average only half of the
  520.         entries move to the new half. This works because we are effectively
  521.         shifting the "binary point" of the hash value to the left each time,
  522.         thereby leaving the number unchanged or adding an MSBit of 1. */
  523.     tableSize <<= 2;
  524.     symTab = (SYMTABLE*)reallocVar(symTab, tableSize * sizeof(SYMTABLE));
  525.     memset (&symTab[tableSize/2], 0, (tableSize/2) * sizeof(SYMTABLE));
  526.  
  527.     /* Now we have to move some of the entries to take advantage of the extra
  528.         space */
  529.  
  530.     for (i=0; i < numEntry; i++)
  531.     {
  532.         newPost = symTab[i].preHash % tableSize;
  533.         if (newPost != symTab[i].postHash)
  534.         {
  535.             /* This entry is now in the wrong place. Copy it to the new position,
  536.                 then delete it. */
  537.             j = findBlankSym(symTab[i].pSymName);
  538.             memcpy(&symTab[j], &symTab[i], sizeof(SYMTABLE));
  539.             /* Correct the post hash value */
  540.             symTab[j].postHash = newPost;
  541.  
  542.             /* Now adjust links */
  543.             n = symTab[j].prevOvf;
  544.             if (n != NIL)
  545.             {
  546.                 symTab[n].nextOvf = j;
  547.             }
  548.  
  549.             n = symTab[j].nextOvf;
  550.             if (n != NIL)
  551.             {
  552.                 symTab[n].prevOvf = j;
  553.             }
  554.             
  555.             /* Mark old position as deleted */
  556.             symTab[i].pSymName = 0;
  557.         }
  558.     }
  559. }
  560.  
  561. /* This function adds to the string table. At this stage, strings are not
  562.     deleted */
  563. char *
  564. addStrTbl(char *pStr)
  565. {
  566.     char *p;
  567.  
  568.     if ((strTabNext + strlen(pStr) + 1) >= STRTABSIZE)
  569.     {
  570.         /* We can't realloc the old string table pointer, since that will
  571.             potentially move the string table, and pointers will be invalid.
  572.             So we realloc this one to its present usage (hopefully it won't
  573.             move), and allocate a new one */
  574.         if (reallocVar((void *)pStrTab, strTabNext) != pStrTab)
  575.         {
  576.             printf("Damn it! String table moved on shrinking!\n");
  577.             exit(1);
  578.         }
  579.         pStrTab = (char *)allocMem(STRTABSIZE);
  580.         strTabNext = 0;
  581.     }
  582.     p = strcpy(&pStrTab[strTabNext], pStr);
  583.     strTabNext += strlen(pStr) +1;
  584.     return p;
  585. }
  586.