| OLD | NEW |
| 1 /* | 1 /* |
| 2 * Copyright (C) 2005, 2006, 2007, 2008 Apple Inc. All rights reserved. | 2 * Copyright (C) 2005, 2006, 2007, 2008 Apple Inc. All rights reserved. |
| 3 * | 3 * |
| 4 * This library is free software; you can redistribute it and/or | 4 * This library is free software; you can redistribute it and/or |
| 5 * modify it under the terms of the GNU Library General Public | 5 * modify it under the terms of the GNU Library General Public |
| 6 * License as published by the Free Software Foundation; either | 6 * License as published by the Free Software Foundation; either |
| 7 * version 2 of the License, or (at your option) any later version. | 7 * version 2 of the License, or (at your option) any later version. |
| 8 * | 8 * |
| 9 * This library is distributed in the hope that it will be useful, | 9 * This library is distributed in the hope that it will be useful, |
| 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of | 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of |
| (...skipping 823 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 834 | 834 |
| 835 Vector(std::initializer_list<T> elements); | 835 Vector(std::initializer_list<T> elements); |
| 836 Vector& operator=(std::initializer_list<T> elements); | 836 Vector& operator=(std::initializer_list<T> elements); |
| 837 | 837 |
| 838 size_t size() const { return m_size; } | 838 size_t size() const { return m_size; } |
| 839 size_t capacity() const { return Base::capacity(); } | 839 size_t capacity() const { return Base::capacity(); } |
| 840 bool isEmpty() const { return !size(); } | 840 bool isEmpty() const { return !size(); } |
| 841 | 841 |
| 842 T& at(size_t i) | 842 T& at(size_t i) |
| 843 { | 843 { |
| 844 RELEASE_ASSERT(i < size()); | 844 CHECK_LT(i, size()); |
| 845 return Base::buffer()[i]; | 845 return Base::buffer()[i]; |
| 846 } | 846 } |
| 847 const T& at(size_t i) const | 847 const T& at(size_t i) const |
| 848 { | 848 { |
| 849 RELEASE_ASSERT(i < size()); | 849 CHECK_LT(i, size()); |
| 850 return Base::buffer()[i]; | 850 return Base::buffer()[i]; |
| 851 } | 851 } |
| 852 | 852 |
| 853 T& operator[](size_t i) { return at(i); } | 853 T& operator[](size_t i) { return at(i); } |
| 854 const T& operator[](size_t i) const { return at(i); } | 854 const T& operator[](size_t i) const { return at(i); } |
| 855 | 855 |
| 856 T* data() { return Base::buffer(); } | 856 T* data() { return Base::buffer(); } |
| 857 const T* data() const { return Base::buffer(); } | 857 const T* data() const { return Base::buffer(); } |
| 858 | 858 |
| 859 iterator begin() { return data(); } | 859 iterator begin() { return data(); } |
| (...skipping 286 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1146 size_t oldCapacity = capacity(); | 1146 size_t oldCapacity = capacity(); |
| 1147 size_t expandedCapacity = oldCapacity; | 1147 size_t expandedCapacity = oldCapacity; |
| 1148 // We use a more aggressive expansion strategy for Vectors with inline | 1148 // We use a more aggressive expansion strategy for Vectors with inline |
| 1149 // storage. This is because they are more likely to be on the stack, so the | 1149 // storage. This is because they are more likely to be on the stack, so the |
| 1150 // risk of heap bloat is minimized. Furthermore, exceeding the inline | 1150 // risk of heap bloat is minimized. Furthermore, exceeding the inline |
| 1151 // capacity limit is not supposed to happen in the common case and may | 1151 // capacity limit is not supposed to happen in the common case and may |
| 1152 // indicate a pathological condition or microbenchmark. | 1152 // indicate a pathological condition or microbenchmark. |
| 1153 if (INLINE_CAPACITY) { | 1153 if (INLINE_CAPACITY) { |
| 1154 expandedCapacity *= 2; | 1154 expandedCapacity *= 2; |
| 1155 // Check for integer overflow, which could happen in the 32-bit build. | 1155 // Check for integer overflow, which could happen in the 32-bit build. |
| 1156 RELEASE_ASSERT(expandedCapacity > oldCapacity); | 1156 CHECK_GT(expandedCapacity, oldCapacity); |
| 1157 } else { | 1157 } else { |
| 1158 // This cannot integer overflow. | 1158 // This cannot integer overflow. |
| 1159 // On 64-bit, the "expanded" integer is 32-bit, and any encroachment | 1159 // On 64-bit, the "expanded" integer is 32-bit, and any encroachment |
| 1160 // above 2^32 will fail allocation in allocateBuffer(). On 32-bit, | 1160 // above 2^32 will fail allocation in allocateBuffer(). On 32-bit, |
| 1161 // there's not enough address space to hold the old and new buffers. In | 1161 // there's not enough address space to hold the old and new buffers. In |
| 1162 // addition, our underlying allocator is supposed to always fail on > | 1162 // addition, our underlying allocator is supposed to always fail on > |
| 1163 // (2^31 - 1) allocations. | 1163 // (2^31 - 1) allocations. |
| 1164 expandedCapacity += (expandedCapacity / 4) + 1; | 1164 expandedCapacity += (expandedCapacity / 4) + 1; |
| 1165 } | 1165 } |
| 1166 reserveCapacity(std::max(newMinCapacity, std::max(static_cast<size_t>(kIniti
alVectorSize), expandedCapacity))); | 1166 reserveCapacity(std::max(newMinCapacity, std::max(static_cast<size_t>(kIniti
alVectorSize), expandedCapacity))); |
| (...skipping 145 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1312 template <typename T, size_t inlineCapacity, typename Allocator> | 1312 template <typename T, size_t inlineCapacity, typename Allocator> |
| 1313 template <typename U> | 1313 template <typename U> |
| 1314 void Vector<T, inlineCapacity, Allocator>::append(const U* data, size_t dataSize
) | 1314 void Vector<T, inlineCapacity, Allocator>::append(const U* data, size_t dataSize
) |
| 1315 { | 1315 { |
| 1316 ASSERT(Allocator::isAllocationAllowed()); | 1316 ASSERT(Allocator::isAllocationAllowed()); |
| 1317 size_t newSize = m_size + dataSize; | 1317 size_t newSize = m_size + dataSize; |
| 1318 if (newSize > capacity()) { | 1318 if (newSize > capacity()) { |
| 1319 data = expandCapacity(newSize, data); | 1319 data = expandCapacity(newSize, data); |
| 1320 ASSERT(begin()); | 1320 ASSERT(begin()); |
| 1321 } | 1321 } |
| 1322 RELEASE_ASSERT(newSize >= m_size); | 1322 CHECK_GE(newSize, m_size); |
| 1323 T* dest = end(); | 1323 T* dest = end(); |
| 1324 ANNOTATE_CHANGE_SIZE(begin(), capacity(), m_size, newSize); | 1324 ANNOTATE_CHANGE_SIZE(begin(), capacity(), m_size, newSize); |
| 1325 VectorCopier<VectorTraits<T>::canCopyWithMemcpy, T>::uninitializedCopy(data,
&data[dataSize], dest); | 1325 VectorCopier<VectorTraits<T>::canCopyWithMemcpy, T>::uninitializedCopy(data,
&data[dataSize], dest); |
| 1326 m_size = newSize; | 1326 m_size = newSize; |
| 1327 } | 1327 } |
| 1328 | 1328 |
| 1329 template <typename T, size_t inlineCapacity, typename Allocator> | 1329 template <typename T, size_t inlineCapacity, typename Allocator> |
| 1330 template <typename U> | 1330 template <typename U> |
| 1331 ALWAYS_INLINE void Vector<T, inlineCapacity, Allocator>::append(U&& val) | 1331 ALWAYS_INLINE void Vector<T, inlineCapacity, Allocator>::append(U&& val) |
| 1332 { | 1332 { |
| (...skipping 46 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1379 inline void Vector<T, inlineCapacity, Allocator>::appendVector(const Vector<U, o
therCapacity, OtherAllocator>& val) | 1379 inline void Vector<T, inlineCapacity, Allocator>::appendVector(const Vector<U, o
therCapacity, OtherAllocator>& val) |
| 1380 { | 1380 { |
| 1381 append(val.begin(), val.size()); | 1381 append(val.begin(), val.size()); |
| 1382 } | 1382 } |
| 1383 | 1383 |
| 1384 template <typename T, size_t inlineCapacity, typename Allocator> | 1384 template <typename T, size_t inlineCapacity, typename Allocator> |
| 1385 template <typename U> | 1385 template <typename U> |
| 1386 void Vector<T, inlineCapacity, Allocator>::insert(size_t position, const U* data
, size_t dataSize) | 1386 void Vector<T, inlineCapacity, Allocator>::insert(size_t position, const U* data
, size_t dataSize) |
| 1387 { | 1387 { |
| 1388 ASSERT(Allocator::isAllocationAllowed()); | 1388 ASSERT(Allocator::isAllocationAllowed()); |
| 1389 RELEASE_ASSERT(position <= size()); | 1389 CHECK_LE(position, size()); |
| 1390 size_t newSize = m_size + dataSize; | 1390 size_t newSize = m_size + dataSize; |
| 1391 if (newSize > capacity()) { | 1391 if (newSize > capacity()) { |
| 1392 data = expandCapacity(newSize, data); | 1392 data = expandCapacity(newSize, data); |
| 1393 ASSERT(begin()); | 1393 ASSERT(begin()); |
| 1394 } | 1394 } |
| 1395 RELEASE_ASSERT(newSize >= m_size); | 1395 CHECK_GE(newSize, m_size); |
| 1396 ANNOTATE_CHANGE_SIZE(begin(), capacity(), m_size, newSize); | 1396 ANNOTATE_CHANGE_SIZE(begin(), capacity(), m_size, newSize); |
| 1397 T* spot = begin() + position; | 1397 T* spot = begin() + position; |
| 1398 TypeOperations::moveOverlapping(spot, end(), spot + dataSize); | 1398 TypeOperations::moveOverlapping(spot, end(), spot + dataSize); |
| 1399 VectorCopier<VectorTraits<T>::canCopyWithMemcpy, T>::uninitializedCopy(data,
&data[dataSize], spot); | 1399 VectorCopier<VectorTraits<T>::canCopyWithMemcpy, T>::uninitializedCopy(data,
&data[dataSize], spot); |
| 1400 m_size = newSize; | 1400 m_size = newSize; |
| 1401 } | 1401 } |
| 1402 | 1402 |
| 1403 template <typename T, size_t inlineCapacity, typename Allocator> | 1403 template <typename T, size_t inlineCapacity, typename Allocator> |
| 1404 template <typename U> | 1404 template <typename U> |
| 1405 inline void Vector<T, inlineCapacity, Allocator>::insert(size_t position, U&& va
l) | 1405 inline void Vector<T, inlineCapacity, Allocator>::insert(size_t position, U&& va
l) |
| 1406 { | 1406 { |
| 1407 ASSERT(Allocator::isAllocationAllowed()); | 1407 ASSERT(Allocator::isAllocationAllowed()); |
| 1408 RELEASE_ASSERT(position <= size()); | 1408 CHECK_LE(position, size()); |
| 1409 typename std::remove_reference<U>::type* data = &val; | 1409 typename std::remove_reference<U>::type* data = &val; |
| 1410 if (size() == capacity()) { | 1410 if (size() == capacity()) { |
| 1411 data = expandCapacity(size() + 1, data); | 1411 data = expandCapacity(size() + 1, data); |
| 1412 ASSERT(begin()); | 1412 ASSERT(begin()); |
| 1413 } | 1413 } |
| 1414 ANNOTATE_CHANGE_SIZE(begin(), capacity(), m_size, m_size + 1); | 1414 ANNOTATE_CHANGE_SIZE(begin(), capacity(), m_size, m_size + 1); |
| 1415 T* spot = begin() + position; | 1415 T* spot = begin() + position; |
| 1416 TypeOperations::moveOverlapping(spot, end(), spot + 1); | 1416 TypeOperations::moveOverlapping(spot, end(), spot + 1); |
| 1417 new (NotNull, spot) T(std::forward<U>(*data)); | 1417 new (NotNull, spot) T(std::forward<U>(*data)); |
| 1418 ++m_size; | 1418 ++m_size; |
| (...skipping 23 matching lines...) Expand all Loading... |
| 1442 template <typename T, size_t inlineCapacity, typename Allocator> | 1442 template <typename T, size_t inlineCapacity, typename Allocator> |
| 1443 template <typename U, size_t c, typename V> | 1443 template <typename U, size_t c, typename V> |
| 1444 inline void Vector<T, inlineCapacity, Allocator>::prependVector(const Vector<U,
c, V>& val) | 1444 inline void Vector<T, inlineCapacity, Allocator>::prependVector(const Vector<U,
c, V>& val) |
| 1445 { | 1445 { |
| 1446 insert(0, val.begin(), val.size()); | 1446 insert(0, val.begin(), val.size()); |
| 1447 } | 1447 } |
| 1448 | 1448 |
| 1449 template <typename T, size_t inlineCapacity, typename Allocator> | 1449 template <typename T, size_t inlineCapacity, typename Allocator> |
| 1450 inline void Vector<T, inlineCapacity, Allocator>::remove(size_t position) | 1450 inline void Vector<T, inlineCapacity, Allocator>::remove(size_t position) |
| 1451 { | 1451 { |
| 1452 RELEASE_ASSERT(position < size()); | 1452 CHECK_LT(position, size()); |
| 1453 T* spot = begin() + position; | 1453 T* spot = begin() + position; |
| 1454 spot->~T(); | 1454 spot->~T(); |
| 1455 TypeOperations::moveOverlapping(spot + 1, end(), spot); | 1455 TypeOperations::moveOverlapping(spot + 1, end(), spot); |
| 1456 clearUnusedSlots(end() - 1, end()); | 1456 clearUnusedSlots(end() - 1, end()); |
| 1457 ANNOTATE_CHANGE_SIZE(begin(), capacity(), m_size, m_size - 1); | 1457 ANNOTATE_CHANGE_SIZE(begin(), capacity(), m_size, m_size - 1); |
| 1458 --m_size; | 1458 --m_size; |
| 1459 } | 1459 } |
| 1460 | 1460 |
| 1461 template <typename T, size_t inlineCapacity, typename Allocator> | 1461 template <typename T, size_t inlineCapacity, typename Allocator> |
| 1462 inline void Vector<T, inlineCapacity, Allocator>::remove(size_t position, size_t
length) | 1462 inline void Vector<T, inlineCapacity, Allocator>::remove(size_t position, size_t
length) |
| 1463 { | 1463 { |
| 1464 ASSERT_WITH_SECURITY_IMPLICATION(position <= size()); | 1464 ASSERT_WITH_SECURITY_IMPLICATION(position <= size()); |
| 1465 if (!length) | 1465 if (!length) |
| 1466 return; | 1466 return; |
| 1467 RELEASE_ASSERT(position + length <= size()); | 1467 CHECK_LE(position + length, size()); |
| 1468 T* beginSpot = begin() + position; | 1468 T* beginSpot = begin() + position; |
| 1469 T* endSpot = beginSpot + length; | 1469 T* endSpot = beginSpot + length; |
| 1470 TypeOperations::destruct(beginSpot, endSpot); | 1470 TypeOperations::destruct(beginSpot, endSpot); |
| 1471 TypeOperations::moveOverlapping(endSpot, end(), beginSpot); | 1471 TypeOperations::moveOverlapping(endSpot, end(), beginSpot); |
| 1472 clearUnusedSlots(end() - length, end()); | 1472 clearUnusedSlots(end() - length, end()); |
| 1473 ANNOTATE_CHANGE_SIZE(begin(), capacity(), m_size, m_size - length); | 1473 ANNOTATE_CHANGE_SIZE(begin(), capacity(), m_size, m_size - length); |
| 1474 m_size -= length; | 1474 m_size -= length; |
| 1475 } | 1475 } |
| 1476 | 1476 |
| 1477 template <typename T, size_t inlineCapacity, typename Allocator> | 1477 template <typename T, size_t inlineCapacity, typename Allocator> |
| (...skipping 50 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1528 Allocator::template trace<VisitorDispatcher, T, VectorTraits<T>>(vis
itor, *const_cast<T*>(bufferEntry)); | 1528 Allocator::template trace<VisitorDispatcher, T, VectorTraits<T>>(vis
itor, *const_cast<T*>(bufferEntry)); |
| 1529 checkUnusedSlots(buffer() + size(), buffer() + capacity()); | 1529 checkUnusedSlots(buffer() + size(), buffer() + capacity()); |
| 1530 } | 1530 } |
| 1531 } | 1531 } |
| 1532 | 1532 |
| 1533 } // namespace WTF | 1533 } // namespace WTF |
| 1534 | 1534 |
| 1535 using WTF::Vector; | 1535 using WTF::Vector; |
| 1536 | 1536 |
| 1537 #endif // WTF_Vector_h | 1537 #endif // WTF_Vector_h |
| OLD | NEW |