| 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 982 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 993 bool IsEmpty() const { return !size(); } | 993 bool IsEmpty() const { return !size(); } |
| 994 | 994 |
| 995 // at() and operator[]: Obtain the reference of the element that is located | 995 // at() and operator[]: Obtain the reference of the element that is located |
| 996 // at the given index. The reference may be invalidated on a reallocation. | 996 // at the given index. The reference may be invalidated on a reallocation. |
| 997 // | 997 // |
| 998 // at() can be used in cases like: | 998 // at() can be used in cases like: |
| 999 // pointerToVector->at(1); | 999 // pointerToVector->at(1); |
| 1000 // instead of: | 1000 // instead of: |
| 1001 // (*pointerToVector)[1]; | 1001 // (*pointerToVector)[1]; |
| 1002 T& at(size_t i) { | 1002 T& at(size_t i) { |
| 1003 RELEASE_ASSERT(i < size()); | 1003 CHECK_LT(i, size()); |
| 1004 return Base::Buffer()[i]; | 1004 return Base::Buffer()[i]; |
| 1005 } | 1005 } |
| 1006 const T& at(size_t i) const { | 1006 const T& at(size_t i) const { |
| 1007 RELEASE_ASSERT(i < size()); | 1007 CHECK_LT(i, size()); |
| 1008 return Base::Buffer()[i]; | 1008 return Base::Buffer()[i]; |
| 1009 } | 1009 } |
| 1010 | 1010 |
| 1011 T& operator[](size_t i) { return at(i); } | 1011 T& operator[](size_t i) { return at(i); } |
| 1012 const T& operator[](size_t i) const { return at(i); } | 1012 const T& operator[](size_t i) const { return at(i); } |
| 1013 | 1013 |
| 1014 // Return a pointer to the front of the backing buffer. Those pointers get | 1014 // Return a pointer to the front of the backing buffer. Those pointers get |
| 1015 // invalidated on a reallocation. | 1015 // invalidated on a reallocation. |
| 1016 T* data() { return Base::Buffer(); } | 1016 T* data() { return Base::Buffer(); } |
| 1017 const T* data() const { return Base::Buffer(); } | 1017 const T* data() const { return Base::Buffer(); } |
| (...skipping 482 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1500 size_t old_capacity = capacity(); | 1500 size_t old_capacity = capacity(); |
| 1501 size_t expanded_capacity = old_capacity; | 1501 size_t expanded_capacity = old_capacity; |
| 1502 // We use a more aggressive expansion strategy for Vectors with inline | 1502 // We use a more aggressive expansion strategy for Vectors with inline |
| 1503 // storage. This is because they are more likely to be on the stack, so the | 1503 // storage. This is because they are more likely to be on the stack, so the |
| 1504 // risk of heap bloat is minimized. Furthermore, exceeding the inline | 1504 // risk of heap bloat is minimized. Furthermore, exceeding the inline |
| 1505 // capacity limit is not supposed to happen in the common case and may | 1505 // capacity limit is not supposed to happen in the common case and may |
| 1506 // indicate a pathological condition or microbenchmark. | 1506 // indicate a pathological condition or microbenchmark. |
| 1507 if (INLINE_CAPACITY) { | 1507 if (INLINE_CAPACITY) { |
| 1508 expanded_capacity *= 2; | 1508 expanded_capacity *= 2; |
| 1509 // Check for integer overflow, which could happen in the 32-bit build. | 1509 // Check for integer overflow, which could happen in the 32-bit build. |
| 1510 RELEASE_ASSERT(expanded_capacity > old_capacity); | 1510 CHECK_GT(expanded_capacity, old_capacity); |
| 1511 } else { | 1511 } else { |
| 1512 // This cannot integer overflow. | 1512 // This cannot integer overflow. |
| 1513 // On 64-bit, the "expanded" integer is 32-bit, and any encroachment | 1513 // On 64-bit, the "expanded" integer is 32-bit, and any encroachment |
| 1514 // above 2^32 will fail allocation in allocateBuffer(). On 32-bit, | 1514 // above 2^32 will fail allocation in allocateBuffer(). On 32-bit, |
| 1515 // there's not enough address space to hold the old and new buffers. In | 1515 // there's not enough address space to hold the old and new buffers. In |
| 1516 // addition, our underlying allocator is supposed to always fail on > | 1516 // addition, our underlying allocator is supposed to always fail on > |
| 1517 // (2^31 - 1) allocations. | 1517 // (2^31 - 1) allocations. |
| 1518 expanded_capacity += (expanded_capacity / 4) + 1; | 1518 expanded_capacity += (expanded_capacity / 4) + 1; |
| 1519 } | 1519 } |
| 1520 ReserveCapacity(std::max( | 1520 ReserveCapacity(std::max( |
| (...skipping 178 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1699 template <typename T, size_t inlineCapacity, typename Allocator> | 1699 template <typename T, size_t inlineCapacity, typename Allocator> |
| 1700 template <typename U> | 1700 template <typename U> |
| 1701 void Vector<T, inlineCapacity, Allocator>::Append(const U* data, | 1701 void Vector<T, inlineCapacity, Allocator>::Append(const U* data, |
| 1702 size_t data_size) { | 1702 size_t data_size) { |
| 1703 DCHECK(Allocator::IsAllocationAllowed()); | 1703 DCHECK(Allocator::IsAllocationAllowed()); |
| 1704 size_t new_size = size_ + data_size; | 1704 size_t new_size = size_ + data_size; |
| 1705 if (new_size > capacity()) { | 1705 if (new_size > capacity()) { |
| 1706 data = ExpandCapacity(new_size, data); | 1706 data = ExpandCapacity(new_size, data); |
| 1707 DCHECK(begin()); | 1707 DCHECK(begin()); |
| 1708 } | 1708 } |
| 1709 RELEASE_ASSERT(new_size >= size_); | 1709 CHECK_GE(new_size, size_); |
| 1710 T* dest = end(); | 1710 T* dest = end(); |
| 1711 ANNOTATE_CHANGE_SIZE(begin(), capacity(), size_, new_size); | 1711 ANNOTATE_CHANGE_SIZE(begin(), capacity(), size_, new_size); |
| 1712 VectorCopier<VectorTraits<T>::kCanCopyWithMemcpy, T>::UninitializedCopy( | 1712 VectorCopier<VectorTraits<T>::kCanCopyWithMemcpy, T>::UninitializedCopy( |
| 1713 data, &data[data_size], dest); | 1713 data, &data[data_size], dest); |
| 1714 size_ = new_size; | 1714 size_ = new_size; |
| 1715 } | 1715 } |
| 1716 | 1716 |
| 1717 template <typename T, size_t inlineCapacity, typename Allocator> | 1717 template <typename T, size_t inlineCapacity, typename Allocator> |
| 1718 template <typename U> | 1718 template <typename U> |
| 1719 NEVER_INLINE void Vector<T, inlineCapacity, Allocator>::AppendSlowCase( | 1719 NEVER_INLINE void Vector<T, inlineCapacity, Allocator>::AppendSlowCase( |
| (...skipping 39 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1759 new (NotNull, end()) T(std::forward<U>(val)); | 1759 new (NotNull, end()) T(std::forward<U>(val)); |
| 1760 ++size_; | 1760 ++size_; |
| 1761 #endif | 1761 #endif |
| 1762 } | 1762 } |
| 1763 | 1763 |
| 1764 template <typename T, size_t inlineCapacity, typename Allocator> | 1764 template <typename T, size_t inlineCapacity, typename Allocator> |
| 1765 template <typename U> | 1765 template <typename U> |
| 1766 inline void Vector<T, inlineCapacity, Allocator>::insert(size_t position, | 1766 inline void Vector<T, inlineCapacity, Allocator>::insert(size_t position, |
| 1767 U&& val) { | 1767 U&& val) { |
| 1768 DCHECK(Allocator::IsAllocationAllowed()); | 1768 DCHECK(Allocator::IsAllocationAllowed()); |
| 1769 RELEASE_ASSERT(position <= size()); | 1769 CHECK_LE(position, size()); |
| 1770 typename std::remove_reference<U>::type* data = &val; | 1770 typename std::remove_reference<U>::type* data = &val; |
| 1771 if (size() == capacity()) { | 1771 if (size() == capacity()) { |
| 1772 data = ExpandCapacity(size() + 1, data); | 1772 data = ExpandCapacity(size() + 1, data); |
| 1773 DCHECK(begin()); | 1773 DCHECK(begin()); |
| 1774 } | 1774 } |
| 1775 ANNOTATE_CHANGE_SIZE(begin(), capacity(), size_, size_ + 1); | 1775 ANNOTATE_CHANGE_SIZE(begin(), capacity(), size_, size_ + 1); |
| 1776 T* spot = begin() + position; | 1776 T* spot = begin() + position; |
| 1777 TypeOperations::MoveOverlapping(spot, end(), spot + 1); | 1777 TypeOperations::MoveOverlapping(spot, end(), spot + 1); |
| 1778 new (NotNull, spot) T(std::forward<U>(*data)); | 1778 new (NotNull, spot) T(std::forward<U>(*data)); |
| 1779 ++size_; | 1779 ++size_; |
| 1780 } | 1780 } |
| 1781 | 1781 |
| 1782 template <typename T, size_t inlineCapacity, typename Allocator> | 1782 template <typename T, size_t inlineCapacity, typename Allocator> |
| 1783 template <typename U> | 1783 template <typename U> |
| 1784 void Vector<T, inlineCapacity, Allocator>::insert(size_t position, | 1784 void Vector<T, inlineCapacity, Allocator>::insert(size_t position, |
| 1785 const U* data, | 1785 const U* data, |
| 1786 size_t data_size) { | 1786 size_t data_size) { |
| 1787 DCHECK(Allocator::IsAllocationAllowed()); | 1787 DCHECK(Allocator::IsAllocationAllowed()); |
| 1788 RELEASE_ASSERT(position <= size()); | 1788 CHECK_LE(position, size()); |
| 1789 size_t new_size = size_ + data_size; | 1789 size_t new_size = size_ + data_size; |
| 1790 if (new_size > capacity()) { | 1790 if (new_size > capacity()) { |
| 1791 data = ExpandCapacity(new_size, data); | 1791 data = ExpandCapacity(new_size, data); |
| 1792 DCHECK(begin()); | 1792 DCHECK(begin()); |
| 1793 } | 1793 } |
| 1794 RELEASE_ASSERT(new_size >= size_); | 1794 CHECK_GE(new_size, size_); |
| 1795 ANNOTATE_CHANGE_SIZE(begin(), capacity(), size_, new_size); | 1795 ANNOTATE_CHANGE_SIZE(begin(), capacity(), size_, new_size); |
| 1796 T* spot = begin() + position; | 1796 T* spot = begin() + position; |
| 1797 TypeOperations::MoveOverlapping(spot, end(), spot + data_size); | 1797 TypeOperations::MoveOverlapping(spot, end(), spot + data_size); |
| 1798 VectorCopier<VectorTraits<T>::kCanCopyWithMemcpy, T>::UninitializedCopy( | 1798 VectorCopier<VectorTraits<T>::kCanCopyWithMemcpy, T>::UninitializedCopy( |
| 1799 data, &data[data_size], spot); | 1799 data, &data[data_size], spot); |
| 1800 size_ = new_size; | 1800 size_ = new_size; |
| 1801 } | 1801 } |
| 1802 | 1802 |
| 1803 template <typename T, size_t inlineCapacity, typename Allocator> | 1803 template <typename T, size_t inlineCapacity, typename Allocator> |
| 1804 template <typename U, size_t otherCapacity, typename OtherAllocator> | 1804 template <typename U, size_t otherCapacity, typename OtherAllocator> |
| (...skipping 18 matching lines...) Expand all Loading... |
| 1823 | 1823 |
| 1824 template <typename T, size_t inlineCapacity, typename Allocator> | 1824 template <typename T, size_t inlineCapacity, typename Allocator> |
| 1825 template <typename U, size_t otherCapacity, typename OtherAllocator> | 1825 template <typename U, size_t otherCapacity, typename OtherAllocator> |
| 1826 inline void Vector<T, inlineCapacity, Allocator>::PrependVector( | 1826 inline void Vector<T, inlineCapacity, Allocator>::PrependVector( |
| 1827 const Vector<U, otherCapacity, OtherAllocator>& val) { | 1827 const Vector<U, otherCapacity, OtherAllocator>& val) { |
| 1828 insert(0, val.begin(), val.size()); | 1828 insert(0, val.begin(), val.size()); |
| 1829 } | 1829 } |
| 1830 | 1830 |
| 1831 template <typename T, size_t inlineCapacity, typename Allocator> | 1831 template <typename T, size_t inlineCapacity, typename Allocator> |
| 1832 inline void Vector<T, inlineCapacity, Allocator>::erase(size_t position) { | 1832 inline void Vector<T, inlineCapacity, Allocator>::erase(size_t position) { |
| 1833 RELEASE_ASSERT(position < size()); | 1833 CHECK_LT(position, size()); |
| 1834 T* spot = begin() + position; | 1834 T* spot = begin() + position; |
| 1835 spot->~T(); | 1835 spot->~T(); |
| 1836 TypeOperations::MoveOverlapping(spot + 1, end(), spot); | 1836 TypeOperations::MoveOverlapping(spot + 1, end(), spot); |
| 1837 ClearUnusedSlots(end() - 1, end()); | 1837 ClearUnusedSlots(end() - 1, end()); |
| 1838 ANNOTATE_CHANGE_SIZE(begin(), capacity(), size_, size_ - 1); | 1838 ANNOTATE_CHANGE_SIZE(begin(), capacity(), size_, size_ - 1); |
| 1839 --size_; | 1839 --size_; |
| 1840 } | 1840 } |
| 1841 | 1841 |
| 1842 template <typename T, size_t inlineCapacity, typename Allocator> | 1842 template <typename T, size_t inlineCapacity, typename Allocator> |
| 1843 inline void Vector<T, inlineCapacity, Allocator>::erase(size_t position, | 1843 inline void Vector<T, inlineCapacity, Allocator>::erase(size_t position, |
| 1844 size_t length) { | 1844 size_t length) { |
| 1845 SECURITY_DCHECK(position <= size()); | 1845 SECURITY_DCHECK(position <= size()); |
| 1846 if (!length) | 1846 if (!length) |
| 1847 return; | 1847 return; |
| 1848 RELEASE_ASSERT(position + length <= size()); | 1848 CHECK_LE(position + length, size()); |
| 1849 T* begin_spot = begin() + position; | 1849 T* begin_spot = begin() + position; |
| 1850 T* end_spot = begin_spot + length; | 1850 T* end_spot = begin_spot + length; |
| 1851 TypeOperations::Destruct(begin_spot, end_spot); | 1851 TypeOperations::Destruct(begin_spot, end_spot); |
| 1852 TypeOperations::MoveOverlapping(end_spot, end(), begin_spot); | 1852 TypeOperations::MoveOverlapping(end_spot, end(), begin_spot); |
| 1853 ClearUnusedSlots(end() - length, end()); | 1853 ClearUnusedSlots(end() - length, end()); |
| 1854 ANNOTATE_CHANGE_SIZE(begin(), capacity(), size_, size_ - length); | 1854 ANNOTATE_CHANGE_SIZE(begin(), capacity(), size_, size_ - length); |
| 1855 size_ -= length; | 1855 size_ -= length; |
| 1856 } | 1856 } |
| 1857 | 1857 |
| 1858 template <typename T, size_t inlineCapacity, typename Allocator> | 1858 template <typename T, size_t inlineCapacity, typename Allocator> |
| (...skipping 58 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1917 visitor, *const_cast<T*>(buffer_entry)); | 1917 visitor, *const_cast<T*>(buffer_entry)); |
| 1918 CheckUnusedSlots(Buffer() + size(), Buffer() + capacity()); | 1918 CheckUnusedSlots(Buffer() + size(), Buffer() + capacity()); |
| 1919 } | 1919 } |
| 1920 } | 1920 } |
| 1921 | 1921 |
| 1922 } // namespace WTF | 1922 } // namespace WTF |
| 1923 | 1923 |
| 1924 using WTF::Vector; | 1924 using WTF::Vector; |
| 1925 | 1925 |
| 1926 #endif // WTF_Vector_h | 1926 #endif // WTF_Vector_h |
| OLD | NEW |