Thrill  0.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
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 <[email protected]>
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  //! stack memory area used for allocations.
37  alignas(alignment) char buf_[Size];
38 
39  //! pointer into free bytes in buf_
40  char* ptr_;
41 
42  //! debug method to check whether ptr_ is still in buf_.
43  bool pointer_in_buffer(char* p) noexcept
44  { return buf_ <= p && p <= buf_ + Size; }
45 
46 public:
47  //! default constructor: free pointer at the beginning.
48  StackArena() noexcept : ptr_(buf_) { }
49 
50  //! destructor clears ptr_ for debugging.
51  ~StackArena() { ptr_ = nullptr; }
52 
53  StackArena(const StackArena&) = delete;
54  StackArena& operator = (const StackArena&) = delete;
55 
56  char * allocate(size_t n) {
57  assert(pointer_in_buffer(ptr_) &&
58  "StackAllocator has outlived StackArena");
59 
60  // try to allocate from stack memory area
61  if (buf_ + Size >= ptr_ + n) {
62  char* r = ptr_;
63  ptr_ += n;
64  if (n % alignment != 0)
65  ptr_ += alignment - n % alignment;
66  return r;
67  }
68  // otherwise fallback to malloc()
69  return static_cast<char*>(malloc(n));
70  }
71 
72  void deallocate(char* p, size_t n) noexcept {
73  assert(pointer_in_buffer(ptr_) &&
74  "StackAllocator has outlived StackArena");
75 
76  if (pointer_in_buffer(p)) {
77  // free memory area (only works for a stack-ordered
78  // allocations/deallocations).
79  if (p + n == ptr_)
80  ptr_ = p;
81  }
82  else {
83  free(p);
84  }
85  }
86 
87  //! size of memory area
88  static constexpr size_t size() noexcept { return Size; }
89 
90  //! return number of bytes used in StackArena
91  size_t used() const noexcept { return static_cast<size_t>(ptr_ - buf_); }
92 
93  //! reset memory area
94  void reset() noexcept { ptr_ = buf_; }
95 };
96 
97 template <typename Type, size_t Size>
98 class StackAllocator : public AllocatorBase<Type>
99 {
100 public:
101  using value_type = Type;
102  using pointer = Type *;
103  using const_pointer = const Type *;
104  using reference = Type &;
105  using const_reference = const Type &;
106  using size_type = std::size_t;
107  using difference_type = std::ptrdiff_t;
108 
109  //! C++11 type flag
110  using is_always_equal = std::false_type;
111 
112  //! required rebind.
113  template <typename Other>
115 
116  //! default constructor to invalid arena
117  StackAllocator() noexcept : arena_(nullptr) { }
118 
119  //! constructor with explicit arena reference
120  explicit StackAllocator(StackArena<Size>& arena) noexcept
121  : arena_(&arena) { }
122 
123  //! constructor from another allocator with same arena size
124  template <typename Other>
126  : arena_(other.arena_) { }
127 
128  //! copy-constructor: default
129  StackAllocator(const StackAllocator&) noexcept = default;
130 
131 #if !defined(_MSC_VER)
132  //! copy-assignment: default
133  StackAllocator& operator = (StackAllocator&) noexcept = default;
134 
135  //! move-constructor: default
136  StackAllocator(StackAllocator&&) noexcept = default;
137 
138  //! move-assignment: default
139  StackAllocator& operator = (StackAllocator&&) noexcept = default;
140 #endif
141 
142  //! allocate method: get memory from arena
143  pointer allocate(size_t n) {
144  return reinterpret_cast<Type*>(arena_->allocate(n * sizeof(Type)));
145  }
146 
147  //! deallocate method: release from arena
148  void deallocate(pointer p, size_t n) noexcept {
149  arena_->deallocate(reinterpret_cast<char*>(p), n * sizeof(Type));
150  }
151 
152  template <typename Other, size_t OtherSize>
154  const StackAllocator<Other, OtherSize>& other) const noexcept {
155  return Size == OtherSize && arena_ == other.arena_;
156  }
157 
158  template <typename Other, size_t OtherSize>
160  const StackAllocator<Other, OtherSize>& other) const noexcept {
161  return !operator == (other);
162  }
163 
164  template <typename Other, size_t OtherSize>
165  friend class StackAllocator;
166 
167 private:
169 };
170 
171 } // namespace tlx
172 
173 #endif // !TLX_STACK_ALLOCATOR_HEADER
174 
175 /******************************************************************************/
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_.
Type
VFS object type.
Definition: file_io.hpp:52
char * allocate(size_t n)
StackArena< Size > * arena_
bool operator==(const StackAllocator< Other, OtherSize > &other) const noexcept
Storage area allocated on the stack and usable by a StackAllocator.
const Type & const_reference
size_t used() const noexcept
return number of bytes used in StackArena
void * malloc(size_t size) NOEXCEPT
exported malloc symbol that overrides loading from libc
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
StackAllocator & operator=(StackAllocator &) noexcept=default
copy-assignment: default
char buf_[Size]
stack memory area used for allocations.
static constexpr size_t size() noexcept
size of memory area
void deallocate(char *p, size_t n) noexcept
void reset() noexcept
reset memory area
bool operator!=(const StackAllocator< Other, OtherSize > &other) const noexcept
~StackArena()
destructor clears ptr_ for debugging.
StackAllocator(StackArena< Size > &arena) noexcept
constructor with explicit arena reference
void free(void *ptr) NOEXCEPT
exported free symbol that overrides loading from libc
void deallocate(pointer p, size_t n) noexcept
deallocate method: release from arena
StackArena & operator=(const StackArena &)=delete