util/ego/share/cset.c

   1 /* $Id: cset.c,v 1.4 1994/06/24 10:29:32 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 /*  S H A R E D   F I L E
   7  *
   8  *  C S E T . C
   9  */
  10
  11
  12 #include "types.h"
  13 #include "cset.h"
  14 #include "alloc.h"
  15 #include "debug.h"
  16 #include "global.h"
  17
  18
  19 /* A set over a range of integers from 1 to N may be represented
  20  * as a 'compact' set. Such a set is represented as a 'bitvector'
  21  * record, containing the size of the set (i.e. N) and a row
  22  * of words (the bitvector itself). An integer J (1 <= J  <= N) is
  23  * an element of the set iff the J-th bit of the vector is a '1'.
  24  * Any redundant bits in the last word are garanteed to be zero bits.
  25  * This package implements the usual operations on sets.
  26  * The name of every operation is preceede by a 'C' to
  27  * distinguish it from the operation on 'long' (list)
  28  * sets whth a similar name.
  29  */
  30
  31
  32 /* The two arithmetic operations 'divide by wordlength' and
  33  * 'modulo wordlength' can be performed very efficiently
  34  * if the word length (of the source machine) is 16.
  35  */
  36
  37
  38
  39
  40 cset Cempty_set(n)
  41         short n;
  42 {
  43         cset s;
  44
  45         s = newbitvect(DIVWL(n-1) + 1);
  46         s->v_size = n;
  47         return s;
  48 }
  49
  50
  51 bool Cis_elem(x,s)
  52         Celem_t x;
  53         cset    s;
  54 {
  55         short n;
  56         int mask;
  57
  58         assert(x>0 && x <= s->v_size);
  59         n = DIVWL(x-1);
  60         mask = (1 << MODWL(x-1));
  61         if ((s->v_bits[n] & mask) == 0) {
  62                 return FALSE;
  63         } else {
  64                 return TRUE;
  65         }
  66 }
  67
  68
  69
  70 Cadd(x,s_p)
  71         Celem_t x;
  72         cset    *s_p;
  73 {
  74         cset s;
  75         short n;
  76         int mask;
  77
  78         s = *s_p;
  79         assert(x>0 && x <= s->v_size);
  80         n = DIVWL(x-1);
  81         mask = (1 << MODWL(x-1));
  82         s->v_bits[n] |= mask;
  83 }
  84
  85
  86 Cremove(x,s_p)
  87         Celem_t x;
  88         cset    *s_p;
  89 {
  90         cset s;
  91         short n;
  92         int mask;
  93
  94         s = *s_p;
  95         assert(x>0 && x <= s->v_size);
  96         n = DIVWL(x-1);
  97         mask = (1 << MODWL(x-1));
  98         s->v_bits[n] &= ~mask;
  99 }
 100
 101
 102
 103 /* The operations first, next and elem can be used to iterate
 104  * over a set. For example:
 105  *      for (i = Cfirst(s); i != (Cindex) 0; i = Cnext(i,s) {
 106  *              x = Celem(i);
 107  *              use x
 108  *      }
 109  * which is like:
 110  *      'for all elements x of s do'
 111  *              use x
 112  *
 113  * The implementation of first and next is not very fast.
 114  * It could be made much more efficient (at the price of a
 115  * higher complexity) by not using 'is_elem'.
 116  * Iteration over a bitvector, however, is not supposed to
 117  * be used very often.
 118  */
 119
 120 Cindex Cfirst(s)
 121         cset s;
 122 {
 123         return Cnext((Cindex) 0,s);
 124 }
 125
 126
 127 Cindex Cnext(i,s)
 128         Cindex i;
 129         cset   s;
 130 {
 131         register short n;
 132
 133         for (n = i+1; n <= s->v_size; n++) {
 134                 if (Cis_elem(n,s)) {
 135                         return (Cindex) n;
 136                 }
 137         }
 138         return (Cindex) 0;
 139 }
 140
 141
 142 Celem_t Celem(i)
 143         Cindex i;
 144 {
 145         return (Celem_t) i;
 146 }
 147
 148
 149
 150 Cjoin(s1,s2_p)
 151         cset s1, *s2_p;
 152 {
 153         /* Two sets are joined by or-ing their bitvectors,
 154          * word by word.
 155          */
 156
 157         cset s2;
 158         short n;
 159         register short i;
 160
 161         s2 = *s2_p;
 162         assert(s1->v_size == s2->v_size);
 163         n = DIVWL(s1->v_size -1);  /* #words -1 */
 164         for (i = 0; i <= n; i++) {
 165                 s2->v_bits[i] |= s1->v_bits[i];
 166         }
 167 }
 168
 169
 170
 171 Cintersect(s1,s2_p)
 172         cset s1, *s2_p;
 173 {
 174         /* Two sets are intersected by and-ing their bitvectors,
 175          * word by word.
 176          */
 177
 178         cset s2;
 179         short n;
 180         register short i;
 181
 182         s2 = *s2_p;
 183         assert(s1->v_size == s2->v_size);
 184         n = DIVWL(s1->v_size -1);  /* #words -1 */
 185         for (i = 0; i <= n; i++) {
 186                 s2->v_bits[i] &= s1->v_bits[i];
 187         }
 188 }
 189
 190
 191 Cdeleteset(s)
 192         cset s;
 193 {
 194         oldbitvect(s,DIVWL(s->v_size - 1) + 1);
 195 }
 196
 197
 198 bool Cis_subset(s1,s2)
 199         cset s1,s2;
 200 {
 201         /* See if s1 is a subset of s2 */
 202
 203         register short i;
 204
 205         assert(s1->v_size == s2->v_size);
 206         if (s1->v_size == 0) return TRUE;
 207         for (i = 0; i <= DIVWL(s1->v_size-1); i++) {
 208                 if ((s1->v_bits[i] & ~(s2->v_bits[i])) != 0) {
 209                         return FALSE;
 210                 }
 211         }
 212         return TRUE;
 213 }
 214
 215
 216 Cclear_set(s_p)
 217         cset *s_p;
 218 {
 219         cset s;
 220         register short i;
 221
 222         s = *s_p;
 223         assert (s != (cset) 0);
 224         for (i = 0; i <=  DIVWL(s->v_size-1); i++) {
 225                 s->v_bits[i] = 0;
 226         }
 227 }
 228
 229
 230 Ccopy_set(s1,s2_p)
 231         cset s1, *s2_p;
 232 {
 233         cset s2;
 234         register short i;
 235
 236         s2 = *s2_p;
 237         assert (s1->v_size == s2->v_size);
 238         for (i = 0; i <=  DIVWL(s1->v_size-1); i++) {
 239                 s2->v_bits[i] = s1->v_bits[i];
 240         }
 241 }
 242
 243
 244 Csubtract(s1,s2_p)
 245         cset s1, *s2_p;
 246 {
 247         cset s2;
 248         register short i;
 249
 250         s2 = *s2_p;
 251         assert (s1->v_size == s2->v_size);
 252         for (i = 0; i <=  DIVWL(s1->v_size-1); i++) {
 253                 s2->v_bits[i] &= ~(s1->v_bits[i]);
 254         }
 255 }
 256
 257
 258 bool Cequal(s1,s2)
 259         cset s1, s2;
 260 {
 261         register short i;
 262
 263         assert (s1->v_size == s2->v_size);
 264         for (i = 0; i <=  DIVWL(s1->v_size-1); i++) {
 265                 if (s1->v_bits[i] != s2->v_bits[i]) return FALSE;
 266         }
 267         return TRUE;
 268 }
 269
 270 short Cnrelems(s)
 271         cset s;
 272 {
 273         register short n, cnt;
 274
 275         cnt = 0;
 276         for (n = 1; n <= s->v_size; n++) {
 277                 if (Cis_elem(n,s)) {
 278                         cnt++;
 279                 }
 280         }
 281         return cnt;
 282 }