CrystalSpace

Public API Reference

csBitArrayTweakable< InlinedBits, Allocator > Class Template Reference

A one-dimensional array of bits, similar to STL bitset. More...

#include <csutil/bitarray.h>

List of all members.

Public Member Functions

bool AllBitsFalse () const
 Returns true if all bits are false.
bool AreSomeBitsSet (size_t pos, size_t count) const
 Checks whether at least one of count bits is set starting at pos.
void Clear ()
 Set all bits to false.
void ClearBit (size_t pos)
 Set the bit at position pos to false.
 csBitArrayTweakable (size_t size)
 Construct with a size of size bits.
 csBitArrayTweakable ()
 Default constructor.
 csBitArrayTweakable (const csBitArrayTweakable &that)
 Construct as duplicate of that (copy constructor).
void Delete (size_t pos, size_t count)
 Delete from the array count bits starting at pos, making the array shorter.
csBitArrayTweakableFlipAllBits ()
 Change value of all bits.
void FlipBit (size_t pos)
 Toggle the bit at position pos.
size_t GetFirstBitSet () const
 Find first bit in array which is set.
size_t GetFirstBitUnset () const
 Find first bit in array which is not set.
size_t GetLastBitSet () const
 Find last bit in array which is set.
size_t GetLastBitUnset () const
 Find last bit in array which is not set.
size_t GetSize () const
 Return the number of stored bits.
bool IsBitSet (size_t pos) const
 Returns true if the bit at position pos is true.
size_t Length () const
 Return the number of stored bits.
size_t NumBitsSet () const
 Count the number of bits that are set.
bool operator!= (const csBitArrayTweakable &that) const
 Not equal to other array?
csBitArrayTweakableoperator&= (const csBitArrayTweakable &that)
 Bit-wise `and'. The arrays must be the same length.
csBitArrayTweakableoperator= (const csBitArrayTweakable &that)
 Copy from other array.
bool operator== (const csBitArrayTweakable &that) const
 Equal to other array?
BitProxy operator[] (size_t pos)
 Return bit at position pos.
bool operator[] (size_t pos) const
 Return bit at position pos.
csBitArrayTweakable operator^= (const csBitArrayTweakable &that)
 Bit-wise `xor'. The arrays must be the same length.
csBitArrayTweakable operator|= (const csBitArrayTweakable &that)
 Bit-wise `or'. The arrays must be the same length.
csBitArrayTweakable operator~ () const
 Return complement bit array in which all bits are flipped from this one.
void Set (size_t pos, bool val=true)
 Set the bit at position pos to the given value.
void SetBit (size_t pos)
 Set the bit at position pos to true.
void SetLength (size_t newSize)
 Set the number of stored bits.
void SetSize (size_t newSize)
 Set the number of stored bits.
csBitArrayTweakable Slice (size_t pos, size_t count) const
 Return a new bit array containing a slice count bits in length from this array starting at pos.
 ~csBitArrayTweakable ()
 Destructor.

csBitArrayStorageTypeGetArrayBits ()
 Return the full backing-store.
const csBitArrayStorageTypeGetArrayBits () const
 Return the full backing-store.

Protected Member Functions

csBitArrayStorageTypeGetStore ()
 Get a non-constant pointer to bit store, which may be internal mSingleWord or heap-allocated mpStore.
csBitArrayStorageType const * GetStore () const
 Get a constant pointer to bit store, which may be internal mSingleWord or heap-allocated mpStore.
void Trim ()
 Force overhang bits at the end to 0.
bool UseInlineStore () const
 Return whether the inline or heap store is used.

Static Protected Member Functions

static size_t GetIndex (size_t bit_num)
 Get the GetStore()[] index for a given bit number.
static size_t GetOffset (size_t bit_num)
 Get the offset within GetStore()[GetIndex()] for a given bit number.

Protected Attributes

size_t mLength
 Length of heapStore/inlineStore in units of csBitArrayStorageType.

Friends

class csComparatorBitArray
class csHashComputerBitArray
csBitArrayTweakable operator& (const csBitArrayTweakable &a1, const csBitArrayTweakable &a2)
 Bit-wise `and'. The arrays must be the same length.
csBitArrayTweakable operator^ (const csBitArrayTweakable &a1, const csBitArrayTweakable &a2)
 Bit-wise `xor'. The arrays must be the same length.
csBitArrayTweakable operator| (const csBitArrayTweakable &a1, const csBitArrayTweakable &a2)
 Bit-wise `or'. The arrays must be the same length.

