Home | History | Annotate | Download | only in wtf 
      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
    247