bitstring.cc

早期freebsd实现

  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;

  unsigned int startx, starty;
  if (startpos < 0)
  {
    startx = xl + startpos;
    starty = yl + startpos;
  }
  else
    startx = starty = startpos;

  if (startx >= xl || 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;

void BitString::printon(ostream& os, char f, char t) const
{
  unsigned int  xl = rep->len;
  const unsigned short* ptr = rep->s;
  register streambuf *sb = os.rdbuf();
  unsigned short a = 0;

  for (unsigned int  i = 0; i < xl; ++i)
  {
    if (i % BITSTRBITS == 0)
      a = *ptr++;
    sb->sputc((a & 1)? t : f);
    a >>= 1;
  }
}
const char* BitStringtoa(const BitString& x, char f, char t)
{
  int wrksiz = x.length() + 2;
  char* fmtbase = (char *) _libgxx_fmtq.alloc(wrksiz);
  ostrstream stream(fmtbase, wrksiz);
  
  x.printon(stream, f, t);
  stream << ends;
  return fmtbase;
}

ostream& operator << (ostream& s, const BitString& x)
{
  if (s.opfx())
    x.printon(s);
  return s;
}

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);
  ostrstream stream(fmtbase, wrksiz);
  
  p.printon(stream, f, t, x);
  stream << ends;
  return fmtbase;
}

void BitPattern::printon(ostream& s, char f,char t,char x) const
{
  unsigned int  pl = pattern.rep->len;
  unsigned int  ml = mask.rep->len;
  unsigned int  l = (pl <= ml)? pl : ml;
  register streambuf *sb = s.rdbuf();

  const unsigned short* ps = pattern.rep->s;
  const unsigned short* ms = 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)
      sb->sputc((a & 1)? t : f);
    else
      sb->sputc(x);
    a >>= 1;
    m >>= 1;
  }
}

ostream& operator << (ostream& s, const BitPattern& x)
{
  if (s.opfx())
    x.printon(s);
  return s;
}


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