bitstring.cc

早期freebsd实现

/* 
Copyright (C) 1988 Free Software Foundation
    written by Doug Lea ([e-mail])

This file is part of the GNU C++ Library.  This library is free
software; you can redistribute it and/or modify it under the terms of
the GNU Library General Public License as published by the Free
Software Foundation; either version 2 of the License, or (at your
option) any later version.  This library is distributed in the hope
that it will be useful, but WITHOUT ANY WARRANTY; without even the
implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
PURPOSE.  See the GNU Library General Public License for more details.
You should have received a copy of the GNU Library General Public
License along with this library; if not, write to the Free Software
Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
*/

/* 
  BitString class implementation
 */
 
#ifdef __GNUG__
#pragma implementation
#endif
#include <BitString.h>
#include <std.h>
#include <limits.h>
#include <Obstack.h>
#include <AllocRing.h>
#include <new.h>
#include <builtin.h>
#include <strstream.h>

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 << (sizeof(short)*CHAR_BIT - 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) memmove((void*)ds, (const void*)ss, 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) memset((void*)ds, 0, 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];
  memset(rep, 0, 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);
    memcpy(rep->s, old->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;
    
    memcpy(rep->s, src->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 && 
    memcmp((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;