// This may look like C code, but it is really -*- C++ -*-
Copyright (C) 1988 Free Software Foundation
written by Doug Lea (dl@rocky.oswego.edu)
This file is part of the GNU C++ Library. This library is free
software; you can redistribute it and/or modify it under the terms of
the GNU Library General Public License as published by the Free
Software Foundation; either version 2 of the License, or (at your
option) any later version. This library is distributed in the hope
that it will be useful, but WITHOUT ANY WARRANTY; without even the
implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
PURPOSE. See the GNU Library General Public License for more details.
You should have received a copy of the GNU Library General Public
License along with this library; if not, write to the Free Software
Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
#define BITSTRBITS (sizeof(short) * CHAR_BIT)
unsigned int len
; // length in bits
unsigned short sz
; // allocated slots
unsigned short s
[1]; // bits start here
extern BitStrRep
* BStr_alloc(BitStrRep
*, const unsigned short*, int, int,int);
extern BitStrRep
* BStr_resize(BitStrRep
*, int);
extern BitStrRep
* BStr_copy(BitStrRep
*, const BitStrRep
*);
extern BitStrRep
* cmpl(const BitStrRep
*, BitStrRep
*);
extern BitStrRep
* and(const BitStrRep
*, const BitStrRep
*, BitStrRep
*);
extern BitStrRep
* or(const BitStrRep
*, const BitStrRep
*, BitStrRep
*);
extern BitStrRep
* xor(const BitStrRep
*, const BitStrRep
*, BitStrRep
*);
extern BitStrRep
* diff(const BitStrRep
*, const BitStrRep
*, BitStrRep
*);
extern BitStrRep
* cat(const BitStrRep
*, const BitStrRep
*, BitStrRep
*);
extern BitStrRep
* cat(const BitStrRep
*, unsigned int, BitStrRep
*);
extern BitStrRep
* lshift(const BitStrRep
*, int, BitStrRep
*);
BitStrBit(BitString
& v
, int p
);
BitStrBit(const BitStrBit
& b
);
operator unsigned int() const;
int operator = (unsigned int b
);
BitSubString(BitString
& x
, int p
, int l
);
BitSubString(const BitSubString
& x
);
void operator = (const BitString
&);
void operator = (const BitSubString
&);
friend class BitSubString
;
int search(int, int, const unsigned short*, int, int) const;
int match(int, int, int, const unsigned short*,int,int) const;
BitSubString
_substr(int first
, int l
);
BitString(const BitString
&);
BitString(const BitSubString
& y
);
void operator = (unsigned int bit
);
void operator = (const BitString
& y
);
void operator = (const BitSubString
& y
);
// equality & subset tests
friend int operator == (const BitString
&, const BitString
&);
friend int operator != (const BitString
&, const BitString
&);
friend int operator < (const BitString
&, const BitString
&);
friend int operator <= (const BitString
&, const BitString
&);
friend int operator > (const BitString
&, const BitString
&);
friend int operator >= (const BitString
&, const BitString
&);
// procedural versions of operators
friend void and(const BitString
&, const BitString
&, BitString
&);
friend void or(const BitString
&, const BitString
&, BitString
&);
friend void xor(const BitString
&, const BitString
&, BitString
&);
friend void diff(const BitString
&, const BitString
&, BitString
&);
friend void cat(const BitString
&, const BitString
&, BitString
&);
friend void cat(const BitString
&, unsigned int, BitString
&);
friend void lshift(const BitString
&, int, BitString
&);
friend void rshift(const BitString
&, int, BitString
&);
friend void complement(const BitString
&, BitString
&);
friend int lcompare(const BitString
&, const BitString
&);
// assignment-based operators
// (constuctive versions decalred inline below
void operator |= (const BitString
&);
void operator &= (const BitString
&);
void operator -= (const BitString
&);
void operator ^= (const BitString
&);
void operator += (const BitString
&);
void operator += (unsigned int b
);
void operator <<=(int s
);
void operator >>=(int s
);
// individual bit manipulation
void set(int from
, int to
);
void clear(int from
, int to
);
void invert(int from
, int to
);
int test(int from
, int to
) const;
void assign(int p
, unsigned int bit
);
BitStrBit
operator [] (int pos
);
int first(unsigned int bit
= 1) const;
int last(unsigned int b
= 1) const;
int next(int pos
, unsigned int b
= 1) const;
int prev(int pos
, unsigned int b
= 1) const;
int previous(int pos
, unsigned int b
= 1) const
{ return prev(pos
, b
); } /* Obsolete synonym */
int index(unsigned int bit
, int startpos
= 0) const ;
int index(const BitString
&, int startpos
= 0) const;
int index(const BitSubString
&, int startpos
= 0) const;
int index(const BitPattern
&, int startpos
= 0) const;
int contains(const BitString
&) const;
int contains(const BitSubString
&) const;
int contains(const BitPattern
&) const;
int contains(const BitString
&, int pos
) const;
int contains(const BitSubString
&, int pos
) const;
int contains(const BitPattern
&, int pos
) const;
int matches(const BitString
&, int pos
= 0) const;
int matches(const BitSubString
&, int pos
= 0) const;
int matches(const BitPattern
&, int pos
= 0) const;
// BitSubString extraction
BitSubString
at(int pos
, int len
);
BitSubString
at(const BitString
&, int startpos
= 0);
BitSubString
at(const BitSubString
&, int startpos
= 0);
BitSubString
at(const BitPattern
&, int startpos
= 0);
BitSubString
before(int pos
);
BitSubString
before(const BitString
&, int startpos
= 0);
BitSubString
before(const BitSubString
&, int startpos
= 0);
BitSubString
before(const BitPattern
&, int startpos
= 0);
BitSubString
after(int pos
);
BitSubString
after(const BitString
&, int startpos
= 0);
BitSubString
after(const BitSubString
&, int startpos
= 0);
BitSubString
after(const BitPattern
&, int startpos
= 0);
// other friends & utilities
friend BitString
common_prefix(const BitString
&, const BitString
&,
friend BitString
common_suffix(const BitString
&, const BitString
&,
friend BitString
reverse(const BitString
&);
void right_trim(unsigned int bit
);
void left_trim(unsigned int bit
);
int count(unsigned int bit
= 1) const;
friend BitString
atoBitString(const char* s
, char f
='0', char t
='1');
// BitStringtoa is deprecated; do not use in new programs!
friend const char* BitStringtoa(const BitString
&, char f
='0', char t
='1');
void printon(ostream
&, char f
='0', char t
='1') const;
friend BitString
shorttoBitString(unsigned short);
friend BitString
longtoBitString(unsigned long);
friend ostream
& operator << (ostream
& s
, const BitString
&);
void error(const char* msg
) const;
friend BitPattern
atoBitPattern(const char* s
,
char f
='0',char t
='1',char x
='X');
friend const char* BitPatterntoa(const BitPattern
& p
,
char f
='0',char t
='1',char x
='X');
BitPattern(const BitPattern
&);
BitPattern(const BitString
& p
, const BitString
& m
);
friend const char* BitPatterntoa(const BitPattern
& p
,
char f
/*='0'*/,char t
/*='1'*/,char x
/*='X'*/);
void printon(ostream
&, char f
='0',char t
='1',char x
='X') const;
friend BitPattern
atoBitPattern(const char* s
, char f
,char t
, char x
);
friend ostream
& operator << (ostream
& s
, const BitPattern
&);
int search(const unsigned short*, int, int) const;
int match(const unsigned short* xs
, int, int, int) const;
BitString
operator & (const BitString
& x
, const BitString
& y
);
BitString
operator | (const BitString
& x
, const BitString
& y
);
BitString
operator ^ (const BitString
& x
, const BitString
& y
);
BitString
operator << (const BitString
& x
, int y
);
BitString
operator >> (const BitString
& x
, int y
);
BitString
operator - (const BitString
& x
, const BitString
& y
);
BitString
operator + (const BitString
& x
, const BitString
& y
);
BitString
operator + (const BitString
& x
, unsigned int y
);
BitString
operator ~ (const BitString
& x
);
int operator != (const BitString
& x
, const BitString
& y
);
int operator>(const BitString
& x
, const BitString
& y
);
int operator>=(const BitString
& x
, const BitString
& y
);
extern BitStrRep _nilBitStrRep
;
extern BitString _nil_BitString
;
// primitive bit extraction
// These must be inlined regardless of optimization.
inline int BitStr_index(int l
) { return (unsigned)(l
) / BITSTRBITS
; }
inline int BitStr_pos(int l
) { return l
& (BITSTRBITS
- 1); }
// constructors & assignment
inline BitString::BitString() :rep(&_nilBitStrRep
) {}
inline BitString::BitString(const BitString
& x
) :rep(BStr_copy(0, x
.rep
)) {}
inline BitString::BitString(const BitSubString
& y
)
:rep (BStr_alloc(0, y
.S
.rep
->s
, y
.pos
, y
.pos
+y
.len
, y
.len
)) {}
inline BitString::~BitString()
if (rep
!= &_nilBitStrRep
) delete rep
;
#if defined(__GNUG__) && !defined(NO_NRV)
inline BitString
shorttoBitString(unsigned short w
) return r
r
.rep
= BStr_alloc(0, &w
, 0, BITSTRBITS
, BITSTRBITS
);
inline BitString
longtoBitString(unsigned long w
) return r
u
[0] = w
& ((unsigned short)(~(0)));
r
.rep
= BStr_alloc(0, &u
[0], 0, 2*BITSTRBITS
, 2*BITSTRBITS
);
inline BitString
shorttoBitString(unsigned short w
)
BitString r
; r
.rep
= BStr_alloc(0, &w
, 0, BITSTRBITS
, BITSTRBITS
); return r
;
inline BitString
longtoBitString(unsigned long w
)
u
[0] = w
& ((unsigned short)(~(0)));
r
.rep
= BStr_alloc(0, &u
[0], 0, 2*BITSTRBITS
, 2*BITSTRBITS
);
inline void BitString::operator = (const BitString
& y
)
rep
= BStr_copy(rep
, y
.rep
);
inline void BitString::operator = (unsigned int b
)
rep
= BStr_alloc(rep
, &bit
, 0, 1, 1);
inline void BitString::operator=(const BitSubString
& y
)
rep
= BStr_alloc(rep
, y
.S
.rep
->s
, y
.pos
, y
.pos
+y
.len
, y
.len
);
inline BitSubString::BitSubString(const BitSubString
& x
)
:S(x
.S
), pos(x
.pos
), len(x
.len
) {}
inline BitSubString::BitSubString(BitString
& x
, int p
, int l
)
: S(x
), pos(p
), len(l
) {}
inline BitSubString::~BitSubString() {}
inline BitPattern::BitPattern(const BitString
& p
, const BitString
& m
)
inline BitPattern::BitPattern(const BitPattern
& b
)
:pattern(b
.pattern
), mask(b
.mask
) {}
inline BitPattern::BitPattern() {}
inline BitPattern::~BitPattern() {}
// procedural versions of operators
inline void and(const BitString
& x
, const BitString
& y
, BitString
& r
)
r
.rep
= and(x
.rep
, y
.rep
, r
.rep
);
inline void or(const BitString
& x
, const BitString
& y
, BitString
& r
)
r
.rep
= or(x
.rep
, y
.rep
, r
.rep
);
inline void xor(const BitString
& x
, const BitString
& y
, BitString
& r
)
r
.rep
= xor(x
.rep
, y
.rep
, r
.rep
);
inline void diff(const BitString
& x
, const BitString
& y
, BitString
& r
)
r
.rep
= diff(x
.rep
, y
.rep
, r
.rep
);
inline void cat(const BitString
& x
, const BitString
& y
, BitString
& r
)
r
.rep
= cat(x
.rep
, y
.rep
, r
.rep
);
inline void cat(const BitString
& x
, unsigned int y
, BitString
& r
)
r
.rep
= cat(x
.rep
, y
, r
.rep
);
inline void rshift(const BitString
& x
, int y
, BitString
& r
)
r
.rep
= lshift(x
.rep
, -y
, r
.rep
);
inline void lshift(const BitString
& x
, int y
, BitString
& r
)
r
.rep
= lshift(x
.rep
, y
, r
.rep
);
inline void complement(const BitString
& x
, BitString
& r
)
r
.rep
= cmpl(x
.rep
, r
.rep
);
inline void BitString::operator &= (const BitString
& y
)
inline void BitString::operator |= (const BitString
& y
)
inline void BitString::operator ^= (const BitString
& y
)
inline void BitString::operator <<= (int y
)
inline void BitString::operator >>= (int y
)
inline void BitString::operator -= (const BitString
& y
)
inline void BitString::operator += (const BitString
& y
)
inline void BitString::operator += (unsigned int y
)
inline void BitString::complement()
::complement(*this, *this);
#if defined(__GNUG__) && !defined(NO_NRV)
inline BitString
operator & (const BitString
& x
, const BitString
& y
) return r
inline BitString
operator | (const BitString
& x
, const BitString
& y
) return r
inline BitString
operator ^ (const BitString
& x
, const BitString
& y
) return r
inline BitString
operator << (const BitString
& x
, int y
) return r
inline BitString
operator >> (const BitString
& x
, int y
) return r
inline BitString
operator - (const BitString
& x
, const BitString
& y
) return r
inline BitString
operator + (const BitString
& x
, const BitString
& y
) return r
inline BitString
operator + (const BitString
& x
, unsigned int y
) return r
inline BitString
operator ~ (const BitString
& x
) return r
inline BitString
operator & (const BitString
& x
, const BitString
& y
)
BitString r
; and(x
, y
, r
); return r
;
inline BitString
operator | (const BitString
& x
, const BitString
& y
)
BitString r
; or(x
, y
, r
); return r
;
inline BitString
operator ^ (const BitString
& x
, const BitString
& y
)
BitString r
; xor(x
, y
, r
); return r
;
inline BitString
operator << (const BitString
& x
, int y
)
BitString r
; lshift(x
, y
, r
); return r
;
inline BitString
operator >> (const BitString
& x
, int y
)
BitString r
; rshift(x
, y
, r
); return r
;
inline BitString
operator - (const BitString
& x
, const BitString
& y
)
BitString r
; diff(x
, y
, r
); return r
;
inline BitString
operator + (const BitString
& x
, const BitString
& y
)
BitString r
; cat(x
, y
, r
); return r
;
inline BitString
operator + (const BitString
& x
, unsigned int y
)
BitString r
; cat(x
, y
, r
); return r
;
inline BitString
operator ~ (const BitString
& x
)
BitString r
; complement(x
, r
); return r
;
inline int BitString::length() const
inline int BitString::empty() const
inline int BitString::index(const BitString
& y
, int startpos
) const
return search(startpos
, rep
->len
, y
.rep
->s
, 0, y
.rep
->len
);
inline int BitString::index(const BitSubString
& y
, int startpos
) const
return search(startpos
, rep
->len
, y
.S
.rep
->s
, y
.pos
, y
.pos
+y
.len
);
inline int BitString::contains(const BitString
& y
) const
return search(0, rep
->len
, y
.rep
->s
, 0, y
.rep
->len
) >= 0;
inline int BitString::contains(const BitSubString
& y
) const
return search(0, rep
->len
, y
.S
.rep
->s
, y
.pos
, y
.pos
+y
.len
) >= 0;
inline int BitString::contains(const BitString
& y
, int p
) const
return match(p
, rep
->len
, 0, y
.rep
->s
, 0, y
.rep
->len
);
inline int BitString::matches(const BitString
& y
, int p
) const
return match(p
, rep
->len
, 1, y
.rep
->s
, 0, y
.rep
->len
);
inline int BitString::contains(const BitSubString
& y
, int p
) const
return match(p
, rep
->len
, 0, y
.S
.rep
->s
, y
.pos
, y
.pos
+y
.len
);
inline int BitString::matches(const BitSubString
& y
, int p
) const
return match(p
, rep
->len
, 1, y
.S
.rep
->s
, y
.pos
, y
.pos
+y
.len
);
inline int BitString::contains(const BitPattern
& r
) const
return r
.search(rep
->s
, 0, rep
->len
) >= 0;
inline int BitString::contains(const BitPattern
& r
, int p
) const
return r
.match(rep
->s
, p
, rep
->len
, 0);
inline int BitString::matches(const BitPattern
& r
, int p
) const
return r
.match(rep
->s
, p
, rep
->len
, 1);
inline int BitString::index(const BitPattern
& r
, int startpos
) const
return r
.search(rep
->s
, startpos
, rep
->len
);
inline int BitSubString::length() const
inline int BitSubString::empty() const
inline int operator != (const BitString
& x
, const BitString
& y
)
inline int operator>(const BitString
& x
, const BitString
& y
)
inline int operator>=(const BitString
& x
, const BitString
& y
)
inline int BitString::first(unsigned int b
) const
inline int BitString::last(unsigned int b
) const
return prev(rep
->len
, b
);
inline int BitString::index(unsigned int bit
, int startpos
) const
return next(startpos
- 1, bit
);
return prev(rep
->len
+ startpos
+ 1, bit
);
inline void BitString::right_trim(unsigned int b
)
int nb
= (b
== 0)? 1 : 0;
rep
= BStr_resize(rep
, prev(rep
->len
, nb
) + 1);
inline void BitString::left_trim(unsigned int b
)
int nb
= (b
== 0)? 1 : 0;
rep
= BStr_alloc(rep
, rep
->s
, p
, rep
->len
, rep
->len
- p
);
inline int BitString::test(int i
) const
return ((unsigned)(i
) >= rep
->len
)? 0 :
((rep
->s
[BitStr_index(i
)] & (1 << (BitStr_pos(i
)))) != 0);
inline BitStrBit::BitStrBit(const BitStrBit
& b
) :src(b
.src
), pos(b
.pos
) {}
inline BitStrBit::BitStrBit(BitString
& v
, int p
) :src(v
), pos(p
) {}
inline BitStrBit::~BitStrBit() {}
inline BitStrBit::operator unsigned int() const
inline int BitStrBit::operator = (unsigned int b
)
src
.assign(pos
, b
); return b
;
inline BitStrBit
BitString::operator [] (int i
)
if ((unsigned)(i
) >= rep
->len
) error("illegal bit index");
return BitStrBit(*this, i
);
inline BitSubString
BitString::_substr(int first
, int l
)
if (first
< 0 || l
<= 0 || (unsigned)(first
+ l
) > rep
->len
)
return BitSubString(_nil_BitString
, 0, 0) ;
return BitSubString(*this, first
, l
);