Public API Reference

csutil/bitarray.h

Go to the documentation of this file.

/*
    Copyright (C) 2000 by Andrew Kirmse
                  2008 by Marten Svanfeldt

    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, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/

// A one-dimensional array of bits, similar to STL bitset.
//
// Copyright 2000 Andrew Kirmse.  All rights reserved.
//
// Permission is granted to use this code for any purpose, as long as this
// copyright message remains intact.

#ifndef __CS_BITARRAY_H__
#define __CS_BITARRAY_H__

#include "csextern.h"
#include "csutil/allocator.h"
#include "csutil/bitops.h"
#include "csutil/comparator.h"
#include "csutil/hash.h"

#include "csutil/metautils.h"
#include "csutil/compileassert.h"

#if defined(CS_COMPILER_MSVC) && (CS_PROCESSOR_SIZE == 64)
/* long is 32 bit even on 64-bit MSVC, so use uint64 to utilize a storage in
 * 64 bit units.
 */
typedef uint64 csBitArrayStorageType;
#else
typedef unsigned long csBitArrayStorageType;
#endif
const size_t csBitArrayDefaultInlineBits = 
  sizeof (csBitArrayStorageType) * 8;
  
  
template<typename BitArray>
class csComparatorBitArray
{
public:
  static int Compare (BitArray const& key1, BitArray const& key2)
  {
    csBitArrayStorageType const* p0 = key1.GetStore();
    csBitArrayStorageType const* p1 = key2.GetStore();
    size_t compareNum = csMin (key1.mLength, key2.mLength);
    size_t i = 0;
    for (; i < compareNum; i++)
      if (p0[i] != p1[i])
        return (int)p0[i] - (int)p1[i];
    if (key1.mLength > key2.mLength)
    {
      for (; i < key1.mLength; i++)
        if (p0[i] != 0)
          return (int)p0[i];
    }
    else
    {
      for (; i < key2.mLength; i++)
        if (p1[i] != 0)
          return -((int)p1[i]);
    }
    return 0;
  }
};

  
template<typename BitArray>
class csHashComputerBitArray
{
public:
  static uint ComputeHash (BitArray const& key)
  {
    const size_t uintCount = sizeof (csBitArrayStorageType) / sizeof (uint);
    uint ui[uintCount];
    uint hash = 0;
    csBitArrayStorageType const* p = key.GetStore();
    // \todo Not very good. Find a better hash function; however, it should
    // return the same hash for two bit arrays that are the same except for
    // the amount of trailing zeros. (e.g. f(10010110) == f(100101100000...))
    for (size_t i = 0; i < key.mLength; i++)
    {
      memcpy (ui, &p[i], sizeof (ui));
      for (size_t j = 0; j < uintCount; j++)
        hash += ui[j];
    }
    return hash;
  }
};

template<int InlinedBits = csBitArrayDefaultInlineBits,
  typename Allocator = CS::Memory::AllocatorMalloc>
class csBitArrayTweakable
{
public:
  typedef csBitArrayTweakable<InlinedBits, Allocator> ThisType;
  typedef Allocator AllocatorType;

protected:
  template<typename BitArray> friend class csComparatorBitArray;
  template<typename BitArray> friend class csHashComputerBitArray;

  enum
  {
    cellSize    = csBitArrayDefaultInlineBits,            // This _have_ to be PO2
    cellCount   = (InlinedBits + (cellSize-1)) / cellSize,
    
    cellMask    = (cellSize - 1),
    cellShift   = CS::Meta::Log2<cellSize>::value
  };
  CS_COMPILE_ASSERT(CS::Meta::IsLog2<cellSize>::value);

  struct Storage : public Allocator
  {
    union
    {
      csBitArrayStorageType* heapStore;
      csBitArrayStorageType inlineStore[cellCount];
    };
    Storage()
    {
      memset (&inlineStore, 0, 
        csMax (sizeof (heapStore), sizeof (inlineStore)));
    }
  };
  Storage storage;
  size_t mLength;          
  size_t mNumBits;

