lset.c 3.6 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199
  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(Lelem_t x, lset s)
  32. {
  33. /* Search the list to see if x is an element of s */
  34. while (s != (elem_p) 0) {
  35. if (s->e_elem == x) {
  36. return TRUE;
  37. }
  38. s = s->e_next;
  39. }
  40. return FALSE;
  41. }
  42. void Ladd(Lelem_t x, lset *s_p)
  43. {
  44. /* add x to a set. Note that the set is given as in-out
  45. * parameter, because it may be changed.
  46. */
  47. elem_p t;
  48. if (!Lis_elem(x,*s_p)) {
  49. t = newelem(); /* allocate a new elemholder */
  50. t->e_elem = x;
  51. t->e_next = *s_p; /* insert it at the head of the list */
  52. *s_p = t;
  53. }
  54. }
  55. void Lremove(Lelem_t x, lset *s_p)
  56. {
  57. /* Remove x from a set. If x was not an element of
  58. * the set, nothing happens.
  59. */
  60. register elem_p *epp, ep;
  61. lset s;
  62. s = *s_p;
  63. epp = &s;
  64. while ((ep = *epp) != (elem_p) 0) {
  65. if (ep->e_elem == x) {
  66. *epp = ep->e_next;
  67. oldelem(ep);
  68. break;
  69. } else {
  70. epp = &ep->e_next;
  71. }
  72. }
  73. *s_p = s;
  74. }
  75. /* The operations first, next and elem can be used to iterate
  76. * over a set. For example:
  77. * for (i = Lfirst(s); i != (Lindex) 0; i = Lnext(i,s) {
  78. * x = Lelem(i);
  79. * use x
  80. * }
  81. * which is like:
  82. * 'for all elements x of s do'
  83. * use x
  84. */
  85. Lindex Lfirst(lset s)
  86. {
  87. return ((Lindex) s);
  88. /* Note that an index for long sets is just
  89. * a pointer to an elemholder.
  90. */
  91. }
  92. /*ARGSUSED1*/
  93. Lindex Lnext(Lindex i, lset s)
  94. {
  95. assert(i != (Lindex) 0);
  96. return (i->e_next);
  97. }
  98. Lelem_t Lelem(Lindex i)
  99. {
  100. return (i->e_elem);
  101. }
  102. void Ljoin(lset s1, lset *s2_p)
  103. {
  104. /* Join two sets, assign the result to the second set
  105. * and delete the first set (i.e. the value of the
  106. * first set becomes undefined).
  107. */
  108. elem_p *epp, ep;
  109. lset s2;
  110. /* First all elements of s1 that are also an element of s2
  111. * are removed from the s1 list. The two resulting lists
  112. * (for s1 and s2) are linked (s1 first).
  113. * Note the usage of epp, which points to a pointer that
  114. * points to the next elemholder record of the list.
  115. */
  116. s2 = *s2_p;
  117. epp = &s1;
  118. while ((ep = *epp) != (elem_p) 0) {
  119. if (Lis_elem(ep->e_elem,s2)) {
  120. /* remove an element */
  121. *epp = ep->e_next;
  122. oldelem(ep);
  123. } else {
  124. epp = &ep->e_next;
  125. }
  126. }
  127. *epp = s2; /* last record of s1 (or s1 itself) now points
  128. * to first record of s2.
  129. */
  130. *s2_p = s1;
  131. }
  132. void Ldeleteset(lset s)
  133. {
  134. elem_p ep, next;
  135. for (ep = s; ep != (elem_p) 0; ep = next) {
  136. next = ep->e_next;
  137. oldelem(ep);
  138. }
  139. }
  140. bool Lis_subset(lset s1, lset s2)
  141. {
  142. /* See if s1 is a subset of s2 */
  143. Lindex i;
  144. for (i = Lfirst(s1); i != (Lindex) 0; i = Lnext(i,s1)) {
  145. if (!Lis_elem(Lelem(i),s2)) return FALSE;
  146. }
  147. return TRUE;
  148. }
  149. short Lnrelems(lset s)
  150. {
  151. /* Compute the number of elements of a set */
  152. elem_p ep;
  153. short cnt;
  154. cnt = 0;
  155. for (ep = s; ep != (elem_p) 0; ep = ep->e_next) {
  156. cnt++;
  157. }
  158. return cnt;
  159. }