notification_queue.hpp

#ifndef BLUETOE_NOTIFICATION_QUEUE_HPP
#define BLUETOE_NOTIFICATION_QUEUE_HPP
 
#include <cstdint>
#include <cstdlib>
#include <utility>
#include <cassert>
#include <algorithm>
#include <iterator>
 
namespace bluetoe {
 
    namespace details {
        enum class notification_queue_entry_type {
            empty,
            notification,
            indication
        };
 
        template < typename Size, int C >
        class notification_queue_impl_base;
 
        static constexpr std::size_t no_outstanding_indicaton = ~std::size_t{ 0 };
    }
 
    template < typename Sizes, class Mixin >
    class notification_queue : public Mixin, details::notification_queue_impl_base< Sizes, 0 >
    {
    public:
        using entry_type = details::notification_queue_entry_type;
        template < class ... Args >
        notification_queue( Args... mixin_arguments );
 
        bool queue_notification( std::size_t index );
 
        bool queue_indication( std::size_t index );
 
        void indication_confirmed();
 
        std::pair< details::notification_queue_entry_type, std::size_t > dequeue_indication_or_confirmation();
 
        void clear_indications_and_confirmations();
 
    private:
        using impl = details::notification_queue_impl_base< Sizes, 0 >;
        std::size_t outstanding_confirmation_index_;
    };
 
    // impl
    template < typename Sizes, class Mixin >
    template < class ... Args >
    notification_queue< Sizes, Mixin >::notification_queue( Args... mixin_arguments )
        : Mixin( mixin_arguments... )
        , outstanding_confirmation_index_( details::no_outstanding_indicaton )
    {
    }
 
    template < typename Sizes, class Mixin >
    bool notification_queue< Sizes, Mixin >::queue_notification( std::size_t index )
    {
        return impl::queue_notification( index );
    }
 
    template < typename Sizes, class Mixin >
    bool notification_queue< Sizes, Mixin >::queue_indication( std::size_t index )
    {
        return impl::queue_indication( index );
    }
 
    template < typename Sizes, class Mixin >
    void notification_queue< Sizes, Mixin >::indication_confirmed()
    {
        outstanding_confirmation_index_ = details::no_outstanding_indicaton;
    }
 
    template < typename Sizes, class Mixin >
    std::pair< details::notification_queue_entry_type, std::size_t > notification_queue< Sizes, Mixin >::dequeue_indication_or_confirmation()
    {
        const auto result = impl::dequeue_indication_or_confirmation( 0, outstanding_confirmation_index_ );
 
        return result;
    }
 
    template < typename Sizes, class Mixin >
    void notification_queue< Sizes, Mixin >::clear_indications_and_confirmations()
    {
        outstanding_confirmation_index_ = details::no_outstanding_indicaton;
        impl::clear_indications_and_confirmations();
    }
 
    namespace details
    {
        // C is introduced to make baseclasses with the very same Size not ambiguous
        template < int Size, int C >
        class notification_queue_impl
        {
        public:
            notification_queue_impl()
            {
                clear_indications_and_confirmations();
            }
 
            bool queue_notification( std::size_t index )
            {
                assert( index < Size );
                return add( index, notification_bit );
            }
 
            bool queue_indication( std::size_t index )
            {
                assert( index < Size );
 
                return add( index, indication_bit );
            }
 
            std::pair< notification_queue_entry_type, std::size_t > dequeue_indication_or_confirmation( std::size_t offset, std::size_t& outstanding_confirmation )
            {
                bool ignore_first = true;
 
                // loop over all entries in a circle
                for ( std::size_t i = next_; ignore_first || i != next_; i = ( i + 1 ) % Size )
                {
                    ignore_first = false;
                    auto entry = at( i );
 
                    if ( entry & indication_bit && outstanding_confirmation == no_outstanding_indicaton )
                    {
                        outstanding_confirmation = i + offset;
                        next_ = ( i + 1 ) % Size;
                        remove( i, indication_bit );
                        return { notification_queue_entry_type::indication, i + offset };
                    }
                    else if ( entry & notification_bit )
                    {
                        next_ = ( i + 1 ) % Size;
                        remove( i, notification_bit );
                        return { notification_queue_entry_type::notification, i + offset };
                    }
 
                }
 
                return { notification_queue_entry_type::empty, 0 };
            }
 
            void clear_indications_and_confirmations()
            {
                next_ = 0;
                std::fill( std::begin( queue_ ), std::end( queue_ ), 0 );
            }
 
        private:
            int at( std::size_t index )
            {
                const auto bit_offset  = ( index * bits_per_characteristc ) % 8;
                const auto byte_offset = index * bits_per_characteristc / 8;
                assert( byte_offset < sizeof( queue_ ) / sizeof( queue_[ 0 ] ) );
 
                return ( queue_[ byte_offset ] >> bit_offset ) & 0x03;
            }
 
