lset.c 3.7 KB

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