sets.c 3.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201
  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 <stdlib.h>
  17. #include <stdio.h>
  18. # include "types.h"
  19. # include "extern.h"
  20. # include "sets.h"
  21. # include "assert.h"
  22. #include "LLgen.h"
  23. /* In this file the following routines are defined: */
  24. int nbytes;
  25. static int setsize;
  26. int tsetsize;
  27. p_set *setptr, *maxptr;
  28. static t_info set_info;
  29. void setinit(int nt_needed) {
  30. /*
  31. * Initialises some variables needed for setcomputations
  32. */
  33. register int bitset;
  34. nbytes = NBYTES(ntokens);
  35. bitset = ALIGN(nbytes);
  36. tsetsize = NINTS(bitset);
  37. if (nt_needed) {
  38. /* nonterminals must be included in the sets */
  39. bitset += NBYTES(nnonterms);
  40. }
  41. setsize = NINTS(bitset);
  42. set_info.i_esize = sizeof(p_set);
  43. set_info.i_incr = 20;
  44. }
  45. p_set get_set() {
  46. /*
  47. * Allocate a set that cannot be freed
  48. */
  49. register p_set p, q;
  50. static p_set sets, maxsets;
  51. if ((p = sets) >= maxsets) {
  52. q = p = (p_set) alloc((unsigned) (50*setsize*sizeof(*sets)));
  53. maxsets = p + 50 * setsize;
  54. do {
  55. *q++ = 0;
  56. } while (q < maxsets);
  57. }
  58. sets = p + setsize;;
  59. return p;
  60. }
  61. p_set setalloc() {
  62. /*
  63. * Allocate a set which can later be freed.
  64. */
  65. register p_set p;
  66. register int size = setsize;
  67. p = (p_set) alloc((unsigned) (size * sizeof(*p))) + size;
  68. do {
  69. *--p = 0;
  70. } while (--size);
  71. return p;
  72. }
  73. int setunion(p_set a, p_set b) {
  74. /*
  75. * a = a union b.
  76. * Return 1 if the set a changed
  77. */
  78. register int i;
  79. register int j;
  80. register int nsub = 0;
  81. i = setsize;
  82. do {
  83. *a = (j = *a) | *b++;
  84. if (*a++ != j) {
  85. nsub = 1;
  86. }
  87. } while (--i);
  88. return nsub;
  89. }
  90. int setintersect(p_set a, p_set b) {
  91. /*
  92. * a = a intersect b.
  93. * return 1 if the result is empty
  94. */
  95. register int i;
  96. register int nempty;
  97. nempty = 1;
  98. i = setsize;
  99. do {
  100. if (*a++ &= *b++) nempty = 0;
  101. } while (--i);
  102. return nempty;
  103. }
  104. void setminus(p_set a, p_set b) {
  105. /*
  106. * a = a setminus b
  107. */
  108. register int i;
  109. i = setsize;
  110. do {
  111. *a++ &= ~(*b++);
  112. } while (--i);
  113. }
  114. int setempty(p_set p) {
  115. /*
  116. * Return 1 if the set p is empty
  117. */
  118. register int i;
  119. i = tsetsize;
  120. do {
  121. if (*p++) return 0;
  122. } while (--i);
  123. return 1;
  124. }
  125. int findindex(p_set set) {
  126. /*
  127. * The set "set" will serve as a recovery set.
  128. * Search for it in the table. If not present, enter it.
  129. * Here is room for improvement. At the moment, the list of
  130. * sets is examined with linear search.
  131. */
  132. register p_set *t;
  133. p_mem new_mem();
  134. register p_set a;
  135. register p_set b;
  136. register int i;
  137. int saved;
  138. /*
  139. * First search for the set in the table
  140. */
  141. for (t = setptr; t < maxptr; t++) {
  142. a = *t;
  143. b = set;
  144. i = tsetsize;
  145. do {
  146. if (*a++ != *b++) break;
  147. } while (--i);
  148. if (i) continue;
  149. /*
  150. * Here, the sets are equal.
  151. */
  152. return nbytes * (t - setptr);
  153. }
  154. /*
  155. * Now check if the set consists of only one element.
  156. * It would be a waste to use a set for that
  157. */
  158. if (setcount(set, &saved) == 1) return -(saved + 1);
  159. /*
  160. * If it does, return its number as a negative number.
  161. */
  162. maxptr = (p_set *) new_mem(&set_info);
  163. setptr = (p_set *) set_info.i_ptr;
  164. *maxptr = setalloc();
  165. setunion(*maxptr, set);
  166. return nbytes * (maxptr++ - setptr);
  167. }
  168. int setcount(p_set set, int *saved) {
  169. register int i, j;
  170. for (j = 0, i = 0; i < ntokens; i++) {
  171. if (IN(set,i)) {
  172. j++;
  173. *saved = i;
  174. }
  175. }
  176. return j;
  177. }