  static size_t GetIndex (size_t bit_num)
  {
    return bit_num >> cellShift;
  }

  static size_t GetOffset (size_t bit_num)
  {
    return bit_num & cellMask;
  }

  bool UseInlineStore () const
  {
    return mLength <= cellCount;
  }

  csBitArrayStorageType const* GetStore() const
  {
    return UseInlineStore () ? storage.inlineStore : storage.heapStore;
  }

  csBitArrayStorageType* GetStore()
  {
    return UseInlineStore () ? storage.inlineStore : storage.heapStore;
  }

  void Trim()
  {
    size_t extra_bits = mNumBits % cellSize;
    if (mLength > 0 && extra_bits != 0)
      GetStore()[mLength - 1] &= ~((~(csBitArrayStorageType)0) << extra_bits);
  }

  void SetSizeInternal (size_t newSize)
  {
    size_t newLength;
    if (newSize == 0)
      newLength = 0;
    else
      newLength = 1 + GetIndex (newSize - 1);

    if (newLength != mLength)
    {
      // Avoid allocation if length is 1 (common case)
      csBitArrayStorageType* newStore;
      if (newLength <= cellCount)
        newStore = storage.inlineStore;
      else
        newStore = (csBitArrayStorageType*)storage.Alloc (
          newLength * sizeof (csBitArrayStorageType));

      if (newLength > 0)
      {
        if (mLength > 0)
        {
          csBitArrayStorageType* oldStore = GetStore();
          if (newStore != oldStore)
          {
            memcpy (newStore, oldStore, 
              (csMin (mLength, newLength)) * sizeof (csBitArrayStorageType));
            if (newLength > mLength)
              memset(newStore + mLength, 0,
                     (newLength - mLength) * sizeof (csBitArrayStorageType));
            if (!UseInlineStore ())
              storage.Free (oldStore);
          }
        }
        else
          memset (newStore, 0, newLength * sizeof (csBitArrayStorageType));
      }
      mLength = newLength;
      if (!UseInlineStore()) storage.heapStore = newStore;
    }

    mNumBits = newSize;
  }

public:
  class BitProxy
  {
  private:
    csBitArrayTweakable& mArray;
    size_t mPos;
  public:
    BitProxy (csBitArrayTweakable& array, size_t pos): mArray(array), mPos(pos)
    {}

    BitProxy &operator= (bool value)
    {
      mArray.Set (mPos, value);
      return *this;
    }

    BitProxy &operator= (const BitProxy &that)
    {
      mArray.Set (mPos, that.mArray.IsBitSet (that.mPos));
      return *this;
    }

    operator bool() const
    {
      return mArray.IsBitSet (mPos);
    }

    bool Flip()
    {
      mArray.FlipBit (mPos);
      return mArray.IsBitSet (mPos);
    }
  };
  friend class BitProxy;

  csBitArrayTweakable () : mLength(0), mNumBits(0)
  {
    SetSize (0);
  }

  explicit csBitArrayTweakable (size_t size) : mLength(0), mNumBits(0)
  {
    SetSize (size);
  }

  csBitArrayTweakable (const csBitArrayTweakable& that) : mLength(0), mNumBits(0)
  {
    *this = that; // Invokes this->operator=().
  }

  ~csBitArrayTweakable()
  {
    if (!UseInlineStore ())
      storage.Free (storage.heapStore);
  }

  size_t GetSize() const
  {
    return mNumBits;
  }

  CS_DEPRECATED_METHOD_MSG("Use GetSize() instead.")
  size_t Length () const
  {
    return GetSize();
  }

  CS_DEPRECATED_METHOD_MSG("Use SetSize() instead.")
  void SetLength (size_t newSize)
  {
    SetSize (newSize);
  }

  void SetSize (size_t newSize)
  {
    SetSizeInternal (newSize);
    Trim();
  }

  //
  // Operators
  //

