JavaScriptCore/wtf/Vector.h

   1 // -*- mode: c++; c-basic-offset: 4 -*-
   2 /*
   3  *  This file is part of the KDE libraries
   4  *  Copyright (C) 2005, 2006 Apple Computer, Inc.
   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 "VectorTraits.h"
  29 #include <limits>
  30 #include <stdlib.h>
  31 #include <utility>
  32
  33 namespace WTF {
  34
  35     using std::min;
  36     using std::max;
  37
  38     template <bool needsDestruction, typename T>
  39     class VectorDestructor;
  40
  41     template<typename T>
  42     struct VectorDestructor<false, T>
  43     {
  44         static void destruct(T*, T*) {}
  45     };
  46
  47     template<typename T>
  48     struct VectorDestructor<true, T>
  49     {
  50         static void destruct(T* begin, T* end)
  51         {
  52             for (T* cur = begin; cur != end; ++cur)
  53                 cur->~T();
  54         }
  55     };
  56
  57     template <bool needsInitialization, bool canInitializeWithMemset, typename T>
  58     class VectorInitializer;
  59
  60     template<bool ignore, typename T>
  61     struct VectorInitializer<false, ignore, T>
  62     {
  63         static void initialize(T*, T*) {}
  64     };
  65
  66     template<typename T>
  67     struct VectorInitializer<true, false, T>
  68     {
  69         static void initialize(T* begin, T* end)
  70         {
  71             for (T* cur = begin; cur != end; ++cur)
  72                 new (cur) T;
  73         }
  74     };
  75
  76     template<typename T>
  77     struct VectorInitializer<true, true, T>
  78     {
  79         static void initialize(T* begin, T* end)
  80         {
  81             memset(begin, 0, reinterpret_cast<char*>(end) - reinterpret_cast<char*>(begin));
  82         }
  83     };
  84
  85     template <bool canMoveWithMemcpy, typename T>
  86     class VectorMover;
  87
  88     template<typename T>
  89     struct VectorMover<false, T>
  90     {
  91         static void move(const T* src, const T* srcEnd, T* dst)
  92         {
  93             while (src != srcEnd) {
  94                 new (dst) T(*src);
  95                 src->~T();
  96                 ++dst;
  97                 ++src;
  98             }
  99         }
 100         static void moveOverlapping(const T* src, const T* srcEnd, T* dst)
 101         {
 102             if (src > dst)
 103                 move(src, srcEnd, dst);
 104             else {
 105                 T* dstEnd = dst + (srcEnd - src);
 106                 while (src != srcEnd) {
 107                     --srcEnd;
 108                     --dstEnd;
 109                     new (dstEnd) T(*srcEnd);
 110                     srcEnd->~T();
 111                 }
 112             }
 113         }
 114     };
 115
 116     template<typename T>
 117     struct VectorMover<true, T>
 118     {
 119         static void move(const T* src, const T* srcEnd, T* dst)
 120         {
 121             memcpy(dst, src, reinterpret_cast<const char*>(srcEnd) - reinterpret_cast<const char*>(src));
 122         }
 123         static void moveOverlapping(const T* src, const T* srcEnd, T* dst)
 124         {
 125             memmove(dst, src, reinterpret_cast<const char*>(srcEnd) - reinterpret_cast<const char*>(src));
 126         }
 127     };
 128
 129     template <bool canCopyWithMemcpy, typename T>
 130     class VectorCopier;
 131
 132     template<typename T>
 133     struct VectorCopier<false, T>
 134     {
 135         static void uninitializedCopy(const T* src, const T* srcEnd, T* dst)
 136         {
 137             while (src != srcEnd) {
 138                 new (dst) T(*src);
 139                 ++dst;
 140                 ++src;
 141             }
 142         }
 143     };
 144
 145     template<typename T>
 146     struct VectorCopier<true, T>
 147     {
 148         static void uninitializedCopy(const T* src, const T* srcEnd, T* dst)
 149         {
 150             memcpy(dst, src, reinterpret_cast<const char*>(srcEnd) - reinterpret_cast<const char*>(src));
 151         }
 152     };
 153
 154     template <bool canFillWithMemset, typename T>
 155     class VectorFiller;
 156
 157     template<typename T>
 158     struct VectorFiller<false, T>
 159     {
 160         static void uninitializedFill(T* dst, T* dstEnd, const T& val)
 161         {
 162             while (dst != dstEnd) {
 163                 new (dst) T(val);
 164                 ++dst;
 165             }
 166         }
 167     };
 168
 169     template<typename T>
 170     struct VectorFiller<true, T>
 171     {
 172         static void uninitializedFill(T* dst, T* dstEnd, const T& val)
 173         {
 174             ASSERT(sizeof(T) == sizeof(char));
 175             memset(dst, val, dstEnd - dst);
 176         }
 177     };
 178
 179     template<typename T>
 180     struct VectorTypeOperations
 181     {
 182         static void destruct(T* begin, T* end)
 183         {
 184             VectorDestructor<VectorTraits<T>::needsDestruction, T>::destruct(begin, end);
 185         }
 186
 187         static void initialize(T* begin, T* end)
 188         {
 189             VectorInitializer<VectorTraits<T>::needsInitialization, VectorTraits<T>::canInitializeWithMemset, T>::initialize(begin, end);
 190         }
 191
 192         static void move(const T* src, const T* srcEnd, T* dst)
 193         {
 194             VectorMover<VectorTraits<T>::canMoveWithMemcpy, T>::move(src, srcEnd, dst);
 195         }
 196
 197         static void moveOverlapping(const T* src, const T* srcEnd, T* dst)
 198         {
 199             VectorMover<VectorTraits<T>::canMoveWithMemcpy, T>::moveOverlapping(src, srcEnd, dst);
 200         }
 201
 202         static void uninitializedCopy(const T* src, const T* srcEnd, T* dst)
 203         {
 204             VectorCopier<VectorTraits<T>::canCopyWithMemcpy, T>::uninitializedCopy(src, srcEnd, dst);
 205         }
 206
 207         static void uninitializedFill(T* dst, T* dstEnd, const T& val)
 208         {
 209             VectorFiller<VectorTraits<T>::canFillWithMemset, T>::uninitializedFill(dst, dstEnd, val);
 210         }
 211     };
 212
 213     template<typename T, size_t inlineCapacity>
 214     class VectorBuffer;
 215
 216     template<typename T>
 217     class VectorBuffer<T, 0> {
 218     public:
 219         VectorBuffer()
 220             : m_buffer(0), m_capacity(0)
 221         {
 222         }
 223
 224         VectorBuffer(size_t capacity)
 225 #if !ASSERT_DISABLED
 226             : m_capacity(0)
 227 #endif
 228         {
 229             allocateBuffer(capacity);
 230         }
 231
 232         ~VectorBuffer()
 233         {
 234             deallocateBuffer(m_buffer);
 235         }
 236
 237         static void deallocateBuffer(T* buffer)
 238         {
 239             fastFree(buffer);
 240         }
 241
 242         void allocateBuffer(size_t newCapacity)
 243         {
 244             ASSERT(newCapacity >= m_capacity);
 245             m_capacity = newCapacity;
 246             if (newCapacity > std::numeric_limits<size_t>::max() / sizeof(T))
 247                 abort();
 248             m_buffer = static_cast<T*>(fastMalloc(newCapacity * sizeof(T)));
 249         }
 250
 251         T* buffer() { return m_buffer; }
 252         const T* buffer() const { return m_buffer; }
 253         size_t capacity() const { return m_capacity; }
 254
 255         void swap(VectorBuffer<T, 0>& other)
 256         {
 257             std::swap(m_capacity, other.m_capacity);
 258             std::swap(m_buffer, other.m_buffer);
 259         }
 260
 261         T* releaseBuffer()
 262         {
 263             T* buffer = m_buffer;
 264             m_buffer = 0;
 265             m_capacity = 0;
 266             return buffer;
 267         }
 268
 269     protected:
 270         VectorBuffer(T* buffer, size_t capacity)
 271             : m_buffer(buffer), m_capacity(capacity)
 272         {
 273         }
 274
 275         T* m_buffer;
 276
 277     private:
 278         size_t m_capacity;
 279     };
 280
 281     template<typename T, size_t inlineCapacity>
 282     class VectorBuffer : private VectorBuffer<T, 0> {
 283     private:
 284         typedef VectorBuffer<T, 0> BaseBuffer;
 285     public:
 286         VectorBuffer()
 287             : BaseBuffer(inlineBuffer(), inlineCapacity)
 288         {
 289         }
 290
 291         VectorBuffer(size_t capacity)
 292             : BaseBuffer(inlineBuffer(), inlineCapacity)
 293         {
 294             if (capacity > inlineCapacity)
 295                 allocateBuffer(capacity);
 296         }
 297
 298         ~VectorBuffer()
 299         {
 300             if (buffer() == inlineBuffer())
 301                 BaseBuffer::m_buffer = 0;
 302         }
 303
 304         void deallocateBuffer(T* buffer)
 305         {
 306             if (buffer != inlineBuffer())
 307                 BaseBuffer::deallocateBuffer(buffer);
 308         }
 309
 310         using BaseBuffer::allocateBuffer;
 311
 312         using BaseBuffer::buffer;
 313         using BaseBuffer::capacity;
 314
 315         T* releaseBuffer()
 316         {
 317             if (buffer() == inlineBuffer())
 318                 return 0;
 319             return BaseBuffer::releaseBuffer();
 320         }
 321
 322         void swap(VectorBuffer<T, inlineCapacity>&);
 323
 324     private:
 325         static const size_t m_inlineBufferSize = inlineCapacity * sizeof(T);
 326         T* inlineBuffer() { return reinterpret_cast<T*>(&m_inlineBuffer); }
 327
 328         // FIXME: Nothing guarantees this buffer is appropriately aligned to hold objects of type T.
 329         char m_inlineBuffer[m_inlineBufferSize];
 330     };
 331
 332     template<typename T, size_t inlineCapacity = 0>
 333     class Vector {
 334     private:
 335         typedef VectorBuffer<T, inlineCapacity> Impl;
 336         typedef VectorTypeOperations<T> TypeOperations;
 337
 338     public:
 339         typedef T* iterator;
 340         typedef const T* const_iterator;
 341
 342         Vector()
 343             : m_size(0)
 344         {
 345         }
 346
 347         explicit Vector(size_t size)
 348             : m_size(0)
 349         {
 350             resize(size);
 351         }
 352
 353         ~Vector()
 354         {
 355             clear();
 356         }
 357
 358         Vector(const Vector&);
 359         template<size_t otherCapacity>
 360         Vector(const Vector<T, otherCapacity>&);
 361
 362         Vector& operator=(const Vector&);
 363         template<size_t otherCapacity>
 364         Vector& operator=(const Vector<T, otherCapacity>&);
 365
 366         size_t size() const { return m_size; }
 367         size_t capacity() const { return m_impl.capacity(); }
 368         bool isEmpty() const { return !size(); }
 369
 370         T& at(size_t i)
 371         {
 372             ASSERT(i < size());
 373             return m_impl.buffer()[i];
 374         }
 375         const T& at(size_t i) const
 376         {
 377             ASSERT(i < size());
 378             return m_impl.buffer()[i];
 379         }
 380
 381         T& operator[](long i) { return at(i); }
 382         const T& operator[](long i) const { return at(i); }
 383         T& operator[](unsigned long i) { return at(i); }
 384         const T& operator[](unsigned long i) const { return at(i); }
 385         T& operator[](int i) { return at(i); }
 386         const T& operator[](int i) const { return at(i); }
 387         T& operator[](unsigned i) { return at(i); }
 388         const T& operator[](unsigned i) const { return at(i); }
 389         T& operator[](short i) { return at(i); }
 390         const T& operator[](short i) const { return at(i); }
 391         T& operator[](unsigned short i) { return at(i); }
 392         const T& operator[](unsigned short i) const { return at(i); }
 393
 394         T* data() { return m_impl.buffer(); }
 395         const T* data() const { return m_impl.buffer(); }
 396         operator T*() { return data(); }
 397         operator const T*() const { return data(); }
 398
 399         iterator begin() { return data(); }
 400         iterator end() { return begin() + m_size; }
 401         const_iterator begin() const { return data(); }
 402         const_iterator end() const { return begin() + m_size; }
 403
 404         T& first() { return at(0); }
 405         const T& first() const { return at(0); }
 406         T& last() { return at(size() - 1); }
 407         const T& last() const { return at(size() - 1); }
 408
 409         void resize(size_t size);
 410         void reserveCapacity(size_t newCapacity);
 411
 412         void clear() { resize(0); }
 413
 414         template<typename U> void append(const U*, size_t);
 415         template<typename U> void append(const U&);
 416         template<typename U, size_t c> void append(const Vector<U, c>&);
 417
 418         template<typename U> void insert(size_t position, const U&);
 419
 420         void remove(size_t position);
 421
 422         void removeLast()
 423         {
 424             ASSERT(!isEmpty());
 425             resize(size() - 1);
 426         }
 427
 428         Vector(size_t size, const T& val)
 429             : m_size(size)
 430             , m_impl(size)
 431         {
 432             TypeOperations::uninitializedFill(begin(), end(), val);
 433         }
 434
 435         void fill(const T&, size_t);
 436         void fill(const T& val) { fill(val, size()); }
 437
 438         T* releaseBuffer();
 439
 440         void swap(Vector<T, inlineCapacity>& other)
 441         {
 442             std::swap(m_size, other.m_size);
 443             m_impl.swap(other.m_impl);
 444         }
 445
 446     private:
 447         void expandCapacity(size_t newMinCapacity);
 448         const T* expandCapacity(size_t newMinCapacity, const T*);
 449         template<typename U> U* expandCapacity(size_t newMinCapacity, U*);
 450
 451         size_t m_size;
 452         Impl m_impl;
 453     };
 454
 455     template<typename T, size_t inlineCapacity>
 456     Vector<T, inlineCapacity>::Vector(const Vector& other)
 457         : m_size(other.size())
 458         , m_impl(other.capacity())
 459     {
 460         TypeOperations::uninitializedCopy(other.begin(), other.end(), begin());
 461     }
 462
 463     template<typename T, size_t inlineCapacity>
 464     template<size_t otherCapacity>
 465     Vector<T, inlineCapacity>::Vector(const Vector<T, otherCapacity>& other)
 466         : m_size(other.size())
 467         , m_impl(other.capacity())
 468     {
 469         TypeOperations::uninitializedCopy(other.begin(), other.end(), begin());
 470     }
 471
 472     template<typename T, size_t inlineCapacity>
 473     Vector<T, inlineCapacity>& Vector<T, inlineCapacity>::operator=(const Vector<T, inlineCapacity>& other)
 474     {
 475         if (&other == this)
 476             return *this;
 477
 478         if (size() > other.size())
 479             resize(other.size());
 480         else if (other.size() > capacity()) {
 481             clear();
 482             reserveCapacity(other.size());
 483         }
 484
 485         std::copy(other.begin(), other.begin() + size(), begin());
 486         TypeOperations::uninitializedCopy(other.begin() + size(), other.end(), end());
 487         m_size = other.size();
 488
 489         return *this;
 490     }
 491
 492     template<typename T, size_t inlineCapacity>
 493     template<size_t otherCapacity>
 494     Vector<T, inlineCapacity>& Vector<T, inlineCapacity>::operator=(const Vector<T, otherCapacity>& other)
 495     {
 496         if (&other == this)
 497             return *this;
 498
 499         if (size() > other.size())
 500             resize(other.size());
 501         else if (other.size() > capacity()) {
 502             clear();
 503             reserveCapacity(other.size());
 504         }
 505
 506         std::copy(other.begin(), other.begin() + size(), begin());
 507         TypeOperations::uninitializedCopy(other.begin() + size(), other.end(), end());
 508         m_size = other.size();
 509
 510         return *this;
 511     }
 512
 513     template<typename T, size_t inlineCapacity>
 514     void Vector<T, inlineCapacity>::fill(const T& val, size_t newSize)
 515     {
 516         if (size() > newSize)
 517             resize(newSize);
 518         else if (newSize > capacity()) {
 519             clear();
 520             reserveCapacity(newSize);
 521         }
 522
 523         std::fill(begin(), end(), val);
 524         TypeOperations::uninitializedFill(end(), begin() + newSize, val);
 525         m_size = newSize;
 526     }
 527
 528     template<typename T, size_t inlineCapacity>
 529     void Vector<T, inlineCapacity>::expandCapacity(size_t newMinCapacity)
 530     {
 531         reserveCapacity(max(newMinCapacity, max(static_cast<size_t>(16), capacity() + capacity() / 4 + 1)));
 532     }
 533
 534     template<typename T, size_t inlineCapacity>
 535     const T* Vector<T, inlineCapacity>::expandCapacity(size_t newMinCapacity, const T* ptr)
 536     {
 537         if (ptr < begin() || ptr >= end()) {
 538             expandCapacity(newMinCapacity);
 539             return ptr;
 540         }
 541         size_t index = ptr - begin();
 542         expandCapacity(newMinCapacity);
 543         return begin() + index;
 544     }
 545
 546     template<typename T, size_t inlineCapacity> template<typename U>
 547     inline U* Vector<T, inlineCapacity>::expandCapacity(size_t newMinCapacity, U* ptr)
 548     {
 549         expandCapacity(newMinCapacity);
 550         return ptr;
 551     }
 552
 553     template<typename T, size_t inlineCapacity>
 554     void Vector<T, inlineCapacity>::resize(size_t size)
 555     {
 556         if (size <= m_size)
 557             TypeOperations::destruct(begin() + size, end());
 558         else {
 559             if (size > capacity())
 560                 expandCapacity(size);
 561             TypeOperations::initialize(end(), begin() + size);
 562         }
 563
 564         m_size = size;
 565     }
 566
 567     template<typename T, size_t inlineCapacity>
 568     void Vector<T, inlineCapacity>::reserveCapacity(size_t newCapacity)
 569     {
 570         if (newCapacity < capacity())
 571             return;
 572         T* oldBuffer = begin();
 573         T* oldEnd = end();
 574         m_impl.allocateBuffer(newCapacity);
 575         TypeOperations::move(oldBuffer, oldEnd, begin());
 576         m_impl.deallocateBuffer(oldBuffer);
 577     }
 578
 579     // Templatizing these is better than just letting the conversion happen implicitly,
 580     // because for instance it allows a PassRefPtr to be appended to a RefPtr vector
 581     // without refcount thrash.
 582
 583     template<typename T, size_t inlineCapacity> template<typename U>
 584     void Vector<T, inlineCapacity>::append(const U* data, size_t dataSize)
 585     {
 586         size_t newSize = m_size + dataSize;
 587         if (newSize > capacity())
 588             data = expandCapacity(newSize, data);
 589         T* dest = end();
 590         for (size_t i = 0; i < dataSize; ++i)
 591             new (&dest[i]) T(data[i]);
 592         m_size = newSize;
 593     }
 594
 595     template<typename T, size_t inlineCapacity> template<typename U>
 596     inline void Vector<T, inlineCapacity>::append(const U& val)
 597     {
 598         const U* ptr = &val;
 599         if (size() == capacity())
 600             ptr = expandCapacity(size() + 1, ptr);
 601         new (end()) T(*ptr);
 602         ++m_size;
 603     }
 604
 605     template<typename T, size_t inlineCapacity> template<typename U, size_t c>
 606     inline void Vector<T, inlineCapacity>::append(const Vector<U, c>& val)
 607     {
 608         append(val.begin(), val.size());
 609     }
 610
 611     template<typename T, size_t inlineCapacity> template<typename U>
 612     inline void Vector<T, inlineCapacity>::insert(size_t position, const U& val)
 613     {
 614         ASSERT(position <= size());
 615         const U* ptr = &val;
 616         if (size() == capacity())
 617             ptr = expandCapacity(size() + 1, ptr);
 618         T* spot = begin() + position;
 619         TypeOperations::moveOverlapping(spot, end(), spot + 1);
 620         new (spot) T(*ptr);
 621         ++m_size;
 622     }
 623
 624     template<typename T, size_t inlineCapacity>
 625     inline void Vector<T, inlineCapacity>::remove(size_t position)
 626     {
 627         ASSERT(position < size());
 628         T* spot = begin() + position;
 629         spot->~T();
 630         TypeOperations::moveOverlapping(spot + 1, end(), spot);
 631         --m_size;
 632     }
 633
 634     template<typename T, size_t inlineCapacity>
 635     T* Vector<T, inlineCapacity>::releaseBuffer()
 636     {
 637         T* buffer = m_impl.releaseBuffer();
 638         if (!buffer && m_size) {
 639             // If the vector had some data, but no buffer to release,
 640             // that means it was using the inline buffer. In that case,
 641             // we create a brand new buffer so the caller always gets one.
 642             size_t bytes = m_size * sizeof(T);
 643             buffer = static_cast<T*>(fastMalloc(bytes));
 644             memcpy(buffer, data(), bytes);
 645         }
 646         m_size = 0;
 647         return buffer;
 648     }
 649
 650     template<typename T, size_t inlineCapacity>
 651     void deleteAllValues(const Vector<T, inlineCapacity>& collection)
 652     {
 653         typedef typename Vector<T, inlineCapacity>::const_iterator iterator;
 654         iterator end = collection.end();
 655         for (iterator it = collection.begin(); it != end; ++it)
 656             delete *it;
 657     }
 658
 659     template<typename T, size_t inlineCapacity>
 660     inline void swap(Vector<T, inlineCapacity>& a, Vector<T, inlineCapacity>& b)
 661     {
 662         a.swap(b);
 663     }
 664
 665 } // namespace WTF
 666
 667 using WTF::Vector;
 668
 669 #endif // WTF_Vector_h