• Skip to content
  • Skip to link menu
  • KDE API Reference
  • kdelibs-4.14.38 API Reference
  • KDE Home
  • Contact Us
 

WTF

  • kjs
  • wtf
Vector.h
Go to the documentation of this file.
1// -*- mode: c++; c-basic-offset: 4 -*-
2/*
3 * This file is part of the KDE libraries
4 * Copyright (C) 2005, 2006, 2007, 2008 Apple Inc. All rights reserved.
5 *
6 * This library is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU Library General Public
8 * License as published by the Free Software Foundation; either
9 * version 2 of the License, or (at your option) any later version.
10 *
11 * This library is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 * Library General Public License for more details.
15 *
16 * You should have received a copy of the GNU Library General Public License
17 * along with this library; see the file COPYING.LIB. If not, write to
18 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
19 * Boston, MA 02110-1301, USA.
20 *
21 */
22
23#ifndef WTF_Vector_h
24#define WTF_Vector_h
25
26#include "Assertions.h"
27#include "FastMalloc.h"
28#include "Noncopyable.h"
29#include "VectorTraits.h"
30#include <limits>
31#include <stdlib.h>
32#include <cstring>
33#include <utility>
34
35// Temporary workaround for Win32.
36// We should use NOMINMAX instead.
37#undef max
38
39namespace WTF {
40
41 using std::min;
42 using std::max;
43
44 template <bool needsDestruction, typename T>
45 struct VectorDestructor;
46
47 template<typename T>
48 struct VectorDestructor<false, T>
49 {
50 static void destruct(T*, T*) {}
51 };
52
53 template<typename T>
54 struct VectorDestructor<true, T>
55 {
56 static void destruct(T* begin, T* end)
57 {
58 for (T* cur = begin; cur != end; ++cur)
59 cur->~T();
60 }
61 };
62
63 template <bool needsInitialization, bool canInitializeWithMemset, typename T>
64 struct VectorInitializer;
65
66 template<bool ignore, typename T>
67 struct VectorInitializer<false, ignore, T>
68 {
69 static void initialize(T*, T*) {}
70 };
71
72 template<typename T>
73 struct VectorInitializer<true, false, T>
74 {
75 static void initialize(T* begin, T* end)
76 {
77 for (T* cur = begin; cur != end; ++cur)
78 new (cur) T;
79 }
80 };
81
82 template<typename T>
83 struct VectorInitializer<true, true, T>
84 {
85 static void initialize(T* begin, T* end)
86 {
87 std::memset(begin, 0, reinterpret_cast<char *>(end) - reinterpret_cast<char *>(begin));
88 }
89 };
90
91 template <bool canMoveWithMemcpy, typename T>
92 struct VectorMover;
93
94 template<typename T>
95 struct VectorMover<false, T>
96 {
97 static void move(const T* src, const T* srcEnd, T* dst)
98 {
99 while (src != srcEnd) {
100 new (dst) T(*src);
101 const_cast<T*>(src)->~T();
102 ++dst;
103 ++src;
104 }
105 }
106 static void moveOverlapping(const T* src, const T* srcEnd, T* dst)
107 {
108 if (src > dst)
109 move(src, srcEnd, dst);
110 else {
111 T* dstEnd = dst + (srcEnd - src);
112 while (src != srcEnd) {
113 --srcEnd;
114 --dstEnd;
115 new (dstEnd) T(*srcEnd);
116 const_cast<T*>(srcEnd)->~T();
117 }
118 }
119 }
120 };
121
122 template<typename T>
123 struct VectorMover<true, T>
124 {
125 static void move(const T* src, const T* srcEnd, T* dst)
126 {
127 std::memcpy(dst, src, reinterpret_cast<const char *>(srcEnd) - reinterpret_cast<const char *>(src));
128 }
129 static void moveOverlapping(const T* src, const T* srcEnd, T* dst)
130 {
131 std::memmove(dst, src, reinterpret_cast<const char *>(srcEnd) - reinterpret_cast<const char *>(src));
132 }
133 };
134
135 template <bool canCopyWithMemcpy, typename T>
136 struct VectorCopier;
137
138 template<typename T>
139 struct VectorCopier<false, T>
140 {
141 static void uninitializedCopy(const T* src, const T* srcEnd, T* dst)
142 {
143 while (src != srcEnd) {
144 new (dst) T(*src);
145 ++dst;
146 ++src;
147 }
148 }
149 };
150
151 template<typename T>
152 struct VectorCopier<true, T>
153 {
154 static void uninitializedCopy(const T* src, const T* srcEnd, T* dst)
155 {
156 std::memcpy(dst, src, reinterpret_cast<const char *>(srcEnd) - reinterpret_cast<const char *>(src));
157 }
158 };
159
160 template <bool canFillWithMemset, typename T>
161 struct VectorFiller;
162
163 template<typename T>
164 struct VectorFiller<false, T>
165 {
166 static void uninitializedFill(T* dst, T* dstEnd, const T& val)
167 {
168 while (dst != dstEnd) {
169 new (dst) T(val);
170 ++dst;
171 }
172 }
173 };
174
175 template<typename T>
176 struct VectorFiller<true, T>
177 {
178 static void uninitializedFill(T* dst, T* dstEnd, const T& val)
179 {
180 ASSERT(sizeof(T) == sizeof(char));
181 std::memset(dst, val, dstEnd - dst);
182 }
183 };
184
185 template<bool canCompareWithMemcmp, typename T>
186 struct VectorComparer;
187
188 template<typename T>
189 struct VectorComparer<false, T>
190 {
191 static bool compare(const T* a, const T* b, size_t size)
192 {
193 for (size_t i = 0; i < size; ++i)
194 if (a[i] != b[i])
195 return false;
196 return true;
197 }
198 };
199
200 template<typename T>
201 struct VectorComparer<true, T>
202 {
203 static bool compare(const T* a, const T* b, size_t size)
204 {
205 return std::memcmp(a, b, sizeof(T) * size) == 0;
206 }
207 };
208
209 template<typename T>
210 struct VectorTypeOperations
211 {
212 static void destruct(T* begin, T* end)
213 {
214 VectorDestructor<VectorTraits<T>::needsDestruction, T>::destruct(begin, end);
215 }
216
217 static void initialize(T* begin, T* end)
218 {
219 VectorInitializer<VectorTraits<T>::needsInitialization, VectorTraits<T>::canInitializeWithMemset, T>::initialize(begin, end);
220 }
221
222 static void move(const T* src, const T* srcEnd, T* dst)
223 {
224 VectorMover<VectorTraits<T>::canMoveWithMemcpy, T>::move(src, srcEnd, dst);
225 }
226
227 static void moveOverlapping(const T* src, const T* srcEnd, T* dst)
228 {
229 VectorMover<VectorTraits<T>::canMoveWithMemcpy, T>::moveOverlapping(src, srcEnd, dst);
230 }
231
232 static void uninitializedCopy(const T* src, const T* srcEnd, T* dst)
233 {
234 VectorCopier<VectorTraits<T>::canCopyWithMemcpy, T>::uninitializedCopy(src, srcEnd, dst);
235 }
236
237 static void uninitializedFill(T* dst, T* dstEnd, const T& val)
238 {
239 VectorFiller<VectorTraits<T>::canFillWithMemset, T>::uninitializedFill(dst, dstEnd, val);
240 }
241
242 static bool compare(const T* a, const T* b, size_t size)
243 {
244 return VectorComparer<VectorTraits<T>::canCompareWithMemcmp, T>::compare(a, b, size);
245 }
246 };
247
248 template<typename T>
249 class VectorBufferBase : Noncopyable {
250 public:
251 void allocateBuffer(size_t newCapacity)
252 {
253 m_capacity = newCapacity;
254 if (newCapacity > std::numeric_limits<size_t>::max() / sizeof(T))
255 CRASH();
256 m_buffer = static_cast<T*>(fastMalloc(newCapacity * sizeof(T)));
257 }
258
259 void deallocateBuffer(T* bufferToDeallocate)
260 {
261 if (m_buffer == bufferToDeallocate)
262 m_buffer = 0;
263 fastFree(bufferToDeallocate);
264 }
265
266 T* buffer() { return m_buffer; }
267 const T* buffer() const { return m_buffer; }
268 size_t capacity() const { return m_capacity; }
269
270 T* releaseBuffer()
271 {
272 T* buffer = m_buffer;
273 m_buffer = 0;
274 m_capacity = 0;
275 return buffer;
276 }
277
278 protected:
279 VectorBufferBase()
280 : m_buffer(0)
281 , m_capacity(0)
282 {
283 }
284
285 VectorBufferBase(T* buffer, size_t capacity)
286 : m_buffer(buffer)
287 , m_capacity(capacity)
288 {
289 }
290
291 ~VectorBufferBase()
292 {
293 // FIXME: It would be nice to find a way to ASSERT that m_buffer hasn't leaked here.
294 }
295
296 T* m_buffer;
297 size_t m_capacity;
298 };
299
300 template<typename T, size_t inlineCapacity>
301 class VectorBuffer;
302
303 template<typename T>
304 class VectorBuffer<T, 0> : private VectorBufferBase<T> {
305 private:
306 typedef VectorBufferBase<T> Base;
307 public:
308 VectorBuffer()
309 {
310 }
311
312 VectorBuffer(size_t capacity)
313 {
314 allocateBuffer(capacity);
315 }
316
317 ~VectorBuffer()
318 {
319 deallocateBuffer(buffer());
320 }
321
322 void swap(VectorBuffer<T, 0>& other)
323 {
324 std::swap(m_buffer, other.m_buffer);
325 std::swap(m_capacity, other.m_capacity);
326 }
327
328 using Base::allocateBuffer;
329 using Base::deallocateBuffer;
330
331 using Base::buffer;
332 using Base::capacity;
333
334 using Base::releaseBuffer;
335 private:
336 using Base::m_buffer;
337 using Base::m_capacity;
338 };
339
340 template<typename T, size_t inlineCapacity>
341 class VectorBuffer : private VectorBufferBase<T> {
342 private:
343 typedef VectorBufferBase<T> Base;
344 public:
345 VectorBuffer()
346 : Base(inlineBuffer(), inlineCapacity)
347 {
348 }
349
350 VectorBuffer(size_t capacity)
351 : Base(inlineBuffer(), inlineCapacity)
352 {
353 allocateBuffer(capacity);
354 }
355
356 ~VectorBuffer()
357 {
358 deallocateBuffer(buffer());
359 }
360
361 void allocateBuffer(size_t newCapacity)
362 {
363 if (newCapacity > inlineCapacity)
364 Base::allocateBuffer(newCapacity);
365 }
366
367 void deallocateBuffer(T* bufferToDeallocate)
368 {
369 if (bufferToDeallocate == inlineBuffer())
370 return;
371 Base::deallocateBuffer(bufferToDeallocate);
372 }
373
374 using Base::buffer;
375 using Base::capacity;
376
377 T* releaseBuffer()
378 {
379 if (buffer() == inlineBuffer())
380 return 0;
381 return Base::releaseBuffer();
382 }
383
384 private:
385 using Base::m_buffer;
386 using Base::m_capacity;
387
388 static const size_t m_inlineBufferSize = inlineCapacity * sizeof(T);
389 T* inlineBuffer() { return reinterpret_cast<T*>(&m_inlineBuffer); }
390
391 // FIXME: Nothing guarantees this buffer is appropriately aligned to hold objects of type T.
392 char m_inlineBuffer[m_inlineBufferSize];
393 };
394
395 template<typename T, size_t inlineCapacity = 0>
396 class Vector {
397 private:
398 typedef VectorBuffer<T, inlineCapacity> Buffer;
399 typedef VectorTypeOperations<T> TypeOperations;
400
401 public:
402 typedef T ValueType;
403
404 typedef T* iterator;
405 typedef const T* const_iterator;
406
407 Vector()
408 : m_size(0)
409 {
410 }
411
412 explicit Vector(size_t size)
413 : m_size(size)
414 , m_buffer(size)
415 {
416 TypeOperations::initialize(begin(), end());
417 }
418
419 ~Vector()
420 {
421 clear();
422 }
423
424 Vector(const Vector&);
425 template<size_t otherCapacity>
426 Vector(const Vector<T, otherCapacity>&);
427
428 Vector& operator=(const Vector&);
429 template<size_t otherCapacity>
430 Vector& operator=(const Vector<T, otherCapacity>&);
431
432 size_t size() const { return m_size; }
433 size_t capacity() const { return m_buffer.capacity(); }
434 bool isEmpty() const { return !size(); }
435
436 T& at(size_t i)
437 {
438 ASSERT(i < size());
439 return m_buffer.buffer()[i];
440 }
441 const T& at(size_t i) const
442 {
443 ASSERT(i < size());
444 return m_buffer.buffer()[i];
445 }
446
447 T& operator[](size_t i) { return at(i); }
448 const T& operator[](size_t i) const { return at(i); }
449
450 T* data() { return m_buffer.buffer(); }
451 const T* data() const { return m_buffer.buffer(); }
452
453 iterator begin() { return data(); }
454 iterator end() { return begin() + m_size; }
455 const_iterator begin() const { return data(); }
456 const_iterator end() const { return begin() + m_size; }
457
458 T& first() { return at(0); }
459 const T& first() const { return at(0); }
460 T& last() { return at(size() - 1); }
461 const T& last() const { return at(size() - 1); }
462
463 void shrink(size_t size);
464 void grow(size_t size);
465 void resize(size_t size);
466 void reserveCapacity(size_t newCapacity);
467 void shrinkCapacity(size_t newCapacity);
468
469 void clear() { if (m_size) shrink(0); }
470
471 template<typename U> void append(const U*, size_t);
472 template<typename U> void append(const U&);
473 template<typename U> void uncheckedAppend(const U& val);
474 template<typename U, size_t c> void append(const Vector<U, c>&);
475
476 template<typename U> void insert(size_t position, const U*, size_t);
477 template<typename U> void insert(size_t position, const U&);
478 template<typename U, size_t c> void insert(size_t position, const Vector<U, c>&);
479
480 template<typename U> void prepend(const U*, size_t);
481 template<typename U> void prepend(const U&);
482 template<typename U, size_t c> void prepend(const Vector<U, c>&);
483
484 void remove(size_t position);
485 void remove(size_t position, size_t length);
486
487 void removeLast()
488 {
489 ASSERT(!isEmpty());
490 shrink(size() - 1);
491 }
492
493 Vector(size_t size, const T& val)
494 : m_size(size)
495 , m_buffer(size)
496 {
497 TypeOperations::uninitializedFill(begin(), end(), val);
498 }
499
500 void fill(const T&, size_t);
501 void fill(const T& val) { fill(val, size()); }
502
503 template<typename Iterator> void appendRange(Iterator start, Iterator end);
504
505 T* releaseBuffer();
506
507 void swap(Vector<T, inlineCapacity>& other)
508 {
509 std::swap(m_size, other.m_size);
510 m_buffer.swap(other.m_buffer);
511 }
512
513 private:
514 void expandCapacity(size_t newMinCapacity);
515 const T* expandCapacity(size_t newMinCapacity, const T*);
516 template<typename U> U* expandCapacity(size_t newMinCapacity, U*);
517
518 size_t m_size;
519 Buffer m_buffer;
520 };
521
522 template<typename T, size_t inlineCapacity>
523 Vector<T, inlineCapacity>::Vector(const Vector& other)
524 : m_size(other.size())
525 , m_buffer(other.capacity())
526 {
527 TypeOperations::uninitializedCopy(other.begin(), other.end(), begin());
528 }
529
530 template<typename T, size_t inlineCapacity>
531 template<size_t otherCapacity>
532 Vector<T, inlineCapacity>::Vector(const Vector<T, otherCapacity>& other)
533 : m_size(other.size())
534 , m_buffer(other.capacity())
535 {
536 TypeOperations::uninitializedCopy(other.begin(), other.end(), begin());
537 }
538
539 template<typename T, size_t inlineCapacity>
540 Vector<T, inlineCapacity>& Vector<T, inlineCapacity>::operator=(const Vector<T, inlineCapacity>& other)
541 {
542 if (&other == this)
543 return *this;
544
545 if (size() > other.size())
546 shrink(other.size());
547 else if (other.size() > capacity()) {
548 clear();
549 reserveCapacity(other.size());
550 }
551
552 std::copy(other.begin(), other.begin() + size(), begin());
553 TypeOperations::uninitializedCopy(other.begin() + size(), other.end(), end());
554 m_size = other.size();
555
556 return *this;
557 }
558
559 template<typename T, size_t inlineCapacity>
560 template<size_t otherCapacity>
561 Vector<T, inlineCapacity>& Vector<T, inlineCapacity>::operator=(const Vector<T, otherCapacity>& other)
562 {
563 if (&other == this)
564 return *this;
565
566 if (size() > other.size())
567 shrink(other.size());
568 else if (other.size() > capacity()) {
569 clear();
570 reserveCapacity(other.size());
571 }
572
573 std::copy(other.begin(), other.begin() + size(), begin());
574 TypeOperations::uninitializedCopy(other.begin() + size(), other.end(), end());
575 m_size = other.size();
576
577 return *this;
578 }
579
580 template<typename T, size_t inlineCapacity>
581 void Vector<T, inlineCapacity>::fill(const T& val, size_t newSize)
582 {
583 if (size() > newSize)
584 shrink(newSize);
585 else if (newSize > capacity()) {
586 clear();
587 reserveCapacity(newSize);
588 }
589
590 std::fill(begin(), end(), val);
591 TypeOperations::uninitializedFill(end(), begin() + newSize, val);
592 m_size = newSize;
593 }
594
595 template<typename T, size_t inlineCapacity>
596 template<typename Iterator>
597 void Vector<T, inlineCapacity>::appendRange(Iterator start, Iterator end)
598 {
599 for (Iterator it = start; it != end; ++it)
600 append(*it);
601 }
602
603 template<typename T, size_t inlineCapacity>
604 void Vector<T, inlineCapacity>::expandCapacity(size_t newMinCapacity)
605 {
606 reserveCapacity(max(newMinCapacity, max(static_cast<size_t>(16), capacity() + capacity() / 4 + 1)));
607 }
608
609 template<typename T, size_t inlineCapacity>
610 const T* Vector<T, inlineCapacity>::expandCapacity(size_t newMinCapacity, const T* ptr)
611 {
612 if (ptr < begin() || ptr >= end()) {
613 expandCapacity(newMinCapacity);
614 return ptr;
615 }
616 size_t index = ptr - begin();
617 expandCapacity(newMinCapacity);
618 return begin() + index;
619 }
620
621 template<typename T, size_t inlineCapacity> template<typename U>
622 inline U* Vector<T, inlineCapacity>::expandCapacity(size_t newMinCapacity, U* ptr)
623 {
624 expandCapacity(newMinCapacity);
625 return ptr;
626 }
627
628 template<typename T, size_t inlineCapacity>
629 void Vector<T, inlineCapacity>::resize(size_t size)
630 {
631 if (size <= m_size)
632 TypeOperations::destruct(begin() + size, end());
633 else {
634 if (size > capacity())
635 expandCapacity(size);
636 if (begin())
637 TypeOperations::initialize(end(), begin() + size);
638 }
639
640 m_size = size;
641 }
642
643 template<typename T, size_t inlineCapacity>
644 void Vector<T, inlineCapacity>::shrink(size_t size)
645 {
646 ASSERT(size <= m_size);
647 TypeOperations::destruct(begin() + size, end());
648 m_size = size;
649 }
650
651 template<typename T, size_t inlineCapacity>
652 void Vector<T, inlineCapacity>::grow(size_t size)
653 {
654 ASSERT(size >= m_size);
655 if (size > capacity())
656 expandCapacity(size);
657 if (begin())
658 TypeOperations::initialize(end(), begin() + size);
659 m_size = size;
660 }
661
662 template<typename T, size_t inlineCapacity>
663 void Vector<T, inlineCapacity>::reserveCapacity(size_t newCapacity)
664 {
665 if (newCapacity <= capacity())
666 return;
667 T* oldBuffer = begin();
668 T* oldEnd = end();
669 m_buffer.allocateBuffer(newCapacity);
670 if (begin())
671 TypeOperations::move(oldBuffer, oldEnd, begin());
672 m_buffer.deallocateBuffer(oldBuffer);
673 }
674
675 template<typename T, size_t inlineCapacity>
676 void Vector<T, inlineCapacity>::shrinkCapacity(size_t newCapacity)
677 {
678 if (newCapacity >= capacity())
679 return;
680
681 resize(min(m_size, newCapacity));
682
683 T* oldBuffer = begin();
684 if (newCapacity > 0) {
685 T* oldEnd = end();
686 m_buffer.allocateBuffer(newCapacity);
687 if (begin() != oldBuffer)
688 TypeOperations::move(oldBuffer, oldEnd, begin());
689 }
690
691 m_buffer.deallocateBuffer(oldBuffer);
692 }
693
694 // Templatizing these is better than just letting the conversion happen implicitly,
695 // because for instance it allows a PassRefPtr to be appended to a RefPtr vector
696 // without refcount thrash.
697
698 template<typename T, size_t inlineCapacity> template<typename U>
699 void Vector<T, inlineCapacity>::append(const U* data, size_t dataSize)
700 {
701 size_t newSize = m_size + dataSize;
702 if (newSize > capacity()) {
703 data = expandCapacity(newSize, data);
704 if (!begin())
705 return;
706 }
707 T* dest = end();
708 for (size_t i = 0; i < dataSize; ++i)
709 new (&dest[i]) T(data[i]);
710 m_size = newSize;
711 }
712
713 template<typename T, size_t inlineCapacity> template<typename U>
714 inline void Vector<T, inlineCapacity>::append(const U& val)
715 {
716 const U* ptr = &val;
717 if (size() == capacity()) {
718 ptr = expandCapacity(size() + 1, ptr);
719 if (!begin())
720 return;
721 }
722
723#if COMPILER(MSVC7)
724 // FIXME: MSVC7 generates compilation errors when trying to assign
725 // a pointer to a Vector of its base class (i.e. can't downcast). So far
726 // I've been unable to determine any logical reason for this, so I can
727 // only assume it is a bug with the compiler. Casting is a bad solution,
728 // however, because it subverts implicit conversions, so a better
729 // one is needed.
730 new (end()) T(static_cast<T>(*ptr));
731#else
732 new (end()) T(*ptr);
733#endif
734 ++m_size;
735 }
736
737 // This version of append saves a branch in the case where you know that the
738 // vector's capacity is large enough for the append to succeed.
739
740 template<typename T, size_t inlineCapacity> template<typename U>
741 inline void Vector<T, inlineCapacity>::uncheckedAppend(const U& val)
742 {
743 ASSERT(size() < capacity());
744 const U* ptr = &val;
745 new (end()) T(*ptr);
746 ++m_size;
747 }
748
749 template<typename T, size_t inlineCapacity> template<typename U, size_t c>
750 inline void Vector<T, inlineCapacity>::append(const Vector<U, c>& val)
751 {
752 append(val.begin(), val.size());
753 }
754
755 template<typename T, size_t inlineCapacity> template<typename U>
756 void Vector<T, inlineCapacity>::insert(size_t position, const U* data, size_t dataSize)
757 {
758 ASSERT(position <= size());
759 size_t newSize = m_size + dataSize;
760 if (newSize > capacity()) {
761 data = expandCapacity(newSize, data);
762 if (!begin())
763 return;
764 }
765 T* spot = begin() + position;
766 TypeOperations::moveOverlapping(spot, end(), spot + dataSize);
767 for (size_t i = 0; i < dataSize; ++i)
768 new (&spot[i]) T(data[i]);
769 m_size = newSize;
770 }
771
772 template<typename T, size_t inlineCapacity> template<typename U>
773 inline void Vector<T, inlineCapacity>::insert(size_t position, const U& val)
774 {
775 ASSERT(position <= size());
776 const U* data = &val;
777 if (size() == capacity()) {
778 data = expandCapacity(size() + 1, data);
779 if (!begin())
780 return;
781 }
782 T* spot = begin() + position;
783 TypeOperations::moveOverlapping(spot, end(), spot + 1);
784 new (spot) T(*data);
785 ++m_size;
786 }
787
788 template<typename T, size_t inlineCapacity> template<typename U, size_t c>
789 inline void Vector<T, inlineCapacity>::insert(size_t position, const Vector<U, c>& val)
790 {
791 insert(position, val.begin(), val.size());
792 }
793
794 template<typename T, size_t inlineCapacity> template<typename U>
795 void Vector<T, inlineCapacity>::prepend(const U* data, size_t dataSize)
796 {
797 insert(0, data, dataSize);
798 }
799
800 template<typename T, size_t inlineCapacity> template<typename U>
801 inline void Vector<T, inlineCapacity>::prepend(const U& val)
802 {
803 insert(0, val);
804 }
805
806 template<typename T, size_t inlineCapacity> template<typename U, size_t c>
807 inline void Vector<T, inlineCapacity>::prepend(const Vector<U, c>& val)
808 {
809 insert(0, val.begin(), val.size());
810 }
811
812 template<typename T, size_t inlineCapacity>
813 inline void Vector<T, inlineCapacity>::remove(size_t position)
814 {
815 ASSERT(position < size());
816 T* spot = begin() + position;
817 spot->~T();
818 TypeOperations::moveOverlapping(spot + 1, end(), spot);
819 --m_size;
820 }
821
822 template<typename T, size_t inlineCapacity>
823 inline void Vector<T, inlineCapacity>::remove(size_t position, size_t length)
824 {
825 ASSERT(position < size());
826 ASSERT(position + length < size());
827 T* beginSpot = begin() + position;
828 T* endSpot = beginSpot + length;
829 TypeOperations::destruct(beginSpot, endSpot);
830 TypeOperations::moveOverlapping(endSpot, end(), beginSpot);
831 m_size -= length;
832 }
833
834 template<typename T, size_t inlineCapacity>
835 inline T* Vector<T, inlineCapacity>::releaseBuffer()
836 {
837 T* buffer = m_buffer.releaseBuffer();
838 if (inlineCapacity && !buffer && m_size) {
839 // If the vector had some data, but no buffer to release,
840 // that means it was using the inline buffer. In that case,
841 // we create a brand new buffer so the caller always gets one.
842 size_t bytes = m_size * sizeof(T);
843 buffer = static_cast<T*>(fastMalloc(bytes));
844 memcpy(buffer, data(), bytes);
845 }
846 ASSERT(buffer);
847 m_size = 0;
848 return buffer;
849 }
850
851 template<typename T, size_t inlineCapacity>
852 void deleteAllValues(const Vector<T, inlineCapacity>& collection)
853 {
854 typedef typename Vector<T, inlineCapacity>::const_iterator iterator;
855 iterator end = collection.end();
856 for (iterator it = collection.begin(); it != end; ++it)
857 delete *it;
858 }
859
860 template<typename T, size_t inlineCapacity>
861 inline void swap(Vector<T, inlineCapacity>& a, Vector<T, inlineCapacity>& b)
862 {
863 a.swap(b);
864 }
865
866 template<typename T, size_t inlineCapacity>
867 bool operator==(const Vector<T, inlineCapacity>& a, const Vector<T, inlineCapacity>& b)
868 {
869 if (a.size() != b.size())
870 return false;
871
872 return VectorTypeOperations<T>::compare(a.data(), b.data(), a.size());
873 }
874
875 template<typename T, size_t inlineCapacity>
876 inline bool operator!=(const Vector<T, inlineCapacity>& a, const Vector<T, inlineCapacity>& b)
877 {
878 return !(a == b);
879 }
880
881
882} // namespace WTF
883
884using WTF::Vector;
885
886#endif // WTF_Vector_h
Assertions.h
ASSERT
#define ASSERT(x)
Definition: Assertions.h:33
CRASH
#define CRASH()
Definition: Assertions.h:47
FastMalloc.h
Noncopyable.h
VectorTraits.h
WTFNoncopyable::Noncopyable
Definition: Noncopyable.h:32
WTF::VectorBufferBase
Definition: Vector.h:249
WTF::VectorBufferBase::buffer
T * buffer()
Definition: Vector.h:266
WTF::VectorBufferBase::m_buffer
T * m_buffer
Definition: Vector.h:296
WTF::VectorBufferBase::buffer
const T * buffer() const
Definition: Vector.h:267
WTF::VectorBufferBase::VectorBufferBase
VectorBufferBase()
Definition: Vector.h:279
WTF::VectorBufferBase::allocateBuffer
void allocateBuffer(size_t newCapacity)
Definition: Vector.h:251
WTF::VectorBufferBase::~VectorBufferBase
~VectorBufferBase()
Definition: Vector.h:291
WTF::VectorBufferBase::VectorBufferBase
VectorBufferBase(T *buffer, size_t capacity)
Definition: Vector.h:285
WTF::VectorBufferBase::releaseBuffer
T * releaseBuffer()
Definition: Vector.h:270
WTF::VectorBufferBase::capacity
size_t capacity() const
Definition: Vector.h:268
WTF::VectorBufferBase::m_capacity
size_t m_capacity
Definition: Vector.h:297
WTF::VectorBufferBase::deallocateBuffer
void deallocateBuffer(T *bufferToDeallocate)
Definition: Vector.h:259
WTF::VectorBuffer< T, 0 >::swap
void swap(VectorBuffer< T, 0 > &other)
Definition: Vector.h:322
WTF::VectorBuffer< T, 0 >::VectorBuffer
VectorBuffer()
Definition: Vector.h:308
WTF::VectorBuffer< T, 0 >::~VectorBuffer
~VectorBuffer()
Definition: Vector.h:317
WTF::VectorBuffer< T, 0 >::VectorBuffer
VectorBuffer(size_t capacity)
Definition: Vector.h:312
WTF::VectorBuffer
Definition: Vector.h:341
WTF::VectorBuffer::buffer
T * buffer()
Definition: Vector.h:266
WTF::VectorBuffer::releaseBuffer
T * releaseBuffer()
Definition: Vector.h:377
WTF::VectorBuffer::~VectorBuffer
~VectorBuffer()
Definition: Vector.h:356
WTF::VectorBuffer::deallocateBuffer
void deallocateBuffer(T *bufferToDeallocate)
Definition: Vector.h:367
WTF::VectorBuffer::VectorBuffer
VectorBuffer(size_t capacity)
Definition: Vector.h:350
WTF::VectorBuffer::allocateBuffer
void allocateBuffer(size_t newCapacity)
Definition: Vector.h:361
WTF::VectorBuffer::VectorBuffer
VectorBuffer()
Definition: Vector.h:345
WTF::VectorBuffer::capacity
size_t capacity() const
Definition: Vector.h:268
WTF::Vector
Definition: Vector.h:396
WTF::Vector::appendRange
void appendRange(Iterator start, Iterator end)
Definition: Vector.h:597
WTF::Vector::grow
void grow(size_t size)
Definition: Vector.h:652
WTF::Vector::releaseBuffer
T * releaseBuffer()
Definition: Vector.h:835
WTF::Vector::uncheckedAppend
void uncheckedAppend(const U &val)
Definition: Vector.h:741
WTF::Vector::data
const T * data() const
Definition: Vector.h:451
WTF::Vector::begin
iterator begin()
Definition: Vector.h:453
WTF::Vector::fill
void fill(const T &, size_t)
Definition: Vector.h:581
WTF::Vector::capacity
size_t capacity() const
Definition: Vector.h:433
WTF::Vector::end
const_iterator end() const
Definition: Vector.h:456
WTF::Vector::operator=
Vector & operator=(const Vector &)
Definition: Vector.h:540
WTF::Vector::shrinkCapacity
void shrinkCapacity(size_t newCapacity)
Definition: Vector.h:676
WTF::Vector::last
T & last()
Definition: Vector.h:460
WTF::Vector::data
T * data()
Definition: Vector.h:450
WTF::Vector::insert
void insert(size_t position, const U *, size_t)
Definition: Vector.h:756
WTF::Vector::fill
void fill(const T &val)
Definition: Vector.h:501
WTF::Vector::last
const T & last() const
Definition: Vector.h:461
WTF::Vector::append
void append(const U *, size_t)
Definition: Vector.h:699
WTF::Vector::operator=
Vector & operator=(const Vector< T, otherCapacity > &)
WTF::Vector::resize
void resize(size_t size)
Definition: Vector.h:629
WTF::Vector::shrink
void shrink(size_t size)
Definition: Vector.h:644
WTF::Vector::reserveCapacity
void reserveCapacity(size_t newCapacity)
Definition: Vector.h:663
WTF::Vector::removeLast
void removeLast()
Definition: Vector.h:487
WTF::Vector::first
T & first()
Definition: Vector.h:458
WTF::Vector::operator[]
const T & operator[](size_t i) const
Definition: Vector.h:448
WTF::Vector::first
const T & first() const
Definition: Vector.h:459
WTF::Vector::Vector
Vector(size_t size)
Definition: Vector.h:412
WTF::Vector::Vector
Vector()
Definition: Vector.h:407
WTF::Vector::prepend
void prepend(const U *, size_t)
Definition: Vector.h:795
WTF::Vector::size
size_t size() const
Definition: Vector.h:432
WTF::Vector::end
iterator end()
Definition: Vector.h:454
WTF::Vector::~Vector
~Vector()
Definition: Vector.h:419
WTF::Vector::at
const T & at(size_t i) const
Definition: Vector.h:441
WTF::Vector::begin
const_iterator begin() const
Definition: Vector.h:455
WTF::Vector::isEmpty
bool isEmpty() const
Definition: Vector.h:434
WTF::Vector::swap
void swap(Vector< T, inlineCapacity > &other)
Definition: Vector.h:507
WTF::Vector::ValueType
T ValueType
Definition: Vector.h:402
WTF::Vector::Vector
Vector(size_t size, const T &val)
Definition: Vector.h:493
WTF::Vector::clear
void clear()
Definition: Vector.h:469
WTF::Vector::remove
void remove(size_t position)
Definition: Vector.h:813
WTF::Vector::operator[]
T & operator[](size_t i)
Definition: Vector.h:447
WTF::Vector::at
T & at(size_t i)
Definition: Vector.h:436
WTF
Definition: ASCIICType.h:45
WTF::deleteAllValues
void deleteAllValues(const HashMap< T, U, V, W, X > &collection)
Definition: HashMap.h:283
WTF::fastMalloc
void * fastMalloc(size_t n)
Definition: FastMalloc.h:36
WTF::fastFree
void fastFree(void *p)
Definition: FastMalloc.h:44
WTF::swap
void swap(OwnArrayPtr< T > &a, OwnArrayPtr< T > &b)
Definition: OwnArrayPtr.h:61
WTF::operator!=
bool operator!=(const HashTableConstKeysIterator< T, U, V > &a, const HashTableConstKeysIterator< T, U, V > &b)
Definition: HashIterators.h:173
WTF::operator==
bool operator==(const HashTableConstKeysIterator< T, U, V > &a, const HashTableConstKeysIterator< T, U, V > &b)
Definition: HashIterators.h:167
WTF::VectorComparer< false, T >::compare
static bool compare(const T *a, const T *b, size_t size)
Definition: Vector.h:191
WTF::VectorComparer< true, T >::compare
static bool compare(const T *a, const T *b, size_t size)
Definition: Vector.h:203
WTF::VectorComparer
Definition: Vector.h:186
WTF::VectorCopier< false, T >::uninitializedCopy
static void uninitializedCopy(const T *src, const T *srcEnd, T *dst)
Definition: Vector.h:141
WTF::VectorCopier< true, T >::uninitializedCopy
static void uninitializedCopy(const T *src, const T *srcEnd, T *dst)
Definition: Vector.h:154
WTF::VectorCopier
Definition: Vector.h:136
WTF::VectorDestructor< false, T >::destruct
static void destruct(T *, T *)
Definition: Vector.h:50
WTF::VectorDestructor< true, T >::destruct
static void destruct(T *begin, T *end)
Definition: Vector.h:56
WTF::VectorDestructor
Definition: Vector.h:45
WTF::VectorFiller< false, T >::uninitializedFill
static void uninitializedFill(T *dst, T *dstEnd, const T &val)
Definition: Vector.h:166
WTF::VectorFiller< true, T >::uninitializedFill
static void uninitializedFill(T *dst, T *dstEnd, const T &val)
Definition: Vector.h:178
WTF::VectorFiller
Definition: Vector.h:161
WTF::VectorInitializer< false, ignore, T >::initialize
static void initialize(T *, T *)
Definition: Vector.h:69
WTF::VectorInitializer< true, false, T >::initialize
static void initialize(T *begin, T *end)
Definition: Vector.h:75
WTF::VectorInitializer< true, true, T >::initialize
static void initialize(T *begin, T *end)
Definition: Vector.h:85
WTF::VectorInitializer
Definition: Vector.h:64
WTF::VectorMover< false, T >::move
static void move(const T *src, const T *srcEnd, T *dst)
Definition: Vector.h:97
WTF::VectorMover< false, T >::moveOverlapping
static void moveOverlapping(const T *src, const T *srcEnd, T *dst)
Definition: Vector.h:106
WTF::VectorMover< true, T >::move
static void move(const T *src, const T *srcEnd, T *dst)
Definition: Vector.h:125
WTF::VectorMover< true, T >::moveOverlapping
static void moveOverlapping(const T *src, const T *srcEnd, T *dst)
Definition: Vector.h:129
WTF::VectorMover
Definition: Vector.h:92
WTF::VectorTraits
Definition: VectorTraits.h:79
WTF::VectorTypeOperations
Definition: Vector.h:211
WTF::VectorTypeOperations::destruct
static void destruct(T *begin, T *end)
Definition: Vector.h:212
WTF::VectorTypeOperations::compare
static bool compare(const T *a, const T *b, size_t size)
Definition: Vector.h:242
WTF::VectorTypeOperations::move
static void move(const T *src, const T *srcEnd, T *dst)
Definition: Vector.h:222
WTF::VectorTypeOperations::uninitializedFill
static void uninitializedFill(T *dst, T *dstEnd, const T &val)
Definition: Vector.h:237
WTF::VectorTypeOperations::moveOverlapping
static void moveOverlapping(const T *src, const T *srcEnd, T *dst)
Definition: Vector.h:227
WTF::VectorTypeOperations::initialize
static void initialize(T *begin, T *end)
Definition: Vector.h:217
WTF::VectorTypeOperations::uninitializedCopy
static void uninitializedCopy(const T *src, const T *srcEnd, T *dst)
Definition: Vector.h:232
This file is part of the KDE documentation.
Documentation copyright © 1996-2023 The KDE developers.
Generated on Mon Feb 20 2023 00:00:00 by doxygen 1.9.6 written by Dimitri van Heesch, © 1997-2006

