00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023 #ifndef WTF_Vector_h
00024 #define WTF_Vector_h
00025
00026 #include "Assertions.h"
00027 #include "FastMalloc.h"
00028 #include "Noncopyable.h"
00029 #include "VectorTraits.h"
00030 #include <limits>
00031 #include <stdlib.h>
00032 #include <cstring>
00033 #include <utility>
00034
00035
00036
00037 #undef max
00038
00039 namespace WTF {
00040
00041 using std::min;
00042 using std::max;
00043
00044 template <bool needsDestruction, typename T>
00045 struct VectorDestructor;
00046
00047 template<typename T>
00048 struct VectorDestructor<false, T>
00049 {
00050 static void destruct(T*, T*) {}
00051 };
00052
00053 template<typename T>
00054 struct VectorDestructor<true, T>
00055 {
00056 static void destruct(T* begin, T* end)
00057 {
00058 for (T* cur = begin; cur != end; ++cur)
00059 cur->~T();
00060 }
00061 };
00062
00063 template <bool needsInitialization, bool canInitializeWithMemset, typename T>
00064 struct VectorInitializer;
00065
00066 template<bool ignore, typename T>
00067 struct VectorInitializer<false, ignore, T>
00068 {
00069 static void initialize(T*, T*) {}
00070 };
00071
00072 template<typename T>
00073 struct VectorInitializer<true, false, T>
00074 {
00075 static void initialize(T* begin, T* end)
00076 {
00077 for (T* cur = begin; cur != end; ++cur)
00078 new (cur) T;
00079 }
00080 };
00081
00082 template<typename T>
00083 struct VectorInitializer<true, true, T>
00084 {
00085 static void initialize(T* begin, T* end)
00086 {
00087 std::memset(begin, 0, reinterpret_cast<char *>(end) - reinterpret_cast<char *>(begin));
00088 }
00089 };
00090
00091 template <bool canMoveWithMemcpy, typename T>
00092 struct VectorMover;
00093
00094 template<typename T>
00095 struct VectorMover<false, T>
00096 {
00097 static void move(const T* src, const T* srcEnd, T* dst)
00098 {
00099 while (src != srcEnd) {
00100 new (dst) T(*src);
00101 src->~T();
00102 ++dst;
00103 ++src;
00104 }
00105 }
00106 static void moveOverlapping(const T* src, const T* srcEnd, T* dst)
00107 {
00108 if (src > dst)
00109 move(src, srcEnd, dst);
00110 else {
00111 T* dstEnd = dst + (srcEnd - src);
00112 while (src != srcEnd) {
00113 --srcEnd;
00114 --dstEnd;
00115 new (dstEnd) T(*srcEnd);
00116 srcEnd->~T();
00117 }
00118 }
00119 }
00120 };
00121
00122 template<typename T>
00123 struct VectorMover<true, T>
00124 {
00125 static void move(const T* src, const T* srcEnd, T* dst)
00126 {
00127 std::memcpy(dst, src, reinterpret_cast<const char *>(srcEnd) - reinterpret_cast<const char *>(src));
00128 }
00129 static void moveOverlapping(const T* src, const T* srcEnd, T* dst)
00130 {
00131 std::memmove(dst, src, reinterpret_cast<const char *>(srcEnd) - reinterpret_cast<const char *>(src));
00132 }
00133 };
00134
00135 template <bool canCopyWithMemcpy, typename T>
00136 struct VectorCopier;
00137
00138 template<typename T>
00139 struct VectorCopier<false, T>
00140 {
00141 static void uninitializedCopy(const T* src, const T* srcEnd, T* dst)
00142 {
00143 while (src != srcEnd) {
00144 new (dst) T(*src);
00145 ++dst;
00146 ++src;
00147 }
00148 }
00149 };
00150
00151 template<typename T>
00152 struct VectorCopier<true, T>
00153 {
00154 static void uninitializedCopy(const T* src, const T* srcEnd, T* dst)
00155 {
00156 std::memcpy(dst, src, reinterpret_cast<const char *>(srcEnd) - reinterpret_cast<const char *>(src));
00157 }
00158 };
00159
00160 template <bool canFillWithMemset, typename T>
00161 struct VectorFiller;
00162
00163 template<typename T>
00164 struct VectorFiller<false, T>
00165 {
00166 static void uninitializedFill(T* dst, T* dstEnd, const T& val)
00167 {
00168 while (dst != dstEnd) {
00169 new (dst) T(val);
00170 ++dst;
00171 }
00172 }
00173 };
00174
00175 template<typename T>
00176 struct VectorFiller<true, T>
00177 {
00178 static void uninitializedFill(T* dst, T* dstEnd, const T& val)
00179 {
00180 ASSERT(sizeof(T) == sizeof(char));
00181 std::memset(dst, val, dstEnd - dst);
00182 }
00183 };
00184
00185 template<bool canCompareWithMemcmp, typename T>
00186 struct VectorComparer;
00187
00188 template<typename T>
00189 struct VectorComparer<false, T>
00190 {
00191 static bool compare(const T* a, const T* b, size_t size)
00192 {
00193 for (size_t i = 0; i < size; ++i)
00194 if (a[i] != b[i])
00195 return false;
00196 return true;
00197 }
00198 };
00199
00200 template<typename T>
00201 struct VectorComparer<true, T>
00202 {
00203 static bool compare(const T* a, const T* b, size_t size)
00204 {
00205 return std::memcmp(a, b, sizeof(T) * size) == 0;
00206 }
00207 };
00208
00209 template<typename T>
00210 struct VectorTypeOperations
00211 {
00212 static void destruct(T* begin, T* end)
00213 {
00214 VectorDestructor<VectorTraits<T>::needsDestruction, T>::destruct(begin, end);
00215 }
00216
00217 static void initialize(T* begin, T* end)
00218 {
00219 VectorInitializer<VectorTraits<T>::needsInitialization, VectorTraits<T>::canInitializeWithMemset, T>::initialize(begin, end);
00220 }
00221
00222 static void move(const T* src, const T* srcEnd, T* dst)
00223 {
00224 VectorMover<VectorTraits<T>::canMoveWithMemcpy, T>::move(src, srcEnd, dst);
00225 }
00226
00227 static void moveOverlapping(const T* src, const T* srcEnd, T* dst)
00228 {
00229 VectorMover<VectorTraits<T>::canMoveWithMemcpy, T>::moveOverlapping(src, srcEnd, dst);
00230 }
00231
00232 static void uninitializedCopy(const T* src, const T* srcEnd, T* dst)
00233 {
00234 VectorCopier<VectorTraits<T>::canCopyWithMemcpy, T>::uninitializedCopy(src, srcEnd, dst);
00235 }
00236
00237 static void uninitializedFill(T* dst, T* dstEnd, const T& val)
00238 {
00239 VectorFiller<VectorTraits<T>::canFillWithMemset, T>::uninitializedFill(dst, dstEnd, val);
00240 }
00241
00242 static bool compare(const T* a, const T* b, size_t size)
00243 {
00244 return VectorComparer<VectorTraits<T>::canCompareWithMemcmp, T>::compare(a, b, size);
00245 }
00246 };
00247
00248 template<typename T>
00249 class VectorBufferBase : Noncopyable {
00250 public:
00251 void allocateBuffer(size_t newCapacity)
00252 {
00253 m_capacity = newCapacity;
00254 if (newCapacity > std::numeric_limits<size_t>::max() / sizeof(T))
00255 CRASH();
00256 m_buffer = static_cast<T*>(fastMalloc(newCapacity * sizeof(T)));
00257 }
00258
00259 void deallocateBuffer(T* bufferToDeallocate)
00260 {
00261 if (m_buffer == bufferToDeallocate)
00262 m_buffer = 0;
00263 fastFree(bufferToDeallocate);
00264 }
00265
00266 T* buffer() { return m_buffer; }
00267 const T* buffer() const { return m_buffer; }
00268 size_t capacity() const { return m_capacity; }
00269
00270 T* releaseBuffer()
00271 {
00272 T* buffer = m_buffer;
00273 m_buffer = 0;
00274 m_capacity = 0;
00275 return buffer;
00276 }
00277
00278 protected:
00279 VectorBufferBase()
00280 : m_buffer(0)
00281 , m_capacity(0)
00282 {
00283 }
00284
00285 VectorBufferBase(T* buffer, size_t capacity)
00286 : m_buffer(buffer)
00287 , m_capacity(capacity)
00288 {
00289 }
00290
00291 ~VectorBufferBase()
00292 {
00293
00294 }
00295
00296 T* m_buffer;
00297 size_t m_capacity;
00298 };
00299
00300 template<typename T, size_t inlineCapacity>
00301 class VectorBuffer;
00302
00303 template<typename T>
00304 class VectorBuffer<T, 0> : private VectorBufferBase<T> {
00305 private:
00306 typedef VectorBufferBase<T> Base;
00307 public:
00308 VectorBuffer()
00309 {
00310 }
00311
00312 VectorBuffer(size_t capacity)
00313 {
00314 allocateBuffer(capacity);
00315 }
00316
00317 ~VectorBuffer()
00318 {
00319 deallocateBuffer(buffer());
00320 }
00321
00322 void swap(VectorBuffer<T, 0>& other)
00323 {
00324 std::swap(m_buffer, other.m_buffer);
00325 std::swap(m_capacity, other.m_capacity);
00326 }
00327
00328 using Base::allocateBuffer;
00329 using Base::deallocateBuffer;
00330
00331 using Base::buffer;
00332 using Base::capacity;
00333
00334 using Base::releaseBuffer;
00335 private:
00336 using Base::m_buffer;
00337 using Base::m_capacity;
00338 };
00339
00340 template<typename T, size_t inlineCapacity>
00341 class VectorBuffer : private VectorBufferBase<T> {
00342 private:
00343 typedef VectorBufferBase<T> Base;
00344 public:
00345 VectorBuffer()
00346 : Base(inlineBuffer(), inlineCapacity)
00347 {
00348 }
00349
00350 VectorBuffer(size_t capacity)
00351 : Base(inlineBuffer(), inlineCapacity)
00352 {
00353 allocateBuffer(capacity);
00354 }
00355
00356 ~VectorBuffer()
00357 {
00358 deallocateBuffer(buffer());
00359 }
00360
00361 void allocateBuffer(size_t newCapacity)
00362 {
00363 if (newCapacity > inlineCapacity)
00364 Base::allocateBuffer(newCapacity);
00365 }
00366
00367 void deallocateBuffer(T* bufferToDeallocate)
00368 {
00369 if (bufferToDeallocate == inlineBuffer())
00370 return;
00371 Base::deallocateBuffer(bufferToDeallocate);
00372 }
00373
00374 using Base::buffer;
00375 using Base::capacity;
00376
00377 T* releaseBuffer()
00378 {
00379 if (buffer() == inlineBuffer())
00380 return 0;
00381 return Base::releaseBuffer();
00382 }
00383
00384 private:
00385 using Base::m_buffer;
00386 using Base::m_capacity;
00387
00388 static const size_t m_inlineBufferSize = inlineCapacity * sizeof(T);
00389 T* inlineBuffer() { return reinterpret_cast<T*>(&m_inlineBuffer); }
00390
00391
00392 char m_inlineBuffer[m_inlineBufferSize];
00393 };
00394
00395 template<typename T, size_t inlineCapacity = 0>
00396 class Vector {
00397 private:
00398 typedef VectorBuffer<T, inlineCapacity> Buffer;
00399 typedef VectorTypeOperations<T> TypeOperations;
00400
00401 public:
00402 typedef T ValueType;
00403
00404 typedef T* iterator;
00405 typedef const T* const_iterator;
00406
00407 Vector()
00408 : m_size(0)
00409 {
00410 }
00411
00412 explicit Vector(size_t size)
00413 : m_size(size)
00414 , m_buffer(size)
00415 {
00416 TypeOperations::initialize(begin(), end());
00417 }
00418
00419 ~Vector()
00420 {
00421 clear();
00422 }
00423
00424 Vector(const Vector&);
00425 template<size_t otherCapacity>
00426 Vector(const Vector<T, otherCapacity>&);
00427
00428 Vector& operator=(const Vector&);
00429 template<size_t otherCapacity>
00430 Vector& operator=(const Vector<T, otherCapacity>&);
00431
00432 size_t size() const { return m_size; }
00433 size_t capacity() const { return m_buffer.capacity(); }
00434 bool isEmpty() const { return !size(); }
00435
00436 T& at(size_t i)
00437 {
00438 ASSERT(i < size());
00439 return m_buffer.buffer()[i];
00440 }
00441 const T& at(size_t i) const
00442 {
00443 ASSERT(i < size());
00444 return m_buffer.buffer()[i];
00445 }
00446
00447 T& operator[](size_t i) { return at(i); }
00448 const T& operator[](size_t i) const { return at(i); }
00449
00450 T* data() { return m_buffer.buffer(); }
00451 const T* data() const { return m_buffer.buffer(); }
00452
00453 iterator begin() { return data(); }
00454 iterator end() { return begin() + m_size; }
00455 const_iterator begin() const { return data(); }
00456 const_iterator end() const { return begin() + m_size; }
00457
00458 T& first() { return at(0); }
00459 const T& first() const { return at(0); }
00460 T& last() { return at(size() - 1); }
00461 const T& last() const { return at(size() - 1); }
00462
00463 void shrink(size_t size);
00464 void grow(size_t size);
00465 void resize(size_t size);
00466 void reserveCapacity(size_t newCapacity);
00467 void shrinkCapacity(size_t newCapacity);
00468
00469 void clear() { if (m_size) shrink(0); }
00470
00471 template<typename U> void append(const U*, size_t);
00472 template<typename U> void append(const U&);
00473 template<typename U> void uncheckedAppend(const U& val);
00474 template<typename U, size_t c> void append(const Vector<U, c>&);
00475
00476 template<typename U> void insert(size_t position, const U*, size_t);
00477 template<typename U> void insert(size_t position, const U&);
00478 template<typename U, size_t c> void insert(size_t position, const Vector<U, c>&);
00479
00480 template<typename U> void prepend(const U*, size_t);
00481 template<typename U> void prepend(const U&);
00482 template<typename U, size_t c> void prepend(const Vector<U, c>&);
00483
00484 void remove(size_t position);
00485 void remove(size_t position, size_t length);
00486
00487 void removeLast()
00488 {
00489 ASSERT(!isEmpty());
00490 shrink(size() - 1);
00491 }
00492
00493 Vector(size_t size, const T& val)
00494 : m_size(size)
00495 , m_buffer(size)
00496 {
00497 TypeOperations::uninitializedFill(begin(), end(), val);
00498 }
00499
00500 void fill(const T&, size_t);
00501 void fill(const T& val) { fill(val, size()); }
00502
00503 template<typename Iterator> void appendRange(Iterator start, Iterator end);
00504
00505 T* releaseBuffer();
00506
00507 void swap(Vector<T, inlineCapacity>& other)
00508 {
00509 std::swap(m_size, other.m_size);
00510 m_buffer.swap(other.m_buffer);
00511 }
00512
00513 private:
00514 void expandCapacity(size_t newMinCapacity);
00515 const T* expandCapacity(size_t newMinCapacity, const T*);
00516 template<typename U> U* expandCapacity(size_t newMinCapacity, U*);
00517
00518 size_t m_size;
00519 Buffer m_buffer;
00520 };
00521
00522 template<typename T, size_t inlineCapacity>
00523 Vector<T, inlineCapacity>::Vector(const Vector& other)
00524 : m_size(other.size())
00525 , m_buffer(other.capacity())
00526 {
00527 TypeOperations::uninitializedCopy(other.begin(), other.end(), begin());
00528 }
00529
00530 template<typename T, size_t inlineCapacity>
00531 template<size_t otherCapacity>
00532 Vector<T, inlineCapacity>::Vector(const Vector<T, otherCapacity>& other)
00533 : m_size(other.size())
00534 , m_buffer(other.capacity())
00535 {
00536 TypeOperations::uninitializedCopy(other.begin(), other.end(), begin());
00537 }
00538
00539 template<typename T, size_t inlineCapacity>
00540 Vector<T, inlineCapacity>& Vector<T, inlineCapacity>::operator=(const Vector<T, inlineCapacity>& other)
00541 {
00542 if (&other == this)
00543 return *this;
00544
00545 if (size() > other.size())
00546 shrink(other.size());
00547 else if (other.size() > capacity()) {
00548 clear();
00549 reserveCapacity(other.size());
00550 }
00551
00552 std::copy(other.begin(), other.begin() + size(), begin());
00553 TypeOperations::uninitializedCopy(other.begin() + size(), other.end(), end());
00554 m_size = other.size();
00555
00556 return *this;
00557 }
00558
00559 template<typename T, size_t inlineCapacity>
00560 template<size_t otherCapacity>
00561 Vector<T, inlineCapacity>& Vector<T, inlineCapacity>::operator=(const Vector<T, otherCapacity>& other)
00562 {
00563 if (&other == this)
00564 return *this;
00565
00566 if (size() > other.size())
00567 shrink(other.size());
00568 else if (other.size() > capacity()) {
00569 clear();
00570 reserveCapacity(other.size());
00571 }
00572
00573 std::copy(other.begin(), other.begin() + size(), begin());
00574 TypeOperations::uninitializedCopy(other.begin() + size(), other.end(), end());
00575 m_size = other.size();
00576
00577 return *this;
00578 }
00579
00580 template<typename T, size_t inlineCapacity>
00581 void Vector<T, inlineCapacity>::fill(const T& val, size_t newSize)
00582 {
00583 if (size() > newSize)
00584 shrink(newSize);
00585 else if (newSize > capacity()) {
00586 clear();
00587 reserveCapacity(newSize);
00588 }
00589
00590 std::fill(begin(), end(), val);
00591 TypeOperations::uninitializedFill(end(), begin() + newSize, val);
00592 m_size = newSize;
00593 }
00594
00595 template<typename T, size_t inlineCapacity>
00596 template<typename Iterator>
00597 void Vector<T, inlineCapacity>::appendRange(Iterator start, Iterator end)
00598 {
00599 for (Iterator it = start; it != end; ++it)
00600 append(*it);
00601 }
00602
00603 template<typename T, size_t inlineCapacity>
00604 void Vector<T, inlineCapacity>::expandCapacity(size_t newMinCapacity)
00605 {
00606 reserveCapacity(max(newMinCapacity, max(static_cast<size_t>(16), capacity() + capacity() / 4 + 1)));
00607 }
00608
00609 template<typename T, size_t inlineCapacity>
00610 const T* Vector<T, inlineCapacity>::expandCapacity(size_t newMinCapacity, const T* ptr)
00611 {
00612 if (ptr < begin() || ptr >= end()) {
00613 expandCapacity(newMinCapacity);
00614 return ptr;
00615 }
00616 size_t index = ptr - begin();
00617 expandCapacity(newMinCapacity);
00618 return begin() + index;
00619 }
00620
00621 template<typename T, size_t inlineCapacity> template<typename U>
00622 inline U* Vector<T, inlineCapacity>::expandCapacity(size_t newMinCapacity, U* ptr)
00623 {
00624 expandCapacity(newMinCapacity);
00625 return ptr;
00626 }
00627
00628 template<typename T, size_t inlineCapacity>
00629 void Vector<T, inlineCapacity>::resize(size_t size)
00630 {
00631 if (size <= m_size)
00632 TypeOperations::destruct(begin() + size, end());
00633 else {
00634 if (size > capacity())
00635 expandCapacity(size);
00636 if (begin())
00637 TypeOperations::initialize(end(), begin() + size);
00638 }
00639
00640 m_size = size;
00641 }
00642
00643 template<typename T, size_t inlineCapacity>
00644 void Vector<T, inlineCapacity>::shrink(size_t size)
00645 {
00646 ASSERT(size <= m_size);
00647 TypeOperations::destruct(begin() + size, end());
00648 m_size = size;
00649 }
00650
00651 template<typename T, size_t inlineCapacity>
00652 void Vector<T, inlineCapacity>::grow(size_t size)
00653 {
00654 ASSERT(size >= m_size);
00655 if (size > capacity())
00656 expandCapacity(size);
00657 if (begin())
00658 TypeOperations::initialize(end(), begin() + size);
00659 m_size = size;
00660 }
00661
00662 template<typename T, size_t inlineCapacity>
00663 void Vector<T, inlineCapacity>::reserveCapacity(size_t newCapacity)
00664 {
00665 if (newCapacity <= capacity())
00666 return;
00667 T* oldBuffer = begin();
00668 T* oldEnd = end();
00669 m_buffer.allocateBuffer(newCapacity);
00670 if (begin())
00671 TypeOperations::move(oldBuffer, oldEnd, begin());
00672 m_buffer.deallocateBuffer(oldBuffer);
00673 }
00674
00675 template<typename T, size_t inlineCapacity>
00676 void Vector<T, inlineCapacity>::shrinkCapacity(size_t newCapacity)
00677 {
00678 if (newCapacity >= capacity())
00679 return;
00680
00681 resize(min(m_size, newCapacity));
00682
00683 T* oldBuffer = begin();
00684 if (newCapacity > 0) {
00685 T* oldEnd = end();
00686 m_buffer.allocateBuffer(newCapacity);
00687 if (begin() != oldBuffer)
00688 TypeOperations::move(oldBuffer, oldEnd, begin());
00689 }
00690
00691 m_buffer.deallocateBuffer(oldBuffer);
00692 }
00693
00694
00695
00696
00697
00698 template<typename T, size_t inlineCapacity> template<typename U>
00699 void Vector<T, inlineCapacity>::append(const U* data, size_t dataSize)
00700 {
00701 size_t newSize = m_size + dataSize;
00702 if (newSize > capacity()) {
00703 data = expandCapacity(newSize, data);
00704 if (!begin())
00705 return;
00706 }
00707 T* dest = end();
00708 for (size_t i = 0; i < dataSize; ++i)
00709 new (&dest[i]) T(data[i]);
00710 m_size = newSize;
00711 }
00712
00713 template<typename T, size_t inlineCapacity> template<typename U>
00714 inline void Vector<T, inlineCapacity>::append(const U& val)
00715 {
00716 const U* ptr = &val;
00717 if (size() == capacity()) {
00718 ptr = expandCapacity(size() + 1, ptr);
00719 if (!begin())
00720 return;
00721 }
00722
00723 #if COMPILER(MSVC7)
00724
00725
00726
00727
00728
00729
00730 new (end()) T(static_cast<T>(*ptr));
00731 #else
00732 new (end()) T(*ptr);
00733 #endif
00734 ++m_size;
00735 }
00736
00737
00738
00739
00740 template<typename T, size_t inlineCapacity> template<typename U>
00741 inline void Vector<T, inlineCapacity>::uncheckedAppend(const U& val)
00742 {
00743 ASSERT(size() < capacity());
00744 const U* ptr = &val;
00745 new (end()) T(*ptr);
00746 ++m_size;
00747 }
00748
00749 template<typename T, size_t inlineCapacity> template<typename U, size_t c>
00750 inline void Vector<T, inlineCapacity>::append(const Vector<U, c>& val)
00751 {
00752 append(val.begin(), val.size());
00753 }
00754
00755 template<typename T, size_t inlineCapacity> template<typename U>
00756 void Vector<T, inlineCapacity>::insert(size_t position, const U* data, size_t dataSize)
00757 {
00758 ASSERT(position <= size());
00759 size_t newSize = m_size + dataSize;
00760 if (newSize > capacity()) {
00761 data = expandCapacity(newSize, data);
00762 if (!begin())
00763 return;
00764 }
00765 T* spot = begin() + position;
00766 TypeOperations::moveOverlapping(spot, end(), spot + dataSize);
00767 for (size_t i = 0; i < dataSize; ++i)
00768 new (&spot[i]) T(data[i]);
00769 m_size = newSize;
00770 }
00771
00772 template<typename T, size_t inlineCapacity> template<typename U>
00773 inline void Vector<T, inlineCapacity>::insert(size_t position, const U& val)
00774 {
00775 ASSERT(position <= size());
00776 const U* data = &val;
00777 if (size() == capacity()) {
00778 data = expandCapacity(size() + 1, data);
00779 if (!begin())
00780 return;
00781 }
00782 T* spot = begin() + position;
00783 TypeOperations::moveOverlapping(spot, end(), spot + 1);
00784 new (spot) T(*data);
00785 ++m_size;
00786 }
00787
00788 template<typename T, size_t inlineCapacity> template<typename U, size_t c>
00789 inline void Vector<T, inlineCapacity>::insert(size_t position, const Vector<U, c>& val)
00790 {
00791 insert(position, val.begin(), val.size());
00792 }
00793
00794 template<typename T, size_t inlineCapacity> template<typename U>
00795 void Vector<T, inlineCapacity>::prepend(const U* data, size_t dataSize)
00796 {
00797 insert(0, data, dataSize);
00798 }
00799
00800 template<typename T, size_t inlineCapacity> template<typename U>
00801 inline void Vector<T, inlineCapacity>::prepend(const U& val)
00802 {
00803 insert(0, val);
00804 }
00805
00806 template<typename T, size_t inlineCapacity> template<typename U, size_t c>
00807 inline void Vector<T, inlineCapacity>::prepend(const Vector<U, c>& val)
00808 {
00809 insert(0, val.begin(), val.size());
00810 }
00811
00812 template<typename T, size_t inlineCapacity>
00813 inline void Vector<T, inlineCapacity>::remove(size_t position)
00814 {
00815 ASSERT(position < size());
00816 T* spot = begin() + position;
00817 spot->~T();
00818 TypeOperations::moveOverlapping(spot + 1, end(), spot);
00819 --m_size;
00820 }
00821
00822 template<typename T, size_t inlineCapacity>
00823 inline void Vector<T, inlineCapacity>::remove(size_t position, size_t length)
00824 {
00825 ASSERT(position < size());
00826 ASSERT(position + length < size());
00827 T* beginSpot = begin() + position;
00828 T* endSpot = beginSpot + length;
00829 TypeOperations::destruct(beginSpot, endSpot);
00830 TypeOperations::moveOverlapping(endSpot, end(), beginSpot);
00831 m_size -= length;
00832 }
00833
00834 template<typename T, size_t inlineCapacity>
00835 inline T* Vector<T, inlineCapacity>::releaseBuffer()
00836 {
00837 T* buffer = m_buffer.releaseBuffer();
00838 if (inlineCapacity && !buffer && m_size) {
00839
00840
00841
00842 size_t bytes = m_size * sizeof(T);
00843 buffer = static_cast<T*>(fastMalloc(bytes));
00844 memcpy(buffer, data(), bytes);
00845 }
00846 ASSERT(buffer);
00847 m_size = 0;
00848 return buffer;
00849 }
00850
00851 template<typename T, size_t inlineCapacity>
00852 void deleteAllValues(const Vector<T, inlineCapacity>& collection)
00853 {
00854 typedef typename Vector<T, inlineCapacity>::const_iterator iterator;
00855 iterator end = collection.end();
00856 for (iterator it = collection.begin(); it != end; ++it)
00857 delete *it;
00858 }
00859
00860 template<typename T, size_t inlineCapacity>
00861 inline void swap(Vector<T, inlineCapacity>& a, Vector<T, inlineCapacity>& b)
00862 {
00863 a.swap(b);
00864 }
00865
00866 template<typename T, size_t inlineCapacity>
00867 bool operator==(const Vector<T, inlineCapacity>& a, const Vector<T, inlineCapacity>& b)
00868 {
00869 if (a.size() != b.size())
00870 return false;
00871
00872 return VectorTypeOperations<T>::compare(a.data(), b.data(), a.size());
00873 }
00874
00875 template<typename T, size_t inlineCapacity>
00876 inline bool operator!=(const Vector<T, inlineCapacity>& a, const Vector<T, inlineCapacity>& b)
00877 {
00878 return !(a == b);
00879 }
00880
00881
00882 }
00883
00884 using WTF::Vector;
00885
00886 #endif // WTF_Vector_h