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 |