CircularBuffer.hpp

Go to the documentation of this file.

// <CircularBuffer.h> -*- C++ -*-
 
 
#pragma once
 
#include <cinttypes>
#include <list>
#include <limits>
#include <algorithm>
 
#include "sparta/utils/SpartaAssert.hpp"
#include "sparta/statistics/CycleCounter.hpp"
#include "sparta/statistics/StatisticInstance.hpp"
#include "sparta/statistics/StatisticDef.hpp"
#include "sparta/collection/IterableCollector.hpp"
#include "sparta/statistics/Counter.hpp"
#include "sparta/utils/IteratorTraits.hpp"
 
namespace sparta
{
 
    template <class DataT>
    class CircularBuffer
    {
    public:
 
        // A typedef for this CircularBuffer's type. This is useful for my
        // subclasses, CircularBufferIterator & EntryValidator
        typedef CircularBuffer<DataT> CircularBufferType;
 
        // Typedef for the DataT
        typedef DataT value_type;
 
        // Typedef for size_type
        typedef uint32_t size_type;
 
    private:
 
        struct CircularBufferData
        {
            template<typename U = value_type>
            CircularBufferData(U && dat,
                               const uint64_t window_idx) :
                data(std::forward<U>(dat)),
                window_idx(window_idx)
            {}
            CircularBufferData(const uint64_t window_idx) :
                window_idx(window_idx)
            {}
            value_type data{};   // The data supplied by the user
            uint64_t window_idx; // The location in the validity
                                 // window of the CB.  Serves as a
                                 // fast check for validity of
                                 // outstanding iterator
        };
        using CircularBufferDataStorage = std::list<CircularBufferData>;
        typedef typename CircularBufferDataStorage::iterator       InternalCircularBufferIterator;
        typedef typename CircularBufferDataStorage::const_iterator InternalCircularBufferConstIterator;
 
