sets.c 3.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218
  1. /* Copyright (c) 1991 by the Vrije Universiteit, Amsterdam, the Netherlands.
  2. * For full copyright and restrictions on use see the file COPYING in the top
  3. * level of the LLgen tree.
  4. */
  5. /*
  6. * L L G E N
  7. *
  8. * An Extended LL(1) Parser Generator
  9. *
  10. * Author : Ceriel J.H. Jacobs
  11. */
  12. /*
  13. * sets.c
  14. * Set manipulation and allocation routines.
  15. */
  16. # include "types.h"
  17. # include "extern.h"
  18. # include "sets.h"
  19. # include "assert.h"
  20. # ifndef NORCSID
  21. static string rcsid9 = "$Id$";
  22. # endif
  23. /* In this file the following routines are defined: */
  24. extern setinit();
  25. extern p_set setalloc();
  26. extern p_set get_set();
  27. extern int setunion();
  28. extern int setintersect();
  29. extern setminus();
  30. extern int setempty();
  31. extern int findindex();
  32. extern int setcount();
  33. int nbytes;
  34. static int setsize;
  35. int tsetsize;
  36. p_set *setptr, *maxptr;
  37. static t_info set_info;
  38. p_mem alloc();
  39. setinit(nt_needed) {
  40. /*
  41. * Initialises some variables needed for setcomputations
  42. */
  43. register int bitset;
  44. nbytes = NBYTES(ntokens);
  45. bitset = ALIGN(nbytes);
  46. tsetsize = NINTS(bitset);
  47. if (nt_needed) {
  48. /* nonterminals must be included in the sets */
  49. bitset += NBYTES(nnonterms);
  50. }
  51. setsize = NINTS(bitset);
  52. set_info.i_esize = sizeof(p_set);
  53. set_info.i_incr = 20;
  54. }
  55. p_set
  56. get_set() {
  57. /*
  58. * Allocate a set that cannot be freed
  59. */
  60. register p_set p, q;
  61. static p_set sets, maxsets;
  62. if ((p = sets) >= maxsets) {
  63. q = p = (p_set) alloc((unsigned) (50*setsize*sizeof(*sets)));
  64. maxsets = p + 50 * setsize;
  65. do {
  66. *q++ = 0;
  67. } while (q < maxsets);
  68. }
  69. sets = p + setsize;;
  70. return p;
  71. }
  72. p_set
  73. setalloc() {
  74. /*
  75. * Allocate a set which can later be freed.
  76. */
  77. register p_set p;
  78. register int size = setsize;
  79. p = (p_set) alloc((unsigned) (size * sizeof(*p))) + size;
  80. do {
  81. *--p = 0;
  82. } while (--size);
  83. return p;
  84. }
  85. int
  86. setunion(a,b) register p_set a,b; {
  87. /*
  88. * a = a union b.
  89. * Return 1 if the set a changed
  90. */
  91. register int i;
  92. register int j;
  93. register int nsub = 0;
  94. i = setsize;
  95. do {
  96. *a = (j = *a) | *b++;
  97. if (*a++ != j) {
  98. nsub = 1;
  99. }
  100. } while (--i);
  101. return nsub;
  102. }
  103. int
  104. setintersect(a,b) register p_set a,b; {
  105. /*
  106. * a = a intersect b.
  107. * return 1 if the result is empty
  108. */
  109. register int i;
  110. register int nempty;
  111. nempty = 1;
  112. i = setsize;
  113. do {
  114. if (*a++ &= *b++) nempty = 0;
  115. } while (--i);
  116. return nempty;
  117. }
  118. setminus(a,b) register p_set a,b; {
  119. /*
  120. * a = a setminus b
  121. */
  122. register int i;
  123. i = setsize;
  124. do {
  125. *a++ &= ~(*b++);
  126. } while (--i);
  127. }
  128. int
  129. setempty(p) register p_set p; {
  130. /*
  131. * Return 1 if the set p is empty
  132. */
  133. register int i;
  134. i = tsetsize;
  135. do {
  136. if (*p++) return 0;
  137. } while (--i);
  138. return 1;
  139. }
  140. int
  141. findindex(set) p_set set; {
  142. /*
  143. * The set "set" will serve as a recovery set.
  144. * Search for it in the table. If not present, enter it.
  145. * Here is room for improvement. At the moment, the list of
  146. * sets is examined with linear search.
  147. */
  148. register p_set *t;
  149. p_mem new_mem();
  150. register p_set a;
  151. register p_set b;
  152. register int i;
  153. int saved;
  154. /*
  155. * First search for the set in the table
  156. */
  157. for (t = setptr; t < maxptr; t++) {
  158. a = *t;
  159. b = set;
  160. i = tsetsize;
  161. do {
  162. if (*a++ != *b++) break;
  163. } while (--i);
  164. if (i) continue;
  165. /*
  166. * Here, the sets are equal.
  167. */
  168. return nbytes * (t - setptr);
  169. }
  170. /*
  171. * Now check if the set consists of only one element.
  172. * It would be a waste to use a set for that
  173. */
  174. if (setcount(set, &saved) == 1) return -(saved + 1);
  175. /*
  176. * If it does, return its number as a negative number.
  177. */
  178. maxptr = (p_set *) new_mem(&set_info);
  179. setptr = (p_set *) set_info.i_ptr;
  180. *maxptr = setalloc();
  181. setunion(*maxptr, set);
  182. return nbytes * (maxptr++ - setptr);
  183. }
  184. int
  185. setcount(set, saved) register p_set set; int *saved; {
  186. register int i, j;
  187. for (j = 0, i = 0; i < ntokens; i++) {
  188. if (IN(set,i)) {
  189. j++;
  190. *saved = i;
  191. }
  192. }
  193. return j;
  194. }