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