bitstring.cc

早期freebsd实现

          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;

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

  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++;
  unsigned int xp = startx;

  const unsigned short* ys = &(y.rep->s[BitStr_index(starty)]);
  unsigned short b = *ys++;
  unsigned int yp = starty;