Queue.hpp

Go to the documentation of this file.

// <Queue.hpp> -*- C++ -*-
 
 
#pragma once
 
#include <cinttypes>
#include <vector>
#include <type_traits>
 
#include "sparta/utils/SpartaAssert.hpp"
#include "sparta/ports/Port.hpp"
#include "sparta/statistics/CycleHistogram.hpp"
#include "sparta/statistics/StatisticSet.hpp"
#include "sparta/collection/IterableCollector.hpp"
#include "sparta/statistics/InstrumentationNode.hpp"
#include "sparta/utils/IteratorTraits.hpp"
 
namespace sparta
{
    template <class DataT>
    class Queue
    {
    public:
 
        using value_type = DataT;
 
        using QueueType = Queue<value_type>;
 
        // Typedef for size_type
        using size_type = uint32_t;
 
    private:
 
        //
        // How the Queue works internally.
        //
        // The queue will create storage for the next pow2 elements
        // for efficiency.  So, if the user creates a Queue of 12
        // elements, the internal storage will be 16.
        //
        // There are two pointers, each represents the _physical_
        // location in the array, not the logical.
        //
        //   current_write_idx_ -- the insertion point used by push()
        //   current_head_idx_  -- the top of the queue, used by pop()
        //
        // There is one dynamically created array for the data:
        //
        //   queue_data_ -- equal to capacity ^ next pow2
        //
        // At init time, current_head_idx_ == current_write_idx_.  As
        // elements are push()ed, the new objects is added and
        // current_write_idx_ is incremented.  When current_write_idx_
        // surpasses the end of the array, it will be wrapped to the
        // beginning -- as long as there are invalidations.  The
        // "distance" between current_write_idx_ and current_head_idx_
        // is always <= the capacity() of the queue.  The distance
        // between the indexes represents the size().
        //
        // Valid iterators are given an index into the queue, which is
        // used to retrieve the data at the given location in the
        // queue.  As the iterator is incremented, it re-validates the
        // index given, so it will always fall into one of two
        // locations: the next valid data element, or end()
        //
        // Reading/accessing the Queue from a modeler's POV is a
        // little different.  The modeler can index into the queue
        // starting from 0 -> size().  The Queue will need to
        // "convert" this logical index to the physical one.  For
        // example, 0 might not be the data at index 0 of the array,
        // but instead, index 6:
        //
        //          L  P
        //          2  0  x
        //          3  1  x
        //          4  2  x
        //          5  3    <- write idx
        //          6  4
        //          7  5
        //          0  6  x <- head
        //          1  7  x
        //
        // Another layout of queue during runtime:
        //
        //          L  P
        //          7  0
        //          0  1  x <- head
        //          1  2  x
        //          2  3  x
        //          3  4  x
        //          4  5  x
        //          5  6  x
        //          6  7    <- write idx
 
        constexpr uint32_t nextPowerOfTwo_(uint32_t val) const
        {
            if(val < 2) { return 1ull; }
            return 1ull << ((sizeof(uint64_t) * 8) - __builtin_clzll(val - 1ull));
        }
 
        uint32_t rollPhysicalIndex_(const uint32_t phys_idx) const {
            return (vector_size_ - 1) & (phys_idx);
        }
 
        uint32_t getPhysicalIndex_(const uint32_t logical_idx) const {
            return rollPhysicalIndex_(logical_idx + current_head_idx_);
        }
 
        uint32_t incrementIndexValue_(const uint32_t val) const {
            return rollPhysicalIndex_(val + 1);
        }
 
        uint32_t decrementIndexValue_(const uint32_t val) const {
            return rollPhysicalIndex_(val - 1);
        }
 
        struct QueueData {
            template<class DataTRef>
            QueueData(DataTRef && dat, uint64_t in_obj_id) :
                data(std::forward<DataTRef>(dat)),
                obj_id(in_obj_id)
            {}
 
            DataT data;
            uint64_t obj_id = 0;
        };
 
        const value_type & readPhysical_(const uint32_t phys_idx) const
        {
            return queue_data_[phys_idx].data;
        }
 
        value_type & accessPhysical_(const uint32_t phys_idx)
        {
            return queue_data_[phys_idx].data;
        }
 
        uint32_t physicalToLogical_(const uint32_t physical_idx) const {
            if(physical_idx == invalid_index_) { return invalid_index_; }
            // Neat trick from the previous author...
            return rollPhysicalIndex_(physical_idx - current_head_idx_);
        }
 
        bool isValidPhysical_(const uint32_t physical_idx) const
        {
            const auto log_idx = physicalToLogical_(physical_idx);
            return (log_idx < size());
        }
 
