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 _BitString_h
25 #ifdef __GNUG__
26 #pragma once
27 #pragma interface
28 #endif
29
30 #define _BitString_h 1
31
32 #include <stream.h>
33 #include <values.h>
34
35 #define BITSTRBITS BITS(short)
36
37 struct BitStrRep
38 {
39 unsigned int len; // length in bits
40 unsigned short sz; // allocated slots
41 unsigned short s[1]; // bits start here
42 };
43
44 extern BitStrRep* BStr_alloc(BitStrRep*, const unsigned short*, int, int,int);
45 extern BitStrRep* BStr_resize(BitStrRep*, int);
46 extern BitStrRep* BStr_copy(BitStrRep*, const BitStrRep*);
47 extern BitStrRep* cmpl(const BitStrRep*, BitStrRep*);
48 extern BitStrRep* and(const BitStrRep*, const BitStrRep*, BitStrRep*);
49 extern BitStrRep* or(const BitStrRep*, const BitStrRep*, BitStrRep*);
50 extern BitStrRep* xor(const BitStrRep*, const BitStrRep*, BitStrRep*);
51 extern BitStrRep* diff(const BitStrRep*, const BitStrRep*, BitStrRep*);
52 extern BitStrRep* cat(const BitStrRep*, const BitStrRep*, BitStrRep*);
53 extern BitStrRep* cat(const BitStrRep*, unsigned int, BitStrRep*);
54 extern BitStrRep* lshift(const BitStrRep*, int, BitStrRep*);
55
56
57 class BitString;
58 class BitPattern;
59
60 class BitStrBit
61 {
62 protected:
63 BitString& src;
64 unsigned int pos;
65
66 public:
67 BitStrBit(BitString& v, int p);
68 BitStrBit(const BitStrBit& b);
69 ~BitStrBit();
70 operator unsigned int() const;
71 int operator = (unsigned int b);
72 int operator == (unsigned int b) const ;
73 int operator != (unsigned int b) const ;
74 };
75
76 class BitSubString
77 {
78 friend class BitString;
79 friend class BitPattern;
80
81 protected:
82
83 BitString& S;
84 int pos;
85 int len;
86
87 BitSubString(BitString& x, int p, int l);
88 BitSubString(const BitSubString& x);
89 public:
90 ~BitSubString();
91
92 void operator = (const BitString&);
93 void operator = (const BitSubString&);
94
95 int length() const;
96 int empty() const;
97
98 int OK() const;
99 };
100
101 class BitString
102 {
103 friend class BitSubString;
104 friend class BitPattern;
105 protected:
106 BitStrRep* rep;
107
108 int search(int, int, const unsigned short*, int, int) const;
109 int match(int, int, int, const unsigned short*,int,int) const;
110 BitSubString _substr(int first, int l);
111
112 public:
113
114 // constructors
115 BitString();
116 BitString(const BitString&);
117 BitString(const BitSubString& y);
118
119 ~BitString();
120
121 void operator = (unsigned int bit);
122 void operator = (const BitString& y);
123 void operator = (const BitSubString& y);
124
125 // equality & subset tests
126
127 friend int operator == (const BitString&, const BitString&);
128 friend int operator != (const BitString&, const BitString&);
129 friend int operator < (const BitString&, const BitString&);
130 friend int operator <= (const BitString&, const BitString&);
131 friend int operator > (const BitString&, const BitString&);
132 friend int operator >= (const BitString&, const BitString&);
133
134 // procedural versions of operators
135
136
137 friend void and(const BitString&, const BitString&, BitString&);
138 friend void or(const BitString&, const BitString&, BitString&);
139 friend void xor(const BitString&, const BitString&, BitString&);
140 friend void diff(const BitString&, const BitString&, BitString&);
141 friend void cat(const BitString&, const BitString&, BitString&);
142 friend void cat(const BitString&, unsigned int, BitString&);
143 friend void lshift(const BitString&, int, BitString&);
144 friend void rshift(const BitString&, int, BitString&);
145
146 friend void complement(const BitString&, BitString&);
147
148 friend int lcompare(const BitString&, const BitString&);
149
150 // assignment-based operators
151 // (constuctive versions decalred inline below
152
153 void operator |= (const BitString&);
154 void operator &= (const BitString&);
155 void operator -= (const BitString&);
156 void operator ^= (const BitString&);
157 void operator += (const BitString&);
158 void operator += (unsigned int b);
159 void operator <<=(int s);
160 void operator >>=(int s);
161
162 void complement();
163
164 // individual bit manipulation
165
166 void set(int pos);
167 void set(int from, int to);
168 void set();
169
170 void clear(int pos);
171 void clear(int from, int to);
172 void clear();
173
174 void invert(int pos);
175 void invert(int from, int to);
176
177 int test(int pos) const;
178 int test(int from, int to) const;
179
180 void assign(int p, unsigned int bit);
181
182 // indexing
183
184 BitStrBit operator [] (int pos);
185
186 // iterators
187
188 int first(unsigned int bit = 1) const;
189 int last(unsigned int b = 1) const;
190
191 int next(int pos, unsigned int b = 1) const;
192 int previous(int pos, unsigned int b = 1) const;
193
194 // searching & matching
195
196 int index(unsigned int bit, int startpos = 0) const ;
197 int index(const BitString&, int startpos = 0) const;
198 int index(const BitSubString&, int startpos = 0) const;
199 int index(const BitPattern&, int startpos = 0) const;
200
201 int contains(const BitString&) const;
202 int contains(const BitSubString&) const;
203 int contains(const BitPattern&) const;
204
205 int contains(const BitString&, int pos) const;
206 int contains(const BitSubString&, int pos) const;
207 int contains(const BitPattern&, int pos) const;
208
209 int matches(const BitString&, int pos = 0) const;
210 int matches(const BitSubString&, int pos = 0) const;
211 int matches(const BitPattern&, int pos = 0) const;
212
213 // BitSubString extraction
214
215 BitSubString at(int pos, int len);
216 BitSubString at(const BitString&, int startpos = 0);
217 BitSubString at(const BitSubString&, int startpos = 0);
218 BitSubString at(const BitPattern&, int startpos = 0);
219
220 BitSubString before(int pos);
221 BitSubString before(const BitString&, int startpos = 0);
222 BitSubString before(const BitSubString&, int startpos = 0);
223 BitSubString before(const BitPattern&, int startpos = 0);
224
225 BitSubString after(int pos);
226 BitSubString after(const BitString&, int startpos = 0);
227 BitSubString after(const BitSubString&, int startpos = 0);
228 BitSubString after(const BitPattern&, int startpos = 0);
229
230 // other friends & utilities
231
232 friend BitString common_prefix(const BitString&, const BitString&,
233 int pos = 0);
234 friend BitString common_suffix(const BitString&, const BitString&,
235 int pos = -1);
236 friend BitString reverse(const BitString&);
237
238 void right_trim(unsigned int bit);
239 void left_trim(unsigned int bit);
240
241 // status
242
243 int empty() const ;
244 int count(unsigned int bit = 1) const;
245 int length() const;
246
247 // convertors & IO
248
249 friend BitString atoBitString(const char* s, char f='0', char t='1');
250 friend const char* BitStringtoa(const BitString&, char f='0', char t='1');
251
252 friend BitString shorttoBitString(unsigned short);
253 friend BitString longtoBitString(unsigned long);
254
255 friend ostream& operator << (ostream& s, const BitString&);
256
257 // misc
258
259 volatile void error(const char* msg) const;
260
261 // indirect friends
262
263 friend const char* BitPatterntoa(const BitPattern& p,
264 char f='0',char t='1',char x='X');
265 friend BitPattern atoBitPattern(const char* s,
266 char f='0',char t='1',char x='X');
267
268 int OK() const;
269 };
270
271
272 class BitPattern
273 {
274 public:
275 BitString pattern;
276 BitString mask;
277
278 BitPattern();
279 BitPattern(const BitPattern&);
280 BitPattern(const BitString& p, const BitString& m);
281
282 ~BitPattern();
283
284 friend const char* BitPatterntoa(const BitPattern&, char f, char t, char x);
285 friend BitPattern atoBitPattern(const char* s, char f,char t, char x);
286 friend ostream& operator << (ostream& s, const BitPattern&);
287
288 int search(const unsigned short*, int, int) const;
289 int match(const unsigned short* xs, int, int, int) const;
290
291 int OK() const;
292 };
293
294 BitString operator & (const BitString& x, const BitString& y);
295 BitString operator | (const BitString& x, const BitString& y);
296 BitString operator ^ (const BitString& x, const BitString& y);
297 BitString operator << (const BitString& x, int y);
298 BitString operator >> (const BitString& x, int y);
299 BitString operator - (const BitString& x, const BitString& y);
300 BitString operator + (const BitString& x, const BitString& y);
301 BitString operator + (const BitString& x, unsigned int y);
302 BitString operator ~ (const BitString& x);
303 int operator != (const BitString& x, const BitString& y);
304 int operator>(const BitString& x, const BitString& y);
305 int operator>=(const BitString& x, const BitString& y);
306
307 extern BitStrRep _nilBitStrRep;
308 extern BitString _nil_BitString;
309
310 // primitive bit extraction
311
312 // These must be inlined regardless of optimization.
313
BitStr_index(int l)314 inline int BitStr_index(int l) { return (unsigned)(l) / BITSTRBITS; }
315
BitStr_pos(int l)316 inline int BitStr_pos(int l) { return l & (BITSTRBITS - 1); }
317
318 #if defined(__OPTIMIZE__) || defined(USE_LIBGXX_INLINES)
319
320 // constructors & assignment
321
BitString()322 inline BitString::BitString() :rep(&_nilBitStrRep) {}
323
BitString(const BitString & x)324 inline BitString::BitString(const BitString& x) :rep(BStr_copy(0, x.rep)) {}
325
BitString(const BitSubString & y)326 inline BitString::BitString(const BitSubString& y)
327 :rep (BStr_alloc(0, y.S.rep->s, y.pos, y.pos+y.len, y.len)) {}
328
~BitString()329 inline BitString::~BitString()
330 {
331 if (rep != &_nilBitStrRep) delete rep;
332 }
333
334 #if defined(__GNUG__) && !defined(NO_NRV)
335
336 inline BitString shorttoBitString(unsigned short w) return r
337 {
338 r.rep = BStr_alloc(0, &w, 0, BITSTRBITS, BITSTRBITS);
339 }
340
341 inline BitString longtoBitString(unsigned long w) return r
342 {
343 unsigned short u[2];
344 u[0] = w & ((unsigned short)(~(0)));
345 u[1] = w >> BITSTRBITS;
346 r.rep = BStr_alloc(0, &u[0], 0, 2*BITSTRBITS, 2*BITSTRBITS);
347 }
348
349 #else
350
351 inline BitString shorttoBitString(unsigned short w)
352 {
353 BitString r; r.rep = BStr_alloc(0, &w, 0, BITSTRBITS, BITSTRBITS); return r;
354 }
355
356 inline BitString longtoBitString(unsigned long w)
357 {
358 BitString r;
359 unsigned short u[2];
360 u[0] = w & ((unsigned short)(~(0)));
361 u[1] = w >> BITSTRBITS;
362 r.rep = BStr_alloc(0, &u[0], 0, 2*BITSTRBITS, 2*BITSTRBITS);
363 return r;
364 }
365
366 #endif
367
368 inline void BitString::operator = (const BitString& y)
369 {
370 rep = BStr_copy(rep, y.rep);
371 }
372
373 inline void BitString::operator = (unsigned int b)
374 {
375 unsigned short bit = b;
376 rep = BStr_alloc(rep, &bit, 0, 1, 1);
377 }
378
379 inline void BitString::operator=(const BitSubString& y)
380 {
381 rep = BStr_alloc(rep, y.S.rep->s, y.pos, y.pos+y.len, y.len);
382 }
383
384 inline BitSubString::BitSubString(const BitSubString& x)
385 :S(x.S), pos(x.pos), len(x.len) {}
386
387 inline BitSubString::BitSubString(BitString& x, int p, int l)
388 : S(x), pos(p), len(l) {}
389
390 inline BitSubString::~BitSubString() {}
391
392 inline BitPattern::BitPattern(const BitString& p, const BitString& m)
393 :pattern(p), mask(m) {}
394
395 inline BitPattern::BitPattern(const BitPattern& b)
396 :pattern(b.pattern), mask(b.mask) {}
397
398 inline BitPattern::BitPattern() {}
399 inline BitPattern::~BitPattern() {}
400
401
402 // procedural versions of operators
403
404 inline void and(const BitString& x, const BitString& y, BitString& r)
405 {
406 r.rep = and(x.rep, y.rep, r.rep);
407 }
408
409 inline void or(const BitString& x, const BitString& y, BitString& r)
410 {
411 r.rep = or(x.rep, y.rep, r.rep);
412 }
413
414 inline void xor(const BitString& x, const BitString& y, BitString& r)
415 {
416 r.rep = xor(x.rep, y.rep, r.rep);
417 }
418
419 inline void diff(const BitString& x, const BitString& y, BitString& r)
420 {
421 r.rep = diff(x.rep, y.rep, r.rep);
422 }
423
424 inline void cat(const BitString& x, const BitString& y, BitString& r)
425 {
426 r.rep = cat(x.rep, y.rep, r.rep);
427 }
428
429 inline void cat(const BitString& x, unsigned int y, BitString& r)
430 {
431 r.rep = cat(x.rep, y, r.rep);
432 }
433
434 inline void rshift(const BitString& x, int y, BitString& r)
435 {
436 r.rep = lshift(x.rep, -y, r.rep);
437 }
438
439 inline void lshift(const BitString& x, int y, BitString& r)
440 {
441 r.rep = lshift(x.rep, y, r.rep);
442 }
443
444 inline void complement(const BitString& x, BitString& r)
445 {
446 r.rep = cmpl(x.rep, r.rep);
447 }
448
449 // operators
450
451
452 inline void BitString::operator &= (const BitString& y)
453 {
454 and(*this, y, *this);
455 }
456
457
458 inline void BitString::operator |= (const BitString& y)
459 {
460 or(*this, y, *this);
461 }
462
463 inline void BitString::operator ^= (const BitString& y)
464 {
465 xor(*this, y, *this);
466 }
467
468 inline void BitString::operator <<= (int y)
469 {
470 lshift(*this, y, *this);
471 }
472
473 inline void BitString::operator >>= (int y)
474 {
475 rshift(*this, y, *this);
476 }
477
478 inline void BitString::operator -= (const BitString& y)
479 {
480 diff(*this, y, *this);
481 }
482
483 inline void BitString::operator += (const BitString& y)
484 {
485 cat(*this, y, *this);
486 }
487
488 inline void BitString::operator += (unsigned int y)
489 {
490 cat(*this, y, *this);
491 }
492
493 inline void BitString::complement()
494 {
495 ::complement(*this, *this);
496 }
497
498 #if defined(__GNUG__) && !defined(NO_NRV)
499
500 inline BitString operator & (const BitString& x, const BitString& y) return r
501 {
502 and(x, y, r);
503 }
504
505 inline BitString operator | (const BitString& x, const BitString& y) return r
506 {
507 or(x, y, r);
508 }
509
510 inline BitString operator ^ (const BitString& x, const BitString& y) return r
511 {
512 xor(x, y, r);
513 }
514
515 inline BitString operator << (const BitString& x, int y) return r
516 {
517 lshift(x, y, r);
518 }
519
520 inline BitString operator >> (const BitString& x, int y) return r
521 {
522 rshift(x, y, r);
523 }
524
525 inline BitString operator - (const BitString& x, const BitString& y) return r
526 {
527 diff(x, y, r);
528 }
529
530 inline BitString operator + (const BitString& x, const BitString& y) return r
531 {
532 cat(x, y, r);
533 }
534
535 inline BitString operator + (const BitString& x, unsigned int y) return r
536 {
537 cat(x, y, r);
538 }
539
540 inline BitString operator ~ (const BitString& x) return r
541 {
542 complement(x, r);
543 }
544
545 #else /* NO_NRV */
546
547 inline BitString operator & (const BitString& x, const BitString& y)
548 {
549 BitString r; and(x, y, r); return r;
550 }
551
552 inline BitString operator | (const BitString& x, const BitString& y)
553 {
554 BitString r; or(x, y, r); return r;
555 }
556
557 inline BitString operator ^ (const BitString& x, const BitString& y)
558 {
559 BitString r; xor(x, y, r); return r;
560 }
561
562 inline BitString operator << (const BitString& x, int y)
563 {
564 BitString r; lshift(x, y, r); return r;
565 }
566
567 inline BitString operator >> (const BitString& x, int y)
568 {
569 BitString r; rshift(x, y, r); return r;
570 }
571
572 inline BitString operator - (const BitString& x, const BitString& y)
573 {
574 BitString r; diff(x, y, r); return r;
575 }
576
577 inline BitString operator + (const BitString& x, const BitString& y)
578 {
579 BitString r; cat(x, y, r); return r;
580 }
581
582 inline BitString operator + (const BitString& x, unsigned int y)
583 {
584 BitString r; cat(x, y, r); return r;
585 }
586
587 inline BitString operator ~ (const BitString& x)
588 {
589 BitString r; complement(x, r); return r;
590 }
591
592 #endif
593
594 // status, matching
595
596 inline int BitString::length() const
597 {
598 return rep->len;
599 }
600
601 inline int BitString::empty() const
602 {
603 return rep->len == 0;
604 }
605
606 inline int BitString::index(const BitString& y, int startpos) const
607 {
608 return search(startpos, rep->len, y.rep->s, 0, y.rep->len);
609 }
610
611 inline int BitString::index(const BitSubString& y, int startpos) const
612 {
613 return search(startpos, rep->len, y.S.rep->s, y.pos, y.pos+y.len);
614 }
615
616 inline int BitString::contains(const BitString& y) const
617 {
618 return search(0, rep->len, y.rep->s, 0, y.rep->len) >= 0;
619 }
620
621 inline int BitString::contains(const BitSubString& y) const
622 {
623 return search(0, rep->len, y.S.rep->s, y.pos, y.pos+y.len) >= 0;
624 }
625
626 inline int BitString::contains(const BitString& y, int p) const
627 {
628 return match(p, rep->len, 0, y.rep->s, 0, y.rep->len);
629 }
630
631 inline int BitString::matches(const BitString& y, int p) const
632 {
633 return match(p, rep->len, 1, y.rep->s, 0, y.rep->len);
634 }
635
636 inline int BitString::contains(const BitSubString& y, int p) const
637 {
638 return match(p, rep->len, 0, y.S.rep->s, y.pos, y.pos+y.len);
639 }
640
641 inline int BitString::matches(const BitSubString& y, int p) const
642 {
643 return match(p, rep->len, 1, y.S.rep->s, y.pos, y.pos+y.len);
644 }
645
646 inline int BitString::contains(const BitPattern& r) const
647 {
648 return r.search(rep->s, 0, rep->len) >= 0;
649 }
650
651 inline int BitString::contains(const BitPattern& r, int p) const
652 {
653 return r.match(rep->s, p, rep->len, 0);
654 }
655
656 inline int BitString::matches(const BitPattern& r, int p) const
657 {
658 return r.match(rep->s, p, rep->len, 1);
659 }
660
661 inline int BitString::index(const BitPattern& r, int startpos) const
662 {
663 return r.search(rep->s, startpos, rep->len);
664 }
665
666 inline int BitSubString::length() const
667 {
668 return len;
669 }
670
671 inline int BitSubString::empty() const
672 {
673 return len == 0;
674 }
675
676 inline int operator != (const BitString& x, const BitString& y)
677 {
678 return !(x == y);
679 }
680
681 inline int operator>(const BitString& x, const BitString& y)
682 {
683 return y < x;
684 }
685
686 inline int operator>=(const BitString& x, const BitString& y)
687 {
688 return y <= x;
689 }
690
691 inline int BitString::first(unsigned int b) const
692 {
693 return next(-1, b);
694 }
695
696 inline int BitString::last(unsigned int b) const
697 {
698 return previous(rep->len, b);
699 }
700
701 inline int BitString::index(unsigned int bit, int startpos) const
702 {
703 if (startpos >= 0)
704 return next(startpos - 1, bit);
705 else
706 return previous(rep->len + startpos + 1, bit);
707 }
708
709 inline void BitString::right_trim(unsigned int b)
710 {
711 int nb = (b == 0)? 1 : 0;
712 rep = BStr_resize(rep, previous(rep->len, nb) + 1);
713 }
714
715 inline void BitString::left_trim(unsigned int b)
716 {
717 int nb = (b == 0)? 1 : 0;
718 int p = next(-1, nb);
719 rep = BStr_alloc(rep, rep->s, p, rep->len, rep->len - p);
720 }
721
722 inline int BitString::test(int i) const
723 {
724 return ((unsigned)(i) >= rep->len)? 0 :
725 ((rep->s[BitStr_index(i)] & (1 << (BitStr_pos(i)))) != 0);
726 }
727
728
729 // subscripting
730
731 inline BitStrBit::BitStrBit(const BitStrBit& b) :src(b.src), pos(b.pos) {}
732
733 inline BitStrBit::BitStrBit(BitString& v, int p) :src(v), pos(p) {}
734
735 inline BitStrBit::~BitStrBit() {}
736
737 inline BitStrBit::operator unsigned int() const
738 {
739 return src.test(pos);
740 }
741
742 inline int BitStrBit::operator = (unsigned int b)
743 {
744 src.assign(pos, b); return b;
745 }
746
747 inline int BitStrBit::operator == (unsigned int b) const
748 {
749 return src.test(pos) == b;
750 }
751
752 inline int BitStrBit::operator != (unsigned int b) const
753 {
754 return src.test(pos) != b;
755 }
756
757 inline BitStrBit BitString::operator [] (int i)
758 {
759 if ((unsigned)(i) >= rep->len) error("illegal bit index");
760 return BitStrBit(*this, i);
761 }
762
763 inline BitSubString BitString::_substr(int first, int l)
764 {
765 if (first < 0 || l <= 0 || (unsigned)(first + l) > rep->len)
766 return BitSubString(_nil_BitString, 0, 0) ;
767 else
768 return BitSubString(*this, first, l);
769 }
770
771 #endif
772
773 #endif
774