idf_pkg.body 3.1 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161
  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
  17. init_idf()
  18. {
  19. }
  20. static struct idf *
  21. IDF_new(tg, size, cpy)
  22. register char *tg;
  23. register int size;
  24. {
  25. static int nidf;
  26. static struct idf *pidf;
  27. static struct idf null_idf;
  28. register struct idf *id;
  29. #define NIDS 50
  30. #define IBUFSIZ 2048
  31. static unsigned int icnt;
  32. static char *ip;
  33. register char *p;
  34. if (! nidf--) {
  35. nidf += NIDS;
  36. pidf = (struct idf *) Malloc(NIDS * sizeof (struct idf));
  37. }
  38. id = pidf;
  39. pidf++;
  40. *id = null_idf;
  41. if (cpy) {
  42. if (size > icnt) {
  43. icnt = size > IBUFSIZ ? size : IBUFSIZ;
  44. p = Malloc(icnt);
  45. }
  46. else p = ip;
  47. icnt -= size;
  48. id->id_text = p;
  49. while (size--) {
  50. *p++ = *tg++;
  51. }
  52. ip = p;
  53. }
  54. else id->id_text = tg;
  55. return id;
  56. }
  57. #ifdef IDF_DEBUG
  58. void
  59. hash_stat()
  60. {
  61. register int i;
  62. int total_count = 0;
  63. print("Hash table tally:\n");
  64. for (i = 0; i < IDF_HASHSIZE; i++) {
  65. register struct idf *notch = IDF_hashtable[i];
  66. register int cnt = 0;
  67. print ("%d ", i);
  68. while (notch) {
  69. cnt++;
  70. print("'%s' ", notch->id_text);
  71. notch = notch->id_next;
  72. }
  73. print("%d\n", cnt);
  74. total_count += cnt;
  75. }
  76. print("total = %d\n", total_count);
  77. print("End hash table tally\n");
  78. }
  79. void
  80. idfappfun(fun, opt)
  81. int (*fun)();
  82. int opt;
  83. {
  84. register int i;
  85. for (i = 0; i < IDF_HASHSIZE; i++) {
  86. register struct idf *notch = IDF_hashtable[i];
  87. while (notch) {
  88. (*fun)(notch, opt);
  89. notch = notch->id_next;
  90. }
  91. }
  92. }
  93. #endif /* IDF_DEBUG */
  94. struct idf *
  95. str2idf(tg, cpy)
  96. char tg[];
  97. {
  98. /* str2idf() returns an entry in the symbol table for the
  99. identifier tg. If necessary, an entry is created.
  100. */
  101. register char *cp = tg;
  102. struct idf **hook;
  103. register struct idf *notch;
  104. register unsigned int hash;
  105. register int c;
  106. int size;
  107. IDF_STARTHASH(hash);
  108. while (c = *cp++) {
  109. IDF_ENHASH(hash, c);
  110. }
  111. IDF_STOPHASH(hash);
  112. size = cp - tg;
  113. /* The tag tg with length size and known hash value hash is
  114. looked up in the identifier table; if not found, it is
  115. entered if cpy >= 0. A pointer to it is returned.
  116. Notice that the chains of idf's are sorted alphabetically.
  117. */
  118. hook = &IDF_hashtable[hash];
  119. while ((notch = *hook)) {
  120. register char *s1 = tg;
  121. cp = notch->id_text;
  122. while (!(c = (*s1 - *cp++))) {
  123. if (*s1++ == '\0') {
  124. break;
  125. }
  126. }
  127. if (c == 0) return notch;
  128. if (c < 0) break;
  129. hook = &notch->id_next;
  130. }
  131. /* a new struct idf must be inserted at the hook */
  132. if (cpy < 0) return 0;
  133. notch = IDF_new(tg, size, cpy);
  134. notch->id_next = *hook;
  135. *hook = notch; /* hooked in */
  136. return notch;
  137. }