            bool add( std::size_t index, int bits )
            {
                assert( bits & ( ( 1 << bits_per_characteristc ) -1 ) );
                const auto bit_offset  = ( index * bits_per_characteristc ) % 8;
                const auto byte_offset = index * bits_per_characteristc / 8;
                assert( byte_offset < sizeof( queue_ ) / sizeof( queue_[ 0 ] ) );
 
                const bool result = ( queue_[ byte_offset ] & ( bits << bit_offset ) ) == 0;
                queue_[ byte_offset ] |= bits << bit_offset;
 
                return result;
            }
 
            void remove( std::size_t index, int bits )
            {
                assert( bits & ( ( 1 << bits_per_characteristc ) -1 ) );
                const auto bit_offset  = ( index * bits_per_characteristc ) % 8;
                const auto byte_offset = index * bits_per_characteristc / 8;
                assert( byte_offset < sizeof( queue_ ) / sizeof( queue_[ 0 ] ) );
 
                queue_[ byte_offset ] &= ~( bits << bit_offset );
            }
 
            static constexpr std::size_t bits_per_characteristc = 2;
 
            enum char_bits {
                notification_bit = 0x01,
                indication_bit   = 0x02
            };
 
            std::size_t     next_;
            std::uint8_t    queue_[ ( Size * bits_per_characteristc + 7 ) / 8 ];
        };
 
        template < int C >
        class notification_queue_impl< 1, C >
        {
        public:
            notification_queue_impl()
                : state_( notification_queue_entry_type::empty )
            {
            }
 
            bool queue_notification( std::size_t idx )
            {
                static_cast< void >( idx );
                assert( idx == 0 );
 
                const bool result = state_ == notification_queue_entry_type::empty;
 
                if ( result )
                    state_ = notification_queue_entry_type::notification;
 
                return result;
            }
 
            bool queue_indication( std::size_t idx )
            {
                static_cast< void >( idx );
                assert( idx == 0 );
                const bool result = state_ == notification_queue_entry_type::empty;
 
                if ( result )
                    state_ = notification_queue_entry_type::indication;
 
                return result;
            }
 
            std::pair< notification_queue_entry_type, std::size_t > dequeue_indication_or_confirmation( std::size_t offset, std::size_t& outstanding_confirmation )
            {
                const auto result = state_ == notification_queue_entry_type::notification || ( state_ == notification_queue_entry_type::indication && outstanding_confirmation == details::no_outstanding_indicaton )
                    ? std::pair< notification_queue_entry_type, std::size_t >{ static_cast< notification_queue_entry_type >( state_ ), offset }
                    : std::pair< notification_queue_entry_type, std::size_t >{ notification_queue_entry_type::empty, 0 };
 
                if ( result.first == notification_queue_entry_type::indication )
                    outstanding_confirmation = offset;
 
                if ( result.first != notification_queue_entry_type::empty )
                    state_ = notification_queue_entry_type::empty;
 
                return result;
            }
 
            void clear_indications_and_confirmations()
            {
                state_ = notification_queue_entry_type::empty;
            }
        private:
            notification_queue_entry_type state_;
        };
 
        template < int C >
        class notification_queue_impl_base< std::tuple<>, C >
        {
        public:
            bool queue_notification( std::size_t ) { return false; }
            bool queue_indication( std::size_t ) { return false; }
 
            std::pair< notification_queue_entry_type, std::size_t > dequeue_indication_or_confirmation( std::size_t, std::size_t )
            {
                return { notification_queue_entry_type::empty, 0 };
            }
 
            void clear_indications_and_confirmations() {}
        };
 
        template < int Size, class ...Ts, int C >
        class notification_queue_impl_base< std::tuple< std::integral_constant< int, Size >, Ts... >, C >
            : public notification_queue_impl_base< std::tuple< Ts... >, C + 1 >
            , private notification_queue_impl< Size, C >
        {
        public:
            using base = notification_queue_impl_base< std::tuple< Ts... >, C + 1 >;
            using impl = notification_queue_impl< Size, C >;
 
            bool queue_notification( std::size_t idx )
            {
                return idx < Size
                    ? impl::queue_notification( idx )
                    : base::queue_notification( idx - Size );
            }
 
            bool queue_indication( std::size_t idx )
            {
                return idx < Size
                    ? impl::queue_indication( idx )
                    : base::queue_indication( idx - Size );
            }
 
            std::pair< notification_queue_entry_type, std::size_t > dequeue_indication_or_confirmation( std::size_t offset, std::size_t& outstanding_confirmation )
            {
                auto result = impl::dequeue_indication_or_confirmation( offset, outstanding_confirmation );
 
                if ( result.first != notification_queue_entry_type::empty )
                {
                    return result;
                }
 
                result = base::dequeue_indication_or_confirmation( offset + Size, outstanding_confirmation );
 
                return result;
            }
 
            void clear_indications_and_confirmations()
            {
                impl::clear_indications_and_confirmations();
                base::clear_indications_and_confirmations();
            }
        };
 
    } // namespace details
 
} // namespace bluetoe
 
#endif // include guard