KDE's Doxygen guidelines are available online.

WTF

Skip menu "WTF"
  • Main Page
  • Namespace List
  • Namespace Members
  • Alphabetical List
  • Class List
  • Class Hierarchy
  • Class Members
  • File List
  • File Members
  • Related Pages

kdelibs-4.14.38 API Reference

Skip menu "kdelibs-4.14.38 API Reference"
  • DNSSD
  • Interfaces
  •   KHexEdit
  •   KMediaPlayer
  •   KSpeech
  •   KTextEditor
  • kconf_update
  • KDE3Support
  •   KUnitTest
  • KDECore
  • KDED
  • KDEsu
  • KDEUI
  • KDEWebKit
  • KDocTools
  • KFile
  • KHTML
  • KImgIO
  • KInit
  • kio
  • KIOSlave
  • KJS
  •   KJS-API
  •   WTF
  • kjsembed
  • KNewStuff
  • KParts
  • KPty
  • Kross
  • KUnitConversion
  • KUtils
  • Nepomuk
  • Plasma
  • Solid
  • Sonnet
  • ThreadWeaver
Report problems with this website to our bug tracking system.
Contact the specific authors with questions and comments about the page contents.

KDE® and the K Desktop Environment® logo are registered trademarks of KDE e.V. | Legal