  csBitArrayTweakable& operator=(const csBitArrayTweakable& that)
  {
    if (this != &that)
    {
      SetSizeInternal (that.mNumBits);
      memcpy (GetStore(), that.GetStore(), 
        mLength * sizeof (csBitArrayStorageType));
    }
    return *this;
  }

  BitProxy operator[] (size_t pos)
  {
    CS_ASSERT (pos < mNumBits);
    return BitProxy(*this, pos);
  }

  bool operator[] (size_t pos) const
  {
    return IsBitSet(pos);
  }

  bool operator==(const csBitArrayTweakable& that) const
  {
    if (mNumBits != that.mNumBits)
      return false;

    csBitArrayStorageType const* p0 = GetStore();
    csBitArrayStorageType const* p1 = that.GetStore();
    for (unsigned i = 0; i < mLength; i++)
      if (p0[i] != p1[i])
        return false;
    return true;
  }

  bool operator != (const csBitArrayTweakable& that) const
  {
    return !(*this == that);
  }

  csBitArrayTweakable& operator &= (const csBitArrayTweakable &that)
  {
    CS_ASSERT (mNumBits == that.mNumBits);
    csBitArrayStorageType* p0 = GetStore();
    csBitArrayStorageType const* p1 = that.GetStore();
    for (size_t i = 0; i < mLength; i++)
      p0[i] &= p1[i];
    return *this;
  }

  csBitArrayTweakable operator |= (const csBitArrayTweakable& that)
  {
    CS_ASSERT (mNumBits == that.mNumBits);
    csBitArrayStorageType* p0 = GetStore();
    csBitArrayStorageType const* p1 = that.GetStore();
    for (size_t i = 0; i < mLength; i++)
      p0[i] |= p1[i];
    return *this;
  }

  csBitArrayTweakable operator ^= (const csBitArrayTweakable& that)
  {
    CS_ASSERT (mNumBits == that.mNumBits);
    csBitArrayStorageType* p0 = GetStore();
    csBitArrayStorageType const* p1 = that.GetStore();
    for (size_t i = 0; i < mLength; i++)
      p0[i] ^= p1[i];
    return *this;
  }

  csBitArrayTweakable operator~() const
  {
    return csBitArrayTweakable(*this).FlipAllBits();
  }

  friend csBitArrayTweakable operator& (const csBitArrayTweakable& a1, 
    const csBitArrayTweakable& a2)
  {
    return csBitArrayTweakable (a1) &= a2;
  }

  friend csBitArrayTweakable operator | (const csBitArrayTweakable& a1, 
    const csBitArrayTweakable& a2)
  {
    return csBitArrayTweakable (a1) |= a2;
  }

  friend csBitArrayTweakable operator ^ (const csBitArrayTweakable& a1, 
    const csBitArrayTweakable& a2)
  {
    return csBitArrayTweakable (a1) ^= a2;
  }

  //
  // Plain English interface
  //

  void Clear()
  {
    memset (GetStore(), 0, mLength * sizeof(csBitArrayStorageType));
  }

  void SetAll()
  {
    csBitArrayStorageType* store = GetStore();
    for (size_t i = 0; i < mNumBits; i++)
      store[GetIndex(i)] = ((csBitArrayStorageType)1) << GetOffset(i);
  }

  void SetBit (size_t pos)
  {
    CS_ASSERT (pos < mNumBits);
    GetStore()[GetIndex(pos)] |= ((csBitArrayStorageType)1) << GetOffset(pos);
  }

  void ClearBit (size_t pos)
  {
    CS_ASSERT (pos < mNumBits);
    GetStore()[GetIndex(pos)] &= ~(((csBitArrayStorageType)1) << GetOffset(pos));
  }

  void FlipBit (size_t pos)
  {
    CS_ASSERT (pos < mNumBits);
    GetStore()[GetIndex(pos)] ^= ((csBitArrayStorageType)1) << GetOffset(pos);
  }

  void Set (size_t pos, bool val = true)
  {
    if (val)
      SetBit(pos);
    else
      ClearBit(pos);
  }

