third_party/WebKit/Source/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 "wtf/Assertions.h"
  30 #include "wtf/StdLibExtras.h"
  31 #include "wtf/WTFExport.h"
  32
  33 namespace WTF {
  34
  35 class PrintStream;
  36
  37 // This is a space-efficient, resizeable bitvector class. In the common case it
  38 // occupies one word, but if necessary, it will inflate this one word to point
  39 // to a single chunk of out-of-line allocated storage to store an arbitrary number
  40 // of bits.
  41 //
  42 // - The bitvector remembers the bound of how many bits can be stored, but this
  43 //   may be slightly greater (by as much as some platform-specific constant)
  44 //   than the last argument passed to ensureSize().
  45 //
  46 // - The bitvector can resize itself automatically (set, clear, get) or can be used
  47 //   in a manual mode, which is faster (quickSet, quickClear, quickGet, ensureSize).
  48 //
  49 // - Accesses ASSERT that you are within bounds.
  50 //
  51 // - Bits are automatically initialized to zero.
  52 //
  53 // On the other hand, this BitVector class may not be the fastest around, since
  54 // it does conditionals on every get/set/clear. But it is great if you need to
  55 // juggle a lot of variable-length BitVectors and you're worried about wasting
  56 // space.
  57
  58 class WTF_EXPORT BitVector {
  59 public:
  60     BitVector()
  61         : m_bitsOrPointer(makeInlineBits(0))
  62     {
  63     }
  64
  65     explicit BitVector(size_t numBits)
  66         : m_bitsOrPointer(makeInlineBits(0))
  67     {
  68         ensureSize(numBits);
  69     }
  70
  71     BitVector(const BitVector& other)
  72         : m_bitsOrPointer(makeInlineBits(0))
  73     {
  74         (*this) = other;
  75     }
  76
  77
  78     ~BitVector()
  79     {
  80         if (isInline())
  81             return;
  82         OutOfLineBits::destroy(outOfLineBits());
  83     }
  84
  85     BitVector& operator=(const BitVector& other)
  86     {
  87         if (isInline() && other.isInline())
  88             m_bitsOrPointer = other.m_bitsOrPointer;
  89         else
  90             setSlow(other);
  91         return *this;
  92     }
  93
  94     size_t size() const
  95     {
  96         if (isInline())
  97             return maxInlineBits();
  98         return outOfLineBits()->numBits();
  99     }
 100
 101     void ensureSize(size_t numBits)
 102     {
 103         if (numBits <= size())
 104             return;
 105         resizeOutOfLine(numBits);
 106     }
 107
 108     // Like ensureSize(), but supports reducing the size of the bitvector.
 109     void resize(size_t numBits);
 110
 111     void clearAll();
 112
 113     bool quickGet(size_t bit) const
 114     {
 115         ASSERT_WITH_SECURITY_IMPLICATION(bit < size());
 116         return !!(bits()[bit / bitsInPointer()] & (static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1))));
 117     }
 118
 119     void quickSet(size_t bit)
 120     {
 121         ASSERT_WITH_SECURITY_IMPLICATION(bit < size());
 122         bits()[bit / bitsInPointer()] |= (static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1)));
 123     }
 124
 125     void quickClear(size_t bit)
 126     {
 127         ASSERT_WITH_SECURITY_IMPLICATION(bit < size());
 128         bits()[bit / bitsInPointer()] &= ~(static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1)));
 129     }
 130
 131     void quickSet(size_t bit, bool value)
 132     {
 133         if (value)
 134             quickSet(bit);
 135         else
 136             quickClear(bit);
 137     }
 138
 139     bool get(size_t bit) const
 140     {
 141         if (bit >= size())
 142             return false;
 143         return quickGet(bit);
 144     }
 145
 146     void set(size_t bit)
 147     {
 148         ensureSize(bit + 1);
 149         quickSet(bit);
 150     }
 151
 152     void ensureSizeAndSet(size_t bit, size_t size)
 153     {
 154         ensureSize(size);
 155         quickSet(bit);
 156     }
 157
 158     void clear(size_t bit)
 159     {
 160         if (bit >= size())
 161             return;
 162         quickClear(bit);
 163     }
 164
 165     void set(size_t bit, bool value)
 166     {
 167         if (value)
 168             set(bit);
 169         else
 170             clear(bit);
 171     }
 172
 173     void dump(PrintStream& out);
 174
 175 private:
 176     static unsigned bitsInPointer()
 177     {
 178         return sizeof(void*) << 3;
 179     }
 180
 181     static unsigned maxInlineBits()
 182     {
 183         return bitsInPointer() - 1;
 184     }
 185
 186     static size_t byteCount(size_t bitCount)
 187     {
 188         return (bitCount + 7) >> 3;
 189     }
 190
 191     static uintptr_t makeInlineBits(uintptr_t bits)
 192     {
 193         ASSERT(!(bits & (static_cast<uintptr_t>(1) << maxInlineBits())));
 194         return bits | (static_cast<uintptr_t>(1) << maxInlineBits());
 195     }
 196
 197     class WTF_EXPORT OutOfLineBits {
 198     public:
 199         size_t numBits() const { return m_numBits; }
 200         size_t numWords() const { return (m_numBits + bitsInPointer() - 1) / bitsInPointer(); }
 201         uintptr_t* bits() { return bitwise_cast<uintptr_t*>(this + 1); }
 202         const uintptr_t* bits() const { return bitwise_cast<const uintptr_t*>(this + 1); }
 203
 204         static OutOfLineBits* create(size_t numBits);
 205
 206         static void destroy(OutOfLineBits*);
 207
 208     private:
 209         OutOfLineBits(size_t numBits)
 210             : m_numBits(numBits)
 211         {
 212         }
 213
 214         size_t m_numBits;
 215     };
 216
 217     bool isInline() const { return m_bitsOrPointer >> maxInlineBits(); }
 218
 219     const OutOfLineBits* outOfLineBits() const { return bitwise_cast<const OutOfLineBits*>(m_bitsOrPointer << 1); }
 220     OutOfLineBits* outOfLineBits() { return bitwise_cast<OutOfLineBits*>(m_bitsOrPointer << 1); }
 221
 222     void resizeOutOfLine(size_t numBits);
 223     void setSlow(const BitVector& other);
 224
 225     uintptr_t* bits()
 226     {
 227         if (isInline())
 228             return &m_bitsOrPointer;
 229         return outOfLineBits()->bits();
 230     }
 231
 232     const uintptr_t* bits() const
 233     {
 234         if (isInline())
 235             return &m_bitsOrPointer;
 236         return outOfLineBits()->bits();
 237     }
 238
 239     uintptr_t m_bitsOrPointer;
 240 };
 241
 242 } // namespace WTF
 243
 244 using WTF::BitVector;
 245
 246 #endif // BitVector_h