src/dasynq/dasynq-svec.h

   1 #ifndef DASYNQ_SVEC_H_INCLUDED
   2 #define DASYNQ_SVEC_H_INCLUDED
   3
   4 #include <limits>
   5 #include <utility>
   6 #include <new>
   7
   8 // Vector with possibility to shrink capacity arbitrarily.
   9 //
  10 // The standard vector (std::vector) only allows shrinking a vector's capacity to its current size. In cases
  11 // where we need to keep some reserved capacity beyond the current size, we need an alternative solution: hence,
  12 // this class, svector.
  13
  14 namespace dasynq {
  15
  16 template <typename T>
  17 class svector
  18 {
  19     private:
  20     union vec_node {
  21         T elem;
  22
  23         vec_node() { }
  24         ~vec_node() { }
  25     };
  26
  27     vec_node * array;
  28     size_t size_v;
  29     size_t capacity_v;
  30
  31     void check_capacity()
  32     {
  33         if (size_v == capacity_v) {
  34             // double capacity now:
  35             if (capacity_v == 0) capacity_v = 1;
  36             vec_node * new_array = new vec_node[capacity_v * 2];
  37             for (size_t i = 0; i < size_v; i++) {
  38                 new (&new_array[i].elem) T(std::move(array[i].elem));
  39                 array[i].elem.T::~T();
  40             }
  41             delete[] array;
  42             array = new_array;
  43             capacity_v *= 2;
  44         }
  45     }
  46
  47     public:
  48     using size_type = size_t;
  49
  50     svector() : array(nullptr), size_v(0), capacity_v(0)
  51     {
  52
  53     }
  54
  55     svector(const svector<T> &other)
  56     {
  57         capacity_v = other.size_v;
  58         size_v = other.size_v;
  59         array = new T[capacity_v];
  60         for (size_t i = 0; i < size_v; i++) {
  61             new (&array[i].elem) T(other[i].elem);
  62         }
  63     }
  64
  65     ~svector()
  66     {
  67         for (size_t i = 0; i < size_v; i++) {
  68             array[i].elem.T::~T();
  69         }
  70         delete[] array;
  71     }
  72
  73     void push_back(const T &t)
  74     {
  75         check_capacity();
  76         new (&array[size_v].elem) T(t);
  77         size_v++;
  78     }
  79
  80     void push_back(T &&t)
  81     {
  82         check_capacity();
  83         new (&array[size_v].elem) T(t);
  84         size_v++;
  85     }
  86
  87     template <typename ...U>
  88     void emplace_back(U... args)
  89     {
  90         check_capacity();
  91         new (&array[size_v].elem) T(args...);
  92         size_v++;
  93     }
  94
  95     void pop_back()
  96     {
  97         size_v--;
  98     }
  99
 100     T &operator[](size_t index)
 101     {
 102         return array[index].elem;
 103     }
 104
 105     const T &operator[](size_t index) const
 106     {
 107         return array[index].elem;
 108     }
 109
 110     size_t size() const
 111     {
 112         return size_v;
 113     }
 114
 115     size_t capacity() const
 116     {
 117         return capacity_v;
 118     }
 119
 120     bool empty() const
 121     {
 122         return size_v == 0;
 123     }
 124
 125     static size_t max_size() noexcept
 126     {
 127         return std::numeric_limits<size_type>::max() / sizeof(T);
 128
 129         // if we were to support allocators:
 130         //size_t max = std::allocator_traits<std::allocator<char>>::max_size(std::allocator<T>());
 131         //return max / sizeof(T);
 132         //  (but not / sizeof(T) for C++17 apparently)
 133     }
 134
 135     void reserve(size_t amount)
 136     {
 137         if (capacity_v < amount) {
 138             vec_node * new_array = new vec_node[amount];
 139             for (size_t i = 0; i < size_v; i++) {
 140                 new (&new_array[i].elem) T(std::move(array[i].elem));
 141                 array[i].elem.T::~T();
 142             }
 143             delete[] array;
 144             array = new_array;
 145             capacity_v = amount;
 146         }
 147     }
 148
 149     void shrink_to(size_t amount)
 150     {
 151         if (capacity_v > amount) {
 152             vec_node * new_array = new(std::nothrow) vec_node[amount];
 153             if (new_array == nullptr) {
 154                 return;
 155             }
 156             for (size_t i = 0; i < size_v; i++) {
 157                 new (&new_array[i].elem) T(std::move(array[i].elem));
 158                 array[i].elem.T::~T();
 159             }
 160             delete[] array;
 161             array = new_array;
 162             capacity_v = amount;
 163         }
 164     }
 165
 166     T &back()
 167     {
 168         return array[size_v - 1].elem;
 169     }
 170
 171     T* begin()
 172     {
 173         return reinterpret_cast<T *>(array);
 174     }
 175
 176     const T *begin() const
 177     {
 178         return reinterpret_cast<const T *>(array);
 179     }
 180
 181     T* end()
 182     {
 183         return reinterpret_cast<T *>(array + size_v);
 184     }
 185
 186     const T *end() const
 187     {
 188         return reinterpret_cast<const T *>(array + size_v);
 189     }
 190 };
 191
 192
 193 } // namespace
 194
 195 #endif