| 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 38 matching lines...) Expand 10 before | Expand all | Expand 10 after 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 |
| 64 explicit BitVector(size_t numBits) |
| 65 : m_bitsOrPointer(makeInlineBits(0)) { |
| 66 ensureSize(numBits); |
| 67 } |
| 68 |
| 69 BitVector(const BitVector& other) |
| 70 : m_bitsOrPointer(makeInlineBits(0)) { |
| 71 (*this) = other; |
| 72 } |
| 73 |
| 74 ~BitVector() { |
| 75 if (isInline()) |
| 76 return; |
| 77 OutOfLineBits::destroy(outOfLineBits()); |
| 78 } |
| 79 |
| 80 BitVector& operator=(const BitVector& other) { |
| 81 if (isInline() && other.isInline()) |
| 82 m_bitsOrPointer = other.m_bitsOrPointer; |
| 83 else |
| 84 setSlow(other); |
| 85 return *this; |
| 86 } |
| 87 |
| 88 size_t size() const { |
| 89 if (isInline()) |
| 90 return maxInlineBits(); |
| 91 return outOfLineBits()->numBits(); |
| 92 } |
| 93 |
| 94 void ensureSize(size_t numBits) { |
| 95 if (numBits <= size()) |
| 96 return; |
| 97 resizeOutOfLine(numBits); |
| 98 } |
| 99 |
| 100 // Like ensureSize(), but supports reducing the size of the bitvector. |
| 101 void resize(size_t numBits); |
| 102 |
| 103 void clearAll(); |
| 104 |
| 105 bool quickGet(size_t bit) const { |
| 106 ASSERT_WITH_SECURITY_IMPLICATION(bit < size()); |
| 107 return !!(bits()[bit / bitsInPointer()] & (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()] |= (static_cast<uintptr_t>(1) << (bit & (bitsI
nPointer() - 1))); |
| 113 } |
| 114 |
| 115 void quickClear(size_t bit) { |
| 116 ASSERT_WITH_SECURITY_IMPLICATION(bit < size()); |
| 117 bits()[bit / bitsInPointer()] &= ~(static_cast<uintptr_t>(1) << (bit & (bits
InPointer() - 1))); |
| 118 } |
| 119 |
| 120 void quickSet(size_t bit, bool value) { |
| 121 if (value) |
| 122 quickSet(bit); |
| 123 else |
| 124 quickClear(bit); |
| 125 } |
| 126 |
| 127 bool get(size_t bit) const { |
| 128 if (bit >= size()) |
| 129 return false; |
| 130 return quickGet(bit); |
| 131 } |
| 132 |
| 133 void set(size_t bit) { |
| 134 ensureSize(bit + 1); |
| 135 quickSet(bit); |
| 136 } |
| 137 |
| 138 void ensureSizeAndSet(size_t bit, size_t size) { |
| 139 ensureSize(size); |
| 140 quickSet(bit); |
| 141 } |
| 142 |
| 143 void clear(size_t bit) { |
| 144 if (bit >= size()) |
| 145 return; |
| 146 quickClear(bit); |
| 147 } |
| 148 |
| 149 void set(size_t bit, bool value) { |
| 150 if (value) |
| 151 set(bit); |
| 152 else |
| 153 clear(bit); |
| 154 } |
| 155 |
| 156 void dump(PrintStream& out); |
| 157 |
| 158 private: |
| 159 static unsigned bitsInPointer() { |
| 160 return sizeof(void*) << 3; |
| 161 } |
| 162 |
| 163 static unsigned maxInlineBits() { |
| 164 return bitsInPointer() - 1; |
| 165 } |
| 166 |
| 167 static size_t byteCount(size_t bitCount) { |
| 168 return (bitCount + 7) >> 3; |
| 169 } |
| 170 |
| 171 static uintptr_t makeInlineBits(uintptr_t bits) { |
| 172 ASSERT(!(bits & (static_cast<uintptr_t>(1) << maxInlineBits()))); |
| 173 return bits | (static_cast<uintptr_t>(1) << maxInlineBits()); |
| 174 } |
| 175 |
| 176 class WTF_EXPORT OutOfLineBits { |
| 177 public: |
| 178 size_t numBits() const { return m_numBits; } |
| 179 size_t numWords() const { return (m_numBits + bitsInPointer() - 1) / bitsInP
ointer(); } |
| 180 uintptr_t* bits() { return bitwise_cast<uintptr_t*>(this + 1); } |
| 181 const uintptr_t* bits() const { return bitwise_cast<const uintptr_t*>(this +
1); } |
| 182 |
| 183 static OutOfLineBits* create(size_t numBits); |
| 184 |
| 185 static void destroy(OutOfLineBits*); |
| 186 |
| 187 private: |
| 188 OutOfLineBits(size_t numBits) |
| 189 : m_numBits(numBits) { |
| 63 } | 190 } |
| 64 | 191 |
| 65 explicit BitVector(size_t numBits) | 192 size_t m_numBits; |
| 66 : m_bitsOrPointer(makeInlineBits(0)) | 193 }; |
| 67 { | |
| 68 ensureSize(numBits); | |
| 69 } | |
| 70 | 194 |
| 71 BitVector(const BitVector& other) | 195 bool isInline() const { return m_bitsOrPointer >> maxInlineBits(); } |
| 72 : m_bitsOrPointer(makeInlineBits(0)) | |
| 73 { | |
| 74 (*this) = other; | |
| 75 } | |
| 76 | 196 |
| 197 const OutOfLineBits* outOfLineBits() const { return bitwise_cast<const OutOfLi
neBits*>(m_bitsOrPointer << 1); } |
| 198 OutOfLineBits* outOfLineBits() { return bitwise_cast<OutOfLineBits*>(m_bitsOrP
ointer << 1); } |
| 77 | 199 |
| 78 ~BitVector() | 200 void resizeOutOfLine(size_t numBits); |
| 79 { | 201 void setSlow(const BitVector& other); |
| 80 if (isInline()) | |
| 81 return; | |
| 82 OutOfLineBits::destroy(outOfLineBits()); | |
| 83 } | |
| 84 | 202 |
| 85 BitVector& operator=(const BitVector& other) | 203 uintptr_t* bits() { |
| 86 { | 204 if (isInline()) |
| 87 if (isInline() && other.isInline()) | 205 return &m_bitsOrPointer; |
| 88 m_bitsOrPointer = other.m_bitsOrPointer; | 206 return outOfLineBits()->bits(); |
| 89 else | 207 } |
| 90 setSlow(other); | |
| 91 return *this; | |
| 92 } | |
| 93 | 208 |
| 94 size_t size() const | 209 const uintptr_t* bits() const { |
| 95 { | 210 if (isInline()) |
| 96 if (isInline()) | 211 return &m_bitsOrPointer; |
| 97 return maxInlineBits(); | 212 return outOfLineBits()->bits(); |
| 98 return outOfLineBits()->numBits(); | 213 } |
| 99 } | |
| 100 | 214 |
| 101 void ensureSize(size_t numBits) | 215 uintptr_t m_bitsOrPointer; |
| 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 & (b
itsInPointer() - 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) / bit
sInPointer(); } | |
| 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); } | |
| 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 OutOf
LineBits*>(m_bitsOrPointer << 1); } | |
| 220 OutOfLineBits* outOfLineBits() { return bitwise_cast<OutOfLineBits*>(m_bitsO
rPointer << 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 }; | 216 }; |
| 241 | 217 |
| 242 } // namespace WTF | 218 } // namespace WTF |
| 243 | 219 |
| 244 using WTF::BitVector; | 220 using WTF::BitVector; |
| 245 | 221 |
| 246 #endif // BitVector_h | 222 #endif // BitVector_h |
| OLD | NEW |