Detailed Description

template<int InlinedBits = csBitArrayDefaultInlineBits, typename Allocator = CS::Memory::AllocatorMalloc>
class csBitArrayTweakable< InlinedBits, Allocator >

A one-dimensional array of bits, similar to STL bitset.

The amount of bits is dynamic at runtime.

Internally, bits are stored in multiple values of the type csBitArrayStorageType. If the number of bits is below a certain threshold, the bits are stored in a field inside the class for more performance, above that threshold, the data is stored on the heap.

This threshold can be tweaked by changing the InlinedBits template parameter. At least InlinedBits bits will be stored inlined in the class (the actual amount is the next bigger multiple of the number of bits fitting into one csBitArrayStorageType). In scenarios where you can anticipate that the common number of stored bits is larger than the default number, you can tweak InlinedBits to gain more performance.

The Allocator template allocator allows you to override the logic to allocate bits from the heap.

Definition at line 132 of file bitarray.h.


Constructor & Destructor Documentation

template<int InlinedBits = csBitArrayDefaultInlineBits, typename Allocator = CS::Memory::AllocatorMalloc>
csBitArrayTweakable< InlinedBits, Allocator >::csBitArrayTweakable (  )  [inline]

Default constructor.

Definition at line 263 of file bitarray.h.

template<int InlinedBits = csBitArrayDefaultInlineBits, typename Allocator = CS::Memory::AllocatorMalloc>
csBitArrayTweakable< InlinedBits, Allocator >::csBitArrayTweakable ( size_t  size  )  [inline, explicit]

Construct with a size of size bits.

Definition at line 271 of file bitarray.h.

template<int InlinedBits = csBitArrayDefaultInlineBits, typename Allocator = CS::Memory::AllocatorMalloc>
csBitArrayTweakable< InlinedBits, Allocator >::csBitArrayTweakable ( const csBitArrayTweakable< InlinedBits, Allocator > &  that  )  [inline]

Construct as duplicate of that (copy constructor).

Definition at line 279 of file bitarray.h.

template<int InlinedBits = csBitArrayDefaultInlineBits, typename Allocator = CS::Memory::AllocatorMalloc>
csBitArrayTweakable< InlinedBits, Allocator >::~csBitArrayTweakable (  )  [inline]

Destructor.

Definition at line 285 of file bitarray.h.


Member Function Documentation

template<int InlinedBits = csBitArrayDefaultInlineBits, typename Allocator = CS::Memory::AllocatorMalloc>
bool csBitArrayTweakable< InlinedBits, Allocator >::AllBitsFalse (  )  const [inline]

Returns true if all bits are false.

Definition at line 546 of file bitarray.h.

template<int InlinedBits = csBitArrayDefaultInlineBits, typename Allocator = CS::Memory::AllocatorMalloc>
bool csBitArrayTweakable< InlinedBits, Allocator >::AreSomeBitsSet ( size_t  pos,
size_t  count 
) const [inline]

Checks whether at least one of count bits is set starting at pos.

Definition at line 525 of file bitarray.h.

template<int InlinedBits = csBitArrayDefaultInlineBits, typename Allocator = CS::Memory::AllocatorMalloc>
void csBitArrayTweakable< InlinedBits, Allocator >::Clear (  )  [inline]

Set all bits to false.

Definition at line 481 of file bitarray.h.

template<int InlinedBits = csBitArrayDefaultInlineBits, typename Allocator = CS::Memory::AllocatorMalloc>
void csBitArrayTweakable< InlinedBits, Allocator >::ClearBit ( size_t  pos  )  [inline]

Set the bit at position pos to false.

Definition at line 494 of file bitarray.h.

template<int InlinedBits = csBitArrayDefaultInlineBits, typename Allocator = CS::Memory::AllocatorMalloc>
void csBitArrayTweakable< InlinedBits, Allocator >::Delete ( size_t  pos,
size_t  count 
) [inline]

Delete from the array count bits starting at pos, making the array shorter.

Definition at line 728 of file bitarray.h.

template<int InlinedBits = csBitArrayDefaultInlineBits, typename Allocator = CS::Memory::AllocatorMalloc>
csBitArrayTweakable& csBitArrayTweakable< InlinedBits, Allocator >::FlipAllBits (  )  [inline]