        template <bool is_const_iterator = true>
        class CircularBufferIterator :
            public utils::IteratorTraits<std::bidirectional_iterator_tag, value_type>
        {
        private:
            // Constant to indicate constness
            static constexpr bool is_const_iterator_type = is_const_iterator;
 
            friend class CircularBuffer<value_type>;
            typedef typename std::conditional<is_const_iterator,
                                              const value_type &, value_type &>::type DataReferenceType;
            typedef typename std::conditional<is_const_iterator,
                                              const CircularBufferType *, CircularBufferType *>::type CircularBufferPointerType;
 
            // Pointer to the CircularBuffer which created this entry
            CircularBufferPointerType attached_circularbuffer_ = nullptr;
 
            typedef typename std::conditional<is_const_iterator,
                                              InternalCircularBufferConstIterator,
                                              InternalCircularBufferIterator>::type SpecificCircularBufferIterator;
            SpecificCircularBufferIterator circularbuffer_entry_;
 
            uint64_t window_idx_ = std::numeric_limits<uint64_t>::max();
 
            CircularBufferIterator(CircularBufferPointerType circularbuffer,
                                   SpecificCircularBufferIterator entry,
                                   const uint64_t window_idx) :
                attached_circularbuffer_(circularbuffer),
                circularbuffer_entry_(entry),
                window_idx_(window_idx)
            {}
 
            // Used by the CircularBuffer to get the position in the
            // internal CircularBuffer
            SpecificCircularBufferIterator getInternalBufferEntry_() const {
                return circularbuffer_entry_;
            }
 
        public:
 
            CircularBufferIterator() = default;
 
            CircularBufferIterator(const CircularBufferIterator<false> & iter) :
                attached_circularbuffer_(iter.attached_circularbuffer_),
                circularbuffer_entry_(iter.circularbuffer_entry_),
                window_idx_(iter.window_idx_)
            {}
 
            CircularBufferIterator(const CircularBufferIterator<true> & iter) :
                attached_circularbuffer_(iter.attached_circularbuffer_),
                circularbuffer_entry_(iter.circularbuffer_entry_),
                window_idx_(iter.window_idx_)
            {}
 
            CircularBufferIterator& operator=(const CircularBufferIterator& rhs) = default;
 
            bool operator<(const CircularBufferIterator& rhs) const
            {
                sparta_assert(attached_circularbuffer_ == rhs.attached_circularbuffer_,
                            "Cannot compare CircularBufferIterators created by different CircularBuffers.");
                return window_idx_ > rhs.window_idx_;
            }
 
            bool operator>(const CircularBufferIterator& rhs) const
            {
                sparta_assert(attached_circularbuffer_ == rhs.attached_circularbuffer_,
                            "Cannot compare CircularBufferIterators created by different CircularBuffers.");
                return window_idx_ < rhs.window_idx_;
            }
 
            bool operator==(const CircularBufferIterator& rhs) const
            {
                sparta_assert(attached_circularbuffer_ == rhs.attached_circularbuffer_,
                            "Cannot compare CircularBufferIterators created by different CircularBuffers.");
                return (window_idx_ == rhs.window_idx_);
            }
 
            bool operator!=(const CircularBufferIterator& rhs) const
            {
                sparta_assert(attached_circularbuffer_ == rhs.attached_circularbuffer_,
                            "Cannot compare CircularBufferIterators created by different CircularBuffers.");
                return !operator==(rhs);
            }
 
            bool isValid() const
            {
                if(attached_circularbuffer_) {
                    return attached_circularbuffer_->isValidIterator_(window_idx_);
                }
                return false;
            }
 
            DataReferenceType operator* () {
                sparta_assert(attached_circularbuffer_,
                            "This iterator is not attached to a CircularBuffer. Was it initialized?");
                sparta_assert(isValid(), "Iterator is not valid for dereferencing");
                return circularbuffer_entry_->data;
            }
            value_type* operator->()
            {
                sparta_assert(attached_circularbuffer_,
                            "This iterator is not attached to a CircularBuffer. Was it initialized?");
                sparta_assert(isValid(), "Iterator is not valid for dereferencing");
                return &circularbuffer_entry_->data;
            }
            const value_type* operator->() const
            {
                sparta_assert(attached_circularbuffer_,
                            "This iterator is not attached to a CircularBuffer. Was it initialized?");
                sparta_assert(isValid(), "Iterator is not valid for dereferencing");
                return &circularbuffer_entry_->data;
            }
 
            CircularBufferIterator & operator++() {
                sparta_assert(attached_circularbuffer_,
                            "This iterator is not attached to a CircularBuffer. Was it initialized?");
                if(isValid()) {
                    ++window_idx_;
                    ++circularbuffer_entry_;
                }
                else {
                    sparta_assert(!"Attempt to increment an invalid iterator");
                }
                return *this;
            }
 
            CircularBufferIterator operator++ (int) {
                CircularBufferIterator buf_iter(*this);
                operator++();
                return buf_iter;
            }
 
            CircularBufferIterator & operator-- ()
            {
                sparta_assert(attached_circularbuffer_, "The iterator is not attached to a CircularBuffer. Was it initialized?");
                if(attached_circularbuffer_->isValidIterator_(window_idx_ - 1)) {
                    --window_idx_;
                    --circularbuffer_entry_;
                }
                else {
                    sparta_assert(!"Attempt to decrement an iterator beyond bounds or that is invalid");
                }
                return *this;
            }
 
            CircularBufferIterator  operator-- (int) {
                CircularBufferIterator buf_iter(*this);
                operator--();
                return buf_iter;
            }
 
            friend class CircularBufferIterator<true>;
        };
 
