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