projects / unix-history / blob
? search:
summary | tags | clone url | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
Initial import, 0.1 + pk 0.2.4-B1
[unix-history] / gnu / lib / libg++ / g++-include / BitString.h
// 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 GNU CC.
GNU CC is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY. No author or distributor
accepts responsibility to anyone for the consequences of using it
or for whether it serves any particular purpose or works at all,
unless he says so in writing. Refer to the GNU CC General Public
License for full details.
Everyone is granted permission to copy, modify and redistribute
GNU CC, but only under the conditions described in the
GNU CC General Public License. A copy of this license is
supposed to have been given to you along with GNU CC so you
can know your rights and responsibilities. It should be in a
file named COPYING. Among other things, the copyright notice
and this notice must be preserved on all copies.
*/
#ifndef _BitString_h
#ifdef __GNUG__
#pragma once
#pragma interface
#endif
#define _BitString_h 1
#include <stream.h>
#include <values.h>
#define BITSTRBITS BITS(short)
struct BitStrRep
{
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*);
class BitString;
class BitPattern;
class BitStrBit
{
protected:
BitString& src;
unsigned int pos;
public:
BitStrBit(BitString& v, int p);
BitStrBit(const BitStrBit& b);
~BitStrBit();
operator unsigned int() const;
int operator = (unsigned int b);
int operator == (unsigned int b) const ;
int operator != (unsigned int b) const ;
};
class BitSubString
{
friend class BitString;
friend class BitPattern;
protected:
BitString& S;
int pos;
int len;
BitSubString(BitString& x, int p, int l);
BitSubString(const BitSubString& x);
public:
~BitSubString();
void operator = (const BitString&);
void operator = (const BitSubString&);
int length() const;
int empty() const;
int OK() const;
};
class BitString
{
friend class BitSubString;
friend class BitPattern;
protected:
BitStrRep* rep;
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);
public:
// constructors
BitString();
BitString(const BitString&);
BitString(const BitSubString& y);
~BitString();
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);
void complement();
// individual bit manipulation
void set(int pos);
void set(int from, int to);
void set();
void clear(int pos);
void clear(int from, int to);
void clear();
void invert(int pos);
void invert(int from, int to);
int test(int pos) const;
int test(int from, int to) const;
void assign(int p, unsigned int bit);
// indexing
BitStrBit operator [] (int pos);
// iterators
int first(unsigned int bit = 1) const;
int last(unsigned int b = 1) const;
int next(int pos, unsigned int b = 1) const;
int previous(int pos, unsigned int b = 1) const;
// searching & matching
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&,
int pos = 0);
friend BitString common_suffix(const BitString&, const BitString&,
int pos = -1);
friend BitString reverse(const BitString&);
void right_trim(unsigned int bit);
void left_trim(unsigned int bit);
// status
int empty() const ;
int count(unsigned int bit = 1) const;
int length() const;
// convertors & IO
friend BitString atoBitString(const char* s, char f='0', char t='1');
friend const char* BitStringtoa(const BitString&, char f='0', char t='1');
friend BitString shorttoBitString(unsigned short);
friend BitString longtoBitString(unsigned long);
friend ostream& operator << (ostream& s, const BitString&);
// misc
volatile void error(const char* msg) const;
// indirect friends
friend const char* BitPatterntoa(const BitPattern& p,
char f='0',char t='1',char x='X');
friend BitPattern atoBitPattern(const char* s,
char f='0',char t='1',char x='X');
int OK() const;
};
class BitPattern
{
public:
BitString pattern;
BitString mask;
BitPattern();
BitPattern(const BitPattern&);
BitPattern(const BitString& p, const BitString& m);
~BitPattern();
friend const char* BitPatterntoa(const BitPattern&, char f, char t, char x);
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;
int OK() 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); }
#if defined(__OPTIMIZE__) || defined(USE_LIBGXX_INLINES)
// 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
{
unsigned short u[2];
u[0] = w & ((unsigned short)(~(0)));
u[1] = w >> BITSTRBITS;
r.rep = BStr_alloc(0, &u[0], 0, 2*BITSTRBITS, 2*BITSTRBITS);
}
#else
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)
{
BitString r;
unsigned short u[2];
u[0] = w & ((unsigned short)(~(0)));
u[1] = w >> BITSTRBITS;
r.rep = BStr_alloc(0, &u[0], 0, 2*BITSTRBITS, 2*BITSTRBITS);
return r;
}
#endif
inline void BitString::operator = (const BitString& y)
{
rep = BStr_copy(rep, y.rep);
}
inline void BitString::operator = (unsigned int b)
{
unsigned short bit = 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)
:pattern(p), mask(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);
}
// operators
inline void BitString::operator &= (const BitString& y)
{
and(*this, y, *this);
}
inline void BitString::operator |= (const BitString& y)
{
or(*this, y, *this);
}
inline void BitString::operator ^= (const BitString& y)
{
xor(*this, y, *this);
}
inline void BitString::operator <<= (int y)
{
lshift(*this, y, *this);
}
inline void BitString::operator >>= (int y)
{
rshift(*this, y, *this);
}
inline void BitString::operator -= (const BitString& y)
{
diff(*this, y, *this);
}
inline void BitString::operator += (const BitString& y)
{
cat(*this, y, *this);
}
inline void BitString::operator += (unsigned int y)
{
cat(*this, y, *this);
}
inline void BitString::complement()
{
::complement(*this, *this);
}
#if defined(__GNUG__) && !defined(NO_NRV)
inline BitString operator & (const BitString& x, const BitString& y) return r
{
and(x, y, r);
}
inline BitString operator | (const BitString& x, const BitString& y) return r
{
or(x, y, r);
}
inline BitString operator ^ (const BitString& x, const BitString& y) return r
{
xor(x, y, r);
}
inline BitString operator << (const BitString& x, int y) return r
{
lshift(x, y, r);
}
inline BitString operator >> (const BitString& x, int y) return r
{
rshift(x, y, r);
}
inline BitString operator - (const BitString& x, const BitString& y) return r
{
diff(x, y, r);
}
inline BitString operator + (const BitString& x, const BitString& y) return r
{
cat(x, y, r);
}
inline BitString operator + (const BitString& x, unsigned int y) return r
{
cat(x, y, r);
}
inline BitString operator ~ (const BitString& x) return r
{
complement(x, r);
}
#else /* NO_NRV */
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;
}
#endif
// status, matching
inline int BitString::length() const
{
return rep->len;
}
inline int BitString::empty() const
{
return rep->len == 0;
}
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
{
return len;
}
inline int BitSubString::empty() const
{
return len == 0;
}
inline int operator != (const BitString& x, const BitString& y)
{
return !(x == y);
}
inline int operator>(const BitString& x, const BitString& y)
{
return y < x;
}
inline int operator>=(const BitString& x, const BitString& y)
{
return y <= x;
}
inline int BitString::first(unsigned int b) const
{
return next(-1, b);
}
inline int BitString::last(unsigned int b) const
{
return previous(rep->len, b);
}
inline int BitString::index(unsigned int bit, int startpos) const
{
if (startpos >= 0)
return next(startpos - 1, bit);
else
return previous(rep->len + startpos + 1, bit);
}
inline void BitString::right_trim(unsigned int b)
{
int nb = (b == 0)? 1 : 0;
rep = BStr_resize(rep, previous(rep->len, nb) + 1);
}
inline void BitString::left_trim(unsigned int b)
{
int nb = (b == 0)? 1 : 0;
int p = next(-1, nb);
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);
}
// subscripting
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
{
return src.test(pos);
}
inline int BitStrBit::operator = (unsigned int b)
{
src.assign(pos, b); return b;
}
inline int BitStrBit::operator == (unsigned int b) const
{
return src.test(pos) == b;
}
inline int BitStrBit::operator != (unsigned int b) const
{
return src.test(pos) != 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) ;
else
return BitSubString(*this, first, l);
}
#endif
#endif
Continuous source code history from original PDP-7 UNIX to FreeBSD 2, the first fully unencumbered FreeBSD release.