スタック領域にメモリーを解放する場合は、ポインターが内部バッファーにあるかのチェックが必要な場合があります。
例えば以下のようなケースですかね。
前の項目の例では、力技で乗り切った部分がありましたが、実際
この基準にあうのであれば、アドレス領域がスタック領域内で定義した内部バッファーにアドレスがあるかチェックするようにしたほうが良いです。
さらにフォールバックを行うには 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