src/vector/vstackallocator.h

   1 /*
   2  * Copyright (c) 2018 Samsung Electronics Co., Ltd. All rights reserved.
   3  *
   4  * This library is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU Lesser General Public
   6  * License as published by the Free Software Foundation; either
   7  * version 2.1 of the License, or (at your option) any later version.
   8  *
   9  * This library is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * Lesser General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU Lesser General Public
  15  * License along with this library; if not, write to the Free Software
  16  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
  17  */
  18
  19 #ifndef VSTACK_ALLOCATOR_H
  20 #define VSTACK_ALLOCATOR_H
  21
  22 #include <cstddef>
  23 #include <cassert>
  24
  25 template <std::size_t N, std::size_t alignment = alignof(std::max_align_t)>
  26 class arena
  27 {
  28     alignas(alignment) char buf_[N];
  29     char* ptr_;
  30
  31 public:
  32     ~arena() {ptr_ = nullptr;}
  33     arena() noexcept : ptr_(buf_) {}
  34     arena(const arena&) = delete;
  35     arena& operator=(const arena&) = delete;
  36
  37     template <std::size_t ReqAlign> char* allocate(std::size_t n);
  38     void deallocate(char* p, std::size_t n) noexcept;
  39
  40     static constexpr std::size_t size() noexcept {return N;}
  41     std::size_t used() const noexcept {return static_cast<std::size_t>(ptr_ - buf_);}
  42     void reset() noexcept {ptr_ = buf_;}
  43
  44 private:
  45     static
  46     std::size_t
  47     align_up(std::size_t n) noexcept
  48         {return (n + (alignment-1)) & ~(alignment-1);}
  49
  50     bool
  51     pointer_in_buffer(char* p) noexcept
  52         {return buf_ <= p && p <= buf_ + N;}
  53 };
  54
  55 template <std::size_t N, std::size_t alignment>
  56 template <std::size_t ReqAlign>
  57 char*
  58 arena<N, alignment>::allocate(std::size_t n)
  59 {
  60     static_assert(ReqAlign <= alignment, "alignment is too small for this arena");
  61     assert(pointer_in_buffer(ptr_) && "stack_alloc has outlived arena");
  62     auto const aligned_n = align_up(n);
  63     if (static_cast<decltype(aligned_n)>(buf_ + N - ptr_) >= aligned_n)
  64     {
  65         char* r = ptr_;
  66         ptr_ += aligned_n;
  67         return r;
  68     }
  69
  70     static_assert(alignment <= alignof(std::max_align_t), "you've chosen an "
  71                   "alignment that is larger than alignof(std::max_align_t), and "
  72                   "cannot be guaranteed by normal operator new");
  73     return static_cast<char*>(::operator new(n));
  74 }
  75
  76 template <std::size_t N, std::size_t alignment>
  77 void
  78 arena<N, alignment>::deallocate(char* p, std::size_t n) noexcept
  79 {
  80     assert(pointer_in_buffer(ptr_) && "stack_alloc has outlived arena");
  81     if (pointer_in_buffer(p))
  82     {
  83         n = align_up(n);
  84         if (p + n == ptr_)
  85             ptr_ = p;
  86     }
  87     else
  88         ::operator delete(p);
  89 }
  90
  91 template <class T, std::size_t N, std::size_t Align = alignof(std::max_align_t)>
  92 class stack_alloc
  93 {
  94 public:
  95     using value_type = T;
  96     static auto constexpr alignment = Align;
  97     static auto constexpr size = N;
  98     using arena_type = arena<size, alignment>;
  99
 100 private:
 101     arena_type& a_;
 102
 103 public:
 104     stack_alloc(const stack_alloc&) = default;
 105     stack_alloc& operator=(const stack_alloc&) = delete;
 106
 107     stack_alloc(arena_type& a) noexcept : a_(a)
 108     {
 109         static_assert(size % alignment == 0,
 110                       "size N needs to be a multiple of alignment Align");
 111     }
 112     template <class U>
 113         stack_alloc(const stack_alloc<U, N, alignment>& a) noexcept
 114             : a_(a.a_) {}
 115
 116     template <class _Up> struct rebind {using other = stack_alloc<_Up, N, alignment>;};
 117
 118     T* allocate(std::size_t n)
 119     {
 120         return reinterpret_cast<T*>(a_.template allocate<alignof(T)>(n*sizeof(T)));
 121     }
 122     void deallocate(T* p, std::size_t n) noexcept
 123     {
 124         a_.deallocate(reinterpret_cast<char*>(p), n*sizeof(T));
 125     }
 126
 127     template <class T1, std::size_t N1, std::size_t A1,
 128               class U, std::size_t M, std::size_t A2>
 129     friend
 130     bool
 131     operator==(const stack_alloc<T1, N1, A1>& x, const stack_alloc<U, M, A2>& y) noexcept;
 132
 133     template <class U, std::size_t M, std::size_t A> friend class stack_alloc;
 134 };
 135
 136 template <class T, std::size_t N, std::size_t A1, class U, std::size_t M, std::size_t A2>
 137 inline
 138 bool
 139 operator==(const stack_alloc<T, N, A1>& x, const stack_alloc<U, M, A2>& y) noexcept
 140 {
 141     return N == M && A1 == A2 && &x.a_ == &y.a_;
 142 }
 143
 144 template <class T, std::size_t N, std::size_t A1, class U, std::size_t M, std::size_t A2>
 145 inline
 146 bool
 147 operator!=(const stack_alloc<T, N, A1>& x, const stack_alloc<U, M, A2>& y) noexcept
 148 {
 149     return !(x == y);
 150 }
 151
 152 #endif  // VSTACK_ALLOCATOR_H