util/ego/share/lset.c

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