include/am-vector.h
author David Anderson <dvander@alliedmods.net>
Sat Aug 31 19:52:41 2013 -0700 (2013-08-31)
changeset 17 563aea5eba06
parent 11 cfe800908837
permissions -rw-r--r--
Sync AMTL.
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@11
    46
   : data_(NULL),
danderson@11
    47
     nitems_(0),
danderson@11
    48
     maxsize_(0)
danderson@0
    49
  {
danderson@0
    50
  }
danderson@0
    51
danderson@11
    52
  Vector(Moveable<Vector<T, AllocPolicy> > other) {
danderson@11
    53
    data_ = other->data_;
danderson@11
    54
    nitems_ = other->nitems_;
danderson@11
    55
    maxsize_ = other->maxsize_;
danderson@11
    56
    other->reset();
danderson@11
    57
  }
danderson@11
    58
danderson@0
    59
  ~Vector() {
danderson@0
    60
    zap();
danderson@0
    61
  }
danderson@0
    62
danderson@11
    63
  bool append(const T &item) {
danderson@11
    64
    if (!growIfNeeded(1))
danderson@11
    65
      return false;
danderson@11
    66
    new (&data_[nitems_]) T(item);
danderson@11
    67
    nitems_++;
danderson@11
    68
    return true;
danderson@0
    69
  }
danderson@11
    70
  bool append(Moveable<T> item) {
danderson@0
    71
    if (!growIfNeeded(1))
danderson@0
    72
      return false;
danderson@0
    73
    new (&data_[nitems_]) T(item);
danderson@0
    74
    nitems_++;
danderson@0
    75
    return true;
danderson@0
    76
  }
danderson@0
    77
  void infallibleAppend(const T &item) {
danderson@0
    78
    assert(growIfNeeded(1));
danderson@0
    79
    new (&data_[nitems_]) T(item);
danderson@0
    80
    nitems_++;
danderson@0
    81
  }
danderson@11
    82
  void infallibleAppend(Moveable<T> item) {
danderson@11
    83
    assert(growIfNeeded(1));
danderson@11
    84
    new (&data_[nitems_]) T(item);
danderson@11
    85
    nitems_++;
danderson@11
    86
  }
danderson@11
    87
dvander@17
    88
  // Shift all elements including |at| up by one, and insert |item| at the
dvander@17
    89
  // given position. This is a linear-time operation.
dvander@17
    90
  bool insert(size_t at, const T &item) {
dvander@17
    91
    if (!moveUp(at))
dvander@17
    92
      return false;
dvander@17
    93
    new (&data_[at]) T(item);
dvander@17
    94
    return true;
dvander@17
    95
  }
dvander@17
    96
  bool insert(size_t at, Moveable<T> item) {
dvander@17
    97
    if (!moveUp(at))
dvander@17
    98
      return false;
dvander@17
    99
    new (&data_[at]) T(item);
dvander@17
   100
    return true;
dvander@17
   101
  }
dvander@17
   102
dvander@17
   103
  // Shift all elements at the given position down, removing the given
dvander@17
   104
  // element. This is a linear-time operation.
dvander@17
   105
  void remove(size_t at) {
dvander@17
   106
    for (size_t i = at; i < length() - 1; i++)
dvander@17
   107
      data_[i] = T(Moveable<T>(data_[i + 1]));
dvander@17
   108
    pop();
dvander@17
   109
  }
dvander@17
   110
danderson@0
   111
  T popCopy() {
danderson@0
   112
    T t = at(length() - 1);
danderson@0
   113
    pop();
danderson@0
   114
    return t;
danderson@0
   115
  }
danderson@0
   116
  void pop() {
danderson@0
   117
    assert(nitems_);
danderson@0
   118
    data_[nitems_ - 1].~T();
danderson@0
   119
    nitems_--;
danderson@0
   120
  }
danderson@0
   121
  bool empty() const {
danderson@0
   122
    return length() == 0;
danderson@0
   123
  }
danderson@0
   124
  size_t length() const {
danderson@0
   125
    return nitems_;
danderson@0
   126
  }
danderson@0
   127
  T& at(size_t i) {
danderson@0
   128
    assert(i < length());
danderson@0
   129
    return data_[i];
danderson@0
   130
  }
danderson@0
   131
  const T& at(size_t i) const {
danderson@0
   132
    assert(i < length());
danderson@0
   133
    return data_[i];
danderson@0
   134
  }
danderson@0
   135
  T& operator [](size_t i) {
danderson@0
   136
    return at(i);
danderson@0
   137
  }
danderson@0
   138
  const T& operator [](size_t i) const {
danderson@0
   139
    return at(i);
danderson@0
   140
  }
danderson@0
   141
  void clear() {
danderson@0
   142
    nitems_ = 0;
danderson@0
   143
  }
danderson@0
   144
  const T &back() const {
danderson@0
   145
    return at(length() - 1);
danderson@0
   146
  }
danderson@0
   147
  T &back() {
danderson@0
   148
    return at(length() - 1);
danderson@0
   149
  }
danderson@0
   150
danderson@0
   151
  T *buffer() const {
danderson@0
   152
    return data_;
danderson@0
   153
  }
danderson@0
   154
danderson@0
   155
  bool ensure(size_t desired) {
danderson@0
   156
    if (desired <= length())
danderson@0
   157
      return true;
danderson@0
   158
danderson@0
   159
    return growIfNeeded(desired - length());
danderson@0
   160
  }
danderson@0
   161
danderson@0
   162
 private:
danderson@0
   163
  // These are disallowed because they basically violate the failure handling
danderson@0
   164
  // model for AllocPolicies and are also likely to have abysmal performance.
danderson@0
   165
  Vector(const Vector<T> &other) KE_DELETE;
danderson@0
   166
  Vector &operator =(const Vector<T> &other) KE_DELETE;
danderson@0
   167
danderson@0
   168
 private:
danderson@0
   169
  void zap() {
danderson@0
   170
    for (size_t i = 0; i < nitems_; i++)
danderson@0
   171
      data_[i].~T();
danderson@0
   172
    this->free(data_);
danderson@0
   173
  }
danderson@0
   174
  void reset() {
danderson@0
   175
    data_ = NULL;
danderson@0
   176
    nitems_ = 0;
danderson@0
   177
    maxsize_ = 0;
danderson@0
   178
  }
danderson@0
   179
dvander@17
   180
  bool moveUp(size_t at) {
dvander@17
   181
    if (!growIfNeeded(1))
dvander@17
   182
      return false;
dvander@17
   183
    nitems_++;
dvander@17
   184
    for (size_t i = nitems_ - 1; i > at; i--)
dvander@17
   185
      data_[i] = T(Moveable<T>(data_[i - 1]));
dvander@17
   186
    return true;
dvander@17
   187
  }
dvander@17
   188
danderson@0
   189
  bool growIfNeeded(size_t needed)
danderson@0
   190
  {
danderson@0
   191
    if (!IsUintPtrAddSafe(nitems_, needed)) {
danderson@0
   192
      this->reportAllocationOverflow();
danderson@0
   193
      return false;
danderson@0
   194
    }
danderson@0
   195
    if (nitems_ + needed < maxsize_)
danderson@0
   196
      return true;
danderson@0
   197
danderson@0
   198
    size_t new_maxsize = maxsize_ ? maxsize_ : 8;
danderson@0
   199
    while (nitems_ + needed > new_maxsize) {
danderson@0
   200
      if (!IsUintPtrMultiplySafe(new_maxsize, 2)) {
danderson@0
   201
        this->reportAllocationOverflow();
danderson@0
   202
        return false;
danderson@0
   203
      }
danderson@0
   204
      new_maxsize *= 2;
danderson@0
   205
    }
danderson@0
   206
danderson@0
   207
    T* newdata = (T*)this->malloc(sizeof(T) * new_maxsize);
danderson@0
   208
    if (newdata == NULL)
danderson@0
   209
      return false;
danderson@0
   210
    for (size_t i = 0; i < nitems_; i++) {
dvander@10
   211
      new (&newdata[i]) T(Moveable<T>(data_[i]));
danderson@0
   212
      data_[i].~T();
danderson@0
   213
    }
danderson@0
   214
    this->free(data_);
danderson@0
   215
danderson@0
   216
    data_ = newdata;
danderson@0
   217
    maxsize_ = new_maxsize;
danderson@0
   218
    return true;
danderson@0
   219
  }
danderson@0
   220
danderson@0
   221
 private:
danderson@0
   222
  T* data_;
danderson@0
   223
  size_t nitems_;
danderson@0
   224
  size_t maxsize_;
danderson@0
   225
};
danderson@0
   226
danderson@0
   227
}
danderson@0
   228
danderson@0
   229
#endif /* _INCLUDE_KEIMA_TPL_CPP_VECTOR_H_ */
danderson@0
   230