lset.c 3.6 KB

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