tlx
Loading...
Searching...
No Matches
stack_allocator.hpp
Go to the documentation of this file.
1/*******************************************************************************
2 * tlx/stack_allocator.hpp
3 *
4 * An allocator derived from short_alloc by Howard Hinnant, which first takes
5 * memory from a stack allocated reserved area and then from malloc().
6 *
7 * from http://howardhinnant.github.io/stack_alloc.html by Howard Hinnant and
8 * http://codereview.stackexchange.com/questions/31528/a-working-stack-allocator
9 *
10 * Part of tlx - http://panthema.net/tlx
11 *
12 * Copyright (C) 2015-2017 Timo Bingmann <tb@panthema.net>
13 *
14 * All rights reserved. Published under the Boost Software License, Version 1.0
15 ******************************************************************************/
16
17#ifndef TLX_STACK_ALLOCATOR_HEADER
18#define TLX_STACK_ALLOCATOR_HEADER
19
20#include <cassert>
21#include <cstddef>
22#include <cstdlib>
23
25
26namespace tlx {
27
28/*!
29 * Storage area allocated on the stack and usable by a StackAllocator.
30 */
31template <size_t Size>
33{
34 static constexpr size_t alignment = 16;
35
36 //! union to enforce alignment of buffer area
38 int i;
39 long l;
40 long long ll;
41 long double ld;
42 double d;
43 void* p;
44 void (* pf)();
46 };
47
48 union {
49 //! stack memory area used for allocations.
50 char buf_[Size];
51 //! enforce alignment
53 };
54
55 //! pointer into free bytes in buf_
56 char* ptr_;
57
58 //! debug method to check whether ptr_ is still in buf_.
59 bool pointer_in_buffer(char* p) noexcept
60 { return buf_ <= p && p <= buf_ + Size; }
61
62public:
63 //! default constructor: free pointer at the beginning.
64 StackArena() noexcept : ptr_(buf_) { }
65
66 //! destructor clears ptr_ for debugging.
67 ~StackArena() { ptr_ = nullptr; }
68
69 StackArena(const StackArena&) = delete;
71
72 char * allocate(size_t n) {
73 assert(pointer_in_buffer(ptr_) &&
74 "StackAllocator has outlived StackArena");
75
76 // try to allocate from stack memory area
77 if (buf_ + Size >= ptr_ + n) {
78 char* r = ptr_;
79 ptr_ += n;
80 if (n % alignment != 0)
81 ptr_ += alignment - n % alignment;
82 return r;
83 }
84 // otherwise fallback to malloc()
85 return static_cast<char*>(malloc(n));
86 }
87
88 void deallocate(char* p, size_t n) noexcept {
89 assert(pointer_in_buffer(ptr_) &&
90 "StackAllocator has outlived StackArena");
91
92 if (pointer_in_buffer(p)) {
93 // free memory area (only works for a stack-ordered
94 // allocations/deallocations).
95 if (p + n == ptr_)
96 ptr_ = p;
97 }
98 else {
99 free(p);
100 }
101 }
102
103 //! size of memory area
104 static constexpr size_t size() noexcept { return Size; }
105
106 //! return number of bytes used in StackArena
107 size_t used() const noexcept { return static_cast<size_t>(ptr_ - buf_); }
108
109 //! reset memory area
110 void reset() noexcept { ptr_ = buf_; }
111};
112
113template <typename Type, size_t Size>
114class StackAllocator : public AllocatorBase<Type>
115{
116public:
117 using value_type = Type;
118 using pointer = Type*;
119 using const_pointer = const Type*;
120 using reference = Type&;
121 using const_reference = const Type&;
122 using size_type = std::size_t;
123 using difference_type = std::ptrdiff_t;
124
125 //! C++11 type flag
126 using is_always_equal = std::false_type;
127
128 //! required rebind.
129 template <typename Other>
131
132 //! default constructor to invalid arena
133 StackAllocator() noexcept : arena_(nullptr) { }
134
135 //! constructor with explicit arena reference
136 explicit StackAllocator(StackArena<Size>& arena) noexcept
137 : arena_(&arena) { }
138
139 //! constructor from another allocator with same arena size
140 template <typename Other>
142 : arena_(other.arena_) { }
143
144 //! copy-constructor: default
145 StackAllocator(const StackAllocator&) noexcept = default;
146
147#if !defined(_MSC_VER)
148 //! copy-assignment: default
149 StackAllocator& operator = (const StackAllocator&) noexcept = default;
150
151 //! move-constructor: default
152 StackAllocator(StackAllocator&&) noexcept = default;
153
154 //! move-assignment: default
155 StackAllocator& operator = (StackAllocator&&) noexcept = default;
156#endif
157
158 //! allocate method: get memory from arena
159 pointer allocate(size_t n) {
160 return reinterpret_cast<Type*>(arena_->allocate(n * sizeof(Type)));
161 }
162
163 //! deallocate method: release from arena
164 void deallocate(pointer p, size_t n) noexcept {
165 arena_->deallocate(reinterpret_cast<char*>(p), n * sizeof(Type));
166 }
167
168 template <typename Other, size_t OtherSize>
170 const StackAllocator<Other, OtherSize>& other) const noexcept {
171 return Size == OtherSize && arena_ == other.arena_;
172 }
173
174 template <typename Other, size_t OtherSize>
176 const StackAllocator<Other, OtherSize>& other) const noexcept {
177 return !operator == (other);
178 }
179
180 template <typename Other, size_t OtherSize>
181 friend class StackAllocator;
182
183private:
185};
186
187} // namespace tlx
188
189#endif // !TLX_STACK_ALLOCATOR_HEADER
190
191/******************************************************************************/
StackAllocator(const StackAllocator &) noexcept=default
copy-constructor: default
StackAllocator(StackArena< Size > &arena) noexcept
constructor with explicit arena reference
pointer allocate(size_t n)
allocate method: get memory from arena
StackAllocator & operator=(const StackAllocator &) noexcept=default
copy-assignment: default
bool operator==(const StackAllocator< Other, OtherSize > &other) const noexcept
StackAllocator() noexcept
default constructor to invalid arena
void deallocate(pointer p, size_t n) noexcept
deallocate method: release from arena
std::false_type is_always_equal
C++11 type flag.
bool operator!=(const StackAllocator< Other, OtherSize > &other) const noexcept
std::ptrdiff_t difference_type
StackAllocator(const StackAllocator< Other, Size > &other) noexcept
constructor from another allocator with same arena size
StackAllocator(StackAllocator &&) noexcept=default
move-constructor: default
Storage area allocated on the stack and usable by a StackAllocator.
void reset() noexcept
reset memory area
~StackArena()
destructor clears ptr_ for debugging.
StackArena() noexcept
default constructor: free pointer at the beginning.
bool pointer_in_buffer(char *p) noexcept
debug method to check whether ptr_ is still in buf_.
AlignmentHelper dummy_for_alignment_
enforce alignment
StackArena(const StackArena &)=delete
char * ptr_
pointer into free bytes in buf_
void deallocate(char *p, size_t n) noexcept
size_t used() const noexcept
return number of bytes used in StackArena
char * allocate(size_t n)
static constexpr size_t alignment
char buf_[Size]
stack memory area used for allocations.
StackArena & operator=(const StackArena &)=delete
static constexpr size_t size() noexcept
size of memory area
StackAllocator< Other, Size > other
union to enforce alignment of buffer area