⟦84de752ea⟧

TextFile

/* 
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
 */

#include <BitSet.h>
#include <std.h>
#include <values.h>
#include <Obstack.h>
#include <AllocQueue.h>


void BitSet::error(char* msg)
{
  (*lib_error_handler)("BitSet", msg);
}

//  globals & constants

BitSetRep  _nilBitSetRep = { 0, 1, 0, {0} }; // nil BitSets point here

#define ONES               ((unsigned short)(~0L))
#define MINBitSetRep_SIZE  16
#define MAXBitSetRep_SIZE  (1 << (SHORTBITS - 1) - 1)
#define MALLOC_OVERHEAD     4

// 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_OVERHEAD;
  unsigned int allocsiz = MINBitSetRep_SIZE;;
  while (allocsiz < siz) allocsiz <<= 1;
  allocsiz -= MALLOC_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, 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, BitSetRep* src)
{
  if (old == src) return old; 
  BitSetRep* rep;
  if (old == &_nilBitSetRep) old = 0;
  if (src == &_nilBitSetRep) src = 0;
  if (src == 0)
  {
    if (old == 0)
      rep = BSnew(0);
    else
      rep = old;
    rep->len = 0;
    rep->virt = 0;
  }
  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 == (BitSet& x, 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 <= (BitSet& x, 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 < (BitSet& x, 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;
}

BitSetTmp shorttoBitSet(unsigned short w)
{
  BitSetRep* r = BitSetalloc(0, &w, 1, 0, 2);
  trim(r);
  return r;
}

BitSetTmp longtoBitSet(unsigned long w)
{
  unsigned short u[2];
  u[0] = w & ((unsigned short)(~(0)));
  u[1] = w >> BITSETBITS;
  BitSetRep* r = BitSetalloc(0, &u[0], 2, 0, 3);
  trim(r);
  return r;
}


int BitSet::empty()
{
  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 = 1)
{
  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(BitSetRep* src, BitSetRep* r)
{
  r = BitSetcopy(r, src);
  r->virt = !src->virt;
  unsigned short* rs = r->s;
  unsigned short* topr = &(rs[r->len]);
  while (rs < topr)
  {
    unsigned short cmp = ~(*rs);
    *rs++ = cmp;
  }
  trim(r);
  return r;
}


BitSetRep* BitSetop(BitSetRep* x, BitSetRep* y, BitSetRep* r, char op)
{
  int xrsame = x == r;
  int yrsame = y == r;

  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;
  unsigned short* as;
  unsigned short* topa;
  unsigned short* bs;
  unsigned short* topb;
  
  if (xl <= yl)
  {
    as = (xrsame)? r->s : x->s;
    topa = &(as[xl]);
    av = x->virt;
    bs = (yrsame)? r->s : y->s;
    topb = &(bs[yl]);
    bv = y->virt;
  }
  else
  {
    as = (yrsame)? r->s : y->s;
    topa = &(as[yl]);
    av = y->virt;
    bs = (xrsame)? r->s : x->s;
    topb = &(bs[xl]);
    bv = x->virt;
    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)
{
  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 = 1)
{
  ++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 = 1)
{
  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 = 1)
{
  if (b == rep->virt)
    return -1;
  else
    return previous((rep->len) * BITSETBITS, b);
}

extern Obstack _libgxx_io_ob;
extern char* _libgxx_io_oblast;

extern AllocQueue _libgxx_fmtq;

const char* BitSettoa(BitSet& x, char f = '0', char t = '1', char star = '*')
{


  trim(x.rep);

  int wrksiz = (x.rep->len + 1) * BITSETBITS + 2;
  char* fmtbase = _libgxx_fmtq.alloc(wrksiz);
  char* fmt = fmtbase;

  unsigned short* s = x.rep->s;
  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;
}

BitSetTmp atoBitSet(const char* s, char f = '0', char t = '1', 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;
}

ostream& operator << (ostream& s, BitSet& x)
{
  return s << BitSettoa(x);
}

int BitSet::OK()
{
  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;
}
DataMuseum.dk

DKUUG/EUUG Conference tapes

⟦84de752ea⟧ TextFile

Derivation

TextFile