    public:
 
        template <bool is_const_iterator = true>
        class QueueIterator : public utils::IteratorTraits<std::bidirectional_iterator_tag, value_type>
        {
        private:
            using DataReferenceType = typename std::conditional<is_const_iterator,
                                                                const value_type &, value_type &>::type;
            using QueuePointerType =  typename std::conditional<is_const_iterator,
                                                                const QueueType * , QueueType * >::type;
 
            QueueIterator(QueuePointerType q, uint32_t physical_index, uint32_t obj_id) :
                attached_queue_(q),
                physical_index_(physical_index),
                obj_id_(obj_id)
            { }
 
            friend class Queue<DataT>;
 
            bool isAttached_() const { return nullptr != attached_queue_; }
 
        public:
 
            QueueIterator() = default;
 
            /* Make QueueIterator<true> a friend class of QueueIterator<false>
             * So const iterator can access non-const iterators private members
             */
            friend class QueueIterator<true>;
 
            QueueIterator(const QueueIterator<false> & iter) :
                attached_queue_(iter.attached_queue_),
                physical_index_(iter.physical_index_),
                obj_id_(iter.obj_id_)
            {}
 
            QueueIterator(const QueueIterator<true> & iter) :
                attached_queue_(iter.attached_queue_),
                physical_index_(iter.physical_index_),
                obj_id_(iter.obj_id_)
            {}
 
            bool isValid() const {
                if(nullptr == attached_queue_) { return false; }
                return attached_queue_->determineIteratorValidity_(this);
            }
 
            QueueIterator& operator=(const QueueIterator& rhs) = default;
 
            bool operator<(const QueueIterator& rhs) const
            {
                sparta_assert(attached_queue_ == rhs.attached_queue_,
                              "Cannot compare QueueIterators created by different Queues");
                return getIndex() < rhs.getIndex();
            }
 
            bool operator>(const QueueIterator& rhs) const
            {
                sparta_assert(attached_queue_ == rhs.attached_queue_,
                              "Cannot compare QueueIterators created by different Queues");
                return getIndex() > rhs.getIndex();
            }
 
            bool operator==(const QueueIterator& rhs) const
            {
                sparta_assert(attached_queue_ == rhs.attached_queue_,
                              "Cannot compare QueueIterators created by different Queues");
                return (physical_index_ == rhs.physical_index_) && (obj_id_ == rhs.obj_id_);
            }
 
            bool operator!=(const QueueIterator& rhs) const {
                return !(*this == rhs);
            }
 
            QueueIterator & operator++()
            {
                sparta_assert(isAttached_(), "This is an invalid iterator");
                attached_queue_->incrementIterator_(this);
                return *this;
            }
 
            QueueIterator operator++(int)
            {
                QueueIterator it(*this);
                operator++();
                return it;
            }
 
            QueueIterator & operator--()
            {
                sparta_assert(isAttached_(), "This is an invalid iterator");
                attached_queue_->decrementIterator_(this);
                return *this;
            }
 
            QueueIterator operator-- (int){
                QueueIterator it(*this);
                operator--();
                return it;
            }
 
            DataReferenceType operator* ()
            {
                sparta_assert(isValid(), "This is an invalid iterator");
                return getAccess_(std::integral_constant<bool, is_const_iterator>());
            }
 
            value_type* operator->()
            {
                sparta_assert(isValid(), "This is an invalid iterator");
                return std::addressof(getAccess_(std::integral_constant<bool, is_const_iterator>()));
            }
 
            const value_type* operator->() const
            {
                sparta_assert(isValid(), "This is an invalid iterator");
                return std::addressof(getAccess_(std::integral_constant<bool, is_const_iterator>()));
            }
 
            uint32_t getIndex() const
            {
                sparta_assert(isAttached_(), "This is an invalid iterator");
                return attached_queue_->physicalToLogical_(physical_index_);
            }
 
        private:
 
            QueuePointerType attached_queue_ {nullptr};
            uint32_t physical_index_ = std::numeric_limits<uint32_t>::max();
            uint64_t obj_id_ = 0;
 
            DataReferenceType getAccess_(std::false_type) const {
                return attached_queue_->accessPhysical_(physical_index_);
            }
 
            DataReferenceType getAccess_(std::true_type) const {
                return attached_queue_->readPhysical_(physical_index_);
            }
        };
 
        using iterator = QueueIterator<false> ;
 
        using const_iterator = QueueIterator<true>;
 
