<file_sep>#include "allocator.hpp"

#include <cstdlib>
#include <cassert>

#include "utils.hpp"

void* detail::allocate_aligned_memory(size_t align, size_t size)
{
    assert(align >= sizeof(void*));
    assert(is_power_of_two(align));

    if (size == 0) {
        return nullptr;
    }

    void* ptr = nullptr;
    int rc = posix_memalign(&ptr, align, size);

    if (rc != 0) {
        return nullptr;
    }

    return ptr;
}


void detail::deallocate_aligned_memory(void *ptr) noexcept
{
    return free(ptr);
}
<file_sep>
add_library(skip_list
	allocator.cpp
	allocator.hpp
	skip_list.hpp
	utils.hpp
)

target_include_directories(skip_list
	INTERFACE .)
<file_sep>cmake_minimum_required(VERSION 3.6)
project(skip_list)

set(CMAKE_CXX_STANDARD 14)

enable_testing()

include(gtest.cmake)

add_subdirectory(src)
add_subdirectory(test)
<file_sep>#pragma once

#include <cstdint>
#include <cstring>
#include <cassert>
#include <climits>
#include <cmath>

#include <vector>
#include <utility>
#include <random>
#include <string>
#include <array>
#include <algorithm>
#include <iterator>
#include <unordered_set>

#include "utils.hpp"
#include "allocator.hpp"

template<typename key_type, typename value_type,
	size_t N = (64 - sizeof(key_type) - sizeof(value_type)) / sizeof(void*) >
struct skip_list
{
	public:
		using side_t = uint8_t;
		constexpr static bool use_uniform_dist = false;
		constexpr static bool use_log_dist = false;
		constexpr static bool use_sqrt_dist = false;
		constexpr static bool use_rev_sqrt_dist = false;
		constexpr static bool use_rev_log_dist = true;

		constexpr static bool allow_duplicates = false;
	protected:
		static bool eq(key_type a, key_type b) { return a==b; }
		bool lt(key_type a, key_type b) const { return sd_?(b<a):(a<b); }
		bool gt(key_type a, key_type b) const { return sd_?(a<b):(b<a); }

		bool ge(key_type a, key_type b) const { return gt(a,b) || eq(a,b); }

		struct elem
		{
			constexpr static size_t align = 64;
			key_type key;
			value_type value;
			std::array<elem*, N> forwards { nullptr };

			elem(key_type k, value_type v) : key(k), value(v), forwards({}) {}

			elem(key_type k, value_type v, std::array<elem*, N> const & a)
				: key(k), value(v), forwards(a)
			{}

			static void set_forwards(std::array<elem*, N> & forwards, size_t a, size_t b, elem * p)
			{
				for(size_t i = a; i < b; ++i) { forwards[i] = p; }
			}
			void set_forwards(size_t a, size_t b, elem * p) { set_forwards(forwards, a, b, p); }

			static std::string distance_between(elem const * p, elem const * o)
			{
				if ( !p ) return ".";
				if ( !o ) return "-";
				int r = 0;
				for(; p != o; p = p->forwards[0], ++r);
				return std::to_string(r);
			}

			template<typename ostream>
				static ostream & dump_distances(ostream & o,
						elem const * p, std::array<elem *,N> const & f)
				{
					char const * sep = "[";
					for(auto & e : f) {
						o << sep << distance_between(p, e) << " (" << e << ")";
						sep = ", ";
					}
					o << "]";
					return o;
				}

			template<typename ostream>
				ostream & dump(ostream & o) const
				{
					return dump_distances( o << "[" << (void*)this << ": "
							<< key << " -> " << value << " ", this, forwards ) << "]";
				}
		};

		static_assert( sizeof(elem) == 64, "elem is expected to fit into a cache line" );

		side_t sd_;
		size_t size_ = 0;
		elem * head_ = nullptr;

		using allocator_type = aligned_allocator< elem, elem::align >;

	public:

		skip_list(side_t sd) : sd_(sd) {}
		~skip_list() { clear(); }

		bool empty() const { return head_ == nullptr; }
		size_t size() const { return size_; }
		void clear()
		{
			elem * p = head_;
			while( p ) {
				elem * n = p->forwards[0];
				allocator_type::destroy(p);
				allocator_type::deallocate(p,1);
				p = n;
			}
			size_ = 0;
		}

