Buffer.hpp

Go to the documentation of this file.

// <Buffer.h> -*- C++ -*-
 
 
#pragma once
 
#include <cinttypes>
#include <vector>
#include <algorithm>
#include <type_traits>
 
#include "sparta/utils/SpartaAssert.hpp"
#include "sparta/utils/MetaStructs.hpp"
#include "sparta/statistics/CycleHistogram.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 Buffer
    {
    public:
 
        // A typedef for this Buffer's type. This is useful for my
        // subclasses, BufferIterator & EntryValidator
        typedef Buffer<DataT> BufferType;
 
        // Typedef for the DataT
        typedef DataT value_type;
 
        // Typedef for size_type
        typedef uint32_t size_type;
 
    private:
 
        struct DataPointer {
        private:
            alignas(value_type) std::byte object_memory_[sizeof(value_type)];
 
        public:
            DataPointer() { }
 
            DataPointer(DataPointer &&orig) {
                ::memcpy(&object_memory_, &orig.object_memory_, sizeof(object_memory_));
                data = reinterpret_cast<value_type*>(&object_memory_);
            }
 
            // No copies, only moves
            DataPointer(const DataPointer &) = delete;
 
            template<typename U>
            void allocate(U && dat) {
                data = new (&object_memory_) value_type(std::forward<U>(dat));
            }
 
            value_type * data         = nullptr;
            DataPointer* next_free    = nullptr;
            uint32_t     physical_idx = 0; 
        };
        //Forward Declaration
        struct DataPointerValidator;
 
        template <bool is_const_iterator = true>
        class BufferIterator : public utils::IteratorTraits<std::bidirectional_iterator_tag, value_type>
        {
        private:
            friend class Buffer<value_type>;
            typedef typename std::conditional<is_const_iterator,
                                              const value_type &, value_type &>::type DataReferenceType;
            typedef typename std::conditional<is_const_iterator,
                                              const BufferType *, BufferType *>::type BufferPointerType;
            typedef typename std::conditional<is_const_iterator,
                                              const DataPointer *, DataPointer *>::type DataPointerType;
            uint32_t getIndex_() const {
                if(buffer_entry_ == nullptr) {
                    return attached_buffer_->capacity();
                }
                return buffer_entry_->physical_idx;
            }
 
            BufferPointerType attached_buffer_ = nullptr;
 
            DataPointerType   buffer_entry_ = nullptr;
 
            BufferIterator(BufferPointerType buffer, DataPointerType entry) :
                attached_buffer_(buffer),
                buffer_entry_(entry)
            {}
 
 
        public:
 
            BufferIterator() = default;
 
            BufferIterator(const BufferIterator<false> & iter) :
                attached_buffer_(iter.attached_buffer_),
                buffer_entry_(iter.buffer_entry_)
            {}
 
            BufferIterator(const BufferIterator<true> & iter) :
                attached_buffer_(iter.attached_buffer_),
                buffer_entry_(iter.buffer_entry_)
            {}
 
            BufferIterator& operator=(const BufferIterator&) = default;
 
            bool operator<(const BufferIterator& rhs) const
            {
                sparta_assert(attached_buffer_ == rhs.attached_buffer_,
                              "Cannot compare BufferIterators created by different buffers.");
                return getIndex_() < rhs.getIndex_();
            }
 
            bool operator>(const BufferIterator& rhs) const
            {
                sparta_assert(attached_buffer_ == rhs.attached_buffer_,
                              "Cannot compare BufferIterators created by different buffers.");
                return getIndex_() > rhs.getIndex_();
            }
 
            bool operator==(const BufferIterator& rhs) const
            {
                sparta_assert(attached_buffer_ == rhs.attached_buffer_,
                              "Cannot compare BufferIterators created by different buffers.");
                return (buffer_entry_ == rhs.buffer_entry_);
            }
 
            bool operator!=(const BufferIterator& rhs) const
            {
                sparta_assert(attached_buffer_ == rhs.attached_buffer_,
                              "Cannot compare BufferIterators created by different buffers.");
                return !operator==(rhs);
            }
 
            bool isValid() const
            {
                if(buffer_entry_ != nullptr) {
                    return attached_buffer_->validator_->isValid(buffer_entry_);
                }
                return false;
            }
 
            DataReferenceType operator* () const {
                sparta_assert(attached_buffer_,
                              "The iterator is not attached to a buffer. Was it initialized?");
                sparta_assert(isValid(), "Iterator is not valid for dereferencing");
                return *(buffer_entry_->data);
            }
 
            value_type * operator -> () {
                sparta_assert(attached_buffer_,
                              "The iterator is not attached to a buffer. Was it initialized?");
                sparta_assert(isValid(), "Iterator is not valid for dereferencing");
                return buffer_entry_->data;
            }
 
            value_type const * operator -> () const {
                sparta_assert(attached_buffer_,
                              "The iterator is not attached to a buffer. Was it initialized?");
                sparta_assert(isValid(), "Iterator is not valid for dereferencing");
                return buffer_entry_->data;
            }
 
            BufferIterator & operator++() {
                sparta_assert(attached_buffer_,
                              "The iterator is not attached to a buffer. Was it initialized?");
                sparta_assert(isValid(), "Incrementing an iterator that is not valid");
                const uint32_t idx = buffer_entry_->physical_idx + 1;
                if(attached_buffer_->isValid(idx)) {
                    buffer_entry_ = attached_buffer_->buffer_map_[idx];
                }
                else {
                    buffer_entry_ = nullptr;
                }
                return *this;
            }
 
            BufferIterator operator++ (int) {
                BufferIterator buf_iter(*this);
                operator++();
                return buf_iter;
            }
 
            BufferIterator & operator-- ()
            {
                sparta_assert(attached_buffer_, "The iterator is not attached to a buffer. Was it initialized?");
                if(isValid()) {
                    uint32_t idx = buffer_entry_->physical_idx;
                    --idx;
                    if(attached_buffer_->isValid(idx)) {
                        buffer_entry_ = attached_buffer_->buffer_map_[idx];
                    }
                    else {
                        sparta_assert(idx < attached_buffer_->capacity(), "Decrementing the iterator results in buffer underrun");
                        buffer_entry_ = nullptr;
                    }
                }
                else if (attached_buffer_->size()) {
                    buffer_entry_ = attached_buffer_->buffer_map_[attached_buffer_->size()-1];
                }
                return *this;
            }
 
            BufferIterator  operator-- (int) {
                BufferIterator buf_iter(*this);
                operator--();
                return buf_iter;
            }
 
            friend class BufferIterator<true>;
        };
 
    public:
 
        typedef BufferIterator<false>                      iterator;
 
        typedef BufferIterator<true>                       const_iterator;
 
        typedef std::reverse_iterator<const_iterator>      const_reverse_iterator;
 
        typedef std::reverse_iterator<iterator>            reverse_iterator;
 
        Buffer(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);
 
        Buffer(const Buffer<value_type> & ) = delete;
 
        Buffer &operator=(const Buffer<value_type> &) = delete;
 
        Buffer(Buffer<value_type> &&);
 
        ~Buffer() { clear(); }
 
        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));
            return *(buffer_map_[idx]->data);
        }
 
        const value_type & read(const const_iterator & entry) const
        {
            return read(entry.getIndex_());
        }
 
        const value_type & read(const const_reverse_iterator & entry) const
        {
            return read(std::prev(entry.base()));
        }
 
        value_type & access(uint32_t idx) {
            sparta_assert(isValid(idx));
            return *(buffer_map_[idx]->data);
        }
 
        value_type & access(const const_iterator & entry) {
            return access(entry.getIndex_());
        }
 
        value_type & access(const const_reverse_iterator & entry) {
            return access(std::prev(entry.base()));
        }
 
        value_type & accessBack() {
            sparta_assert(isValid(num_valid_ - 1));
            return *(buffer_map_[num_valid_ - 1]->data);
        }
 
        size_type capacity() const {
            return num_entries_;
        }
 
        size_type size() const {
            return num_valid_;
        }
 
        size_type numFree() const {
            return capacity() - size();
        }
 
        iterator push_back(const value_type& dat)
        {
            return push_backImpl_(dat);
        }
 
        iterator push_back(value_type&& dat)
        {
            return push_backImpl_(std::move(dat));
        }
 
        iterator insert(uint32_t idx, const value_type& dat)
        {
            return insertImpl_(idx, dat);
        }
 
        iterator insert(uint32_t idx, value_type&& dat)
        {
            return insertImpl_(idx, std::move(dat));
        }
 
        iterator insert(const const_iterator & entry, const value_type& dat)
        {
            return insert(entry.getIndex_(), dat);
        }
 
        iterator insert(const const_iterator & entry, value_type&& dat)
        {
            return insert(entry.getIndex_(), std::move(dat));
        }
 
        iterator insert(const const_reverse_iterator & entry, const value_type& dat)
        {
            return insert(entry.base().getIndex_(), dat);
        }
 
        iterator insert(const const_reverse_iterator & entry, value_type&& dat)
        {
            return insert(entry.base().getIndex_(), std::move(dat));
        }
 
        void erase(uint32_t idx)
        {
            // Make sure we are invalidating an already valid object.
            sparta_assert(idx < size(),
                          "Cannot erase an index that is not already valid");
 
            // Do the invalidation immediately
            // 1. Move the free space pointer to the erased position.
            // 2. Call the DataT's destructor
            // 3. Set the current free space pointer's next to the old free position
            DataPointer* oldFree = free_position_;
            free_position_ = buffer_map_[idx];
            free_position_->data->~value_type();
            free_position_->next_free = oldFree;
 
            // Mark DataPointer as invalid
            validator_->detachDataPointer(free_position_);
 
            // Shift all the positions above the invalidation in the map one space down.
            sparta_assert(num_valid_ > 0);
            const uint32_t top_idx_of_buffer = num_valid_ - 1;
            while(idx < top_idx_of_buffer)
            {
                // assert that we are not going to do an invalid read.
                sparta_assert(idx + 1 < num_entries_);
                buffer_map_[idx] = buffer_map_[idx + 1];
                buffer_map_[idx]->physical_idx = idx;
 
                // Shift the indexes in the address map.
                address_map_[idx] = address_map_[idx + 1];
                ++idx;
            }
 
            // the entry at the old num_valid_ in the map now points to nullptr
            buffer_map_[top_idx_of_buffer] = nullptr;
 
            // Remove this entry of the address map as it becomes a free position.
            address_map_.erase(top_idx_of_buffer);
 
            // update counts.
            --num_valid_;
            updateUtilizationCounters_();
        }
 
        iterator erase(const const_iterator& entry)
        {
            sparta_assert(entry.attached_buffer_ == this,
                          "Cannot erase an entry created by another Buffer");
            // erase the index in the actual buffer.
            erase(entry.getIndex_());
            return {this, buffer_map_[entry.getIndex_()]};
        }
 
        reverse_iterator erase(const const_reverse_iterator& entry)
        {
            return reverse_iterator{erase(std::prev(entry.base()))};
        }
 
        void clear()
        {
            num_valid_ = 0;
            std::for_each(buffer_map_.begin(), buffer_map_.end(),
                          [] (auto map_entry)
                          {
                              if(map_entry) {
                                  map_entry->data->~value_type();
                              }
                          });
            std::fill(buffer_map_.begin(), buffer_map_.end(), nullptr);
            for(uint32_t i = 0; i < data_pool_size_ - 1; ++i) {
                data_pool_[i].next_free = &data_pool_[i + 1];
            }
            data_pool_[data_pool_size_ - 1].next_free = &data_pool_[data_pool_size_ - 1];
            free_position_ = &data_pool_[0];
            first_position_ = &data_pool_[0];
            validator_->clear();
            address_map_.clear();
            updateUtilizationCounters_();
        }
 
        bool empty() const
        {
            return num_valid_ == 0;
        }
 
        void enableCollection(TreeNode * parent) {
            collector_.
                reset(new collection::IterableCollector<Buffer<DataT> >(parent, getName(),
                                                                        this, capacity()));
        }
 
        iterator begin(){
            if(size()) {
                sparta_assert(buffer_map_[0]);
                return iterator(this, buffer_map_[0]);
            }
            return end();
        }
 
        iterator end() { return iterator(this, nullptr);}
 
        const_iterator begin() const {
            if(size()) {
                return const_iterator(this, buffer_map_[0]);
            }
            return end();
        }
 
        const_iterator end() const { return const_iterator(this, nullptr);}
 
        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());}
 
        void makeInfinite(const uint32_t resize_delta = 1) {
            is_infinite_mode_ = true;
            resize_delta_ = resize_delta;
        }
 
    private:
 
        typedef std::vector<DataPointer>  DataPool;
        typedef std::vector<DataPointer*> PointerList;
 
        struct DataPointerValidator
        {
            //  data_pool_ of the Buffer class.
            const DataPool * data_pool_;
            std::vector<uint32_t>  validator_; 
            size_type getIndex_(const DataPointer * dp)const {
                auto i = (dp - &(*data_pool_)[0]);
                return static_cast<size_type>(i);
            }
 
            DataPointerValidator(const Buffer &b):
                data_pool_(&b.data_pool_),
                validator_(b.num_entries_, 0)
            {}
 
            void attachDataPointer(const DataPointer* dp){
                validator_[getIndex_(dp)] = 1;
            }
 
            bool isValid(const DataPointer * dp) const {
                return bool(validator_[getIndex_(dp)]);
            }
 
            void detachDataPointer(DataPointer * dp) {
                validator_[getIndex_(dp)] = 0;
            }
 
            void clear() {
                std::fill(validator_.begin(), validator_.end(), 0);
            }
 
            void resizeIteratorValidator(const uint32_t resize_delta,
                                         const DataPool & data_pool) {
                validator_.resize(validator_.capacity() + resize_delta);
                data_pool_ = &data_pool;
            }
        };
 
        void updateUtilizationCounters_() {
            // Update Counters
            if(utilization_) {
                utilization_->setValue(num_valid_);
            }
        }
 
        void resizeInternalContainers_() {
 
            // Assert that the Buffer class is in Infinite-Mode.
            sparta_assert(is_infinite_mode_,
                          "The Buffer class must be in Infinite-Mode in order to resize itself.");
 
            // We do not resize if there are available slots in buffer.
            if(numFree() != 0) {
                return;
            }
 
            // Resize the buffer_map_ with the amount provided by user.
            buffer_map_.resize(buffer_map_.capacity() + resize_delta_);
 
            // The number of entries the buffer can hold is its capacity.
            num_entries_ = buffer_map_.capacity();
 
            // Resize the data_pool_ to twice the capacity of the buffer_map_.
            data_pool_.resize(num_entries_ * 2);
 
            // The number of entries the pool can hold is its capacity.
            data_pool_size_ = data_pool_.capacity();
 
 
            // Each entry in data_pool_ should have their next free position
            // pointer point to the slot to its right.
            for(uint32_t i = 0; i < data_pool_size_ - 1; ++i) {
                data_pool_[i].next_free = &data_pool_[i + 1];
            }
 
            // The last entry should point to itself as the next free position.
            data_pool_[data_pool_size_ - 1].next_free = &data_pool_[data_pool_size_ - 1];
 
            // The first position should point to the first entry.
            first_position_ = &data_pool_[0];
 
            // The free position should point to the location according to
            // the number of entries in the buffer.
            free_position_ = &data_pool_[num_valid_];
 
            // Make all the pointers in buffer_map_ point to the appropriate indexes.
            for(uint32_t i = 0; i < num_valid_; ++i) {
                buffer_map_[i] = &data_pool_[address_map_[i]];
            }
 
            // Resize the validator vector and relink the validator data pool.
            validator_->resizeIteratorValidator(resize_delta_, data_pool_);
        }
 
        template<typename U>
        iterator push_backImpl_(U&& dat)
        {
 
            // Check to see if the vectors need to be resized and relinked.
            if(SPARTA_EXPECT_FALSE(is_infinite_mode_)) {
                resizeInternalContainers_();
            }
            sparta_assert(numFree(), "Buffer exhausted");
            sparta_assert(free_position_ != nullptr);
            free_position_->allocate(std::forward<U>(dat));
            free_position_->physical_idx = num_valid_;
 
            // Create the entry to be returned.
            iterator entry(this, free_position_);
 
            // Do the append now.  We can do this with different logic
            // that does not require a process.
            buffer_map_[num_valid_] = free_position_;
 
            // Store the index in the data_pool_ to which current
            // free_position_ points to. We need to relink all these
            // pointers once the data_pool_ resizes.
            address_map_[num_valid_] =
                static_cast<uint32_t>(free_position_ - &data_pool_[0]);
            //Mark this data pointer as valid
            validator_->attachDataPointer(free_position_);
            ++num_valid_;
            free_position_ = free_position_->next_free;
            updateUtilizationCounters_();
 
            return entry;
        }
 
        template<typename U>
        iterator insertImpl_(uint32_t idx, U&& dat)
        {
            // Check to see if the vectors need to be resized and relinked.
            if(SPARTA_EXPECT_FALSE(is_infinite_mode_)) {
                resizeInternalContainers_();
            }
            sparta_assert(numFree(), "Buffer '" << getName() << "' exhausted");
            sparta_assert(idx <= num_valid_, "Buffer '" << getName()
                          << "': Cannot insert before a non valid index");
            sparta_assert(free_position_ != nullptr);
            free_position_->allocate(std::forward<U>(dat));
            free_position_->physical_idx = idx;
 
            //Mark this data pointer as valid
            validator_->attachDataPointer(free_position_);
 
            // Create the entry to be returned.
            iterator entry(this, free_position_);
 
            //Shift all the positions above idx in the map one space down.
            uint32_t i = num_valid_;
            while(i > idx)
            {
                //assert that we are not going to do an invalid read.
                buffer_map_[i] = buffer_map_[i - 1];
                buffer_map_[i]->physical_idx = i ;
 
                // Shift the indexes in the map.
                address_map_[i] = address_map_[i - 1];
                --i;
            }
 
            buffer_map_[idx] = free_position_;
 
            // Store the index in the data_pool_ to which current
            // free_position_ points to. We need to relink all these
            // pointers once the data_pool_ resizes.
            address_map_[num_valid_] =
                static_cast<uint32_t>(free_position_ - &data_pool_[0]);
            ++num_valid_;
            free_position_ = free_position_->next_free;
            updateUtilizationCounters_();
            return entry;
        }
 
        std::string name_;
        const Clock * clk_ = nullptr;
        size_type   num_entries_ = 0;    
        PointerList buffer_map_;         
        size_type   data_pool_size_ = 0; 
        DataPool    data_pool_;          
        DataPointer*  free_position_  = nullptr; 
        DataPointer*  first_position_ = nullptr; 
        size_type     num_valid_      = 0;       
        std::unique_ptr<DataPointerValidator> validator_;    
        // Counters
        std::unique_ptr<sparta::CycleHistogramStandalone> utilization_;
 
        // Collectors
        std::unique_ptr<collection::IterableCollector<Buffer<value_type> > > collector_;
 
        //  The behaviour of these methods change accordingly.
        bool is_infinite_mode_ {false};
 
        //  The additional amount of entries the vector must allocate when resizing.
        sparta::utils::ValidValue<uint32_t> resize_delta_;
 
        std::unordered_map<uint32_t, uint32_t> address_map_;
    };
 
    // Definitions...
    template<class DataT>
    Buffer<DataT>::Buffer(const std::string & name,
                          uint32_t num_entries,
                          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) :
        name_(name),
        clk_(clk),
        num_entries_(num_entries),
        data_pool_size_(num_entries* 2)
    {
        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));
        }
 
        buffer_map_.resize(num_entries_);
        data_pool_.resize(data_pool_size_);
 
        // Must set the validator before you clear
        validator_.reset(new DataPointerValidator(*this));
        clear();
    }
 
    template<typename DataT>
    Buffer<DataT>::Buffer(Buffer<DataT>&& rval) :
        name_(std::move(rval.name_)),
        clk_(rval.clk_),
        num_entries_(rval.num_entries_),
        buffer_map_(std::move(rval.buffer_map_)),
        data_pool_size_(rval.data_pool_size_),
        data_pool_(std::move(rval.data_pool_)),
        free_position_(rval.free_position_),
        first_position_(rval.first_position_),
        num_valid_(rval.num_valid_),
        validator_(new DataPointerValidator(*this)),
        utilization_(std::move(rval.utilization_)),
        collector_(std::move(rval.collector_)),
        is_infinite_mode_(rval.is_infinite_mode_),
        resize_delta_(std::move(rval.resize_delta_)),
        address_map_(std::move(rval.address_map_)){
        rval.clk_ = nullptr;
        rval.num_entries_ = 0;
        rval.data_pool_size_ = 0;
        rval.free_position_ = nullptr;
        rval.first_position_ = nullptr;
        rval.num_valid_ = 0;
        rval.utilization_ = nullptr;
        rval.collector_ = nullptr;
        validator_->validator_ = std::move(rval.validator_->validator_);
        if(collector_) {
            collector_->reattach(this);
        }
    }
}