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