From df1ef68cd8e8582724ce1192bfc202e0b9aeaf0c Mon Sep 17 00:00:00 2001 From: Karen Arutyunov Date: Tue, 28 Sep 2021 19:24:31 +0300 Subject: Get rid of C++ modules related code and rename *.mxx files to *.hxx --- libbutl/small-allocator.hxx | 181 ++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 181 insertions(+) create mode 100644 libbutl/small-allocator.hxx (limited to 'libbutl/small-allocator.hxx') diff --git a/libbutl/small-allocator.hxx b/libbutl/small-allocator.hxx new file mode 100644 index 0000000..429ba41 --- /dev/null +++ b/libbutl/small-allocator.hxx @@ -0,0 +1,181 @@ +// file : libbutl/small-allocator.hxx -*- C++ -*- +// license : MIT; see accompanying LICENSE file + +#pragma once + +#include +#include // size_t +#include // move() +#include // true_type, is_same + +#include + +namespace butl +{ + // Implementation of the allocator (and its buffer) for small containers. + // + template + struct small_allocator_buffer + { + using value_type = T; + + // Note that the names are decorated in order not to conflict with + // the container's interface. + + // If free_ is true then the buffer is not allocated. + // + alignas (alignof (value_type)) char data_[sizeof (value_type) * N]; + bool free_ = true; + + // Note that the buffer should be constructed before the container and + // destroyed after (since the container's destructor will be destroying + // elements potentially residing in the buffer). This means that the + // buffer should be inherited from and before the std:: container. + // + small_allocator_buffer () = default; + + small_allocator_buffer (small_allocator_buffer&&) = delete; + small_allocator_buffer (const small_allocator_buffer&) = delete; + + small_allocator_buffer& operator= (small_allocator_buffer&&) = delete; + small_allocator_buffer& operator= (const small_allocator_buffer&) = delete; + }; + + template > + class small_allocator + { + public: + using buffer_type = B; + + explicit + small_allocator (buffer_type* b) noexcept: buf_ (b) {} + + // Allocator interface. + // + public: + using value_type = T; + + // These shouldn't be required but as usual there are old/broken + // implementations (like std::list in GCC 4.9). + // + using pointer = value_type*; + using const_pointer = const value_type*; + using reference = value_type&; + using const_reference = const value_type&; + + static void destroy (T* p) {p->~T ();} + + template + static void construct (T* p, A&&... a) + { + ::new (static_cast (p)) T (std::forward (a)...); + } + + // Allocator rebinding. + // + // We assume that only one of the rebound allocators will actually be + // doing allocations and that its value type is the same as buffer value + // type. This is needed, for instance, for std::list since what actually + // gets allocated is the node type, not T (see small_list for details). + // + template + struct rebind {using other = small_allocator;}; + + template + explicit + small_allocator (const small_allocator& x) noexcept + : buf_ (x.buf_) {} + + T* + allocate (std::size_t n) + { + // An implementation can rebind the allocator to something completely + // different. For example, VC15u3 with _ITERATOR_DEBUG_LEVEL != 0 + // allocates some extra stuff which cannot possibly come from the static + // buffer. + // + if (std::is_same::value) + { + if (buf_->free_) + { + assert (n >= N); // We should never be asked for less than N. + + if (n == N) + { + buf_->free_ = false; + return reinterpret_cast (buf_->data_); + } + // Fall through. + } + } + + return static_cast (::operator new (sizeof (T) * n)); + } + + void + deallocate (void* p, std::size_t) noexcept + { + if (p == buf_->data_) + buf_->free_ = true; + else + ::operator delete (p); + } + + friend bool + operator== (small_allocator x, small_allocator y) noexcept + { + // We can use y to deallocate x's allocations if they use the same small + // buffer or neither uses its small buffer (which means all allocations, + // if any, have been from the shared heap). + // + // Things get trickier with rebinding. If A is allocator and B is its + // rebinding, then the following must hold true: + // + // A a1(a) => a1==a + // A a(b) => B(a)==b && A(b)==a + // + // As a result, the rebinding constructor above always copies the buffer + // pointer and we decide whether to use the small buffer by comparing + // allocator/buffer value types. + // + // We also expect that any copy of the original allocator made by the + // std:: implementation of the container is temporary (that is, it + // doesn't outlive the small buffer). + // + return (x.buf_ == y.buf_) || (x.buf_->free_ && y.buf_->free_); + } + + friend bool + operator!= (small_allocator x, small_allocator y) noexcept + { + return !(x == y); + } + + // It might get instantiated but should not be called. + // + small_allocator + select_on_container_copy_construction () const noexcept + { + assert (false); + return small_allocator (nullptr); + } + + // propagate_on_container_copy_assignment = false + // propagate_on_container_move_assignment = false + + // Swap is not supported (see explanation in small_vector::swap()). + // + using propagate_on_container_swap = std::true_type; + + void + swap (small_allocator&) = delete; + + private: + template + friend class small_allocator; // For buffer access in rebind. + + buffer_type* buf_; // Must not be NULL. + }; +} -- cgit v1.1