My deque-replaement

Discussion:

My deque-replaement

(too old to reply)

Bonita Montero

2024-09-20 13:18:22 UTC

Just a ring-buffer with functional access:

#pragma once
#include <utility>
#include <cassert>
#include <memory>
#include <span>
#include "invoke_on_destruct.h"
#include "nui.h"

#if defined(__llvm__)
#pragma clang diagnostic push
#pragma clang diagnostic ignored "-Wparentheses"
#pragma clang diagnostic ignored "-Wunqualified-std-cast-call"
#endif

template<typename T, typename Alloc = std::allocator<T>>
struct ring_deque
{
ring_deque( ptrdiff_t capacity = 0, Alloc const &alloc = Alloc() );
~ring_deque();
ring_deque( ring_deque<T, Alloc> const &other );
ring_deque( ring_deque<T, Alloc> &&other ) noexcept;
ring_deque<T, Alloc> &operator =( ring_deque<T, Alloc> const &other );
ring_deque<T, Alloc> &operator =( ring_deque<T, Alloc> &&other ) noexcept;
template<bool Forward, typename Consumer>
void scan( Consumer consumer )
requires requires( T &value ) { { consumer( value ) }; };
template<bool Forward, typename Consumer>
void scan( Consumer consumer ) const
requires requires( T const &value ) { { consumer( value ) }; };
T &front() noexcept;
T const &front() const noexcept;
T &back() noexcept;
T const &back() const noexcept;
template<bool Forward, typename Consumer>
size_t consume( Consumer consumer )
requires requires( T &value ) { { consumer( value ) } ->
std::same_as<int>; };
template<bool Back, typename ... Args>
T &emplace( Args &&... args )
requires std::is_constructible_v<T, Args ...>;
void pop_back() noexcept;
void pop_front() noexcept;
void pop_n( ptrdiff_t n ) noexcept;
void shrink_to_fit();
bool empty() const noexcept;
size_t size() const noexcept;
size_t capacity() const noexcept;
void clear();
T &operator []( ptrdiff_t i ) noexcept;
T const &operator []( ptrdiff_t i ) const noexcept;
void reserve( ptrdiff_t capacity );
private:
using span_t = std::span<T>;
span_t allocRing( size_t capacity );
void freeRing( span_t sp );
template<bool Forward, typename Consumer>
void scanInternal( Consumer consumer );
template<bool Forward, typename Consumer>
void scanInternal( span_t::iterator &it, Consumer consumer );
void grow();
void reCap( ptrdiff_t capacity );
static size_t normCap( ptrdiff_t capacity );
using alloc_t = Alloc;
NO_UNIQUE_ADDRESS alloc_t m_alloc;
span_t m_ring;
span_t::iterator m_front, m_back;
size_t m_n;
};

template<typename T, typename Alloc>
ring_deque<T, Alloc>::ring_deque( ptrdiff_t capacity, Alloc const &alloc ) :
m_alloc( alloc ),
m_ring( allocRing( normCap( capacity ) ) ),
m_front( m_ring.begin() ),
m_back( m_ring.begin() ),
m_n( 0 )
{
}

template<typename T, typename Alloc>
ring_deque<T, Alloc>::~ring_deque()
{
consume<true>( [&]( T & ) -> int { return 1; } );
freeRing( m_ring );
}

template<typename T, typename Alloc>
ring_deque<T, Alloc>::ring_deque( ring_deque<T, Alloc> const &other ) :
ring_deque( other.m_n, other.m_alloc )
{
invoke_on_destruct reset( [&] { this->~ring_deque(); } );
other.scanInternal<true>( [&]( T const &value ) { emplace_back( value
); return true; } );
reset.disable();
}

template<typename T, typename Alloc>
ring_deque<T, Alloc>::ring_deque( ring_deque<T, Alloc> &&other ) noexcept :
m_alloc( other.m_alloc ),
m_ring( other.m_ring ),
m_front( other.m_front ),
m_back( other.m_back ),
m_n( other.m_n )
{
other.m_ring = span_t();
other.m_n = 0;
#if !defined(NDEBUG)
other.m_front = span_t().begin();
other.m_back = span_t().begin();
#endif
}

template<typename T, typename Alloc>
ring_deque<T, Alloc> &ring_deque<T, Alloc>::operator =( ring_deque<T,
Alloc> const &other )
{
clear();
reserve( other.size() );
other.scanInternal<true>( [&]( T const &value ) { emplace_back( value
); return true; } );
return *this;
}

