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 "FastAllocBase.h" |
25 | #include "Noncopyable.h" |
26 | #include "NotFound.h" |
27 | #include "VectorTraits.h" |
28 | #include <limits> |
29 | #include <utility> |
30 | |
31 | #if PLATFORM(QT) |
32 | #include <QtCore/qdatastream.h> |
33 | #endif |
34 | |
35 | namespace WTF { |
36 | |
37 | using std::min; |
38 | using std::max; |
39 | |
40 | // WTF_ALIGN_OF / WTF_ALIGNED |
41 | #if COMPILER(GCC) || COMPILER(MINGW) || COMPILER(RVCT) || COMPILER(WINSCW) |
42 | #define WTF_ALIGN_OF(type) __alignof__(type) |
43 | #define WTF_ALIGNED(variable_type, variable, n) variable_type variable __attribute__((__aligned__(n))) |
44 | #elif COMPILER(MSVC) |
45 | #define WTF_ALIGN_OF(type) __alignof(type) |
46 | #define WTF_ALIGNED(variable_type, variable, n) __declspec(align(n)) variable_type variable |
47 | #else |
48 | #define WTF_ALIGN_OF(type) 0 |
49 | #endif |
50 | |
51 | #if COMPILER(GCC) && !COMPILER(INTEL) && (((__GNUC__ * 100) + __GNUC_MINOR__) >= 303) |
52 | typedef char __attribute__((__may_alias__)) AlignedBufferChar; |
53 | #else |
54 | typedef char AlignedBufferChar; |
55 | #endif |
56 | |
57 | #ifdef WTF_ALIGNED |
58 | template <size_t size, size_t alignment> struct AlignedBuffer; |
59 | template <size_t size> struct AlignedBuffer<size, 1> { AlignedBufferChar buffer[size]; }; |
60 | template <size_t size> struct AlignedBuffer<size, 2> { WTF_ALIGNED(AlignedBufferChar, buffer[size], 2); }; |
61 | template <size_t size> struct AlignedBuffer<size, 4> { WTF_ALIGNED(AlignedBufferChar, buffer[size], 4); }; |
62 | template <size_t size> struct AlignedBuffer<size, 8> { WTF_ALIGNED(AlignedBufferChar, buffer[size], 8); }; |
63 | template <size_t size> struct AlignedBuffer<size, 16> { WTF_ALIGNED(AlignedBufferChar, buffer[size], 16); }; |
64 | template <size_t size> struct AlignedBuffer<size, 32> { WTF_ALIGNED(AlignedBufferChar, buffer[size], 32); }; |
65 | template <size_t size> struct AlignedBuffer<size, 64> { WTF_ALIGNED(AlignedBufferChar, buffer[size], 64); }; |
66 | #else |
67 | template <size_t size, size_t> struct AlignedBuffer |
68 | { |
69 | AlignedBufferChar oversizebuffer[size + 64]; |
70 | AlignedBufferChar *buffer() |
71 | { |
72 | AlignedBufferChar *ptr = oversizebuffer; |
73 | ptr += 64 - (reinterpret_cast<size_t>(ptr) & 0x3f); |
74 | return ptr; |
75 | } |
76 | }; |
77 | #endif |
78 | |
79 | template <size_t size, size_t alignment> |
80 | void swap(AlignedBuffer<size, alignment>& a, AlignedBuffer<size, alignment>& b) |
81 | { |
82 | for (size_t i = 0; i < size; ++i) |
83 | std::swap(a.buffer[i], b.buffer[i]); |
84 | } |
85 | |
86 | template <bool needsDestruction, typename T> |
87 | struct VectorDestructor; |
88 | |
89 | template<typename T> |
90 | struct VectorDestructor<false, T> |
91 | { |
92 | static void destruct(T*, T*) {} |
93 | }; |
94 | |
95 | template<typename T> |
96 | struct VectorDestructor<true, T> |
97 | { |
98 | static void destruct(T* begin, T* end) |
99 | { |
100 | for (T* cur = begin; cur != end; ++cur) |
101 | cur->~T(); |
102 | } |
103 | }; |
104 | |
105 | template <bool needsInitialization, bool canInitializeWithMemset, typename T> |
106 | struct VectorInitializer; |
107 | |
108 | template<bool ignore, typename T> |
109 | struct VectorInitializer<false, ignore, T> |
110 | { |
111 | static void initialize(T*, T*) {} |
112 | }; |
113 | |
114 | template<typename T> |
115 | struct VectorInitializer<true, false, T> |
116 | { |
117 | static void initialize(T* begin, T* end) |
118 | { |
119 | for (T* cur = begin; cur != end; ++cur) |
120 | new (cur) T; |
121 | } |
122 | }; |
123 | |
124 | template<typename T> |
125 | struct VectorInitializer<true, true, T> |
126 | { |
127 | static void initialize(T* begin, T* end) |
128 | { |
129 | memset(begin, 0, reinterpret_cast<char*>(end) - reinterpret_cast<char*>(begin)); |
130 | } |
131 | }; |
132 | |
133 | template <bool canMoveWithMemcpy, typename T> |
134 | struct VectorMover; |
135 | |
136 | template<typename T> |
137 | struct VectorMover<false, T> |
138 | { |
139 | static void move(T* src, const T* srcEnd, T* dst) |
140 | { |
141 | while (src != srcEnd) { |
142 | new (dst) T(*src); |
143 | src->~T(); |
144 | ++dst; |
145 | ++src; |
146 | } |
147 | } |
148 | static void moveOverlapping(T* src, const T* srcEnd, T* dst) |
149 | { |
150 | if (src > dst) |
151 | move(src, srcEnd, dst); |
152 | else { |
153 | T* dstEnd = dst + (srcEnd - src); |
154 | while (src != srcEnd) { |
155 | --srcEnd; |
156 | --dstEnd; |
157 | new (dstEnd) T(*srcEnd); |
158 | srcEnd->~T(); |
159 | } |
160 | } |
161 | } |
162 | }; |
163 | |
164 | template<typename T> |
165 | struct VectorMover<true, T> |
166 | { |
167 | static void move(T* src, const T* srcEnd, T* dst) |
168 | { |
169 | memcpy(dst, src, reinterpret_cast<const char*>(srcEnd) - reinterpret_cast<const char*>(src)); |
170 | } |
171 | static void moveOverlapping(T* src, const T* srcEnd, T* dst) |
172 | { |
173 | memmove(dst, src, reinterpret_cast<const char*>(srcEnd) - reinterpret_cast<const char*>(src)); |
174 | } |
175 | }; |
176 | |
177 | template <bool canCopyWithMemcpy, typename T> |
178 | struct VectorCopier; |
179 | |
180 | template<typename T> |
181 | struct VectorCopier<false, T> |
182 | { |
183 | static void uninitializedCopy(const T* src, const T* srcEnd, T* dst) |
184 | { |
185 | while (src != srcEnd) { |
186 | new (dst) T(*src); |
187 | ++dst; |
188 | ++src; |
189 | } |
190 | } |
191 | }; |
192 | |
193 | template<typename T> |
194 | struct VectorCopier<true, T> |
195 | { |
196 | static void uninitializedCopy(const T* src, const T* srcEnd, T* dst) |
197 | { |
198 | memcpy(dst, src, reinterpret_cast<const char*>(srcEnd) - reinterpret_cast<const char*>(src)); |
199 | } |
200 | }; |
201 | |
202 | template <bool canFillWithMemset, typename T> |
203 | struct VectorFiller; |
204 | |
205 | template<typename T> |
206 | struct VectorFiller<false, T> |
207 | { |
208 | static void uninitializedFill(T* dst, T* dstEnd, const T& val) |
209 | { |
210 | while (dst != dstEnd) { |
211 | new (dst) T(val); |
212 | ++dst; |
213 | } |
214 | } |
215 | }; |
216 | |
217 | template<typename T> |
218 | struct VectorFiller<true, T> |
219 | { |
220 | static void uninitializedFill(T* dst, T* dstEnd, const T& val) |
221 | { |
222 | ASSERT(sizeof(T) == sizeof(char)); |
223 | memset(dst, val, dstEnd - dst); |
224 | } |
225 | }; |
226 | |
227 | template<bool canCompareWithMemcmp, typename T> |
228 | struct VectorComparer; |
229 | |
230 | template<typename T> |
231 | struct VectorComparer<false, T> |
232 | { |
233 | static bool compare(const T* a, const T* b, size_t size) |
234 | { |
235 | for (size_t i = 0; i < size; ++i) |
236 | if (a[i] != b[i]) |
237 | return false; |
238 | return true; |
239 | } |
240 | }; |
241 | |
242 | template<typename T> |
243 | struct VectorComparer<true, T> |
244 | { |
245 | static bool compare(const T* a, const T* b, size_t size) |
246 | { |
247 | return memcmp(a, b, sizeof(T) * size) == 0; |
248 | } |
249 | }; |
250 | |
251 | template<typename T> |
252 | struct VectorTypeOperations |
253 | { |
254 | static void destruct(T* begin, T* end) |
255 | { |
256 | VectorDestructor<VectorTraits<T>::needsDestruction, T>::destruct(begin, end); |
257 | } |
258 | |
259 | static void initialize(T* begin, T* end) |
260 | { |
261 | VectorInitializer<VectorTraits<T>::needsInitialization, VectorTraits<T>::canInitializeWithMemset, T>::initialize(begin, end); |
262 | } |
263 | |
264 | static void move(T* src, const T* srcEnd, T* dst) |
265 | { |
266 | VectorMover<VectorTraits<T>::canMoveWithMemcpy, T>::move(src, srcEnd, dst); |
267 | } |
268 | |
269 | static void moveOverlapping(T* src, const T* srcEnd, T* dst) |
270 | { |
271 | VectorMover<VectorTraits<T>::canMoveWithMemcpy, T>::moveOverlapping(src, srcEnd, dst); |
272 | } |
273 | |
274 | static void uninitializedCopy(const T* src, const T* srcEnd, T* dst) |
275 | { |
276 | VectorCopier<VectorTraits<T>::canCopyWithMemcpy, T>::uninitializedCopy(src, srcEnd, dst); |
277 | } |
278 | |
279 | static void uninitializedFill(T* dst, T* dstEnd, const T& val) |
280 | { |
281 | VectorFiller<VectorTraits<T>::canFillWithMemset, T>::uninitializedFill(dst, dstEnd, val); |
282 | } |
283 | |
284 | static bool compare(const T* a, const T* b, size_t size) |
285 | { |
286 | return VectorComparer<VectorTraits<T>::canCompareWithMemcmp, T>::compare(a, b, size); |
287 | } |
288 | }; |
289 | |
290 | template<typename T> |
291 | class VectorBufferBase : public Noncopyable { |
292 | public: |
293 | void allocateBuffer(size_t newCapacity) |
294 | { |
295 | m_capacity = newCapacity; |
296 | if (newCapacity > std::numeric_limits<size_t>::max() / sizeof(T)) |
297 | CRASH(); |
298 | m_buffer = static_cast<T*>(fastMalloc(newCapacity * sizeof(T))); |
299 | } |
300 | |
301 | void deallocateBuffer(T* bufferToDeallocate) |
302 | { |
303 | if (m_buffer == bufferToDeallocate) { |
304 | m_buffer = 0; |
305 | m_capacity = 0; |
306 | } |
307 | fastFree(bufferToDeallocate); |
308 | } |
309 | |
310 | T* buffer() { return m_buffer; } |
311 | const T* buffer() const { return m_buffer; } |
312 | T** bufferSlot() { return &m_buffer; } |
313 | size_t capacity() const { return m_capacity; } |
314 | |
315 | T* releaseBuffer() |
316 | { |
317 | T* buffer = m_buffer; |
318 | m_buffer = 0; |
319 | m_capacity = 0; |
320 | return buffer; |
321 | } |
322 | |
323 | protected: |
324 | VectorBufferBase() |
325 | : m_buffer(0) |
326 | , m_capacity(0) |
327 | { |
328 | } |
329 | |
330 | VectorBufferBase(T* buffer, size_t capacity) |
331 | : m_buffer(buffer) |
332 | , m_capacity(capacity) |
333 | { |
334 | } |
335 | |
336 | ~VectorBufferBase() |
337 | { |
338 | // FIXME: It would be nice to find a way to ASSERT that m_buffer hasn't leaked here. |
339 | } |
340 | |
341 | T* m_buffer; |
342 | size_t m_capacity; |
343 | }; |
344 | |
345 | template<typename T, size_t inlineCapacity> |
346 | class VectorBuffer; |
347 | |
348 | template<typename T> |
349 | class VectorBuffer<T, 0> : private VectorBufferBase<T> { |
350 | private: |
351 | typedef VectorBufferBase<T> Base; |
352 | public: |
353 | VectorBuffer() |
354 | { |
355 | } |
356 | |
357 | VectorBuffer(size_t capacity) |
358 | { |
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::deallocateBuffer; |
377 | |
378 | using Base::buffer; |
379 | using Base::bufferSlot; |
380 | using Base::capacity; |
381 | |
382 | using Base::releaseBuffer; |
383 | private: |
384 | using Base::m_buffer; |
385 | using Base::m_capacity; |
386 | }; |
387 | |
388 | template<typename T, size_t inlineCapacity> |
389 | class VectorBuffer : private VectorBufferBase<T> { |
390 | private: |
391 | typedef VectorBufferBase<T> Base; |
392 | public: |
393 | VectorBuffer() |
394 | : Base(inlineBuffer(), inlineCapacity) |
395 | { |
396 | } |
397 | |
398 | VectorBuffer(size_t capacity) |
399 | : Base(inlineBuffer(), inlineCapacity) |
400 | { |
401 | if (capacity > inlineCapacity) |
402 | Base::allocateBuffer(capacity); |
403 | } |
404 | |
405 | ~VectorBuffer() |
406 | { |
407 | deallocateBuffer(bufferToDeallocate: buffer()); |
408 | } |
409 | |
410 | void allocateBuffer(size_t newCapacity) |
411 | { |
412 | if (newCapacity > inlineCapacity) |
413 | Base::allocateBuffer(newCapacity); |
414 | else { |
415 | m_buffer = inlineBuffer(); |
416 | m_capacity = inlineCapacity; |
417 | } |
418 | } |
419 | |
420 | void deallocateBuffer(T* bufferToDeallocate) |
421 | { |
422 | if (bufferToDeallocate == inlineBuffer()) |
423 | return; |
424 | Base::deallocateBuffer(bufferToDeallocate); |
425 | } |
426 | |
427 | void swap(VectorBuffer<T, inlineCapacity>& other) |
428 | { |
429 | if (buffer() == inlineBuffer() && other.buffer() == other.inlineBuffer()) { |
430 | WTF::swap(m_inlineBuffer, other.m_inlineBuffer); |
431 | std::swap(m_capacity, other.m_capacity); |
432 | } else if (buffer() == inlineBuffer()) { |
433 | m_buffer = other.m_buffer; |
434 | other.m_buffer = other.inlineBuffer(); |
435 | WTF::swap(m_inlineBuffer, other.m_inlineBuffer); |
436 | std::swap(m_capacity, other.m_capacity); |
437 | } else if (other.buffer() == other.inlineBuffer()) { |
438 | other.m_buffer = m_buffer; |
439 | m_buffer = inlineBuffer(); |
440 | WTF::swap(m_inlineBuffer, other.m_inlineBuffer); |
441 | std::swap(m_capacity, other.m_capacity); |
442 | } else { |
443 | std::swap(m_buffer, other.m_buffer); |
444 | std::swap(m_capacity, other.m_capacity); |
445 | } |
446 | } |
447 | |
448 | void restoreInlineBufferIfNeeded() |
449 | { |
450 | if (m_buffer) |
451 | return; |
452 | m_buffer = inlineBuffer(); |
453 | m_capacity = inlineCapacity; |
454 | } |
455 | |
456 | using Base::buffer; |
457 | using Base::bufferSlot; |
458 | using Base::capacity; |
459 | |
460 | T* releaseBuffer() |
461 | { |
462 | if (buffer() == inlineBuffer()) |
463 | return 0; |
464 | return Base::releaseBuffer(); |
465 | } |
466 | |
467 | private: |
468 | using Base::m_buffer; |
469 | using Base::m_capacity; |
470 | |
471 | static const size_t m_inlineBufferSize = inlineCapacity * sizeof(T); |
472 | #ifdef WTF_ALIGNED |
473 | T* inlineBuffer() { return reinterpret_cast<T*>(m_inlineBuffer.buffer); } |
474 | #else |
475 | T* inlineBuffer() { return reinterpret_cast<T*>(m_inlineBuffer.buffer()); } |
476 | #endif |
477 | |
478 | AlignedBuffer<m_inlineBufferSize, WTF_ALIGN_OF(T)> m_inlineBuffer; |
479 | }; |
480 | |
481 | template<typename T, size_t inlineCapacity = 0> |
482 | class Vector : public FastAllocBase { |
483 | private: |
484 | typedef VectorBuffer<T, inlineCapacity> Buffer; |
485 | typedef VectorTypeOperations<T> TypeOperations; |
486 | |
487 | public: |
488 | typedef T ValueType; |
489 | |
490 | typedef T* iterator; |
491 | typedef const T* const_iterator; |
492 | |
493 | Vector() |
494 | : m_size(0) |
495 | { |
496 | } |
497 | |
498 | explicit Vector(size_t size) |
499 | : m_size(size) |
500 | , m_buffer(size) |
501 | { |
502 | if (begin()) |
503 | TypeOperations::initialize(begin(), end()); |
504 | } |
505 | |
506 | ~Vector() |
507 | { |
508 | if (m_size) shrink(size: 0); |
509 | } |
510 | |
511 | Vector(const Vector&); |
512 | template<size_t otherCapacity> |
513 | Vector(const Vector<T, otherCapacity>&); |
514 | |
515 | Vector& operator=(const Vector&); |
516 | template<size_t otherCapacity> |
517 | Vector& operator=(const Vector<T, otherCapacity>&); |
518 | |
519 | size_t size() const { return m_size; } |
520 | size_t capacity() const { return m_buffer.capacity(); } |
521 | bool isEmpty() const { return !size(); } |
522 | |
523 | T& at(size_t i) |
524 | { |
525 | ASSERT(i < size()); |
526 | return m_buffer.buffer()[i]; |
527 | } |
528 | const T& at(size_t i) const |
529 | { |
530 | ASSERT(i < size()); |
531 | return m_buffer.buffer()[i]; |
532 | } |
533 | |
534 | T& operator[](size_t i) { return at(i); } |
535 | const T& operator[](size_t i) const { return at(i); } |
536 | |
537 | T* data() { return m_buffer.buffer(); } |
538 | const T* data() const { return m_buffer.buffer(); } |
539 | T** dataSlot() { return m_buffer.bufferSlot(); } |
540 | |
541 | iterator begin() { return data(); } |
542 | iterator end() { return begin() + m_size; } |
543 | const_iterator begin() const { return data(); } |
544 | const_iterator end() const { return begin() + m_size; } |
545 | |
546 | T& first() { return at(0); } |
547 | const T& first() const { return at(0); } |
548 | T& last() { return at(size() - 1); } |
549 | const T& last() const { return at(size() - 1); } |
550 | |
551 | template<typename U> size_t find(const U&) const; |
552 | |
553 | void shrink(size_t size); |
554 | void grow(size_t size); |
555 | void resize(size_t size); |
556 | void reserveCapacity(size_t newCapacity); |
557 | void reserveInitialCapacity(size_t initialCapacity); |
558 | void shrinkCapacity(size_t newCapacity); |
559 | void shrinkToFit() { shrinkCapacity(newCapacity: size()); } |
560 | |
561 | void clear() { shrinkCapacity(newCapacity: 0); } |
562 | |
563 | template<typename U> void append(const U*, size_t); |
564 | template<typename U> void append(const U&); |
565 | template<typename U> void uncheckedAppend(const U& val); |
566 | template<size_t otherCapacity> void append(const Vector<T, otherCapacity>&); |
567 | |
568 | template<typename U> void insert(size_t position, const U*, size_t); |
569 | template<typename U> void insert(size_t position, const U&); |
570 | template<typename U, size_t c> void insert(size_t position, const Vector<U, c>&); |
571 | |
572 | template<typename U> void prepend(const U*, size_t); |
573 | template<typename U> void prepend(const U&); |
574 | template<typename U, size_t c> void prepend(const Vector<U, c>&); |
575 | |
576 | void remove(size_t position); |
577 | void remove(size_t position, size_t length); |
578 | |
579 | void removeLast() |
580 | { |
581 | ASSERT(!isEmpty()); |
582 | shrink(size: size() - 1); |
583 | } |
584 | |
585 | Vector(size_t size, const T& val) |
586 | : m_size(size) |
587 | , m_buffer(size) |
588 | { |
589 | if (begin()) |
590 | TypeOperations::uninitializedFill(begin(), end(), val); |
591 | } |
592 | |
593 | void fill(const T&, size_t); |
594 | void fill(const T& val) { fill(val, size()); } |
595 | |
596 | template<typename Iterator> void appendRange(Iterator start, Iterator end); |
597 | |
598 | T* releaseBuffer(); |
599 | |
600 | void swap(Vector<T, inlineCapacity>& other) |
601 | { |
602 | std::swap(m_size, other.m_size); |
603 | m_buffer.swap(other.m_buffer); |
604 | } |
605 | |
606 | private: |
607 | void expandCapacity(size_t newMinCapacity); |
608 | const T* expandCapacity(size_t newMinCapacity, const T*); |
609 | template<typename U> U* expandCapacity(size_t newMinCapacity, U*); |
610 | |
611 | size_t m_size; |
612 | Buffer m_buffer; |
613 | }; |
614 | |
615 | #if PLATFORM(QT) |
616 | QT_USE_NAMESPACE |
617 | template<typename T> |
618 | QDataStream& operator<<(QDataStream& stream, const Vector<T>& data) |
619 | { |
620 | stream << qint64(data.size()); |
621 | for (const T& i : data) |
622 | stream << i; |
623 | return stream; |
624 | } |
625 | |
626 | template<typename T> |
627 | QDataStream& operator>>(QDataStream& stream, Vector<T>& data) |
628 | { |
629 | data.clear(); |
630 | qint64 count; |
631 | T item; |
632 | stream >> count; |
633 | data.reserveCapacity(count); |
634 | for (qint64 i = 0; i < count; ++i) { |
635 | stream >> item; |
636 | data.append(item); |
637 | } |
638 | return stream; |
639 | } |
640 | #endif |
641 | |
642 | template<typename T, size_t inlineCapacity> |
643 | Vector<T, inlineCapacity>::Vector(const Vector& other) |
644 | : m_size(other.size()) |
645 | , m_buffer(other.capacity()) |
646 | { |
647 | if (begin()) |
648 | TypeOperations::uninitializedCopy(other.begin(), other.end(), begin()); |
649 | } |
650 | |
651 | template<typename T, size_t inlineCapacity> |
652 | template<size_t otherCapacity> |
653 | Vector<T, inlineCapacity>::Vector(const Vector<T, otherCapacity>& other) |
654 | : m_size(other.size()) |
655 | , m_buffer(other.capacity()) |
656 | { |
657 | if (begin()) |
658 | TypeOperations::uninitializedCopy(other.begin(), other.end(), begin()); |
659 | } |
660 | |
661 | template<typename T, size_t inlineCapacity> |
662 | Vector<T, inlineCapacity>& Vector<T, inlineCapacity>::operator=(const Vector<T, inlineCapacity>& other) |
663 | { |
664 | if (&other == this) |
665 | return *this; |
666 | |
667 | if (size() > other.size()) |
668 | shrink(size: other.size()); |
669 | else if (other.size() > capacity()) { |
670 | clear(); |
671 | reserveCapacity(newCapacity: other.size()); |
672 | if (!begin()) |
673 | return *this; |
674 | } |
675 | |
676 | std::copy(other.begin(), other.begin() + size(), begin()); |
677 | TypeOperations::uninitializedCopy(other.begin() + size(), other.end(), end()); |
678 | m_size = other.size(); |
679 | |
680 | return *this; |
681 | } |
682 | |
683 | template<typename T, size_t inlineCapacity> |
684 | template<size_t otherCapacity> |
685 | Vector<T, inlineCapacity>& Vector<T, inlineCapacity>::operator=(const Vector<T, otherCapacity>& other) |
686 | { |
687 | if (&other == this) |
688 | return *this; |
689 | |
690 | if (size() > other.size()) |
691 | shrink(size: other.size()); |
692 | else if (other.size() > capacity()) { |
693 | clear(); |
694 | reserveCapacity(newCapacity: other.size()); |
695 | if (!begin()) |
696 | return *this; |
697 | } |
698 | |
699 | std::copy(other.begin(), other.begin() + size(), begin()); |
700 | TypeOperations::uninitializedCopy(other.begin() + size(), other.end(), end()); |
701 | m_size = other.size(); |
702 | |
703 | return *this; |
704 | } |
705 | |
706 | template<typename T, size_t inlineCapacity> |
707 | template<typename U> |
708 | size_t Vector<T, inlineCapacity>::find(const U& value) const |
709 | { |
710 | for (size_t i = 0; i < size(); ++i) { |
711 | if (at(i) == value) |
712 | return i; |
713 | } |
714 | return notFound; |
715 | } |
716 | |
717 | template<typename T, size_t inlineCapacity> |
718 | void Vector<T, inlineCapacity>::fill(const T& val, size_t newSize) |
719 | { |
720 | if (size() > newSize) |
721 | shrink(size: newSize); |
722 | else if (newSize > capacity()) { |
723 | clear(); |
724 | reserveCapacity(newCapacity: newSize); |
725 | if (!begin()) |
726 | return; |
727 | } |
728 | |
729 | std::fill(begin(), end(), val); |
730 | TypeOperations::uninitializedFill(end(), begin() + newSize, val); |
731 | m_size = newSize; |
732 | } |
733 | |
734 | template<typename T, size_t inlineCapacity> |
735 | template<typename Iterator> |
736 | void Vector<T, inlineCapacity>::appendRange(Iterator start, Iterator end) |
737 | { |
738 | for (Iterator it = start; it != end; ++it) |
739 | append(*it); |
740 | } |
741 | |
742 | template<typename T, size_t inlineCapacity> |
743 | void Vector<T, inlineCapacity>::expandCapacity(size_t newMinCapacity) |
744 | { |
745 | reserveCapacity(newCapacity: max(newMinCapacity, max(static_cast<size_t>(16), capacity() + capacity() / 4 + 1))); |
746 | } |
747 | |
748 | template<typename T, size_t inlineCapacity> |
749 | const T* Vector<T, inlineCapacity>::expandCapacity(size_t newMinCapacity, const T* ptr) |
750 | { |
751 | if (ptr < begin() || ptr >= end()) { |
752 | expandCapacity(newMinCapacity); |
753 | return ptr; |
754 | } |
755 | size_t index = ptr - begin(); |
756 | expandCapacity(newMinCapacity); |
757 | return begin() + index; |
758 | } |
759 | |
760 | template<typename T, size_t inlineCapacity> template<typename U> |
761 | inline U* Vector<T, inlineCapacity>::expandCapacity(size_t newMinCapacity, U* ptr) |
762 | { |
763 | expandCapacity(newMinCapacity); |
764 | return ptr; |
765 | } |
766 | |
767 | template<typename T, size_t inlineCapacity> |
768 | inline void Vector<T, inlineCapacity>::resize(size_t size) |
769 | { |
770 | if (size <= m_size) |
771 | TypeOperations::destruct(begin() + size, end()); |
772 | else { |
773 | if (size > capacity()) |
774 | expandCapacity(size); |
775 | if (begin()) |
776 | TypeOperations::initialize(end(), begin() + size); |
777 | } |
778 | |
779 | m_size = size; |
780 | } |
781 | |
782 | template<typename T, size_t inlineCapacity> |
783 | void Vector<T, inlineCapacity>::shrink(size_t size) |
784 | { |
785 | ASSERT(size <= m_size); |
786 | TypeOperations::destruct(begin() + size, end()); |
787 | m_size = size; |
788 | } |
789 | |
790 | template<typename T, size_t inlineCapacity> |
791 | void Vector<T, inlineCapacity>::grow(size_t size) |
792 | { |
793 | ASSERT(size >= m_size); |
794 | if (size > capacity()) |
795 | expandCapacity(size); |
796 | if (begin()) |
797 | TypeOperations::initialize(end(), begin() + size); |
798 | m_size = size; |
799 | } |
800 | |
801 | template<typename T, size_t inlineCapacity> |
802 | void Vector<T, inlineCapacity>::reserveCapacity(size_t newCapacity) |
803 | { |
804 | if (newCapacity <= capacity()) |
805 | return; |
806 | T* oldBuffer = begin(); |
807 | T* oldEnd = end(); |
808 | m_buffer.allocateBuffer(newCapacity); |
809 | if (begin()) |
810 | TypeOperations::move(oldBuffer, oldEnd, begin()); |
811 | m_buffer.deallocateBuffer(oldBuffer); |
812 | } |
813 | |
814 | template<typename T, size_t inlineCapacity> |
815 | inline void Vector<T, inlineCapacity>::reserveInitialCapacity(size_t initialCapacity) |
816 | { |
817 | ASSERT(!m_size); |
818 | ASSERT(capacity() == inlineCapacity); |
819 | if (initialCapacity > inlineCapacity) |
820 | m_buffer.allocateBuffer(initialCapacity); |
821 | } |
822 | |
823 | template<typename T, size_t inlineCapacity> |
824 | void Vector<T, inlineCapacity>::shrinkCapacity(size_t newCapacity) |
825 | { |
826 | if (newCapacity >= capacity()) |
827 | return; |
828 | |
829 | if (newCapacity < size()) |
830 | shrink(size: newCapacity); |
831 | |
832 | T* oldBuffer = begin(); |
833 | if (newCapacity > 0) { |
834 | T* oldEnd = end(); |
835 | m_buffer.allocateBuffer(newCapacity); |
836 | if (begin() != oldBuffer) |
837 | TypeOperations::move(oldBuffer, oldEnd, begin()); |
838 | } |
839 | |
840 | m_buffer.deallocateBuffer(oldBuffer); |
841 | m_buffer.restoreInlineBufferIfNeeded(); |
842 | } |
843 | |
844 | // Templatizing these is better than just letting the conversion happen implicitly, |
845 | // because for instance it allows a PassRefPtr to be appended to a RefPtr vector |
846 | // without refcount thrash. |
847 | |
848 | template<typename T, size_t inlineCapacity> template<typename U> |
849 | void Vector<T, inlineCapacity>::append(const U* data, size_t dataSize) |
850 | { |
851 | size_t newSize = m_size + dataSize; |
852 | if (newSize > capacity()) { |
853 | data = expandCapacity(newSize, data); |
854 | if (!begin()) |
855 | return; |
856 | } |
857 | if (newSize < m_size) |
858 | CRASH(); |
859 | T* dest = end(); |
860 | for (size_t i = 0; i < dataSize; ++i) |
861 | new (&dest[i]) T(data[i]); |
862 | m_size = newSize; |
863 | } |
864 | |
865 | template<typename T, size_t inlineCapacity> template<typename U> |
866 | ALWAYS_INLINE void Vector<T, inlineCapacity>::append(const U& val) |
867 | { |
868 | const U* ptr = &val; |
869 | if (size() == capacity()) { |
870 | ptr = expandCapacity(size() + 1, ptr); |
871 | if (!begin()) |
872 | return; |
873 | } |
874 | |
875 | #if COMPILER(MSVC7) |
876 | // FIXME: MSVC7 generates compilation errors when trying to assign |
877 | // a pointer to a Vector of its base class (i.e. can't downcast). So far |
878 | // I've been unable to determine any logical reason for this, so I can |
879 | // only assume it is a bug with the compiler. Casting is a bad solution, |
880 | // however, because it subverts implicit conversions, so a better |
881 | // one is needed. |
882 | new (end()) T(static_cast<T>(*ptr)); |
883 | #else |
884 | new (end()) T(*ptr); |
885 | #endif |
886 | ++m_size; |
887 | } |
888 | |
889 | // This version of append saves a branch in the case where you know that the |
890 | // vector's capacity is large enough for the append to succeed. |
891 | |
892 | template<typename T, size_t inlineCapacity> template<typename U> |
893 | inline void Vector<T, inlineCapacity>::uncheckedAppend(const U& val) |
894 | { |
895 | ASSERT(size() < capacity()); |
896 | const U* ptr = &val; |
897 | new (end()) T(*ptr); |
898 | ++m_size; |
899 | } |
900 | |
901 | // This method should not be called append, a better name would be appendElements. |
902 | // It could also be eliminated entirely, and call sites could just use |
903 | // appendRange(val.begin(), val.end()). |
904 | template<typename T, size_t inlineCapacity> template<size_t otherCapacity> |
905 | inline void Vector<T, inlineCapacity>::append(const Vector<T, otherCapacity>& val) |
906 | { |
907 | append(val.begin(), val.size()); |
908 | } |
909 | |
910 | template<typename T, size_t inlineCapacity> template<typename U> |
911 | void Vector<T, inlineCapacity>::insert(size_t position, const U* data, size_t dataSize) |
912 | { |
913 | ASSERT(position <= size()); |
914 | size_t newSize = m_size + dataSize; |
915 | if (newSize > capacity()) { |
916 | data = expandCapacity(newSize, data); |
917 | if (!begin()) |
918 | return; |
919 | } |
920 | if (newSize < m_size) |
921 | CRASH(); |
922 | T* spot = begin() + position; |
923 | TypeOperations::moveOverlapping(spot, end(), spot + dataSize); |
924 | for (size_t i = 0; i < dataSize; ++i) |
925 | new (&spot[i]) T(data[i]); |
926 | m_size = newSize; |
927 | } |
928 | |
929 | template<typename T, size_t inlineCapacity> template<typename U> |
930 | inline void Vector<T, inlineCapacity>::insert(size_t position, const U& val) |
931 | { |
932 | ASSERT(position <= size()); |
933 | const U* data = &val; |
934 | if (size() == capacity()) { |
935 | data = expandCapacity(size() + 1, data); |
936 | if (!begin()) |
937 | return; |
938 | } |
939 | T* spot = begin() + position; |
940 | TypeOperations::moveOverlapping(spot, end(), spot + 1); |
941 | new (spot) T(*data); |
942 | ++m_size; |
943 | } |
944 | |
945 | template<typename T, size_t inlineCapacity> template<typename U, size_t c> |
946 | inline void Vector<T, inlineCapacity>::insert(size_t position, const Vector<U, c>& val) |
947 | { |
948 | insert(position, val.begin(), val.size()); |
949 | } |
950 | |
951 | template<typename T, size_t inlineCapacity> template<typename U> |
952 | void Vector<T, inlineCapacity>::prepend(const U* data, size_t dataSize) |
953 | { |
954 | insert(0, data, dataSize); |
955 | } |
956 | |
957 | template<typename T, size_t inlineCapacity> template<typename U> |
958 | inline void Vector<T, inlineCapacity>::prepend(const U& val) |
959 | { |
960 | insert(0, val); |
961 | } |
962 | |
963 | template<typename T, size_t inlineCapacity> template<typename U, size_t c> |
964 | inline void Vector<T, inlineCapacity>::prepend(const Vector<U, c>& val) |
965 | { |
966 | insert(0, val.begin(), val.size()); |
967 | } |
968 | |
969 | template<typename T, size_t inlineCapacity> |
970 | inline void Vector<T, inlineCapacity>::remove(size_t position) |
971 | { |
972 | ASSERT(position < size()); |
973 | T* spot = begin() + position; |
974 | spot->~T(); |
975 | TypeOperations::moveOverlapping(spot + 1, end(), spot); |
976 | --m_size; |
977 | } |
978 | |
979 | template<typename T, size_t inlineCapacity> |
980 | inline void Vector<T, inlineCapacity>::remove(size_t position, size_t length) |
981 | { |
982 | ASSERT(position < size()); |
983 | ASSERT(position + length <= size()); |
984 | T* beginSpot = begin() + position; |
985 | T* endSpot = beginSpot + length; |
986 | TypeOperations::destruct(beginSpot, endSpot); |
987 | TypeOperations::moveOverlapping(endSpot, end(), beginSpot); |
988 | m_size -= length; |
989 | } |
990 | |
991 | template<typename T, size_t inlineCapacity> |
992 | inline T* Vector<T, inlineCapacity>::releaseBuffer() |
993 | { |
994 | T* buffer = m_buffer.releaseBuffer(); |
995 | if (inlineCapacity && !buffer && m_size) { |
996 | // If the vector had some data, but no buffer to release, |
997 | // that means it was using the inline buffer. In that case, |
998 | // we create a brand new buffer so the caller always gets one. |
999 | size_t bytes = m_size * sizeof(T); |
1000 | buffer = static_cast<T*>(fastMalloc(bytes)); |
1001 | memcpy(buffer, data(), bytes); |
1002 | } |
1003 | m_size = 0; |
1004 | return buffer; |
1005 | } |
1006 | |
1007 | template<typename T, size_t inlineCapacity> |
1008 | void deleteAllValues(const Vector<T, inlineCapacity>& collection) |
1009 | { |
1010 | typedef typename Vector<T, inlineCapacity>::const_iterator iterator; |
1011 | iterator end = collection.end(); |
1012 | for (iterator it = collection.begin(); it != end; ++it) |
1013 | delete *it; |
1014 | } |
1015 | |
1016 | template<typename T, size_t inlineCapacity> |
1017 | inline void swap(Vector<T, inlineCapacity>& a, Vector<T, inlineCapacity>& b) |
1018 | { |
1019 | a.swap(b); |
1020 | } |
1021 | |
1022 | template<typename T, size_t inlineCapacity> |
1023 | bool operator==(const Vector<T, inlineCapacity>& a, const Vector<T, inlineCapacity>& b) |
1024 | { |
1025 | if (a.size() != b.size()) |
1026 | return false; |
1027 | |
1028 | return VectorTypeOperations<T>::compare(a.data(), b.data(), a.size()); |
1029 | } |
1030 | |
1031 | template<typename T, size_t inlineCapacity> |
1032 | inline bool operator!=(const Vector<T, inlineCapacity>& a, const Vector<T, inlineCapacity>& b) |
1033 | { |
1034 | return !(a == b); |
1035 | } |
1036 | |
1037 | |
1038 | } // namespace WTF |
1039 | |
1040 | using WTF::Vector; |
1041 | |
1042 | #endif // WTF_Vector_h |
1043 | |