• Skip to content
  • Skip to link menu
KDE 4.1 API Reference
  • KDE API Reference
  • kdelibs
  • Sitemap
  • Contact Us
 

WTF

Vector.h

Go to the documentation of this file.
00001 // -*- mode: c++; c-basic-offset: 4 -*-
00002 /*
00003  *  This file is part of the KDE libraries
00004  *  Copyright (C) 2005, 2006, 2007, 2008 Apple Inc. All rights reserved.
00005  *
00006  *  This library is free software; you can redistribute it and/or
00007  *  modify it under the terms of the GNU Library General Public
00008  *  License as published by the Free Software Foundation; either
00009  *  version 2 of the License, or (at your option) any later version.
00010  *
00011  *  This library is distributed in the hope that it will be useful,
00012  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
00013  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00014  *  Library General Public License for more details.
00015  *
00016  *  You should have received a copy of the GNU Library General Public License
00017  *  along with this library; see the file COPYING.LIB.  If not, write to
00018  *  the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
00019  *  Boston, MA 02110-1301, USA.
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 // Temporary workaround for Win32.
00036 // We should use NOMINMAX instead.
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             // FIXME: It would be nice to find a way to ASSERT that m_buffer hasn't leaked here.
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         // FIXME: Nothing guarantees this buffer is appropriately aligned to hold objects of type T.
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     // Templatizing these is better than just letting the conversion happen implicitly,
00695     // because for instance it allows a PassRefPtr to be appended to a RefPtr vector
00696     // without refcount thrash.
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         // FIXME: MSVC7 generates compilation errors when trying to assign
00725         // a pointer to a Vector of its base class (i.e. can't downcast). So far
00726         // I've been unable to determine any logical reason for this, so I can
00727         // only assume it is a bug with the compiler. Casting is a bad solution,
00728         // however, because it subverts implicit conversions, so a better 
00729         // one is needed. 
00730         new (end()) T(static_cast<T>(*ptr));
00731 #else
00732         new (end()) T(*ptr);
00733 #endif
00734         ++m_size;
00735     }
00736 
00737     // This version of append saves a branch in the case where you know that the
00738     // vector's capacity is large enough for the append to succeed.
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             // If the vector had some data, but no buffer to release,
00840             // that means it was using the inline buffer. In that case,
00841             // we create a brand new buffer so the caller always gets one.
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 } // namespace WTF
00883 
00884 using WTF::Vector;
00885 
00886 #endif // WTF_Vector_h

WTF

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

kdelibs

Skip menu "kdelibs"
  • DNSSD
  • Interfaces
  •   KHexEdit
  •   KMediaPlayer
  •   KSpeech
  •   KTextEditor
  • Kate
  • kconf_update
  • KDE3Support
  •   KUnitTest
  • KDECore
  • KDED
  • KDEsu
  • KDEUI
  • KDocTools
  • KFile
  • KHTML
  • KImgIO
  • KInit
  • KIO
  • KIOSlave
  • KJS
  •   KJS-API
  •   WTF
  • kjsembed
  • KNewStuff
  • KParts
  • Kross
  • KUtils
  • Nepomuk
  • Solid
  • Sonnet
  • ThreadWeaver
Generated for kdelibs by doxygen 1.5.4
This website is maintained by Adriaan de Groot and Allen Winter.
KDE® and the K Desktop Environment® logo are registered trademarks of KDE e.V. | Legal