Skip to content

Instantly share code, notes, and snippets.

@tomilov
Last active October 7, 2015 06:34
Show Gist options
  • Save tomilov/ab62e68ada0c5650c609 to your computer and use it in GitHub Desktop.
Save tomilov/ab62e68ada0c5650c609 to your computer and use it in GitHub Desktop.
Howard Hinnant's short_allocator implementation
#include <iostream>
#include <ostream>
#include <utility>
#include <type_traits>
#include <functional>
#include <memory>
#include <vector>
#include <cstdlib>
#include <cassert>
#include <cstddef>
struct arena // control block
{
template< typename storage >
arena(storage & a) noexcept
: b(&a)
, p(b)
, s(sizeof(storage))
{ ; }
template< typename type >
type *
allocate(std::size_t n) noexcept
{
std::size_t const size = sizeof(type) * n;
void * r = std::align(alignof(type), size, p, s);
if (r) {
p = static_cast< type * >(p) + n;
s -= size;
}
return static_cast< type * >(r);
}
template< typename type >
bool
deallocate(type * r, std::size_t n) noexcept
{
std::less< void * > less;
if (less(r, b) || !less(r, static_cast< char * >(p) + s)) {
return false;
}
assert(!less(static_cast< char * >(p) + s, r + n));
if (r + n == p) {
p = r;
s += n * sizeof(type);
}
return true;
}
constexpr
bool
operator == (arena const & _rhs) noexcept
{
return (this == &_rhs);
}
friend
std::ostream &
operator << (std::ostream & _out, arena const & _arena)
{
return _out << _arena.p << ' ' << _arena.s;
}
private :
void * b;
void * p;
std::size_t s;
};
template< typename type >
struct arena_allocator
{
using value_type = type;
using propagate_on_container_copy_assignment = std::true_type;
using propagate_on_container_move_assignment = std::true_type;
using propagate_on_container_swap = std::true_type;
constexpr
arena_allocator(arena & _arena) noexcept
: arena_(&_arena)
{ ; }
template< typename rhs >
constexpr
arena_allocator(arena_allocator< rhs > const & _rhs) noexcept
: arena_(_rhs.arena_)
{ ; }
value_type *
allocate(std::size_t n) noexcept
{
value_type * r = arena_->allocate< value_type >(n);
if (!r) {
r = static_cast< value_type * >(::operator new(n));
}
return r;
}
void
deallocate(value_type * p, std::size_t n) noexcept
{
if (!arena_->deallocate(p, n)) {
::operator delete(p);
}
}
template< typename rhs >
constexpr
bool
operator == (arena_allocator< rhs > const & _rhs) noexcept
{
return (*_rhs.arena_ == *arena_);
}
template< typename rhs >
constexpr
bool
operator != (arena_allocator< rhs > const & _rhs) noexcept
{
return !operator == (_rhs);
}
friend
std::ostream &
operator << (std::ostream & _out, arena_allocator const & _short_allocator)
{
return _out << *_short_allocator.arena_;
}
private :
arena * arena_;
};
int
main()
{
char storage_[3];
arena arena_{storage_};
using type = struct {};
using allocator = arena_allocator< type >;
allocator allocator_{arena_};
using container = std::vector< type, allocator >;
std::cout << allocator_ << std::endl;
container x{allocator_};
std::cout << allocator_ << std::endl;
x.reserve(2);
std::cout << allocator_ << std::endl;
x.emplace_back();
std::cout << allocator_ << std::endl;
x.emplace_back();
std::cout << allocator_ << std::endl;
auto y = x;
std::cout << allocator_ << std::endl;
x.pop_back();
std::cout << allocator_ << std::endl;
x.pop_back();
std::cout << allocator_ << std::endl;
y.clear();
std::cout << allocator_ << std::endl;
y.shrink_to_fit();
std::cout << allocator_ << std::endl;
x.shrink_to_fit();
std::cout << allocator_ << std::endl;
return EXIT_SUCCESS;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment