Source/WTF/wtf/BitVector.h

   1 /*
   2  * Copyright (C) 2011 Apple Inc. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  * 1. Redistributions of source code must retain the above copyright
   8  *    notice, this list of conditions and the following disclaimer.
   9  * 2. Redistributions in binary form must reproduce the above copyright
  10  *    notice, this list of conditions and the following disclaimer in the
  11  *    documentation and/or other materials provided with the distribution.
  12  *
  13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
  14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
  17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
  21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  24  */
  25
  26 #ifndef BitVector_h
  27 #define BitVector_h
  28
  29 #include <stdio.h>
  30 #include <wtf/Assertions.h>
  31 #include <wtf/StdLibExtras.h>
  32
  33 namespace WTF {
  34
  35 // This is a space-efficient, resizeable bitvector class. In the common case it
  36 // occupies one word, but if necessary, it will inflate this one word to point
  37 // to a single chunk of out-of-line allocated storage to store an arbitrary number
  38 // of bits.
  39 //
  40 // - The bitvector remembers the bound of how many bits can be stored, but this
  41 //   may be slightly greater (by as much as some platform-specific constant)
  42 //   than the last argument passed to ensureSize().
  43 //
  44 // - The bitvector can resize itself automatically (set, clear, get) or can be used
  45 //   in a manual mode, which is faster (quickSet, quickClear, quickGet, ensureSize).
  46 //
  47 // - Accesses ASSERT that you are within bounds.
  48 //
  49 // - Bits are automatically initialized to zero.
  50 //
  51 // On the other hand, this BitVector class may not be the fastest around, since
  52 // it does conditionals on every get/set/clear. But it is great if you need to
  53 // juggle a lot of variable-length BitVectors and you're worried about wasting
  54 // space.
  55
  56 class BitVector {
  57 public:
  58     BitVector()
  59         : m_bitsOrPointer(makeInlineBits(0))
  60     {
  61     }
  62
  63     explicit BitVector(size_t numBits)
  64         : m_bitsOrPointer(makeInlineBits(0))
  65     {
  66         ensureSize(numBits);
  67     }
  68
  69     BitVector(const BitVector& other)
  70         : m_bitsOrPointer(makeInlineBits(0))
  71     {
  72         (*this) = other;
  73     }
  74
  75
  76     ~BitVector()
  77     {
  78         if (isInline())
  79             return;
  80         OutOfLineBits::destroy(outOfLineBits());
  81     }
  82
  83     BitVector& operator=(const BitVector& other)
  84     {
  85         if (isInline() && other.isInline())
  86             m_bitsOrPointer = other.m_bitsOrPointer;
  87         else
  88             setSlow(other);
  89         return *this;
  90     }
  91
  92     size_t size() const
  93     {
  94         if (isInline())
  95             return maxInlineBits();
  96         return outOfLineBits()->numBits();
  97     }
  98
  99     void ensureSize(size_t numBits)
 100     {
 101         if (numBits <= size())
 102             return;
 103         resizeOutOfLine(numBits);
 104     }
 105
 106     // Like ensureSize(), but supports reducing the size of the bitvector.
 107     WTF_EXPORT_PRIVATE void resize(size_t numBits);
 108
 109     WTF_EXPORT_PRIVATE void clearAll();
 110
 111     bool quickGet(size_t bit) const
 112     {
 113         ASSERT(bit < size());
 114         return !!(bits()[bit / bitsInPointer()] & (static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1))));
 115     }
 116
 117     void quickSet(size_t bit)
 118     {
 119         ASSERT(bit < size());
 120         bits()[bit / bitsInPointer()] |= (static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1)));
 121     }
 122
 123     void quickClear(size_t bit)
 124     {
 125         ASSERT(bit < size());
 126         bits()[bit / bitsInPointer()] &= ~(static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1)));
 127     }
 128
 129     void quickSet(size_t bit, bool value)
 130     {
 131         if (value)
 132             quickSet(bit);
 133         else
 134             quickClear(bit);
 135     }
 136
 137     bool get(size_t bit) const
 138     {
 139         if (bit >= size())
 140             return false;
 141         return quickGet(bit);
 142     }
 143
 144     void set(size_t bit)
 145     {
 146         ensureSize(bit + 1);
 147         quickSet(bit);
 148     }
 149
 150     void ensureSizeAndSet(size_t bit, size_t size)
 151     {
 152         ensureSize(size);
 153         quickSet(bit);
 154     }
 155
 156     void clear(size_t bit)
 157     {
 158         if (bit >= size())
 159             return;
 160         quickClear(bit);
 161     }
 162
 163     void set(size_t bit, bool value)
 164     {
 165         if (value)
 166             set(bit);
 167         else
 168             clear(bit);
 169     }
 170
 171     void dump(FILE* out);
 172
 173 private:
 174     static unsigned bitsInPointer()
 175     {
 176         return sizeof(void*) << 3;
 177     }
 178
 179     static unsigned maxInlineBits()
 180     {
 181         return bitsInPointer() - 1;
 182     }
 183
 184     static size_t byteCount(size_t bitCount)
 185     {
 186         return (bitCount + 7) >> 3;
 187     }
 188
 189     static uintptr_t makeInlineBits(uintptr_t bits)
 190     {
 191         ASSERT(!(bits & (static_cast<uintptr_t>(1) << maxInlineBits())));
 192         return bits | (static_cast<uintptr_t>(1) << maxInlineBits());
 193     }
 194
 195     class OutOfLineBits {
 196     public:
 197         size_t numBits() const { return m_numBits; }
 198         size_t numWords() const { return (m_numBits + bitsInPointer() - 1) / bitsInPointer(); }
 199         uintptr_t* bits() { return bitwise_cast<uintptr_t*>(this + 1); }
 200         const uintptr_t* bits() const { return bitwise_cast<const uintptr_t*>(this + 1); }
 201
 202         static WTF_EXPORT_PRIVATE OutOfLineBits* create(size_t numBits);
 203
 204         static WTF_EXPORT_PRIVATE void destroy(OutOfLineBits*);
 205
 206     private:
 207         OutOfLineBits(size_t numBits)
 208             : m_numBits(numBits)
 209         {
 210         }
 211
 212         size_t m_numBits;
 213     };
 214
 215     bool isInline() const { return m_bitsOrPointer >> maxInlineBits(); }
 216
 217     const OutOfLineBits* outOfLineBits() const { return bitwise_cast<const OutOfLineBits*>(m_bitsOrPointer << 1); }
 218     OutOfLineBits* outOfLineBits() { return bitwise_cast<OutOfLineBits*>(m_bitsOrPointer << 1); }
 219
 220     WTF_EXPORT_PRIVATE void resizeOutOfLine(size_t numBits);
 221     WTF_EXPORT_PRIVATE void setSlow(const BitVector& other);
 222
 223     uintptr_t* bits()
 224     {
 225         if (isInline())
 226             return &m_bitsOrPointer;
 227         return outOfLineBits()->bits();
 228     }
 229
 230     const uintptr_t* bits() const
 231     {
 232         if (isInline())
 233             return &m_bitsOrPointer;
 234         return outOfLineBits()->bits();
 235     }
 236
 237     uintptr_t m_bitsOrPointer;
 238 };
 239
 240 } // namespace WTF
 241
 242 using WTF::BitVector;
 243
 244 #endif // BitVector_h