bitset.cc

早期freebsd实现

    *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);
  ostrstream stream(fmtbase, wrksiz);
  
  x.printon(stream, f, t, star);
  stream << ends;
  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)
{
  if (s.opfx())
    x.printon(s);
  return s;
}

void BitSet::printon(ostream& s, char f, char t, char star) const
// FIXME:  Does not respect s.width()!
{
  trim(rep);
  register streambuf* sb = s.rdbuf();
  const unsigned short* s = rep->s;
  const unsigned short* top = &(s[rep->len - 1]);

  while (s < top)
  {
    unsigned short a = *s++;
    for (int j = 0; j < BITSETBITS; ++j)
    {
      sb->sputc((a & 1)? t : f);
      a >>= 1;
    }
  }

  if (!rep->virt)
  {
    unsigned short a = *s;
    if (rep->len != 0)
    {
      for (int j = 0; j < BITSETBITS && a != 0; ++j)
      {
        sb->sputc((a & 1)? t : f);
        a >>= 1;
      }
    }
    sb->sputc(f);
  }
  else
  {
    unsigned short a = *s;
    unsigned short mask = ONES;
    unsigned short himask = (1 << (BITSETBITS - 1)) - 1;
    if (rep->len != 0)
    {
      for (int j = 0; j < BITSETBITS && a != mask; ++j)
      {
        sb->sputc((a & 1)? t : f);
        a = (a >> 1) & himask;
        mask = (mask >> 1) & himask;
      }
    }
    sb->sputc(t);
  }

  sb->sputc(star);
}

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;
}