Public API Reference

csutil/bitarray.h

Go to the documentation of this file.

/*
    Copyright (C) 2000 by Andrew Kirmse

    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 "allocator.h"
#include "comparator.h"
#include "hash.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 = MIN (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;

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

  enum
  {
    cellSize    = csBitArrayDefaultInlineBits,
    cellCount   = (InlinedBits + (cellSize-1)) / cellSize
  };

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

  static size_t GetIndex (size_t bit_num)
  {
    return bit_num / cellSize;
  }

  static size_t GetOffset (size_t bit_num)
  {
    return bit_num % cellSize;
  }

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

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)
  {
    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, 
              (MIN (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;
    Trim();
  }

  //
  // Operators
  //

  csBitArrayTweakable& operator=(const csBitArrayTweakable& that)
  {
    if (this != &that)
    {
      SetSize (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 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 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 = MIN(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;
  }

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

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


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


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


#endif // __CS_BITARRAY_H__

---