silo/masstree/local_vector.hh

   1 #ifndef GSTORE_LOCAL_VECTOR_HH
   2 #define GSTORE_LOCAL_VECTOR_HH 1
   3 #include "compiler.hh"
   4 #include <memory>
   5 #include <iterator>
   6 #include <assert.h>
   7
   8 template <typename T, int N, typename A = std::allocator<T> >
   9 class local_vector {
  10   public:
  11     typedef bool (local_vector<T, N, A>::*unspecified_bool_type)() const;
  12     typedef T value_type;
  13     typedef value_type* iterator;
  14     typedef const value_type* const_iterator;
  15     typedef std::reverse_iterator<iterator> reverse_iterator;
  16     typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
  17     typedef unsigned size_type;
  18
  19     inline local_vector(const A& allocator = A());
  20     local_vector(const local_vector<T, N, A>& x);
  21     template <int NN, typename AA>
  22     local_vector(const local_vector<T, NN, AA>& x);
  23     inline ~local_vector();
  24
  25     inline size_type size() const;
  26     inline size_type capacity() const;
  27     inline bool empty() const;
  28     inline operator unspecified_bool_type() const;
  29     inline bool operator!() const;
  30
  31     inline iterator begin();
  32     inline iterator end();
  33     inline const_iterator begin() const;
  34     inline const_iterator end() const;
  35     inline const_iterator cbegin() const;
  36     inline const_iterator cend() const;
  37     inline reverse_iterator rbegin();
  38     inline reverse_iterator rend();
  39     inline const_reverse_iterator rbegin() const;
  40     inline const_reverse_iterator rend() const;
  41     inline const_reverse_iterator crbegin() const;
  42     inline const_reverse_iterator crend() const;
  43
  44     inline value_type& operator[](size_type i);
  45     inline const value_type& operator[](size_type i) const;
  46     inline value_type& front();
  47     inline const value_type& front() const;
  48     inline value_type& back();
  49     inline const value_type& back() const;
  50
  51     inline void push_back(const value_type& x);
  52     inline void push_back(value_type&& x);
  53     template <typename... Args> inline void emplace_back(Args&&... args);
  54     inline void pop_back();
  55
  56     inline void clear();
  57     inline void resize(size_type n, value_type x = value_type());
  58     iterator erase(iterator position);
  59     iterator erase(iterator first, iterator last);
  60
  61     inline local_vector<T, N, A>& operator=(const local_vector<T, N, A>& x);
  62     template <int NN, typename AA>
  63     inline local_vector<T, N, A>& operator=(const local_vector<T, NN, AA>& x);
  64
  65   private:
  66     struct rep : public A {
  67         T* first_;
  68         T* last_;
  69         T* capacity_;
  70         char lv_[sizeof(T) * N]; // XXX does not obey alignof(T)
  71
  72         inline rep(const A& a);
  73     };
  74     rep r_;
  75
  76     void grow(size_type n = 0);
  77 };
  78
  79 template <typename T, int N, typename A>
  80 inline local_vector<T, N, A>::rep::rep(const A& a)
  81     : A(a), first_(reinterpret_cast<T*>(lv_)),
  82       last_(first_), capacity_(first_ + N) {
  83 }
  84
  85 template <typename T, int N, typename A>
  86 inline local_vector<T, N, A>::local_vector(const A& allocator)
  87     : r_(allocator) {
  88 }
  89
  90 template <typename T, int N, typename A>
  91 local_vector<T, N, A>::local_vector(const local_vector<T, N, A>& x)
  92     : r_(A()) {
  93     for (const T* it = x.r_.first_; it != x.r_.last_; ++it)
  94         push_back(*it);
  95 }
  96
  97 template <typename T, int N, typename A> template <int NN, typename AA>
  98 local_vector<T, N, A>::local_vector(const local_vector<T, NN, AA>& x)
  99     : r_(A()) {
 100     for (const T* it = x.r_.first_; it != x.r_.last_; ++it)
 101         push_back(*it);
 102 }
 103
 104 template <typename T, int N, typename A>
 105 inline local_vector<T, N, A>::~local_vector() {
 106     for (T* it = r_.first_; it != r_.last_; ++it)
 107         r_.destroy(it);
 108     if (r_.first_ != reinterpret_cast<T*>(r_.lv_))
 109         r_.deallocate(r_.first_, r_.capacity_ - r_.first_);
 110 }
 111
 112 template <typename T, int N, typename A>
 113 inline unsigned local_vector<T, N, A>::size() const {
 114     return r_.last_ - r_.first_;
 115 }
 116
 117 template <typename T, int N, typename A>
 118 inline unsigned local_vector<T, N, A>::capacity() const {
 119     return r_.capacity_ - r_.first_;
 120 }
 121
 122 template <typename T, int N, typename A>
 123 inline bool local_vector<T, N, A>::empty() const {
 124     return r_.first_ == r_.last_;
 125 }
 126
 127 template <typename T, int N, typename A>
 128 inline local_vector<T, N, A>::operator unspecified_bool_type() const {
 129     return empty() ? 0 : &local_vector<T, N, A>::empty;
 130 }
 131
 132 template <typename T, int N, typename A>
 133 inline bool local_vector<T, N, A>::operator!() const {
 134     return empty();
 135 }
 136
 137 template <typename T, int N, typename A>
 138 void local_vector<T, N, A>::grow(size_type n) {
 139     size_t newcap = capacity() * 2;
 140     while (newcap < n)
 141         newcap *= 2;
 142     T* m = r_.allocate(newcap);
 143     for (T* it = r_.first_, *mit = m; it != r_.last_; ++it, ++mit) {
 144         r_.construct(mit, std::move(*it));
 145         r_.destroy(it);
 146     }
 147     if (r_.first_ != reinterpret_cast<T*>(r_.lv_))
 148         r_.deallocate(r_.first_, capacity());
 149     r_.last_ = m + (r_.last_ - r_.first_);
 150     r_.first_ = m;
 151     r_.capacity_ = m + newcap;
 152 }
 153
 154 template <typename T, int N, typename A>
 155 inline auto local_vector<T, N, A>::begin() -> iterator {
 156     return r_.first_;
 157 }
 158
 159 template <typename T, int N, typename A>
 160 inline auto local_vector<T, N, A>::end() -> iterator {
 161     return r_.last_;
 162 }
 163
 164 template <typename T, int N, typename A>
 165 inline auto local_vector<T, N, A>::begin() const -> const_iterator {
 166     return r_.first_;
 167 }
 168
 169 template <typename T, int N, typename A>
 170 inline auto local_vector<T, N, A>::end() const -> const_iterator {
 171     return r_.last_;
 172 }
 173
 174 template <typename T, int N, typename A>
 175 inline auto local_vector<T, N, A>::cbegin() const -> const_iterator {
 176     return r_.first_;
 177 }
 178
 179 template <typename T, int N, typename A>
 180 inline auto local_vector<T, N, A>::cend() const -> const_iterator {
 181     return r_.last_;
 182 }
 183
 184 template <typename T, int N, typename A>
 185 inline auto local_vector<T, N, A>::rbegin() -> reverse_iterator {
 186     return reverse_iterator(end());
 187 }
 188
 189 template <typename T, int N, typename A>
 190 inline auto local_vector<T, N, A>::rend() -> reverse_iterator {
 191     return reverse_iterator(begin());
 192 }
 193
 194 template <typename T, int N, typename A>
 195 inline auto local_vector<T, N, A>::rbegin() const -> const_reverse_iterator {
 196     return const_reverse_iterator(end());
 197 }
 198
 199 template <typename T, int N, typename A>
 200 inline auto local_vector<T, N, A>::rend() const -> const_reverse_iterator {
 201     return const_reverse_iterator(begin());
 202 }
 203
 204 template <typename T, int N, typename A>
 205 inline auto local_vector<T, N, A>::crbegin() const -> const_reverse_iterator {
 206     return const_reverse_iterator(end());
 207 }
 208
 209 template <typename T, int N, typename A>
 210 inline auto local_vector<T, N, A>::crend() const -> const_reverse_iterator {
 211     return const_reverse_iterator(begin());
 212 }
 213
 214 template <typename T, int N, typename A>
 215 inline T& local_vector<T, N, A>::operator[](size_type i) {
 216     return r_.first_[i];
 217 }
 218
 219 template <typename T, int N, typename A>
 220 inline const T& local_vector<T, N, A>::operator[](size_type i) const {
 221     return r_.first_[i];
 222 }
 223
 224 template <typename T, int N, typename A>
 225 inline T& local_vector<T, N, A>::front() {
 226     return r_.first_[0];
 227 }
 228
 229 template <typename T, int N, typename A>
 230 inline const T& local_vector<T, N, A>::front() const {
 231     return r_.first_[0];
 232 }
 233
 234 template <typename T, int N, typename A>
 235 inline T& local_vector<T, N, A>::back() {
 236     return r_.last_[-1];
 237 }
 238
 239 template <typename T, int N, typename A>
 240 inline const T& local_vector<T, N, A>::back() const {
 241     return r_.last_[-1];
 242 }
 243
 244 template <typename T, int N, typename A>
 245 inline void local_vector<T, N, A>::push_back(const T& x) {
 246     if (r_.last_ == r_.capacity_)
 247         grow();
 248     r_.construct(r_.last_, x);
 249     ++r_.last_;
 250 }
 251
 252 template <typename T, int N, typename A>
 253 inline void local_vector<T, N, A>::push_back(T&& x) {
 254     if (r_.last_ == r_.capacity_)
 255         grow();
 256     r_.construct(r_.last_, std::move(x));
 257     ++r_.last_;
 258 }
 259
 260 template <typename T, int N, typename A> template <typename... Args>
 261 inline void local_vector<T, N, A>::emplace_back(Args&&... args) {
 262     if (r_.last_ == r_.capacity_)
 263         grow();
 264     r_.construct(r_.last_, std::forward<Args>(args)...);
 265     ++r_.last_;
 266 }
 267
 268 template <typename T, int N, typename A>
 269 inline void local_vector<T, N, A>::pop_back() {
 270     assert(r_.first_ != r_.last_);
 271     --r_.last_;
 272     r_.destroy(r_.last_);
 273 }
 274
 275 template <typename T, int N, typename A>
 276 inline void local_vector<T, N, A>::clear() {
 277     for (auto it = r_.first_; it != r_.last_; ++it)
 278         r_.destroy(it);
 279     r_.last_ = r_.first_;
 280 }
 281
 282 template <typename T, int N, typename A>
 283 inline void local_vector<T, N, A>::resize(size_type n, value_type v) {
 284     if (capacity() < n)
 285         grow(n);
 286     auto it = r_.first_ + n;
 287     auto xt = r_.last_;
 288     r_.last_ = it;
 289     for (; it < xt; ++it)
 290         r_.destroy(it);
 291     for (; xt < it; ++xt)
 292         r_.construct(xt, v);
 293 }
 294
 295 template <typename T, int N, typename A>
 296 local_vector<T, N, A>&
 297 local_vector<T, N, A>::operator=(const local_vector<T, N, A>& x) {
 298     if (&x != this) {
 299         clear();
 300         if (capacity() < x.capacity())
 301             grow(x.capacity());
 302         for (auto xit = x.r_.first_; xit != x.r_.last_; ++xit, ++r_.last_)
 303             r_.construct(r_.last_, *xit);
 304     }
 305     return *this;
 306 }
 307
 308 template <typename T, int N, typename A> template <int NN, typename AA>
 309 local_vector<T, N, A>&
 310 local_vector<T, N, A>::operator=(const local_vector<T, NN, AA>& x) {
 311     clear();
 312     if (capacity() < x.capacity())
 313         grow(x.capacity());
 314     for (auto xit = x.r_.first_; xit != x.r_.last_; ++xit, ++r_.last_)
 315         r_.construct(r_.last_, *xit);
 316     return *this;
 317 }
 318
 319 template <typename T, int N, typename A>
 320 inline T* local_vector<T, N, A>::erase(iterator position) {
 321     return erase(position, position + 1);
 322 }
 323
 324 template <typename T, int N, typename A>
 325 T* local_vector<T, N, A>::erase(iterator first, iterator last) {
 326     if (first != last) {
 327         iterator it = first, xend = end();
 328         for (; last != xend; ++it, ++last)
 329             *it = std::move(*last);
 330         r_.last_ = it;
 331         for (; it != xend; ++it)
 332             r_.destroy(it);
 333     }
 334     return first;
 335 }
 336
 337 #endif