lset.c 3.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214
  1. /* $Id$ */
  2. /*
  3. * (c) copyright 1987 by the Vrije Universiteit, Amsterdam, The Netherlands.
  4. * See the copyright notice in the ACK home directory, in the file "Copyright".
  5. */
  6. /* L O N G S E T S
  7. *
  8. * L S E T . C
  9. */
  10. #include "types.h"
  11. #include "lset.h"
  12. #include "alloc.h"
  13. #include "debug.h"
  14. /* A 'long' set is represented as a linear list of 'elemholder'
  15. * records. Every such record contains a pointer to an element
  16. * of the set and to the next elemholder. An empty set is
  17. * represented as a null pointer.
  18. * An element of a long set must be of some pointer type or,
  19. * in any case, must have the size of a pointer. Note that
  20. * the strict typing rules are not obeyed here.
  21. * This package implements the usual operations on sets.
  22. * The name of every operation is preceeded by a 'L' to
  23. * distinguish it from the operation on 'compact' (bitvector)
  24. * sets with a similar name.
  25. */
  26. lset Lempty_set()
  27. {
  28. return ((lset) 0);
  29. }
  30. bool Lis_elem(x,s)
  31. register Lelem_t x;
  32. register lset s;
  33. {
  34. /* Search the list to see if x is an element of s */
  35. while (s != (elem_p) 0) {
  36. if (s->e_elem == x) {
  37. return TRUE;
  38. }
  39. s = s->e_next;
  40. }
  41. return FALSE;
  42. }
  43. Ladd(x,s_p)
  44. Lelem_t x;
  45. lset *s_p;
  46. {
  47. /* add x to a set. Note that the set is given as in-out
  48. * parameter, because it may be changed.
  49. */
  50. elem_p t;
  51. if (!Lis_elem(x,*s_p)) {
  52. t = newelem(); /* allocate a new elemholder */
  53. t->e_elem = x;
  54. t->e_next = *s_p; /* insert it at the head of the list */
  55. *s_p = t;
  56. }
  57. }
  58. Lremove(x,s_p)
  59. Lelem_t x;
  60. lset *s_p;
  61. {
  62. /* Remove x from a set. If x was not an element of
  63. * the set, nothing happens.
  64. */
  65. register elem_p *epp, ep;
  66. lset s;
  67. s = *s_p;
  68. epp = &s;
  69. while ((ep = *epp) != (elem_p) 0) {
  70. if (ep->e_elem == x) {
  71. *epp = ep->e_next;
  72. oldelem(ep);
  73. break;
  74. } else {
  75. epp = &ep->e_next;
  76. }
  77. }
  78. *s_p = s;
  79. }
  80. /* The operations first, next and elem can be used to iterate
  81. * over a set. For example:
  82. * for (i = Lfirst(s); i != (Lindex) 0; i = Lnext(i,s) {
  83. * x = Lelem(i);
  84. * use x
  85. * }
  86. * which is like:
  87. * 'for all elements x of s do'
  88. * use x
  89. */
  90. Lindex Lfirst(s)
  91. lset s;
  92. {
  93. return ((Lindex) s);
  94. /* Note that an index for long sets is just
  95. * a pointer to an elemholder.
  96. */
  97. }
  98. /*ARGSUSED1*/
  99. Lindex Lnext(i,s)
  100. Lindex i;
  101. lset s;
  102. {
  103. assert(i != (Lindex) 0);
  104. return (i->e_next);
  105. }
  106. Lelem_t Lelem(i)
  107. Lindex i;
  108. {
  109. return (i->e_elem);
  110. }
  111. Ljoin(s1,s2_p)
  112. lset s1,*s2_p;
  113. {
  114. /* Join two sets, assign the result to the second set
  115. * and delete the first set (i.e. the value of the
  116. * first set becomes undefined).
  117. */
  118. register elem_p *epp, ep;
  119. lset s2;
  120. /* First all elements of s1 that are also an element of s2
  121. * are removed from the s1 list. The two resulting lists
  122. * (for s1 and s2) are linked (s1 first).
  123. * Note the usage of epp, which points to a pointer that
  124. * points to the next elemholder record of the list.
  125. */
  126. s2 = *s2_p;
  127. epp = &s1;
  128. while ((ep = *epp) != (elem_p) 0) {
  129. if (Lis_elem(ep->e_elem,s2)) {
  130. /* remove an element */
  131. *epp = ep->e_next;
  132. oldelem(ep);
  133. } else {
  134. epp = &ep->e_next;
  135. }
  136. }
  137. *epp = s2; /* last record of s1 (or s1 itself) now points
  138. * to first record of s2.
  139. */
  140. *s2_p = s1;
  141. }
  142. Ldeleteset(s)
  143. lset s;
  144. {
  145. register elem_p ep, next;
  146. for (ep = s; ep != (elem_p) 0; ep = next) {
  147. next = ep->e_next;
  148. oldelem(ep);
  149. }
  150. }
  151. bool Lis_subset(s1,s2)
  152. lset s1,s2;
  153. {
  154. /* See if s1 is a subset of s2 */
  155. register Lindex i;
  156. for (i = Lfirst(s1); i != (Lindex) 0; i = Lnext(i,s1)) {
  157. if (!Lis_elem(Lelem(i),s2)) return FALSE;
  158. }
  159. return TRUE;
  160. }
  161. short Lnrelems(s)
  162. lset s;
  163. {
  164. /* Compute the number of elements of a set */
  165. register elem_p ep;
  166. register short cnt;
  167. cnt = 0;
  168. for (ep = s; ep != (elem_p) 0; ep = ep->e_next) {
  169. cnt++;
  170. }
  171. return cnt;
  172. }