スタック領域にメモリーを解放する場合は、ポインターが内部バッファーにあるかのチェックが必要な場合があります。
例えば以下のようなケースですかね。
前の項目の例では、力技で乗り切った部分がありましたが、実際
この基準にあうのであれば、アドレス領域がスタック領域内で定義した内部バッファーにアドレスがあるかチェックするようにしたほうが良いです。
さらにフォールバックを行うには std::allocator<T> を使えるようにしたいです。
内部バッファーのアドレスかのチェックは、かなり定型化しているのですが、以下のようになるかと思います。
147 bool internal_buffer(const_pointer p) const
148 {
149 return ((const_pointer)M_begin_ <= p && p <= (const_pointer)M_end_);
150 }この internal_buffer() 関数がやってるのはポインター p が M_begin_ と M_end_ の範囲内にあるかというチェックです。
そして、もしこの internal_buffer() の返す値が偽ならば、 std::allocator<T> へフォールバックするというのが一般的な実装方法かと思いまする。
ではサンプルコードを見てみましょう。
main.cpp.
1 #include <memory>
2 #include <vector>
3 #include <iostream>
4 #include <cassert>
5 #include <cstddef>
6 #include <map>
7
8 template<typename T, std::size_t N, typename Allocator = std::allocator<T>>
9 class stack_allocator
10 {
11 public:
12 typedef typename std::allocator_traits<Allocator>::value_type value_type;
13 typedef typename std::allocator_traits<Allocator>::pointer pointer;
14 typedef typename std::allocator_traits<Allocator>::const_pointer const_pointer;
15 typedef typename std::allocator_traits<Allocator>::size_type size_type;
16 typedef typename std::allocator_traits<Allocator>::difference_type difference_type;
17 typedef typename std::allocator_traits<Allocator>::void_pointer void_pointer;
18 typedef typename std::allocator_traits<Allocator>::const_void_pointer const_void_pointer;
19 typedef typename Allocator::reference reference;
20 typedef typename Allocator::const_reference const_reference;
21
22 typedef std::map<void*,size_t> size_map_t;
23 typedef std::map<size_t,std::vector<void*>> free_list_t;
24 typedef std::byte byte;
25
26 typedef Allocator allocator_type;
27
28 explicit stack_allocator(const allocator_type& alloc = allocator_type())
29 : M_allocator_(alloc),
30 M_block_size_(sizeof(T) < 8 ? sizeof(long long) : sizeof(T)),
31 M_max_objects_(N),
32 M_begin_(M_buffer_),
33 M_end_(M_buffer_+M_block_size_*M_max_objects_),
34 M_stack_pointer_(M_buffer_)
35 {}
36
37 template<typename U>
38 stack_allocator(const stack_allocator<U,N,Allocator>& other)
39 : M_allocator_(other.M_allocator_),
40 M_block_size_(sizeof(T) < 8 ? sizeof(long long) : sizeof(T)),
41 M_max_objects_(N),
42 M_begin_(other.M_begin_),
43 M_end_(other.M_end_),
44 M_stack_pointer_(other.M_stack_pointer_)
45 {}
46
47 template<typename U>
48 struct rebind
49 {
50 typedef stack_allocator<U,N,allocator_type> other;
51 };
52
53 pointer allocate(size_type n, const_void_pointer hint = const_void_pointer())
54 {
55 auto& free_chunks = M_free_list_[n * M_block_size_];
56 if(!free_chunks.empty()){
57 std::cout << "reuse pointer" << '\n';
58 auto old_block = static_cast<T*>(free_chunks.back());
59 free_chunks.pop_back();
60 return old_block;
61 } else if(M_end_ - M_stack_pointer_ >= n * M_block_size_) {
62 std::cout << "allocate on the stack" << '\n';
63 pointer new_block = reinterpret_cast<pointer>(M_stack_pointer_);
64 M_stack_pointer_ += n * M_block_size_;
65 M_size_map_[new_block] = n * M_block_size_;
66 return new_block;
67 } else {
68 std::cout << "allocate on the heap" << '\n';
69 return M_allocator_.allocate(n,hint);
70 }
71 }
72
73 void deallocate(pointer p, size_type n)
74 {
75 auto chunk_size = M_size_map_[(void*)p];
76 if(internal_buffer(p) || chunk_size != 0)
77 {
78 M_free_list_[chunk_size].push_back((void*)p);
79 std::cout << "deallocate on the stack" << '\n';
80 } else {
81 M_allocator_.deallocate(p,n);
82 std::cout << "deallocate on the heap" << '\n';
83 }
84 }
85
86 size_type max_size() const noexcept
87 {
88 return (size_type)(~0) / sizeof(T);
89 }
90
91 template<typename U, typename... Args>
92 void construct(U* p, Args&&... args)
93 {
94 if(internal_buffer(p)) {
95 std::cout << "internal buffer construct" << '\n';
96 ::new ((void*)p) T(args...);
97 } else {
98 std::cout << "construct on the heap" << '\n';
99 M_allocator_.construct(p,std::forward<Args>(args)...);
100 }
101 }
102
103 template<typename U>
104 void destroy(U* p)
105 {
106 if(internal_buffer(p)) {
107 std::cout << "internal buffer destroy" << '\n';
108 p->~T();
109 } else {
110 std::cout << "destroy the heap object" << '\n';
111 M_allocator_.destroy(p);
112 }
113 }
114
115 pointer address(reference x) const noexcept
116 {
117 if(internal_buffer(std::addressof(x)))
118 {
119 return std::addressof(x);
120 }
121
122 return M_allocator_.address(x);
123 }
124
125 const_pointer address(const_reference x) const noexcept
126 {
127 if(internal_buffer(std::addressof(x)))
128 {
129 return addressof(x);
130 }
131
132 return M_allocator_.address(x);
133 }
134
135 pointer buffer() const noexcept
136 {
137 return M_begin_;
138 }
139
140 constexpr static size_type capacity()
141 {
142 return N;
143 }
144
145 private:
146
147 bool internal_buffer(const_pointer p) const
148 {
149 return ((const_pointer)M_begin_ <= p && p <= (const_pointer)M_end_);
150 }
151
152 allocator_type M_allocator_;
153 size_map_t M_size_map_;
154 free_list_t M_free_list_;
155 byte M_buffer_[N*(sizeof(T) < 8 ? sizeof(long long) : sizeof(T))];
156 size_type M_block_size_;
157 size_type M_max_objects_;
158
159 byte* M_begin_;
160 byte* M_end_;
161 byte* M_stack_pointer_;
162 };
163
164 template<typename T1, std::size_t N, typename Allocator, typename T2>
165 bool operator==(const stack_allocator<T1,N,Allocator>& lhs, const stack_allocator<T2,N,Allocator>& rhs) noexcept
166 {
167 return lhs.buffer() == rhs.buffer();
168 }
169
170 template<typename T1, std::size_t N, typename Allocator, typename T2>
171 bool operator!=(const stack_allocator<T1,N,Allocator>& lhs, const stack_allocator<T2,N,Allocator>& rhs) noexcept
172 {
173 return !(lhs == rhs);
174 }
175
176 const std::size_t stack_size = 8;
177
178 int main()
179 {
180 typedef stack_allocator<int,stack_size> allocator_type;
181 allocator_type alloc;
182 int* t = alloc.allocate(1);
183 alloc.construct(t,100);
184 std::cout << *t << '\n';
185 alloc.destroy(t);
186 alloc.deallocate(t,1);
187
188 int* data[15];
189
190 for(int i = 0; i < 5; ++i){
191 data[i] = alloc.allocate(1);
192 }
193 for(int i = 1; i < 5; ++i){
194 alloc.deallocate(data[i],1);
195 }
196
197 for(int i = 5; i < 15; ++i){
198 data[i] = alloc.allocate(1);
199 }
200
201 for(int i = 5; i < 15; ++i){
202 alloc.deallocate(data[i],1);
203 }
204
205 alloc.deallocate(data[0],1);
206
207 return 0;
208 }
ビルドと実行結果.
$ g++ main.cpp -std=c++17 $ ./a.out allocate on the stack internal buffer construct 100 internal buffer destroy deallocate on the stack reuse pointer allocate on the stack allocate on the stack allocate on the stack allocate on the stack deallocate on the stack deallocate on the stack deallocate on the stack deallocate on the stack reuse pointer reuse pointer reuse pointer reuse pointer allocate on the stack allocate on the stack allocate on the stack allocate on the heap allocate on the heap allocate on the heap deallocate on the stack deallocate on the stack deallocate on the stack deallocate on the stack deallocate on the stack deallocate on the stack deallocate on the stack deallocate on the heap deallocate on the heap deallocate on the heap deallocate on the stack
まずはクラス内のメンバー型とメンバーオブジェクト・変数から見ていきましょう。
8 template<typename T, std::size_t N, typename Allocator = std::allocator<T>>
9 class stack_allocator
10 {
11 public:
12 typedef typename std::allocator_traits<Allocator>::value_type value_type;
13 typedef typename std::allocator_traits<Allocator>::pointer pointer;
14 typedef typename std::allocator_traits<Allocator>::const_pointer const_pointer;
15 typedef typename std::allocator_traits<Allocator>::size_type size_type;
16 typedef typename std::allocator_traits<Allocator>::difference_type difference_type;
17 typedef typename std::allocator_traits<Allocator>::void_pointer void_pointer;
18 typedef typename std::allocator_traits<Allocator>::const_void_pointer const_void_pointer;
19 typedef typename Allocator::reference reference;
20 typedef typename Allocator::const_reference const_reference;
21
22 typedef std::map<void*,size_t> size_map_t;
23 typedef std::map<size_t,std::vector<void*>> free_list_t;
24 typedef std::byte byte;
25
26 typedef Allocator allocator_type;
// 中略
152 allocator_type M_allocator_;
153 size_map_t M_size_map_;
154 free_list_t M_free_list_;
155 byte M_buffer_[N*(sizeof(T) < 8 ? sizeof(long long) : sizeof(T))];
156 size_type M_block_size_;
157 size_type M_max_objects_;
158
159 byte* M_begin_;
160 byte* M_end_;
161 byte* M_stack_pointer_;
162 };この中で内部バッファーの範囲を定義するのは M_begin_ と M_end_ です。
後は M_buffer_ がベースとなるデータを保管してくれるスタック領域のバッファーです。
28 explicit stack_allocator(const allocator_type& alloc = allocator_type())
29 : M_allocator_(alloc),
30 M_block_size_(sizeof(T) < 8 ? sizeof(long long) : sizeof(T)),
31 M_max_objects_(N),
32 M_begin_(M_buffer_),
33 M_end_(M_buffer_+M_block_size_*M_max_objects_),
34 M_stack_pointer_(M_buffer_)
35 {}コンストラクターでは M_begin_ を M_buffer_ に設定しています。
まあ M_buffer_ はスタックバッファーの開始アドレスを指すポインターなので、これが開始点となるのはご依存ないですよね？
次に M_end_ には 「 M_buffer_+M_block_size_*M_max_objects_ 」が代入されます。
まあこれも M_buffer_ に M_buffer_ のバイトサイズを加算しているので、終端を指すポインターになるだけです。
この内部バッファーチェックを使っている箇所が以下の deallocate() 関数です。
73 void deallocate(pointer p, size_type n)
74 {
75 auto chunk_size = M_size_map_[(void*)p];
76 if(internal_buffer(p) || chunk_size != 0)
77 {
78 M_free_list_[chunk_size].push_back((void*)p);
79 std::cout << "deallocate on the stack" << '\n';
80 } else {
81 M_allocator_.deallocate(p,n);
82 std::cout << "deallocate on the heap" << '\n';
83 }
84 }p が内部バッファーにないか、フリーチャンクが存在しない場合は標準アロケーターにフォールバックしていますね。
まあ、こんな感じで内部バッファーのチェックを行うと良いかと思います。
筆者は時間が無かったのと、説明するときのコードはキレイよりベタな方が良さそうという、その場のノリで、あまりチェックはしていないです。
まあそれと、書くのも時間かかりますんでご理解賜りたいものです… (´・ω・｀)
Copyright 2018-2019, by Masaki Komatsu