circular_queue.hh

Go to the documentation of this file.

/*
 * Copyright (c) 2017-2018 ARM Limited
 * All rights reserved
 *
 * The license below extends only to copyright in the software and shall
 * not be construed as granting a license to any other intellectual
 * property including but not limited to intellectual property relating
 * to a hardware implementation of the functionality of the software
 * licensed hereunder.  You may use the software subject to the license
 * terms below provided that you ensure that this notice is replicated
 * unmodified and in its entirety in all distributions of the software,
 * modified or unmodified, in source code or in binary form.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met: redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer;
 * redistributions in binary form must reproduce the above copyright
 * notice, this list of conditions and the following disclaimer in the
 * documentation and/or other materials provided with the distribution;
 * neither the name of the copyright holders nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

#ifndef __BASE_CIRCULAR_QUEUE_HH__
#define __BASE_CIRCULAR_QUEUE_HH__

#include <cassert>
#include <cstddef>
#include <cstdint>
#include <iterator>
#include <type_traits>
#include <vector>

template <typename T>
class CircularQueue : private std::vector<T>
{
  protected:
    using Base = std::vector<T>;
    using typename Base::reference;
    using typename Base::const_reference;
    const uint32_t _capacity;
    uint32_t _head;
    uint32_t _tail;
    uint32_t _empty;

    uint32_t _round;

    static uint32_t
    moduloAdd(uint32_t op1, uint32_t op2, uint32_t size)
    {
        return (op1 + op2) % size;
    }

    static uint32_t
    moduloSub(uint32_t op1, uint32_t op2, uint32_t size)
    {
        int32_t ret = sub(op1, op2, size);
        return ret >= 0 ? ret : ret + size;
    }

    static int32_t
    sub(uint32_t op1, uint32_t op2, uint32_t size)
    {
        if (op1 > op2)
            return (op1 - op2) % size;
        else
            return -((op2 - op1) % size);
    }

    void increase(uint32_t& v, size_t delta = 1)
    {
        v = moduloAdd(v, delta, _capacity);
    }

    void decrease(uint32_t& v)
    {
        v = (v ? v : _capacity) - 1;
    }

  public:
    struct iterator {
        CircularQueue* _cq;
        uint32_t _idx;
        uint32_t _round;

      public:
        iterator(CircularQueue* cq, uint32_t idx, uint32_t round)
            : _cq(cq), _idx(idx), _round(round) {}

        using value_type = T;
        using difference_type = std::ptrdiff_t;
        using reference = value_type&;
        using const_reference = const value_type&;
        using pointer = value_type*;
        using const_pointer = const value_type*;
        using iterator_category = std::random_access_iterator_tag;

        static_assert(std::is_same<reference, T&>::value,
                "reference type is not assignable as required");

        iterator() : _cq(nullptr), _idx(0), _round(0) { }

        iterator(const iterator& it)
            : _cq(it._cq), _idx(it._idx), _round(it._round) {}

        iterator&
        operator=(const iterator& it)
        {
            _cq = it._cq;
            _idx = it._idx;
            _round = it._round;
            return *this;
        }

        ~iterator() { _cq = nullptr; _idx = 0; _round = 0; }

        bool
        dereferenceable() const
        {
            return _cq != nullptr && _cq->isValidIdx(_idx, _round);
        }

        bool operator==(const iterator& that) const
        {
            return _cq == that._cq && _idx == that._idx &&
                _round == that._round;
        }

        bool operator!=(const iterator& that)
        {
            return !(*this == that);
        }

        reference operator*()
        {
            /* this has to be dereferenceable. */
            return (*_cq)[_idx];
        }

        const_reference operator*() const
        {
            /* this has to be dereferenceable. */
            return (*_cq)[_idx];
        }

        pointer operator->()
        {
            return &((*_cq)[_idx]);
        }

        const_pointer operator->() const
        {
            return &((*_cq)[_idx]);
        }

        iterator& operator++()
        {
            /* this has to be dereferenceable. */
            _cq->increase(_idx);
            if (_idx == 0)
                ++_round;
            return *this;
        }

        iterator
        operator++(int)
        {
            iterator t = *this;
            ++*this;
            return t;
        }

      private:
        bool
        decrementable() const
        {
            return _cq && !(_idx == _cq->head() &&
                            (_cq->empty() ||
                             (_idx == 0 && _round != _cq->_round + 1) ||
                             (_idx !=0 && _round != _cq->_round)));
        }

      public:
        iterator& operator--()
        {
            /* this has to be decrementable. */
            assert(decrementable());
            if (_idx == 0)
                --_round;
            _cq->decrease(_idx);
            return *this;
        }

        iterator operator--(int ) { iterator t = *this; --*this; return t; }

        iterator& operator+=(const difference_type& t)
        {
            assert(_cq);
            _round += (t + _idx) / _cq->capacity();
            _idx = _cq->moduloAdd(_idx, t);
            return *this;
        }

        iterator& operator-=(const difference_type& t)
        {
            assert(_cq);

            /* C does not do euclidean division, so we have to adjust */
            if (t >= 0) {
                _round += (-t + _idx) / _cq->capacity();
                _idx = _cq->moduloSub(_idx, t);
            } else {
                *this += -t;
            }
            return *this;
        }

        iterator operator+(const difference_type& t)
        {
            iterator ret(*this);
            return ret += t;
        }

        friend iterator operator+(const difference_type& t, iterator& it)
        {
            iterator ret = it;
            return ret += t;
        }

        iterator operator-(const difference_type& t)
        {
            iterator ret(*this);
            return ret -= t;
        }

        friend iterator operator-(const difference_type& t, iterator& it)
        {
            iterator ret = it;
            return ret -= t;
        }

        difference_type operator-(const iterator& that)
        {
            /* If a is already at the end, we can safely return 0. */
            auto ret = _cq->sub(this->_idx, that._idx, _cq->capacity());

            if (this->_round != that._round) {
                ret += ((this->_round - that._round) * _cq->capacity());
            }
            return ret;
        }

        template<typename Idx>
        typename std::enable_if<std::is_integral<Idx>::value,reference>::type
        operator[](const Idx& index) { return *(*this + index); }

        bool
        operator<(const iterator& that) const
        {
            assert(_cq && that._cq == _cq);
            return (this->_round < that._round) ||
                (this->_round == that._round && _idx < that._idx);
        }

        bool
        operator>(const iterator& that) const
        { return !(*this <= that); }

        bool operator>=(const iterator& that) const
        { return !(*this < that); }

        bool operator<=(const iterator& that) const
        { return !(that < *this); }

        size_t idx() const { return _idx; }
    };

  public:
    using Base::operator[];

    explicit CircularQueue(uint32_t size = 0)
        : _capacity(size), _head(1), _tail(0), _empty(true), _round(0)
    {
        Base::resize(size);
    }

    void flush()
    {
        _head = 1;
        _round = 0;
        _tail = 0;
        _empty = true;
    }

    bool isValidIdx(size_t idx) const
    {
        /* An index is invalid if:
         *   - The queue is empty.
         *   (6,T,3,2): |-|-|-]|[-|-|x|
         *   - head is small than tail and:
         *       - It is greater than both head and tail.
         *       (6,F,1,3): |-|[o|o|o]|-|x|
         *       - It is less than both head and tail.
         *       (6,F,1,3): |x|[o|o|o]|-|-|
         *   - It is greater than the tail and not than the head.
         *   (6,F,4,1): |o|o]|-|x|[o|o|
         */
        return !(_empty || (
            (_head < _tail) && (
                (_head < idx && _tail < idx) ||
                (_head > idx && _tail > idx)
            )) || (_tail < idx && idx < _head));
    }

    bool isValidIdx(size_t idx, uint32_t round) const
    {
        /* An index is valid if:
         *   - The queue is not empty.
         *      - round == R and
         *          - index <= tail (if index > tail, that would be PTE)
         *          - Either:
         *             - head <= index
         *               (6,F,1,3,R): |-|[o|(*,r)|o]|-|-|
         *             - head > tail
         *               (6,F,5,3,R): |o|o|(*,r)|o]|-|[o|
         *            The remaining case means the the iterator is BTB:
         *               (6,F,3,4,R): |-|-|(x,r)|[o|o]|-|
         *      - round + 1 == R and:
         *          - index > tail. If index <= tail, that would be BTB:
         *               (6,F,2,3,r):   | -|- |[(*,r)|o]|-|-|
         *               (6,F,0,1,r+1): |[o|o]| (x,r)|- |-|-|
         *               (6,F,0,3,r+1): |[o|o | (*,r)|o]|-|-|
         *          - index >= head. If index < head, that would be BTB:
         *               (6,F,5,2,R): |o|o]|-|-|(x,r)|[o|
         *          - head > tail. If head <= tail, that would be BTB:
         *               (6,F,3,4,R): |[o|o]|(x,r)|-|-|-|
         *      Other values of the round meand that the index is PTE or BTB
         */
        return (!_empty && (
                    (round == _round && idx <= _tail && (
                        _head <= idx || _head > _tail)) ||
                    (round + 1 == _round &&
                     idx > _tail &&
                     idx >= _head &&
                     _head > _tail)
                    ));
    }

    reference front() { return (*this)[_head]; }
    reference back() { return (*this)[_tail]; }
    uint32_t head() const { return _head; }
    uint32_t tail() const { return _tail; }
    size_t capacity() const { return _capacity; }

    uint32_t size() const
    {
        if (_empty)
            return 0;
        else if (_head <= _tail)
            return _tail - _head + 1;
        else
            return _capacity - _head + _tail + 1;
    }

    uint32_t moduloAdd(uint32_t s1, uint32_t s2) const
    {
        return moduloAdd(s1, s2, _capacity);
    }

    uint32_t moduloSub(uint32_t s1, uint32_t s2) const
    {
        return moduloSub(s1, s2, _capacity);
    }

    void pop_front(size_t num_elem = 1)
    {
        if (num_elem == 0) return;
        auto hIt = begin();
        hIt += num_elem;
        assert(hIt <= end());
        _empty = hIt == end();
        _head = hIt._idx;
    }

    void pop_back()
    {
        assert (!_empty);
        _empty = _head == _tail;
        if (_tail == 0)
            --_round;
        decrease(_tail);
    }

    void push_back(typename Base::value_type val)
    {
        advance_tail();
        (*this)[_tail] = val;
    }

    void advance_tail()
    {
        increase(_tail);
        if (_tail == 0)
            ++_round;

        if (_tail == _head && !_empty)
            increase(_head);

        _empty = false;
    }

    void advance_tail(uint32_t len)
    {
        for (auto idx = 0; idx < len; idx++)
            advance_tail();
    }

    bool empty() const { return _empty; }

    bool full() const
    {
        return !_empty &&
            (_tail + 1 == _head || (_tail + 1 == _capacity && _head == 0));
    }

    iterator begin()
    {
        if (_empty)
            return end();
        else if (_head > _tail)
            return iterator(this, _head, _round - 1);
        else
            return iterator(this, _head, _round);
    }

    /* TODO: This should return a const_iterator. */
    iterator begin() const
    {
        if (_empty)
            return end();
        else if (_head > _tail)
            return iterator(const_cast<CircularQueue*>(this), _head,
                    _round - 1);
        else
            return iterator(const_cast<CircularQueue*>(this), _head,
                    _round);
    }

    iterator end()
    {
        auto poi = moduloAdd(_tail, 1);
        auto round = _round;
        if (poi == 0)
            ++round;
        return iterator(this, poi, round);
    }

    iterator end() const
    {
        auto poi = moduloAdd(_tail, 1);
        auto round = _round;
        if (poi == 0)
            ++round;
        return iterator(const_cast<CircularQueue*>(this), poi, round);
    }

    iterator getIterator(size_t idx)
    {
        assert(isValidIdx(idx) || moduloAdd(_tail, 1) == idx);
        if (_empty)
            return end();

        uint32_t round = _round;
        if (idx > _tail) {
            if (idx >= _head && _head > _tail) {
                round -= 1;
            }
        } else if (idx < _head && _tail + 1 == _capacity) {
            round += 1;
        }
        return iterator(this, idx, round);
    }
};

#endif /* __BASE_CIRCULARQUEUE_HH__ */