symtab.cpp 18 KB

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