| 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 |
| (...skipping 39 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 50 // - Accesses ASSERT that you are within bounds. | 50 // - Accesses ASSERT that you are within bounds. |
| 51 // | 51 // |
| 52 // - Bits are automatically initialized to zero. | 52 // - Bits are automatically initialized to zero. |
| 53 // | 53 // |
| 54 // On the other hand, this BitVector class may not be the fastest around, since | 54 // On the other hand, this BitVector class may not be the fastest around, since |
| 55 // it does conditionals on every get/set/clear. But it is great if you need to | 55 // it does conditionals on every get/set/clear. But it is great if you need to |
| 56 // juggle a lot of variable-length BitVectors and you're worried about wasting | 56 // juggle a lot of variable-length BitVectors and you're worried about wasting |
| 57 // space. | 57 // space. |
| 58 | 58 |
| 59 class WTF_EXPORT BitVector { | 59 class WTF_EXPORT BitVector { |
| 60 DISALLOW_NEW(); | 60 DISALLOW_NEW(); |
| 61 public: | 61 |
| 62 BitVector() | 62 public: |
| 63 : m_bitsOrPointer(makeInlineBits(0)) | 63 BitVector() : m_bitsOrPointer(makeInlineBits(0)) {} |
| 64 { | 64 |
| 65 explicit BitVector(size_t numBits) : m_bitsOrPointer(makeInlineBits(0)) { |
| 66 ensureSize(numBits); |
| 67 } |
| 68 |
| 69 BitVector(const BitVector& other) : m_bitsOrPointer(makeInlineBits(0)) { |
| 70 (*this) = other; |
| 71 } |
| 72 |
| 73 ~BitVector() { |
| 74 if (isInline()) |
| 75 return; |
| 76 OutOfLineBits::destroy(outOfLineBits()); |
| 77 } |
| 78 |
| 79 BitVector& operator=(const BitVector& other) { |
| 80 if (isInline() && other.isInline()) |
| 81 m_bitsOrPointer = other.m_bitsOrPointer; |
| 82 else |
| 83 setSlow(other); |
| 84 return *this; |
| 85 } |
| 86 |
| 87 size_t size() const { |
| 88 if (isInline()) |
| 89 return maxInlineBits(); |
| 90 return outOfLineBits()->numBits(); |
| 91 } |
| 92 |
| 93 void ensureSize(size_t numBits) { |
| 94 if (numBits <= size()) |
| 95 return; |
| 96 resizeOutOfLine(numBits); |
| 97 } |
| 98 |
| 99 // Like ensureSize(), but supports reducing the size of the bitvector. |
| 100 void resize(size_t numBits); |
| 101 |
| 102 void clearAll(); |
| 103 |
| 104 bool quickGet(size_t bit) const { |
| 105 ASSERT_WITH_SECURITY_IMPLICATION(bit < size()); |
| 106 return !!(bits()[bit / bitsInPointer()] & |
| 107 (static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1)))); |
| 108 } |
| 109 |
| 110 void quickSet(size_t bit) { |
| 111 ASSERT_WITH_SECURITY_IMPLICATION(bit < size()); |
| 112 bits()[bit / bitsInPointer()] |= |
| 113 (static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1))); |
| 114 } |
| 115 |
| 116 void quickClear(size_t bit) { |
| 117 ASSERT_WITH_SECURITY_IMPLICATION(bit < size()); |
| 118 bits()[bit / bitsInPointer()] &= |
| 119 ~(static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1))); |
| 120 } |
| 121 |
| 122 void quickSet(size_t bit, bool value) { |
| 123 if (value) |
| 124 quickSet(bit); |
| 125 else |
| 126 quickClear(bit); |
| 127 } |
| 128 |
| 129 bool get(size_t bit) const { |
| 130 if (bit >= size()) |
| 131 return false; |
| 132 return quickGet(bit); |
| 133 } |
| 134 |
| 135 void set(size_t bit) { |
| 136 ensureSize(bit + 1); |
| 137 quickSet(bit); |
| 138 } |
| 139 |
| 140 void ensureSizeAndSet(size_t bit, size_t size) { |
| 141 ensureSize(size); |
| 142 quickSet(bit); |
| 143 } |
| 144 |
| 145 void clear(size_t bit) { |
| 146 if (bit >= size()) |
| 147 return; |
| 148 quickClear(bit); |
| 149 } |
| 150 |
| 151 void set(size_t bit, bool value) { |
| 152 if (value) |
| 153 set(bit); |
| 154 else |
| 155 clear(bit); |
| 156 } |
| 157 |
| 158 void dump(PrintStream& out); |
| 159 |
| 160 private: |
| 161 static unsigned bitsInPointer() { return sizeof(void*) << 3; } |
| 162 |
| 163 static unsigned maxInlineBits() { return bitsInPointer() - 1; } |
| 164 |
| 165 static size_t byteCount(size_t bitCount) { return (bitCount + 7) >> 3; } |
| 166 |
| 167 static uintptr_t makeInlineBits(uintptr_t bits) { |
| 168 ASSERT(!(bits & (static_cast<uintptr_t>(1) << maxInlineBits()))); |
| 169 return bits | (static_cast<uintptr_t>(1) << maxInlineBits()); |
| 170 } |
| 171 |
| 172 class WTF_EXPORT OutOfLineBits { |
| 173 DISALLOW_NEW_EXCEPT_PLACEMENT_NEW(); |
| 174 |
| 175 public: |
| 176 size_t numBits() const { return m_numBits; } |
| 177 size_t numWords() const { |
| 178 return (m_numBits + bitsInPointer() - 1) / bitsInPointer(); |
| 179 } |
| 180 uintptr_t* bits() { return bitwise_cast<uintptr_t*>(this + 1); } |
| 181 const uintptr_t* bits() const { |
| 182 return bitwise_cast<const uintptr_t*>(this + 1); |
| 65 } | 183 } |
| 66 | 184 |
| 67 explicit BitVector(size_t numBits) | 185 static OutOfLineBits* create(size_t numBits); |
| 68 : m_bitsOrPointer(makeInlineBits(0)) | |
| 69 { | |
| 70 ensureSize(numBits); | |
| 71 } | |
| 72 | 186 |
| 73 BitVector(const BitVector& other) | 187 static void destroy(OutOfLineBits*); |
| 74 : m_bitsOrPointer(makeInlineBits(0)) | |
| 75 { | |
| 76 (*this) = other; | |
| 77 } | |
| 78 | 188 |
| 189 private: |
| 190 OutOfLineBits(size_t numBits) : m_numBits(numBits) {} |
| 79 | 191 |
| 80 ~BitVector() | 192 size_t m_numBits; |
| 81 { | 193 }; |
| 82 if (isInline()) | |
| 83 return; | |
| 84 OutOfLineBits::destroy(outOfLineBits()); | |
| 85 } | |
| 86 | 194 |
| 87 BitVector& operator=(const BitVector& other) | 195 bool isInline() const { return m_bitsOrPointer >> maxInlineBits(); } |
| 88 { | |
| 89 if (isInline() && other.isInline()) | |
| 90 m_bitsOrPointer = other.m_bitsOrPointer; | |
| 91 else | |
| 92 setSlow(other); | |
| 93 return *this; | |
| 94 } | |
| 95 | 196 |
| 96 size_t size() const | 197 const OutOfLineBits* outOfLineBits() const { |
| 97 { | 198 return bitwise_cast<const OutOfLineBits*>(m_bitsOrPointer << 1); |
| 98 if (isInline()) | 199 } |
| 99 return maxInlineBits(); | 200 OutOfLineBits* outOfLineBits() { |
| 100 return outOfLineBits()->numBits(); | 201 return bitwise_cast<OutOfLineBits*>(m_bitsOrPointer << 1); |
| 101 } | 202 } |
| 102 | 203 |
| 103 void ensureSize(size_t numBits) | 204 void resizeOutOfLine(size_t numBits); |
| 104 { | 205 void setSlow(const BitVector& other); |
| 105 if (numBits <= size()) | |
| 106 return; | |
| 107 resizeOutOfLine(numBits); | |
| 108 } | |
| 109 | 206 |
| 110 // Like ensureSize(), but supports reducing the size of the bitvector. | 207 uintptr_t* bits() { |
| 111 void resize(size_t numBits); | 208 if (isInline()) |
| 209 return &m_bitsOrPointer; |
| 210 return outOfLineBits()->bits(); |
| 211 } |
| 112 | 212 |
| 113 void clearAll(); | 213 const uintptr_t* bits() const { |
| 214 if (isInline()) |
| 215 return &m_bitsOrPointer; |
| 216 return outOfLineBits()->bits(); |
| 217 } |
| 114 | 218 |
| 115 bool quickGet(size_t bit) const | 219 uintptr_t m_bitsOrPointer; |
| 116 { | |
| 117 ASSERT_WITH_SECURITY_IMPLICATION(bit < size()); | |
| 118 return !!(bits()[bit / bitsInPointer()] & (static_cast<uintptr_t>(1) <<
(bit & (bitsInPointer() - 1)))); | |
| 119 } | |
| 120 | |
| 121 void quickSet(size_t bit) | |
| 122 { | |
| 123 ASSERT_WITH_SECURITY_IMPLICATION(bit < size()); | |
| 124 bits()[bit / bitsInPointer()] |= (static_cast<uintptr_t>(1) << (bit & (b
itsInPointer() - 1))); | |
| 125 } | |
| 126 | |
| 127 void quickClear(size_t bit) | |
| 128 { | |
| 129 ASSERT_WITH_SECURITY_IMPLICATION(bit < size()); | |
| 130 bits()[bit / bitsInPointer()] &= ~(static_cast<uintptr_t>(1) << (bit & (
bitsInPointer() - 1))); | |
| 131 } | |
| 132 | |
| 133 void quickSet(size_t bit, bool value) | |
| 134 { | |
| 135 if (value) | |
| 136 quickSet(bit); | |
| 137 else | |
| 138 quickClear(bit); | |
| 139 } | |
| 140 | |
| 141 bool get(size_t bit) const | |
| 142 { | |
| 143 if (bit >= size()) | |
| 144 return false; | |
| 145 return quickGet(bit); | |
| 146 } | |
| 147 | |
| 148 void set(size_t bit) | |
| 149 { | |
| 150 ensureSize(bit + 1); | |
| 151 quickSet(bit); | |
| 152 } | |
| 153 | |
| 154 void ensureSizeAndSet(size_t bit, size_t size) | |
| 155 { | |
| 156 ensureSize(size); | |
| 157 quickSet(bit); | |
| 158 } | |
| 159 | |
| 160 void clear(size_t bit) | |
| 161 { | |
| 162 if (bit >= size()) | |
| 163 return; | |
| 164 quickClear(bit); | |
| 165 } | |
| 166 | |
| 167 void set(size_t bit, bool value) | |
| 168 { | |
| 169 if (value) | |
| 170 set(bit); | |
| 171 else | |
| 172 clear(bit); | |
| 173 } | |
| 174 | |
| 175 void dump(PrintStream& out); | |
| 176 | |
| 177 private: | |
| 178 static unsigned bitsInPointer() | |
| 179 { | |
| 180 return sizeof(void*) << 3; | |
| 181 } | |
| 182 | |
| 183 static unsigned maxInlineBits() | |
| 184 { | |
| 185 return bitsInPointer() - 1; | |
| 186 } | |
| 187 | |
| 188 static size_t byteCount(size_t bitCount) | |
| 189 { | |
| 190 return (bitCount + 7) >> 3; | |
| 191 } | |
| 192 | |
| 193 static uintptr_t makeInlineBits(uintptr_t bits) | |
| 194 { | |
| 195 ASSERT(!(bits & (static_cast<uintptr_t>(1) << maxInlineBits()))); | |
| 196 return bits | (static_cast<uintptr_t>(1) << maxInlineBits()); | |
| 197 } | |
| 198 | |
| 199 class WTF_EXPORT OutOfLineBits { | |
| 200 DISALLOW_NEW_EXCEPT_PLACEMENT_NEW(); | |
| 201 public: | |
| 202 size_t numBits() const { return m_numBits; } | |
| 203 size_t numWords() const { return (m_numBits + bitsInPointer() - 1) / bit
sInPointer(); } | |
| 204 uintptr_t* bits() { return bitwise_cast<uintptr_t*>(this + 1); } | |
| 205 const uintptr_t* bits() const { return bitwise_cast<const uintptr_t*>(th
is + 1); } | |
| 206 | |
| 207 static OutOfLineBits* create(size_t numBits); | |
| 208 | |
| 209 static void destroy(OutOfLineBits*); | |
| 210 | |
| 211 private: | |
| 212 OutOfLineBits(size_t numBits) | |
| 213 : m_numBits(numBits) | |
| 214 { | |
| 215 } | |
| 216 | |
| 217 size_t m_numBits; | |
| 218 }; | |
| 219 | |
| 220 bool isInline() const { return m_bitsOrPointer >> maxInlineBits(); } | |
| 221 | |
| 222 const OutOfLineBits* outOfLineBits() const { return bitwise_cast<const OutOf
LineBits*>(m_bitsOrPointer << 1); } | |
| 223 OutOfLineBits* outOfLineBits() { return bitwise_cast<OutOfLineBits*>(m_bitsO
rPointer << 1); } | |
| 224 | |
| 225 void resizeOutOfLine(size_t numBits); | |
| 226 void setSlow(const BitVector& other); | |
| 227 | |
| 228 uintptr_t* bits() | |
| 229 { | |
| 230 if (isInline()) | |
| 231 return &m_bitsOrPointer; | |
| 232 return outOfLineBits()->bits(); | |
| 233 } | |
| 234 | |
| 235 const uintptr_t* bits() const | |
| 236 { | |
| 237 if (isInline()) | |
| 238 return &m_bitsOrPointer; | |
| 239 return outOfLineBits()->bits(); | |
| 240 } | |
| 241 | |
| 242 uintptr_t m_bitsOrPointer; | |
| 243 }; | 220 }; |
| 244 | 221 |
| 245 } // namespace WTF | 222 } // namespace WTF |
| 246 | 223 |
| 247 using WTF::BitVector; | 224 using WTF::BitVector; |
| 248 | 225 |
| 249 #endif // BitVector_h | 226 #endif // BitVector_h |
| OLD | NEW |