1 /*
2 * Copyright (c) 2020 Samsung Electronics Co., Ltd. All rights reserved.
3
4 * Permission is hereby granted, free of charge, to any person obtaining a copy
5 * of this software and associated documentation files (the "Software"), to deal
6 * in the Software without restriction, including without limitation the rights
7 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
8 * copies of the Software, and to permit persons to whom the Software is
9 * furnished to do so, subject to the following conditions:
10
11 * The above copyright notice and this permission notice shall be included in all
12 * copies or substantial portions of the Software.
13
14 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
19 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
20 * SOFTWARE.
21 */
22
23 #ifndef VSTACK_ALLOCATOR_H
24 #define VSTACK_ALLOCATOR_H
25
26 #include <cstddef>
27 #include <cassert>
28
29 template <std::size_t N, std::size_t alignment = alignof(std::max_align_t)>
30 class arena
31 {
32 alignas(alignment) char buf_[N];
33 char* ptr_;
34
35 public:
~arena()36 ~arena() {ptr_ = nullptr;}
arena()37 arena() noexcept : ptr_(buf_) {}
38 arena(const arena&) = delete;
39 arena& operator=(const arena&) = delete;
40
41 template <std::size_t ReqAlign> char* allocate(std::size_t n);
42 void deallocate(char* p, std::size_t n) noexcept;
43
size()44 static constexpr std::size_t size() noexcept {return N;}
used()45 std::size_t used() const noexcept {return static_cast<std::size_t>(ptr_ - buf_);}
reset()46 void reset() noexcept {ptr_ = buf_;}
47
48 private:
49 static
50 std::size_t
align_up(std::size_t n)51 align_up(std::size_t n) noexcept
52 {return (n + (alignment-1)) & ~(alignment-1);}
53
54 bool
pointer_in_buffer(char * p)55 pointer_in_buffer(char* p) noexcept
56 {return buf_ <= p && p <= buf_ + N;}
57 };
58
59 template <std::size_t N, std::size_t alignment>
60 template <std::size_t ReqAlign>
61 char*
allocate(std::size_t n)62 arena<N, alignment>::allocate(std::size_t n)
63 {
64 static_assert(ReqAlign <= alignment, "alignment is too small for this arena");
65 assert(pointer_in_buffer(ptr_) && "stack_alloc has outlived arena");
66 auto const aligned_n = align_up(n);
67 if (static_cast<decltype(aligned_n)>(buf_ + N - ptr_) >= aligned_n)
68 {
69 char* r = ptr_;
70 ptr_ += aligned_n;
71 return r;
72 }
73
74 static_assert(alignment <= alignof(std::max_align_t), "you've chosen an "
75 "alignment that is larger than alignof(std::max_align_t), and "
76 "cannot be guaranteed by normal operator new");
77 return static_cast<char*>(::operator new(n));
78 }
79
80 template <std::size_t N, std::size_t alignment>
81 void
deallocate(char * p,std::size_t n)82 arena<N, alignment>::deallocate(char* p, std::size_t n) noexcept
83 {
84 assert(pointer_in_buffer(ptr_) && "stack_alloc has outlived arena");
85 if (pointer_in_buffer(p))
86 {
87 n = align_up(n);
88 if (p + n == ptr_)
89 ptr_ = p;
90 }
91 else
92 ::operator delete(p);
93 }
94
95 template <class T, std::size_t N, std::size_t Align = alignof(std::max_align_t)>
96 class stack_alloc
97 {
98 public:
99 using value_type = T;
100 static auto constexpr alignment = Align;
101 static auto constexpr size = N;
102 using arena_type = arena<size, alignment>;
103
104 private:
105 arena_type& a_;
106
107 public:
108 stack_alloc(const stack_alloc&) = default;
109 stack_alloc& operator=(const stack_alloc&) = delete;
110
stack_alloc(arena_type & a)111 stack_alloc(arena_type& a) noexcept : a_(a)
112 {
113 static_assert(size % alignment == 0,
114 "size N needs to be a multiple of alignment Align");
115 }
116 template <class U>
stack_alloc(const stack_alloc<U,N,alignment> & a)117 stack_alloc(const stack_alloc<U, N, alignment>& a) noexcept
118 : a_(a.a_) {}
119
120 template <class _Up> struct rebind {using other = stack_alloc<_Up, N, alignment>;};
121
allocate(std::size_t n)122 T* allocate(std::size_t n)
123 {
124 return reinterpret_cast<T*>(a_.template allocate<alignof(T)>(n*sizeof(T)));
125 }
deallocate(T * p,std::size_t n)126 void deallocate(T* p, std::size_t n) noexcept
127 {
128 a_.deallocate(reinterpret_cast<char*>(p), n*sizeof(T));
129 }
130
131 template <class T1, std::size_t N1, std::size_t A1,
132 class U, std::size_t M, std::size_t A2>
133 friend
134 bool
135 operator==(const stack_alloc<T1, N1, A1>& x, const stack_alloc<U, M, A2>& y) noexcept;
136
137 template <class U, std::size_t M, std::size_t A> friend class stack_alloc;
138 };
139
140 template <class T, std::size_t N, std::size_t A1, class U, std::size_t M, std::size_t A2>
141 inline
142 bool
143 operator==(const stack_alloc<T, N, A1>& x, const stack_alloc<U, M, A2>& y) noexcept
144 {
145 return N == M && A1 == A2 && &x.a_ == &y.a_;
146 }
147
148 template <class T, std::size_t N, std::size_t A1, class U, std::size_t M, std::size_t A2>
149 inline
150 bool
151 operator!=(const stack_alloc<T, N, A1>& x, const stack_alloc<U, M, A2>& y) noexcept
152 {
153 return !(x == y);
154 }
155
156 #endif // VSTACK_ALLOCATOR_H
157