		size_t count() const
		{
			size_t r = 0;
			for(elem const * p = head_; p; p = p->forwards[0], ++r);
			return r;
		}

		std::vector< std::pair<key_type, value_type> > to_vector() const
		{
			std::vector< std::pair<key_type, value_type> > r;
			r.reserve( size_ );
			for(elem const * p = head_; p; p = p->forwards[0]) {
				r.push_back( std::make_pair(p->key, p->value) );
			}
			return r;
		}

		value_type * find(key_type k) const
		{
			if ( elem * p = head_ )
			{
				if( eq( p->key, k ) ) return &(p->value);

				for(size_t lvl = N; lvl > 0;) {
					--lvl;
					while( p->forwards[lvl] && lt( p->forwards[lvl]->key, k) ) {
						p = p->forwards[lvl];
					}
					assert( p->forwards[lvl] == nullptr || ge( p->forwards[lvl]->key, k) );
				}

				if ( p->forwards[0] ) {
					return ( eq( p->forwards[0]->key, k ) ?  &(p->forwards[0]->value) : nullptr );
				}
			}

			return nullptr;
		}
		bool contains(key_type k) const { return find(k) != nullptr; }

		template<typename ostream>
			ostream & dump(ostream & o, char const * sep = ", ", int limit = INT_MAX,
					std::set<elem const*> marked = {}) const
			{
				o << "[sd=" << (int)sd_ << ", size=" << size_ << ", head=" << (void*)head_ << ": ";
				int cnt = 0;
				char const * ssep = sep;
				for(elem const * p = head_; p; p = p->forwards[0], ssep=sep)
				{
					if ( cnt++ >= limit ) {
						o << sep << "...";
						break;
					}
					p->dump(o << sep << (marked.count(p) ? "*" : " " ));
				}
				o << "]";

				return o;
			}

		bool insert(key_type k, value_type v)
		{
			//dump(std::cout << "-- insert (" << k << "->" << v << "), into:\n", "\n") << std::endl;
			std::array<elem*, N> forwards {};
			if ( elem * p = head_ ) {
				if ( lt( p->key, k ) ) {
					for(size_t lvl = N; lvl > 0;) {
						--lvl;
						while( p->forwards[lvl] && lt( p->forwards[lvl]->key, k) ) {
							p = p->forwards[lvl];
						}
						forwards[lvl] = p;
						assert( lt(p->key, k) ); // p->key < k, k is strictly greater than p->key
					}

					if ( !allow_duplicates && p->forwards[0] && eq( p->forwards[0]->key, k ) )
						return false;

					insert_after(p, k, v, random_level(), forwards);
				}
				else {
					if ( !allow_duplicates && eq(p->key, k) ) return false;

					assert( p == head_ );
					assert( lt(k, p->key) || eq(p->key, k) ); // k < p->key

					// insert before head: take current head's forward as new refs, p->forwards
					if ( p->forwards[0] ) {
						assert( p->forwards[N-1] != nullptr && "head needs to have all levels");
						insert_head( k, v, random_level(), p->forwards );
					}
					else {
						assert( size_ == 1 );
						elem::set_forwards( forwards, 0, N, p );
						insert_head( k, v, random_level(), forwards );
						assert( size_ == 2 );
					}
					assert( head_->forwards[N-1] != nullptr && "head needs to have all levels");
					assert( head_ != p && "new elem inserted as a head" );
				}
			}
			else {
				assert( head_ == nullptr );
				assert( std::all_of(forwards.begin(), forwards.end(),
							[](auto * p){ return p == nullptr; }));

				insert_head( k, v, 0, forwards );
				assert( size_ == 1 );
			}
			return true;
		}

		void erase_head()
		{
			assert( head_ && size_ > 0 );
			elem * old = head_;
			head_ = head_->forwards[0];
			if ( head_ ) {
				size_t i = 1;
				for( ; i < N && head_->forwards[i]; ++i ) ; // skip filled cells
				for( ; i < N; ++i ) {
					assert( head_->forwards[i] == nullptr );
					// copy from old head unless it would cause a loop
					head_->forwards[i] = ( old->forwards[i] != head_ ) ?
						old->forwards[i] :
						head_->forwards[i-1];
				}
			}

			assert( size_ > 0 );
			size_--;
			allocator_type::destroy(old);
			allocator_type::deallocate(old, 1);
		}