        /*
         * Custom class for reverse iterator to support validity checking
         */
        template <typename iter_type>
        class CircularBufferReverseIterator : public std::reverse_iterator<iter_type>
        {
        public:
            typedef typename std::conditional<iter_type::is_const_iterator_type,
                                              InternalCircularBufferConstIterator,
                                              InternalCircularBufferIterator>::type SpecificCircularBufferIterator;
            SpecificCircularBufferIterator circularbuffer_entry_;
 
            explicit CircularBufferReverseIterator(const iter_type & it) :
                std::reverse_iterator<iter_type>(it)
            {}
 
            template<class U >
            CircularBufferReverseIterator(const std::reverse_iterator<U> & other) :
                std::reverse_iterator<iter_type>(other)
            {}
 
            bool isValid() const {
                auto it = std::reverse_iterator<iter_type>::base();
                try {
                    return (--it).isValid();
                }
                catch(...) {
                    return false;
                }
                return false;
            }
        private:
            friend class CircularBuffer<value_type>;
            SpecificCircularBufferIterator getInternalBufferEntry_() const {
                auto it = std::reverse_iterator<iter_type>::base();
                return (--it).circularbuffer_entry_;
            }
        };
 
    public:
 
        typedef CircularBufferIterator<false>                 iterator;
 
        typedef CircularBufferIterator<true>                  const_iterator;
 
        typedef CircularBufferReverseIterator<const_iterator> const_reverse_iterator;
 
        typedef CircularBufferReverseIterator<iterator>       reverse_iterator;
 
        CircularBuffer(const std::string & name,
                       const uint32_t max_size,
                       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);
 
        CircularBuffer(const CircularBuffer<value_type> & ) = delete;
 
        CircularBuffer &operator=(const CircularBuffer<value_type> &) = delete;
 
        void enableCollection(TreeNode * parent) {
            collector_.
                reset(new collection::IterableCollector<CircularBuffer<DataT> >(parent, getName(),
                                                                                this, capacity()));
        }
 
        std::string getName() const {
            return name_;
        }
 
        bool isValid(uint32_t idx) const {
            return idx < size();
        }
 
        size_type capacity() const {
            return max_size_;
        }
 
        size_type size() const {
            return num_valid_;
        }
 
        size_type numFree() const {
            return capacity() - size();
        }
 
        void push_back(const value_type& dat)
        {
            push_backImpl_(dat);
        }
 
        void push_back(value_type&& dat)
        {
            push_backImpl_(std::move(dat));
        }
 
        iterator insert(const iterator & entry, const value_type& dat)
        {
            return insertEntry_(entry, dat);
        }
 
        iterator insert(const iterator & entry, value_type&& dat)
        {
            return insertEntry_(entry, std::move(dat));
        }
 
        iterator insert(const const_iterator & entry, const value_type& dat)
        {
            return insertEntry_(entry, dat);
        }
 
        iterator insert(const const_iterator & entry, value_type&& dat)
        {
            return insertEntry_(entry, std::move(dat));
        }
 
        void erase(const_iterator entry)
        {
            sparta_assert(entry.attached_circularbuffer_ == this,
                        "Cannot erase an entry created by another CircularBuffer");
            eraseEntry_(entry);
        }
 
        void erase(const_reverse_iterator entry)
        {
            sparta_assert(entry.base().attached_circularbuffer_ == this,
                        "Cannot erase an entry created by another CircularBuffer");
            eraseEntry_(entry);
        }
        void erase(reverse_iterator entry) {
            erase(const_reverse_iterator(entry));
        }
 
        void clear()
        {
            circularbuffer_data_.clear();
            num_valid_ = 0;
            start_idx_ = end_idx_;
            updateUtilizationCounters_();
        }
 
        iterator begin() {
            if(size()) {
                return iterator(this,
                                circularbuffer_data_.begin(),
                                circularbuffer_data_.begin()->window_idx);
            }
            return end();
        }
 
        iterator end() {
            return iterator(this, circularbuffer_data_.end(), end_idx_);
        }
 
