idf_pkg.body 3.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151
  1. /* SYMBOL TABLE HANDLING */
  2. #include <alloc.h>
  3. #define IDF_HASHSIZE 307 /* size of hashtable, must be odd */
  4. #define IDF_STARTHASH(hs) (hs = 0)
  5. #define IDF_ENHASH(hs,ch) (hs = (hs << 2) + ch)
  6. #define IDF_STOPHASH(hs) (hs = hs % IDF_HASHSIZE)
  7. static struct idf *IDF_hashtable[IDF_HASHSIZE];
  8. /* All identifiers can in principle be reached through
  9. IDF_hashtable; IDF_hashtable[hc] is the start of a chain of
  10. idf's whose tags all hash to hc.
  11. Any identifier is entered into this
  12. list, regardless of the nature of its declaration
  13. (variable, selector, structure tag, etc.).
  14. */
  15. _PROTOTYPE(static struct idf *IDF_new, (char *, int, int));
  16. void init_idf()
  17. {
  18. }
  19. static struct idf *IDF_new(char *tg, int size, int cpy)
  20. {
  21. static int nidf;
  22. static struct idf *pidf;
  23. static struct idf null_idf;
  24. register struct idf *id;
  25. #define NIDS 50
  26. #define IBUFSIZ 2048
  27. static unsigned int icnt;
  28. static char *ip;
  29. register char *p;
  30. if (! nidf--) {
  31. nidf += NIDS;
  32. pidf = (struct idf *) Malloc(NIDS * sizeof (struct idf));
  33. }
  34. id = pidf;
  35. pidf++;
  36. *id = null_idf;
  37. if (cpy) {
  38. if (size > icnt) {
  39. icnt = size > IBUFSIZ ? size : IBUFSIZ;
  40. p = Malloc(icnt);
  41. }
  42. else p = ip;
  43. icnt -= size;
  44. id->id_text = p;
  45. while (size--) {
  46. *p++ = *tg++;
  47. }
  48. ip = p;
  49. }
  50. else id->id_text = tg;
  51. return id;
  52. }
  53. #ifdef IDF_DEBUG
  54. void hash_stat()
  55. {
  56. register int i;
  57. int total_count = 0;
  58. print("Hash table tally:\n");
  59. for (i = 0; i < IDF_HASHSIZE; i++) {
  60. register struct idf *notch = IDF_hashtable[i];
  61. register int cnt = 0;
  62. print ("%d ", i);
  63. while (notch) {
  64. cnt++;
  65. print("'%s' ", notch->id_text);
  66. notch = notch->id_next;
  67. }
  68. print("%d\n", cnt);
  69. total_count += cnt;
  70. }
  71. print("total = %d\n", total_count);
  72. print("End hash table tally\n");
  73. }
  74. void idfappfun(int (*fun)(struct idf *, int), int opt)
  75. {
  76. register int i;
  77. for (i = 0; i < IDF_HASHSIZE; i++) {
  78. register struct idf *notch = IDF_hashtable[i];
  79. while (notch) {
  80. (*fun)(notch, opt);
  81. notch = notch->id_next;
  82. }
  83. }
  84. }
  85. #endif /* IDF_DEBUG */
  86. struct idf *str2idf(char tg[], int cpy)
  87. {
  88. /* str2idf() returns an entry in the symbol table for the
  89. identifier tg. If necessary, an entry is created.
  90. */
  91. register char *cp = tg;
  92. struct idf **hook;
  93. register struct idf *notch;
  94. register unsigned int hash;
  95. register int c;
  96. int size;
  97. IDF_STARTHASH(hash);
  98. while ((c = *cp++)) {
  99. IDF_ENHASH(hash, c);
  100. }
  101. IDF_STOPHASH(hash);
  102. size = cp - tg;
  103. /* The tag tg with length size and known hash value hash is
  104. looked up in the identifier table; if not found, it is
  105. entered if cpy >= 0. A pointer to it is returned.
  106. Notice that the chains of idf's are sorted alphabetically.
  107. */
  108. hook = &IDF_hashtable[hash];
  109. while ((notch = *hook)) {
  110. register char *s1 = tg;
  111. cp = notch->id_text;
  112. while (!(c = (*s1 - *cp++))) {
  113. if (*s1++ == '\0') {
  114. break;
  115. }
  116. }
  117. if (c == 0) return notch;
  118. if (c < 0) break;
  119. hook = &notch->id_next;
  120. }
  121. /* a new struct idf must be inserted at the hook */
  122. if (cpy < 0) return 0;
  123. notch = IDF_new(tg, size, cpy);
  124. notch->id_next = *hook;
  125. *hook = notch; /* hooked in */
  126. return notch;
  127. }