		void erase_after( elem * prev, elem * del, std::array<elem*, N> & fwrds)
		{
			assert( prev && size_ > 0 );
			assert( del && del == prev->forwards[0]);
			assert( fwrds[0] == prev );

			fwrds[0]->forwards[0] = del->forwards[0];
			for(size_t i = 1; i < N; ++i) {
				// fixup level pointers
				if ( del == fwrds[i]->forwards[i] ) {
					// copy from deleted, unless it would cause a loop, then take previous forwards
					fwrds[i]->forwards[i] =
						( del->forwards[i] && del->forwards[i] != fwrds[i] ) ?
						del->forwards[i] :
						fwrds[i]->forwards[i-1];
				}
			}

			assert( size_ > 0 );
			size_--;
			allocator_type::destroy(del);
			allocator_type::deallocate(del, 1);
		};

		std::pair<value_type, size_t> erase(key_type k)
		{
			if ( elem * p = head_ ) {
				std::array<elem*, N> forwards {};
				if ( lt( p->key, k ) ) {
					for(size_t lvl = N; lvl > 0;) {
						--lvl;
						while( p->forwards[lvl] && lt( p->forwards[lvl]->key, k) ) {
							p = p->forwards[lvl];
						}
						forwards[lvl] = p;
						assert( lt(p->key, k) ); // p->key < k, k is strictly greater than p->key
					}

					elem * q = p->forwards[0];
					if ( q && eq( q->key, k ) ) {
						auto r = q->value;
						erase_after(p, q, forwards);
						return std::make_pair(r, 1);
					}
				}
				else {
					if ( eq(p->key, k) ) {
						auto r = p->value;
						assert( p == head_ );
						erase_head();
						return std::make_pair(r, 1);
					}
				}
			}
			return std::make_pair(value_type{}, 0);
		}

		struct iter_impl : public std::iterator< std::forward_iterator_tag, elem >
		{
			elem * p;

			iter_impl(elem * x) : p(x) {}
			void next() { p = p->forwards[0]; }
			bool operator==(iter_impl o) const { return p == o.p; }
			bool operator!=(iter_impl o) const { return p != o.p; }
			elem & operator*() { return *p; }
			elem const & operator*() const { return *p; }
			elem * operator->() { return p; }
			elem const * operator->() const { return p; }
			iter_impl & operator++() { next(); return *this; }
			iter_impl operator++(int) { iter_impl tmp{*this}; next(); return tmp; }
		};

		using iterator = iter_impl;
		using const_iterator = const iter_impl;

		iterator begin() { return iterator{head_}; }
		iterator end() { return iterator{nullptr}; }
		const_iterator cbegin() { return const_iterator{head_}; }
		const_iterator cend() { return const_iterator{nullptr}; }
		const_iterator begin() const { return const_iterator{head_}; }
		const_iterator end() const { return const_iterator{nullptr}; }

	protected:

		size_t random_level()
		{
			static std::random_device rd;
			size_t r = N;
			if ( use_uniform_dist )
			{
				std::uniform_int_distribution<int> dist_{1,N};
				r = dist_(rd);
			}
			else if ( use_log_dist )
			{
				std::uniform_int_distribution<int> dist_{2,1<<N};
				r = std::log2(dist_(rd));
			}
			else if ( use_rev_log_dist )
			{
				std::uniform_int_distribution<int> dist_{2,1<<N};
				r = N-std::log2(dist_(rd))+1;
			}
			else if ( use_sqrt_dist )
			{
				std::uniform_int_distribution<int> dist_{1,N*N};
				r = std::sqrt(dist_(rd));
			}
			else if ( use_rev_sqrt_dist )
			{
				std::uniform_int_distribution<int> dist_{1,N*N};
				r = N-std::sqrt(dist_(rd))+1;
			}
			assert( r != 0 );
			assert( 1 <= r && r <= N );
			return r;
		}

