symtab.cpp 20 KB

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