template<typename T, typename Alloc>
ring_deque<T, Alloc> &ring_deque<T, Alloc>::operator =( ring_deque<T,
Alloc> &&other ) noexcept
{
freeRing( m_ring );
m_alloc = other.m_alloc;
m_ring = other.m_ring;
m_front = other.m_front;
m_back = other.m_back;
m_n = other.m_n;
other.m_ring = span_t();
other.m_n = 0;
#if !defined(NDEBUG)
other.m_front = span_t().begin();
other.m_back = span_t().begin();
#endif
return *this;
}

template<typename T, typename Alloc>
template<bool Forward, typename Consumer>
inline void ring_deque<T, Alloc>::scan( Consumer consumer )
requires requires( T &value ) { { consumer( value ) }; }
{
using namespace std;
scanInternal<Forward>( [&]( T &value )
{
bool ret = true;
if constexpr( requires() { { consumer( value ) } ->
convertible_to<bool>; } )
ret = consumer( value );
else
consumer( value );
return ret;
} );
}

template<typename T, typename Alloc>
template<bool Forward, typename Consumer>
inline void ring_deque<T, Alloc>::scan( Consumer consumer ) const
requires requires( T const &value ) { { consumer( value ) }; }
{
const_cast<ring_deque<T, Alloc> *>(this)->scan<Forward>( [&]( T &value
) { return consumer( value ); } );
}

template<typename T, typename Alloc>
inline T &ring_deque<T, Alloc>::front() noexcept
{
assert(m_n);
return *m_front;
}

template<typename T, typename Alloc>
inline T const &ring_deque<T, Alloc>::front() const noexcept
{
assert(m_n);
return *m_front;
}

template<typename T, typename Alloc>
inline T &ring_deque<T, Alloc>::back() noexcept
{
assert(m_n);
return m_back[-1];
}

template<typename T, typename Alloc>
inline T const &ring_deque<T, Alloc>::back() const noexcept
{
assert(m_n);
return m_back[-1];
}

template<typename T, typename Alloc>
template<bool Forward, typename Consumer>
inline size_t ring_deque<T, Alloc>::consume( Consumer consumer )
requires requires( T &value ) { { consumer( value ) } ->
std::same_as<int>; }
{
size_t nInitial = m_n;
typename span_t::iterator it = Forward ? m_front : m_back;
invoke_on_destruct adjust( [&] { (Forward ? m_front : m_back) = it; } );
scanInternal<Forward>( it, [&]( T &value ) -> bool
{
int cont = consumer( value );
if( cont >= 0 ) [[likely]]
{
value.~T();
--m_n;
}
return cont > 0;
} );
return nInitial - m_n;
}

template<typename T, typename Alloc>
template<bool Back, typename ... Args>
T &ring_deque<T, Alloc>::emplace( Args &&... args )
requires std::is_constructible_v<T, Args ...>
{
using namespace std;
assert(m_ring.size() >= m_n);
if( m_n == m_ring.size() ) [[unlikely]]
grow();
auto next = Back ? m_back : m_front;
if( next == (Back ? m_ring.end() : m_ring.begin()) ) [[unlikely]]
next = Back ? m_ring.begin() : m_ring.end();
next -= !Back;
new( (void *)&*next ) T( forward<Args>( args ) ... );
next += Back;
(Back ? m_back : m_front) = next;
++m_n;
return *(Back ? m_back - 1 : m_front);
}

template<typename T, typename Alloc>
inline void ring_deque<T, Alloc>::pop_back() noexcept
{
assert(m_n);
(*--m_back).~T();
if( m_back == m_ring.begin() ) [[unlikely]]
m_back = m_ring.end();
--m_n;
}

template<typename T, typename Alloc>
inline void ring_deque<T, Alloc>::pop_front() noexcept
{
assert(m_n);
(*m_front++).~T();
if( m_front == m_ring.end() ) [[unlikely]]
m_front = m_ring.begin();
--m_n;
}

template<typename T, typename Alloc>
void ring_deque<T, Alloc>::pop_n( ptrdiff_t n ) noexcept
{
if( n > 0 )
{
assert(m_n >= (size_t)n);
size_t dest = m_n - n;
consume<true>( [&]( T &value ) -> int { return --m_n != dest; } );
}
else if( n < 0 )
{
assert(m_n >= (size_t)-n);
size_t dest = m_n - -n;
consume<false>( [&]( T &value ) -> int { return --m_n != dest; } );
}
}

template<typename T, typename Alloc>
inline void ring_deque<T, Alloc>::shrink_to_fit()
{
reCap( m_n );
}

template<typename T, typename Alloc>
inline bool ring_deque<T, Alloc>::empty() const noexcept
{
return !size();
}