		void insert_after(elem* p, key_type k, value_type v,
				size_t lvl, std::array<elem*, N> const fwrds)
		{
			elem * e = allocator_type::allocate(1);
			allocator_type::construct(e, k, v);

			//elem::dump_distances(std::cout << "-- insert_after (p=" << p << ", lvl=" << lvl << ", "
			//	<< k << "->" << v << ", fwrds=", nullptr, fwrds) << ")" << std::endl;

			size_t n = fwrds[N-1] == head_ ? N : lvl;
			for(size_t i = 0; i < n; ++i)
			{
				//TODO: embed ranvom level
				elem * f = fwrds[i];
				elem * aux = f->forwards[i];
				f->forwards[i] = e;
				e->forwards[i] = aux;
			}
			size_++;
		}

		void insert_head( key_type k, value_type v, size_t lvl, std::array<elem*, N> const & fwrds)
		{
			elem * e = allocator_type::allocate(1);
			allocator_type::construct(e, k, v, fwrds);

			//elem::dump_distances(std::cout << "-- insert_head (lvl=" << lvl << ", "
			//		<< k << "->" << v << ", fwrds=", nullptr, fwrds) << ")" << std::endl;

			elem * p = head_;
			head_ = e;
			head_->set_forwards(0, lvl, p);
			if ( p ) p->set_forwards(lvl, N, nullptr);
			size_++;
		}

};



<file_sep>#include "skip_list.hpp"
<file_sep>add_executable(tester
	skip_list_test.cpp)

target_link_libraries(tester
	skip_list
	libgtest
	libgtest_main)

add_test(NAME skip_list_test
	COMMAND tester)

<file_sep>#include <gtest/gtest.h>

#include <iostream>

#include "skip_list.hpp"

using test_type = skip_list<int32_t, void*>;

struct skip_list_test : public ::testing::TestWithParam<int8_t> {};

INSTANTIATE_TEST_CASE_P(bid_or_ask, skip_list_test, ::testing::Values(0,1));

TEST_P(skip_list_test, instance)
{
	EXPECT_NO_THROW({
			test_type x(GetParam());
			test_type y = x;
			//const test_type x = y;
	});
}

TEST_P(skip_list_test, empty)
{
	test_type x(GetParam());

	EXPECT_TRUE( x.empty() );
	EXPECT_EQ( 0, x.size() );
	EXPECT_EQ( 0, x.count() );
	EXPECT_EQ( nullptr, x.find(0) );
	EXPECT_EQ( nullptr, x.find(1) );
	EXPECT_FALSE( x.contains(0) );
	EXPECT_FALSE( x.contains(1) );
}

TEST_P(skip_list_test, insert_1)
{
	test_type x(GetParam());

	EXPECT_TRUE( x.empty() );

	EXPECT_TRUE( x.insert(1, (void*)1UL ) );
	EXPECT_FALSE( x.empty() );
	EXPECT_EQ( 1, x.size() );
	EXPECT_EQ( x.size(), x.count() );
	EXPECT_TRUE( x.contains(1) );
	ASSERT_NE( nullptr, x.find(1) );
	EXPECT_EQ( (void*)1UL, *x.find(1) );

	EXPECT_FALSE( x.insert(1, (void*)1UL ) );
	EXPECT_EQ( 1, x.size() );
	EXPECT_TRUE( x.contains(1) );
}

TEST_P(skip_list_test, insert_315)
{
	test_type x(GetParam());
	EXPECT_TRUE ( x.insert(3, (void*)1UL ) );
	EXPECT_TRUE ( x.insert(1, (void*)1UL ) );
	EXPECT_TRUE ( x.insert(5, (void*)1UL ) );

	//x.dump(std::cout, "\n") << std::endl;

	auto v = x.to_vector();
	ASSERT_EQ( 3, v.size() );
	if ( GetParam() == 0 )
	{
		EXPECT_EQ( 1, v[0].first );
		EXPECT_EQ( 3, v[1].first );
		EXPECT_EQ( 5, v[2].first );
	}
	else
	{
		EXPECT_EQ( 5, v[0].first );
		EXPECT_EQ( 3, v[1].first );
		EXPECT_EQ( 1, v[2].first );
	}
}