        const_iterator begin() const {
            if(size()) {
                return const_iterator(this,
                                      circularbuffer_data_.begin(),
                                      circularbuffer_data_.begin()->window_idx);
            }
            return end();
        }
 
        const_iterator end() const {
            return const_iterator(this, circularbuffer_data_.end(), end_idx_);
        }
 
        reverse_iterator rbegin(){
            return reverse_iterator(end());
        }
 
        reverse_iterator rend() { return reverse_iterator(begin()); }
 
        const_reverse_iterator rbegin() const {
            return const_reverse_iterator(end());
        }
 
        const_reverse_iterator rend() const { return const_reverse_iterator(begin());}
 
        value_type operator[](const uint32_t idx) {
            sparta_assert(idx < size(), "Index out of range");
            auto it = this->begin();
            std::advance(it, idx);
            return *it;
        }
 
    private:
 
        // Used by the internal iterator type to see if it's still
        // valid
        bool isValidIterator_(uint32_t window_idx) const {
            return (window_idx >= start_idx_ && window_idx < end_idx_);
        }
 
        template<typename EntryIteratorT>
        void eraseEntry_(const EntryIteratorT & entry)
        {
            sparta_assert(entry.isValid());
            circularbuffer_data_.erase(entry.getInternalBufferEntry_());
            --num_valid_;
            invalidateIndexes_();
        }
 
        template<typename U>
        void push_backImpl_(U&& dat)
        {
            circularbuffer_data_.emplace(circularbuffer_data_.end(), std::forward<U>(dat), end_idx_);
            ++end_idx_;
            if(num_valid_ == max_size_) {
                circularbuffer_data_.pop_front();
                ++start_idx_;
            }
            else {
                ++num_valid_;
            }
 
            // XXX Remove when testing complete.  This is an O(n) operation
            sparta_assert(circularbuffer_data_.size() <= size());
 
            updateUtilizationCounters_();
        }
 
        template<typename EntryIteratorT, typename U>
        iterator insertEntry_(const EntryIteratorT & entry, U&& dat)
        {
            // If the buffer is empty, the iterator is not valid, so
            // just do a push_back
            if(circularbuffer_data_.empty()) {
                push_back(std::forward<U>(dat));
                return begin();
            }
            sparta_assert(entry.isValid(),
                        "Cannot insert into Circularbuffer at given iterator");
            auto it = circularbuffer_data_.insert(entry.getInternalBufferEntry_(),
                                                  CircularBufferData(std::forward<U>(dat), end_idx_));
            ++num_valid_;
            invalidateIndexes_();
            return iterator(this, it, it->window_idx);
        }
 
        void invalidateIndexes_() {
            // To invalidate any and all outstanding iterators, move
            // the start/end indexes outside the current window.  Do
            // not set the start_idx_ to the old end_idx_ as any older
            // "end" iterator would be considered valid (equals the
            // start_idx_)
            start_idx_ = ++end_idx_;
            for(auto & it : circularbuffer_data_) {
                it.window_idx = end_idx_;
                ++end_idx_;
            }
        }
 
        void updateUtilizationCounters_() {
            // Update Counters
            if(!utilization_count_.empty()) {
                if(previous_valid_entry_ != num_valid_) {
                    utilization_count_[previous_valid_entry_]->stopCounting();
                    utilization_count_[num_valid_]->startCounting();
                    previous_valid_entry_ = num_valid_;
                }
                if (num_valid_ > utilization_max_->get()) {
                    utilization_max_->set(num_valid_);
                }
            }
        }
 
        const size_type            max_size_;            
        const std::string          name_;                
        CircularBufferDataStorage  circularbuffer_data_; 
        size_type       num_valid_       = 0;  
        uint64_t        start_idx_       = 0;  
        uint64_t        end_idx_         = 0;  
 
