15c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/* 25c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Copyright (C) 2005, 2006, 2007, 2008 Apple Inc. All rights reserved. 35c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 45c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * This library is free software; you can redistribute it and/or 55c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * modify it under the terms of the GNU Library General Public 65c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * License as published by the Free Software Foundation; either 75c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * version 2 of the License, or (at your option) any later version. 85c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 95c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * This library is distributed in the hope that it will be useful, 105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * but WITHOUT ANY WARRANTY; without even the implied warranty of 115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Library General Public License for more details. 135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * You should have received a copy of the GNU Library General Public License 155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * along with this library; see the file COPYING.LIB. If not, write to 165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, 175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Boston, MA 02110-1301, USA. 185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#ifndef WTF_Vector_h 225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#define WTF_Vector_h 235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 24591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch#include "wtf/Alignment.h" 2509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)#include "wtf/DefaultAllocator.h" 26591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch#include "wtf/FastAllocBase.h" 27591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch#include "wtf/Noncopyable.h" 28591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch#include "wtf/NotFound.h" 29591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch#include "wtf/StdLibExtras.h" 30591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch#include "wtf/VectorTraits.h" 31bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles)#include "wtf/WTF.h" 3253e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles)#include <string.h> 339bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles)#include <utility> 345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)namespace WTF { 365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 37197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch#if defined(MEMORY_SANITIZER_INITIAL_SIZE) 383c9e4aeaee9f9b0a9a814da07bcb33319c7ea363Ben Murdochstatic const size_t kInitialVectorSize = 1; 393c9e4aeaee9f9b0a9a814da07bcb33319c7ea363Ben Murdoch#else 408abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles)#ifndef WTF_VECTOR_INITIAL_SIZE 418abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles)#define WTF_VECTOR_INITIAL_SIZE 4 428abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles)#endif 438abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles)static const size_t kInitialVectorSize = WTF_VECTOR_INITIAL_SIZE; 443c9e4aeaee9f9b0a9a814da07bcb33319c7ea363Ben Murdoch#endif 453c9e4aeaee9f9b0a9a814da07bcb33319c7ea363Ben Murdoch 46f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles) template<typename T, size_t inlineBuffer, typename Allocator> 47f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles) class Deque; 48f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles) 495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template <bool needsDestruction, typename T> 505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) struct VectorDestructor; 515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T> 535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) struct VectorDestructor<false, T> 545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static void destruct(T*, T*) {} 565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) }; 575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T> 595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) struct VectorDestructor<true, T> 605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 6102772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch static void destruct(T* begin, T* end) 625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (T* cur = begin; cur != end; ++cur) 645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) cur->~T(); 655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) }; 675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 6809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template <bool unusedSlotsMustBeZeroed, typename T> 6909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) struct VectorUnusedSlotClearer; 7009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 7109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T> 7209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) struct VectorUnusedSlotClearer<false, T> { 7309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) static void clear(T*, T*) { } 7409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) }; 7509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 7609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T> 7709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) struct VectorUnusedSlotClearer<true, T> { 7809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) static void clear(T* begin, T* end) 7909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) { 8009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // We clear out unused slots so that the visitor and the finalizer 8109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // do not visit them (or at least it does not matter if they do). 8209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) memset(begin, 0, sizeof(T) * (end - begin)); 8309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) } 8409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) }; 8509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 86d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles) template <bool canInitializeWithMemset, typename T> 875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) struct VectorInitializer; 885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T> 90d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles) struct VectorInitializer<false, T> 915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 9202772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch static void initialize(T* begin, T* end) 935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (T* cur = begin; cur != end; ++cur) 955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) new (NotNull, cur) T; 965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) }; 985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T> 100d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles) struct VectorInitializer<true, T> 1015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 10202772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch static void initialize(T* begin, T* end) 1035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 1045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) memset(begin, 0, reinterpret_cast<char*>(end) - reinterpret_cast<char*>(begin)); 1055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) }; 1075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template <bool canMoveWithMemcpy, typename T> 1095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) struct VectorMover; 1105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T> 1125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) struct VectorMover<false, T> 1135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 1145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static void move(const T* src, const T* srcEnd, T* dst) 1155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 1165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while (src != srcEnd) { 1175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) new (NotNull, dst) T(*src); 1185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) src->~T(); 1195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ++dst; 1205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ++src; 1215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static void moveOverlapping(const T* src, const T* srcEnd, T* dst) 1245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 1255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (src > dst) 1265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) move(src, srcEnd, dst); 1275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) else { 1285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) T* dstEnd = dst + (srcEnd - src); 1295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while (src != srcEnd) { 1305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) --srcEnd; 1315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) --dstEnd; 1325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) new (NotNull, dstEnd) T(*srcEnd); 1335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) srcEnd->~T(); 1345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 137d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) static void swap(T* src, T* srcEnd, T* dst) 138d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) { 139d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) std::swap_ranges(src, srcEnd, dst); 140d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) } 1415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) }; 1425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T> 1445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) struct VectorMover<true, T> 1455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 14602772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch static void move(const T* src, const T* srcEnd, T* dst) 1475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 1485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) memcpy(dst, src, reinterpret_cast<const char*>(srcEnd) - reinterpret_cast<const char*>(src)); 1495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 15002772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch static void moveOverlapping(const T* src, const T* srcEnd, T* dst) 1515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 1525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) memmove(dst, src, reinterpret_cast<const char*>(srcEnd) - reinterpret_cast<const char*>(src)); 1535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 154d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) static void swap(T* src, T* srcEnd, T* dst) 155d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) { 15607a852d8c1953036774d8f3b65d18dcfea3bb4a2Ben Murdoch std::swap_ranges(reinterpret_cast<char*>(src), reinterpret_cast<char*>(srcEnd), reinterpret_cast<char*>(dst)); 157d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) } 1585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) }; 1595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template <bool canCopyWithMemcpy, typename T> 1615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) struct VectorCopier; 1625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T> 1645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) struct VectorCopier<false, T> 1655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 166d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) template<typename U> 167d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) static void uninitializedCopy(const U* src, const U* srcEnd, T* dst) 1685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 1695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while (src != srcEnd) { 1705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) new (NotNull, dst) T(*src); 1715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ++dst; 1725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ++src; 1735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) }; 1765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T> 1785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) struct VectorCopier<true, T> 1795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 18002772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch static void uninitializedCopy(const T* src, const T* srcEnd, T* dst) 1815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 1825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) memcpy(dst, src, reinterpret_cast<const char*>(srcEnd) - reinterpret_cast<const char*>(src)); 1835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 184d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) template<typename U> 185d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) static void uninitializedCopy(const U* src, const U* srcEnd, T* dst) 186d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) { 187d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) VectorCopier<false, T>::uninitializedCopy(src, srcEnd, dst); 188d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) } 1895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) }; 1905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template <bool canFillWithMemset, typename T> 1925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) struct VectorFiller; 1935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T> 1955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) struct VectorFiller<false, T> 1965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 19702772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch static void uninitializedFill(T* dst, T* dstEnd, const T& val) 1985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 1995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while (dst != dstEnd) { 2005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) new (NotNull, dst) T(val); 2015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ++dst; 2025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) }; 2055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T> 2075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) struct VectorFiller<true, T> 2085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 20902772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch static void uninitializedFill(T* dst, T* dstEnd, const T& val) 2105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 2118abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles) COMPILE_ASSERT(sizeof(T) == sizeof(char), Size_of_type_should_be_equal_to_one); 2125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#if COMPILER(GCC) && defined(_FORTIFY_SOURCE) 2135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!__builtin_constant_p(dstEnd - dst) || (!(dstEnd - dst))) 2145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 2155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) memset(dst, val, dstEnd - dst); 2165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) }; 21802772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 2195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<bool canCompareWithMemcmp, typename T> 2205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) struct VectorComparer; 22102772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 2225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T> 2235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) struct VectorComparer<false, T> 2245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 2255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static bool compare(const T* a, const T* b, size_t size) 2265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 2275d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles) if (LIKELY(a && b)) 2285d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles) return std::equal(a, a + size, b); 2295d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles) return !a && !b; 2305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) }; 2325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T> 2345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) struct VectorComparer<true, T> 2355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 2365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static bool compare(const T* a, const T* b, size_t size) 2375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 2385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return memcmp(a, b, sizeof(T) * size) == 0; 2395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) }; 24102772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 2425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T> 2435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) struct VectorTypeOperations 2445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 2455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static void destruct(T* begin, T* end) 2465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 2475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) VectorDestructor<VectorTraits<T>::needsDestruction, T>::destruct(begin, end); 2485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static void initialize(T* begin, T* end) 2515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 252d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles) VectorInitializer<VectorTraits<T>::canInitializeWithMemset, T>::initialize(begin, end); 2535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static void move(const T* src, const T* srcEnd, T* dst) 2565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 2575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) VectorMover<VectorTraits<T>::canMoveWithMemcpy, T>::move(src, srcEnd, dst); 2585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static void moveOverlapping(const T* src, const T* srcEnd, T* dst) 2615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 2625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) VectorMover<VectorTraits<T>::canMoveWithMemcpy, T>::moveOverlapping(src, srcEnd, dst); 2635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 265d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) static void swap(T* src, T* srcEnd, T* dst) 266d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) { 267d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) VectorMover<VectorTraits<T>::canMoveWithMemcpy, T>::swap(src, srcEnd, dst); 268d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) } 269d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) 2705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static void uninitializedCopy(const T* src, const T* srcEnd, T* dst) 2715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 2725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) VectorCopier<VectorTraits<T>::canCopyWithMemcpy, T>::uninitializedCopy(src, srcEnd, dst); 2735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static void uninitializedFill(T* dst, T* dstEnd, const T& val) 2765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 2775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) VectorFiller<VectorTraits<T>::canFillWithMemset, T>::uninitializedFill(dst, dstEnd, val); 2785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 27902772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 2805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static bool compare(const T* a, const T* b, size_t size) 2815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 2825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return VectorComparer<VectorTraits<T>::canCompareWithMemcmp, T>::compare(a, b, size); 2835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) }; 2855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 28609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, typename Allocator> 2875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) class VectorBufferBase { 2885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) WTF_MAKE_NONCOPYABLE(VectorBufferBase); 2895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) public: 2905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void allocateBuffer(size_t newCapacity) 2915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 29209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) typedef typename Allocator::template VectorBackingHelper<T, VectorTraits<T> >::Type VectorBacking; 2935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(newCapacity); 2949bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) size_t sizeToAllocate = allocationSize(newCapacity); 29509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) m_buffer = Allocator::template backingMalloc<T*, VectorBacking>(sizeToAllocate); 296926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) m_capacity = sizeToAllocate / sizeof(T); 2975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2999bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) size_t allocationSize(size_t capacity) const 3005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 30109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) return Allocator::Quantizer::template quantizedSize<T>(capacity); 3025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) T* buffer() { return m_buffer; } 3055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const T* buffer() const { return m_buffer; } 3065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) size_t capacity() const { return m_capacity; } 3075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 308a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch void clearUnusedSlots(T* from, T* to) 309a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch { 3105d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles) VectorUnusedSlotClearer<Allocator::isGarbageCollected && (VectorTraits<T>::needsDestruction || ShouldBeTraced<VectorTraits<T> >::value), T>::clear(from, to); 311a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch } 312a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch 3135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) protected: 3145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) VectorBufferBase() 3155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) : m_buffer(0) 3165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) , m_capacity(0) 3175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 3185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) VectorBufferBase(T* buffer, size_t capacity) 3215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) : m_buffer(buffer) 3225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) , m_capacity(capacity) 3235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 3245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) T* m_buffer; 327f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles) unsigned m_capacity; 328f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles) unsigned m_size; 3295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) }; 3305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 33109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename Allocator = DefaultAllocator> 3325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) class VectorBuffer; 3335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 33409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, typename Allocator> 335a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch class VectorBuffer<T, 0, Allocator> : protected VectorBufferBase<T, Allocator> { 3365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) private: 33709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) typedef VectorBufferBase<T, Allocator> Base; 3385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) public: 3395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) VectorBuffer() 3405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 3415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) VectorBuffer(size_t capacity) 3445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 3455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Calling malloc(0) might take a lock and may actually do an 3465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // allocation on some systems. 3475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (capacity) 3485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) allocateBuffer(capacity); 3495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3519bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) void destruct() 3529bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) { 3539bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) deallocateBuffer(m_buffer); 3548abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles) m_buffer = 0; 3555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 35602772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 3579bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) void deallocateBuffer(T* bufferToDeallocate) 3589bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) { 35909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) Allocator::backingFree(bufferToDeallocate); 3609bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) } 3619bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) 3629bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) void resetBufferPointer() 3639bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) { 3649bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) m_buffer = 0; 3659bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) m_capacity = 0; 3669bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) } 3679bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) 36809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) void swapVectorBuffer(VectorBuffer<T, 0, Allocator>& other) 3695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 3705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) std::swap(m_buffer, other.m_buffer); 3715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) std::swap(m_capacity, other.m_capacity); 3725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 37302772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 3745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) using Base::allocateBuffer; 3759bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) using Base::allocationSize; 3765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) using Base::buffer; 3785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) using Base::capacity; 3795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 380a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch using Base::clearUnusedSlots; 381f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles) 38209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) bool hasOutOfLineBuffer() const 38309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) { 38409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // When inlineCapacity is 0 we have an out of line buffer if we have a buffer. 38509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) return buffer(); 38609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) } 38709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 388a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch protected: 389a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch using Base::m_size; 390a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch 3915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) private: 3925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) using Base::m_buffer; 3935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) using Base::m_capacity; 3945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) }; 3955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 39609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename Allocator> 397a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch class VectorBuffer : protected VectorBufferBase<T, Allocator> { 3985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) WTF_MAKE_NONCOPYABLE(VectorBuffer); 3995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) private: 40009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) typedef VectorBufferBase<T, Allocator> Base; 4015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) public: 4025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) VectorBuffer() 4035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) : Base(inlineBuffer(), inlineCapacity) 4045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 4055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 4065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) VectorBuffer(size_t capacity) 4085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) : Base(inlineBuffer(), inlineCapacity) 4095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 4105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (capacity > inlineCapacity) 4115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Base::allocateBuffer(capacity); 4125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 4135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4149bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) void destruct() 4155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 4169bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) deallocateBuffer(m_buffer); 4179bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) m_buffer = 0; 4185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 4195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 42009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) NEVER_INLINE void reallyDeallocateBuffer(T* bufferToDeallocate) 42109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) { 42209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) Allocator::backingFree(bufferToDeallocate); 42309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) } 42409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 4255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void deallocateBuffer(T* bufferToDeallocate) 4265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 42709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) if (UNLIKELY(bufferToDeallocate != inlineBuffer())) 42809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) reallyDeallocateBuffer(bufferToDeallocate); 4295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 4305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4319bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) void resetBufferPointer() 4325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 4339bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) m_buffer = inlineBuffer(); 4349bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) m_capacity = inlineCapacity; 4355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 4365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4379bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) void allocateBuffer(size_t newCapacity) 4385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 4399bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) // FIXME: This should ASSERT(!m_buffer) to catch misuse/leaks. 4409bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) if (newCapacity > inlineCapacity) 4419bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) Base::allocateBuffer(newCapacity); 4429bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) else 4439bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) resetBufferPointer(); 4449bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) } 4459bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) 4469bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) size_t allocationSize(size_t capacity) const 4479bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) { 4489bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) if (capacity <= inlineCapacity) 4499bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) return m_inlineBufferSize; 4509bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) return Base::allocationSize(capacity); 4515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 4525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 45309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) void swapVectorBuffer(VectorBuffer<T, inlineCapacity, Allocator>& other) 4545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 455d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) typedef VectorTypeOperations<T> TypeOperations; 456d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) 4575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (buffer() == inlineBuffer() && other.buffer() == other.inlineBuffer()) { 458d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) ASSERT(m_capacity == other.m_capacity); 459d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) if (m_size > other.m_size) { 460d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) TypeOperations::swap(inlineBuffer(), inlineBuffer() + other.m_size, other.inlineBuffer()); 461d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) TypeOperations::move(inlineBuffer() + other.m_size, inlineBuffer() + m_size, other.inlineBuffer() + other.m_size); 462d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) } else { 463d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) TypeOperations::swap(inlineBuffer(), inlineBuffer() + m_size, other.inlineBuffer()); 464d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) TypeOperations::move(other.inlineBuffer() + m_size, other.inlineBuffer() + other.m_size, inlineBuffer() + m_size); 465d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) } 4665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } else if (buffer() == inlineBuffer()) { 4675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_buffer = other.m_buffer; 4685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) other.m_buffer = other.inlineBuffer(); 469d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) TypeOperations::move(inlineBuffer(), inlineBuffer() + m_size, other.inlineBuffer()); 4705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) std::swap(m_capacity, other.m_capacity); 4715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } else if (other.buffer() == other.inlineBuffer()) { 4725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) other.m_buffer = m_buffer; 4735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_buffer = inlineBuffer(); 474d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) TypeOperations::move(other.inlineBuffer(), other.inlineBuffer() + other.m_size, inlineBuffer()); 4755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) std::swap(m_capacity, other.m_capacity); 4765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } else { 4775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) std::swap(m_buffer, other.m_buffer); 4785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) std::swap(m_capacity, other.m_capacity); 4795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 4805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 4815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) using Base::buffer; 4835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) using Base::capacity; 4845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 48509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) bool hasOutOfLineBuffer() const 48609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) { 48709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) return buffer() && buffer() != inlineBuffer(); 48809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) } 48909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 490a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch protected: 491a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch using Base::m_size; 492a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch 4935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) private: 4945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) using Base::m_buffer; 4955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) using Base::m_capacity; 4965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static const size_t m_inlineBufferSize = inlineCapacity * sizeof(T); 4985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) T* inlineBuffer() { return reinterpret_cast_ptr<T*>(m_inlineBuffer.buffer); } 4995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const T* inlineBuffer() const { return reinterpret_cast_ptr<const T*>(m_inlineBuffer.buffer); } 5005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) AlignedBuffer<m_inlineBufferSize, WTF_ALIGN_OF(T)> m_inlineBuffer; 502f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles) template<typename U, size_t inlineBuffer, typename V> 503f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles) friend class Deque; 5045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) }; 5055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 506d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename Allocator> 507d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) class Vector; 508d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) 509d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) // VectorDestructorBase defines the destructor of a vector. This base is used in order to 510d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) // completely avoid creating a destructor for a vector that does not need to be destructed. 511d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) // By doing so, the clang compiler will have correct information about whether or not a 512d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) // vector has a trivial destructor and we use that in a compiler plugin to ensure the 513d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) // correctness of non-finalized garbage-collected classes and the use of VectorTraits::needsDestruction. 514d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) 515a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch // All non-GC managed vectors need a destructor. This destructor will simply call finalize on the actual vector type. 516d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) template<typename Derived, typename Elements, bool hasInlineCapacity, bool isGarbageCollected> 517d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) class VectorDestructorBase { 518d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) public: 519d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) ~VectorDestructorBase() { static_cast<Derived*>(this)->finalize(); } 520d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) }; 521d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) 522d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) // Heap-allocated vectors with no inlineCapacity never need a destructor. 523d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) template<typename Derived, typename Elements> 524d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) class VectorDestructorBase<Derived, Elements, false, true> { }; 525d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) 526d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) // Heap-allocator vectors with inlineCapacity need a destructor if the inline elements do. 527d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) // The use of VectorTraits<Elements>::needsDestruction is delayed until we know that 528d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) // inlineCapacity is non-zero to allow classes that recursively refer to themselves in vector 529d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) // members. If inlineCapacity is non-zero doing so would have undefined meaning, so in this 530d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) // case we can use HeapVectorWithInlineCapacityDestructorBase to define a destructor 531d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) // depending on the value of VectorTraits<Elements>::needsDestruction. 532d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) template<typename Derived, bool elementsNeedsDestruction> 533d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) class HeapVectorWithInlineCapacityDestructorBase; 534d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) 535d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) template<typename Derived> 536d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) class HeapVectorWithInlineCapacityDestructorBase<Derived, true> { 537d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) public: 538d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) ~HeapVectorWithInlineCapacityDestructorBase() { static_cast<Derived*>(this)->finalize(); } 539d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) }; 540d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) 541d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) template<typename Derived> 542d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) class HeapVectorWithInlineCapacityDestructorBase<Derived, false> { }; 543d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) 544d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) template<typename Derived, typename Elements> 545d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) class VectorDestructorBase<Derived, Elements, true, true> : public HeapVectorWithInlineCapacityDestructorBase<Derived, VectorTraits<Elements>::needsDestruction> { }; 546d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) 54709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, size_t inlineCapacity = 0, typename Allocator = DefaultAllocator> 548d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) class Vector : private VectorBuffer<T, inlineCapacity, Allocator>, public VectorDestructorBase<Vector<T, inlineCapacity, Allocator>, T, (inlineCapacity > 0), Allocator::isGarbageCollected> { 549f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu WTF_USE_ALLOCATOR(Vector, Allocator); 5505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) private: 55109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) typedef VectorBuffer<T, inlineCapacity, Allocator> Base; 5525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef VectorTypeOperations<T> TypeOperations; 5535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) public: 5555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef T ValueType; 5565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef T* iterator; 5585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef const T* const_iterator; 5595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef std::reverse_iterator<iterator> reverse_iterator; 5605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 5615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 56202772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch Vector() 5635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 564aafa69cb17c9d6606c07663ade5f81388a2c5986Ben Murdoch // Unused slots are initialized to zero so that the visitor and the 565aafa69cb17c9d6606c07663ade5f81388a2c5986Ben Murdoch // finalizer can visit them safely. canInitializeWithMemset tells us 566aafa69cb17c9d6606c07663ade5f81388a2c5986Ben Murdoch // that the class does not expect matching constructor and 567aafa69cb17c9d6606c07663ade5f81388a2c5986Ben Murdoch // destructor calls as long as the memory is zeroed. 568aafa69cb17c9d6606c07663ade5f81388a2c5986Ben Murdoch COMPILE_ASSERT(!Allocator::isGarbageCollected || !VectorTraits<T>::needsDestruction || VectorTraits<T>::canInitializeWithMemset, ClassHasProblemsWithFinalizersCalledOnClearedMemory); 569d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles) COMPILE_ASSERT(!WTF::IsPolymorphic<T>::value || !VectorTraits<T>::canInitializeWithMemset, CantInitializeWithMemsetIfThereIsAVtable); 570f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles) m_size = 0; 5715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 57202772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 57302772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch explicit Vector(size_t size) 57453e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) : Base(size) 5755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 576aafa69cb17c9d6606c07663ade5f81388a2c5986Ben Murdoch // Unused slots are initialized to zero so that the visitor and the 577aafa69cb17c9d6606c07663ade5f81388a2c5986Ben Murdoch // finalizer can visit them safely. canInitializeWithMemset tells us 578aafa69cb17c9d6606c07663ade5f81388a2c5986Ben Murdoch // that the class does not expect matching constructor and 579aafa69cb17c9d6606c07663ade5f81388a2c5986Ben Murdoch // destructor calls as long as the memory is zeroed. 580aafa69cb17c9d6606c07663ade5f81388a2c5986Ben Murdoch COMPILE_ASSERT(!Allocator::isGarbageCollected || !VectorTraits<T>::needsDestruction || VectorTraits<T>::canInitializeWithMemset, ClassHasProblemsWithFinalizersCalledOnClearedMemory); 581f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles) m_size = size; 5828abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles) TypeOperations::initialize(begin(), end()); 5835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 5845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 58509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // Off-GC-heap vectors: Destructor should be called. 58609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // On-GC-heap vectors: Destructor should be called for inline buffers 58709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // (if any) but destructor shouldn't be called for vector backing since 58809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // it is managed by the traced GC heap. 589d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) void finalize() 5905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 5919bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) if (!inlineCapacity) { 5929bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) if (LIKELY(!Base::buffer())) 5939bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) return; 5949bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) } 59509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) if (LIKELY(m_size) && !(Allocator::isGarbageCollected && this->hasOutOfLineBuffer())) { 59609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) TypeOperations::destruct(begin(), end()); 59709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) m_size = 0; // Partial protection against use-after-free. 59809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) } 5999bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) 6009bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) Base::destruct(); 6015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 6025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 60343e7502580f146aa5b3db8267ba6dbb5c733a489Torne (Richard Coles) void finalizeGarbageCollectedObject() 60443e7502580f146aa5b3db8267ba6dbb5c733a489Torne (Richard Coles) { 60543e7502580f146aa5b3db8267ba6dbb5c733a489Torne (Richard Coles) finalize(); 60643e7502580f146aa5b3db8267ba6dbb5c733a489Torne (Richard Coles) } 60743e7502580f146aa5b3db8267ba6dbb5c733a489Torne (Richard Coles) 6085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Vector(const Vector&); 60902772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch template<size_t otherCapacity> 61009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) explicit Vector(const Vector<T, otherCapacity, Allocator>&); 6115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 6125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Vector& operator=(const Vector&); 61302772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch template<size_t otherCapacity> 61409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) Vector& operator=(const Vector<T, otherCapacity, Allocator>&); 6155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 6165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#if COMPILER_SUPPORTS(CXX_RVALUE_REFERENCES) 6175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Vector(Vector&&); 6185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Vector& operator=(Vector&&); 6195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 6205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 6215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) size_t size() const { return m_size; } 62253e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) size_t capacity() const { return Base::capacity(); } 6235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool isEmpty() const { return !size(); } 6245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 62502772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch T& at(size_t i) 62602772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch { 62753e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) RELEASE_ASSERT(i < size()); 62853e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) return Base::buffer()[i]; 6295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 63002772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch const T& at(size_t i) const 6315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 63253e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) RELEASE_ASSERT(i < size()); 63353e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) return Base::buffer()[i]; 6345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 6355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 6365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) T& operator[](size_t i) { return at(i); } 6375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const T& operator[](size_t i) const { return at(i); } 6385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 63953e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) T* data() { return Base::buffer(); } 64053e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) const T* data() const { return Base::buffer(); } 6415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 6425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) iterator begin() { return data(); } 6435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) iterator end() { return begin() + m_size; } 6445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const_iterator begin() const { return data(); } 6455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const_iterator end() const { return begin() + m_size; } 6465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 6475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) reverse_iterator rbegin() { return reverse_iterator(end()); } 6485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) reverse_iterator rend() { return reverse_iterator(begin()); } 6495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); } 6505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const_reverse_iterator rend() const { return const_reverse_iterator(begin()); } 6515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 6525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) T& first() { return at(0); } 6535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const T& first() const { return at(0); } 6545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) T& last() { return at(size() - 1); } 6555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const T& last() const { return at(size() - 1); } 6565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 6575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename U> bool contains(const U&) const; 6585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename U> size_t find(const U&) const; 6595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename U> size_t reverseFind(const U&) const; 6605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 6615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void shrink(size_t size); 6625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void grow(size_t size); 6635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void resize(size_t size); 6645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void reserveCapacity(size_t newCapacity); 6655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void reserveInitialCapacity(size_t initialCapacity); 6665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void shrinkToFit() { shrinkCapacity(size()); } 667323480423219ecd77329f8326dc5e0e3b50926d4Torne (Richard Coles) void shrinkToReasonableCapacity() 668323480423219ecd77329f8326dc5e0e3b50926d4Torne (Richard Coles) { 669323480423219ecd77329f8326dc5e0e3b50926d4Torne (Richard Coles) if (size() * 2 < capacity()) 670323480423219ecd77329f8326dc5e0e3b50926d4Torne (Richard Coles) shrinkCapacity(size() + size() / 4 + 1); 671323480423219ecd77329f8326dc5e0e3b50926d4Torne (Richard Coles) } 6725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 6735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void clear() { shrinkCapacity(0); } 6745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 6755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename U> void append(const U*, size_t); 6765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename U> void append(const U&); 6775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename U> void uncheckedAppend(const U& val); 67809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename U, size_t otherCapacity, typename V> void appendVector(const Vector<U, otherCapacity, V>&); 6795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 6805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename U> void insert(size_t position, const U*, size_t); 6815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename U> void insert(size_t position, const U&); 68209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename U, size_t c, typename V> void insert(size_t position, const Vector<U, c, V>&); 6835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 6845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename U> void prepend(const U*, size_t); 6855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename U> void prepend(const U&); 68609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename U, size_t c, typename V> void prepend(const Vector<U, c, V>&); 6875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 6885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void remove(size_t position); 6895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void remove(size_t position, size_t length); 6905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 69102772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch void removeLast() 6925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 6935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(!isEmpty()); 69402772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch shrink(size() - 1); 6955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 6965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 6975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Vector(size_t size, const T& val) 69853e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) : Base(size) 6995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 700f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles) m_size = size; 7018abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles) TypeOperations::uninitializedFill(begin(), end(), val); 7025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 7035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void fill(const T&, size_t); 7055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void fill(const T& val) { fill(val, size()); } 7065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename Iterator> void appendRange(Iterator start, Iterator end); 7085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 70909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) void swap(Vector& other) 7105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 71109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) Base::swapVectorBuffer(other); 712d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) std::swap(m_size, other.m_size); 7135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 7145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void reverse(); 7165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 71709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) void trace(typename Allocator::Visitor*); 71809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 7195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) private: 7205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void expandCapacity(size_t newMinCapacity); 7215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const T* expandCapacity(size_t newMinCapacity, const T*); 72202772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch template<typename U> U* expandCapacity(size_t newMinCapacity, U*); 7239bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) void shrinkCapacity(size_t newCapacity); 7245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename U> void appendSlowCase(const U&); 7255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 726f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles) using Base::m_size; 72753e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) using Base::buffer; 72853e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) using Base::capacity; 72909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) using Base::swapVectorBuffer; 73053e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) using Base::allocateBuffer; 7319bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) using Base::allocationSize; 732a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch using Base::clearUnusedSlots; 7335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) }; 7345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 73509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename Allocator> 73609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) Vector<T, inlineCapacity, Allocator>::Vector(const Vector& other) 73753e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) : Base(other.capacity()) 7385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 739f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles) m_size = other.size(); 7408abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles) TypeOperations::uninitializedCopy(other.begin(), other.end(), begin()); 7415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 7425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 74309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename Allocator> 74402772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch template<size_t otherCapacity> 74509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) Vector<T, inlineCapacity, Allocator>::Vector(const Vector<T, otherCapacity, Allocator>& other) 74653e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) : Base(other.capacity()) 7475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 748f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles) m_size = other.size(); 7498abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles) TypeOperations::uninitializedCopy(other.begin(), other.end(), begin()); 7505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 7515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 75209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename Allocator> 75309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) Vector<T, inlineCapacity, Allocator>& Vector<T, inlineCapacity, Allocator>::operator=(const Vector<T, inlineCapacity, Allocator>& other) 7545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 7558abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles) if (UNLIKELY(&other == this)) 7565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return *this; 75702772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 7585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (size() > other.size()) 7595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) shrink(other.size()); 7605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) else if (other.size() > capacity()) { 7615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) clear(); 7625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) reserveCapacity(other.size()); 7633c9e4aeaee9f9b0a9a814da07bcb33319c7ea363Ben Murdoch ASSERT(begin()); 7645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 76502772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 7665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) std::copy(other.begin(), other.begin() + size(), begin()); 7675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) TypeOperations::uninitializedCopy(other.begin() + size(), other.end(), end()); 7685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_size = other.size(); 7695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return *this; 7715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 7725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) inline bool typelessPointersAreEqual(const void* a, const void* b) { return a == b; } 7745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 77509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename Allocator> 77602772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch template<size_t otherCapacity> 77709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) Vector<T, inlineCapacity, Allocator>& Vector<T, inlineCapacity, Allocator>::operator=(const Vector<T, otherCapacity, Allocator>& other) 7785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 7795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // If the inline capacities match, we should call the more specific 7805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // template. If the inline capacities don't match, the two objects 7815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // shouldn't be allocated the same address. 7825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(!typelessPointersAreEqual(&other, this)); 7835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (size() > other.size()) 7855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) shrink(other.size()); 7865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) else if (other.size() > capacity()) { 7875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) clear(); 7885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) reserveCapacity(other.size()); 7893c9e4aeaee9f9b0a9a814da07bcb33319c7ea363Ben Murdoch ASSERT(begin()); 7905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 79102772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 7925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) std::copy(other.begin(), other.begin() + size(), begin()); 7935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) TypeOperations::uninitializedCopy(other.begin() + size(), other.end(), end()); 7945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_size = other.size(); 7955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return *this; 7975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 7985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#if COMPILER_SUPPORTS(CXX_RVALUE_REFERENCES) 80009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename Allocator> 80109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) Vector<T, inlineCapacity, Allocator>::Vector(Vector<T, inlineCapacity, Allocator>&& other) 8025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 803f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles) m_size = 0; 8045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // It's a little weird to implement a move constructor using swap but this way we 8055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // don't have to add a move constructor to VectorBuffer. 8065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) swap(other); 8075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 8085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 80909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename Allocator> 81009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) Vector<T, inlineCapacity, Allocator>& Vector<T, inlineCapacity, Allocator>::operator=(Vector<T, inlineCapacity, Allocator>&& other) 8115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 8125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) swap(other); 8135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return *this; 8145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 8155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 8165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 81709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename Allocator> 8185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename U> 81909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) bool Vector<T, inlineCapacity, Allocator>::contains(const U& value) const 8205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 82106f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles) return find(value) != kNotFound; 8225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 82302772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 82409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename Allocator> 8255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename U> 82609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) size_t Vector<T, inlineCapacity, Allocator>::find(const U& value) const 8275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 82853e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) const T* b = begin(); 82953e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) const T* e = end(); 83053e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) for (const T* iter = b; iter < e; ++iter) { 83153e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) if (*iter == value) 83253e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) return iter - b; 8335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 83406f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles) return kNotFound; 8355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 8365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 83709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename Allocator> 8385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename U> 83909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) size_t Vector<T, inlineCapacity, Allocator>::reverseFind(const U& value) const 8405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 84153e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) const T* b = begin(); 84253e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) const T* iter = end(); 84353e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) while (iter > b) { 84453e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) --iter; 84553e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) if (*iter == value) 84653e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) return iter - b; 8475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 84806f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles) return kNotFound; 8495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 8505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 85109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename Allocator> 85209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) void Vector<T, inlineCapacity, Allocator>::fill(const T& val, size_t newSize) 8535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 8545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (size() > newSize) 8555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) shrink(newSize); 8565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) else if (newSize > capacity()) { 8575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) clear(); 8585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) reserveCapacity(newSize); 8593c9e4aeaee9f9b0a9a814da07bcb33319c7ea363Ben Murdoch ASSERT(begin()); 8605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 86102772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 8625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) std::fill(begin(), end(), val); 8635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) TypeOperations::uninitializedFill(end(), begin() + newSize, val); 8645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_size = newSize; 8655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 8665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 86709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename Allocator> 8685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename Iterator> 86909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) void Vector<T, inlineCapacity, Allocator>::appendRange(Iterator start, Iterator end) 8705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 8715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (Iterator it = start; it != end; ++it) 8725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) append(*it); 8735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 8745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 87509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename Allocator> 87609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) void Vector<T, inlineCapacity, Allocator>::expandCapacity(size_t newMinCapacity) 8775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 8789bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) size_t oldCapacity = capacity(); 8799bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) size_t expandedCapacity = oldCapacity; 8809bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) // We use a more aggressive expansion strategy for Vectors with inline storage. 8819bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) // This is because they are more likely to be on the stack, so the risk of heap bloat is minimized. 8829bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) // Furthermore, exceeding the inline capacity limit is not supposed to happen in the common case and may indicate a pathological condition or microbenchmark. 8839bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) if (inlineCapacity) { 8849bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) expandedCapacity *= 2; 8859bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) // Check for integer overflow, which could happen in the 32-bit build. 8869bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) RELEASE_ASSERT(expandedCapacity > oldCapacity); 8879bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) } else { 8889bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) // This cannot integer overflow. 8899bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) // On 64-bit, the "expanded" integer is 32-bit, and any encroachment above 2^32 will fail allocation in allocateBuffer(). 8909bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) // On 32-bit, there's not enough address space to hold the old and new buffers. 8919bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) // In addition, our underlying allocator is supposed to always fail on > (2^31 - 1) allocations. 8929bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) expandedCapacity += (expandedCapacity / 4) + 1; 8939bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) } 8949bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) reserveCapacity(std::max(newMinCapacity, std::max(static_cast<size_t>(kInitialVectorSize), expandedCapacity))); 8955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 89602772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 89709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename Allocator> 89809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) const T* Vector<T, inlineCapacity, Allocator>::expandCapacity(size_t newMinCapacity, const T* ptr) 8995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 9005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (ptr < begin() || ptr >= end()) { 9015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) expandCapacity(newMinCapacity); 9025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return ptr; 9035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 9045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) size_t index = ptr - begin(); 9055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) expandCapacity(newMinCapacity); 9065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return begin() + index; 9075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 9085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 90909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename Allocator> template<typename U> 91009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) inline U* Vector<T, inlineCapacity, Allocator>::expandCapacity(size_t newMinCapacity, U* ptr) 9115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 9125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) expandCapacity(newMinCapacity); 9135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return ptr; 9145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 9155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 91609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename Allocator> 91709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) inline void Vector<T, inlineCapacity, Allocator>::resize(size_t size) 9185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 9195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (size <= m_size) 9205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) TypeOperations::destruct(begin() + size, end()); 9215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) else { 9225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (size > capacity()) 9235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) expandCapacity(size); 9248abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles) TypeOperations::initialize(end(), begin() + size); 9255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 92602772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 9275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_size = size; 9285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 9295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 93009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename Allocator> 93109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) void Vector<T, inlineCapacity, Allocator>::shrink(size_t size) 9325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 9335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(size <= m_size); 9345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) TypeOperations::destruct(begin() + size, end()); 93509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) clearUnusedSlots(begin() + size, end()); 9365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_size = size; 9375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 9385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 93909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename Allocator> 94009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) void Vector<T, inlineCapacity, Allocator>::grow(size_t size) 9415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 9425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(size >= m_size); 9435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (size > capacity()) 9445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) expandCapacity(size); 9458abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles) TypeOperations::initialize(end(), begin() + size); 9465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_size = size; 9475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 9485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 94909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename Allocator> 95009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) void Vector<T, inlineCapacity, Allocator>::reserveCapacity(size_t newCapacity) 9515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 9528abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles) if (UNLIKELY(newCapacity <= capacity())) 9535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return; 9545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) T* oldBuffer = begin(); 9555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) T* oldEnd = end(); 95653e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) Base::allocateBuffer(newCapacity); 9578abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles) TypeOperations::move(oldBuffer, oldEnd, begin()); 95853e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) Base::deallocateBuffer(oldBuffer); 9595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 96002772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 96109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename Allocator> 96209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) inline void Vector<T, inlineCapacity, Allocator>::reserveInitialCapacity(size_t initialCapacity) 9635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 9645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(!m_size); 9655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(capacity() == inlineCapacity); 9665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (initialCapacity > inlineCapacity) 96753e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) Base::allocateBuffer(initialCapacity); 9685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 96902772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 97009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename Allocator> 97109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) void Vector<T, inlineCapacity, Allocator>::shrinkCapacity(size_t newCapacity) 9725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 9735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (newCapacity >= capacity()) 9745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return; 9755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 97602772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch if (newCapacity < size()) 9775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) shrink(newCapacity); 9785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 9795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) T* oldBuffer = begin(); 9805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (newCapacity > 0) { 9819bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) // Optimization: if we're downsizing inside the same allocator bucket, we can exit with no additional work. 9829bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) if (Base::allocationSize(capacity()) == Base::allocationSize(newCapacity)) 9835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return; 9845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 9855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) T* oldEnd = end(); 98653e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) Base::allocateBuffer(newCapacity); 9875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (begin() != oldBuffer) 9885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) TypeOperations::move(oldBuffer, oldEnd, begin()); 9899bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) } else { 9909bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) Base::resetBufferPointer(); 9915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 9925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 99353e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) Base::deallocateBuffer(oldBuffer); 9945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 9955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 9965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Templatizing these is better than just letting the conversion happen implicitly, 9975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // because for instance it allows a PassRefPtr to be appended to a RefPtr vector 9985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // without refcount thrash. 9995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 100009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename Allocator> template<typename U> 100109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) void Vector<T, inlineCapacity, Allocator>::append(const U* data, size_t dataSize) 10025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 1003e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles) ASSERT(Allocator::isAllocationAllowed()); 10045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) size_t newSize = m_size + dataSize; 10055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (newSize > capacity()) { 10065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) data = expandCapacity(newSize, data); 10073c9e4aeaee9f9b0a9a814da07bcb33319c7ea363Ben Murdoch ASSERT(begin()); 10085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 100953e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) RELEASE_ASSERT(newSize >= m_size); 10105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) T* dest = end(); 1011d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) VectorCopier<VectorTraits<T>::canCopyWithMemcpy, T>::uninitializedCopy(data, &data[dataSize], dest); 10125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_size = newSize; 10135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 10145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 101509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename Allocator> template<typename U> 101609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ALWAYS_INLINE void Vector<T, inlineCapacity, Allocator>::append(const U& val) 10175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 1018e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles) ASSERT(Allocator::isAllocationAllowed()); 10193c9e4aeaee9f9b0a9a814da07bcb33319c7ea363Ben Murdoch if (LIKELY(size() != capacity())) { 10205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) new (NotNull, end()) T(val); 10215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ++m_size; 10225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return; 10235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 10245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 10255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) appendSlowCase(val); 10265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 10275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 102809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename Allocator> template<typename U> 102909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) NEVER_INLINE void Vector<T, inlineCapacity, Allocator>::appendSlowCase(const U& val) 10305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 10315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(size() == capacity()); 10325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 10335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const U* ptr = &val; 10345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ptr = expandCapacity(size() + 1, ptr); 10353c9e4aeaee9f9b0a9a814da07bcb33319c7ea363Ben Murdoch ASSERT(begin()); 10365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 10375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) new (NotNull, end()) T(*ptr); 10385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ++m_size; 10395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 10405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 10415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // This version of append saves a branch in the case where you know that the 10425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // vector's capacity is large enough for the append to succeed. 10435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 104409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename Allocator> template<typename U> 104509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ALWAYS_INLINE void Vector<T, inlineCapacity, Allocator>::uncheckedAppend(const U& val) 10465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 10475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(size() < capacity()); 10485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const U* ptr = &val; 10495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) new (NotNull, end()) T(*ptr); 10505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ++m_size; 10515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 10525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 105309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename Allocator> template<typename U, size_t otherCapacity, typename OtherAllocator> 105409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) inline void Vector<T, inlineCapacity, Allocator>::appendVector(const Vector<U, otherCapacity, OtherAllocator>& val) 10555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 10565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) append(val.begin(), val.size()); 10575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 10585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 105909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename Allocator> template<typename U> 106009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) void Vector<T, inlineCapacity, Allocator>::insert(size_t position, const U* data, size_t dataSize) 10615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 1062e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles) ASSERT(Allocator::isAllocationAllowed()); 106353e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) RELEASE_ASSERT(position <= size()); 10645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) size_t newSize = m_size + dataSize; 10655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (newSize > capacity()) { 10665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) data = expandCapacity(newSize, data); 10673c9e4aeaee9f9b0a9a814da07bcb33319c7ea363Ben Murdoch ASSERT(begin()); 10685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 106953e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) RELEASE_ASSERT(newSize >= m_size); 10705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) T* spot = begin() + position; 10715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) TypeOperations::moveOverlapping(spot, end(), spot + dataSize); 1072d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) VectorCopier<VectorTraits<T>::canCopyWithMemcpy, T>::uninitializedCopy(data, &data[dataSize], spot); 10735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_size = newSize; 10745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 107502772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 107609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename Allocator> template<typename U> 107709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) inline void Vector<T, inlineCapacity, Allocator>::insert(size_t position, const U& val) 10785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 1079e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles) ASSERT(Allocator::isAllocationAllowed()); 108053e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) RELEASE_ASSERT(position <= size()); 10815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const U* data = &val; 10825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (size() == capacity()) { 10835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) data = expandCapacity(size() + 1, data); 10843c9e4aeaee9f9b0a9a814da07bcb33319c7ea363Ben Murdoch ASSERT(begin()); 10855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 10865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) T* spot = begin() + position; 10875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) TypeOperations::moveOverlapping(spot, end(), spot + 1); 10885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) new (NotNull, spot) T(*data); 10895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ++m_size; 10905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 109102772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 109209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename Allocator> template<typename U, size_t c, typename OtherAllocator> 109309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) inline void Vector<T, inlineCapacity, Allocator>::insert(size_t position, const Vector<U, c, OtherAllocator>& val) 10945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 10955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) insert(position, val.begin(), val.size()); 10965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 10975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 109809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename Allocator> template<typename U> 109909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) void Vector<T, inlineCapacity, Allocator>::prepend(const U* data, size_t dataSize) 11005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 11015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) insert(0, data, dataSize); 11025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 11035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 110409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename Allocator> template<typename U> 110509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) inline void Vector<T, inlineCapacity, Allocator>::prepend(const U& val) 11065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 11075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) insert(0, val); 11085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 110902772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 111009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename Allocator> template<typename U, size_t c, typename V> 111109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) inline void Vector<T, inlineCapacity, Allocator>::prepend(const Vector<U, c, V>& val) 11125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 11135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) insert(0, val.begin(), val.size()); 11145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 111502772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 111609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename Allocator> 111709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) inline void Vector<T, inlineCapacity, Allocator>::remove(size_t position) 11185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 111953e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) RELEASE_ASSERT(position < size()); 11205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) T* spot = begin() + position; 11215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) spot->~T(); 11225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) TypeOperations::moveOverlapping(spot + 1, end(), spot); 112309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) clearUnusedSlots(end() - 1, end()); 11245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) --m_size; 11255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 11265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 112709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename Allocator> 112809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) inline void Vector<T, inlineCapacity, Allocator>::remove(size_t position, size_t length) 11295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 1130926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) ASSERT_WITH_SECURITY_IMPLICATION(position <= size()); 113153e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) RELEASE_ASSERT(position + length <= size()); 11325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) T* beginSpot = begin() + position; 11335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) T* endSpot = beginSpot + length; 113402772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch TypeOperations::destruct(beginSpot, endSpot); 11355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) TypeOperations::moveOverlapping(endSpot, end(), beginSpot); 113609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) clearUnusedSlots(end() - length, end()); 11375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_size -= length; 11385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 11395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 114009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename Allocator> 114109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) inline void Vector<T, inlineCapacity, Allocator>::reverse() 11425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 11435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (size_t i = 0; i < m_size / 2; ++i) 11445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) std::swap(at(i), at(m_size - 1 - i)); 11455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 11465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 114709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename Allocator> 114809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) void deleteAllValues(const Vector<T, inlineCapacity, Allocator>& collection) 11495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 115009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) typedef typename Vector<T, inlineCapacity, Allocator>::const_iterator iterator; 11515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) iterator end = collection.end(); 11525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (iterator it = collection.begin(); it != end; ++it) 11535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) delete *it; 11545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 11555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 115609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename Allocator> 115709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) inline void swap(Vector<T, inlineCapacity, Allocator>& a, Vector<T, inlineCapacity, Allocator>& b) 11585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 11595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) a.swap(b); 11605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 11615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1162d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) template<typename T, size_t inlineCapacityA, size_t inlineCapacityB, typename Allocator> 1163d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) bool operator==(const Vector<T, inlineCapacityA, Allocator>& a, const Vector<T, inlineCapacityB, Allocator>& b) 11645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 11655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (a.size() != b.size()) 11665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return false; 11675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 11685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return VectorTypeOperations<T>::compare(a.data(), b.data(), a.size()); 11695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 11705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1171d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) template<typename T, size_t inlineCapacityA, size_t inlineCapacityB, typename Allocator> 1172d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) inline bool operator!=(const Vector<T, inlineCapacityA, Allocator>& a, const Vector<T, inlineCapacityB, Allocator>& b) 11735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 11745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return !(a == b); 11755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 11765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 117709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // This is only called if the allocator is a HeapAllocator. It is used when 117809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // visiting during a tracing GC. 117909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename Allocator> 118009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) void Vector<T, inlineCapacity, Allocator>::trace(typename Allocator::Visitor* visitor) 118109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) { 1182197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch ASSERT(Allocator::isGarbageCollected); // Garbage collector must be enabled. 118309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) const T* bufferBegin = buffer(); 118409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) const T* bufferEnd = buffer() + size(); 1185d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) if (ShouldBeTraced<VectorTraits<T> >::value) { 118609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) for (const T* bufferEntry = bufferBegin; bufferEntry != bufferEnd; bufferEntry++) 118709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) Allocator::template trace<T, VectorTraits<T> >(visitor, *const_cast<T*>(bufferEntry)); 118809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) } 118909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) if (this->hasOutOfLineBuffer()) 119009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) Allocator::markNoTracing(visitor, buffer()); 119109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) } 119209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 1193197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch#if !ENABLE(OILPAN) 1194197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch template<typename T, size_t N> 1195197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch struct NeedsTracing<Vector<T, N> > { 1196197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch static const bool value = false; 1197197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch }; 1198197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch#endif 1199197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch 12005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} // namespace WTF 12015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 12025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)using WTF::Vector; 12035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 12045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif // WTF_Vector_h 1205