Program Listing for File RingDeque.h

↰ Return to documentation for file (ADS/queue/RingDeque.h)

/*--------------------------------------------------------------------------*/
/*---------------------------- File RingDeque.h ----------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

#ifndef __ADS_RingDeque
 #define __ADS_RingDeque
                      /* self-identification: #endif constant */

/*--------------------------------------------------------------------------*/
/*------------------------------ INCLUDES ----------------------------------*/
/*--------------------------------------------------------------------------*/

#include "ADS/Contract.h"

#include <bit>
#include <compare>
#include <cstddef>
#include <cstring>
#include <initializer_list>
#include <iterator>
#include <memory>
#include <new>
#include <type_traits>
#include <utility>

/*--------------------------------------------------------------------------*/
/*--------------------------- NAMESPACE ------------------------------------*/
/*--------------------------------------------------------------------------*/

#if defined( __GNUC__ ) || defined( __clang__ )
 #define ADS_RING_INLINE inline __attribute__(( always_inline ))
 #define ADS_RING_NOINLINE __attribute__(( noinline ))
#elif defined( _MSC_VER )
 #define ADS_RING_INLINE __forceinline
 #define ADS_RING_NOINLINE __declspec( noinline )
#else
 #define ADS_RING_INLINE inline
 #define ADS_RING_NOINLINE
#endif

namespace ADS {

namespace detail {

template< class T , bool Const >
class MaskIterator {
 using Item = std::conditional_t< Const , const T , T >;

 public:
 using iterator_category = std::random_access_iterator_tag;
 using value_type = T;
 using difference_type = std::ptrdiff_t;
 using reference = Item &;
 using pointer = Item *;

 MaskIterator( void ) = default;
 MaskIterator( Item * A , std::size_t head , std::size_t mask ,
               std::size_t i )
  : f_A( A ) , f_head( head ) , f_mask( mask ) , f_i( i ) {}

 template< bool K > requires ( Const && ! K )
 MaskIterator( const MaskIterator< T , K > & o )
  : f_A( o.f_A ) , f_head( o.f_head ) , f_mask( o.f_mask ) , f_i( o.f_i ) {}

 reference operator*( void ) const {
  return( f_A[ ( f_head + f_i ) & f_mask ] );
  }
 pointer operator->( void ) const { return( &**this ); }
 reference operator[]( difference_type k ) const {
  return( f_A[ ( f_head + f_i + std::size_t( k ) ) & f_mask ] );
  }

 MaskIterator & operator++( void ) { ++f_i; return( *this ); }
 MaskIterator & operator--( void ) { --f_i; return( *this ); }
 MaskIterator operator++( int ) { auto t = *this; ++f_i; return( t ); }
 MaskIterator operator--( int ) { auto t = *this; --f_i; return( t ); }
 MaskIterator & operator+=( difference_type k ) {
  f_i += std::size_t( k );
  return( *this );
  }
 MaskIterator & operator-=( difference_type k ) {
  f_i -= std::size_t( k );
  return( *this );
  }
 friend MaskIterator operator+( MaskIterator a , difference_type k ) {
  return( a += k );
  }
 friend MaskIterator operator+( difference_type k , MaskIterator a ) {
  return( a += k );
  }
 friend MaskIterator operator-( MaskIterator a , difference_type k ) {
  return( a -= k );
  }
 friend difference_type operator-( const MaskIterator & a ,
                                   const MaskIterator & b ) {
  return( difference_type( a.f_i - b.f_i ) );
  }
 bool operator==( const MaskIterator & o ) const { return( f_i == o.f_i ); }
 std::strong_ordering operator<=>( const MaskIterator & o ) const {
  return( f_i <=> o.f_i );
  }

 private:
 template< class , bool > friend class MaskIterator;

 Item * f_A = nullptr;
 std::size_t f_head = 0 , f_mask = 0;
 std::size_t f_i = 0;
 };  // end( class MaskIterator )

}  // end( namespace detail )

/*--------------------------------------------------------------------------*/
/*---------------------------- CLASS RingDeque -----------------------------*/
/*--------------------------------------------------------------------------*/

template< class T >
class RingDeque {
/*--------------------------------------------------------------------------*/
 public:
 using value_type = T;
 using size_type = std::size_t;
 using difference_type = std::ptrdiff_t;
 using reference = T &;
 using const_reference = const T &;
 using iterator = detail::MaskIterator< T , false >;
 using const_iterator = detail::MaskIterator< T , true >;
 using reverse_iterator = std::reverse_iterator< iterator >;
 using const_reverse_iterator = std::reverse_iterator< const_iterator >;

