queue.h

Go to the documentation of this file.

//   Copyright 2016-2023 Jean-Francois Poilpret
//
//   Licensed under the Apache License, Version 2.0 (the "License");
//   you may not use this file except in compliance with the License.
//   You may obtain a copy of the License at
//
//       http://www.apache.org/licenses/LICENSE-2.0
//
//   Unless required by applicable law or agreed to in writing, software
//   distributed under the License is distributed on an "AS IS" BASIS,
//   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
//   See the License for the specific language governing permissions and
//   limitations under the License.
 
 
#ifndef QUEUE_HH
#define QUEUE_HH
 
#include "utilities.h"
#include "time.h"
 
namespace containers
{
    template<typename T_, typename TREF_ = const T_&> class Queue
    {
    public:
        Queue(const Queue&) = delete;
        Queue& operator=(const Queue&) = delete;
        
        using T = T_;
 
        using TREF = TREF_;
 
        template<uint8_t SIZE> explicit Queue(T (&buffer)[SIZE], bool locked = false)
        : buffer_{buffer}, size_{SIZE}, locked_{locked} {}
 
        void lock()
        {
            locked_ = true;
        }
 
        void unlock()
        {
            locked_ = false;
        }
 
        bool is_locked() const
        {
            return locked_;
        }
 
        bool push_(TREF item);
 
        bool pull_(T& item);
 
        bool peek_(T& item) const;
 
        uint8_t peek_(T* buffer, uint8_t size) const;
 
        template<uint8_t SIZE> uint8_t peek_(T (&buffer)[SIZE]) const;
 
        uint8_t size() const
        {
            return size_ - 1;
        }
 
        bool empty_() const
        {
            return tail_ == head_;
        }
 
        bool full_() const
        {
            return (tail_ + 1) == (head_ ? head_ : size_);
        }
 
        uint8_t items_() const
        {
            // - must be 0 when head_ = tail_
            // - must be size_ - 1 max, when tail_ = head_ - 1
            return tail_ - head_ + (tail_ >= head_ ? 0 : size_);
        }
 
        uint8_t free_() const
        {
            // - must be 0 when tail_ = head_ - 1
            // - must be size_ - 1, when head_ == tail_
            // We simply return size_ - 1 - items_() but we optimize it a bit
            return head_ - tail_ - 1 + (tail_ >= head_ ? size_ : 0);
        }
 
        void clear_()
        {
            head_ = tail_ = 0;
        }
 
        bool push(TREF item)
        {
            synchronized return push_(item);
        }
 
        bool pull(T& item)
        {
            synchronized return pull_(item);
        }
 
        bool peek(T& item) const
        {
            synchronized return peek_(item);
        }
 
        uint8_t peek(T* buffer, uint8_t size) const
        {
            synchronized return peek_(buffer, size);
        }
 
        template<uint8_t SIZE> uint8_t peek(T (&buffer)[SIZE]) const
        {
            synchronized return peek_(buffer);
        }
 
        bool empty() const
        {
            synchronized return empty_();
        }
 
        uint8_t items() const
        {
            synchronized return items_();
        }
 
        uint8_t free() const
        {
            synchronized return free_();
        }
 
        bool full() const
        {
            synchronized return full_();
        }
 
        void clear()
        {
            synchronized clear_();
        }
 
    private:
        T* const buffer_;
        const uint8_t size_;
        bool locked_;
        volatile uint8_t head_ = 0;
        volatile uint8_t tail_ = 0;
    };
 
    template<typename T, typename TREF> bool Queue<T, TREF>::peek_(T& item) const
    {
        if (empty_()) return false;
        item = buffer_[head_];
        return true;
    }
 
    template<typename T, typename TREF> uint8_t Queue<T, TREF>::peek_(T* buffer, uint8_t size) const
    {
        size = (size <= items_()) ? size : items_();
        if (size)
        {
            // Split peek in 2 parts if needed
            if (head_ < tail_)
            {
                const T* source = &buffer_[head_];
                for (uint8_t i = 0; i < size; ++i) *buffer++ = *source++;
            }
            else
            {
                uint8_t part_size = size_ - head_;
                if (part_size > size) part_size = size;
                const T* source = &buffer_[head_];
                for (uint8_t i = 0; i < part_size; ++i) *buffer++ = *source++;
 
                if (size > part_size)
                {
                    part_size = size - part_size;
                    source = buffer_;
                    for (uint8_t i = 0; i < part_size; ++i) *buffer++ = *source++;
                }
            }
        }
        return size;
    }
 
    template<typename T, typename TREF> template<uint8_t SIZE> uint8_t Queue<T, TREF>::peek_(T (&buffer)[SIZE]) const
    {
        return peek_(&buffer[0], SIZE);
    }
 
    template<typename T, typename TREF> bool Queue<T, TREF>::push_(TREF item)
    {
        if (locked_ || full_()) return false;
        buffer_[tail_] = item;
        ++tail_;
        if (tail_ == size_) tail_ = 0;
        return true;
    }
 
    template<typename T, typename TREF> bool Queue<T, TREF>::pull_(T& item)
    {
        if (empty_()) return false;
        item = buffer_[head_];
        ++head_;
        if (head_ == size_) head_ = 0;
        return true;
    }
 
    template<typename T, typename TREF> T pull(Queue<T, TREF>& queue)
    {
        T item;
        while (!queue.pull(item)) time::yield();
        return item;
    }
 
    template<typename T, typename TREF> T peek(Queue<T, TREF>& queue)
    {
        T item;
        while (!queue.peek(item)) time::yield();
        return item;
    }
}
 
#endif /* QUEUE_HH */