        // Counters
        std::vector<std::unique_ptr<sparta::CycleCounter>> utilization_count_;
        std::unique_ptr<StatisticDef> weighted_utilization_avg_;
        std::unique_ptr<StatisticInstance> avg_instance_;
        std::unique_ptr<sparta::Counter> utilization_max_;
 
        // The last valid entry (to close out a utilization)
        uint32_t previous_valid_entry_ = 0;
 
        // Collectors
        std::unique_ptr<collection::IterableCollector<CircularBuffer<value_type> > > collector_;
    };
 
    // Definitions...
    template<class DataT>
    CircularBuffer<DataT>::CircularBuffer(const std::string & name,
                                          uint32_t max_size,
                                          const Clock * clk,
                                          StatisticSet * statset,
                                          InstrumentationNode::visibility_t stat_vis_general,
                                          InstrumentationNode::visibility_t stat_vis_detailed,
                                          InstrumentationNode::visibility_t stat_vis_max,
                                          InstrumentationNode::visibility_t stat_vis_avg) :
        max_size_(max_size),
        name_(name)
    {
        if(statset)
        {
            std::stringstream expression_numerator;
            std::stringstream expression_denum;
            expression_denum << "( ";
            expression_numerator << "( ";
            // The size is 0 entries up to max_size
            for(uint32_t i = 0; i < max_size_ + 1; ++i)
            {
                std::stringstream str;
                str << name << "_util_cnt" << i;
 
                InstrumentationNode::visibility_t visibility = stat_vis_detailed;
 
                if (i == 0 || i == (max_size_)) {
                    if(stat_vis_general == InstrumentationNode::AUTO_VISIBILITY)
                    {
                        visibility = InstrumentationNode::CONTAINER_DEFAULT_VISIBILITY;
                    }
                    else{
                        visibility = stat_vis_general;
                    }
                }
                else // we are internal counts for different levels of utilization.
                {
                    if(stat_vis_detailed == InstrumentationNode::AUTO_VISIBILITY)
                    {
                        visibility = InstrumentationNode::CONTAINER_DEFAULT_VISIBILITY;
                    }
                    else{
                        visibility = stat_vis_detailed;
                    }
                }
 
                utilization_count_.
                    emplace_back(new CycleCounter(statset,
                                                  str.str(),
                                                  name + "_utilization_count", i,
                                                  "Entry Utilization Counts of " + name,
                                                  CounterBase::COUNT_NORMAL, clk, visibility));
                expression_numerator << "( "<< i << " * " << name << "_util_cnt" << i << " )";
                expression_denum << name << "_util_cnt" << i;
                if( i != max_size_ )
                {
                    expression_numerator << " + ";
                    expression_denum << " + ";
                }
 
            }
            expression_numerator << " )";
            expression_denum << " )";
            utilization_count_[0]->startCounting();
 
            if(stat_vis_avg == InstrumentationNode::AUTO_VISIBILITY)
            {
                stat_vis_avg = InstrumentationNode::DEFAULT_VISIBILITY;
            }
            // add a statasticdef to the set for the weighted average    expression_numerator.str() + "/" + expression_denum.str()
            weighted_utilization_avg_.reset(new StatisticDef(statset,
                                                             name + "_utilization_weighted_avg",
                                                             "Calculate the weighted average of the CircularBuffer's utilization",
                                                             statset,
                                                             expression_numerator.str() + " / " + expression_denum.str(),
                                                             sparta::StatisticDef::VS_ABSOLUTE, stat_vis_avg));
 
            // Add a counter to track the maximum utilization
            if(stat_vis_max == InstrumentationNode::AUTO_VISIBILITY)
            {
                stat_vis_max = InstrumentationNode::DEFAULT_VISIBILITY;
            }
            utilization_max_.reset(new Counter(statset,
                                               name + "_utilization_max",
                                               "The maximum utilization",
                                               CounterBase::COUNT_LATEST,
                                               stat_vis_max));
        }
    }
 
 
 
}