Change value of all bits.

Definition at line 556 of file bitarray.h.

template<int InlinedBits = csBitArrayDefaultInlineBits, typename Allocator = CS::Memory::AllocatorMalloc>
void csBitArrayTweakable< InlinedBits, Allocator >::FlipBit ( size_t  pos  )  [inline]

Toggle the bit at position pos.

Definition at line 501 of file bitarray.h.

template<int InlinedBits = csBitArrayDefaultInlineBits, typename Allocator = CS::Memory::AllocatorMalloc>
csBitArrayStorageType* csBitArrayTweakable< InlinedBits, Allocator >::GetArrayBits (  )  [inline]

Return the full backing-store.

Definition at line 758 of file bitarray.h.

template<int InlinedBits = csBitArrayDefaultInlineBits, typename Allocator = CS::Memory::AllocatorMalloc>
const csBitArrayStorageType* csBitArrayTweakable< InlinedBits, Allocator >::GetArrayBits (  )  const [inline]

Return the full backing-store.

Definition at line 759 of file bitarray.h.

template<int InlinedBits = csBitArrayDefaultInlineBits, typename Allocator = CS::Memory::AllocatorMalloc>
size_t csBitArrayTweakable< InlinedBits, Allocator >::GetFirstBitSet (  )  const [inline]

Find first bit in array which is set.

Returns:
First bit set or csArrayItemNotFound if all bits are set.

Definition at line 593 of file bitarray.h.

template<int InlinedBits = csBitArrayDefaultInlineBits, typename Allocator = CS::Memory::AllocatorMalloc>
size_t csBitArrayTweakable< InlinedBits, Allocator >::GetFirstBitUnset (  )  const [inline]

Find first bit in array which is not set.

Returns:
First bit set or csArrayItemNotFound if all bits are not set.

Definition at line 626 of file bitarray.h.

template<int InlinedBits = csBitArrayDefaultInlineBits, typename Allocator = CS::Memory::AllocatorMalloc>
static size_t csBitArrayTweakable< InlinedBits, Allocator >::GetIndex ( size_t  bit_num  )  [inline, static, protected]

Get the GetStore()[] index for a given bit number.

Definition at line 171 of file bitarray.h.

template<int InlinedBits = csBitArrayDefaultInlineBits, typename Allocator = CS::Memory::AllocatorMalloc>
size_t csBitArrayTweakable< InlinedBits, Allocator >::GetLastBitSet (  )  const [inline]

Find last bit in array which is set.

Returns:
First bit set or csArrayItemNotFound if all bits are set.

Definition at line 659 of file bitarray.h.

template<int InlinedBits = csBitArrayDefaultInlineBits, typename Allocator = CS::Memory::AllocatorMalloc>
size_t csBitArrayTweakable< InlinedBits, Allocator >::GetLastBitUnset (  )  const [inline]

Find last bit in array which is not set.

Returns:
First bit set or csArrayItemNotFound if all bits are not set.

Definition at line 693 of file bitarray.h.

template<int InlinedBits = csBitArrayDefaultInlineBits, typename Allocator = CS::Memory::AllocatorMalloc>
static size_t csBitArrayTweakable< InlinedBits, Allocator >::GetOffset ( size_t  bit_num  )  [inline, static, protected]

Get the offset within GetStore()[GetIndex()] for a given bit number.

Definition at line 177 of file bitarray.h.

template<int InlinedBits = csBitArrayDefaultInlineBits, typename Allocator = CS::Memory::AllocatorMalloc>
size_t csBitArrayTweakable< InlinedBits, Allocator >::GetSize (  )  const [inline]

Return the number of stored bits.

Definition at line 292 of file bitarray.h.

template<int InlinedBits = csBitArrayDefaultInlineBits, typename Allocator = CS::Memory::AllocatorMalloc>
csBitArrayStorageType const* csBitArrayTweakable< InlinedBits, Allocator >::GetStore (  )  const [inline, protected]

Get a constant pointer to bit store, which may be internal mSingleWord or heap-allocated mpStore.

Definition at line 192 of file bitarray.h.

template<int InlinedBits = csBitArrayDefaultInlineBits, typename Allocator = CS::Memory::AllocatorMalloc>
csBitArrayStorageType* csBitArrayTweakable< InlinedBits, Allocator >::GetStore (  )  [inline, protected]

Get a non-constant pointer to bit store, which may be internal mSingleWord or heap-allocated mpStore.

