From: William F. Jolitz Date: Fri, 8 Jun 1990 16:45:45 +0000 (-0800) Subject: 386BSD 0.0 development X-Git-Tag: 386BSD-0.0~1158 X-Git-Url: https://git.subgeniuskitty.com/unix-history/.git/commitdiff_plain/93a94e734d35927ce4c7701f869b6785badde1c2 386BSD 0.0 development Work on file usr/src/lib/libg++/libg++/BitString.cc Work on file usr/src/lib/libg++/libg++/BitSet.cc Work on file usr/src/lib/libg++/libg++/regex.cc Co-Authored-By: Lynne Greer Jolitz Synthesized-from: 386BSD-0.0/src --- diff --git a/usr/src/lib/libg++/libg++/BitSet.cc b/usr/src/lib/libg++/libg++/BitSet.cc new file mode 100644 index 0000000000..18aa7b8ce2 --- /dev/null +++ b/usr/src/lib/libg++/libg++/BitSet.cc @@ -0,0 +1,955 @@ +/* +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. +*/ + +/* + BitSet class implementation + */ + +#ifdef __GNUG__ +#pragma implementation +#endif +#include +#include +#include +#include +#include +#include + +volatile void BitSet::error(const char* msg) const +{ + (*lib_error_handler)("BitSet", msg); +} + +// globals & constants + +BitSetRep _nilBitSetRep = { 0, 1, 0, {0} }; // nil BitSets point here + +#define ONES ((unsigned short)(~0L)) +#define MAXBitSetRep_SIZE ((1 << (SHORTBITS - 1)) - 1) +#define MINBitSetRep_SIZE 16 + +#ifndef MALLOC_MIN_OVERHEAD +#define MALLOC_MIN_OVERHEAD 4 +#endif + +// break things up into .s indices and positions + + +// mask out bits from left + +static inline unsigned short lmask(int p) +{ + return ONES << p; +} + +// mask out high bits + +static inline unsigned short rmask(int p) +{ + return ONES >> (BITSETBITS - 1 - p); +} + + +inline static BitSetRep* BSnew(int newlen) +{ + unsigned int siz = sizeof(BitSetRep) + newlen * sizeof(short) + + MALLOC_MIN_OVERHEAD; + unsigned int allocsiz = MINBitSetRep_SIZE;; + while (allocsiz < siz) allocsiz <<= 1; + allocsiz -= MALLOC_MIN_OVERHEAD; + if (allocsiz >= MAXBitSetRep_SIZE * sizeof(short)) + (*lib_error_handler)("BitSet", "Requested length out of range"); + + BitSetRep* rep = (BitSetRep *) new char[allocsiz]; + bzero(rep, allocsiz); + rep->sz = (allocsiz - sizeof(BitSetRep) + sizeof(short)) / sizeof(short); + return rep; +} + +BitSetRep* BitSetalloc(BitSetRep* old, const unsigned short* src, int srclen, + int newvirt, int newlen) +{ + if (old == &_nilBitSetRep) old = 0; + BitSetRep* rep; + if (old == 0 || newlen >= old->sz) + rep = BSnew(newlen); + else + rep = old; + + rep->len = newlen; + rep->virt = newvirt; + + if (srclen != 0 && src != rep->s) + bcopy(src, rep->s, srclen * sizeof(short)); + + if (old != rep && old != 0) delete old; + return rep; +} + +BitSetRep* BitSetresize(BitSetRep* old, int newlen) +{ + BitSetRep* rep; + if (old == 0 || old == &_nilBitSetRep) + { + rep = BSnew(newlen); + rep->virt = 0; + } + else if (newlen >= old->sz) + { + rep = BSnew(newlen); + bcopy(old->s, rep->s, old->len * sizeof(short)); + rep->virt = old->virt; + delete old; + } + else + rep = old; + + rep->len = newlen; + + return rep; +} + +// same, for straight copy + +BitSetRep* BitSetcopy(BitSetRep* old, const BitSetRep* src) +{ + BitSetRep* rep; + if (old == &_nilBitSetRep) old = 0; + if (src == 0 || src == &_nilBitSetRep) + { + if (old == 0) + rep = BSnew(0); + else + rep = old; + rep->len = 0; + rep->virt = 0; + } + else if (old == src) + return old; + else + { + int newlen = src->len; + if (old == 0 || newlen > old->sz) + { + rep = BSnew(newlen); + if (old != 0) delete old; + } + else + rep = old; + + bcopy(src->s, rep->s, newlen * sizeof(short)); + rep->len = newlen; + rep->virt = src->virt; + } + return rep; +} + + +// remove unneeded top bits + +inline static void trim(BitSetRep* rep) +{ + int l = rep->len; + unsigned short* s = &(rep->s[l - 1]); + + if (rep->virt == 0) + while (l > 0 && *s-- == 0) --l; + else + while (l > 0 && *s-- == ONES) --l; + rep->len = l; +} + +int operator == (const BitSet& x, const BitSet& y) +{ + return x.rep->len == y.rep->len && x.rep->virt == y.rep->virt && + bcmp((void*)x.rep->s, (void*)y.rep->s, + x.rep->len * sizeof(short)) == 0; +} + + +int operator <= (const BitSet& x, const BitSet& y) +{ + if (x.rep->virt > y.rep->virt) + return 0; + + int xl = x.rep->len; + int yl = y.rep->len; + + unsigned short* xs = x.rep->s; + unsigned short* ys = y.rep->s; + unsigned short* topx = &(xs[xl]); + unsigned short* topy = &(ys[yl]); + + while (xs < topx && ys < topy) + { + unsigned short a = *xs++; + unsigned short b = *ys++; + if ((a | b) != b) + return 0; + } + if (xl == yl) + return x.rep->virt <= y.rep->virt; + else if (xl < yl) + return !x.rep->virt; + else + return y.rep->virt; +} + + +int operator < (const BitSet& x, const BitSet& y) +{ + if (x.rep->virt > y.rep->virt) + return 0; + + int xl = x.rep->len; + int yl = y.rep->len; + + unsigned short* xs = x.rep->s; + unsigned short* ys = y.rep->s; + unsigned short* topx = &(xs[xl]); + unsigned short* topy = &(ys[yl]); + int one_diff = 0; + while (xs < topx && ys < topy) + { + unsigned short a = *xs++; + unsigned short b = *ys++; + unsigned short c = a | b; + if (c != b) + return 0; + else if (c != a) + one_diff = 1; + } + if (xl == yl) + return x.rep->virt < y.rep->virt || + (one_diff && x.rep->virt == y.rep->virt); + else if (xl < yl) + return !x.rep->virt; + else + return y.rep->virt; +} + + + +int BitSet::empty() const +{ + if (rep->virt == 1) + return 0; + + unsigned short* bots = rep->s; + unsigned short* s = &(bots[rep->len - 1]); + while (s >= bots) if (*s-- != 0) return 0; + return 1; +} + + +int BitSet::count(int b) const +{ + if (b == rep->virt) + return -1; + int l = 0; + unsigned short* s = rep->s; + unsigned short* tops = &(s[rep->len]); + if (b == 1) + { + while (s < tops) + { + unsigned short a = *s++; + for (int i = 0; i < BITSETBITS && a != 0; ++i) + { + if (a & 1) + ++l; + a >>= 1; + } + } + } + else + { + unsigned short maxbit = 1 << (BITSETBITS - 1); + while (s < tops) + { + unsigned short a = *s++; + for (int i = 0; i < BITSETBITS; ++i) + { + if ((a & maxbit) == 0) + ++l; + a <<= 1; + } + } + } + return l; +} + +BitSetRep* BitSetcmpl(const BitSetRep* src, BitSetRep* r) +{ + r = BitSetcopy(r, src); + r->virt = !src->virt; + unsigned short* rs = r->s; + unsigned short* topr = &(rs[r->len]); + if (r->len == 0) + *rs = ONES; + else + { + while (rs < topr) + { + unsigned short cmp = ~(*rs); + *rs++ = cmp; + } + } + trim(r); + return r; +} + + +BitSetRep* BitSetop(const BitSetRep* x, const BitSetRep* y, + BitSetRep* r, char op) +{ + int xrsame = x == r; + int yrsame = y == r; + int xv = x->virt; + int yv = y->virt; + int xl = x->len; + int yl = y->len; + int rl = (xl >= yl)? xl : yl; + + r = BitSetresize(r, rl); + unsigned short* rs = r->s; + unsigned short* topr = &(rs[rl]); + + int av, bv; + const unsigned short* as; + const unsigned short* topa; + const unsigned short* bs; + const unsigned short* topb; + + if (xl <= yl) + { + as = (xrsame)? r->s : x->s; + av = xv; + topa = &(as[xl]); + bs = (yrsame)? r->s : y->s; + bv = yv; + topb = &(bs[yl]); + } + else + { + as = (yrsame)? r->s : y->s; + av = yv; + topa = &(as[yl]); + bs = (xrsame)? r->s : x->s; + bv = xv; + topb = &(bs[xl]); + if (op == '-') // reverse sense of difference + op = 'D'; + } + + switch (op) + { + case '&': + r->virt = av & bv; + while (as < topa) *rs++ = *as++ & *bs++; + if (av) + while (rs < topr) *rs++ = *bs++; + else + while (rs < topr) *rs++ = 0; + break; + case '|': + r->virt = av | bv; + while (as < topa) *rs++ = *as++ | *bs++; + if (av) + while (rs < topr) *rs++ = ONES; + else + while (rs < topr) *rs++ = *bs++; + break; + case '^': + r->virt = av ^ bv; + while (as < topa) *rs++ = *as++ ^ *bs++; + if (av) + while (rs < topr) *rs++ = ~(*bs++); + else + while (rs < topr) *rs++ = *bs++; + break; + case '-': + r->virt = av & ~(bv); + while (as < topa) *rs++ = *as++ & ~(*bs++); + if (av) + while (rs < topr) *rs++ = ~(*bs++); + else + while (rs < topr) *rs++ = 0; + break; + case 'D': + r->virt = ~(av) & (bv); + while (as < topa) *rs++ = ~(*as++) & (*bs++); + if (av) + while (rs < topr) *rs++ = 0; + else + while (rs < topr) *rs++ = *bs++; + break; + } + trim(r); + return r; +} + + +void BitSet::set(int p) +{ + if (p < 0) error("Illegal bit index"); + + int index = BitSet_index(p); + int pos = BitSet_pos(p); + + if (index >= rep->len) + { + if (rep->virt) + return; + else + rep = BitSetresize(rep, index+1); + } + + rep->s[index] |= (1 << pos); +} + +void BitSet::clear(int p) +{ + if (p < 0) error("Illegal bit index"); + int index = BitSet_index(p); + if (index >= rep->len) + { + if (rep->virt == 0) + return; + else + rep = BitSetresize(rep, index+1); + } + rep->s[index] &= ~(1 << BitSet_pos(p)); +} + +void BitSet::invert(int p) +{ + if (p < 0) error("Illegal bit index"); + int index = BitSet_index(p); + if (index >= rep->len) rep = BitSetresize(rep, index+1); + rep->s[index] ^= (1 << BitSet_pos(p)); +} + +void BitSet::set(int from, int to) +{ + if (from < 0 || from > to) error("Illegal bit index"); + + int index1 = BitSet_index(from); + int pos1 = BitSet_pos(from); + + if (rep->virt && index1 >= rep->len) + return; + + int index2 = BitSet_index(to); + int pos2 = BitSet_pos(to); + + if (index2 >= rep->len) + rep = BitSetresize(rep, index2+1); + + unsigned short* s = &(rep->s[index1]); + unsigned short m1 = lmask(pos1); + unsigned short m2 = rmask(pos2); + if (index2 == index1) + *s |= m1 & m2; + else + { + *s++ |= m1; + unsigned short* top = &(rep->s[index2]); + *top |= m2; + while (s < top) + *s++ = ONES; + } +} + +void BitSet::clear(int from, int to) +{ + if (from < 0 || from > to) error("Illegal bit index"); + + int index1 = BitSet_index(from); + int pos1 = BitSet_pos(from); + + if (!rep->virt && index1 >= rep->len) + return; + + int index2 = BitSet_index(to); + int pos2 = BitSet_pos(to); + + if (index2 >= rep->len) + rep = BitSetresize(rep, index2+1); + + unsigned short* s = &(rep->s[index1]); + unsigned short m1 = lmask(pos1); + unsigned short m2 = rmask(pos2); + if (index2 == index1) + *s &= ~(m1 & m2); + else + { + *s++ &= ~m1; + unsigned short* top = &(rep->s[index2]); + *top &= ~m2; + while (s < top) + *s++ = 0; + } +} + +void BitSet::invert(int from, int to) +{ + if (from < 0 || from > to) error("Illegal bit index"); + + int index1 = BitSet_index(from); + int pos1 = BitSet_pos(from); + int index2 = BitSet_index(to); + int pos2 = BitSet_pos(to); + + if (index2 >= rep->len) + rep = BitSetresize(rep, index2+1); + + unsigned short* s = &(rep->s[index1]); + unsigned short m1 = lmask(pos1); + unsigned short m2 = rmask(pos2); + if (index2 == index1) + *s ^= m1 & m2; + else + { + *s++ ^= m1; + unsigned short* top = &(rep->s[index2]); + *top ^= m2; + while (s < top) + { + unsigned short cmp = ~(*s); + *s++ = cmp; + } + } +} + + +int BitSet::test(int from, int to) const +{ + if (from < 0 || from > to) return 0; + + int index1 = BitSet_index(from); + int pos1 = BitSet_pos(from); + + if (index1 >= rep->len) + return rep->virt; + + int index2 = BitSet_index(to); + int pos2 = BitSet_pos(to); + + if (index2 >= rep->len) + { + if (rep->virt) + return 1; + else + { + index2 = rep->len - 1; + pos2 = BITSETBITS - 1; + } + } + + unsigned short* s = &(rep->s[index1]); + unsigned short m1 = lmask(pos1); + unsigned short m2 = rmask(pos2); + + if (index2 == index1) + return (*s & m1 & m2) != 0; + else + { + if (*s++ & m1) + return 1; + unsigned short* top = &(rep->s[index2]); + if (*top & m2) + return 1; + while (s < top) + if (*s++ != 0) + return 1; + return 0; + } +} + +int BitSet::next(int p, int b) const +{ + ++p; + int index = BitSet_index(p); + int pos = BitSet_pos(p); + + int l = rep->len; + + if (index >= l) + { + if (rep->virt == b) + return p; + else + return -1; + } + int j = index; + unsigned short* s = rep->s; + unsigned short a = s[j] >> pos; + int i = pos; + + if (b == 1) + { + for (; i < BITSETBITS && a != 0; ++i) + { + if (a & 1) + return j * BITSETBITS + i; + a >>= 1; + } + for (++j; j < l; ++j) + { + a = s[j]; + for (i = 0; i < BITSETBITS && a != 0; ++i) + { + if (a & 1) + return j * BITSETBITS + i; + a >>= 1; + } + } + if (rep->virt) + return j * BITSETBITS; + else + return -1; + } + else + { + for (; i < BITSETBITS; ++i) + { + if ((a & 1) == 0) + return j * BITSETBITS + i; + a >>= 1; + } + for (++j; j < l; ++j) + { + a = s[j]; + if (a != ONES) + { + for (i = 0; i < BITSETBITS; ++i) + { + if ((a & 1) == 0) + return j * BITSETBITS + i; + a >>= 1; + } + } + } + if (!rep->virt) + return j * BITSETBITS; + else + return -1; + } +} + +int BitSet::previous(int p, int b) const +{ + if (--p < 0) + return -1; + + int index = BitSet_index(p); + int pos = BitSet_pos(p); + + unsigned short* s = rep->s; + int l = rep->len; + + if (index >= l) + { + if (rep->virt == b) + return p; + else + { + index = l - 1; + pos = BITSETBITS - 1; + } + } + + int j = index; + unsigned short a = s[j]; + + int i = pos; + unsigned short maxbit = 1 << pos; + + if (b == 1) + { + for (; i >= 0 && a != 0; --i) + { + if (a & maxbit) + return j * BITSETBITS + i; + a <<= 1; + } + maxbit = 1 << (BITSETBITS - 1); + for (--j; j >= 0; --j) + { + a = s[j]; + for (i = BITSETBITS - 1; i >= 0 && a != 0; --i) + { + if (a & maxbit) + return j * BITSETBITS + i; + a <<= 1; + } + } + return -1; + } + else + { + if (a != ONES) + { + for (; i >= 0; --i) + { + if ((a & maxbit) == 0) + return j * BITSETBITS + i; + a <<= 1; + } + } + maxbit = 1 << (BITSETBITS - 1); + for (--j; j >= 0; --j) + { + a = s[j]; + if (a != ONES) + { + for (i = BITSETBITS - 1; i >= 0; --i) + { + if ((a & maxbit) == 0) + return j * BITSETBITS + i; + a <<= 1; + } + } + } + return -1; + } +} + +int BitSet::last(int b) const +{ + if (b == rep->virt) + return -1; + else + return previous((rep->len) * BITSETBITS, b); +} + + +extern AllocRing _libgxx_fmtq; + +const char* BitSettoa(const BitSet& x, char f, char t, char star) +{ + trim(x.rep); + + int wrksiz = (x.rep->len + 1) * BITSETBITS + 2; + char* fmtbase = (char *) _libgxx_fmtq.alloc(wrksiz); + char* fmt = fmtbase; + + const unsigned short* s = x.rep->s; + const unsigned short* top = &(s[x.rep->len - 1]); + + while (s < top) + { + unsigned short a = *s++; + for (int j = 0; j < BITSETBITS; ++j) + { + *fmt++ = (a & 1)? t : f; + a >>= 1; + } + } + + if (!x.rep->virt) + { + unsigned short a = *s; + for (int j = 0; j < BITSETBITS && a != 0; ++j) + { + *fmt++ = (a & 1)? t : f; + a >>= 1; + } + *fmt++ = f; + } + else + { + unsigned short a = *s; + unsigned short mask = ONES; + unsigned short himask = (1 << (BITSETBITS - 1)) - 1; + for (int j = 0; j < BITSETBITS && a != mask; ++j) + { + *fmt++ = (a & 1)? t : f; + a = (a >> 1) & himask; + mask = (mask >> 1) & himask; + } + *fmt++ = t; + } + + *fmt++ = star; + *fmt++ = 0; + return fmtbase; +} + +#if defined(__GNUG__) && !defined(NO_NRV) + +BitSet shorttoBitSet(unsigned short w) return r +{ + r.rep = BitSetalloc(0, &w, 1, 0, 2); trim(r.rep); +} + +BitSet longtoBitSet(unsigned long w) return r; +{ + unsigned short u[2]; + u[0] = w & ((unsigned short)(~(0))); + u[1] = w >> BITSETBITS; + r.rep = BitSetalloc(0, &u[0], 2, 0, 3); + trim(r.rep); +} + +BitSet atoBitSet(const char* s, char f, char t, char star) return r +{ + int sl = strlen(s); + if (sl != 0) + { + r.rep = BitSetresize(r.rep, sl / BITSETBITS + 1); + unsigned short* rs = r.rep->s; + unsigned short a = 0; + unsigned short m = 1; + char lastch = 0; + unsigned int i = 0; + unsigned int l = 1; + for(;;) + { + char ch = s[i]; + if (ch == t) + a |= m; + else if (ch == star) + { + if (r.rep->virt = lastch == t) + *rs = a | ~(m - 1); + else + *rs = a; + break; + } + else if (ch != f) + { + *rs = a; + break; + } + lastch = ch; + if (++i == sl) + { + *rs = a; + break; + } + else if (i % BITSETBITS == 0) + { + *rs++ = a; + a = 0; + m = 1; + ++l; + } + else + m <<= 1; + } + r.rep->len = l; + trim(r.rep); + } + return; +} + +#else + +BitSet shorttoBitSet(unsigned short w) +{ + BitSet r; + r.rep = BitSetalloc(0, &w, 1, 0, 2); trim(r.rep); + return r; +} + +BitSet longtoBitSet(unsigned long w) +{ + BitSet r; + unsigned short u[2]; + u[0] = w & ((unsigned short)(~(0))); + u[1] = w >> BITSETBITS; + r.rep = BitSetalloc(0, &u[0], 2, 0, 3); + trim(r.rep); + return r; +} + +BitSet atoBitSet(const char* s, char f, char t, char star) +{ + BitSet r; + int sl = strlen(s); + if (sl != 0) + { + r.rep = BitSetresize(r.rep, sl / BITSETBITS + 1); + unsigned short* rs = r.rep->s; + unsigned short a = 0; + unsigned short m = 1; + char lastch = 0; + unsigned int i = 0; + unsigned int l = 1; + for(;;) + { + char ch = s[i]; + if (ch == t) + a |= m; + else if (ch == star) + { + if (r.rep->virt = lastch == t) + *rs = a | ~(m - 1); + else + *rs = a; + break; + } + else if (ch != f) + { + *rs = a; + break; + } + lastch = ch; + if (++i == sl) + { + *rs = a; + break; + } + else if (i % BITSETBITS == 0) + { + *rs++ = a; + a = 0; + m = 1; + ++l; + } + else + m <<= 1; + } + r.rep->len = l; + trim(r.rep); + } + return r; +} + +#endif + +ostream& operator << (ostream& s, const BitSet& x) +{ + return s << BitSettoa(x); +} + +int BitSet::OK() const +{ + int v = rep != 0; // have a rep + v &= rep->len <= rep->sz; // within bounds + v &= rep->virt == 0 || rep->virt == 1; // valid virtual bit + if (!v) error("invariant failure"); + return v; +} + diff --git a/usr/src/lib/libg++/libg++/BitString.cc b/usr/src/lib/libg++/libg++/BitString.cc new file mode 100644 index 0000000000..ca9ed237f6 --- /dev/null +++ b/usr/src/lib/libg++/libg++/BitString.cc @@ -0,0 +1,2069 @@ +/* +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. +*/ + +/* + BitString class implementation + */ + +#ifdef __GNUG__ +#pragma implementation +#endif +#include +#include +#include +#include +#include +#include + +volatile void BitString::error(const char* msg) const +{ + (*lib_error_handler)("BitString", msg); +} + +// globals + +BitStrRep _nilBitStrRep = { 0, 1, {0} }; + +BitString _nil_BitString; + +#define MINBitStrRep_SIZE 8 +#define MAXBitStrRep_SIZE ((1 << (SHORTBITS - 1)) - 1) + +#ifndef MALLOC_MIN_OVERHEAD +#define MALLOC_MIN_OVERHEAD 4 +#endif + +#define ONES ((unsigned short)(~0L)) +#define MAXBIT (1 << (BITSTRBITS - 1)) + +/* + * bit manipulation utilities +*/ + +// break things up into .s indices and positions + +inline static int BitStr_len(int l) +{ + return (unsigned)(l) / BITSTRBITS + 1; +} + + +// mask out low bits + +static inline unsigned short lmask(int p) +{ + if (p <= 0) + return ONES; + else + return ONES << p; +} + +// mask out high bits + +static inline unsigned short rmask(int p) +{ + int s = BITSTRBITS - 1 - p; + if (s <= 0) + return ONES; + else + return ONES >> s; +} + + +// mask out unused bits in last word of rep + +inline static void check_last(BitStrRep* r) +{ + r->s[r->len / BITSTRBITS] &= ONES >> (BITSTRBITS - (r->len & (BITSTRBITS - 1))); +} + +// merge bits from next word + +static inline unsigned short borrow_hi(const unsigned short a[], int ind, + int maxind, int p) +{ + if (ind < maxind) + return (a[ind] >> p) | (a[ind+1] << (BITSTRBITS - p)); + else + return (a[ind] >> p); +} + +// merge bits from prev word + +static inline unsigned short borrow_lo(const unsigned short a[], int ind, + int minind, int p) +{ + if (ind > minind) + return (a[ind] << (BITSTRBITS - 1 - p)) | (a[ind-1] >> (p + 1)); + else + return (a[ind] << (BITSTRBITS - 1 - p)); +} + +// same with bounds check (for masks shorter than patterns) + +static inline unsigned short safe_borrow_hi(const unsigned short a[], int ind, + int maxind, int p) +{ + if (ind > maxind) + return 0; + else if (ind == maxind) + return(a[ind] >> p); + else + return (a[ind] >> p) | (a[ind+1] << (BITSTRBITS - p)); +} + + +static inline unsigned short safe_borrow_lo(const unsigned short a[], int ind, + int minind, int p) +{ + if (ind < minind) + return 0; + else if (ind == minind) + return (a[ind] << (BITSTRBITS - 1 - p)); + else + return (a[ind] << (BITSTRBITS - 1 - p)) | (a[ind-1] >> (p + 1)); +} + +// copy bits from a word boundary + +static inline void bit_copy(const unsigned short* ss, unsigned short* ds, + int nbits) +{ + if (ss != ds) + { + int n = (unsigned)(nbits) / BITSTRBITS; + if (n > 0) bcopy((void*)ss, (void*)ds, n * sizeof(short)); + unsigned short m = ONES << (nbits & (BITSTRBITS - 1)); + ds[n] = (ss[n] & ~m) | (ds[n] & m); + } +} + +// clear bits from a word boundary + +static inline void bit_clear(unsigned short* ds, int nbits) +{ + int n = (unsigned)(nbits) / BITSTRBITS; + if (n > 0) bzero((void*)ds, n * sizeof(short)); + ds[n] &= ONES << (nbits & (BITSTRBITS - 1)); +} + + + +// Copy ss from starts to fences-1 into ds starting at startd. +// This will work even if ss & ds overlap. +// The g++ optimizer does very good things with the messy shift expressions! + +static void bit_transfer(const unsigned short* ss, int starts, int fences, + unsigned short* ds, int startd) +{ + if (starts >= fences || ss == 0 || (ss == ds && starts == startd)) + return; + + int sind = BitStr_index(starts); + int spos = BitStr_pos(starts); + int dind = BitStr_index(startd); + int dpos = BitStr_pos(startd); + + if (spos == 0 && dpos == 0) + { + bit_copy(&ss[sind], &ds[dind], fences - starts); + return; + } + + int ends = fences - 1; + int endsind = BitStr_index(ends); + int endspos = BitStr_pos(ends); + int endd = startd + (ends - starts); + int enddind = BitStr_index(endd); + int enddpos = BitStr_pos(endd); + + if (dind == enddind) + { + if (sind == endsind) + ds[dind] = (ds[dind] & ((ONES >> (BITSTRBITS - dpos)) | + (ONES << (enddpos + 1)))) | + (((ss[sind] >> spos) << dpos) & + ~((ONES >> (BITSTRBITS - dpos)) | + (ONES << (enddpos + 1)))); + else + ds[dind] = (ds[dind] & ((ONES >> (BITSTRBITS - dpos)) | + (ONES << (enddpos + 1)))) | + ((((ss[sind] >> spos) | + (ss[sind+1] << (BITSTRBITS - spos))) + << dpos) & + ~((ONES >> (BITSTRBITS - dpos)) | + (ONES << (enddpos + 1)))); + return; + } + else if (sind == endsind) + { + unsigned short saveend = (ds[enddind] & (ONES << (enddpos + 1))) | + (((ss[sind] << (BITSTRBITS - 1 - endspos)) >> + (BITSTRBITS - 1 - enddpos)) & ~(ONES << (enddpos + 1))); + ds[dind] = (ds[dind] & (ONES >> (BITSTRBITS - dpos))) | + (((ss[sind] >> spos) << dpos) & ~(ONES >> (BITSTRBITS - dpos))); + ds[enddind] = saveend; + return; + } + + unsigned short saveend = (ds[enddind] & (ONES << (enddpos + 1))) | + ((((ss[endsind] << (BITSTRBITS - 1 - endspos)) | + (ss[endsind-1] >> (endspos + 1))) >> + (BITSTRBITS - 1 - enddpos)) & ~(ONES << (enddpos + 1))); + unsigned short savestart = (ds[dind] & (ONES >> (BITSTRBITS - dpos))) | + ((((ss[sind] >> spos) | (ss[sind+1] << (BITSTRBITS - spos))) << dpos) + & ~(ONES >> (BITSTRBITS - dpos))); + + + if (ds != ss || startd < starts) + { + int pos = spos - dpos; + if (pos < 0) + pos += BITSTRBITS; + else + ++sind; + + for (;;) // lag by one in case of overlaps + { + if (dind == enddind - 1) + { + ds[dind] = savestart; + ds[enddind] = saveend; + return; + } + else + { + unsigned short tmp = ss[sind] >> pos; + if (++sind <= endsind) tmp |= ss[sind] << (BITSTRBITS - pos); + ds[dind++] = savestart; + savestart = tmp; + } + } + } + else + { + int pos = endspos - enddpos; + if (pos <= 0) + { + pos += BITSTRBITS; + --endsind; + } + for (;;) + { + if (enddind == dind + 1) + { + ds[enddind] = saveend; + ds[dind] = savestart; + return; + } + else + { + unsigned short tmp = ss[endsind] << (BITSTRBITS - pos); + if (--endsind >= sind) tmp |= ss[endsind] >> pos; + ds[enddind--] = saveend; + saveend = tmp; + } + } + } +} + +// allocate a new rep; pad to near a power of two + +inline static BitStrRep* BSnew(int newlen) +{ + unsigned int siz = sizeof(BitStrRep) + BitStr_len(newlen) * sizeof(short) + + MALLOC_MIN_OVERHEAD; + unsigned int allocsiz = MINBitStrRep_SIZE;; + while (allocsiz < siz) allocsiz <<= 1; + allocsiz -= MALLOC_MIN_OVERHEAD; + if (allocsiz >= MAXBitStrRep_SIZE * sizeof(short)) + (*lib_error_handler)("BitString", "Requested length out of range"); + + BitStrRep* rep = (BitStrRep *) new char[allocsiz]; + bzero(rep, allocsiz); + rep->sz = (allocsiz - sizeof(BitStrRep) + sizeof(short)) / sizeof(short); + return rep; +} + +BitStrRep* BStr_alloc(BitStrRep* old, const unsigned short* src, + int startpos, int endp, int newlen) +{ + if (old == &_nilBitStrRep) old = 0; + if (newlen < 0) newlen = 0; + int news = BitStr_len(newlen); + BitStrRep* rep; + if (old == 0 || news > old->sz) + rep = BSnew(newlen); + else + rep = old; + rep->len = newlen; + + if (src != 0 && endp > 0 && (src != rep->s || startpos > 0)) + bit_transfer(src, startpos, endp, rep->s, 0); + + check_last(rep); + + if (old != rep && old != 0) delete old; + + return rep; +} + +BitStrRep* BStr_resize(BitStrRep* old, int newlen) +{ + BitStrRep* rep; + if (newlen < 0) newlen = 0; + int news = BitStr_len(newlen); + if (old == 0 || old == &_nilBitStrRep) + { + rep = BSnew(newlen); + } + else if (news > old->sz) + { + rep = BSnew(newlen); + bcopy(old->s, rep->s, BitStr_len(old->len) * sizeof(short)); + delete old; + } + else + rep = old; + + rep->len = newlen; + check_last(rep); + return rep; +} + +BitStrRep* BStr_copy(BitStrRep* old, const BitStrRep* src) +{ + BitStrRep* rep; + if (old == src && old != &_nilBitStrRep) return old; + if (old == &_nilBitStrRep) old = 0; + if (src == &_nilBitStrRep) src = 0; + if (src == 0) + { + if (old == 0) + rep = BSnew(0); + else + rep = old; + rep->len = 0; + } + else + { + int newlen = src->len; + int news = BitStr_len(newlen); + if (old == 0 || news > old->sz) + { + rep = BSnew(newlen); + if (old != 0) delete old; + } + else + rep = old; + + bcopy(src->s, rep->s, news * sizeof(short)); + rep->len = newlen; + } + check_last(rep); + return rep; +} + + +int operator == (const BitString& x, const BitString& y) +{ + return x.rep->len == y.rep->len && + bcmp((void*)x.rep->s, (void*)y.rep->s, + BitStr_len(x.rep->len) * sizeof(short)) == 0; +} + +int operator <= (const BitString& x, const BitString& y) +{ + unsigned int xl = x.rep->len; + unsigned int yl = y.rep->len; + if (xl > yl) + return 0; + + const unsigned short* xs = x.rep->s; + const unsigned short* topx = &(xs[BitStr_len(xl)]); + const unsigned short* ys = y.rep->s; + + while (xs < topx) + { + unsigned short a = *xs++; + unsigned short b = *ys++; + if ((a | b) != b) + return 0; + } + return 1; +} + +int operator < (const BitString& x, const BitString& y) +{ + unsigned short xl = x.rep->len; + unsigned short yl = y.rep->len; + if (xl > yl) + return 0; + + const unsigned short* xs = x.rep->s; + const unsigned short* ys = y.rep->s; + const unsigned short* topx = &(xs[BitStr_len(xl)]); + const unsigned short* topy = &(ys[BitStr_len(yl)]); + int one_diff = 0; + while (xs < topx) + { + unsigned short a = *xs++; + unsigned short b = *ys++; + unsigned short c = a | b; + if (c != b) + return 0; + else if (c != a) + one_diff = 1; + } + if (one_diff) + return 1; + else + { + while (ys < topy) + if (*ys++ != 0) + return 1; + return 0; + } +} + +int lcompare(const BitString& x, const BitString& y) +{ + unsigned int xl = x.rep->len; + unsigned int yl = y.rep->len; + + const unsigned short* xs = x.rep->s; + const unsigned short* topx = &(xs[BitStr_len(xl)]); + const unsigned short* ys = y.rep->s; + const unsigned short* topy = &(ys[BitStr_len(yl)]); + + while (xs < topx && ys < topy) + { + unsigned short a = *xs++; + unsigned short b = *ys++; + if (a != b) + { + unsigned short mask = 1; + for (;;) + { + unsigned short abit = (a & mask) != 0; + unsigned short bbit = (b & mask) != 0; + int diff = abit - bbit; + if (diff != 0) + return diff; + else + mask <<= 1; + } + } + } + return xl - yl; +} + +int BitString::count(unsigned int b) const +{ + check_last(rep); + int xwds = BitStr_len(rep->len); + int xlast = BitStr_pos(rep->len); + int l = 0; + const unsigned short* s = rep->s; + const unsigned short* tops = &(s[xwds - 1]); + unsigned short a; + int i; + if (b != 0) + { + while (s < tops) + { + a = *s++; + for (i = 0; i < BITSTRBITS && a != 0; ++i) + { + if (a & 1) + ++l; + a >>= 1; + } + } + a = *s; + for (i = 0; i < xlast && a != 0; ++i) + { + if (a & 1) + ++l; + a >>= 1; + } + } + else + { + unsigned short maxbit = 1 << (BITSTRBITS - 1); + while (s < tops) + { + a = *s++; + for (i = 0; i < BITSTRBITS; ++i) + { + if ((a & maxbit) == 0) + ++l; + a <<= 1; + } + } + maxbit = 1 << (xlast - 1); + a = *s; + for (i = 0; i < xlast; ++i) + { + if ((a & maxbit) == 0) + ++l; + a <<= 1; + } + } + return l; +} + + +BitStrRep* cmpl(const BitStrRep* src, BitStrRep* r) +{ + r = BStr_copy(r, src); + unsigned short* rs = r->s; + unsigned short* topr = &(rs[BitStr_len(r->len)]); + while (rs < topr) + { + unsigned short cmp = ~(*rs); + *rs++ = cmp; + } + check_last(r); + return r; +} + + +BitStrRep* and(const BitStrRep* x, const BitStrRep* y, BitStrRep* r) +{ + int xrsame = x == r; + int yrsame = y == r; + + unsigned int xl = x->len; + unsigned int yl = y->len; + unsigned int rl = (xl <= yl)? xl : yl; + + r = BStr_resize(r, rl); + + unsigned short* rs = r->s; + unsigned short* topr = &(rs[BitStr_len(rl)]); + const unsigned short* xs = (xrsame)? rs : x->s; + const unsigned short* ys = (yrsame)? rs : y->s; + + while (rs < topr) *rs++ = *xs++ & *ys++; + check_last(r); + return r; +} + +BitStrRep* or(const BitStrRep* x, const BitStrRep* y, BitStrRep* r) +{ + unsigned int xl = x->len; + unsigned int yl = y->len; + unsigned int rl = (xl >= yl)? xl : yl; + int xrsame = x == r; + int yrsame = y == r; + + r = BStr_resize(r, rl); + + unsigned short* rs = r->s; + const unsigned short* xs = (xrsame)? rs : x->s; + const unsigned short* topx = &(xs[BitStr_len(xl)]); + const unsigned short* ys = (yrsame)? rs : y->s; + const unsigned short* topy = &(ys[BitStr_len(yl)]); + + if (xl <= yl) + { + while (xs < topx) *rs++ = *xs++ | *ys++; + if (rs != ys) while (ys < topy) *rs++ = *ys++; + } + else + { + while (ys < topy) *rs++ = *xs++ | *ys++; + if (rs != xs) while (xs < topx) *rs++ = *xs++; + } + check_last(r); + return r; +} + + +BitStrRep* xor(const BitStrRep* x, const BitStrRep* y, BitStrRep* r) +{ + unsigned int xl = x->len; + unsigned int yl = y->len; + unsigned int rl = (xl >= yl)? xl : yl; + int xrsame = x == r; + int yrsame = y == r; + + r = BStr_resize(r, rl); + + unsigned short* rs = r->s; + const unsigned short* xs = (xrsame)? rs : x->s; + const unsigned short* topx = &(xs[BitStr_len(xl)]); + const unsigned short* ys = (yrsame)? rs : y->s; + const unsigned short* topy = &(ys[BitStr_len(yl)]); + + if (xl <= yl) + { + while (xs < topx) *rs++ = *xs++ ^ *ys++; + if (rs != ys) while (ys < topy) *rs++ = *ys++; + } + else + { + while (ys < topy) *rs++ = *xs++ ^ *ys++; + if (rs != xs) while (xs < topx) *rs++ = *xs++; + } + check_last(r); + return r; +} + + +BitStrRep* diff(const BitStrRep* x, const BitStrRep* y, BitStrRep* r) +{ + unsigned int xl = x->len; + unsigned int yl = y->len; + int xrsame = x == y; + int yrsame = y == r; + + r = BStr_resize(r, xl); + + unsigned short* rs = r->s; + const unsigned short* xs = (xrsame)? rs : x->s; + const unsigned short* topx = &(xs[BitStr_len(xl)]); + const unsigned short* ys = (yrsame)? rs : y->s; + const unsigned short* topy = &(ys[BitStr_len(yl)]); + + if (xl <= yl) + { + while (xs < topx) *rs++ = *xs++ & ~(*ys++); + } + else + { + while (ys < topy) *rs++ = *xs++ & ~(*ys++); + if (rs != xs) while (xs < topx) *rs++ = *xs++; + } + check_last(r); + return r; +} + + +BitStrRep* cat(const BitStrRep* x, const BitStrRep* y, BitStrRep* r) +{ + unsigned int xl = x->len; + unsigned int yl = y->len; + unsigned int rl = xl + yl; + int xrsame = x == r; + int yrsame = y == r; + + if (yrsame) + { + if (xrsame) + { + r = BStr_resize(r, rl); + bit_transfer(r->s, 0, yl, r->s, xl); + } + else + { + BitStrRep* tmp = BStr_copy(0, y); + r = BStr_resize(r, rl); + bit_copy(x->s, r->s, xl); + bit_transfer(tmp->s, 0, yl, r->s, xl); + delete tmp; + } + } + else + { + r = BStr_resize(r, rl); + if (!xrsame) bit_copy(x->s, r->s, xl); + bit_transfer(y->s, 0, yl, r->s, xl); + } + check_last(r); + return r; +} + +BitStrRep* cat(const BitStrRep* x, unsigned int bit, BitStrRep* r) +{ + unsigned int xl = x->len; + int xrsame = x == r; + r = BStr_resize(r, xl+1); + if (!xrsame) bit_copy(x->s, r->s, xl); + if (bit) + r->s[BitStr_index(xl)] |= (1 << (BitStr_pos(xl))); + else + r->s[BitStr_index(xl)] &= ~(1 << (BitStr_pos(xl))); + check_last(r); + return r; +} + +BitStrRep* lshift(const BitStrRep* x, int s, BitStrRep* r) +{ + int xrsame = x == r; + int xl = x->len; + int rl = xl + s; + if (s == 0) + r = BStr_copy(r, x); + else if (rl <= 0) + { + r = BStr_resize(r, 0); + r->len = 0; + r->s[0] = 0; + } + else if (s > 0) + { + r = BStr_resize(r, rl); + const unsigned short* xs = (xrsame)? r->s : x->s; + bit_transfer(xs, 0, xl, r->s, s); + bit_clear(r->s, s); + } + else if (xrsame) + { + r = BStr_resize(r, xl); + r->len = rl; + bit_transfer(r->s, -s, xl, r->s, 0); + } + else + { + r = BStr_resize(r, rl); + bit_transfer(x->s, -s, xl, r->s, 0); + } + check_last(r); + return r; +} + + +void BitString::set(int p) +{ + if (p < 0) error("Illegal bit index"); + if (p >= rep->len) rep = BStr_resize(rep, p + 1); + rep->s[BitStr_index(p)] |= (1 << (BitStr_pos(p))); +} + +void BitString::assign(int p, unsigned int bit) +{ + if (p < 0) error("Illegal bit index"); + if (p >= rep->len) rep = BStr_resize(rep, p + 1); + if (bit) + rep->s[BitStr_index(p)] |= (1 << (BitStr_pos(p))); + else + rep->s[BitStr_index(p)] &= ~(1 << (BitStr_pos(p))); +} + +void BitString::clear(int p) +{ + if (p < 0) error("Illegal bit index"); + if (p >= rep->len) rep = BStr_resize(rep, p + 1); + rep->s[BitStr_index(p)] &= ~(1 << (BitStr_pos(p))); +} + +void BitString::clear() +{ + if (rep == &_nilBitStrRep) return; + bit_clear(rep->s, rep->len); +} + +void BitString::set() +{ + if (rep == &_nilBitStrRep) return; + unsigned short* s = rep->s; + unsigned short* tops = &(s[BitStr_len(rep->len)]); + while (s < tops) *s++ = ONES; + check_last(rep); +} + +void BitString::invert(int p) +{ + if (p < 0) error("Illegal bit index"); + if (p >= rep->len) rep = BStr_resize(rep, p + 1); + rep->s[BitStr_index(p)] ^= (1 << (BitStr_pos(p))); +} + + + +void BitString::set(int from, int to) +{ + if (from < 0 || from > to) error("Illegal bit index"); + if (to >= rep->len) rep = BStr_resize(rep, to+1); + + int ind1 = BitStr_index(from); + int pos1 = BitStr_pos(from); + int ind2 = BitStr_index(to); + int pos2 = BitStr_pos(to); + unsigned short* s = &(rep->s[ind1]); + unsigned short m1 = lmask(pos1); + unsigned short m2 = rmask(pos2); + if (ind2 == ind1) + *s |= m1 & m2; + else + { + *s++ |= m1; + unsigned short* top = &(rep->s[ind2]); + *top |= m2; + while (s < top) + *s++ = ONES; + } +} + +void BitString::clear(int from, int to) +{ + if (from < 0 || from > to) error("Illegal bit index"); + if (to >= rep->len) rep = BStr_resize(rep, to+1); + + int ind1 = BitStr_index(from); + int pos1 = BitStr_pos(from); + int ind2 = BitStr_index(to); + int pos2 = BitStr_pos(to); + unsigned short* s = &(rep->s[ind1]); + unsigned short m1 = lmask(pos1); + unsigned short m2 = rmask(pos2); + if (ind2 == ind1) + *s &= ~(m1 & m2); + else + { + *s++ &= ~m1; + unsigned short* top = &(rep->s[ind2]); + *top &= ~m2; + while (s < top) + *s++ = 0; + } +} + +void BitString::invert(int from, int to) +{ + if (from < 0 || from > to) error("Illegal bit index"); + if (to >= rep->len) rep = BStr_resize(rep, to+1); + + int ind1 = BitStr_index(from); + int pos1 = BitStr_pos(from); + int ind2 = BitStr_index(to); + int pos2 = BitStr_pos(to); + unsigned short* s = &(rep->s[ind1]); + unsigned short m1 = lmask(pos1); + unsigned short m2 = rmask(pos2); + if (ind2 == ind1) + *s ^= m1 & m2; + else + { + *s++ ^= m1; + unsigned short* top = &(rep->s[ind2]); + *top ^= m2; + while (s < top) + { + unsigned short cmp = ~(*s); + *s++ = cmp; + } + } +} + + +int BitString::test(int from, int to) const +{ + if (from < 0 || from > to || from >= rep->len) return 0; + + int ind1 = BitStr_index(from); + int pos1 = BitStr_pos(from); + int ind2 = BitStr_index(to); + int pos2 = BitStr_pos(to); + + if (to >= rep->len) + { + ind2 = BitStr_index(rep->len - 1); + pos2 = BitStr_pos(rep->len - 1); + } + + const unsigned short* s = &(rep->s[ind1]); + unsigned short m1 = lmask(pos1); + unsigned short m2 = rmask(pos2); + + if (ind2 == ind1) + return (*s & m1 & m2) != 0; + else + { + if (*s++ & m1) + return 1; + unsigned short* top = &(rep->s[ind2]); + if (*top & m2) + return 1; + while (s < top) + if (*s++ != 0) + return 1; + return 0; + } +} + +int BitString::next(int p, unsigned int b) const +{ + if (++p >= rep->len) + return -1; + + int ind = BitStr_index(p); + int pos = BitStr_pos(p); + int l = BitStr_len(rep->len); + + int j = ind; + const unsigned short* s = rep->s; + unsigned short a = s[j] >> pos; + int i = pos; + + if (b != 0) + { + for (; i < BITSTRBITS && a != 0; ++i) + { + if (a & 1) + return j * BITSTRBITS + i; + a >>= 1; + } + for (++j; j < l; ++j) + { + a = s[j]; + for (i = 0; i < BITSTRBITS && a != 0; ++i) + { + if (a & 1) + return j * BITSTRBITS + i; + a >>= 1; + } + } + return -1; + } + else + { + int last = BitStr_pos(rep->len); + if (j == l - 1) + { + for (; i < last; ++i) + { + if ((a & 1) == 0) + return j * BITSTRBITS + i; + a >>= 1; + } + return -1; + } + + for (; i < BITSTRBITS; ++i) + { + if ((a & 1) == 0) + return j * BITSTRBITS + i; + a >>= 1; + } + for (++j; j < l - 1; ++j) + { + a = s[j]; + if (a != ONES) + { + for (i = 0; i < BITSTRBITS; ++i) + { + if ((a & 1) == 0) + return j * BITSTRBITS + i; + a >>= 1; + } + } + } + a = s[j]; + for (i = 0; i < last; ++i) + { + if ((a & 1) == 0) + return j * BITSTRBITS + i; + a >>= 1; + } + return -1; + } +} + +int BitString::previous(int p, unsigned int b) const +{ + if (--p < 0) + return -1; + + int ind = BitStr_index(p); + int pos = BitStr_pos(p); + + const unsigned short* s = rep->s; + + if (p >= rep->len) + { + ind = BitStr_index(rep->len - 1); + pos = BitStr_pos(rep->len - 1); + } + + int j = ind; + unsigned short a = s[j]; + + int i = pos; + unsigned short maxbit = 1 << pos; + + if (b != 0) + { + for (; i >= 0 && a != 0; --i) + { + if (a & maxbit) + return j * BITSTRBITS + i; + a <<= 1; + } + maxbit = 1 << (BITSTRBITS - 1); + for (--j; j >= 0; --j) + { + a = s[j]; + for (i = BITSTRBITS - 1; i >= 0 && a != 0; --i) + { + if (a & maxbit) + return j * BITSTRBITS + i; + a <<= 1; + } + } + return -1; + } + else + { + if (a != ONES) + { + for (; i >= 0; --i) + { + if ((a & maxbit) == 0) + return j * BITSTRBITS + i; + a <<= 1; + } + } + maxbit = 1 << (BITSTRBITS - 1); + for (--j; j >= 0; --j) + { + a = s[j]; + if (a != ONES) + { + for (i = BITSTRBITS - 1; i >= 0; --i) + { + if ((a & maxbit) == 0) + return j * BITSTRBITS + i; + a <<= 1; + } + } + } + return -1; + } +} + + +int BitString::search(int startx, int lengthx, + const unsigned short* ys, int starty, int lengthy) const +{ + const unsigned short* xs = rep->s; + int ylen = lengthy - starty; + int righty = lengthy - 1; + int rev = startx < 0; + if (rev) + { + int leftx = 0; + int rightx = lengthx + startx; + startx = rightx - ylen + 1; + if (ylen == 0) return startx; + if (starty < 0 || righty < 0 || startx < 0 || startx >= lengthx) return -1; + + int xind = BitStr_index(startx); + int xpos = BitStr_pos(startx); + int yind = BitStr_index(starty); + int ypos = BitStr_pos(starty); + + int rightxind = BitStr_index(rightx); + + unsigned short x = borrow_hi(xs, xind, rightxind, xpos); + + int rightyind = BitStr_index(righty); + int rightypos = BitStr_pos(righty); + unsigned short y = borrow_hi(ys, yind, rightyind, ypos); + unsigned short ymask; + if (yind == rightyind) + ymask = rmask(rightypos); + else if (yind+1 == rightyind) + ymask = rmask(BITSTRBITS - ypos + rightypos + 1); + else + ymask = ONES; + + int p = startx; + for (;;) + { + if ((x & ymask) == y) + { + int xi = xind; + int yi = yind; + for (;;) + { + if (++yi > rightyind || ++xi > rightxind) + return p; + unsigned short tx = borrow_hi(xs, xi, rightxind, xpos); + unsigned short ty = borrow_hi(ys, yi, rightyind, ypos); + if (yi == rightyind) + tx &= rmask(rightypos); + else if (yi+1 == rightyind) + tx &= rmask(BITSTRBITS - ypos + rightypos + 1); + if (tx != ty) + break; + } + } + if (--p < leftx) + return -1; + if (--xpos < 0) + { + xpos = BITSTRBITS - 1; + --xind; + } + x = borrow_hi(xs, xind, rightxind, xpos); + } + } + else + { + + int rightx = lengthx - 1; + if (ylen == 0) return startx; + if (starty < 0 || righty < 0 || startx < 0 || startx >= lengthx) return -1; + + int xind = BitStr_index(startx); + int xpos = BitStr_pos(startx); + int yind = BitStr_index(starty); + int ypos = BitStr_pos(starty); + + int rightxind = BitStr_index(rightx); + + unsigned short x = borrow_hi(xs, xind, rightxind, xpos); + unsigned short nextx = (xind >= rightxind) ? 0 : (xs[xind+1] >> xpos); + + int rightyind = BitStr_index(righty); + int rightypos = BitStr_pos(righty); + unsigned short y = borrow_hi(ys, yind, rightyind, ypos); + unsigned short ymask; + if (yind == rightyind) + ymask = rmask(rightypos); + else if (yind+1 == rightyind) + ymask = rmask(BITSTRBITS - ypos + rightypos + 1); + else + ymask = ONES; + + int p = startx; + for (;;) + { + if ((x & ymask) == y) + { + int xi = xind; + int yi = yind; + for (;;) + { + if (++yi > rightyind || ++xi > rightxind) + return p; + unsigned short tx = borrow_hi(xs, xi, rightxind, xpos); + unsigned short ty = borrow_hi(ys, yi, rightyind, ypos); + if (yi == rightyind) + tx &= rmask(rightypos); + else if (yi+1 == rightyind) + tx &= rmask(BITSTRBITS - ypos + rightypos + 1); + if (tx != ty) + break; + } + } + if (++p > rightx) + return -1; + if (++xpos == BITSTRBITS) + { + xpos = 0; + x = xs[++xind]; + nextx = (xind >= rightxind) ? 0 : xs[xind+1]; + } + else + { + x >>= 1; + if (nextx & 1) + x |= MAXBIT; + nextx >>= 1; + } + } + } +} + + +int BitPattern::search(const unsigned short* xs, int startx, int lengthx) const +{ + const unsigned short* ys = pattern.rep->s; + const unsigned short* ms = mask.rep->s; + int righty = pattern.rep->len - 1; + int rightm = mask.rep->len - 1; + + int rev = startx < 0; + if (rev) + { + int leftx = 0; + int rightx = lengthx + startx; + startx = rightx - righty; + + if (righty < 0) return startx; + if (startx < 0 || startx >= lengthx) return -1; + + int xind = BitStr_index(startx); + int xpos = BitStr_pos(startx); + + int rightxind = BitStr_index(rightx); + + int rightmind = BitStr_index(rightm); + int rightyind = BitStr_index(righty); + + unsigned short x = safe_borrow_hi(xs, xind, rightxind, xpos); + unsigned short m = safe_borrow_hi(ms, 0, rightmind, 0); + unsigned short y = safe_borrow_hi(ys, 0, rightyind, 0) & m; + + int p = startx; + for (;;) + { + if ((x & m) == y) + { + int xi = xind; + int yi = 0; + for (;;) + { + if (++yi > rightyind || ++xi > rightxind) + return p; + unsigned short tm = safe_borrow_hi(ms, yi, rightmind, 0); + unsigned short ty = safe_borrow_hi(ys, yi, rightyind, 0); + unsigned short tx = safe_borrow_hi(xs, xi, rightxind, xpos); + if ((tx & tm) != (ty & tm)) + break; + } + } + if (--p < leftx) + return -1; + if (--xpos < 0) + { + xpos = BITSTRBITS - 1; + --xind; + } + x = safe_borrow_hi(xs, xind, rightxind, xpos); + } + } + else + { + + int rightx = lengthx - 1; + + if (righty < 0) return startx; + if (startx < 0 || startx >= lengthx) return -1; + + int xind = BitStr_index(startx); + int xpos = BitStr_pos(startx); + + int rightxind = BitStr_index(rightx); + + int rightmind = BitStr_index(rightm); + int rightyind = BitStr_index(righty); + + unsigned short x = safe_borrow_hi(xs, xind, rightxind, xpos); + unsigned short m = safe_borrow_hi(ms, 0, rightmind, 0); + unsigned short y = safe_borrow_hi(ys, 0, rightyind, 0) & m; + + unsigned short nextx = (xind >= rightxind) ? 0 : (xs[xind+1] >> xpos); + + int p = startx; + for (;;) + { + if ((x & m) == y) + { + int xi = xind; + int yi = 0; + for (;;) + { + if (++yi > rightyind || ++xi > rightxind) + return p; + unsigned short tm = safe_borrow_hi(ms, yi, rightmind, 0); + unsigned short ty = safe_borrow_hi(ys, yi, rightyind, 0); + unsigned short tx = safe_borrow_hi(xs, xi, rightxind, xpos); + if ((tx & tm) != (ty & tm)) + break; + } + } + if (++p > rightx) + return -1; + if (++xpos == BITSTRBITS) + { + xpos = 0; + x = xs[++xind]; + nextx = (xind >= rightxind) ? 0 : xs[xind+1]; + } + else + { + x >>= 1; + if (nextx & 1) + x |= MAXBIT; + nextx >>= 1; + } + } + } +} + +int BitString::match(int startx, int lengthx, int exact, + const unsigned short* ys, int starty, int yl) const +{ + const unsigned short* xs = rep->s; + int ylen = yl - starty; + int righty = yl - 1; + + int rightx; + int rev = startx < 0; + if (rev) + { + rightx = lengthx + startx; + startx = rightx - ylen + 1; + if (exact && startx != 0) + return 0; + } + else + { + rightx = lengthx - 1; + if (exact && rightx - startx != righty) + return 0; + } + + if (ylen == 0) return 1; + if (righty < 0 || startx < 0 || startx >= lengthx) return 0; + + int xi = BitStr_index(startx); + int xpos = BitStr_pos(startx); + int yi = BitStr_index(starty); + int ypos = BitStr_pos(starty); + + int rightxind = BitStr_index(rightx); + int rightyind = BitStr_index(righty); + int rightypos = BitStr_pos(righty); + + for (;;) + { + unsigned short x = borrow_hi(xs, xi, rightxind, xpos); + unsigned short y = borrow_hi(ys, yi, rightyind, ypos); + if (yi == rightyind) + x &= rmask(rightypos); + else if (yi+1 == rightyind) + x &= rmask(BITSTRBITS - ypos + rightypos + 1); + if (x != y) + return 0; + else if (++yi > rightyind || ++xi > rightxind) + return 1; + } +} + +int BitPattern::match(const unsigned short* xs, int startx, + int lengthx, int exact) const +{ + const unsigned short* ys = pattern.rep->s; + int righty = pattern.rep->len - 1; + unsigned short* ms = mask.rep->s; + int rightm = mask.rep->len - 1; + + int rightx; + int rev = startx < 0; + if (rev) + { + rightx = lengthx + startx; + startx = rightx - righty; + if (exact && startx != 0) + return 0; + } + else + { + rightx = lengthx - 1; + if (exact && rightx - startx != righty) + return 0; + } + + if (righty < 0) return 1; + if (startx < 0 || startx >= lengthx) return 0; + + int xind = BitStr_index(startx); + int xpos = BitStr_pos(startx); + int yind = 0; + + int rightxind = BitStr_index(rightx); + int rightyind = BitStr_index(righty); + int rightmind = BitStr_index(rightm); + + for(;;) + { + unsigned short m = safe_borrow_hi(ms, yind, rightmind, 0); + unsigned short x = safe_borrow_hi(xs, xind, rightxind, xpos) & m; + unsigned short y = safe_borrow_hi(ys, yind, rightyind, 0) & m; + if (x != y) + return 0; + else if (++yind > rightyind || ++xind > rightxind) + return 1; + } +} + +void BitSubString::operator = (const BitString& y) +{ + if (&S == &_nil_BitString) return; + BitStrRep* targ = S.rep; + + int ylen = y.rep->len; + int sl = targ->len - len + ylen; + + if (y.rep == targ || ylen > len) + { + BitStrRep* oldtarg = targ; + targ = BStr_alloc(0, 0, 0, 0, sl); + bit_transfer(oldtarg->s, 0, pos, targ->s, 0); + bit_transfer(y.rep->s, 0, ylen, targ->s, pos); + bit_transfer(oldtarg->s, pos+len, oldtarg->len, targ->s, pos + ylen); + delete oldtarg; + } + else if (len == ylen) + bit_transfer(y.rep->s, 0, len, targ->s, pos); + else if (ylen < len) + { + bit_transfer(y.rep->s, 0, ylen, targ->s, pos); + bit_transfer(targ->s, pos+len, targ->len, targ->s, pos + ylen); + targ->len = sl; + } + check_last(targ); + S.rep = targ; +} + +void BitSubString::operator = (const BitSubString& y) +{ + if (&S == &_nil_BitString) return; + BitStrRep* targ = S.rep; + + if (len == 0 || pos >= targ->len) + return; + + int sl = targ->len - len + y.len; + + if (y.S.rep == targ || y.len > len) + { + BitStrRep* oldtarg = targ; + targ = BStr_alloc(0, 0, 0, 0, sl); + bit_copy(oldtarg->s, targ->s, pos); + bit_transfer(y.S.rep->s, y.pos, y.pos+y.len, targ->s, pos); + bit_transfer(oldtarg->s, pos+len, oldtarg->len, targ->s, pos + y.len); + delete oldtarg; + } + else if (len == y.len) + bit_transfer(y.S.rep->s, y.pos, y.pos+y.len, targ->s, pos); + else if (y.len < len) + { + bit_transfer(y.S.rep->s, y.pos, y.pos+y.len, targ->s, pos); + bit_transfer(targ->s, pos+len, targ->len, targ->s, pos + y.len); + targ->len = sl; + } + check_last(targ); + S.rep = targ; +} + +BitSubString BitString::at(int first, int len) +{ + return _substr(first, len); +} + +BitSubString BitString::before(int pos) +{ + return _substr(0, pos); +} + +BitSubString BitString::after(int pos) +{ + return _substr(pos + 1, rep->len - (pos + 1)); +} + +BitSubString BitString::at(const BitString& y, int startpos) +{ + int first = search(startpos, rep->len, y.rep->s, 0, y.rep->len); + return _substr(first, y.rep->len); +} + +BitSubString BitString::before(const BitString& y, int startpos) +{ + int last = search(startpos, rep->len, y.rep->s, 0, y.rep->len); + return _substr(0, last); +} + +BitSubString BitString::after(const BitString& y, int startpos) +{ + int first = search(startpos, rep->len, y.rep->s, 0, y.rep->len); + if (first >= 0) first += y.rep->len; + return _substr(first, rep->len - first); +} + + +BitSubString BitString::at(const BitSubString& y, int startpos) +{ + int first = search(startpos, rep->len, y.S.rep->s, y.pos, y.len); + return _substr(first, y.len); +} + +BitSubString BitString::before(const BitSubString& y, int startpos) +{ + int last = search(startpos, rep->len, y.S.rep->s, y.pos, y.len); + return _substr(0, last); +} + +BitSubString BitString::after(const BitSubString& y, int startpos) +{ + int first = search(startpos, rep->len, y.S.rep->s, y.pos, y.len); + if (first >= 0) first += y.len; + return _substr(first, rep->len - first); +} + +BitSubString BitString::at(const BitPattern& r, int startpos) +{ + int first = r.search(rep->s, startpos, rep->len); + return _substr(first, r.pattern.rep->len); +} + + +BitSubString BitString::before(const BitPattern& r, int startpos) +{ + int first = r.search(rep->s, startpos, rep->len); + return _substr(0, first); +} + +BitSubString BitString::after(const BitPattern& r, int startpos) +{ + int first = r.search(rep->s, startpos, rep->len); + if (first >= 0) first += r.pattern.rep->len; + return _substr(first, rep->len - first); +} + +#if defined(__GNUG__) && !defined(NO_NRV) + +BitString common_prefix(const BitString& x, const BitString& y, int startpos) + return r +{ + unsigned int xl = x.rep->len; + unsigned int yl = y.rep->len; + + int startx, starty; + if (startpos < 0) + { + startx = xl + startpos; + starty = yl + startpos; + } + else + startx = starty = startpos; + + if (startx < 0 || startx >= xl || starty < 0 || starty >= yl) + return; + + const unsigned short* xs = &(x.rep->s[BitStr_index(startx)]); + unsigned short a = *xs++; + int xp = startx; + + const unsigned short* ys = &(y.rep->s[BitStr_index(starty)]); + unsigned short b = *ys++; + int yp = starty; + + for(; xp < xl && yp < yl; ++xp, ++yp) + { + unsigned short xbit = 1 << (BitStr_pos(xp)); + unsigned short ybit = 1 << (BitStr_pos(yp)); + if (((a & xbit) == 0) != ((b & ybit) == 0)) + break; + if (xbit == MAXBIT) + a = *xs++; + if (ybit == MAXBIT) + b = *ys++; + } + r.rep = BStr_alloc(0, x.rep->s, startx, xp, xp - startx); +} + + +BitString common_suffix(const BitString& x, const BitString& y, int startpos) + return r; +{ + unsigned int xl = x.rep->len; + unsigned int yl = y.rep->len; + + int startx, starty; + if (startpos < 0) + { + startx = xl + startpos; + starty = yl + startpos; + } + else + startx = starty = startpos; + + if (startx < 0 || startx >= xl || starty < 0 || starty >= yl) + return; + + const unsigned short* xs = &(x.rep->s[BitStr_index(startx)]); + unsigned short a = *xs--; + int xp = startx; + + const unsigned short* ys = &(y.rep->s[BitStr_index(starty)]); + unsigned short b = *ys--; + int yp = starty; + + for(; xp >= 0 && yp >= 0; --xp, --yp) + { + unsigned short xbit = 1 << (BitStr_pos(xp)); + unsigned short ybit = 1 << (BitStr_pos(yp)); + if (((a & xbit) == 0) != ((b & ybit) == 0)) + break; + if (xbit == 1) + a = *xs--; + if (ybit == 1) + b = *ys--; + } + r.rep = BStr_alloc(0, x.rep->s, xp+1, startx+1, startx - xp); +} + +BitString reverse(const BitString& x) return r +{ + unsigned int yl = x.rep->len; + BitStrRep* y = BStr_resize(0, yl); + if (yl > 0) + { + const unsigned short* ls = x.rep->s; + unsigned short lm = 1; + unsigned short* rs = &(y->s[BitStr_index(yl - 1)]); + unsigned short rm = 1 << (BitStr_pos(yl - 1)); + for (unsigned int l = 0; l < yl; ++l) + { + if (*ls & lm) + *rs |= rm; + if (lm == MAXBIT) + { + ++ls; + lm = 1; + } + else + lm <<= 1; + if (rm == 1) + { + --rs; + rm = MAXBIT; + } + else + rm >>= 1; + } + } + r.rep = y; +} + +BitString atoBitString(const char* s, char f, char t) return res +{ + int sl = strlen(s); + BitStrRep* r = BStr_resize(0, sl); + if (sl != 0) + { + unsigned int rl = 0; + unsigned short* rs = r->s; + unsigned short a = 0; + unsigned short m = 1; + unsigned int i = 0; + for(;;) + { + char ch = s[i]; + if (ch != t && ch != f) + { + *rs = a; + break; + } + ++rl; + if (ch == t) + a |= m; + if (++i == sl) + { + *rs = a; + break; + } + else if (i % BITSTRBITS == 0) + { + *rs++ = a; + a = 0; + m = 1; + } + else + m <<= 1; + } + r = BStr_resize(r, rl); + } + res.rep = r; +} + +BitPattern atoBitPattern(const char* s, char f,char t,char x) return r +{ + int sl = strlen(s); + if (sl != 0) + { + unsigned int rl = 0; + r.pattern.rep = BStr_resize(r.pattern.rep, sl); + r.mask.rep = BStr_resize(r.mask.rep, sl); + unsigned short* rs = r.pattern.rep->s; + unsigned short* ms = r.mask.rep->s; + unsigned short a = 0; + unsigned short b = 0; + unsigned short m = 1; + unsigned int i = 0; + for(;;) + { + char ch = s[i]; + if (ch != t && ch != f && ch != x) + { + *rs = a; + *ms = b; + break; + } + ++rl; + if (ch == t) + { + a |= m; + b |= m; + } + else if (ch == f) + { + b |= m; + } + if (++i == sl) + { + *rs = a; + *ms = b; + break; + } + else if (i % BITSTRBITS == 0) + { + *rs++ = a; + *ms++ = b; + a = 0; + b = 0; + m = 1; + } + else + m <<= 1; + } + r.pattern.rep = BStr_resize(r.pattern.rep, rl); + r.mask.rep = BStr_resize(r.mask.rep, rl); + } + return; +} + +#else /* NO_NRV */ + +BitString common_prefix(const BitString& x, const BitString& y, int startpos) +{ + BitString r; + + unsigned int xl = x.rep->len; + unsigned int yl = y.rep->len; + + int startx, starty; + if (startpos < 0) + { + startx = xl + startpos; + starty = yl + startpos; + } + else + startx = starty = startpos; + + if (startx < 0 || startx >= xl || starty < 0 || starty >= yl) + return r; + + const unsigned short* xs = &(x.rep->s[BitStr_index(startx)]); + unsigned short a = *xs++; + int xp = startx; + + const unsigned short* ys = &(y.rep->s[BitStr_index(starty)]); + unsigned short b = *ys++; + int yp = starty; + + for(; xp < xl && yp < yl; ++xp, ++yp) + { + unsigned short xbit = 1 << (BitStr_pos(xp)); + unsigned short ybit = 1 << (BitStr_pos(yp)); + if (((a & xbit) == 0) != ((b & ybit) == 0)) + break; + if (xbit == MAXBIT) + a = *xs++; + if (ybit == MAXBIT) + b = *ys++; + } + r.rep = BStr_alloc(0, x.rep->s, startx, xp, xp - startx); + return r; +} + + +BitString common_suffix(const BitString& x, const BitString& y, int startpos) +{ + BitString r; + unsigned int xl = x.rep->len; + unsigned int yl = y.rep->len; + + int startx, starty; + if (startpos < 0) + { + startx = xl + startpos; + starty = yl + startpos; + } + else + startx = starty = startpos; + + if (startx < 0 || startx >= xl || starty < 0 || starty >= yl) + return r; + + const unsigned short* xs = &(x.rep->s[BitStr_index(startx)]); + unsigned short a = *xs--; + int xp = startx; + + const unsigned short* ys = &(y.rep->s[BitStr_index(starty)]); + unsigned short b = *ys--; + int yp = starty; + + for(; xp >= 0 && yp >= 0; --xp, --yp) + { + unsigned short xbit = 1 << (BitStr_pos(xp)); + unsigned short ybit = 1 << (BitStr_pos(yp)); + if (((a & xbit) == 0) != ((b & ybit) == 0)) + break; + if (xbit == 1) + a = *xs--; + if (ybit == 1) + b = *ys--; + } + r.rep = BStr_alloc(0, x.rep->s, xp+1, startx+1, startx - xp); + return r; +} + +BitString reverse(const BitString& x) +{ + BitString r; + unsigned int yl = x.rep->len; + BitStrRep* y = BStr_resize(0, yl); + if (yl > 0) + { + const unsigned short* ls = x.rep->s; + unsigned short lm = 1; + unsigned short* rs = &(y->s[BitStr_index(yl - 1)]); + unsigned short rm = 1 << (BitStr_pos(yl - 1)); + for (unsigned int l = 0; l < yl; ++l) + { + if (*ls & lm) + *rs |= rm; + if (lm == MAXBIT) + { + ++ls; + lm = 1; + } + else + lm <<= 1; + if (rm == 1) + { + --rs; + rm = MAXBIT; + } + else + rm >>= 1; + } + } + r.rep = y; + return r; +} + +BitString atoBitString(const char* s, char f, char t) +{ + BitString res; + int sl = strlen(s); + BitStrRep* r = BStr_resize(0, sl); + if (sl != 0) + { + unsigned int rl = 0; + unsigned short* rs = r->s; + unsigned short a = 0; + unsigned short m = 1; + unsigned int i = 0; + for(;;) + { + char ch = s[i]; + if (ch != t && ch != f) + { + *rs = a; + break; + } + ++rl; + if (ch == t) + a |= m; + if (++i == sl) + { + *rs = a; + break; + } + else if (i % BITSTRBITS == 0) + { + *rs++ = a; + a = 0; + m = 1; + } + else + m <<= 1; + } + r = BStr_resize(r, rl); + } + res.rep = r; + return res; +} + +BitPattern atoBitPattern(const char* s, char f,char t,char x) +{ + BitPattern r; + int sl = strlen(s); + if (sl != 0) + { + unsigned int rl = 0; + r.pattern.rep = BStr_resize(r.pattern.rep, sl); + r.mask.rep = BStr_resize(r.mask.rep, sl); + unsigned short* rs = r.pattern.rep->s; + unsigned short* ms = r.mask.rep->s; + unsigned short a = 0; + unsigned short b = 0; + unsigned short m = 1; + unsigned int i = 0; + for(;;) + { + char ch = s[i]; + if (ch != t && ch != f && ch != x) + { + *rs = a; + *ms = b; + break; + } + ++rl; + if (ch == t) + { + a |= m; + b |= m; + } + else if (ch == f) + { + b |= m; + } + if (++i == sl) + { + *rs = a; + *ms = b; + break; + } + else if (i % BITSTRBITS == 0) + { + *rs++ = a; + *ms++ = b; + a = 0; + b = 0; + m = 1; + } + else + m <<= 1; + } + r.pattern.rep = BStr_resize(r.pattern.rep, rl); + r.mask.rep = BStr_resize(r.mask.rep, rl); + } + return r; +} + +#endif + +extern AllocRing _libgxx_fmtq; + +const char* BitStringtoa(const BitString& x, char f, char t) +{ + int wrksiz = x.length() + 2; + char* fmtbase = (char *) _libgxx_fmtq.alloc(wrksiz); + char* fmt = fmtbase; + unsigned int xl = x.rep->len; + const unsigned short* s = x.rep->s; + unsigned short a = 0; + + for (unsigned int i = 0; i < xl; ++i) + { + if (i % BITSTRBITS == 0) + a = *s++; + *fmt++ = (a & 1)? t : f; + a >>= 1; + } + + *fmt = 0; + + return fmtbase; +} + + +ostream& operator << (ostream& s, const BitString& x) +{ + return s << BitStringtoa(x); +} + +const char* BitPatterntoa(const BitPattern& p, char f,char t,char x) +{ + unsigned int pl = p.pattern.rep->len; + unsigned int ml = p.mask.rep->len; + unsigned int l = (pl <= ml)? pl : ml; + + int wrksiz = l + 2; + char* fmtbase = (char *) _libgxx_fmtq.alloc(wrksiz); + char* fmt = fmtbase; + + const unsigned short* ps = p.pattern.rep->s; + const unsigned short* ms = p.mask.rep->s; + unsigned short a = 0; + unsigned short m = 0; + + for (unsigned int i = 0; i < l; ++i) + { + if (i % BITSTRBITS == 0) + { + a = *ps++; + m = *ms++; + } + if (m & 1) + *fmt++ =(a & 1)? t : f; + else + *fmt++ = x; + a >>= 1; + m >>= 1; + } + + *fmt = 0; + return fmtbase; +} + + +ostream& operator << (ostream& s, const BitPattern& x) +{ + return s << BitPatterntoa(x); +} + + +int BitString::OK() const +{ + int v = rep != 0; // have a rep; + v &= BitStr_len(rep->len) <= rep->sz; // within allocated size + if (!v) error("invariant failure"); + return v; +} + +int BitSubString::OK() const +{ + int v = S.OK(); // valid BitString + v &= pos >= 0 && len >= 0; // valid indices + v &= pos + len <= S.rep->len; // within bounds of targ + if (!v) S.error("BitSubString invariant failure"); + return v; +} + +int BitPattern::OK() const +{ + int v = pattern.OK() && mask.OK(); + if (!v) pattern.error("BitPattern invariant failure"); + return v; +} + diff --git a/usr/src/lib/libg++/libg++/regex.cc b/usr/src/lib/libg++/libg++/regex.cc new file mode 100644 index 0000000000..92860f1a18 --- /dev/null +++ b/usr/src/lib/libg++/libg++/regex.cc @@ -0,0 +1,1782 @@ +/* Extended regular expression matching and search. + Copyright (C) 1985 Free Software Foundation, Inc. + + NO WARRANTY + + BECAUSE THIS PROGRAM IS LICENSED FREE OF CHARGE, WE PROVIDE ABSOLUTELY +NO WARRANTY, TO THE EXTENT PERMITTED BY APPLICABLE STATE LAW. EXCEPT +WHEN OTHERWISE STATED IN WRITING, FREE SOFTWARE FOUNDATION, INC, +RICHARD M. STALLMAN AND/OR OTHER PARTIES PROVIDE THIS PROGRAM "AS IS" +WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, +BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND +FITNESS FOR A PARTICULAR PURPOSE. THE ENTIRE RISK AS TO THE QUALITY +AND PERFORMANCE OF THE PROGRAM IS WITH YOU. SHOULD THE PROGRAM PROVE +DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING, REPAIR OR +CORRECTION. + + IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW WILL RICHARD M. +STALLMAN, THE FREE SOFTWARE FOUNDATION, INC., AND/OR ANY OTHER PARTY +WHO MAY MODIFY AND REDISTRIBUTE THIS PROGRAM AS PERMITTED BELOW, BE +LIABLE TO YOU FOR DAMAGES, INCLUDING ANY LOST PROFITS, LOST MONIES, OR +OTHER SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE +USE OR INABILITY TO USE (INCLUDING BUT NOT LIMITED TO LOSS OF DATA OR +DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY THIRD PARTIES OR +A FAILURE OF THE PROGRAM TO OPERATE WITH ANY OTHER PROGRAMS) THIS +PROGRAM, EVEN IF YOU HAVE BEEN ADVISED OF THE POSSIBILITY OF SUCH +DAMAGES, OR FOR ANY CLAIM BY ANY OTHER PARTY. + + GENERAL PUBLIC LICENSE TO COPY + + 1. You may copy and distribute verbatim copies of this source file +as you receive it, in any medium, provided that you conspicuously and +appropriately publish on each copy a valid copyright notice "Copyright +(C) 1985 Free Software Foundation, Inc."; and include following the +copyright notice a verbatim copy of the above disclaimer of warranty +and of this License. You may charge a distribution fee for the +physical act of transferring a copy. + + 2. You may modify your copy or copies of this source file or +any portion of it, and copy and distribute such modifications under +the terms of Paragraph 1 above, provided that you also do the following: + + a) cause the modified files to carry prominent notices stating + that you changed the files and the date of any change; and + + b) cause the whole of any work that you distribute or publish, + that in whole or in part contains or is a derivative of this + program or any part thereof, to be licensed at no charge to all + third parties on terms identical to those contained in this + License Agreement (except that you may choose to grant more extensive + warranty protection to some or all third parties, at your option). + + c) You may charge a distribution fee for the physical act of + transferring a copy, and you may at your option offer warranty + protection in exchange for a fee. + +Mere aggregation of another unrelated program with this program (or its +derivative) on a volume of a storage or distribution medium does not bring +the other program under the scope of these terms. + + 3. You may copy and distribute this program (or a portion or derivative +of it, under Paragraph 2) in object code or executable form under the terms +of Paragraphs 1 and 2 above provided that you also do one of the following: + + a) accompany it with the complete corresponding machine-readable + source code, which must be distributed under the terms of + Paragraphs 1 and 2 above; or, + + b) accompany it with a written offer, valid for at least three + years, to give any third party free (except for a nominal + shipping charge) a complete machine-readable copy of the + corresponding source code, to be distributed under the terms of + Paragraphs 1 and 2 above; or, + + c) accompany it with the information you received as to where the + corresponding source code may be obtained. (This alternative is + allowed only for noncommercial distribution and only if you + received the program in object code or executable form alone.) + +For an executable file, complete source code means all the source code for +all modules it contains; but, as a special exception, it need not include +source code for modules which are standard libraries that accompany the +operating system on which the executable file runs. + + 4. You may not copy, sublicense, distribute or transfer this program +except as expressly provided under this License Agreement. Any attempt +otherwise to copy, sublicense, distribute or transfer this program is void and +your rights to use the program under this License agreement shall be +automatically terminated. However, parties who have received computer +software programs from you with this License Agreement will not have +their licenses terminated so long as such parties remain in full compliance. + + 5. If you wish to incorporate parts of this program into other free +programs whose distribution conditions are different, write to the Free +Software Foundation at 675 Mass Ave, Cambridge, MA 02139. We have not yet +worked out a simple rule that can be stated here, but we will often permit +this. We will be guided by the two goals of preserving the free status of +all derivatives of our free software and of promoting the sharing and reuse of +software. + + +In other words, you are welcome to use, share and improve this program. +You are forbidden to forbid anyone else to use, share and improve +what you give them. Help stamp out software-hoarding! */ + + +/* To test, compile with -Dtest. + This Dtestable feature turns this into a self-contained program + which reads a pattern, describes how it compiles, + then reads a string and searches for it. */ + +#ifdef emacs + +/* The `emacs' switch turns on certain special matching commands + that make sense only in emacs. */ + +#ifdef __GNUG__ +#pragma implementation +#endif +#include "config.h" +#include "lisp.h" +#include "buffer.h" +#include "syntax.h" + +#else /* not emacs */ + +#include +#include + +/* + * Define the syntax stuff, so we can do the \<...\> things. + */ + +#ifndef Sword /* must be non-zero in some of the tests below... */ +#define Sword 1 +#endif + +#define SYNTAX(c) re_syntax_table[c] + +#ifdef SYNTAX_TABLE + +char *re_syntax_table; + +#else + +static char re_syntax_table[256]; + +static void +init_syntax_once (void) +{ + register int c; + static int done = 0; + + if (done) + return; + + bzero (re_syntax_table, sizeof re_syntax_table); + + for (c = 'a'; c <= 'z'; c++) + re_syntax_table[c] = Sword; + + for (c = 'A'; c <= 'Z'; c++) + re_syntax_table[c] = Sword; + + for (c = '0'; c <= '9'; c++) + re_syntax_table[c] = Sword; + + done = 1; +} + +#endif /* SYNTAX_TABLE */ +#endif /* not emacs */ + +#include "regex.h" + +/* Number of failure points to allocate space for initially, + when matching. If this number is exceeded, more space is allocated, + so it is not a hard limit. */ + +#ifndef NFAILURES +#define NFAILURES 80 +#endif /* NFAILURES */ + +/* width of a byte in bits */ + +#define BYTEWIDTH 8 + +#ifndef SIGN_EXTEND_CHAR +#define SIGN_EXTEND_CHAR(x) (x) +#endif + +static int obscure_syntax = 0; + +/* Specify the precise syntax of regexp for compilation. + This provides for compatibility for various utilities + which historically have different, incompatible syntaxes. + + The argument SYNTAX is a bit-mask containing the two bits + RE_NO_BK_PARENS and RE_NO_BK_VBAR. */ + +int +re_set_syntax (int syntax) +{ + int ret; + + ret = obscure_syntax; + obscure_syntax = syntax; + return ret; +} + +/* re_compile_pattern takes a regular-expression string + and converts it into a buffer full of byte commands for matching. + + PATTERN is the address of the pattern string + SIZE is the length of it. + BUFP is a struct re_pattern_buffer * which points to the info + on where to store the byte commands. + This structure contains a char * which points to the + actual space, which should have been obtained with malloc. + re_compile_pattern may use realloc to grow the buffer space. + + The number of bytes of commands can be found out by looking in + the struct re_pattern_buffer that bufp pointed to, + after re_compile_pattern returns. +*/ + +#define PATPUSH(ch) (*b++ = (char) (ch)) + +#define PATFETCH(c) \ + {if (p == pend) goto end_of_pattern; \ + c = * (unsigned char *) p++; \ + if (translate) c = translate[c]; } + +#define PATFETCH_RAW(c) \ + {if (p == pend) goto end_of_pattern; \ + c = * (unsigned char *) p++; } + +#define PATUNFETCH p-- + +#define EXTEND_BUFFER \ + { char *old_buffer = bufp->buffer; \ + if (bufp->allocated == (1<<16)) goto too_big; \ + bufp->allocated *= 2; \ + if (bufp->allocated > (1<<16)) bufp->allocated = (1<<16); \ + if (!(bufp->buffer = (char *) realloc (bufp->buffer, bufp->allocated))) \ + goto memory_exhausted; \ + c = bufp->buffer - old_buffer; \ + b += c; \ + if (fixup_jump) \ + fixup_jump += c; \ + if (laststart) \ + laststart += c; \ + begalt += c; \ + if (pending_exact) \ + pending_exact += c; \ + } + +static void store_jump (char *, char, char *); +static void insert_jump (char, char *, char *, char *); +int re_match_2 (struct re_pattern_buffer *, unsigned char *, int, unsigned char *, + int, int, struct re_registers *, int mstop); + +char * +re_compile_pattern (char *pattern, int size, struct re_pattern_buffer *bufp) +{ + register char *b = bufp->buffer; + register char *p = pattern; + char *pend = pattern + size; + register unsigned c, c1; + char *p1; + unsigned char *translate = (unsigned char *) bufp->translate; + + /* address of the count-byte of the most recently inserted "exactn" command. + This makes it possible to tell whether a new exact-match character + can be added to that command or requires a new "exactn" command. */ + + char *pending_exact = 0; + + /* address of the place where a forward-jump should go + to the end of the containing expression. + Each alternative of an "or", except the last, ends with a forward-jump + of this sort. */ + + char *fixup_jump = 0; + + /* address of start of the most recently finished expression. + This tells postfix * where to find the start of its operand. */ + + char *laststart = 0; + + /* In processing a repeat, 1 means zero matches is allowed */ + + char zero_times_ok; + + /* In processing a repeat, 1 means many matches is allowed */ + + char many_times_ok; + + /* address of beginning of regexp, or inside of last \( */ + + char *begalt = b; + + /* Stack of information saved by \( and restored by \). + Four stack elements are pushed by each \(: + First, the value of b. + Second, the value of fixup_jump. + Third, the value of regnum. + Fourth, the value of begalt. */ + + int stackb[40]; + int *stackp = stackb; + int *stacke = stackb + 40; + int *stackt; + + /* Counts \('s as they are encountered. Remembered for the matching \), + where it becomes the "register number" to put in the stop_memory command */ + + int regnum = 1; + + bufp->fastmap_accurate = 0; + +#ifndef emacs +#ifndef SYNTAX_TABLE + /* + * Initialize the syntax table. + */ + init_syntax_once(); +#endif +#endif + + if (bufp->allocated == 0) + { + bufp->allocated = 28; + if (bufp->buffer) + /* EXTEND_BUFFER loses when bufp->allocated is 0 */ + bufp->buffer = (char *) realloc (bufp->buffer, 28); + else + /* Caller did not allocate a buffer. Do it for him */ + bufp->buffer = (char *) new char[28]; + if (!bufp->buffer) goto memory_exhausted; + begalt = b = bufp->buffer; + } + + while (p != pend) + { + if (b - bufp->buffer > bufp->allocated - 10) + /* Note that EXTEND_BUFFER clobbers c */ + EXTEND_BUFFER; + + PATFETCH (c); + + switch (c) + { + case '$': + if (obscure_syntax & RE_TIGHT_VBAR) + { + if (! (obscure_syntax & RE_CONTEXT_INDEP_OPS) && p != pend) + goto normal_char; + /* Make operand of last vbar end before this `$'. */ + if (fixup_jump) + store_jump (fixup_jump, jump, b); + fixup_jump = 0; + PATPUSH (endline); + break; + } + + /* $ means succeed if at end of line, but only in special contexts. + If randomly in the middle of a pattern, it is a normal character. */ + if (p == pend || *p == '\n' + || (obscure_syntax & RE_CONTEXT_INDEP_OPS) + || (obscure_syntax & RE_NO_BK_PARENS + ? *p == ')' + : *p == '\\' && p[1] == ')') + || (obscure_syntax & RE_NO_BK_VBAR + ? *p == '|' + : *p == '\\' && p[1] == '|')) + { + PATPUSH (endline); + break; + } + goto normal_char; + + case '^': + /* ^ means succeed if at beg of line, but only if no preceding pattern. */ + + if (laststart && p[-2] != '\n' + && ! (obscure_syntax & RE_CONTEXT_INDEP_OPS)) + goto normal_char; + if (obscure_syntax & RE_TIGHT_VBAR) + { + if (p != pattern + 1 + && ! (obscure_syntax & RE_CONTEXT_INDEP_OPS)) + goto normal_char; + PATPUSH (begline); + begalt = b; + } + else + PATPUSH (begline); + break; + + case '+': + case '?': + if (obscure_syntax & RE_BK_PLUS_QM) + goto normal_char; + handle_plus: + case '*': + /* If there is no previous pattern, char not special. */ + if (!laststart && ! (obscure_syntax & RE_CONTEXT_INDEP_OPS)) + goto normal_char; + /* If there is a sequence of repetition chars, + collapse it down to equivalent to just one. */ + zero_times_ok = 0; + many_times_ok = 0; + while (1) + { + zero_times_ok |= c != '+'; + many_times_ok |= c != '?'; + if (p == pend) + break; + PATFETCH (c); + if (c == '*') + ; + else if (!(obscure_syntax & RE_BK_PLUS_QM) + && (c == '+' || c == '?')) + ; + else if ((obscure_syntax & RE_BK_PLUS_QM) + && c == '\\') + { + int c1; + PATFETCH (c1); + if (!(c1 == '+' || c1 == '?')) + { + PATUNFETCH; + PATUNFETCH; + break; + } + c = c1; + } + else + { + PATUNFETCH; + break; + } + } + + /* Star, etc. applied to an empty pattern is equivalent + to an empty pattern. */ + if (!laststart) + break; + + /* Now we know whether 0 matches is allowed, + and whether 2 or more matches is allowed. */ + if (many_times_ok) + { + /* If more than one repetition is allowed, + put in a backward jump at the end. */ + store_jump (b, maybe_finalize_jump, laststart - 3); + b += 3; + } + insert_jump (on_failure_jump, laststart, b + 3, b); + pending_exact = 0; + b += 3; + if (!zero_times_ok) + { + /* At least one repetition required: insert before the loop + a skip over the initial on-failure-jump instruction */ + insert_jump (dummy_failure_jump, laststart, laststart + 6, b); + b += 3; + } + break; + + case '.': + laststart = b; + PATPUSH (anychar); + break; + + case '[': + while (b - bufp->buffer + > bufp->allocated - 3 - (1 << BYTEWIDTH) / BYTEWIDTH) + /* Note that EXTEND_BUFFER clobbers c */ + EXTEND_BUFFER; + + laststart = b; + if (*p == '^') + PATPUSH (charset_not), p++; + else + PATPUSH (charset); + p1 = p; + + PATPUSH ((1 << BYTEWIDTH) / BYTEWIDTH); + /* Clear the whole map */ + bzero (b, (1 << BYTEWIDTH) / BYTEWIDTH); + /* Read in characters and ranges, setting map bits */ + while (1) + { + PATFETCH (c); + if (c == ']' && p != p1 + 1) break; + if (*p == '-' && p[1] != ']') + { + PATFETCH (c1); + PATFETCH (c1); + while (c <= c1) + b[c / BYTEWIDTH] |= 1 << (c % BYTEWIDTH), c++; + } + else + { + b[c / BYTEWIDTH] |= 1 << (c % BYTEWIDTH); + } + } + /* Discard any bitmap bytes that are all 0 at the end of the map. + Decrement the map-length byte too. */ + while ((int) b[-1] > 0 && b[b[-1] - 1] == 0) + b[-1]--; + b += b[-1]; + break; + + case '(': + if (! (obscure_syntax & RE_NO_BK_PARENS)) + goto normal_char; + else + goto handle_open; + + case ')': + if (! (obscure_syntax & RE_NO_BK_PARENS)) + goto normal_char; + else + goto handle_close; + + case '\n': + if (! (obscure_syntax & RE_NEWLINE_OR)) + goto normal_char; + else + goto handle_bar; + + case '|': + if (! (obscure_syntax & RE_NO_BK_VBAR)) + goto normal_char; + else + goto handle_bar; + + case '\\': + if (p == pend) goto invalid_pattern; + PATFETCH_RAW (c); + switch (c) + { + case '(': + if (obscure_syntax & RE_NO_BK_PARENS) + goto normal_backsl; + handle_open: + if (stackp == stacke) goto nesting_too_deep; + if (regnum < RE_NREGS) + { + PATPUSH (start_memory); + PATPUSH (regnum); + } + *stackp++ = b - bufp->buffer; + *stackp++ = fixup_jump ? fixup_jump - bufp->buffer + 1 : 0; + *stackp++ = regnum++; + *stackp++ = begalt - bufp->buffer; + fixup_jump = 0; + laststart = 0; + begalt = b; + break; + + case ')': + if (obscure_syntax & RE_NO_BK_PARENS) + goto normal_backsl; + handle_close: + if (stackp == stackb) goto unmatched_close; + begalt = *--stackp + bufp->buffer; + if (fixup_jump) + store_jump (fixup_jump, jump, b); + if (stackp[-1] < RE_NREGS) + { + PATPUSH (stop_memory); + PATPUSH (stackp[-1]); + } + stackp -= 2; + fixup_jump = 0; + if (*stackp) + fixup_jump = *stackp + bufp->buffer - 1; + laststart = *--stackp + bufp->buffer; + break; + + case '|': + if (obscure_syntax & RE_NO_BK_VBAR) + goto normal_backsl; + handle_bar: + insert_jump (on_failure_jump, begalt, b + 6, b); + pending_exact = 0; + b += 3; + if (fixup_jump) + store_jump (fixup_jump, jump, b); + fixup_jump = b; + b += 3; + laststart = 0; + begalt = b; + break; + +#ifdef emacs + case '=': + PATPUSH (at_dot); + break; + + case 's': + laststart = b; + PATPUSH (syntaxspec); + PATFETCH (c); + PATPUSH (syntax_spec_code[c]); + break; + + case 'S': + laststart = b; + PATPUSH (notsyntaxspec); + PATFETCH (c); + PATPUSH (syntax_spec_code[c]); + break; +#endif /* emacs */ + + case 'w': + laststart = b; + PATPUSH (wordchar); + break; + + case 'W': + laststart = b; + PATPUSH (notwordchar); + break; + + case '<': + PATPUSH (wordbeg); + break; + + case '>': + PATPUSH (wordend); + break; + + case 'b': + PATPUSH (wordbound); + break; + + case 'B': + PATPUSH (notwordbound); + break; + + case '`': + PATPUSH (begbuf); + break; + + case '\'': + PATPUSH (endbuf); + break; + + case '1': + case '2': + case '3': + case '4': + case '5': + case '6': + case '7': + case '8': + case '9': + c1 = c - '0'; + if (c1 >= regnum) + goto normal_char; + for (stackt = stackp - 2; stackt > stackb; stackt -= 4) + if (*stackt == c1) + goto normal_char; + laststart = b; + PATPUSH (duplicate); + PATPUSH (c1); + break; + + case '+': + case '?': + if (obscure_syntax & RE_BK_PLUS_QM) + goto handle_plus; + + default: + normal_backsl: + /* You might think it would be useful for \ to mean + not to translate; but if we don't translate it + it will never match anything. */ + if (translate) c = translate[c]; + goto normal_char; + } + break; + + default: + normal_char: + if (!pending_exact || pending_exact + *pending_exact + 1 != b + || *pending_exact == 0177 || *p == '*' || *p == '^' + || ((obscure_syntax & RE_BK_PLUS_QM) + ? *p == '\\' && (p[1] == '+' || p[1] == '?') + : (*p == '+' || *p == '?'))) + { + laststart = b; + PATPUSH (exactn); + pending_exact = b; + PATPUSH (0); + } + PATPUSH (c); + (*pending_exact)++; + } + } + + if (fixup_jump) + store_jump (fixup_jump, jump, b); + + if (stackp != stackb) goto unmatched_open; + + bufp->used = b - bufp->buffer; + return 0; + + invalid_pattern: + return "Invalid regular expression"; + + unmatched_open: + return "Unmatched \\("; + + unmatched_close: + return "Unmatched \\)"; + + end_of_pattern: + return "Premature end of regular expression"; + + nesting_too_deep: + return "Nesting too deep"; + + too_big: + return "Regular expression too big"; + + memory_exhausted: + return "Memory exhausted"; +} + +/* Store where `from' points a jump operation to jump to where `to' points. + `opcode' is the opcode to store. */ + +static void +store_jump (char *from, char opcode, char *to) +{ + from[0] = opcode; + from[1] = (to - (from + 3)) & 0377; + from[2] = (to - (from + 3)) >> 8; +} + +/* Open up space at char FROM, and insert there a jump to TO. + CURRENT_END gives te end of the storage no in use, + so we know how much data to copy up. + OP is the opcode of the jump to insert. + + If you call this function, you must zero out pending_exact. */ + +static void +insert_jump (char op, char *from, char *to, char *current_end) +{ + register char *pto = current_end + 3; + register char *pfrom = current_end; + while (pfrom != from) + *--pto = *--pfrom; + store_jump (from, op, to); +} + +/* Given a pattern, compute a fastmap from it. + The fastmap records which of the (1 << BYTEWIDTH) possible characters + can start a string that matches the pattern. + This fastmap is used by re_search to skip quickly over totally implausible text. + + The caller must supply the address of a (1 << BYTEWIDTH)-byte data area + as bufp->fastmap. + The other components of bufp describe the pattern to be used. */ + +void +re_compile_fastmap (struct re_pattern_buffer *bufp) +{ + unsigned char *pattern = (unsigned char *) bufp->buffer; + int size = bufp->used; + register char *fastmap = bufp->fastmap; + register unsigned char *p = pattern; + register unsigned char *pend = pattern + size; + register int j; + unsigned char *translate = (unsigned char *) bufp->translate; + + unsigned char *stackb[NFAILURES]; + unsigned char **stackp = stackb; + + bzero (fastmap, (1 << BYTEWIDTH)); + bufp->fastmap_accurate = 1; + bufp->can_be_null = 0; + + while (p) + { + if (p == pend) + { + bufp->can_be_null = 1; + break; + } +#ifdef SWITCH_ENUM_BUG + switch ((int) ((enum regexpcode) *p++)) +#else + switch ((enum regexpcode) *p++) +#endif + { + case exactn: + if (translate) + fastmap[translate[p[1]]] = 1; + else + fastmap[p[1]] = 1; + break; + + case begline: + case before_dot: + case at_dot: + case after_dot: + case begbuf: + case endbuf: + case wordbound: + case notwordbound: + case wordbeg: + case wordend: + continue; + + case endline: + if (translate) + fastmap[translate['\n']] = 1; + else + fastmap['\n'] = 1; + if (bufp->can_be_null != 1) + bufp->can_be_null = 2; + break; + + case finalize_jump: + case maybe_finalize_jump: + case jump: + case dummy_failure_jump: + bufp->can_be_null = 1; + j = *p++ & 0377; + j += SIGN_EXTEND_CHAR (*(char *)p) << 8; + p += j + 1; /* The 1 compensates for missing ++ above */ + if (j > 0) + continue; + /* Jump backward reached implies we just went through + the body of a loop and matched nothing. + Opcode jumped to should be an on_failure_jump. + Just treat it like an ordinary jump. + For a * loop, it has pushed its failure point already; + if so, discard that as redundant. */ + if ((enum regexpcode) *p != on_failure_jump) + continue; + p++; + j = *p++ & 0377; + j += SIGN_EXTEND_CHAR (*(char *)p) << 8; + p += j + 1; /* The 1 compensates for missing ++ above */ + if (stackp != stackb && *stackp == p) + stackp--; + continue; + + case on_failure_jump: + j = *p++ & 0377; + j += SIGN_EXTEND_CHAR (*(char *)p) << 8; + p++; + *++stackp = p + j; + continue; + + case start_memory: + case stop_memory: + p++; + continue; + + case duplicate: + bufp->can_be_null = 1; + fastmap['\n'] = 1; + case anychar: + for (j = 0; j < (1 << BYTEWIDTH); j++) + if (j != '\n') + fastmap[j] = 1; + if (bufp->can_be_null) + return; + /* Don't return; check the alternative paths + so we can set can_be_null if appropriate. */ + break; + + case wordchar: + for (j = 0; j < (1 << BYTEWIDTH); j++) + if (SYNTAX (j) == Sword) + fastmap[j] = 1; + break; + + case notwordchar: + for (j = 0; j < (1 << BYTEWIDTH); j++) + if (SYNTAX (j) != Sword) + fastmap[j] = 1; + break; + +#ifdef emacs + case syntaxspec: + k = *p++; + for (j = 0; j < (1 << BYTEWIDTH); j++) + if (SYNTAX (j) == (enum syntaxcode) k) + fastmap[j] = 1; + break; + + case notsyntaxspec: + k = *p++; + for (j = 0; j < (1 << BYTEWIDTH); j++) + if (SYNTAX (j) != (enum syntaxcode) k) + fastmap[j] = 1; + break; +#endif /* emacs */ + + case charset: + for (j = *p++ * BYTEWIDTH - 1; j >= 0; j--) + if (p[j / BYTEWIDTH] & (1 << (j % BYTEWIDTH))) + { + if (translate) + fastmap[translate[j]] = 1; + else + fastmap[j] = 1; + } + break; + + case charset_not: + /* Chars beyond end of map must be allowed */ + for (j = *p * BYTEWIDTH; j < (1 << BYTEWIDTH); j++) + if (translate) + fastmap[translate[j]] = 1; + else + fastmap[j] = 1; + + for (j = *p++ * BYTEWIDTH - 1; j >= 0; j--) + if (!(p[j / BYTEWIDTH] & (1 << (j % BYTEWIDTH)))) + { + if (translate) + fastmap[translate[j]] = 1; + else + fastmap[j] = 1; + } + break; + } + + /* Get here means we have successfully found the possible starting characters + of one path of the pattern. We need not follow this path any farther. + Instead, look at the next alternative remembered in the stack. */ + if (stackp != stackb) + p = *stackp--; + else + break; + } +} + +/* Like re_search_2, below, but only one string is specified. */ + +int +re_search (struct re_pattern_buffer *pbufp, char *string, int size, + int startpos, int range, struct re_registers *regs) +{ + return re_search_2 (pbufp, 0, 0, string, size, startpos, range, regs, size); +} + +/* Like re_match_2 but tries first a match starting at index STARTPOS, + then at STARTPOS + 1, and so on. + RANGE is the number of places to try before giving up. + If RANGE is negative, the starting positions tried are + STARTPOS, STARTPOS - 1, etc. + It is up to the caller to make sure that range is not so large + as to take the starting position outside of the input strings. + +The value returned is the position at which the match was found, + or -1 if no match was found, + or -2 if error (such as failure stack overflow). */ + +int +re_search_2 (struct re_pattern_buffer *pbufp, char *string1, int size1, char *string2, + int size2, int startpos, register int range, struct re_registers *regs, + int mstop) +{ + register char *fastmap = pbufp->fastmap; + register unsigned char *translate = (unsigned char *) pbufp->translate; + int total = size1 + size2; + int val; + + /* Update the fastmap now if not correct already */ + if (fastmap && !pbufp->fastmap_accurate) + re_compile_fastmap (pbufp); + + /* Don't waste time in a long search for a pattern + that says it is anchored. */ + if (pbufp->used > 0 && (enum regexpcode) pbufp->buffer[0] == begbuf + && range > 0) + { + if (startpos > 0) + return -1; + else + range = 1; + } + + while (1) + { + /* If a fastmap is supplied, skip quickly over characters + that cannot possibly be the start of a match. + Note, however, that if the pattern can possibly match + the null string, we must test it at each starting point + so that we take the first null string we get. */ + + if (fastmap && startpos < total && pbufp->can_be_null != 1) + { + if (range > 0) + { + register int lim = 0; + register unsigned char *p; + int irange = range; + if (startpos < size1 && startpos + range >= size1) + lim = range - (size1 - startpos); + + p = ((unsigned char *) + &(startpos >= size1 ? string2 - size1 : string1)[startpos]); + + if (translate) + { + while (range > lim && !fastmap[translate[*p++]]) + range--; + } + else + { + while (range > lim && !fastmap[*p++]) + range--; + } + startpos += irange - range; + } + else + { + register unsigned char c; + if (startpos >= size1) + c = string2[startpos - size1]; + else + c = string1[startpos]; + c &= 0xff; + if (translate ? !fastmap[translate[c]] : !fastmap[c]) + goto advance; + } + } + + if (range >= 0 && startpos == total + && fastmap && pbufp->can_be_null == 0) + return -1; + + val = re_match_2 (pbufp, (unsigned char *) string1, size1, (unsigned char *) string2, size2, startpos, regs, mstop); + if (0 <= val) + { + if (val == -2) + return -2; + return startpos; + } + +#ifdef C_ALLOCA + alloca (0); +#endif /* C_ALLOCA */ + + advance: + if (!range) break; + if (range > 0) range--, startpos++; else range++, startpos--; + } + return -1; +} + +#ifndef emacs /* emacs never uses this */ +int +re_match (struct re_pattern_buffer *pbufp, char *string, int size, int pos, + struct re_registers *regs) +{ + return re_match_2 (pbufp, (unsigned char *) 0, 0, (unsigned char *) string, size, pos, regs, size); +} +#endif /* emacs */ + +/* Maximum size of failure stack. Beyond this, overflow is an error. */ + +int re_max_failures = 2000; + +static int bcmp_translate(unsigned char *, unsigned char *, int, unsigned char *); + +/* Match the pattern described by PBUFP + against data which is the virtual concatenation of STRING1 and STRING2. + SIZE1 and SIZE2 are the sizes of the two data strings. + Start the match at position POS. + Do not consider matching past the position MSTOP. + + If pbufp->fastmap is nonzero, then it had better be up to date. + + The reason that the data to match are specified as two components + which are to be regarded as concatenated + is so this function can be used directly on the contents of an Emacs buffer. + + -1 is returned if there is no match. -2 is returned if there is + an error (such as match stack overflow). Otherwise the value is the length + of the substring which was matched. */ + +int +re_match_2 (struct re_pattern_buffer *pbufp, unsigned char *string1, int size1, + unsigned char *string2, int size2, int pos, struct re_registers *regs, + int mstop) +{ + register unsigned char *p = (unsigned char *) pbufp->buffer; + register unsigned char *pend = p + pbufp->used; + /* End of first string */ + unsigned char *end1; + /* End of second string */ + unsigned char *end2; + /* Pointer just past last char to consider matching */ + unsigned char *end_match_1, *end_match_2; + register unsigned char *d, *dend; + register int mcnt; + unsigned char *translate = (unsigned char *) pbufp->translate; + + /* Failure point stack. Each place that can handle a failure further down the line + pushes a failure point on this stack. It consists of two char *'s. + The first one pushed is where to resume scanning the pattern; + the second pushed is where to resume scanning the strings. + If the latter is zero, the failure point is a "dummy". + If a failure happens and the innermost failure point is dormant, + it discards that failure point and tries the next one. */ + + unsigned char *initial_stack[2 * NFAILURES]; + unsigned char **stackb = initial_stack; + unsigned char **stackp = stackb, **stacke = &stackb[2 * NFAILURES]; + + /* Information on the "contents" of registers. + These are pointers into the input strings; they record + just what was matched (on this attempt) by some part of the pattern. + The start_memory command stores the start of a register's contents + and the stop_memory command stores the end. + + At that point, regstart[regnum] points to the first character in the register, + regend[regnum] points to the first character beyond the end of the register, + regstart_seg1[regnum] is true iff regstart[regnum] points into string1, + and regend_seg1[regnum] is true iff regend[regnum] points into string1. */ + + unsigned char *regstart[RE_NREGS]; + unsigned char *regend[RE_NREGS]; + unsigned char regstart_seg1[RE_NREGS], regend_seg1[RE_NREGS]; + + /* Set up pointers to ends of strings. + Don't allow the second string to be empty unless both are empty. */ + if (!size2) + { + string2 = string1; + size2 = size1; + string1 = 0; + size1 = 0; + } + end1 = string1 + size1; + end2 = string2 + size2; + + /* Compute where to stop matching, within the two strings */ + if (mstop <= size1) + { + end_match_1 = string1 + mstop; + end_match_2 = string2; + } + else + { + end_match_1 = end1; + end_match_2 = string2 + mstop - size1; + } + + /* Initialize \) text positions to -1 + to mark ones that no \( or \) has been seen for. */ + + for (mcnt = 0; mcnt < sizeof (regend) / sizeof (*regend); mcnt++) + regend[mcnt] = (unsigned char *) -1; + + /* `p' scans through the pattern as `d' scans through the data. + `dend' is the end of the input string that `d' points within. + `d' is advanced into the following input string whenever necessary, + but this happens before fetching; + therefore, at the beginning of the loop, + `d' can be pointing at the end of a string, + but it cannot equal string2. */ + + if (pos <= size1) + d = string1 + pos, dend = end_match_1; + else + d = string2 + pos - size1, dend = end_match_2; + +/* Write PREFETCH; just before fetching a character with *d. */ +#define PREFETCH \ + while (d == dend) \ + { if (dend == end_match_2) goto fail; /* end of string2 => failure */ \ + d = string2; /* end of string1 => advance to string2. */ \ + dend = end_match_2; } + + /* This loop loops over pattern commands. + It exits by returning from the function if match is complete, + or it drops through if match fails at this starting point in the input data. */ + + while (1) + { + if (p == pend) + /* End of pattern means we have succeeded! */ + { + /* If caller wants register contents data back, convert it to indices */ + if (regs) + { + regs->start[0] = pos; + if (dend == end_match_1) + regs->end[0] = d - string1; + else + regs->end[0] = d - string2 + size1; + for (mcnt = 1; mcnt < RE_NREGS; mcnt++) + { + if (regend[mcnt] == (unsigned char *) -1) + { + regs->start[mcnt] = -1; + regs->end[mcnt] = -1; + continue; + } + if (regstart_seg1[mcnt]) + regs->start[mcnt] = regstart[mcnt] - string1; + else + regs->start[mcnt] = regstart[mcnt] - string2 + size1; + if (regend_seg1[mcnt]) + regs->end[mcnt] = regend[mcnt] - string1; + else + regs->end[mcnt] = regend[mcnt] - string2 + size1; + } + } + if (dend == end_match_1) + return (d - string1 - pos); + else + return d - string2 + size1 - pos; + } + + /* Otherwise match next pattern command */ +#ifdef SWITCH_ENUM_BUG + switch ((int) ((enum regexpcode) *p++)) +#else + switch ((enum regexpcode) *p++) +#endif + { + + /* \( is represented by a start_memory, \) by a stop_memory. + Both of those commands contain a "register number" argument. + The text matched within the \( and \) is recorded under that number. + Then, \ turns into a `duplicate' command which + is followed by the numeric value of as the register number. */ + + case start_memory: + regstart[*p] = d; + regstart_seg1[*p++] = (dend == end_match_1); + break; + + case stop_memory: + regend[*p] = d; + regend_seg1[*p++] = (dend == end_match_1); + break; + + case duplicate: + { + int regno = *p++; /* Get which register to match against */ + register unsigned char *d2, *dend2; + + d2 = regstart[regno]; + dend2 = ((regstart_seg1[regno] == regend_seg1[regno]) + ? regend[regno] : end_match_1); + while (1) + { + /* Advance to next segment in register contents, if necessary */ + while (d2 == dend2) + { + if (dend2 == end_match_2) break; + if (dend2 == regend[regno]) break; + d2 = string2, dend2 = regend[regno]; /* end of string1 => advance to string2. */ + } + /* At end of register contents => success */ + if (d2 == dend2) break; + + /* Advance to next segment in data being matched, if necessary */ + PREFETCH; + + /* mcnt gets # consecutive chars to compare */ + mcnt = dend - d; + if (mcnt > dend2 - d2) + mcnt = dend2 - d2; + /* Compare that many; failure if mismatch, else skip them. */ + if (translate ? bcmp_translate (d, d2, mcnt, translate) : bcmp (d, d2, mcnt)) + goto fail; + d += mcnt, d2 += mcnt; + } + } + break; + + case anychar: + /* fetch a data character */ + PREFETCH; + /* Match anything but a newline. */ + if ((translate ? translate[*d++] : *d++) == '\n') + goto fail; + break; + + case charset: + case charset_not: + { + /* Nonzero for charset_not */ + int not = 0; + register int c; + if (*(p - 1) == (unsigned char) charset_not) + not = 1; + + /* fetch a data character */ + PREFETCH; + + if (translate) + c = translate [*d]; + else + c = *d; + + if (c < *p * BYTEWIDTH + && p[1 + c / BYTEWIDTH] & (1 << (c % BYTEWIDTH))) + not = !not; + + p += 1 + *p; + + if (!not) goto fail; + d++; + break; + } + + case begline: + if (d == string1 || d[-1] == '\n') + break; + goto fail; + + case endline: + if (d == end2 + || (d == end1 ? (size2 == 0 || *string2 == '\n') : *d == '\n')) + break; + goto fail; + + /* "or" constructs ("|") are handled by starting each alternative + with an on_failure_jump that points to the start of the next alternative. + Each alternative except the last ends with a jump to the joining point. + (Actually, each jump except for the last one really jumps + to the following jump, because tensioning the jumps is a hassle.) */ + + /* The start of a stupid repeat has an on_failure_jump that points + past the end of the repeat text. + This makes a failure point so that, on failure to match a repetition, + matching restarts past as many repetitions have been found + with no way to fail and look for another one. */ + + /* A smart repeat is similar but loops back to the on_failure_jump + so that each repetition makes another failure point. */ + + case on_failure_jump: + if (stackp == stacke) + { + unsigned char **stackx; + if (stacke - stackb > re_max_failures * 2) + return -2; + stackx = (unsigned char **) alloca (2 * (stacke - stackb) + * sizeof (char *)); + bcopy (stackb, stackx, (stacke - stackb) * sizeof (char *)); + stackp = stackx + (stackp - stackb); + stacke = stackx + 2 * (stacke - stackb); + stackb = stackx; + } + mcnt = *p++ & 0377; + mcnt += SIGN_EXTEND_CHAR (*(char *)p) << 8; + p++; + *stackp++ = mcnt + p; + *stackp++ = d; + break; + + /* The end of a smart repeat has an maybe_finalize_jump back. + Change it either to a finalize_jump or an ordinary jump. */ + + case maybe_finalize_jump: + mcnt = *p++ & 0377; + mcnt += SIGN_EXTEND_CHAR (*(char *)p) << 8; + p++; + { + register unsigned char *p2 = p; + /* Compare what follows with the begining of the repeat. + If we can establish that there is nothing that they would + both match, we can change to finalize_jump */ + while (p2 != pend + && (*p2 == (unsigned char) stop_memory + || *p2 == (unsigned char) start_memory)) + p2++; + if (p2 == pend) + p[-3] = (unsigned char) finalize_jump; + else if (*p2 == (unsigned char) exactn + || *p2 == (unsigned char) endline) + { + register int c = *p2 == (unsigned char) endline ? '\n' : p2[2]; + register unsigned char *p1 = p + mcnt; + /* p1[0] ... p1[2] are an on_failure_jump. + Examine what follows that */ + if (p1[3] == (unsigned char) exactn && p1[5] != c) + p[-3] = (unsigned char) finalize_jump; + else if (p1[3] == (unsigned char) charset + || p1[3] == (unsigned char) charset_not) + { + int not = p1[3] == (unsigned char) charset_not; + if (c < p1[4] * BYTEWIDTH + && p1[5 + c / BYTEWIDTH] & (1 << (c % BYTEWIDTH))) + not = !not; + /* not is 1 if c would match */ + /* That means it is not safe to finalize */ + if (!not) + p[-3] = (unsigned char) finalize_jump; + } + } + } + p -= 2; + if (p[-1] != (unsigned char) finalize_jump) + { + p[-1] = (unsigned char) jump; + goto nofinalize; + } + + /* The end of a stupid repeat has a finalize-jump + back to the start, where another failure point will be made + which will point after all the repetitions found so far. */ + + case finalize_jump: + stackp -= 2; + + case jump: + nofinalize: + mcnt = *p++ & 0377; + mcnt += SIGN_EXTEND_CHAR (*(char *)p) << 8; + p += mcnt + 1; /* The 1 compensates for missing ++ above */ + break; + + case dummy_failure_jump: + if (stackp == stacke) + { + unsigned char **stackx + = (unsigned char **) alloca (2 * (stacke - stackb) + * sizeof (char *)); + bcopy (stackb, stackx, (stacke - stackb) * sizeof (char *)); + stackp = stackx + (stackp - stackb); + stacke = stackx + 2 * (stacke - stackb); + stackb = stackx; + } + *stackp++ = 0; + *stackp++ = 0; + goto nofinalize; + + case wordbound: + if (d == string1 /* Points to first char */ + || d == end2 /* Points to end */ + || (d == end1 && size2 == 0)) /* Points to end */ + break; + if ((SYNTAX (d[-1]) == Sword) + != (SYNTAX (d == end1 ? *string2 : *d) == Sword)) + break; + goto fail; + + case notwordbound: + if (d == string1 /* Points to first char */ + || d == end2 /* Points to end */ + || (d == end1 && size2 == 0)) /* Points to end */ + goto fail; + if ((SYNTAX (d[-1]) == Sword) + != (SYNTAX (d == end1 ? *string2 : *d) == Sword)) + goto fail; + break; + + case wordbeg: + if (d == end2 /* Points to end */ + || (d == end1 && size2 == 0) /* Points to end */ + || SYNTAX (* (d == end1 ? string2 : d)) != Sword) /* Next char not a letter */ + goto fail; + if (d == string1 /* Points to first char */ + || SYNTAX (d[-1]) != Sword) /* prev char not letter */ + break; + goto fail; + + case wordend: + if (d == string1 /* Points to first char */ + || SYNTAX (d[-1]) != Sword) /* prev char not letter */ + goto fail; + if (d == end2 /* Points to end */ + || (d == end1 && size2 == 0) /* Points to end */ + || SYNTAX (d == end1 ? *string2 : *d) != Sword) /* Next char not a letter */ + break; + goto fail; + +#ifdef emacs + case before_dot: + if (((d - string2 <= (unsigned) size2) + ? d - bf_p2 : d - bf_p1) + <= point) + goto fail; + break; + + case at_dot: + if (((d - string2 <= (unsigned) size2) + ? d - bf_p2 : d - bf_p1) + == point) + goto fail; + break; + + case after_dot: + if (((d - string2 <= (unsigned) size2) + ? d - bf_p2 : d - bf_p1) + >= point) + goto fail; + break; + + case wordchar: + mcnt = (int) Sword; + goto matchsyntax; + + case syntaxspec: + mcnt = *p++; + matchsyntax: + PREFETCH; + if (SYNTAX (*d++) != (enum syntaxcode) mcnt) goto fail; + break; + + case notwordchar: + mcnt = (int) Sword; + goto matchnotsyntax; + + case notsyntaxspec: + mcnt = *p++; + matchnotsyntax: + PREFETCH; + if (SYNTAX (*d++) == (enum syntaxcode) mcnt) goto fail; + break; +#else + case wordchar: + PREFETCH; + if (SYNTAX (*d++) == 0) goto fail; + break; + + case notwordchar: + PREFETCH; + if (SYNTAX (*d++) != 0) goto fail; + break; +#endif /* not emacs */ + + case begbuf: + if (d == string1) /* Note, d cannot equal string2 */ + break; /* unless string1 == string2. */ + goto fail; + + case endbuf: + if (d == end2 || (d == end1 && size2 == 0)) + break; + goto fail; + + case exactn: + /* Match the next few pattern characters exactly. + mcnt is how many characters to match. */ + mcnt = *p++; + if (translate) + { + do + { + PREFETCH; + if (translate[*d++] != *p++) goto fail; + } + while (--mcnt); + } + else + { + do + { + PREFETCH; + if (*d++ != *p++) goto fail; + } + while (--mcnt); + } + break; + } + continue; /* Successfully matched one pattern command; keep matching */ + + /* Jump here if any matching operation fails. */ + fail: + if (stackp != stackb) + /* A restart point is known. Restart there and pop it. */ + { + if (!stackp[-2]) + { /* If innermost failure point is dormant, flush it and keep looking */ + stackp -= 2; + goto fail; + } + d = *--stackp; + p = *--stackp; + if (d >= string1 && d <= end1) + dend = end_match_1; + } + else break; /* Matching at this starting point really fails! */ + } + return -1; /* Failure to match */ +} + +static int +bcmp_translate (unsigned char *s1, unsigned char *s2, register int len, + unsigned char *translate) +{ + register unsigned char *p1 = s1, *p2 = s2; + while (len) + { + if (translate [*p1++] != translate [*p2++]) return 1; + len--; + } + return 0; +} + +/* Entry points compatible with bsd4.2 regex library */ + +#ifndef emacs + +static struct re_pattern_buffer re_comp_buf; + +char * +re_comp (char *s) +{ + if (!s) + { + if (!re_comp_buf.buffer) + return "No previous regular expression"; + return 0; + } + + if (!re_comp_buf.buffer) + { + if (!(re_comp_buf.buffer = (char *) new char[200])) + return "Memory exhausted"; + re_comp_buf.allocated = 200; + if (!(re_comp_buf.fastmap = (char *) new char[ (1 << BYTEWIDTH)])) + return "Memory exhausted"; + } + return re_compile_pattern (s, strlen (s), &re_comp_buf); +} + +int +re_exec (char *s) +{ + int len = strlen (s); + return 0 <= re_search (&re_comp_buf, s, len, 0, len, 0); +} + +#endif /* emacs */ + +#ifdef test + +#include + +/* Indexed by a character, gives the upper case equivalent of the character */ + +static char upcase[0400] = + { 000, 001, 002, 003, 004, 005, 006, 007, + 010, 011, 012, 013, 014, 015, 016, 017, + 020, 021, 022, 023, 024, 025, 026, 027, + 030, 031, 032, 033, 034, 035, 036, 037, + 040, 041, 042, 043, 044, 045, 046, 047, + 050, 051, 052, 053, 054, 055, 056, 057, + 060, 061, 062, 063, 064, 065, 066, 067, + 070, 071, 072, 073, 074, 075, 076, 077, + 0100, 0101, 0102, 0103, 0104, 0105, 0106, 0107, + 0110, 0111, 0112, 0113, 0114, 0115, 0116, 0117, + 0120, 0121, 0122, 0123, 0124, 0125, 0126, 0127, + 0130, 0131, 0132, 0133, 0134, 0135, 0136, 0137, + 0140, 0101, 0102, 0103, 0104, 0105, 0106, 0107, + 0110, 0111, 0112, 0113, 0114, 0115, 0116, 0117, + 0120, 0121, 0122, 0123, 0124, 0125, 0126, 0127, + 0130, 0131, 0132, 0173, 0174, 0175, 0176, 0177, + 0200, 0201, 0202, 0203, 0204, 0205, 0206, 0207, + 0210, 0211, 0212, 0213, 0214, 0215, 0216, 0217, + 0220, 0221, 0222, 0223, 0224, 0225, 0226, 0227, + 0230, 0231, 0232, 0233, 0234, 0235, 0236, 0237, + 0240, 0241, 0242, 0243, 0244, 0245, 0246, 0247, + 0250, 0251, 0252, 0253, 0254, 0255, 0256, 0257, + 0260, 0261, 0262, 0263, 0264, 0265, 0266, 0267, + 0270, 0271, 0272, 0273, 0274, 0275, 0276, 0277, + 0300, 0301, 0302, 0303, 0304, 0305, 0306, 0307, + 0310, 0311, 0312, 0313, 0314, 0315, 0316, 0317, + 0320, 0321, 0322, 0323, 0324, 0325, 0326, 0327, + 0330, 0331, 0332, 0333, 0334, 0335, 0336, 0337, + 0340, 0341, 0342, 0343, 0344, 0345, 0346, 0347, + 0350, 0351, 0352, 0353, 0354, 0355, 0356, 0357, + 0360, 0361, 0362, 0363, 0364, 0365, 0366, 0367, + 0370, 0371, 0372, 0373, 0374, 0375, 0376, 0377 + }; + +main (int argc, char **argv) +{ + char pat[80]; + struct re_pattern_buffer buf; + int i; + char c; + char fastmap[(1 << BYTEWIDTH)]; + + /* Allow a command argument to specify the style of syntax. */ + if (argc > 1) + obscure_syntax = atoi (argv[1]); + + buf.allocated = 40; + buf.buffer = (char *) new char[buf.allocated]; + buf.fastmap = fastmap; + buf.translate = upcase; + + while (1) + { + gets (pat); + + if (*pat) + { + re_compile_pattern (pat, strlen(pat), &buf); + + for (i = 0; i < buf.used; i++) + printchar (buf.buffer[i]); + + putchar ('\n'); + + printf ("%d allocated, %d used.\n", buf.allocated, buf.used); + + re_compile_fastmap (&buf); + printf ("Allowed by fastmap: "); + for (i = 0; i < (1 << BYTEWIDTH); i++) + if (fastmap[i]) printchar (i); + putchar ('\n'); + } + + gets (pat); /* Now read the string to match against */ + + i = re_match (&buf, pat, strlen (pat), 0, 0); + printf ("Match value %d.\n", i); + } +} + +#ifdef NOTDEF +print_buf (struct re_pattern_buffer *bufp) +{ + int i; + + printf ("buf is :\n----------------\n"); + for (i = 0; i < bufp->used; i++) + printchar (bufp->buffer[i]); + + printf ("\n%d allocated, %d used.\n", bufp->allocated, bufp->used); + + printf ("Allowed by fastmap: "); + for (i = 0; i < (1 << BYTEWIDTH); i++) + if (bufp->fastmap[i]) + printchar (i); + printf ("\nAllowed by translate: "); + if (bufp->translate) + for (i = 0; i < (1 << BYTEWIDTH); i++) + if (bufp->translate[i]) + printchar (i); + printf ("\nfastmap is%s accurate\n", bufp->fastmap_accurate ? "" : "n't"); + printf ("can %s be null\n----------", bufp->can_be_null ? "" : "not"); +} +#endif + +printchar (char c) +{ + if (c < 041 || c >= 0177) + { + putchar ('\\'); + putchar (((c >> 6) & 3) + '0'); + putchar (((c >> 3) & 7) + '0'); + putchar ((c & 7) + '0'); + } + else + putchar (c); +} + +error (char *string) +{ + puts (string); + exit (1); +} + +#endif /* test */ +