| OLD | NEW |
| 1 /* | 1 /* |
| 2 * Copyright (C) 2005, 2006, 2007, 2008 Apple Inc. All rights reserved. | 2 * Copyright (C) 2005, 2006, 2007, 2008 Apple Inc. All rights reserved. |
| 3 * | 3 * |
| 4 * This library is free software; you can redistribute it and/or | 4 * This library is free software; you can redistribute it and/or |
| 5 * modify it under the terms of the GNU Library General Public | 5 * modify it under the terms of the GNU Library General Public |
| 6 * License as published by the Free Software Foundation; either | 6 * License as published by the Free Software Foundation; either |
| 7 * version 2 of the License, or (at your option) any later version. | 7 * version 2 of the License, or (at your option) any later version. |
| 8 * | 8 * |
| 9 * This library is distributed in the hope that it will be useful, | 9 * This library is distributed in the hope that it will be useful, |
| 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of | 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of |
| (...skipping 47 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 58 template<typename T> | 58 template<typename T> |
| 59 struct VectorDestructor<true, T> | 59 struct VectorDestructor<true, T> |
| 60 { | 60 { |
| 61 static void destruct(T* begin, T* end) | 61 static void destruct(T* begin, T* end) |
| 62 { | 62 { |
| 63 for (T* cur = begin; cur != end; ++cur) | 63 for (T* cur = begin; cur != end; ++cur) |
| 64 cur->~T(); | 64 cur->~T(); |
| 65 } | 65 } |
| 66 }; | 66 }; |
| 67 | 67 |
| 68 template <bool unusedSlotsMustBeZeroed, typename T> | |
| 69 struct VectorUnusedSlotClearer; | |
| 70 | |
| 71 template<typename T> | |
| 72 struct VectorUnusedSlotClearer<false, T> { | |
| 73 static void clear(T*, T*) { } | |
| 74 }; | |
| 75 | |
| 76 template<typename T> | |
| 77 struct VectorUnusedSlotClearer<true, T> { | |
| 78 static void clear(T* begin, T* end) | |
| 79 { | |
| 80 // We clear out unused slots so that the visitor and the finalizer | |
| 81 // do not visit them (or at least it does not matter if they do). | |
| 82 memset(begin, 0, sizeof(T) * (end - begin)); | |
| 83 } | |
| 84 }; | |
| 85 | |
| 86 template <bool canInitializeWithMemset, typename T> | 68 template <bool canInitializeWithMemset, typename T> |
| 87 struct VectorInitializer; | 69 struct VectorInitializer; |
| 88 | 70 |
| 89 template<typename T> | 71 template<typename T> |
| 90 struct VectorInitializer<false, T> | 72 struct VectorInitializer<false, T> |
| 91 { | 73 { |
| 92 static void initialize(T* begin, T* end) | 74 static void initialize(T* begin, T* end) |
| 93 { | 75 { |
| 94 for (T* cur = begin; cur != end; ++cur) | 76 for (T* cur = begin; cur != end; ++cur) |
| 95 new (NotNull, cur) T; | 77 new (NotNull, cur) T; |
| (...skipping 202 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 298 | 280 |
| 299 size_t allocationSize(size_t capacity) const | 281 size_t allocationSize(size_t capacity) const |
| 300 { | 282 { |
| 301 return Allocator::Quantizer::template quantizedSize<T>(capacity); | 283 return Allocator::Quantizer::template quantizedSize<T>(capacity); |
| 302 } | 284 } |
| 303 | 285 |
| 304 T* buffer() { return m_buffer; } | 286 T* buffer() { return m_buffer; } |
| 305 const T* buffer() const { return m_buffer; } | 287 const T* buffer() const { return m_buffer; } |
| 306 size_t capacity() const { return m_capacity; } | 288 size_t capacity() const { return m_capacity; } |
| 307 | 289 |
| 308 void clearUnusedSlots(T* from, T* to) | |
| 309 { | |
| 310 VectorUnusedSlotClearer<Allocator::isGarbageCollected && (VectorTrai
ts<T>::needsDestruction || ShouldBeTraced<VectorTraits<T> >::value), T>::clear(f
rom, to); | |
| 311 } | |
| 312 | |
| 313 protected: | 290 protected: |
| 314 VectorBufferBase() | 291 VectorBufferBase() |
| 315 : m_buffer(0) | 292 : m_buffer(0) |
| 316 , m_capacity(0) | 293 , m_capacity(0) |
| 317 { | 294 { |
| 318 } | 295 } |
| 319 | 296 |
| 320 VectorBufferBase(T* buffer, size_t capacity) | 297 VectorBufferBase(T* buffer, size_t capacity) |
| 321 : m_buffer(buffer) | 298 : m_buffer(buffer) |
| 322 , m_capacity(capacity) | 299 , m_capacity(capacity) |
| (...skipping 47 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 370 std::swap(m_buffer, other.m_buffer); | 347 std::swap(m_buffer, other.m_buffer); |
| 371 std::swap(m_capacity, other.m_capacity); | 348 std::swap(m_capacity, other.m_capacity); |
| 372 } | 349 } |
| 373 | 350 |
| 374 using Base::allocateBuffer; | 351 using Base::allocateBuffer; |
| 375 using Base::allocationSize; | 352 using Base::allocationSize; |
| 376 | 353 |
| 377 using Base::buffer; | 354 using Base::buffer; |
| 378 using Base::capacity; | 355 using Base::capacity; |
| 379 | 356 |
| 380 using Base::clearUnusedSlots; | |
| 381 | |
| 382 bool hasOutOfLineBuffer() const | 357 bool hasOutOfLineBuffer() const |
| 383 { | 358 { |
| 384 // When inlineCapacity is 0 we have an out of line buffer if we have
a buffer. | 359 // When inlineCapacity is 0 we have an out of line buffer if we have
a buffer. |
| 385 return buffer(); | 360 return buffer(); |
| 386 } | 361 } |
| 387 | 362 |
| 388 protected: | 363 protected: |
| 389 using Base::m_size; | 364 using Base::m_size; |
| 390 | 365 |
| 391 private: | 366 private: |
| (...skipping 308 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 700 template<typename Iterator> void appendRange(Iterator start, Iterator en
d); | 675 template<typename Iterator> void appendRange(Iterator start, Iterator en
d); |
| 701 | 676 |
| 702 void swap(Vector& other) | 677 void swap(Vector& other) |
| 703 { | 678 { |
| 704 Base::swapVectorBuffer(other); | 679 Base::swapVectorBuffer(other); |
| 705 std::swap(m_size, other.m_size); | 680 std::swap(m_size, other.m_size); |
| 706 } | 681 } |
| 707 | 682 |
| 708 void reverse(); | 683 void reverse(); |
| 709 | 684 |
| 710 void trace(typename Allocator::Visitor*); | |
| 711 | |
| 712 private: | 685 private: |
| 713 void expandCapacity(size_t newMinCapacity); | 686 void expandCapacity(size_t newMinCapacity); |
| 714 const T* expandCapacity(size_t newMinCapacity, const T*); | 687 const T* expandCapacity(size_t newMinCapacity, const T*); |
| 715 template<typename U> U* expandCapacity(size_t newMinCapacity, U*); | 688 template<typename U> U* expandCapacity(size_t newMinCapacity, U*); |
| 716 void shrinkCapacity(size_t newCapacity); | 689 void shrinkCapacity(size_t newCapacity); |
| 717 template<typename U> void appendSlowCase(const U&); | 690 template<typename U> void appendSlowCase(const U&); |
| 718 | 691 |
| 719 using Base::m_size; | 692 using Base::m_size; |
| 720 using Base::buffer; | 693 using Base::buffer; |
| 721 using Base::capacity; | 694 using Base::capacity; |
| 722 using Base::swapVectorBuffer; | 695 using Base::swapVectorBuffer; |
| 723 using Base::allocateBuffer; | 696 using Base::allocateBuffer; |
| 724 using Base::allocationSize; | 697 using Base::allocationSize; |
| 725 using Base::clearUnusedSlots; | |
| 726 }; | 698 }; |
| 727 | 699 |
| 728 template<typename T, size_t inlineCapacity, typename Allocator> | 700 template<typename T, size_t inlineCapacity, typename Allocator> |
| 729 Vector<T, inlineCapacity, Allocator>::Vector(const Vector& other) | 701 Vector<T, inlineCapacity, Allocator>::Vector(const Vector& other) |
| 730 : Base(other.capacity()) | 702 : Base(other.capacity()) |
| 731 { | 703 { |
| 732 m_size = other.size(); | 704 m_size = other.size(); |
| 733 TypeOperations::uninitializedCopy(other.begin(), other.end(), begin()); | 705 TypeOperations::uninitializedCopy(other.begin(), other.end(), begin()); |
| 734 } | 706 } |
| 735 | 707 |
| (...skipping 180 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 916 } | 888 } |
| 917 | 889 |
| 918 m_size = size; | 890 m_size = size; |
| 919 } | 891 } |
| 920 | 892 |
| 921 template<typename T, size_t inlineCapacity, typename Allocator> | 893 template<typename T, size_t inlineCapacity, typename Allocator> |
| 922 void Vector<T, inlineCapacity, Allocator>::shrink(size_t size) | 894 void Vector<T, inlineCapacity, Allocator>::shrink(size_t size) |
| 923 { | 895 { |
| 924 ASSERT(size <= m_size); | 896 ASSERT(size <= m_size); |
| 925 TypeOperations::destruct(begin() + size, end()); | 897 TypeOperations::destruct(begin() + size, end()); |
| 926 clearUnusedSlots(begin() + size, end()); | |
| 927 m_size = size; | 898 m_size = size; |
| 928 } | 899 } |
| 929 | 900 |
| 930 template<typename T, size_t inlineCapacity, typename Allocator> | 901 template<typename T, size_t inlineCapacity, typename Allocator> |
| 931 void Vector<T, inlineCapacity, Allocator>::grow(size_t size) | 902 void Vector<T, inlineCapacity, Allocator>::grow(size_t size) |
| 932 { | 903 { |
| 933 ASSERT(size >= m_size); | 904 ASSERT(size >= m_size); |
| 934 if (size > capacity()) | 905 if (size > capacity()) |
| 935 expandCapacity(size); | 906 expandCapacity(size); |
| 936 TypeOperations::initialize(end(), begin() + size); | 907 TypeOperations::initialize(end(), begin() + size); |
| (...skipping 167 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1104 insert(0, val.begin(), val.size()); | 1075 insert(0, val.begin(), val.size()); |
| 1105 } | 1076 } |
| 1106 | 1077 |
| 1107 template<typename T, size_t inlineCapacity, typename Allocator> | 1078 template<typename T, size_t inlineCapacity, typename Allocator> |
| 1108 inline void Vector<T, inlineCapacity, Allocator>::remove(size_t position) | 1079 inline void Vector<T, inlineCapacity, Allocator>::remove(size_t position) |
| 1109 { | 1080 { |
| 1110 RELEASE_ASSERT(position < size()); | 1081 RELEASE_ASSERT(position < size()); |
| 1111 T* spot = begin() + position; | 1082 T* spot = begin() + position; |
| 1112 spot->~T(); | 1083 spot->~T(); |
| 1113 TypeOperations::moveOverlapping(spot + 1, end(), spot); | 1084 TypeOperations::moveOverlapping(spot + 1, end(), spot); |
| 1114 clearUnusedSlots(end() - 1, end()); | |
| 1115 --m_size; | 1085 --m_size; |
| 1116 } | 1086 } |
| 1117 | 1087 |
| 1118 template<typename T, size_t inlineCapacity, typename Allocator> | 1088 template<typename T, size_t inlineCapacity, typename Allocator> |
| 1119 inline void Vector<T, inlineCapacity, Allocator>::remove(size_t position, si
ze_t length) | 1089 inline void Vector<T, inlineCapacity, Allocator>::remove(size_t position, si
ze_t length) |
| 1120 { | 1090 { |
| 1121 ASSERT_WITH_SECURITY_IMPLICATION(position <= size()); | 1091 ASSERT_WITH_SECURITY_IMPLICATION(position <= size()); |
| 1122 RELEASE_ASSERT(position + length <= size()); | 1092 RELEASE_ASSERT(position + length <= size()); |
| 1123 T* beginSpot = begin() + position; | 1093 T* beginSpot = begin() + position; |
| 1124 T* endSpot = beginSpot + length; | 1094 T* endSpot = beginSpot + length; |
| 1125 TypeOperations::destruct(beginSpot, endSpot); | 1095 TypeOperations::destruct(beginSpot, endSpot); |
| 1126 TypeOperations::moveOverlapping(endSpot, end(), beginSpot); | 1096 TypeOperations::moveOverlapping(endSpot, end(), beginSpot); |
| 1127 clearUnusedSlots(end() - length, end()); | |
| 1128 m_size -= length; | 1097 m_size -= length; |
| 1129 } | 1098 } |
| 1130 | 1099 |
| 1131 template<typename T, size_t inlineCapacity, typename Allocator> | 1100 template<typename T, size_t inlineCapacity, typename Allocator> |
| 1132 inline void Vector<T, inlineCapacity, Allocator>::reverse() | 1101 inline void Vector<T, inlineCapacity, Allocator>::reverse() |
| 1133 { | 1102 { |
| 1134 for (size_t i = 0; i < m_size / 2; ++i) | 1103 for (size_t i = 0; i < m_size / 2; ++i) |
| 1135 std::swap(at(i), at(m_size - 1 - i)); | 1104 std::swap(at(i), at(m_size - 1 - i)); |
| 1136 } | 1105 } |
| 1137 | 1106 |
| (...skipping 20 matching lines...) Expand all Loading... |
| 1158 | 1127 |
| 1159 return VectorTypeOperations<T>::compare(a.data(), b.data(), a.size()); | 1128 return VectorTypeOperations<T>::compare(a.data(), b.data(), a.size()); |
| 1160 } | 1129 } |
| 1161 | 1130 |
| 1162 template<typename T, size_t inlineCapacityA, size_t inlineCapacityB, typenam
e Allocator> | 1131 template<typename T, size_t inlineCapacityA, size_t inlineCapacityB, typenam
e Allocator> |
| 1163 inline bool operator!=(const Vector<T, inlineCapacityA, Allocator>& a, const
Vector<T, inlineCapacityB, Allocator>& b) | 1132 inline bool operator!=(const Vector<T, inlineCapacityA, Allocator>& a, const
Vector<T, inlineCapacityB, Allocator>& b) |
| 1164 { | 1133 { |
| 1165 return !(a == b); | 1134 return !(a == b); |
| 1166 } | 1135 } |
| 1167 | 1136 |
| 1168 // This is only called if the allocator is a HeapAllocator. It is used when | |
| 1169 // visiting during a tracing GC. | |
| 1170 template<typename T, size_t inlineCapacity, typename Allocator> | |
| 1171 void Vector<T, inlineCapacity, Allocator>::trace(typename Allocator::Visitor
* visitor) | |
| 1172 { | |
| 1173 ASSERT(Allocator::isGarbageCollected); // Garbage collector must be enab
led. | |
| 1174 const T* bufferBegin = buffer(); | |
| 1175 const T* bufferEnd = buffer() + size(); | |
| 1176 if (ShouldBeTraced<VectorTraits<T> >::value) { | |
| 1177 for (const T* bufferEntry = bufferBegin; bufferEntry != bufferEnd; b
ufferEntry++) | |
| 1178 Allocator::template trace<T, VectorTraits<T> >(visitor, *const_c
ast<T*>(bufferEntry)); | |
| 1179 } | |
| 1180 if (this->hasOutOfLineBuffer()) | |
| 1181 Allocator::markNoTracing(visitor, buffer()); | |
| 1182 } | |
| 1183 | |
| 1184 #if !ENABLE(OILPAN) | |
| 1185 template<typename T, size_t N> | |
| 1186 struct NeedsTracing<Vector<T, N> > { | |
| 1187 static const bool value = false; | |
| 1188 }; | |
| 1189 #endif | |
| 1190 | |
| 1191 } // namespace WTF | 1137 } // namespace WTF |
| 1192 | 1138 |
| 1193 using WTF::Vector; | 1139 using WTF::Vector; |
| 1194 | 1140 |
| 1195 #endif // WTF_Vector_h | 1141 #endif // WTF_Vector_h |
| OLD | NEW |