OLD | NEW |
| (Empty) |
1 /* | |
2 * Copyright (C) 2005, 2006, 2007, 2008 Apple Inc. All rights reserved. | |
3 * | |
4 * This library is free software; you can redistribute it and/or | |
5 * modify it under the terms of the GNU Library General Public | |
6 * License as published by the Free Software Foundation; either | |
7 * version 2 of the License, or (at your option) any later version. | |
8 * | |
9 * This library is distributed in the hope that it will be useful, | |
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
12 * Library General Public License for more details. | |
13 * | |
14 * You should have received a copy of the GNU Library General Public License | |
15 * along with this library; see the file COPYING.LIB. If not, write to | |
16 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, | |
17 * Boston, MA 02110-1301, USA. | |
18 * | |
19 */ | |
20 | |
21 #ifndef WTF_Vector_h | |
22 #define WTF_Vector_h | |
23 | |
24 #include <wtf/Alignment.h> | |
25 #include <wtf/FastAllocBase.h> | |
26 #include <wtf/Noncopyable.h> | |
27 #include <wtf/NotFound.h> | |
28 #include <wtf/StdLibExtras.h> | |
29 #include <wtf/UnusedParam.h> | |
30 #include <wtf/ValueCheck.h> | |
31 #include <wtf/VectorTraits.h> | |
32 #include <limits> | |
33 #include <utility> | |
34 #include <string.h> | |
35 | |
36 namespace WTF { | |
37 | |
38 template <bool needsDestruction, typename T> | |
39 struct VectorDestructor; | |
40 | |
41 template<typename T> | |
42 struct VectorDestructor<false, T> | |
43 { | |
44 static void destruct(T*, T*) {} | |
45 }; | |
46 | |
47 template<typename T> | |
48 struct VectorDestructor<true, T> | |
49 { | |
50 static void destruct(T* begin, T* end) | |
51 { | |
52 for (T* cur = begin; cur != end; ++cur) | |
53 cur->~T(); | |
54 } | |
55 }; | |
56 | |
57 template <bool needsInitialization, bool canInitializeWithMemset, typename T
> | |
58 struct VectorInitializer; | |
59 | |
60 template<bool ignore, typename T> | |
61 struct VectorInitializer<false, ignore, T> | |
62 { | |
63 static void initialize(T*, T*) {} | |
64 }; | |
65 | |
66 template<typename T> | |
67 struct VectorInitializer<true, false, T> | |
68 { | |
69 static void initialize(T* begin, T* end) | |
70 { | |
71 for (T* cur = begin; cur != end; ++cur) | |
72 new (NotNull, cur) T; | |
73 } | |
74 }; | |
75 | |
76 template<typename T> | |
77 struct VectorInitializer<true, true, T> | |
78 { | |
79 static void initialize(T* begin, T* end) | |
80 { | |
81 memset(begin, 0, reinterpret_cast<char*>(end) - reinterpret_cast<cha
r*>(begin)); | |
82 } | |
83 }; | |
84 | |
85 template <bool canMoveWithMemcpy, typename T> | |
86 struct VectorMover; | |
87 | |
88 template<typename T> | |
89 struct VectorMover<false, T> | |
90 { | |
91 static void move(const T* src, const T* srcEnd, T* dst) | |
92 { | |
93 while (src != srcEnd) { | |
94 new (NotNull, dst) T(*src); | |
95 #if COMPILER(SUNCC) && __SUNPRO_CC <= 0x590 | |
96 const_cast<T*>(src)->~T(); // Work around obscure SunCC 12 compi
ler bug. | |
97 #else | |
98 src->~T(); | |
99 #endif | |
100 ++dst; | |
101 ++src; | |
102 } | |
103 } | |
104 static void moveOverlapping(const T* src, const T* srcEnd, T* dst) | |
105 { | |
106 if (src > dst) | |
107 move(src, srcEnd, dst); | |
108 else { | |
109 T* dstEnd = dst + (srcEnd - src); | |
110 while (src != srcEnd) { | |
111 --srcEnd; | |
112 --dstEnd; | |
113 new (NotNull, dstEnd) T(*srcEnd); | |
114 srcEnd->~T(); | |
115 } | |
116 } | |
117 } | |
118 }; | |
119 | |
120 template<typename T> | |
121 struct VectorMover<true, T> | |
122 { | |
123 static void move(const T* src, const T* srcEnd, T* dst) | |
124 { | |
125 memcpy(dst, src, reinterpret_cast<const char*>(srcEnd) - reinterpret
_cast<const char*>(src)); | |
126 } | |
127 static void moveOverlapping(const T* src, const T* srcEnd, T* dst) | |
128 { | |
129 memmove(dst, src, reinterpret_cast<const char*>(srcEnd) - reinterpre
t_cast<const char*>(src)); | |
130 } | |
131 }; | |
132 | |
133 template <bool canCopyWithMemcpy, typename T> | |
134 struct VectorCopier; | |
135 | |
136 template<typename T> | |
137 struct VectorCopier<false, T> | |
138 { | |
139 static void uninitializedCopy(const T* src, const T* srcEnd, T* dst) | |
140 { | |
141 while (src != srcEnd) { | |
142 new (NotNull, dst) T(*src); | |
143 ++dst; | |
144 ++src; | |
145 } | |
146 } | |
147 }; | |
148 | |
149 template<typename T> | |
150 struct VectorCopier<true, T> | |
151 { | |
152 static void uninitializedCopy(const T* src, const T* srcEnd, T* dst) | |
153 { | |
154 memcpy(dst, src, reinterpret_cast<const char*>(srcEnd) - reinterpret
_cast<const char*>(src)); | |
155 } | |
156 }; | |
157 | |
158 template <bool canFillWithMemset, typename T> | |
159 struct VectorFiller; | |
160 | |
161 template<typename T> | |
162 struct VectorFiller<false, T> | |
163 { | |
164 static void uninitializedFill(T* dst, T* dstEnd, const T& val) | |
165 { | |
166 while (dst != dstEnd) { | |
167 new (NotNull, dst) T(val); | |
168 ++dst; | |
169 } | |
170 } | |
171 }; | |
172 | |
173 template<typename T> | |
174 struct VectorFiller<true, T> | |
175 { | |
176 static void uninitializedFill(T* dst, T* dstEnd, const T& val) | |
177 { | |
178 ASSERT(sizeof(T) == sizeof(char)); | |
179 #if COMPILER(GCC) && defined(_FORTIFY_SOURCE) | |
180 if (!__builtin_constant_p(dstEnd - dst) || (!(dstEnd - dst))) | |
181 #endif | |
182 memset(dst, val, dstEnd - dst); | |
183 } | |
184 }; | |
185 | |
186 template<bool canCompareWithMemcmp, typename T> | |
187 struct VectorComparer; | |
188 | |
189 template<typename T> | |
190 struct VectorComparer<false, T> | |
191 { | |
192 static bool compare(const T* a, const T* b, size_t size) | |
193 { | |
194 for (size_t i = 0; i < size; ++i) | |
195 if (!(a[i] == b[i])) | |
196 return false; | |
197 return true; | |
198 } | |
199 }; | |
200 | |
201 template<typename T> | |
202 struct VectorComparer<true, T> | |
203 { | |
204 static bool compare(const T* a, const T* b, size_t size) | |
205 { | |
206 return memcmp(a, b, sizeof(T) * size) == 0; | |
207 } | |
208 }; | |
209 | |
210 template<typename T> | |
211 struct VectorTypeOperations | |
212 { | |
213 static void destruct(T* begin, T* end) | |
214 { | |
215 VectorDestructor<VectorTraits<T>::needsDestruction, T>::destruct(beg
in, end); | |
216 } | |
217 | |
218 static void initialize(T* begin, T* end) | |
219 { | |
220 VectorInitializer<VectorTraits<T>::needsInitialization, VectorTraits
<T>::canInitializeWithMemset, T>::initialize(begin, end); | |
221 } | |
222 | |
223 static void move(const T* src, const T* srcEnd, T* dst) | |
224 { | |
225 VectorMover<VectorTraits<T>::canMoveWithMemcpy, T>::move(src, srcEnd
, dst); | |
226 } | |
227 | |
228 static void moveOverlapping(const T* src, const T* srcEnd, T* dst) | |
229 { | |
230 VectorMover<VectorTraits<T>::canMoveWithMemcpy, T>::moveOverlapping(
src, srcEnd, dst); | |
231 } | |
232 | |
233 static void uninitializedCopy(const T* src, const T* srcEnd, T* dst) | |
234 { | |
235 VectorCopier<VectorTraits<T>::canCopyWithMemcpy, T>::uninitializedCo
py(src, srcEnd, dst); | |
236 } | |
237 | |
238 static void uninitializedFill(T* dst, T* dstEnd, const T& val) | |
239 { | |
240 VectorFiller<VectorTraits<T>::canFillWithMemset, T>::uninitializedFi
ll(dst, dstEnd, val); | |
241 } | |
242 | |
243 static bool compare(const T* a, const T* b, size_t size) | |
244 { | |
245 return VectorComparer<VectorTraits<T>::canCompareWithMemcmp, T>::com
pare(a, b, size); | |
246 } | |
247 }; | |
248 | |
249 template<typename T> | |
250 class VectorBufferBase { | |
251 WTF_MAKE_NONCOPYABLE(VectorBufferBase); | |
252 public: | |
253 void allocateBuffer(size_t newCapacity) | |
254 { | |
255 ASSERT(newCapacity); | |
256 // Using "unsigned" is not a limitation because Chromium's max mallo
c() is 2GB even on 64-bit. | |
257 RELEASE_ASSERT(newCapacity <= std::numeric_limits<unsigned>::max() /
sizeof(T)); | |
258 size_t sizeToAllocate = fastMallocGoodSize(newCapacity * sizeof(T)); | |
259 m_capacity = sizeToAllocate / sizeof(T); | |
260 m_buffer = static_cast<T*>(fastMalloc(sizeToAllocate)); | |
261 } | |
262 | |
263 bool tryAllocateBuffer(size_t newCapacity) | |
264 { | |
265 ASSERT(newCapacity); | |
266 // Using "unsigned" is not a limitation because Chromium's max mallo
c() is 2GB even on 64-bit. | |
267 if (newCapacity > std::numeric_limits<unsigned>::max() / sizeof(T)) | |
268 return false; | |
269 | |
270 size_t sizeToAllocate = fastMallocGoodSize(newCapacity * sizeof(T)); | |
271 T* newBuffer; | |
272 if (tryFastMalloc(sizeToAllocate).getValue(newBuffer)) { | |
273 m_capacity = sizeToAllocate / sizeof(T); | |
274 m_buffer = newBuffer; | |
275 return true; | |
276 } | |
277 return false; | |
278 } | |
279 | |
280 bool shouldReallocateBuffer(size_t newCapacity) const | |
281 { | |
282 return VectorTraits<T>::canMoveWithMemcpy && m_capacity && newCapaci
ty; | |
283 } | |
284 | |
285 void reallocateBuffer(size_t newCapacity) | |
286 { | |
287 ASSERT(shouldReallocateBuffer(newCapacity)); | |
288 // Using "unsigned" is not a limitation because Chromium's max mallo
c() is 2GB even on 64-bit. | |
289 RELEASE_ASSERT(newCapacity <= std::numeric_limits<unsigned>::max() /
sizeof(T)); | |
290 size_t sizeToAllocate = fastMallocGoodSize(newCapacity * sizeof(T)); | |
291 m_capacity = sizeToAllocate / sizeof(T); | |
292 m_buffer = static_cast<T*>(fastRealloc(m_buffer, sizeToAllocate)); | |
293 } | |
294 | |
295 void deallocateBuffer(T* bufferToDeallocate) | |
296 { | |
297 if (!bufferToDeallocate) | |
298 return; | |
299 | |
300 if (m_buffer == bufferToDeallocate) { | |
301 m_buffer = 0; | |
302 m_capacity = 0; | |
303 } | |
304 | |
305 fastFree(bufferToDeallocate); | |
306 } | |
307 | |
308 T* buffer() { return m_buffer; } | |
309 const T* buffer() const { return m_buffer; } | |
310 size_t capacity() const { return m_capacity; } | |
311 | |
312 T* releaseBuffer() | |
313 { | |
314 T* buffer = m_buffer; | |
315 m_buffer = 0; | |
316 m_capacity = 0; | |
317 return buffer; | |
318 } | |
319 | |
320 protected: | |
321 VectorBufferBase() | |
322 : m_buffer(0) | |
323 , m_capacity(0) | |
324 { | |
325 } | |
326 | |
327 VectorBufferBase(T* buffer, size_t capacity) | |
328 : m_buffer(buffer) | |
329 , m_capacity(capacity) | |
330 { | |
331 } | |
332 | |
333 ~VectorBufferBase() | |
334 { | |
335 // FIXME: It would be nice to find a way to ASSERT that m_buffer has
n't leaked here. | |
336 } | |
337 | |
338 T* m_buffer; | |
339 unsigned m_capacity; // Must come last so that it packs cleanly with Ve
ctor::m_size on 64-bit. | |
340 }; | |
341 | |
342 template<typename T, size_t inlineCapacity> | |
343 class VectorBuffer; | |
344 | |
345 template<typename T> | |
346 class VectorBuffer<T, 0> : private VectorBufferBase<T> { | |
347 private: | |
348 typedef VectorBufferBase<T> Base; | |
349 public: | |
350 VectorBuffer() | |
351 { | |
352 } | |
353 | |
354 VectorBuffer(size_t capacity) | |
355 { | |
356 // Calling malloc(0) might take a lock and may actually do an | |
357 // allocation on some systems. | |
358 if (capacity) | |
359 allocateBuffer(capacity); | |
360 } | |
361 | |
362 ~VectorBuffer() | |
363 { | |
364 deallocateBuffer(buffer()); | |
365 } | |
366 | |
367 void swap(VectorBuffer<T, 0>& other) | |
368 { | |
369 std::swap(m_buffer, other.m_buffer); | |
370 std::swap(m_capacity, other.m_capacity); | |
371 } | |
372 | |
373 void restoreInlineBufferIfNeeded() { } | |
374 | |
375 using Base::allocateBuffer; | |
376 using Base::tryAllocateBuffer; | |
377 using Base::shouldReallocateBuffer; | |
378 using Base::reallocateBuffer; | |
379 using Base::deallocateBuffer; | |
380 | |
381 using Base::buffer; | |
382 using Base::capacity; | |
383 | |
384 using Base::releaseBuffer; | |
385 private: | |
386 using Base::m_buffer; | |
387 using Base::m_capacity; | |
388 }; | |
389 | |
390 template<typename T, size_t inlineCapacity> | |
391 class VectorBuffer : private VectorBufferBase<T> { | |
392 WTF_MAKE_NONCOPYABLE(VectorBuffer); | |
393 private: | |
394 typedef VectorBufferBase<T> Base; | |
395 public: | |
396 VectorBuffer() | |
397 : Base(inlineBuffer(), inlineCapacity) | |
398 { | |
399 } | |
400 | |
401 VectorBuffer(size_t capacity) | |
402 : Base(inlineBuffer(), inlineCapacity) | |
403 { | |
404 if (capacity > inlineCapacity) | |
405 Base::allocateBuffer(capacity); | |
406 } | |
407 | |
408 ~VectorBuffer() | |
409 { | |
410 deallocateBuffer(buffer()); | |
411 } | |
412 | |
413 void allocateBuffer(size_t newCapacity) | |
414 { | |
415 // FIXME: This should ASSERT(!m_buffer) to catch misuse/leaks. | |
416 if (newCapacity > inlineCapacity) | |
417 Base::allocateBuffer(newCapacity); | |
418 else { | |
419 m_buffer = inlineBuffer(); | |
420 m_capacity = inlineCapacity; | |
421 } | |
422 } | |
423 | |
424 bool tryAllocateBuffer(size_t newCapacity) | |
425 { | |
426 if (newCapacity > inlineCapacity) | |
427 return Base::tryAllocateBuffer(newCapacity); | |
428 m_buffer = inlineBuffer(); | |
429 m_capacity = inlineCapacity; | |
430 return true; | |
431 } | |
432 | |
433 void deallocateBuffer(T* bufferToDeallocate) | |
434 { | |
435 if (bufferToDeallocate == inlineBuffer()) | |
436 return; | |
437 Base::deallocateBuffer(bufferToDeallocate); | |
438 } | |
439 | |
440 bool shouldReallocateBuffer(size_t newCapacity) const | |
441 { | |
442 // We cannot reallocate the inline buffer. | |
443 return Base::shouldReallocateBuffer(newCapacity) && std::min(static_
cast<size_t>(m_capacity), newCapacity) > inlineCapacity; | |
444 } | |
445 | |
446 void reallocateBuffer(size_t newCapacity) | |
447 { | |
448 ASSERT(shouldReallocateBuffer(newCapacity)); | |
449 Base::reallocateBuffer(newCapacity); | |
450 } | |
451 | |
452 void swap(VectorBuffer<T, inlineCapacity>& other) | |
453 { | |
454 if (buffer() == inlineBuffer() && other.buffer() == other.inlineBuff
er()) { | |
455 WTF::swap(m_inlineBuffer, other.m_inlineBuffer); | |
456 std::swap(m_capacity, other.m_capacity); | |
457 } else if (buffer() == inlineBuffer()) { | |
458 m_buffer = other.m_buffer; | |
459 other.m_buffer = other.inlineBuffer(); | |
460 WTF::swap(m_inlineBuffer, other.m_inlineBuffer); | |
461 std::swap(m_capacity, other.m_capacity); | |
462 } else if (other.buffer() == other.inlineBuffer()) { | |
463 other.m_buffer = m_buffer; | |
464 m_buffer = inlineBuffer(); | |
465 WTF::swap(m_inlineBuffer, other.m_inlineBuffer); | |
466 std::swap(m_capacity, other.m_capacity); | |
467 } else { | |
468 std::swap(m_buffer, other.m_buffer); | |
469 std::swap(m_capacity, other.m_capacity); | |
470 } | |
471 } | |
472 | |
473 void restoreInlineBufferIfNeeded() | |
474 { | |
475 if (m_buffer) | |
476 return; | |
477 m_buffer = inlineBuffer(); | |
478 m_capacity = inlineCapacity; | |
479 } | |
480 | |
481 using Base::buffer; | |
482 using Base::capacity; | |
483 | |
484 T* releaseBuffer() | |
485 { | |
486 if (buffer() == inlineBuffer()) | |
487 return 0; | |
488 return Base::releaseBuffer(); | |
489 } | |
490 | |
491 private: | |
492 using Base::m_buffer; | |
493 using Base::m_capacity; | |
494 | |
495 static const size_t m_inlineBufferSize = inlineCapacity * sizeof(T); | |
496 T* inlineBuffer() { return reinterpret_cast_ptr<T*>(m_inlineBuffer.buffe
r); } | |
497 const T* inlineBuffer() const { return reinterpret_cast_ptr<const T*>(m_
inlineBuffer.buffer); } | |
498 | |
499 AlignedBuffer<m_inlineBufferSize, WTF_ALIGN_OF(T)> m_inlineBuffer; | |
500 }; | |
501 | |
502 template<typename T, size_t inlineCapacity = 0> | |
503 class Vector : private VectorBuffer<T, inlineCapacity> { | |
504 WTF_MAKE_FAST_ALLOCATED; | |
505 private: | |
506 typedef VectorBuffer<T, inlineCapacity> Base; | |
507 typedef VectorTypeOperations<T> TypeOperations; | |
508 | |
509 public: | |
510 typedef T ValueType; | |
511 | |
512 typedef T* iterator; | |
513 typedef const T* const_iterator; | |
514 typedef std::reverse_iterator<iterator> reverse_iterator; | |
515 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; | |
516 | |
517 Vector() | |
518 : m_size(0) | |
519 { | |
520 } | |
521 | |
522 explicit Vector(size_t size) | |
523 : Base(size) | |
524 , m_size(size) | |
525 { | |
526 if (begin()) | |
527 TypeOperations::initialize(begin(), end()); | |
528 } | |
529 | |
530 ~Vector() | |
531 { | |
532 if (m_size) | |
533 shrink(0); | |
534 } | |
535 | |
536 Vector(const Vector&); | |
537 template<size_t otherCapacity> | |
538 Vector(const Vector<T, otherCapacity>&); | |
539 | |
540 Vector& operator=(const Vector&); | |
541 template<size_t otherCapacity> | |
542 Vector& operator=(const Vector<T, otherCapacity>&); | |
543 | |
544 #if COMPILER_SUPPORTS(CXX_RVALUE_REFERENCES) | |
545 Vector(Vector&&); | |
546 Vector& operator=(Vector&&); | |
547 #endif | |
548 | |
549 size_t size() const { return m_size; } | |
550 size_t capacity() const { return Base::capacity(); } | |
551 bool isEmpty() const { return !size(); } | |
552 | |
553 T& at(size_t i) | |
554 { | |
555 RELEASE_ASSERT(i < size()); | |
556 return Base::buffer()[i]; | |
557 } | |
558 const T& at(size_t i) const | |
559 { | |
560 RELEASE_ASSERT(i < size()); | |
561 return Base::buffer()[i]; | |
562 } | |
563 | |
564 T& operator[](size_t i) { return at(i); } | |
565 const T& operator[](size_t i) const { return at(i); } | |
566 | |
567 T* data() { return Base::buffer(); } | |
568 const T* data() const { return Base::buffer(); } | |
569 | |
570 iterator begin() { return data(); } | |
571 iterator end() { return begin() + m_size; } | |
572 const_iterator begin() const { return data(); } | |
573 const_iterator end() const { return begin() + m_size; } | |
574 | |
575 reverse_iterator rbegin() { return reverse_iterator(end()); } | |
576 reverse_iterator rend() { return reverse_iterator(begin()); } | |
577 const_reverse_iterator rbegin() const { return const_reverse_iterator(en
d()); } | |
578 const_reverse_iterator rend() const { return const_reverse_iterator(begi
n()); } | |
579 | |
580 T& first() { return at(0); } | |
581 const T& first() const { return at(0); } | |
582 T& last() { return at(size() - 1); } | |
583 const T& last() const { return at(size() - 1); } | |
584 | |
585 template<typename U> bool contains(const U&) const; | |
586 template<typename U> size_t find(const U&) const; | |
587 template<typename U> size_t reverseFind(const U&) const; | |
588 | |
589 void shrink(size_t size); | |
590 void grow(size_t size); | |
591 void resize(size_t size); | |
592 void reserveCapacity(size_t newCapacity); | |
593 bool tryReserveCapacity(size_t newCapacity); | |
594 void reserveInitialCapacity(size_t initialCapacity); | |
595 void shrinkCapacity(size_t newCapacity); | |
596 void shrinkToFit() { shrinkCapacity(size()); } | |
597 | |
598 void clear() { shrinkCapacity(0); } | |
599 | |
600 template<typename U> void append(const U*, size_t); | |
601 template<typename U> void append(const U&); | |
602 template<typename U> void uncheckedAppend(const U& val); | |
603 template<size_t otherCapacity> void append(const Vector<T, otherCapacity
>&); | |
604 template<typename U, size_t otherCapacity> void appendVector(const Vecto
r<U, otherCapacity>&); | |
605 template<typename U> bool tryAppend(const U*, size_t); | |
606 | |
607 template<typename U> void insert(size_t position, const U*, size_t); | |
608 template<typename U> void insert(size_t position, const U&); | |
609 template<typename U, size_t c> void insert(size_t position, const Vector
<U, c>&); | |
610 | |
611 template<typename U> void prepend(const U*, size_t); | |
612 template<typename U> void prepend(const U&); | |
613 template<typename U, size_t c> void prepend(const Vector<U, c>&); | |
614 | |
615 void remove(size_t position); | |
616 void remove(size_t position, size_t length); | |
617 | |
618 void removeLast() | |
619 { | |
620 ASSERT(!isEmpty()); | |
621 shrink(size() - 1); | |
622 } | |
623 | |
624 Vector(size_t size, const T& val) | |
625 : Base(size) | |
626 , m_size(size) | |
627 { | |
628 if (begin()) | |
629 TypeOperations::uninitializedFill(begin(), end(), val); | |
630 } | |
631 | |
632 void fill(const T&, size_t); | |
633 void fill(const T& val) { fill(val, size()); } | |
634 | |
635 template<typename Iterator> void appendRange(Iterator start, Iterator en
d); | |
636 | |
637 T* releaseBuffer(); | |
638 | |
639 void swap(Vector<T, inlineCapacity>& other) | |
640 { | |
641 std::swap(m_size, other.m_size); | |
642 Base::swap(other); | |
643 } | |
644 | |
645 void reverse(); | |
646 | |
647 void checkConsistency(); | |
648 | |
649 private: | |
650 void expandCapacity(size_t newMinCapacity); | |
651 const T* expandCapacity(size_t newMinCapacity, const T*); | |
652 bool tryExpandCapacity(size_t newMinCapacity); | |
653 const T* tryExpandCapacity(size_t newMinCapacity, const T*); | |
654 template<typename U> U* expandCapacity(size_t newMinCapacity, U*); | |
655 template<typename U> void appendSlowCase(const U&); | |
656 | |
657 unsigned m_size; | |
658 | |
659 using Base::buffer; | |
660 using Base::capacity; | |
661 using Base::swap; | |
662 using Base::allocateBuffer; | |
663 using Base::deallocateBuffer; | |
664 using Base::tryAllocateBuffer; | |
665 using Base::shouldReallocateBuffer; | |
666 using Base::reallocateBuffer; | |
667 using Base::restoreInlineBufferIfNeeded; | |
668 using Base::releaseBuffer; | |
669 }; | |
670 | |
671 template<typename T, size_t inlineCapacity> | |
672 Vector<T, inlineCapacity>::Vector(const Vector& other) | |
673 : Base(other.capacity()) | |
674 , m_size(other.size()) | |
675 { | |
676 if (begin()) | |
677 TypeOperations::uninitializedCopy(other.begin(), other.end(), begin(
)); | |
678 } | |
679 | |
680 template<typename T, size_t inlineCapacity> | |
681 template<size_t otherCapacity> | |
682 Vector<T, inlineCapacity>::Vector(const Vector<T, otherCapacity>& other) | |
683 : Base(other.capacity()) | |
684 , m_size(other.size()) | |
685 { | |
686 if (begin()) | |
687 TypeOperations::uninitializedCopy(other.begin(), other.end(), begin(
)); | |
688 } | |
689 | |
690 template<typename T, size_t inlineCapacity> | |
691 Vector<T, inlineCapacity>& Vector<T, inlineCapacity>::operator=(const Vector
<T, inlineCapacity>& other) | |
692 { | |
693 if (&other == this) | |
694 return *this; | |
695 | |
696 if (size() > other.size()) | |
697 shrink(other.size()); | |
698 else if (other.size() > capacity()) { | |
699 clear(); | |
700 reserveCapacity(other.size()); | |
701 if (!begin()) | |
702 return *this; | |
703 } | |
704 | |
705 // Works around an assert in VS2010. See https://connect.microsoft.com/VisualStu
dio/feedback/details/558044/std-copy-should-not-check-dest-when-first-last | |
706 #if COMPILER(MSVC) && defined(_ITERATOR_DEBUG_LEVEL) && _ITERATOR_DEBUG_LEVEL | |
707 if (!begin()) | |
708 return *this; | |
709 #endif | |
710 | |
711 std::copy(other.begin(), other.begin() + size(), begin()); | |
712 TypeOperations::uninitializedCopy(other.begin() + size(), other.end(), e
nd()); | |
713 m_size = other.size(); | |
714 | |
715 return *this; | |
716 } | |
717 | |
718 inline bool typelessPointersAreEqual(const void* a, const void* b) { return
a == b; } | |
719 | |
720 template<typename T, size_t inlineCapacity> | |
721 template<size_t otherCapacity> | |
722 Vector<T, inlineCapacity>& Vector<T, inlineCapacity>::operator=(const Vector
<T, otherCapacity>& other) | |
723 { | |
724 // If the inline capacities match, we should call the more specific | |
725 // template. If the inline capacities don't match, the two objects | |
726 // shouldn't be allocated the same address. | |
727 ASSERT(!typelessPointersAreEqual(&other, this)); | |
728 | |
729 if (size() > other.size()) | |
730 shrink(other.size()); | |
731 else if (other.size() > capacity()) { | |
732 clear(); | |
733 reserveCapacity(other.size()); | |
734 if (!begin()) | |
735 return *this; | |
736 } | |
737 | |
738 // Works around an assert in VS2010. See https://connect.microsoft.com/VisualStu
dio/feedback/details/558044/std-copy-should-not-check-dest-when-first-last | |
739 #if COMPILER(MSVC) && defined(_ITERATOR_DEBUG_LEVEL) && _ITERATOR_DEBUG_LEVEL | |
740 if (!begin()) | |
741 return *this; | |
742 #endif | |
743 | |
744 std::copy(other.begin(), other.begin() + size(), begin()); | |
745 TypeOperations::uninitializedCopy(other.begin() + size(), other.end(), e
nd()); | |
746 m_size = other.size(); | |
747 | |
748 return *this; | |
749 } | |
750 | |
751 #if COMPILER_SUPPORTS(CXX_RVALUE_REFERENCES) | |
752 template<typename T, size_t inlineCapacity> | |
753 Vector<T, inlineCapacity>::Vector(Vector<T, inlineCapacity>&& other) | |
754 : m_size(0) | |
755 { | |
756 // It's a little weird to implement a move constructor using swap but th
is way we | |
757 // don't have to add a move constructor to VectorBuffer. | |
758 swap(other); | |
759 } | |
760 | |
761 template<typename T, size_t inlineCapacity> | |
762 Vector<T, inlineCapacity>& Vector<T, inlineCapacity>::operator=(Vector<T, in
lineCapacity>&& other) | |
763 { | |
764 swap(other); | |
765 return *this; | |
766 } | |
767 #endif | |
768 | |
769 template<typename T, size_t inlineCapacity> | |
770 template<typename U> | |
771 bool Vector<T, inlineCapacity>::contains(const U& value) const | |
772 { | |
773 return find(value) != notFound; | |
774 } | |
775 | |
776 template<typename T, size_t inlineCapacity> | |
777 template<typename U> | |
778 size_t Vector<T, inlineCapacity>::find(const U& value) const | |
779 { | |
780 const T* b = begin(); | |
781 const T* e = end(); | |
782 for (const T* iter = b; iter < e; ++iter) { | |
783 if (*iter == value) | |
784 return iter - b; | |
785 } | |
786 return notFound; | |
787 } | |
788 | |
789 template<typename T, size_t inlineCapacity> | |
790 template<typename U> | |
791 size_t Vector<T, inlineCapacity>::reverseFind(const U& value) const | |
792 { | |
793 const T* b = begin(); | |
794 const T* iter = end(); | |
795 while (iter > b) { | |
796 --iter; | |
797 if (*iter == value) | |
798 return iter - b; | |
799 } | |
800 return notFound; | |
801 } | |
802 | |
803 template<typename T, size_t inlineCapacity> | |
804 void Vector<T, inlineCapacity>::fill(const T& val, size_t newSize) | |
805 { | |
806 if (size() > newSize) | |
807 shrink(newSize); | |
808 else if (newSize > capacity()) { | |
809 clear(); | |
810 reserveCapacity(newSize); | |
811 if (!begin()) | |
812 return; | |
813 } | |
814 | |
815 std::fill(begin(), end(), val); | |
816 TypeOperations::uninitializedFill(end(), begin() + newSize, val); | |
817 m_size = newSize; | |
818 } | |
819 | |
820 template<typename T, size_t inlineCapacity> | |
821 template<typename Iterator> | |
822 void Vector<T, inlineCapacity>::appendRange(Iterator start, Iterator end) | |
823 { | |
824 for (Iterator it = start; it != end; ++it) | |
825 append(*it); | |
826 } | |
827 | |
828 template<typename T, size_t inlineCapacity> | |
829 void Vector<T, inlineCapacity>::expandCapacity(size_t newMinCapacity) | |
830 { | |
831 reserveCapacity(std::max(newMinCapacity, std::max(static_cast<size_t>(16
), capacity() + capacity() / 4 + 1))); | |
832 } | |
833 | |
834 template<typename T, size_t inlineCapacity> | |
835 const T* Vector<T, inlineCapacity>::expandCapacity(size_t newMinCapacity, co
nst T* ptr) | |
836 { | |
837 if (ptr < begin() || ptr >= end()) { | |
838 expandCapacity(newMinCapacity); | |
839 return ptr; | |
840 } | |
841 size_t index = ptr - begin(); | |
842 expandCapacity(newMinCapacity); | |
843 return begin() + index; | |
844 } | |
845 | |
846 template<typename T, size_t inlineCapacity> | |
847 bool Vector<T, inlineCapacity>::tryExpandCapacity(size_t newMinCapacity) | |
848 { | |
849 return tryReserveCapacity(std::max(newMinCapacity, std::max(static_cast<
size_t>(16), capacity() + capacity() / 4 + 1))); | |
850 } | |
851 | |
852 template<typename T, size_t inlineCapacity> | |
853 const T* Vector<T, inlineCapacity>::tryExpandCapacity(size_t newMinCapacity,
const T* ptr) | |
854 { | |
855 if (ptr < begin() || ptr >= end()) { | |
856 if (!tryExpandCapacity(newMinCapacity)) | |
857 return 0; | |
858 return ptr; | |
859 } | |
860 size_t index = ptr - begin(); | |
861 if (!tryExpandCapacity(newMinCapacity)) | |
862 return 0; | |
863 return begin() + index; | |
864 } | |
865 | |
866 template<typename T, size_t inlineCapacity> template<typename U> | |
867 inline U* Vector<T, inlineCapacity>::expandCapacity(size_t newMinCapacity, U
* ptr) | |
868 { | |
869 expandCapacity(newMinCapacity); | |
870 return ptr; | |
871 } | |
872 | |
873 template<typename T, size_t inlineCapacity> | |
874 inline void Vector<T, inlineCapacity>::resize(size_t size) | |
875 { | |
876 if (size <= m_size) | |
877 TypeOperations::destruct(begin() + size, end()); | |
878 else { | |
879 if (size > capacity()) | |
880 expandCapacity(size); | |
881 if (begin()) | |
882 TypeOperations::initialize(end(), begin() + size); | |
883 } | |
884 | |
885 m_size = size; | |
886 } | |
887 | |
888 template<typename T, size_t inlineCapacity> | |
889 void Vector<T, inlineCapacity>::shrink(size_t size) | |
890 { | |
891 ASSERT(size <= m_size); | |
892 TypeOperations::destruct(begin() + size, end()); | |
893 m_size = size; | |
894 } | |
895 | |
896 template<typename T, size_t inlineCapacity> | |
897 void Vector<T, inlineCapacity>::grow(size_t size) | |
898 { | |
899 ASSERT(size >= m_size); | |
900 if (size > capacity()) | |
901 expandCapacity(size); | |
902 if (begin()) | |
903 TypeOperations::initialize(end(), begin() + size); | |
904 m_size = size; | |
905 } | |
906 | |
907 template<typename T, size_t inlineCapacity> | |
908 void Vector<T, inlineCapacity>::reserveCapacity(size_t newCapacity) | |
909 { | |
910 if (newCapacity <= capacity()) | |
911 return; | |
912 T* oldBuffer = begin(); | |
913 T* oldEnd = end(); | |
914 Base::allocateBuffer(newCapacity); | |
915 if (begin()) | |
916 TypeOperations::move(oldBuffer, oldEnd, begin()); | |
917 Base::deallocateBuffer(oldBuffer); | |
918 } | |
919 | |
920 template<typename T, size_t inlineCapacity> | |
921 bool Vector<T, inlineCapacity>::tryReserveCapacity(size_t newCapacity) | |
922 { | |
923 if (newCapacity <= capacity()) | |
924 return true; | |
925 T* oldBuffer = begin(); | |
926 T* oldEnd = end(); | |
927 if (!Base::tryAllocateBuffer(newCapacity)) | |
928 return false; | |
929 ASSERT(begin()); | |
930 TypeOperations::move(oldBuffer, oldEnd, begin()); | |
931 Base::deallocateBuffer(oldBuffer); | |
932 return true; | |
933 } | |
934 | |
935 template<typename T, size_t inlineCapacity> | |
936 inline void Vector<T, inlineCapacity>::reserveInitialCapacity(size_t initial
Capacity) | |
937 { | |
938 ASSERT(!m_size); | |
939 ASSERT(capacity() == inlineCapacity); | |
940 if (initialCapacity > inlineCapacity) | |
941 Base::allocateBuffer(initialCapacity); | |
942 } | |
943 | |
944 template<typename T, size_t inlineCapacity> | |
945 void Vector<T, inlineCapacity>::shrinkCapacity(size_t newCapacity) | |
946 { | |
947 if (newCapacity >= capacity()) | |
948 return; | |
949 | |
950 if (newCapacity < size()) | |
951 shrink(newCapacity); | |
952 | |
953 T* oldBuffer = begin(); | |
954 if (newCapacity > 0) { | |
955 if (Base::shouldReallocateBuffer(newCapacity)) { | |
956 Base::reallocateBuffer(newCapacity); | |
957 return; | |
958 } | |
959 | |
960 T* oldEnd = end(); | |
961 Base::allocateBuffer(newCapacity); | |
962 if (begin() != oldBuffer) | |
963 TypeOperations::move(oldBuffer, oldEnd, begin()); | |
964 } | |
965 | |
966 Base::deallocateBuffer(oldBuffer); | |
967 Base::restoreInlineBufferIfNeeded(); | |
968 } | |
969 | |
970 // Templatizing these is better than just letting the conversion happen impl
icitly, | |
971 // because for instance it allows a PassRefPtr to be appended to a RefPtr ve
ctor | |
972 // without refcount thrash. | |
973 | |
974 template<typename T, size_t inlineCapacity> template<typename U> | |
975 void Vector<T, inlineCapacity>::append(const U* data, size_t dataSize) | |
976 { | |
977 size_t newSize = m_size + dataSize; | |
978 if (newSize > capacity()) { | |
979 data = expandCapacity(newSize, data); | |
980 if (!begin()) | |
981 return; | |
982 } | |
983 RELEASE_ASSERT(newSize >= m_size); | |
984 T* dest = end(); | |
985 for (size_t i = 0; i < dataSize; ++i) | |
986 new (NotNull, &dest[i]) T(data[i]); | |
987 m_size = newSize; | |
988 } | |
989 | |
990 template<typename T, size_t inlineCapacity> template<typename U> | |
991 bool Vector<T, inlineCapacity>::tryAppend(const U* data, size_t dataSize) | |
992 { | |
993 size_t newSize = m_size + dataSize; | |
994 if (newSize > capacity()) { | |
995 data = tryExpandCapacity(newSize, data); | |
996 if (!data) | |
997 return false; | |
998 ASSERT(begin()); | |
999 } | |
1000 if (newSize < m_size) | |
1001 return false; | |
1002 T* dest = end(); | |
1003 for (size_t i = 0; i < dataSize; ++i) | |
1004 new (NotNull, &dest[i]) T(data[i]); | |
1005 m_size = newSize; | |
1006 return true; | |
1007 } | |
1008 | |
1009 template<typename T, size_t inlineCapacity> template<typename U> | |
1010 ALWAYS_INLINE void Vector<T, inlineCapacity>::append(const U& val) | |
1011 { | |
1012 if (size() != capacity()) { | |
1013 new (NotNull, end()) T(val); | |
1014 ++m_size; | |
1015 return; | |
1016 } | |
1017 | |
1018 appendSlowCase(val); | |
1019 } | |
1020 | |
1021 template<typename T, size_t inlineCapacity> template<typename U> | |
1022 void Vector<T, inlineCapacity>::appendSlowCase(const U& val) | |
1023 { | |
1024 ASSERT(size() == capacity()); | |
1025 | |
1026 const U* ptr = &val; | |
1027 ptr = expandCapacity(size() + 1, ptr); | |
1028 if (!begin()) | |
1029 return; | |
1030 | |
1031 new (NotNull, end()) T(*ptr); | |
1032 ++m_size; | |
1033 } | |
1034 | |
1035 // This version of append saves a branch in the case where you know that the | |
1036 // vector's capacity is large enough for the append to succeed. | |
1037 | |
1038 template<typename T, size_t inlineCapacity> template<typename U> | |
1039 inline void Vector<T, inlineCapacity>::uncheckedAppend(const U& val) | |
1040 { | |
1041 ASSERT(size() < capacity()); | |
1042 const U* ptr = &val; | |
1043 new (NotNull, end()) T(*ptr); | |
1044 ++m_size; | |
1045 } | |
1046 | |
1047 // This method should not be called append, a better name would be appendEle
ments. | |
1048 // It could also be eliminated entirely, and call sites could just use | |
1049 // appendRange(val.begin(), val.end()). | |
1050 template<typename T, size_t inlineCapacity> template<size_t otherCapacity> | |
1051 inline void Vector<T, inlineCapacity>::append(const Vector<T, otherCapacity>
& val) | |
1052 { | |
1053 append(val.begin(), val.size()); | |
1054 } | |
1055 | |
1056 template<typename T, size_t inlineCapacity> template<typename U, size_t othe
rCapacity> | |
1057 inline void Vector<T, inlineCapacity>::appendVector(const Vector<U, otherCap
acity>& val) | |
1058 { | |
1059 append(val.begin(), val.size()); | |
1060 } | |
1061 | |
1062 template<typename T, size_t inlineCapacity> template<typename U> | |
1063 void Vector<T, inlineCapacity>::insert(size_t position, const U* data, size_
t dataSize) | |
1064 { | |
1065 ASSERT_WITH_SECURITY_IMPLICATION(position <= size()); | |
1066 size_t newSize = m_size + dataSize; | |
1067 if (newSize > capacity()) { | |
1068 data = expandCapacity(newSize, data); | |
1069 if (!begin()) | |
1070 return; | |
1071 } | |
1072 RELEASE_ASSERT(newSize >= m_size); | |
1073 T* spot = begin() + position; | |
1074 TypeOperations::moveOverlapping(spot, end(), spot + dataSize); | |
1075 for (size_t i = 0; i < dataSize; ++i) | |
1076 new (NotNull, &spot[i]) T(data[i]); | |
1077 m_size = newSize; | |
1078 } | |
1079 | |
1080 template<typename T, size_t inlineCapacity> template<typename U> | |
1081 inline void Vector<T, inlineCapacity>::insert(size_t position, const U& val) | |
1082 { | |
1083 ASSERT_WITH_SECURITY_IMPLICATION(position <= size()); | |
1084 const U* data = &val; | |
1085 if (size() == capacity()) { | |
1086 data = expandCapacity(size() + 1, data); | |
1087 if (!begin()) | |
1088 return; | |
1089 } | |
1090 T* spot = begin() + position; | |
1091 TypeOperations::moveOverlapping(spot, end(), spot + 1); | |
1092 new (NotNull, spot) T(*data); | |
1093 ++m_size; | |
1094 } | |
1095 | |
1096 template<typename T, size_t inlineCapacity> template<typename U, size_t c> | |
1097 inline void Vector<T, inlineCapacity>::insert(size_t position, const Vector<
U, c>& val) | |
1098 { | |
1099 insert(position, val.begin(), val.size()); | |
1100 } | |
1101 | |
1102 template<typename T, size_t inlineCapacity> template<typename U> | |
1103 void Vector<T, inlineCapacity>::prepend(const U* data, size_t dataSize) | |
1104 { | |
1105 insert(0, data, dataSize); | |
1106 } | |
1107 | |
1108 template<typename T, size_t inlineCapacity> template<typename U> | |
1109 inline void Vector<T, inlineCapacity>::prepend(const U& val) | |
1110 { | |
1111 insert(0, val); | |
1112 } | |
1113 | |
1114 template<typename T, size_t inlineCapacity> template<typename U, size_t c> | |
1115 inline void Vector<T, inlineCapacity>::prepend(const Vector<U, c>& val) | |
1116 { | |
1117 insert(0, val.begin(), val.size()); | |
1118 } | |
1119 | |
1120 template<typename T, size_t inlineCapacity> | |
1121 inline void Vector<T, inlineCapacity>::remove(size_t position) | |
1122 { | |
1123 ASSERT_WITH_SECURITY_IMPLICATION(position < size()); | |
1124 T* spot = begin() + position; | |
1125 spot->~T(); | |
1126 TypeOperations::moveOverlapping(spot + 1, end(), spot); | |
1127 --m_size; | |
1128 } | |
1129 | |
1130 template<typename T, size_t inlineCapacity> | |
1131 inline void Vector<T, inlineCapacity>::remove(size_t position, size_t length
) | |
1132 { | |
1133 ASSERT_WITH_SECURITY_IMPLICATION(position <= size()); | |
1134 ASSERT_WITH_SECURITY_IMPLICATION(position + length <= size()); | |
1135 T* beginSpot = begin() + position; | |
1136 T* endSpot = beginSpot + length; | |
1137 TypeOperations::destruct(beginSpot, endSpot); | |
1138 TypeOperations::moveOverlapping(endSpot, end(), beginSpot); | |
1139 m_size -= length; | |
1140 } | |
1141 | |
1142 template<typename T, size_t inlineCapacity> | |
1143 inline void Vector<T, inlineCapacity>::reverse() | |
1144 { | |
1145 for (size_t i = 0; i < m_size / 2; ++i) | |
1146 std::swap(at(i), at(m_size - 1 - i)); | |
1147 } | |
1148 | |
1149 template<typename T, size_t inlineCapacity> | |
1150 inline T* Vector<T, inlineCapacity>::releaseBuffer() | |
1151 { | |
1152 T* buffer = Base::releaseBuffer(); | |
1153 if (inlineCapacity && !buffer && m_size) { | |
1154 // If the vector had some data, but no buffer to release, | |
1155 // that means it was using the inline buffer. In that case, | |
1156 // we create a brand new buffer so the caller always gets one. | |
1157 size_t bytes = m_size * sizeof(T); | |
1158 buffer = static_cast<T*>(fastMalloc(bytes)); | |
1159 memcpy(buffer, data(), bytes); | |
1160 } | |
1161 m_size = 0; | |
1162 return buffer; | |
1163 } | |
1164 | |
1165 template<typename T, size_t inlineCapacity> | |
1166 inline void Vector<T, inlineCapacity>::checkConsistency() | |
1167 { | |
1168 #if !ASSERT_DISABLED | |
1169 for (size_t i = 0; i < size(); ++i) | |
1170 ValueCheck<T>::checkConsistency(at(i)); | |
1171 #endif | |
1172 } | |
1173 | |
1174 template<typename T, size_t inlineCapacity> | |
1175 void deleteAllValues(const Vector<T, inlineCapacity>& collection) | |
1176 { | |
1177 typedef typename Vector<T, inlineCapacity>::const_iterator iterator; | |
1178 iterator end = collection.end(); | |
1179 for (iterator it = collection.begin(); it != end; ++it) | |
1180 delete *it; | |
1181 } | |
1182 | |
1183 template<typename T, size_t inlineCapacity> | |
1184 inline void swap(Vector<T, inlineCapacity>& a, Vector<T, inlineCapacity>& b) | |
1185 { | |
1186 a.swap(b); | |
1187 } | |
1188 | |
1189 template<typename T, size_t inlineCapacity> | |
1190 bool operator==(const Vector<T, inlineCapacity>& a, const Vector<T, inlineCa
pacity>& b) | |
1191 { | |
1192 if (a.size() != b.size()) | |
1193 return false; | |
1194 | |
1195 return VectorTypeOperations<T>::compare(a.data(), b.data(), a.size()); | |
1196 } | |
1197 | |
1198 template<typename T, size_t inlineCapacity> | |
1199 inline bool operator!=(const Vector<T, inlineCapacity>& a, const Vector<T, i
nlineCapacity>& b) | |
1200 { | |
1201 return !(a == b); | |
1202 } | |
1203 | |
1204 #if !ASSERT_DISABLED | |
1205 template<typename T> struct ValueCheck<Vector<T> > { | |
1206 typedef Vector<T> TraitType; | |
1207 static void checkConsistency(const Vector<T>& v) | |
1208 { | |
1209 v.checkConsistency(); | |
1210 } | |
1211 }; | |
1212 #endif | |
1213 | |
1214 } // namespace WTF | |
1215 | |
1216 using WTF::Vector; | |
1217 | |
1218 #endif // WTF_Vector_h | |
OLD | NEW |