TEST_P(skip_list_test, insert_duplicates)
{
	test_type x(GetParam());

	ASSERT_FALSE( x.allow_duplicates );

	EXPECT_TRUE ( x.insert(1, (void*)1UL ) );
	EXPECT_FALSE( x.insert(1, (void*)1UL ) );
	EXPECT_TRUE ( x.insert(3, (void*)1UL ) );
	EXPECT_FALSE( x.insert(1, (void*)1UL ) );
	EXPECT_FALSE( x.insert(3, (void*)1UL ) );
	EXPECT_TRUE ( x.insert(5, (void*)1UL ) );
	EXPECT_FALSE( x.insert(1, (void*)1UL ) );
	EXPECT_FALSE( x.insert(3, (void*)1UL ) );
	EXPECT_FALSE( x.insert(5, (void*)1UL ) );
	//x.dump(std::cout, "\n") << std::endl;

	auto v = x.to_vector();
	ASSERT_EQ( 3, v.size() );
	if ( GetParam() == 0 )
	{
		EXPECT_EQ( 1, v[0].first );
		EXPECT_EQ( 3, v[1].first );
		EXPECT_EQ( 5, v[2].first );
	}
	else
	{
		EXPECT_EQ( 5, v[0].first );
		EXPECT_EQ( 3, v[1].first );
		EXPECT_EQ( 1, v[2].first );
	}
}


TEST_P(skip_list_test, contains)
{
	test_type x(GetParam());

	ASSERT_TRUE( x.insert(1, (void*)1UL ) );
	ASSERT_TRUE( x.insert(3, (void*)1UL ) );
	ASSERT_TRUE( x.insert(5, (void*)1UL ) );

	//x.dump(std::cout, "\n") << std::endl;

	EXPECT_TRUE( x.contains(1) );
	EXPECT_TRUE( x.contains(3) );
	EXPECT_TRUE( x.contains(5) );

	EXPECT_FALSE( x.contains(0) );
	EXPECT_FALSE( x.contains(2) );
	EXPECT_FALSE( x.contains(4) );
	EXPECT_FALSE( x.contains(6) );
}