Definition at line 201 of file bitarray.h.

template<int InlinedBits = csBitArrayDefaultInlineBits, typename Allocator = CS::Memory::AllocatorMalloc>
bool csBitArrayTweakable< InlinedBits, Allocator >::IsBitSet ( size_t  pos  )  const [inline]

Returns true if the bit at position pos is true.

Definition at line 517 of file bitarray.h.

template<int InlinedBits = csBitArrayDefaultInlineBits, typename Allocator = CS::Memory::AllocatorMalloc>
size_t csBitArrayTweakable< InlinedBits, Allocator >::Length (  )  const [inline]

Return the number of stored bits.

Deprecated:
Deprecated in 1.3. Use GetSize() instead.

Definition at line 302 of file bitarray.h.

template<int InlinedBits = csBitArrayDefaultInlineBits, typename Allocator = CS::Memory::AllocatorMalloc>
size_t csBitArrayTweakable< InlinedBits, Allocator >::NumBitsSet (  )  const [inline]

Count the number of bits that are set.

Definition at line 566 of file bitarray.h.

template<int InlinedBits = csBitArrayDefaultInlineBits, typename Allocator = CS::Memory::AllocatorMalloc>
bool csBitArrayTweakable< InlinedBits, Allocator >::operator!= ( const csBitArrayTweakable< InlinedBits, Allocator > &  that  )  const [inline]

Not equal to other array?

Definition at line 411 of file bitarray.h.

template<int InlinedBits = csBitArrayDefaultInlineBits, typename Allocator = CS::Memory::AllocatorMalloc>
csBitArrayTweakable& csBitArrayTweakable< InlinedBits, Allocator >::operator&= ( const csBitArrayTweakable< InlinedBits, Allocator > &  that  )  [inline]

Bit-wise `and'. The arrays must be the same length.

Definition at line 417 of file bitarray.h.

template<int InlinedBits = csBitArrayDefaultInlineBits, typename Allocator = CS::Memory::AllocatorMalloc>
csBitArrayTweakable& csBitArrayTweakable< InlinedBits, Allocator >::operator= ( const csBitArrayTweakable< InlinedBits, Allocator > &  that  )  [inline]

Copy from other array.

Definition at line 372 of file bitarray.h.

template<int InlinedBits = csBitArrayDefaultInlineBits, typename Allocator = CS::Memory::AllocatorMalloc>
bool csBitArrayTweakable< InlinedBits, Allocator >::operator== ( const csBitArrayTweakable< InlinedBits, Allocator > &  that  )  const [inline]

Equal to other array?

Definition at line 397 of file bitarray.h.

template<int InlinedBits = csBitArrayDefaultInlineBits, typename Allocator = CS::Memory::AllocatorMalloc>
BitProxy csBitArrayTweakable< InlinedBits, Allocator >::operator[] ( size_t  pos  )  [inline]

Return bit at position pos.

Definition at line 384 of file bitarray.h.

template<int InlinedBits = csBitArrayDefaultInlineBits, typename Allocator = CS::Memory::AllocatorMalloc>
bool csBitArrayTweakable< InlinedBits, Allocator >::operator[] ( size_t  pos  )  const [inline]

Return bit at position pos.

Definition at line 391 of file bitarray.h.

template<int InlinedBits = csBitArrayDefaultInlineBits, typename Allocator = CS::Memory::AllocatorMalloc>
csBitArrayTweakable csBitArrayTweakable< InlinedBits, Allocator >::operator^= ( const csBitArrayTweakable< InlinedBits, Allocator > &  that  )  [inline]

Bit-wise `xor'. The arrays must be the same length.

Definition at line 439 of file bitarray.h.

template<int InlinedBits = csBitArrayDefaultInlineBits, typename Allocator = CS::Memory::AllocatorMalloc>
csBitArrayTweakable csBitArrayTweakable< InlinedBits, Allocator >::operator|= ( const csBitArrayTweakable< InlinedBits, Allocator > &  that  )  [inline]

