include/am-vector.h
author David Anderson <danderson@mozilla.com>
Mon Aug 26 23:18:03 2013 -0700 (2013-08-26)
changeset 11 cfe800908837
parent 10 0ac292cc1467
child 17 563aea5eba06
permissions -rw-r--r--
Add tests.
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
danderson@0
    88
  T popCopy() {
danderson@0
    89
    T t = at(length() - 1);
danderson@0
    90
    pop();
danderson@0
    91
    return t;
danderson@0
    92
  }
danderson@0
    93
  void pop() {
danderson@0
    94
    assert(nitems_);
danderson@0
    95
    data_[nitems_ - 1].~T();
danderson@0
    96
    nitems_--;
danderson@0
    97
  }
danderson@0
    98
  bool empty() const {
danderson@0
    99
    return length() == 0;
danderson@0
   100
  }
danderson@0
   101
  size_t length() const {
danderson@0
   102
    return nitems_;
danderson@0
   103
  }
danderson@0
   104
  T& at(size_t i) {
danderson@0
   105
    assert(i < length());
danderson@0
   106
    return data_[i];
danderson@0
   107
  }
danderson@0
   108
  const T& at(size_t i) const {
danderson@0
   109
    assert(i < length());
danderson@0
   110
    return data_[i];
danderson@0
   111
  }
danderson@0
   112
  T& operator [](size_t i) {
danderson@0
   113
    return at(i);
danderson@0
   114
  }
danderson@0
   115
  const T& operator [](size_t i) const {
danderson@0
   116
    return at(i);
danderson@0
   117
  }
danderson@0
   118
  void clear() {
danderson@0
   119
    nitems_ = 0;
danderson@0
   120
  }
danderson@0
   121
  const T &back() const {
danderson@0
   122
    return at(length() - 1);
danderson@0
   123
  }
danderson@0
   124
  T &back() {
danderson@0
   125
    return at(length() - 1);
danderson@0
   126
  }
danderson@0
   127
danderson@0
   128
  T *buffer() const {
danderson@0
   129
    return data_;
danderson@0
   130
  }
danderson@0
   131
danderson@0
   132
  bool ensure(size_t desired) {
danderson@0
   133
    if (desired <= length())
danderson@0
   134
      return true;
danderson@0
   135
danderson@0
   136
    return growIfNeeded(desired - length());
danderson@0
   137
  }
danderson@0
   138
danderson@0
   139
 private:
danderson@0
   140
  // These are disallowed because they basically violate the failure handling
danderson@0
   141
  // model for AllocPolicies and are also likely to have abysmal performance.
danderson@0
   142
  Vector(const Vector<T> &other) KE_DELETE;
danderson@0
   143
  Vector &operator =(const Vector<T> &other) KE_DELETE;
danderson@0
   144
danderson@0
   145
 private:
danderson@0
   146
  void zap() {
danderson@0
   147
    for (size_t i = 0; i < nitems_; i++)
danderson@0
   148
      data_[i].~T();
danderson@0
   149
    this->free(data_);
danderson@0
   150
  }
danderson@0
   151
  void reset() {
danderson@0
   152
    data_ = NULL;
danderson@0
   153
    nitems_ = 0;
danderson@0
   154
    maxsize_ = 0;
danderson@0
   155
  }
danderson@0
   156
danderson@0
   157
  bool growIfNeeded(size_t needed)
danderson@0
   158
  {
danderson@0
   159
    if (!IsUintPtrAddSafe(nitems_, needed)) {
danderson@0
   160
      this->reportAllocationOverflow();
danderson@0
   161
      return false;
danderson@0
   162
    }
danderson@0
   163
    if (nitems_ + needed < maxsize_)
danderson@0
   164
      return true;
danderson@0
   165
danderson@0
   166
    size_t new_maxsize = maxsize_ ? maxsize_ : 8;
danderson@0
   167
    while (nitems_ + needed > new_maxsize) {
danderson@0
   168
      if (!IsUintPtrMultiplySafe(new_maxsize, 2)) {
danderson@0
   169
        this->reportAllocationOverflow();
danderson@0
   170
        return false;
danderson@0
   171
      }
danderson@0
   172
      new_maxsize *= 2;
danderson@0
   173
    }
danderson@0
   174
danderson@0
   175
    T* newdata = (T*)this->malloc(sizeof(T) * new_maxsize);
danderson@0
   176
    if (newdata == NULL)
danderson@0
   177
      return false;
danderson@0
   178
    for (size_t i = 0; i < nitems_; i++) {
dvander@10
   179
      new (&newdata[i]) T(Moveable<T>(data_[i]));
danderson@0
   180
      data_[i].~T();
danderson@0
   181
    }
danderson@0
   182
    this->free(data_);
danderson@0
   183
danderson@0
   184
    data_ = newdata;
danderson@0
   185
    maxsize_ = new_maxsize;
danderson@0
   186
    return true;
danderson@0
   187
  }
danderson@0
   188
danderson@0
   189
 private:
danderson@0
   190
  T* data_;
danderson@0
   191
  size_t nitems_;
danderson@0
   192
  size_t maxsize_;
danderson@0
   193
};
danderson@0
   194
danderson@0
   195
}
danderson@0
   196
danderson@0
   197
#endif /* _INCLUDE_KEIMA_TPL_CPP_VECTOR_H_ */
danderson@0
   198