TEST_P(skip_list_test, insert_10)
{
	test_type x(GetParam());
	std::array<int, 10> v { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

	EXPECT_TRUE( x.empty() );

	for(int i : v)
	{
		ASSERT_TRUE( x.insert(i, (void*)(size_t)i ) ) << "i=" << i;
	}
	EXPECT_FALSE( x.empty() );
	EXPECT_EQ( v.size(), x.size() );
	EXPECT_EQ( x.size(), x.count() );

	//x.dump(std::cout, "\n", 10) << std::endl;

	for(int i : v)
	{
		EXPECT_TRUE( x.contains(i) ) << "i=" << i;
	}
}

TEST_P(skip_list_test, insert_10_perm)
{
	test_type x(GetParam());
	std::array<int, 10> v { 5, 2, 9, 4, 1, 6, 7, 10, 3, 8 };

	EXPECT_TRUE( x.empty() );

	for(int i : v)
	{
		ASSERT_TRUE( x.insert(i, (void*)(size_t)i ) ) << "i=" << i;
	}
	EXPECT_FALSE( x.empty() );
	EXPECT_EQ( v.size(), x.size() );
	EXPECT_EQ( x.size(), x.count() );

	//x.dump(std::cout, "\n", 10) << std::endl;

	for(int i : v)
	{
		EXPECT_TRUE( x.contains(i) ) << "i=" << i;
	}
}
TEST_P(skip_list_test, insert_1000)
{
	test_type x(GetParam());
	int N = 1000; //test_type::max_elements_in_block();

	EXPECT_TRUE( x.empty() );

	for(int i = 1; i <= N; ++i)
	{
		ASSERT_TRUE( x.insert(i, (void*)(size_t)i ) ) << "i=" << i;
	}
	EXPECT_FALSE( x.empty() );
	EXPECT_EQ( N, x.size() );
	EXPECT_EQ( x.size(), x.count() );

	//x.dump(std::cout, "\n") << std::endl;

	for(int i = 1; i <= N; ++i)
	{
		EXPECT_TRUE( x.contains(i) ) << "i=" << i;
	}
}

TEST_P(skip_list_test, insert_1000_rev)
{
	test_type x(GetParam());
	int N = 1000;

	EXPECT_TRUE( x.empty() );

	for(int i = N; i >= 1; --i)
	{
		ASSERT_TRUE( x.insert(i, (void*)(size_t)i ) ) << "i=" << i;
	}
	EXPECT_FALSE( x.empty() );
	EXPECT_EQ( N, x.size() );
	EXPECT_EQ( x.size(), x.count() );

	for(int i = 1; i <= N; ++i)
	{
		EXPECT_TRUE( x.contains(i) ) << "i=" << i;
	}
}

TEST_P(skip_list_test, insert_1000_dup)
{
	test_type x(GetParam());
	int N = 1000; //test_type::max_elements_in_block();

	EXPECT_TRUE( x.empty() );

	ASSERT_FALSE( x.allow_duplicates );

	for(int i = 1; i <= N; ++i)
	{
		ASSERT_TRUE( x.insert(i, (void*)(size_t)i ) ) << "i=" << i;
		ASSERT_FALSE( x.insert(i, (void*)(size_t)i ) ) << "i=" << i;
	}
	for(int i = N; i >= 1; --i)
	{
		ASSERT_FALSE( x.insert(i, (void*)(size_t)i ) ) << "i=" << i;
	}
	EXPECT_FALSE( x.empty() );
	EXPECT_EQ( N, x.size() );
	EXPECT_EQ( x.size(), x.count() );

	//x.dump(std::cout, "\n") << std::endl;

	for(int i = 1; i <= N; ++i)
	{
		EXPECT_TRUE( x.contains(i) ) << "i=" << i;
	}
}

TEST_P(skip_list_test, erase_when_empty)
{
	test_type x(GetParam());

	EXPECT_TRUE( x.empty() );
	EXPECT_EQ( nullptr, x.erase(1).first );
	EXPECT_EQ( 0, x.erase(1).second );
	EXPECT_TRUE( x.empty() );
}

TEST_P(skip_list_test, erase_1_after_insert_1)
{
	test_type x(GetParam());

	EXPECT_TRUE( x.empty() );

	EXPECT_TRUE( x.insert(1, (void*)1UL ) );
	EXPECT_FALSE( x.empty() );
	EXPECT_TRUE( x.contains(1) );

	EXPECT_EQ( (void*)1UL, x.erase(1).first );
	EXPECT_TRUE( x.empty() );
	EXPECT_FALSE( x.contains(1) );

	EXPECT_EQ( nullptr, x.erase(1).first );
}

TEST_P(skip_list_test, insert_and_erase_1000)
{
	test_type x(GetParam());
	int N = 1000; //test_type::max_elements_in_block();

	EXPECT_TRUE( x.empty() );

	ASSERT_FALSE( x.allow_duplicates );

	for(int i = 1; i <= N; ++i)
	{
		ASSERT_TRUE( x.insert(i, (void*)(size_t)i ) ) << "i=" << i;
	}
	ASSERT_FALSE( x.empty() );
	ASSERT_EQ( N, x.size() );

	//x.dump(std::cout, "\n") << std::endl;

	for(int i = 1; i <= N; ++i)
	{
		EXPECT_EQ( (void*)(size_t)i, x.erase(i).first ) << "i=" << i;
		//x.dump(std::cout << "$$", "\n") << std::endl;
	}
	EXPECT_TRUE( x.empty() );
	EXPECT_EQ(0, x.size() );
}

TEST_P(skip_list_test, erase_10_perm)
{
	test_type x(GetParam());
	std::array<int, 10> v { 5, 2, 9, 4, 1, 6, 7, 10, 3, 8 };

	int N = 10;

	for(int i = 1; i <= N; ++i)
	{
		ASSERT_TRUE( x.insert(i, (void*)(size_t)i ) ) << "i=" << i;
	}
	ASSERT_FALSE( x.empty() );
	ASSERT_EQ( N, x.size() );

	for(int i : v)
	{
		EXPECT_EQ( (void*)(size_t)i, x.erase(i).first ) << "i=" << i;
	}
	EXPECT_TRUE( x.empty() );
	EXPECT_EQ(0, x.size() );
}
<file_sep>#pragma once

#include <cstdlib>
#include <cstddef>
#include <memory>
#include <type_traits>
#include <utility>

namespace detail {
    void* allocate_aligned_memory(size_t align, size_t size);
    void deallocate_aligned_memory(void* ptr) noexcept;
}


template <typename T, size_t Align> class aligned_allocator;


template <size_t Align>
class aligned_allocator<void, Align>
{
	public:
		typedef void*             pointer;
		typedef const void*       const_pointer;
		typedef void              value_type;

		template <class U> struct rebind { typedef aligned_allocator<U, Align> other; };
};


template <typename T, size_t Align>
class aligned_allocator
{
	public:
		typedef T         value_type;
		typedef T*        pointer;
		typedef const T*  const_pointer;
		typedef T&        reference;
		typedef const T&  const_reference;
		typedef size_t    size_type;
		typedef ptrdiff_t difference_type;

		typedef std::true_type propagate_on_container_move_assignment;

		template <class U> struct rebind { typedef aligned_allocator<U, Align> other; };

	public:
		aligned_allocator() noexcept = default;
		template <class U> aligned_allocator(const aligned_allocator<U, Align>&) noexcept {}

		static size_type max_size() noexcept { return (size_type(~0) - size_type(Align)) / sizeof(T); }
		static pointer address(reference x) noexcept { return std::addressof(x); }
		static const_pointer address(const_reference x) noexcept { return std::addressof(x); }

		static pointer allocate(size_type n, typename aligned_allocator<void, Align>::const_pointer = 0) noexcept
		{
			const size_type alignment = static_cast<size_type>( Align );
			void* ptr = detail::allocate_aligned_memory(alignment , n * sizeof(T));
			/*
			if (ptr == nullptr) {
				throw std::bad_alloc();
			}
			*/
			return reinterpret_cast<pointer>(ptr);
		}

		static void deallocate(pointer p, size_type) noexcept { return detail::deallocate_aligned_memory(p); }

		template <class U, class ...Args> static void construct(U* p, Args&&... args)
		{
			::new(reinterpret_cast<void*>(p)) U(std::forward<Args>(args)...);
		}

		static void destroy(pointer p) { p->~T(); }
};


template <typename T, size_t Align>
class aligned_allocator<const T, Align>
{
	public:
		typedef T         value_type;
		typedef const T*  pointer;
		typedef const T*  const_pointer;
		typedef const T&  reference;
		typedef const T&  const_reference;
		typedef size_t    size_type;
		typedef ptrdiff_t difference_type;

		typedef std::true_type propagate_on_container_move_assignment;

		template <class U> struct rebind { typedef aligned_allocator<U, Align> other; };

	public:
		aligned_allocator() noexcept = default;
		template <class U> aligned_allocator(const aligned_allocator<U, Align>&) noexcept {}

		static size_type max_size() noexcept { return (size_type(~0) - size_type(Align)) / sizeof(T); }
		static const_pointer address(const_reference x) noexcept { return std::addressof(x); } 
		static pointer allocate(size_type n, typename aligned_allocator<void, Align>::const_pointer = 0) noexcept
		{
			const size_type alignment = static_cast<size_type>( Align );
			void* ptr = detail::allocate_aligned_memory(alignment , n * sizeof(T));
			/*
			if (ptr == nullptr) {
				throw std::bad_alloc();
			}
			*/
			return reinterpret_cast<pointer>(ptr);
		}

		static void deallocate(pointer p, size_type) noexcept { return detail::deallocate_aligned_memory(p); }

		template <class U, class ...Args> static void construct(U* p, Args&&... args)
		{
			::new(reinterpret_cast<void*>(p)) U(std::forward<Args>(args)...);
		}

		static void destroy(pointer p) { p->~T(); }
};

template <typename T, size_t TAlign, typename U, size_t UAlign>
inline bool operator== (const aligned_allocator<T,TAlign>&, const aligned_allocator<U, UAlign>&) noexcept
{
	return TAlign == UAlign;
}

template <typename T, size_t TAlign, typename U, size_t UAlign>
inline bool operator!= (const aligned_allocator<T,TAlign>&, const aligned_allocator<U, UAlign>&) noexcept
{
	return TAlign != UAlign;
}

<file_sep>#pragma once

template<typename R, uintptr_t align, typename T> constexpr inline R mask_ptr(T * p)
{
	static_assert( align && !(align & (align-1)), "power of 2" );
	uintptr_t const aux = reinterpret_cast<uintptr_t>(p) & ~(align-1);
	return reinterpret_cast<R>(aux);
}

template<typename T> constexpr inline bool is_power_of_two(T n)
{
	return (n > 0) & ( 0 == ( n & (n-1) ));
}