 RingDeque( void ) = default;

 RingDeque( std::initializer_list< T > l );

 RingDeque( const RingDeque & o );

 RingDeque( RingDeque && o ) noexcept;

 RingDeque & operator=( RingDeque o ) noexcept;

 ~RingDeque();

 void swap( RingDeque & o ) noexcept;

 [[nodiscard]] bool empty( void ) const { return( f_head == f_tail ); }
 [[nodiscard]] std::size_t size( void ) const { return( f_tail - f_head ); }

 [[nodiscard]] std::size_t capacity( void ) const { return( f_mask + 1 ); }

 void reserve( std::size_t n );

 [[nodiscard]] T & front( void );
 [[nodiscard]] const T & front( void ) const;
 [[nodiscard]] T & back( void );
 [[nodiscard]] const T & back( void ) const;

 [[nodiscard]] T & operator[]( std::size_t i );
 [[nodiscard]] const T & operator[]( std::size_t i ) const;

 ADS_RING_INLINE void push_back( const T & v ) { emplace_back( v ); }
 ADS_RING_INLINE void push_back( T && v ) { emplace_back( std::move( v ) ); }
 ADS_RING_INLINE void push_front( const T & v ) { emplace_front( v ); }
 ADS_RING_INLINE void push_front( T && v ) {
  emplace_front( std::move( v ) );
  }

 template< class ... Args >
 T & emplace_back( Args && ... args );

 template< class ... Args >
 T & emplace_front( Args && ... args );

 void pop_front( void );

 void pop_back( void );

 void clear( void );

 [[nodiscard]] bool operator==( const RingDeque & o ) const;

 [[nodiscard]] iterator begin( void ) {
  return( iterator( f_A , f_head , f_mask , 0 ) );
  }
 [[nodiscard]] iterator end( void ) {
  return( iterator( f_A , f_head , f_mask , size() ) );
  }
 [[nodiscard]] const_iterator begin( void ) const {
  return( const_iterator( f_A , f_head , f_mask , 0 ) );
  }
 [[nodiscard]] const_iterator end( void ) const {
  return( const_iterator( f_A , f_head , f_mask , size() ) );
  }
 [[nodiscard]] const_iterator cbegin( void ) const { return( begin() ); }
 [[nodiscard]] const_iterator cend( void ) const { return( end() ); }
 [[nodiscard]] reverse_iterator rbegin( void ) {
  return( reverse_iterator( end() ) );
  }
 [[nodiscard]] reverse_iterator rend( void ) {
  return( reverse_iterator( begin() ) );
  }
 [[nodiscard]] const_reverse_iterator rbegin( void ) const {
  return( const_reverse_iterator( end() ) );
  }
 [[nodiscard]] const_reverse_iterator rend( void ) const {
  return( const_reverse_iterator( begin() ) );
  }

/*--------------------------------------------------------------------------*/
 private:
 ADS_RING_NOINLINE static T * relocate( T * A , std::size_t m ,
                                        std::size_t h , std::size_t n );

 void grow( void );

 T & growBack( T && v );
 T & growFront( T && v );

 [[nodiscard]] bool fits( void ) const;

 // the front and the back are counters modulo 2^64, apart by the size,
 // so that the insertions at the back and the removals from the front
 // change one each, two chains that do not wait for each other
 using Count = std::size_t;

 T * f_A = nullptr;
 Count f_mask = Count( -1 );
 Count f_head = 0;
 Count f_tail = 0;
 };  // end( class RingDeque )

/*--------------------------------------------------------------------------*/

}  // end( namespace ADS )

/*--------------------------------------------------------------------------*/
/*-------------------------- IMPLEMENTATION --------------------------------*/
/*--------------------------------------------------------------------------*/

#include "ADS/queue/impl/RingDeque.tpp"

/*--------------------------------------------------------------------------*/

#endif  /* RingDeque.h included */

/*--------------------------------------------------------------------------*/
/*-------------------------- End File RingDeque.h --------------------------*/
/*--------------------------------------------------------------------------*/