template<typename T, typename Alloc>
inline size_t ring_deque<T, Alloc>::size() const noexcept
{
return m_n;
}

template<typename T, typename Alloc>
inline size_t ring_deque<T, Alloc>::capacity() const noexcept
{
return m_ring.size();
}

template<typename T, typename Alloc>
inline void ring_deque<T, Alloc>::clear()
{
pop_n( m_n );
}

template<typename T, typename Alloc>
T &ring_deque<T, Alloc>::operator []( ptrdiff_t i ) noexcept
{
using namespace std;
if( i >= 0 )
{
assert((size_t)i < m_n);
ptrdiff_t headRun = m_ring.end() - m_front;
if( i < headRun )
return m_front[i];
else
return m_ring.begin()[i - headRun];
}
else
{
assert((size_t)-i <= m_n);
ptrdiff_t tailRun = m_ring.begin() - m_back;
if( i >= tailRun )
return m_back[i];
else
return m_ring.end()[i - tailRun];
}
}

template<typename T, typename Alloc>
inline T const &ring_deque<T, Alloc>::operator []( ptrdiff_t i ) const
noexcept
{
return (*const_cast<ring_deque<T, Alloc> *>(this))[i];
}

template<typename T, typename Alloc>
inline void ring_deque<T, Alloc>::reserve( ptrdiff_t capacity )
{
reCap( capacity );
}

template<typename T, typename Alloc>
template<bool Forward, typename Consumer>
inline void ring_deque<T, Alloc>::scanInternal( Consumer consumer )
{
typename span_t::iterator it;
scanInternal<Forward>( it, consumer );
}

template<typename T, typename Alloc>
template<bool Forward, typename Consumer>
inline void ring_deque<T, Alloc>::scanInternal( span_t::iterator &it,
Consumer consumer )
{
using namespace std;
it = Forward ? m_front : m_back;
for( size_t n = m_n; n; --n )
{
if( !consumer( it[-(ptrdiff_t)!Forward] ) ) [[unlikely]]
break;
it = it + (Forward - !Forward);
if( it == (Forward ? m_ring.end() : m_ring.begin()) ) [[unlikely]]
it = Forward ? m_ring.begin() : m_ring.end();
}
}

template<typename T, typename Alloc>
inline void ring_deque<T, Alloc>::grow()
{
size_t nBefore = m_ring.size();
reCap( 2 * nBefore + (size_t)!nBefore );
}

template<typename T, typename Alloc>
void ring_deque<T, Alloc>::reCap( ptrdiff_t capacity )
{
using namespace std;
size_t n = normCap( capacity );;
if( n <= m_n )
return;
span_t ring( allocRing( n ) );
size_t nElements = m_n;
invoke_on_destruct finalize( [&]
{
m_n = nElements;
freeRing( ring );
} );
auto it = ring.begin();
invoke_on_destruct moveBack( [&]
{
while( it != ring.begin() )
{
if constexpr( is_move_constructible_v<T> )
emplace<false>( move( *--it ) );
(*it).~T();
}
} );
if constexpr( is_move_constructible_v<T> )
consume<true>( [&]( T &value )
{
new( (void *)&*it ) T( move( value ) );
++it;
return 1;
} );
else
scan<true>( [&]( T &value )
{
new( (void *)&*it ) T( move( value ) );
++it;
return true;
} );
moveBack.disable();
swap( m_ring, ring );
m_front = m_ring.begin();
m_back = it;
}

template<typename T, typename Alloc>
inline size_t ring_deque<T, Alloc>::normCap( ptrdiff_t capacity )
{
if( capacity < 0 ) [[unlikely]]
capacity = (size_t)-capacity / sizeof(T);
return capacity;
}

template<typename T, typename Alloc>
typename ring_deque<T, Alloc>::span_t ring_deque<T, Alloc>::allocRing(
size_t capacity )
{
using namespace std;
if( !capacity )
return span_t();
#if !defined(__cpp_lib_allocate_at_least) && defined(_MSC_VER)
allocation_result<T *, size_t> ar( m_alloc.allocate_at_least( capacity ) );
return span_t( ar.ptr, ar.count );
#else
return span_t( m_alloc.allocate( capacity ), capacity );
#endif
}

template<typename T, typename Alloc>
inline void ring_deque<T, Alloc>::freeRing( span_t sp )
{
if( to_address( sp.begin() ) )
m_alloc.deallocate( sp.data(), sp.size() );
}

#if defined(__llvm__)
#pragma clang diagnostic pop
#endif

M***@dastardlyhq.com

2024-09-20 14:10:14 UTC