        Queue(const std::string & name,
              const uint32_t num_entries,
              const Clock * clk,
              StatisticSet * statset = nullptr,
              InstrumentationNode::visibility_t stat_vis_general = InstrumentationNode::AUTO_VISIBILITY,
              InstrumentationNode::visibility_t stat_vis_detailed= InstrumentationNode::VIS_HIDDEN,
              InstrumentationNode::visibility_t stat_vis_max     = InstrumentationNode::AUTO_VISIBILITY,
              InstrumentationNode::visibility_t stat_vis_avg     = InstrumentationNode::AUTO_VISIBILITY) :
            num_entries_(num_entries),
            vector_size_(nextPowerOfTwo_(num_entries*2)),
            name_(name),
            collector_(nullptr)
        {
 
            if((num_entries > 0) && statset)
            {
                utilization_.reset(new CycleHistogramStandalone(statset, clk,
                                                                name + "_utilization",
                                                                name + " occupancy histogram",
                                                                0, num_entries, 1, 0,
                                                                stat_vis_general,
                                                                stat_vis_detailed,
                                                                stat_vis_max,
                                                                stat_vis_avg));
            }
 
            // Make the queue twice as large and a power of two to
            // allow a complete invalidation followed by a complete
            // population
            queue_data_.reset(static_cast<QueueData *>(malloc(sizeof(QueueData) * vector_size_)));
        }
 
        ~Queue() { clear(); }
 
        Queue(const Queue<value_type> & ) = delete;
 
        Queue &operator=(const Queue<value_type> &) = delete;
 
        const std::string & getName() const {
            return name_;
        }
 
        bool isValid(uint32_t idx) const {
            return (idx < size());
        }
 
        const value_type & read(uint32_t idx) const {
            sparta_assert(isValid(idx), "Cannot read an invalid index");
            return readPhysical_(getPhysicalIndex_(idx));
        }
 
        value_type & access(uint32_t idx) {
            sparta_assert(isValid(idx), name_ << ": Cannot read an invalid index");
            return accessPhysical_(getPhysicalIndex_(idx));
        }
 
        value_type & front() const {
            sparta_assert(size() != 0, name_ << ": Trying to get front() on an empty Queue");
            return queue_data_[current_head_idx_].data;
        }
 
        value_type & back() const {
            sparta_assert(size() != 0, name_ << ": Trying to get back() on an empty Queue");
            uint32_t index = current_write_idx_;
            index = decrementIndexValue_(index);
            return queue_data_[index].data;
        }
 
        uint32_t capacity() const {
            return num_entries_;
        }
 
        size_type size() const {
            return total_valid_;
        }
        size_type numFree() const {
            return (capacity() - total_valid_);
        }
 
        bool empty() const {
            return (total_valid_ == 0);
        }
 
        void clear()
        {
            auto idx = current_head_idx_;
            while (idx != current_write_idx_)
            {
                queue_data_[idx].data.~value_type();
                idx = incrementIndexValue_(idx);
            }
            current_write_idx_ = 0;
            current_head_idx_  = 0;
            total_valid_       = 0;
            updateUtilizationCounters_();
        }
 
        void enableCollection(TreeNode * parent) {
            collector_.reset(new collection::IterableCollector<Queue<value_type> >
                             (parent, name_, this, capacity()));
        }
 
        iterator push(const value_type & dat)
        {
            return pushImpl_(dat);
        }
 
        iterator push(value_type && dat)
        {
            return pushImpl_(std::move(dat));
        }
 
        void pop()
        {
            sparta_assert(total_valid_ != 0, name_ << ": Trying to pop an empty Queue");
 
            // Destruct the element at the head
            queue_data_[current_head_idx_].data.~value_type();
 
            // Our head moves upward
            current_head_idx_ = incrementIndexValue_(current_head_idx_);
 
            // Clean up
            processInvalidation_();
        }
 
        void pop_back()
        {
            sparta_assert(total_valid_ != 0, name_ << ": Trying to pop_back an empty Queue");
 
            // our tail moves upward in the vector now.
            current_write_idx_ = decrementIndexValue_(current_write_idx_);
 
            // Destroy the object at the current write index
            queue_data_[current_write_idx_].data.~value_type();
 
            // Clean up
            processInvalidation_();
        }
 
        iterator begin() {
            if(SPARTA_EXPECT_FALSE(empty())) {
                return end();
            }
            else {
                return iterator(this, current_head_idx_, queue_data_[current_head_idx_].obj_id);
            }
        }
 
        iterator end()  { return iterator(this, invalid_index_, invalid_index_);}
 
