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>
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 
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) {
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 
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>
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 
183 private:
185 };
186 
187 } // namespace tlx
188 
189 #endif // !TLX_STACK_ALLOCATOR_HEADER
190 
191 /******************************************************************************/
AlignmentHelper dummy_for_alignment_
enforce alignment
char * ptr_
pointer into free bytes in buf_
static constexpr size_t alignment
StackAllocator() noexcept
default constructor to invalid arena
const Type * const_pointer
bool pointer_in_buffer(char *p) noexcept
debug method to check whether ptr_ is still in buf_.
const Type & const_reference
static bool operator!=(const StringView &a, const std::string &b) noexcept
inequality operator to compare a StringView with a std::string
char * allocate(size_t n)
StackArena< Size > * arena_
Storage area allocated on the stack and usable by a StackAllocator.
size_t used() const noexcept
return number of bytes used in StackArena
std::true_type is_always_equal
C++11 type flag.
StackArena() noexcept
default constructor: free pointer at the beginning.
StackAllocator(const StackAllocator< Other, Size > &other) noexcept
constructor from another allocator with same arena size
std::ptrdiff_t difference_type
pointer allocate(size_t n)
allocate method: get memory from arena
char buf_[Size]
stack memory area used for allocations.
static constexpr size_t size() noexcept
size of memory area
static bool operator==(const StringView &a, const std::string &b) noexcept
equality operator to compare a StringView with a std::string
void deallocate(char *p, size_t n) noexcept
void reset() noexcept
reset memory area
~StackArena()
destructor clears ptr_ for debugging.
StackAllocator(StackArena< Size > &arena) noexcept
constructor with explicit arena reference
union to enforce alignment of buffer area
void deallocate(pointer p, size_t n) noexcept
deallocate method: release from arena
StackArena & operator=(const StackArena &)=delete