gnu/lib/libg++/g++-include/BitSet.h

   1 // This may look like C code, but it is really -*- C++ -*-
   2 /*
   3 Copyright (C) 1988 Free Software Foundation
   4     written by Doug Lea (dl@rocky.oswego.edu)
   5
   6 This file is part of GNU CC.
   7
   8 GNU CC is distributed in the hope that it will be useful,
   9 but WITHOUT ANY WARRANTY.  No author or distributor
  10 accepts responsibility to anyone for the consequences of using it
  11 or for whether it serves any particular purpose or works at all,
  12 unless he says so in writing.  Refer to the GNU CC General Public
  13 License for full details.
  14
  15 Everyone is granted permission to copy, modify and redistribute
  16 GNU CC, but only under the conditions described in the
  17 GNU CC General Public License.   A copy of this license is
  18 supposed to have been given to you along with GNU CC so you
  19 can know your rights and responsibilities.  It should be in a
  20 file named COPYING.  Among other things, the copyright notice
  21 and this notice must be preserved on all copies.
  22 */
  23
  24 #ifndef _BitSet_h
  25 #ifdef __GNUG__
  26 #pragma once
  27 #pragma interface
  28 #endif
  29
  30 #define _BitSet_h 1
  31
  32 #include <stream.h>
  33 #include <values.h>
  34
  35 #define BITSETBITS  BITS(short)
  36
  37 struct BitSetRep
  38 {
  39   unsigned short  len;          // number of shorts in s
  40   unsigned short  sz;           // allocated slots
  41   unsigned short  virt;         // virtual 0 or 1
  42   unsigned short  s[1];         // bits start here
  43 };
  44
  45 extern BitSetRep*   BitSetalloc(BitSetRep*, const unsigned short*,
  46                                 int, int, int);
  47 extern BitSetRep*   BitSetcopy(BitSetRep*, const BitSetRep*);
  48 extern BitSetRep*   BitSetresize(BitSetRep*, int);
  49 extern BitSetRep*   BitSetop(const BitSetRep*, const BitSetRep*,
  50                              BitSetRep*, char);
  51 extern BitSetRep*   BitSetcmpl(const BitSetRep*, BitSetRep*);
  52
  53
  54 extern BitSetRep    _nilBitSetRep;
  55
  56 class BitSet;
  57
  58 class BitSetBit
  59 {
  60 protected:
  61   BitSet*            src;
  62   unsigned long      pos;
  63
  64  public:
  65                      BitSetBit(BitSet* v, int p);
  66                      BitSetBit(const BitSetBit& b);
  67                     ~BitSetBit();
  68                      operator int();
  69   int                operator = (int b);
  70   int                operator == (int b);
  71   int                operator != (int b);
  72 };
  73
  74 class BitSet
  75 {
  76 protected:
  77   BitSetRep*          rep;
  78
  79
  80 public:
  81
  82 // constructors
  83                      BitSet();
  84                      BitSet(const BitSet&);
  85
  86                     ~BitSet();
  87
  88   void               operator =  (const BitSet& y);
  89
  90 // equality & subset tests
  91
  92   friend int         operator == (const BitSet& x, const BitSet& y);
  93   friend int         operator != (const BitSet& x, const BitSet& y);
  94   friend int         operator <  (const BitSet& x, const BitSet& y);
  95   friend int         operator <= (const BitSet& x, const BitSet& y);
  96   friend int         operator >  (const BitSet& x, const BitSet& y);
  97   friend int         operator >= (const BitSet& x, const BitSet& y);
  98
  99
 100 // operations on self
 101
 102   void               operator |= (const BitSet& y);
 103   void               operator &= (const BitSet& y);
 104   void               operator -= (const BitSet& y);
 105   void               operator ^= (const BitSet& y);
 106
 107   void               complement();
 108
 109 // individual bit manipulation
 110
 111   void               set(int pos);
 112   void               set(int from, int to);
 113   void               set(); // set all
 114
 115   void               clear(int pos);
 116   void               clear(int from, int to);
 117   void               clear(); // clear all
 118
 119   void               invert(int pos);
 120   void               invert(int from, int to);
 121
 122   int                test(int pos) const;
 123   int                test(int from, int to) const;
 124
 125   BitSetBit          operator [] (int i);
 126
 127 // iterators
 128
 129   int                first(int b = 1) const;
 130   int                last(int b = 1) const;
 131
 132   int                next(int pos, int b = 1) const;
 133   int                previous(int pos, int b = 1) const;
 134
 135 // status
 136
 137   int                empty() const;
 138   int                virtual_bit() const;
 139   int                count(int b = 1) const;
 140
 141 // convertors & IO
 142
 143   friend BitSet      atoBitSet(const char* s,
 144                                char f='0', char t='1', char star='*');
 145   friend const char* BitSettoa(const BitSet& x,
 146                                char f='0', char t='1', char star='*');
 147
 148   friend BitSet      shorttoBitSet(unsigned short w);
 149   friend BitSet      longtoBitSet(unsigned long w);
 150
 151   friend ostream&    operator << (ostream& s, const BitSet& x);
 152
 153 // procedural versions of operators
 154
 155   friend void        and(const BitSet& x, const BitSet& y, BitSet& r);
 156   friend void        or(const BitSet& x, const BitSet& y, BitSet& r);
 157   friend void        xor(const BitSet& x, const BitSet& y, BitSet& r);
 158   friend void        diff(const BitSet& x, const BitSet& y, BitSet& r);
 159   friend void        complement(const BitSet& x, BitSet& r);
 160
 161 // misc
 162
 163   volatile void      error(const char* msg) const;
 164   int                OK() const;
 165 };
 166
 167
 168 typedef BitSet BitSetTmp;
 169
 170
 171   BitSet      operator |  (const BitSet& x, const BitSet& y);
 172   BitSet      operator &  (const BitSet& x, const BitSet& y);
 173   BitSet      operator -  (const BitSet& x, const BitSet& y);
 174   BitSet      operator ^  (const BitSet& x, const BitSet& y);
 175
 176   BitSet      operator ~  (const BitSet& x);
 177
 178 // These are inlined regardless of optimization
 179
 180 inline int BitSet_index(int l)
 181 {
 182   return (unsigned)(l) / BITSETBITS;
 183 }
 184
 185 inline int BitSet_pos(int l)
 186 {
 187   return l & (BITSETBITS - 1);
 188 }
 189
 190 #if defined(__OPTIMIZE__) || defined(USE_LIBGXX_INLINES)
 191
 192
 193 inline BitSet::BitSet() : rep(&_nilBitSetRep) {}
 194
 195 inline BitSet::BitSet(const BitSet& x) :rep(BitSetcopy(0, x.rep)) {}
 196
 197 inline BitSet::~BitSet() { if (rep != &_nilBitSetRep) delete rep; }
 198
 199 inline void BitSet::operator =  (const BitSet& y)
 200 {
 201   rep = BitSetcopy(rep, y.rep);
 202 }
 203
 204 inline int operator != (const BitSet& x, const BitSet& y) { return !(x == y); }
 205
 206 inline int operator >  (const BitSet& x, const BitSet& y) { return y < x; }
 207
 208 inline int operator >= (const BitSet& x, const BitSet& y) { return y <= x; }
 209
 210 inline void and(const BitSet& x, const BitSet& y, BitSet& r)
 211 {
 212   r.rep =  BitSetop(x.rep, y.rep, r.rep, '&');
 213 }
 214
 215 inline void or(const BitSet& x, const BitSet& y, BitSet& r)
 216 {
 217   r.rep =  BitSetop(x.rep, y.rep, r.rep, '|');
 218 }
 219
 220 inline void xor(const BitSet& x, const BitSet& y, BitSet& r)
 221 {
 222   r.rep =  BitSetop(x.rep, y.rep, r.rep, '^');
 223 }
 224
 225 inline void diff(const BitSet& x, const BitSet& y, BitSet& r)
 226 {
 227   r.rep =  BitSetop(x.rep, y.rep, r.rep, '-');
 228 }
 229
 230 inline void complement(const BitSet& x, BitSet& r)
 231 {
 232   r.rep = BitSetcmpl(x.rep, r.rep);
 233 }
 234
 235 #if defined(__GNUG__) && !defined(NO_NRV)
 236
 237 inline BitSet operator & (const BitSet& x, const BitSet& y) return r
 238 {
 239   and(x, y, r);
 240 }
 241
 242 inline BitSet operator | (const BitSet& x, const BitSet& y) return r
 243 {
 244   or(x, y, r);
 245 }
 246
 247 inline BitSet operator ^ (const BitSet& x, const BitSet& y) return r
 248 {
 249   xor(x, y, r);
 250 }
 251
 252 inline BitSet operator - (const BitSet& x, const BitSet& y) return r
 253 {
 254   diff(x, y, r);
 255 }
 256
 257 inline BitSet operator ~ (const BitSet& x) return r
 258 {
 259   ::complement(x, r);
 260 }
 261
 262 #else /* NO_NRV */
 263
 264 inline BitSet operator & (const BitSet& x, const BitSet& y)
 265 {
 266   BitSet r; and(x, y, r); return r;
 267 }
 268
 269 inline BitSet operator | (const BitSet& x, const BitSet& y)
 270 {
 271   BitSet r; or(x, y, r); return r;
 272 }
 273
 274 inline BitSet operator ^ (const BitSet& x, const BitSet& y)
 275 {
 276   BitSet r; xor(x, y, r); return r;
 277 }
 278
 279 inline BitSet operator - (const BitSet& x, const BitSet& y)
 280 {
 281   BitSet r; diff(x, y, r); return r;
 282 }
 283
 284 inline BitSet operator ~ (const BitSet& x)
 285 {
 286   BitSet r; ::complement(x, r); return r;
 287 }
 288
 289 #endif
 290
 291 inline void BitSet::operator &= (const BitSet& y)
 292 {
 293   and(*this, y, *this);
 294 }
 295
 296 inline void BitSet::operator |= (const BitSet& y)
 297 {
 298   or(*this, y, *this);
 299 }
 300
 301 inline void BitSet::operator ^= (const BitSet& y)
 302 {
 303   xor(*this, y, *this);
 304 }
 305
 306 inline void BitSet::operator -= (const BitSet& y)
 307 {
 308   diff(*this, y, *this);
 309 }
 310
 311
 312 inline void BitSet::complement()
 313 {
 314   ::complement(*this, *this);
 315 }
 316
 317 inline int BitSet::virtual_bit() const
 318 {
 319   return rep->virt;
 320 }
 321
 322 inline int BitSet::first(int b) const
 323 {
 324   return next(-1, b);
 325 }
 326
 327 inline int BitSet::test(int p) const
 328 {
 329   if (p < 0) error("Illegal bit index");
 330   int index = BitSet_index(p);
 331   return (index >= rep->len)? rep->virt :
 332          ((rep->s[index] & (1 << BitSet_pos(p))) != 0);
 333 }
 334
 335
 336 inline void BitSet::clear()
 337 {
 338   if (rep->len > 0) bzero(rep->s, rep->sz * sizeof(short));
 339   rep->len = rep->virt = 0;
 340 }
 341
 342 inline void BitSet::set()
 343 {
 344   rep = BitSetalloc(rep, 0, 0, 1, 0);
 345 }
 346
 347 inline BitSetBit::BitSetBit(const BitSetBit& b) :src(b.src), pos(b.pos) {}
 348
 349 inline BitSetBit::BitSetBit(BitSet* v, int p)
 350 {
 351   src = v;  pos = p;
 352 }
 353
 354 inline BitSetBit::~BitSetBit() {}
 355
 356 inline BitSetBit::operator int()
 357 {
 358   return src->test(pos);
 359 }
 360
 361 inline int BitSetBit::operator = (int b)
 362 {
 363   if (b) src->set(pos); else src->clear(pos); return b;
 364 }
 365
 366 inline int BitSetBit::operator == (int b)
 367 {
 368   return src->test(pos) == b;
 369 }
 370
 371 inline int BitSetBit::operator != (int b)
 372 {
 373   return src->test(pos) != b;
 374 }
 375
 376 inline BitSetBit BitSet::operator [] (int i)
 377 {
 378   if (i < 0) error("illegal bit index");
 379   return BitSetBit(this, i);
 380 }
 381
 382
 383
 384 #endif
 385 #endif