Bit-wise `or'. The arrays must be the same length.

Definition at line 428 of file bitarray.h.

template<int InlinedBits = csBitArrayDefaultInlineBits, typename Allocator = CS::Memory::AllocatorMalloc>
csBitArrayTweakable csBitArrayTweakable< InlinedBits, Allocator >::operator~ (  )  const [inline]

Return complement bit array in which all bits are flipped from this one.

Definition at line 450 of file bitarray.h.

template<int InlinedBits = csBitArrayDefaultInlineBits, typename Allocator = CS::Memory::AllocatorMalloc>
void csBitArrayTweakable< InlinedBits, Allocator >::Set ( size_t  pos,
bool  val = true 
) [inline]

Set the bit at position pos to the given value.

Definition at line 508 of file bitarray.h.

template<int InlinedBits = csBitArrayDefaultInlineBits, typename Allocator = CS::Memory::AllocatorMalloc>
void csBitArrayTweakable< InlinedBits, Allocator >::SetBit ( size_t  pos  )  [inline]

Set the bit at position pos to true.

Definition at line 487 of file bitarray.h.

template<int InlinedBits = csBitArrayDefaultInlineBits, typename Allocator = CS::Memory::AllocatorMalloc>
void csBitArrayTweakable< InlinedBits, Allocator >::SetLength ( size_t  newSize  )  [inline]

Set the number of stored bits.

Deprecated:
Deprecated in 1.3. Use SetSize() instead.

Definition at line 312 of file bitarray.h.

template<int InlinedBits = csBitArrayDefaultInlineBits, typename Allocator = CS::Memory::AllocatorMalloc>
void csBitArrayTweakable< InlinedBits, Allocator >::SetSize ( size_t  newSize  )  [inline]

Set the number of stored bits.

Remarks:
If the new size is larger than the old size, the newly added bits are cleared.

Definition at line 322 of file bitarray.h.

template<int InlinedBits = csBitArrayDefaultInlineBits, typename Allocator = CS::Memory::AllocatorMalloc>
csBitArrayTweakable csBitArrayTweakable< InlinedBits, Allocator >::Slice ( size_t  pos,
size_t  count 
) const [inline]

Return a new bit array containing a slice count bits in length from this array starting at pos.

Does not modify this array.

Definition at line 746 of file bitarray.h.

template<int InlinedBits = csBitArrayDefaultInlineBits, typename Allocator = CS::Memory::AllocatorMalloc>
void csBitArrayTweakable< InlinedBits, Allocator >::Trim (  )  [inline, protected]

Force overhang bits at the end to 0.

Definition at line 207 of file bitarray.h.

template<int InlinedBits = csBitArrayDefaultInlineBits, typename Allocator = CS::Memory::AllocatorMalloc>
bool csBitArrayTweakable< InlinedBits, Allocator >::UseInlineStore (  )  const [inline, protected]

Return whether the inline or heap store is used.

Definition at line 183 of file bitarray.h.


Friends And Related Function Documentation

template<int InlinedBits = csBitArrayDefaultInlineBits, typename Allocator = CS::Memory::AllocatorMalloc>
csBitArrayTweakable operator& ( const csBitArrayTweakable< InlinedBits, Allocator > &  a1,
const csBitArrayTweakable< InlinedBits, Allocator > &  a2 
) [friend]

Bit-wise `and'. The arrays must be the same length.

Definition at line 456 of file bitarray.h.

template<int InlinedBits = csBitArrayDefaultInlineBits, typename Allocator = CS::Memory::AllocatorMalloc>
csBitArrayTweakable operator^ ( const csBitArrayTweakable< InlinedBits, Allocator > &  a1,
const csBitArrayTweakable< InlinedBits, Allocator > &  a2 
) [friend]

Bit-wise `xor'. The arrays must be the same length.

Definition at line 470 of file bitarray.h.

template<int InlinedBits = csBitArrayDefaultInlineBits, typename Allocator = CS::Memory::AllocatorMalloc>
csBitArrayTweakable operator| ( const csBitArrayTweakable< InlinedBits, Allocator > &  a1,
const csBitArrayTweakable< InlinedBits, Allocator > &  a2 
) [friend]

Bit-wise `or'. The arrays must be the same length.

Definition at line 463 of file bitarray.h.


Member Data Documentation

template<int InlinedBits = csBitArrayDefaultInlineBits, typename Allocator = CS::Memory::AllocatorMalloc>
size_t csBitArrayTweakable< InlinedBits, Allocator >::mLength [protected]

Length of heapStore/inlineStore in units of csBitArrayStorageType.

Definition at line 167 of file bitarray.h.


The documentation for this class was generated from the following file:

Generated for Crystal Space 1.4.1 by doxygen 1.7.1