tlx
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 
24 #include <tlx/allocator_base.hpp>
25 
26 namespace tlx {
27 
28 /*!
29  * Storage area allocated on the stack and usable by a StackAllocator.
30  */
31 template <size_t Size>
32 class StackArena
33 {
34  static constexpr size_t alignment = 16;
35 
36  //! union to enforce alignment of buffer area
37  union AlignmentHelper {
38  int i;
39  long l;
40  long long ll;
41  long double ld;
42  double d;
43  void* p;
44  void (* pf)();
45  AlignmentHelper* ps;
46  };
47 
48  union {
49  //! stack memory area used for allocations.
50  char buf_[Size];
51  //! enforce alignment
52  AlignmentHelper dummy_for_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 
62 public:
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;
70  StackArena& operator = (const StackArena&) = delete;
71 
72  char * allocate(size_t n) {
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 
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 
113 template <typename Type, size_t Size>
114 class StackAllocator : public AllocatorBase<Type>
115 {
116 public:
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>
130  struct rebind { using other = StackAllocator<Other, Size>; };
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>
141  StackAllocator(const StackAllocator<Other, Size>& other) noexcept
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>
169  bool operator == (
170  const StackAllocator<Other, OtherSize>& other) const noexcept {
171  return Size == OtherSize && arena_ == other.arena_;
172  }
173 
174  template <typename Other, size_t OtherSize>
175  bool operator != (
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 
183 private:
185 };
186 
187 } // namespace tlx
188 
189 #endif // !TLX_STACK_ALLOCATOR_HEADER
190 
191 /******************************************************************************/
tlx::StackArena::pointer_in_buffer
bool pointer_in_buffer(char *p) noexcept
debug method to check whether ptr_ is still in buf_.
Definition: stack_allocator.hpp:87
tlx::StackArena::alignment
static constexpr size_t alignment
Definition: stack_allocator.hpp:62
tlx::StackArena::ptr_
char * ptr_
pointer into free bytes in buf_
Definition: stack_allocator.hpp:84
tlx::StackAllocator::arena_
StackArena< Size > * arena_
Definition: stack_allocator.hpp:198
tlx::StackArena::dummy_for_alignment_
AlignmentHelper dummy_for_alignment_
enforce alignment
Definition: stack_allocator.hpp:80
tlx::StackArena::AlignmentHelper::p
void * p
Definition: stack_allocator.hpp:71
tlx::StackAllocator::allocate
pointer allocate(size_t n)
allocate method: get memory from arena
Definition: stack_allocator.hpp:173
tlx::StackArena::AlignmentHelper::i
int i
Definition: stack_allocator.hpp:66
tlx::StackAllocator::pointer
Type * pointer
Definition: stack_allocator.hpp:132
tlx::StackAllocator::deallocate
void deallocate(pointer p, size_t n) noexcept
deallocate method: release from arena
Definition: stack_allocator.hpp:178
tlx::AllocatorBase::pointer
Type * pointer
Definition: allocator_base.hpp:43
tlx::StackArena::allocate
char * allocate(size_t n)
Definition: stack_allocator.hpp:100
tlx::StackArena::AlignmentHelper::pf
void(* pf)()
Definition: stack_allocator.hpp:72
tlx::StackAllocator::is_always_equal
std::false_type is_always_equal
C++11 type flag.
Definition: stack_allocator.hpp:140
tlx::StackArena::AlignmentHelper::l
long l
Definition: stack_allocator.hpp:67
tlx::StackArena::AlignmentHelper::ld
long double ld
Definition: stack_allocator.hpp:69
tlx::StackAllocator::operator=
StackAllocator & operator=(const StackAllocator &) noexcept=default
copy-assignment: default
tlx::StackAllocator::const_reference
const Type & const_reference
Definition: stack_allocator.hpp:135
tlx::StackArena::AlignmentHelper::ll
long long ll
Definition: stack_allocator.hpp:68
tlx::StackAllocator::value_type
Type value_type
Definition: stack_allocator.hpp:131
tlx::StackArena::AlignmentHelper::ps
AlignmentHelper * ps
Definition: stack_allocator.hpp:73
tlx::StackAllocator
Definition: stack_allocator.hpp:128
tlx::StackAllocator::rebind
required rebind.
Definition: stack_allocator.hpp:144
tlx
Definition: exclusive_scan.hpp:17
tlx::StackArena::used
size_t used() const noexcept
return number of bytes used in StackArena
Definition: stack_allocator.hpp:135
tlx::StackAllocator::rebind::other
StackAllocator< Other, Size > other
Definition: stack_allocator.hpp:144
tlx::StackAllocator::operator==
bool operator==(const StackAllocator< Other, OtherSize > &other) const noexcept
Definition: stack_allocator.hpp:183
tlx::StackAllocator::size_type
std::size_t size_type
Definition: stack_allocator.hpp:136
tlx::StackArena
Storage area allocated on the stack and usable by a StackAllocator.
Definition: stack_allocator.hpp:46
tlx::StackArena::buf_
char buf_[Size]
stack memory area used for allocations.
Definition: stack_allocator.hpp:78
tlx::StackArena::StackArena
StackArena() noexcept
default constructor: free pointer at the beginning.
Definition: stack_allocator.hpp:92
tlx::StackArena::size
static constexpr size_t size() noexcept
size of memory area
Definition: stack_allocator.hpp:132
tlx::StackAllocator::difference_type
std::ptrdiff_t difference_type
Definition: stack_allocator.hpp:137
tlx::StackArena::AlignmentHelper::d
double d
Definition: stack_allocator.hpp:70
tlx::StackAllocator::const_pointer
const Type * const_pointer
Definition: stack_allocator.hpp:133
tlx::StackArena::deallocate
void deallocate(char *p, size_t n) noexcept
Definition: stack_allocator.hpp:116
tlx::StackAllocator::StackAllocator
friend class StackAllocator
Definition: stack_allocator.hpp:195
allocator_base.hpp
tlx::StackArena::reset
void reset() noexcept
reset memory area
Definition: stack_allocator.hpp:138
tlx::StackArena::~StackArena
~StackArena()
destructor clears ptr_ for debugging.
Definition: stack_allocator.hpp:95
tlx::StackArena::operator=
StackArena & operator=(const StackArena &)=delete
tlx::StackAllocator::reference
Type & reference
Definition: stack_allocator.hpp:134
tlx::StackAllocator::operator!=
bool operator!=(const StackAllocator< Other, OtherSize > &other) const noexcept
Definition: stack_allocator.hpp:189