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