  bool IsBitSet (size_t pos) const
  {
    CS_ASSERT (pos < mNumBits);
    return (GetStore()[GetIndex(pos)] 
      & (((csBitArrayStorageType)1) << GetOffset(pos))) != 0;
  }

  bool IsBitSetTolerant (size_t pos) const
  {
    if (pos >= mNumBits) return false;
    return (GetStore()[GetIndex(pos)] 
      & (((csBitArrayStorageType)1) << GetOffset(pos))) != 0;
  }
  
  bool AreSomeBitsSet (size_t pos, size_t count) const
  {
    CS_ASSERT (pos + count <= mNumBits);
    csBitArrayStorageType const* p = GetStore();
    while (count > 0)
    {
      size_t index = GetIndex (pos);
      size_t offset = GetOffset (pos);
      size_t checkCount = csMin (count, cellSize - offset);
      csBitArrayStorageType mask = ((checkCount == cellSize) 
        ? ~(csBitArrayStorageType)0 
        : ((((csBitArrayStorageType)1) << checkCount) - 1)) << offset;
      if (p[index] & mask)
        return true;
      pos += checkCount;
      count -= checkCount;
    }
    return false;
  }
  
  bool AllBitsFalse() const
  {
    csBitArrayStorageType const* p = GetStore();
    for (size_t i = 0; i < mLength; i++)
      if (p[i] != 0)
        return false;
    return true;
  }

  csBitArrayTweakable& FlipAllBits()
  {
    csBitArrayStorageType* p = GetStore();
    for (size_t i = 0; i < mLength; i++)
      p[i] = ~p[i];
    Trim();
    return *this;
  }
  
  size_t NumBitsSet() const
  {
    const size_t ui32perStorage = 
      sizeof (csBitArrayStorageType) / sizeof (uint32);

    union
    {
      csBitArrayStorageType s;
      uint32 ui32[ui32perStorage];
    } v;

    const csBitArrayStorageType* p = GetStore();
    size_t num = 0;
    for (size_t i = 0; i < mLength; i++)
    {
      v.s = p[i];
      for (size_t j = 0; j < ui32perStorage; j++)
        num += CS::Utility::BitOps::ComputeBitsSet (v.ui32[j]);
    }

    return num;
  }
  
  size_t GetFirstBitSet() const
  {
    const size_t ui32perStorage = 
      sizeof (csBitArrayStorageType) / sizeof (uint32);

    union
    {
      csBitArrayStorageType s;
      uint32 ui32[ui32perStorage];
    } v;

    const csBitArrayStorageType* p = GetStore();
    size_t ofs = 0, result;
    for (size_t i = 0; i < mLength; i++)
    {
      v.s = p[i];
      for (size_t j = 0; j < ui32perStorage; j++)
      {
        if (CS::Utility::BitOps::ScanBitForward (v.ui32[j], result))
        {
          size_t r = ofs + result;
          if (r >= mNumBits) return csArrayItemNotFound;
          return r;
        }
        ofs += 32;
      }
    }
    return csArrayItemNotFound;
  }
  size_t GetFirstBitUnset() const
  {
    const size_t ui32perStorage = 
      sizeof (csBitArrayStorageType) / sizeof (uint32);

    union
    {
      csBitArrayStorageType s;
      uint32 ui32[ui32perStorage];
    } v;

    const csBitArrayStorageType* p = GetStore();
    size_t ofs = 0;
    unsigned long result;
    for (size_t i = 0; i < mLength; i++)
    {
      v.s = p[i];
      for (size_t j = 0; j < ui32perStorage; j++)
      {
        if (CS::Utility::BitOps::ScanBitForward (~v.ui32[j], result))
        {
          size_t r = ofs + result;
          if (r >= mNumBits) return csArrayItemNotFound;
          return r;
        }
        ofs += 32;
      }
    }
    return csArrayItemNotFound;
  }
  size_t GetLastBitSet() const
  {
    const size_t ui32perStorage = 
      sizeof (csBitArrayStorageType) / sizeof (uint32);

    union
    {
      csBitArrayStorageType s;
      uint32 ui32[ui32perStorage];
    } v;

    const csBitArrayStorageType* p = GetStore();
    size_t ofs, result;
    ofs = 32 * (mLength*ui32perStorage-1);
    for (size_t i = mLength; i-- > 0;)
    {
      v.s = p[i];
      for (size_t j = ui32perStorage; j-- > 0; )
      {
        if (CS::Utility::BitOps::ScanBitForward (v.ui32[j], result))
        {
          size_t r = ofs + result;
          if (r >= mNumBits) return csArrayItemNotFound;
          return r;
        }
        ofs -= 32;
      }
    }
    return csArrayItemNotFound;
  }
  size_t GetLastBitUnset() const
  {
    const size_t ui32perStorage = 
      sizeof (csBitArrayStorageType) / sizeof (uint32);

    union
    {
      csBitArrayStorageType s;
      uint32 ui32[ui32perStorage];
    } v;

    const csBitArrayStorageType* p = GetStore();
    size_t ofs, result;
    ofs = 32 * (mLength*ui32perStorage-1);
    for (size_t i = mLength; i-- > 0;)
    {
      v.s = p[i];
      for (size_t j = ui32perStorage; j-- > 0; )
      {
        if (CS::Utility::BitOps::ScanBitForward (~v.ui32[j], result))
        {
          size_t r = ofs + result;
          if (r >= mNumBits) return csArrayItemNotFound;
          return r;
        }
        ofs -= 32;
      }
    }
    return csArrayItemNotFound;
  }

