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
BitSet_index(int l)180 inline int BitSet_index(int l)
181 {
182 return (unsigned)(l) / BITSETBITS;
183 }
184
BitSet_pos(int l)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
BitSet()193 inline BitSet::BitSet() : rep(&_nilBitSetRep) {}
194
BitSet(const BitSet & x)195 inline BitSet::BitSet(const BitSet& x) :rep(BitSetcopy(0, x.rep)) {}
196
~BitSet()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
and(const BitSet & x,const BitSet & y,BitSet & r)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
or(const BitSet & x,const BitSet & y,BitSet & r)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
xor(const BitSet & x,const BitSet & y,BitSet & r)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
diff(const BitSet & x,const BitSet & y,BitSet & r)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
complement(const BitSet & x,BitSet & r)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
386