include/am-vector.h
author David Anderson <dvander@alliedmods.net>
Mon Aug 26 20:41:58 2013 -0700 (2013-08-26)
changeset 10 0ac292cc1467
parent 6 afbfab9b416e
child 11 cfe800908837
permissions -rw-r--r--
Add move semantics and fix some bugs.
     1 // vim: set sts=8 ts=2 sw=2 tw=99 et:
     2 //
     3 // Copyright (C) 2013, David Anderson and AlliedModders LLC
     4 // All rights reserved.
     5 // 
     6 // Redistribution and use in source and binary forms, with or without
     7 // modification, are permitted provided that the following conditions are met:
     8 // 
     9 //  * Redistributions of source code must retain the above copyright notice, this
    10 //    list of conditions and the following disclaimer.
    11 //  * Redistributions in binary form must reproduce the above copyright notice,
    12 //    this list of conditions and the following disclaimer in the documentation
    13 //    and/or other materials provided with the distribution.
    14 //  * Neither the name of AlliedModders LLC nor the names of its contributors
    15 //    may be used to endorse or promote products derived from this software
    16 //    without specific prior written permission.
    17 //
    18 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
    19 // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
    20 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
    21 // ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
    22 // LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
    23 // CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
    24 // SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
    25 // INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
    26 // CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
    27 // ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
    28 // POSSIBILITY OF SUCH DAMAGE.
    29 
    30 #ifndef _INCLUDE_KEIMA_TPL_CPP_VECTOR_H_
    31 #define _INCLUDE_KEIMA_TPL_CPP_VECTOR_H_
    32 
    33 #include <new>
    34 #include <stdlib.h>
    35 #include <am-allocator-policies.h>
    36 #include <am-utility.h>
    37 #include <am-moveable.h>
    38 
    39 namespace ke {
    40 
    41 template <typename T, typename AllocPolicy = SystemAllocatorPolicy>
    42 class Vector : public AllocPolicy
    43 {
    44  public:
    45   Vector(AllocPolicy = AllocPolicy())
    46   : data_(NULL),
    47     nitems_(0),
    48     maxsize_(0)
    49   {
    50   }
    51 
    52   ~Vector() {
    53     zap();
    54   }
    55 
    56   void steal(Vector &other) {
    57     zap();
    58     data_ = other.data_;
    59     nitems_ = other.nitems_;
    60     maxsize_ = other.maxsize_;
    61     other.reset();
    62   }
    63 
    64   bool append(const T &item) {
    65     if (!growIfNeeded(1))
    66       return false;
    67     new (&data_[nitems_]) T(item);
    68     nitems_++;
    69     return true;
    70   }
    71   void infallibleAppend(const T &item) {
    72     assert(growIfNeeded(1));
    73     new (&data_[nitems_]) T(item);
    74     nitems_++;
    75   }
    76   T popCopy() {
    77     T t = at(length() - 1);
    78     pop();
    79     return t;
    80   }
    81   void pop() {
    82     assert(nitems_);
    83     data_[nitems_ - 1].~T();
    84     nitems_--;
    85   }
    86   bool empty() const {
    87     return length() == 0;
    88   }
    89   size_t length() const {
    90     return nitems_;
    91   }
    92   T& at(size_t i) {
    93     assert(i < length());
    94     return data_[i];
    95   }
    96   const T& at(size_t i) const {
    97     assert(i < length());
    98     return data_[i];
    99   }
   100   T& operator [](size_t i) {
   101     return at(i);
   102   }
   103   const T& operator [](size_t i) const {
   104     return at(i);
   105   }
   106   void clear() {
   107     nitems_ = 0;
   108   }
   109   const T &back() const {
   110     return at(length() - 1);
   111   }
   112   T &back() {
   113     return at(length() - 1);
   114   }
   115 
   116   T *buffer() const {
   117     return data_;
   118   }
   119 
   120   bool ensure(size_t desired) {
   121     if (desired <= length())
   122       return true;
   123 
   124     return growIfNeeded(desired - length());
   125   }
   126 
   127  private:
   128   // These are disallowed because they basically violate the failure handling
   129   // model for AllocPolicies and are also likely to have abysmal performance.
   130   Vector(const Vector<T> &other) KE_DELETE;
   131   Vector &operator =(const Vector<T> &other) KE_DELETE;
   132 
   133  private:
   134   void zap() {
   135     for (size_t i = 0; i < nitems_; i++)
   136       data_[i].~T();
   137     this->free(data_);
   138   }
   139   void reset() {
   140     data_ = NULL;
   141     nitems_ = 0;
   142     maxsize_ = 0;
   143   }
   144 
   145   bool growIfNeeded(size_t needed)
   146   {
   147     if (!IsUintPtrAddSafe(nitems_, needed)) {
   148       this->reportAllocationOverflow();
   149       return false;
   150     }
   151     if (nitems_ + needed < maxsize_)
   152       return true;
   153 
   154     size_t new_maxsize = maxsize_ ? maxsize_ : 8;
   155     while (nitems_ + needed > new_maxsize) {
   156       if (!IsUintPtrMultiplySafe(new_maxsize, 2)) {
   157         this->reportAllocationOverflow();
   158         return false;
   159       }
   160       new_maxsize *= 2;
   161     }
   162 
   163     T* newdata = (T*)this->malloc(sizeof(T) * new_maxsize);
   164     if (newdata == NULL)
   165       return false;
   166     for (size_t i = 0; i < nitems_; i++) {
   167       new (&newdata[i]) T(Moveable<T>(data_[i]));
   168       data_[i].~T();
   169     }
   170     this->free(data_);
   171 
   172     data_ = newdata;
   173     maxsize_ = new_maxsize;
   174     return true;
   175   }
   176 
   177  private:
   178   T* data_;
   179   size_t nitems_;
   180   size_t maxsize_;
   181 };
   182 
   183 }
   184 
   185 #endif /* _INCLUDE_KEIMA_TPL_CPP_VECTOR_H_ */
   186