  void Delete(size_t pos, size_t count)
  {
    if (count > 0)
    {
      size_t dst = pos;
      size_t src = pos + count;
      CS_ASSERT(src <= mNumBits);
      size_t ntail = mNumBits - src;
      while (ntail-- > 0)
        Set(dst++, IsBitSet(src++));
      SetSize(mNumBits - count);
    }
  }

  csBitArrayTweakable Slice(size_t pos, size_t count) const
  {
    CS_ASSERT(pos + count <= mNumBits);
    csBitArrayTweakable a (count);
    for (size_t i = pos, o = 0; i < pos + count; i++)
      if (IsBitSet(i))
        a.SetBit(o++);
    return a;
  }


  csBitArrayStorageType* GetArrayBits() { return GetStore(); }
  const csBitArrayStorageType* GetArrayBits() const { return GetStore(); }


  class SetBitIterator
  {
  public:
    SetBitIterator (const SetBitIterator& other)
      : bitArray (other.bitArray), pos (other.pos), offset (other.offset),
      cachedStore (other.cachedStore)
    {}

    size_t Next ()
    {
      while (offset < 8*sizeof(csBitArrayStorageType))
      {        
        if ((cachedStore & 0x1) != 0)
        {
          const size_t result = (pos-1)*sizeof(csBitArrayStorageType)*8 + offset;

          ++offset;
          cachedStore >>= 1;
          if (!cachedStore)
            GetNextCacheItem ();

          return result;
        }        
        else
        {
          ++offset;
          cachedStore >>= 1;
          if (!cachedStore)
            GetNextCacheItem ();
        }
      }
      CS_ASSERT_MSG ("Invalid iteration", false);
      return 0;
    }

    bool HasNext () const
    {
      return cachedStore != 0;
    }

    void Reset ()
    {
      pos = 0;
      GetNextCacheItem ();
    }

  protected:
    SetBitIterator (const ThisType& bitArray)
      : bitArray (bitArray), pos (0), offset (0), cachedStore (0)
    {
      Reset ();
    }

    friend class csBitArrayTweakable<InlinedBits, Allocator>;

    void GetNextCacheItem ()
    {
      offset = 0;
      while (pos < bitArray.mLength)
      {
        cachedStore = bitArray.GetStore ()[pos++];
        if (cachedStore)
          return;
      }
      cachedStore = 0;
    }

    const ThisType& bitArray;
    size_t pos, offset;
    csBitArrayStorageType cachedStore;    
  };
  friend class SetBitIterator;

