Source/WTF/wtf/FastBitVector.h

   1 /*
   2  * Copyright (C) 2012 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 FastBitVector_h
  27 #define FastBitVector_h
  28
  29 #include <wtf/FastMalloc.h>
  30 #include <wtf/OwnArrayPtr.h>
  31 #include <wtf/PassOwnArrayPtr.h>
  32 #include <wtf/StdLibExtras.h>
  33
  34 namespace WTF {
  35
  36 class FastBitVector {
  37 public:
  38     FastBitVector()
  39         : m_array(0)
  40         , m_numBits(0)
  41     {
  42     }
  43
  44     FastBitVector(const FastBitVector& other)
  45         : m_array(0)
  46         , m_numBits(0)
  47     {
  48         *this = other;
  49     }
  50
  51     ~FastBitVector()
  52     {
  53         if (m_array)
  54             fastFree(m_array);
  55     }
  56
  57     FastBitVector& operator=(const FastBitVector& other)
  58     {
  59         size_t length = other.arrayLength();
  60         uint32_t* newArray = static_cast<uint32_t*>(fastCalloc(length, 4));
  61         memcpy(newArray, other.m_array, length * 4);
  62         if (m_array)
  63             fastFree(m_array);
  64         m_array = newArray;
  65         m_numBits = other.m_numBits;
  66         return *this;
  67     }
  68
  69     size_t numBits() const { return m_numBits; }
  70
  71     void resize(size_t numBits)
  72     {
  73         // Use fastCalloc instead of fastRealloc because we expect the common
  74         // use case for this method to be initializing the size of the bitvector.
  75
  76         size_t newLength = (numBits + 31) >> 5;
  77         uint32_t* newArray = static_cast<uint32_t*>(fastCalloc(newLength, 4));
  78         memcpy(newArray, m_array, arrayLength() * 4);
  79         if (m_array)
  80             fastFree(m_array);
  81         m_array = newArray;
  82         m_numBits = numBits;
  83     }
  84
  85     void setAll()
  86     {
  87         memset(m_array, 255, arrayLength() * 4);
  88     }
  89
  90     void clearAll()
  91     {
  92         memset(m_array, 0, arrayLength() * 4);
  93     }
  94
  95     void set(const FastBitVector& other)
  96     {
  97         ASSERT(m_numBits == other.m_numBits);
  98         memcpy(m_array, other.m_array, arrayLength() * 4);
  99     }
 100
 101     bool setAndCheck(const FastBitVector& other)
 102     {
 103         bool changed = false;
 104         ASSERT(m_numBits == other.m_numBits);
 105         for (unsigned i = arrayLength(); i--;) {
 106             if (m_array[i] == other.m_array[i])
 107                 continue;
 108             m_array[i] = other.m_array[i];
 109             changed = true;
 110         }
 111         return changed;
 112     }
 113
 114     bool equals(const FastBitVector& other) const
 115     {
 116         ASSERT(m_numBits == other.m_numBits);
 117         // Use my own comparison loop because memcmp does more than what I want
 118         // and bcmp is not as standard.
 119         for (unsigned i = arrayLength(); i--;) {
 120             if (m_array[i] != other.m_array[i])
 121                 return false;
 122         }
 123         return true;
 124     }
 125
 126     void merge(const FastBitVector& other)
 127     {
 128         ASSERT(m_numBits == other.m_numBits);
 129         for (unsigned i = arrayLength(); i--;)
 130             m_array[i] |= other.m_array[i];
 131     }
 132
 133     void filter(const FastBitVector& other)
 134     {
 135         ASSERT(m_numBits == other.m_numBits);
 136         for (unsigned i = arrayLength(); i--;)
 137             m_array[i] &= other.m_array[i];
 138     }
 139
 140     void exclude(const FastBitVector& other)
 141     {
 142         ASSERT(m_numBits == other.m_numBits);
 143         for (unsigned i = arrayLength(); i--;)
 144             m_array[i] &= ~other.m_array[i];
 145     }
 146
 147     void set(size_t i)
 148     {
 149         ASSERT(i < m_numBits);
 150         m_array[i >> 5] |= (1 << (i & 31));
 151     }
 152
 153     void clear(size_t i)
 154     {
 155         ASSERT(i < m_numBits);
 156         m_array[i >> 5] &= ~(1 << (i & 31));
 157     }
 158
 159     void set(size_t i, bool value)
 160     {
 161         if (value)
 162             set(i);
 163         else
 164             clear(i);
 165     }
 166
 167     bool get(size_t i) const
 168     {
 169         ASSERT(i < m_numBits);
 170         return !!(m_array[i >> 5] & (1 << (i & 31)));
 171     }
 172 private:
 173     size_t arrayLength() const { return (m_numBits + 31) >> 5; }
 174
 175     uint32_t* m_array; // No, this can't be an OwnArrayPtr.
 176     size_t m_numBits;
 177 };
 178
 179 } // namespace WTF
 180
 181 using WTF::FastBitVector;
 182
 183 #endif // FastBitVector_h
 184