        const_iterator begin() const {
            if(SPARTA_EXPECT_FALSE(empty())) {
                return end();
            }
            else {
                return const_iterator(this, current_head_idx_, queue_data_[current_head_idx_].obj_id);
            }
        }
 
        const_iterator end() const { return const_iterator(this, invalid_index_, invalid_index_);}
 
    private:
 
        template<typename U>
        iterator pushImpl_ (U && dat)
        {
            sparta_assert(total_valid_ != capacity(), name_ << ": Queue is full");
 
            // can't write more than the allowed items
            sparta_assert(current_write_idx_ <= vector_size_);
            new (queue_data_.get() + current_write_idx_) QueueData(std::forward<U>(dat), ++obj_id_);
 
            // move the write index up.
            const uint32_t write_idx = current_write_idx_;
            current_write_idx_ = incrementIndexValue_(current_write_idx_);
 
            // either process now or schedule for later at the correct precedence.
            // update the valid count.
            total_valid_ += 1;
 
            updateUtilizationCounters_();
 
            return iterator(this, write_idx, obj_id_);
        }
 
        template<typename IteratorType>
        bool determineIteratorValidity_(IteratorType * itr) const
        {
            const auto physical_index = itr->physical_index_;
 
            if(physical_index == invalid_index_) {
                return false;
            }
 
            // Short cut... if we're empty, the iterator ain't valid
            if(empty()) { return false; }
 
            if(isValidPhysical_(physical_index)) {
                return (queue_data_[physical_index].obj_id == itr->obj_id_);
            }
            return false;
        }
 
        template<typename IteratorType>
        void decrementIterator_(IteratorType * itr) const
        {
            sparta_assert(itr->physical_index_ != 0, name_ <<
                          ": Iterator is not valid for decrementing");
 
            uint32_t physical_index = itr->physical_index_;
 
            // If it's the end iterator, go to the back - 1
            if(SPARTA_EXPECT_FALSE(physical_index == invalid_index_)) {
                const uint32_t phys_idx = decrementIndexValue_(current_write_idx_);
                itr->physical_index_ = phys_idx;
                itr->obj_id_ = queue_data_[phys_idx].obj_id;
            }
            else {
                // See if decrementing this iterator puts into the weeds.
                // If so, invalidate it.
                physical_index = decrementIndexValue_(physical_index);
                if(isValidPhysical_(physical_index)) {
                    itr->physical_index_ = physical_index;
                    itr->obj_id_ = queue_data_[physical_index].obj_id;
                }
                else {
                    itr->physical_index_ = invalid_index_;
                    itr->obj_id_ = invalid_index_;
               }
            }
        }
 
        template<typename IteratorType>
        void incrementIterator_(IteratorType * itr) const
        {
            uint32_t physical_index = itr->physical_index_;
 
            // See if incrementing this iterator puts it at the end.
            // If so, put it there.
            sparta_assert(physical_index != invalid_index_,
                          name_ << ": Trying to increment an invalid iterator");
 
            physical_index = incrementIndexValue_(physical_index);
 
            // See if the old logical index was valid.  We could be
            // incrementing to end()
            if(isValidPhysical_(physical_index))
            {
                // Safe to increment the physical_index
                itr->physical_index_ = physical_index;
                itr->obj_id_ = queue_data_[physical_index].obj_id;
            }
            else {
                // No longer valid index, but we could be rolling off
                // to the end().
                itr->physical_index_ = invalid_index_;
                itr->obj_id_ = invalid_index_;
            }
        }
 
        void updateUtilizationCounters_() {
            // Update Counters
            if(utilization_) {
                utilization_->setValue(total_valid_);
            }
        }
 
        void processInvalidation_()
        {
            sparta_assert(total_valid_ > 0);
            total_valid_ -= 1;
            updateUtilizationCounters_();
        }
 
        const size_type num_entries_;     
        size_type current_write_idx_ = 0; 
        size_type current_head_idx_  = 0; 
        size_type total_valid_       = 0; 
        const size_type vector_size_;     
        const size_type invalid_index_ {vector_size_ + 1};   
        const std::string name_; 
        uint64_t obj_id_ = 0;
 
        // Counters
        std::unique_ptr<sparta::CycleHistogramStandalone> utilization_;
 
        // Collectors
        std::unique_ptr<collection::IterableCollector<Queue<value_type> > > collector_;
 
        // Notice that our list for storing data is a dynamic array.
        // This is used instead of a stl vector to promote debug
        // performance.
        struct DeleteToFree_{
            void operator()(void * x){
                free(x);
            }
        };
        std::unique_ptr<QueueData[], DeleteToFree_> queue_data_;
    };
 
}