  SetBitIterator GetSetBitIterator () const
  {
    return SetBitIterator (*this);
  }
  
  uint8* Serialize (size_t& numBytes) const
  {
    if (mNumBits == 0)
    {
      numBytes = 0;
      return 0;
    }
  
    struct SerializeHelper
    {
      uint8* buf;
      size_t bufSize, bufUsed;
      
      SerializeHelper () : buf (0), bufSize (0), bufUsed (0) {}
      void PushByte (uint8 b)
      {
        if (bufUsed >= bufSize)
        {
          bufSize += 4;
          buf = (uint8*)cs_realloc (buf, bufSize);
        }
        buf[bufUsed++] = b;
      }
      void TruncZeroes ()
      {
        while ((bufUsed > 0) && (buf[bufUsed-1] == 0))
          bufUsed--;
      }
    } serHelper;
    
    // Write out bits number
    {
      size_t remainder = mNumBits;
      
      while (remainder >= 128)
      {
        uint8 b = (remainder & 0x7f) | 0x80;
        serHelper.PushByte (b);
        remainder >>= 7;
      }
      serHelper.PushByte (uint8 (remainder));
    }
  
    const size_t ui8Count = sizeof (csBitArrayStorageType) / sizeof (uint8);
    uint8 ui8[ui8Count];
    csBitArrayStorageType const* p = GetStore();
    for (size_t i = 0; i < mLength; i++)
    {
      memcpy (ui8, &p[i], sizeof (ui8));
#ifdef CS_LITTLE_ENDIAN
      for (size_t j = 0; j < ui8Count; j++)
#else
      for (size_t j = ui8Count; j-- > 0; )
#endif
      {
        serHelper.PushByte (ui8[j]);
      }
    }
    
    serHelper.TruncZeroes();
    numBytes = serHelper.bufUsed;
    return serHelper.buf;
  }
  static ThisType Unserialize (uint8* bytes, size_t numBytes)
  {
    if ((bytes == 0) || (numBytes == 0))
      return ThisType(); // empty bit array
  
    size_t bufPos = 0;
  
    // Read the bits number
    size_t numBits = 0;
    int shift = 0;
    while (bufPos < numBytes)
    {
      uint8 b = bytes[bufPos++];
      numBits |= (b & 0x7f) << shift;
      if ((b & 0x80) == 0) break;
      shift += 7;
    }
    
    ThisType newArray (numBits);
    
    // Read the actual bits
    csBitArrayStorageType* p = newArray.GetStore();
    size_t storeIndex = 0;
    while (bufPos < numBytes)
    {
      const size_t ui8Count = sizeof (csBitArrayStorageType) / sizeof (uint8);
      uint8 ui8[ui8Count];
      memset (ui8, 0, sizeof (ui8));
#ifdef CS_LITTLE_ENDIAN
      for (size_t j = 0; j < ui8Count; j++)
#else
      for (size_t j = ui8Count; j-- > 0; )
#endif
      {
        ui8[j] = bytes[bufPos++];
        if (bufPos >= numBytes) break;
      }
      memcpy (p + (storeIndex++), ui8, sizeof (ui8));
    }
    
    return newArray;
  }
};

class csBitArray : public csBitArrayTweakable<>
{
public:
  csBitArray () { }
  explicit csBitArray (size_t size) : csBitArrayTweakable<> (size) { }
  csBitArray (const csBitArray& that) : csBitArrayTweakable<> (that) { }

  template<int A, typename B>
  csBitArray& operator=(const csBitArrayTweakable<A, B>& that)
  {
    if (this != &that)
    {
      SetSize (that.GetSize());
      memcpy (GetStore(), that.GetArrayBits(), 
        mLength * sizeof (csBitArrayStorageType));
    }
    return *this;
  }

};


template<>
class csComparator<csBitArray, csBitArray> : 
  public csComparatorBitArray<csBitArray> { };


template<>
class csHashComputer<csBitArray> : 
  public csHashComputerBitArray<csBitArray> { };


#endif // __CS_BITARRAY_H__

---