blob: 1673ac58b9b40387b24184ee24f6d3bb2b5dcf7f [file] [log] [blame]
/*
* Copyright (C) 2011 Apple Inc. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
* EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
* OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
#ifndef BitVector_h
#define BitVector_h
#include <stdio.h>
#include <wtf/Assertions.h>
#include <wtf/PrintStream.h>
#include <wtf/StdLibExtras.h>
namespace WTF {
// This is a space-efficient, resizeable bitvector class. In the common case it
// occupies one word, but if necessary, it will inflate this one word to point
// to a single chunk of out-of-line allocated storage to store an arbitrary number
// of bits.
//
// - The bitvector remembers the bound of how many bits can be stored, but this
// may be slightly greater (by as much as some platform-specific constant)
// than the last argument passed to ensureSize().
//
// - The bitvector can resize itself automatically (set, clear, get) or can be used
// in a manual mode, which is faster (quickSet, quickClear, quickGet, ensureSize).
//
// - Accesses ASSERT that you are within bounds.
//
// - Bits are automatically initialized to zero.
//
// On the other hand, this BitVector class may not be the fastest around, since
// it does conditionals on every get/set/clear. But it is great if you need to
// juggle a lot of variable-length BitVectors and you're worried about wasting
// space.
class BitVector {
public:
BitVector()
: m_bitsOrPointer(makeInlineBits(0))
{
}
explicit BitVector(size_t numBits)
: m_bitsOrPointer(makeInlineBits(0))
{
ensureSize(numBits);
}
BitVector(const BitVector& other)
: m_bitsOrPointer(makeInlineBits(0))
{
(*this) = other;
}
~BitVector()
{
if (isInline())
return;
OutOfLineBits::destroy(outOfLineBits());
}
BitVector& operator=(const BitVector& other)
{
if (isInline() && other.isInline())
m_bitsOrPointer = other.m_bitsOrPointer;
else
setSlow(other);
return *this;
}
size_t size() const
{
if (isInline())
return maxInlineBits();
return outOfLineBits()->numBits();
}
void ensureSize(size_t numBits)
{
if (numBits <= size())
return;
resizeOutOfLine(numBits);
}
// Like ensureSize(), but supports reducing the size of the bitvector.
WTF_EXPORT_PRIVATE void resize(size_t numBits);
WTF_EXPORT_PRIVATE void clearAll();
bool quickGet(size_t bit) const
{
ASSERT(bit < size());
return !!(bits()[bit / bitsInPointer()] & (static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1))));
}
void quickSet(size_t bit)
{
ASSERT(bit < size());
bits()[bit / bitsInPointer()] |= (static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1)));
}
void quickClear(size_t bit)
{
ASSERT(bit < size());
bits()[bit / bitsInPointer()] &= ~(static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1)));
}
void quickSet(size_t bit, bool value)
{
if (value)
quickSet(bit);
else
quickClear(bit);
}
bool get(size_t bit) const
{
if (bit >= size())
return false;
return quickGet(bit);
}
void set(size_t bit)
{
ensureSize(bit + 1);
quickSet(bit);
}
void ensureSizeAndSet(size_t bit, size_t size)
{
ensureSize(size);
quickSet(bit);
}
void clear(size_t bit)
{
if (bit >= size())
return;
quickClear(bit);
}
void set(size_t bit, bool value)
{
if (value)
set(bit);
else
clear(bit);
}
void dump(PrintStream& out);
private:
static unsigned bitsInPointer()
{
return sizeof(void*) << 3;
}
static unsigned maxInlineBits()
{
return bitsInPointer() - 1;
}
static size_t byteCount(size_t bitCount)
{
return (bitCount + 7) >> 3;
}
static uintptr_t makeInlineBits(uintptr_t bits)
{
ASSERT(!(bits & (static_cast<uintptr_t>(1) << maxInlineBits())));
return bits | (static_cast<uintptr_t>(1) << maxInlineBits());
}
class OutOfLineBits {
public:
size_t numBits() const { return m_numBits; }
size_t numWords() const { return (m_numBits + bitsInPointer() - 1) / bitsInPointer(); }
uintptr_t* bits() { return bitwise_cast<uintptr_t*>(this + 1); }
const uintptr_t* bits() const { return bitwise_cast<const uintptr_t*>(this + 1); }
static WTF_EXPORT_PRIVATE OutOfLineBits* create(size_t numBits);
static WTF_EXPORT_PRIVATE void destroy(OutOfLineBits*);
private:
OutOfLineBits(size_t numBits)
: m_numBits(numBits)
{
}
size_t m_numBits;
};
bool isInline() const { return m_bitsOrPointer >> maxInlineBits(); }
const OutOfLineBits* outOfLineBits() const { return bitwise_cast<const OutOfLineBits*>(m_bitsOrPointer << 1); }
OutOfLineBits* outOfLineBits() { return bitwise_cast<OutOfLineBits*>(m_bitsOrPointer << 1); }
WTF_EXPORT_PRIVATE void resizeOutOfLine(size_t numBits);
WTF_EXPORT_PRIVATE void setSlow(const BitVector& other);
uintptr_t* bits()
{
if (isInline())
return &m_bitsOrPointer;
return outOfLineBits()->bits();
}
const uintptr_t* bits() const
{
if (isInline())
return &m_bitsOrPointer;
return outOfLineBits()->bits();
}
uintptr_t m_bitsOrPointer;
};
} // namespace WTF
using WTF::BitVector;
#endif // BitVector_h