Array.hpp

Go to the documentation of this file.

// <Array.hpp> -*- C++ -*-
 
#pragma once
 
#include <cinttypes>
#include <vector>
#include <string>
#include <memory>
 
#include "sparta/utils/SpartaAssert.hpp"
#include "sparta/statistics/CycleHistogram.hpp"
#include "sparta/collection/IterableCollector.hpp"
#include "sparta/utils/IteratorTraits.hpp"
 
namespace sparta
{
    enum class ArrayType {
        NORMAL, 
        AGED    
    };
 
    template<class DataT, ArrayType ArrayT = ArrayType::AGED>
    class Array
    {
    private:
        struct ArrayPosition{
            ArrayPosition() :
                valid(false),
                to_validate(false){}
 
            template<typename U>
            explicit ArrayPosition(U && data) :
                data(std::forward<U>(data)){}
 
            bool valid;
            bool to_validate;
            DataT data;
            std::list<uint32_t>::iterator list_pointer;
            uint64_t age_abs_id = 0; // Absolute ID of all allocations
            uint32_t age_rel_id = 0; // Relative ID of current allocations
        };
 
        typedef std::vector<ArrayPosition> ArrayVector;
 
        typedef Array<DataT, ArrayT>       FullArrayType;
 
    public:
 
        typedef DataT    value_type;
 
        typedef DataT    DataType;
 
        typedef uint32_t size_type;
 
        typedef std::list<uint32_t>        AgedList;
 
        template<bool is_const_iterator = true>
        struct ArrayIterator : public utils::IteratorTraits<std::forward_iterator_tag, value_type>
        {
        private:
 
            typedef typename std::conditional<is_const_iterator,
                                              const value_type &,
                                              value_type &>::type  DataReferenceType;
 
            typedef typename std::conditional<is_const_iterator,
                                              const FullArrayType *,
                                              FullArrayType *>::type   ArrayPointerType;
            friend FullArrayType;
 
            ArrayIterator(ArrayPointerType array,
                          uint32_t start_index,
                          bool is_aged,
                          bool is_circular,
                          bool is_aged_walk) :
                index_(start_index),
                array_(array),
                is_aged_(is_aged),
                is_circular_(is_circular),
                is_aged_walk_(is_aged_walk)
            {}
 
            operator uint32_t() const {
                return index_;
            }
 
            DataReferenceType getAccess_(std::false_type) {
                return array_->access(index_);
            }
 
            DataReferenceType getAccess_(std::true_type) const {
                return array_->read(index_);
            }
 
            // Allow the creation of a const iterator from non-const
            friend ArrayIterator<false>;
        public:
 
            ArrayIterator() = default;
 
            ArrayIterator(const ArrayIterator<false> & other) :
                index_(other.index_),
                array_(other.array_),
                is_aged_(other.is_aged_),
                is_circular_(other.is_circular_),
                is_aged_walk_(other.is_aged_walk_)
            {}
 
            ArrayIterator(const ArrayIterator<true> & other) :
                index_(other.index_),
                array_(other.array_),
                is_aged_(other.is_aged_),
                is_circular_(other.is_circular_),
                is_aged_walk_(other.is_aged_walk_)
            {}
 
            ArrayIterator& operator=(const ArrayIterator& other) = default;
 
            void reset()
            {
                index_ = sparta::notNull(array_)->capacity();
            }
 
            bool isIndexValid() const
            {
                return (index_ < sparta::notNull(array_)->capacity());
            }
 
            uint32_t getIndex() const
            {
                sparta_assert(index_ != sparta::notNull(array_)->invalid_entry_,
                              "Cannot operate on an unitialized iterator.");
                return index_;
            }
 
            bool isValid() const
            {
                return (array_ != nullptr) &&
                    (index_ != array_->invalid_entry_) &&
                    (array_->isValid(index_));
            }
 
            bool isOlder(const uint32_t idx) const
            {
                sparta_assert(index_ < sparta::notNull(array_)->capacity(),
                            "Cannot operate on an uninitialized iterator.");
                return array_->isOlder(index_, idx);
            }
 
            bool isOlder(const ArrayIterator & other) const
            {
                return isOlder(other.index_);
            }
 
            bool isYounger(const uint32_t idx) const
            {
                sparta_assert(index_ < sparta::notNull(array_)->capacity(),
                            "Cannot operate on an uninitialized iterator.");
                return sparta::notNull(array_)->isYounger(index_, idx);
            }
 
            bool isYounger(const ArrayIterator & other) const
            {
                return isYounger(other.index_);
            }
 
            bool operator<(const ArrayIterator &rhs) const {
                return isYounger(rhs);
            }
 
            bool operator==(const ArrayIterator& rhs) const
            {
                return (rhs.index_ == index_) && (rhs.array_ == array_);
            }
 
            bool operator==(const uint32_t & rhs) const
            {
                return (rhs == index_);
            }
 
            bool operator!=(const ArrayIterator& rhs) const
            {
                return (rhs.index_ != index_) || (rhs.array_ != array_);
            }
 
            DataReferenceType operator*() {
                sparta_assert(index_ < sparta::notNull(array_)->capacity(),
                            "Cannot operate on an uninitialized iterator.");
                // return the data at our location in the array.
                return getAccess_(std::integral_constant<bool, is_const_iterator>());
            }
 
            DataReferenceType operator*() const {
                sparta_assert(index_ < sparta::notNull(array_)->capacity(),
                            "Cannot operate on an uninitialized iterator.");
                // return the data at our location in the array.
                return getAccess_(std::integral_constant<bool, is_const_iterator>());
            }
 
            value_type* operator->()
            {
                sparta_assert(index_ < sparta::notNull(array_)->capacity(),
                            "Cannot operate on an uninitialized iterator.");
                return std::addressof(getAccess_(std::integral_constant<bool, is_const_iterator>()));
            }
 
            const value_type* operator->() const
            {
                sparta_assert(index_ < sparta::notNull(array_)->capacity(),
                            "Cannot operate on an uninitialized iterator.");
                return std::addressof(getAccess_(std::integral_constant<bool, is_const_iterator>()));
            }
 
            ArrayIterator & operator++()
            {
                sparta_assert(index_ != sparta::notNull(array_)->invalid_entry_,
                            "Cannot operate on an uninitialized iterator.");
                if(is_aged_walk_) {
                    if(!sparta::notNull(array_)->getNextOldestIndex(index_)) {
                        index_ = (sparta::notNull(array_)->getOldestIndex());
                    }
                }
                else {
                    ++index_;
                    if(index_ == sparta::notNull(array_)->capacity()) {
                        index_ = 0;
                    }
                }
                if(is_circular_) { return *this; }
 
                // Aged iterators will act circular if the array is
                // filled with valid entries.
                if(is_aged_)
                {
                    // We've wrapped around -- we're done.
                    if(*this == sparta::notNull(array_)->abegin()) {
                        *this = sparta::notNull(array_)->aend();
                    }
                    else {
                        // If the iterator is not pointing to a valid
                        // entry, try again.
                        if(!isValid()) {
                            this->operator++();
                        }
                    }
                }
                else {
                    if(*this == sparta::notNull(array_)->begin()) {
                        // We've wrapped around and have hit begin.  We're at
                        // the end now.
                        *this = sparta::notNull(array_)->end();
                    }
                }
                return *this;
            }
 
            ArrayIterator operator++(int)
            {
                iterator old_iter(*this);
                // do the same functionality as the pre increment.
                operator++();
                // return the state before the increment.
                return old_iter;
            }
 
        private:
            uint32_t index_ = std::numeric_limits<uint32_t>::max(); 
            ArrayPointerType array_ = nullptr; 
            bool is_aged_      = false; 
            bool is_circular_  = false; 
            bool is_aged_walk_ = false; 
        };
 
        typedef ArrayIterator<false> iterator;
 
        typedef ArrayIterator<true>  const_iterator;
 
        iterator getCircularIterator(uint32_t idx=0)
        {
            constexpr bool is_aged = false;
            constexpr bool is_circular = true;
            constexpr bool is_aged_walk = false;
            return iterator(this, idx, is_aged, is_circular, is_aged_walk);
        }
 
        iterator getUnitializedIterator()
        {
            constexpr bool is_aged = false;
            constexpr bool is_circular = false;
            constexpr bool is_aged_walk = false;
            return iterator(this, invalid_entry_, is_aged, is_circular, is_aged_walk);
        }
 
       iterator begin() {
            constexpr bool is_aged = false;
            constexpr bool is_circular = false;
            constexpr bool is_aged_walk = false;
            return iterator(this, 0, is_aged, is_circular, is_aged_walk);
        }
 
        const_iterator begin() const {
            constexpr bool is_aged = false;
            constexpr bool is_circular = false;
            constexpr bool is_aged_walk = false;
            return const_iterator(this, 0, is_aged, is_circular, is_aged_walk);
        }
 
        iterator end() {
            constexpr bool is_aged = false;
            constexpr bool is_circular = false;
            constexpr bool is_aged_walk = false;
            return iterator(this, invalid_entry_, is_aged, is_circular, is_aged_walk);
        }
 
        const_iterator end() const {
            constexpr bool is_aged = false;
            constexpr bool is_circular = false;
            constexpr bool is_aged_walk = false;
            return const_iterator(this, invalid_entry_, is_aged, is_circular, is_aged_walk);
        }
 
        iterator abegin() {
            constexpr bool is_aged = true;
            constexpr bool is_circular = false;
            constexpr bool is_aged_walk = true;
            if(numValid()) {
                return iterator(this, getOldestIndex().getIndex(), is_aged, is_circular, is_aged_walk);
            }
            return  iterator(this, invalid_entry_, is_aged, is_circular, is_aged_walk);
        }
 
        const_iterator abegin() const {
            constexpr bool is_aged = true;
            constexpr bool is_circular = false;
            constexpr bool is_aged_walk = true;;
            if(numValid()) {
                return getOldestIndex();
            }
            return  const_iterator(this, invalid_entry_, is_aged, is_circular, is_aged_walk);
        }
 
        iterator aend() {
            constexpr bool is_aged = true;
            constexpr bool is_circular = false;
            constexpr bool is_aged_walk = true;
            return iterator(this, invalid_entry_, is_aged, is_circular, is_aged_walk);
        }
 
        const_iterator aend() const {
            constexpr bool is_aged = true;
            constexpr bool is_circular = false;
            constexpr bool is_aged_walk = true;
            return const_iterator(this, invalid_entry_, is_aged, is_circular, is_aged_walk);
        }
 
        Array(const std::string& name, 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);
 
        virtual ~Array() {
            clear();
        }
 
        const std::string & getName() const {
            return name_;
        }
 
        bool isValid(const uint32_t idx) const {
            return valid_index_set_.find(idx) != valid_index_set_.end();
        }
 
        const DataT& read(const uint32_t idx) const {
            sparta_assert(isValid(idx), "On Array " << name_
                        << " Cannot read from an invalid index. Idx:" << idx);
            return array_[idx].data;
        }
 
        DataT& access(const uint32_t idx) {
            sparta_assert(isValid(idx), "On Array " << name_
                        << " Cannot read from an invalid index. Idx:" << idx);
            return (array_[idx].data);
        }
 
        const_iterator getOldestIndex(const uint32_t nth=0) const
        {
            sparta_assert(ArrayT == ArrayType::AGED,
                        "Only AgedArray types have public member function getOldestIndex");
            sparta_assert(nth < num_valid_,
                        "The array does not have enough elements to find the nth oldest index");
 
            constexpr bool is_aged = true;
            constexpr bool is_circular = false;
            constexpr bool is_aged_walk = true;
 
            // Since our data_list_ always adds new items to the
            // front.  The oldest data is actually kept at the end of
            // the list.  We can iterate from the end to find the nth
            // oldest item.
            auto it = aged_list_.rbegin();
            uint32_t idx = invalid_entry_;
            for(uint32_t i = 0; i <= nth; ++i)
            {
                idx = *it;
                ++it;
            }
            // Double check that we are returning the user a valid
            // index.  We have failed if it isn't.
            sparta_assert(isValid(idx));
            return const_iterator(this, idx, is_aged, is_circular, is_aged_walk);
        }
 
        const_iterator getYoungestIndex(const uint32_t nth=0) const
        {
            sparta_assert(ArrayT == ArrayType::AGED,
                          "Only AgedArray types provide access to public member"
                          " function getYoungestIndex");
            sparta_assert(nth < num_valid_,
                          "The array does not have enough elements to find the nth youngest index");
            constexpr bool is_aged = true;
            constexpr bool is_circular = false;
            constexpr bool is_aged_walk = true;
 
            // Define idx, and set it to a value surely beyond the bounds of our array.
            uint32_t idx = invalid_entry_;
            auto it = aged_list_.begin();
            for(uint32_t i = 0; i <= nth; ++i)
            {
                idx = *it;
                ++it;
            }
            // Make sure we found something valid.
            sparta_assert(isValid(idx));
            return const_iterator(this, idx, is_aged, is_circular, is_aged_walk);
        }
 
        bool getNextOldestIndex(uint32_t & prev_idx) const {
            auto it = std::find(aged_list_.begin(), aged_list_.end(), prev_idx);
            if(it == aged_list_.begin()) {
                return false;
            }
            --it;
            prev_idx = *it;
            return true;
        }
 
        uint32_t getAge(const uint32_t idx) const {
            sparta_assert(ArrayT == ArrayType::AGED,
                          "Only AgedArray types provides age information");
            sparta_assert(isValid(idx));
            return array_[idx].age_rel_id;
        }
 
        const AgedList & getAgedList() const
        {
            sparta_assert(ArrayT == ArrayType::AGED);
            return aged_list_;
        }
 
        size_type capacity() const {
            return num_entries_;
        }
 
        size_type numValid() const {
            return num_valid_;
        }
 
        size_type size() const {
            return numValid();
        }
 
        size_type numFree() const {
            sparta_assert(num_entries_ >= num_valid_);
            return num_entries_ - num_valid_;
        }
 
        void erase(const iterator& iter) {
            sparta_assert(iter.isValid());
            erase(iter.getIndex());
        }
 
        void erase(const uint32_t& idx)
        {
            sparta_assert(isValid(idx), "Cannot invalidate a non valid index.");
            sparta_assert(num_valid_ > 0);
 
            // Just set the data to invalid.
            array_[idx].valid = false;
            --num_valid_;
 
            if constexpr (ArrayT == ArrayType::AGED)
            {
                // Remove the index from our aged list.
                aged_list_.erase(array_[idx].list_pointer);
                // Update the relative age IDs
                updateRelativeAge_();
            }
 
            // Update occupancy counter.
            if(utilization_)
            {
                utilization_->setValue(num_valid_);
            }
            array_[idx].~ArrayPosition();
            valid_index_set_.erase(idx);
        }
 
        void clear()
        {
            std::for_each(valid_index_set_.begin(), valid_index_set_.end(), [this](const auto index){
                array_[index].~ArrayPosition();
            });
            valid_index_set_.clear();
            aged_list_.clear();
            num_valid_ = 0;
            if(utilization_)
            {
                utilization_->setValue(num_valid_);
            }
        }
 
        void write(const uint32_t idx, const DataT& dat)
        {
            writeImpl_(idx, dat);
        }
 
        void write(const uint32_t idx, DataT&& dat)
        {
            writeImpl_(idx, std::move(dat));
        }
 
        void write(const iterator& iter, const DataT& dat)
        {
            write(iter.getIndex(), dat);
        }
 
        void write(const iterator& iter, DataT&& dat)
        {
            write(iter.getIndex(), std::move(dat));
        }
 
        bool isYounger(uint32_t lhs, uint32_t rhs)
        {
            sparta_assert(lhs != rhs);
            sparta_assert(lhs < num_entries_ && rhs < num_entries_,
                          "Cannot compare age on an index outside the bounds of the array");
            return array_[lhs].age_abs_id > array_[rhs].age_abs_id;
        }
 
        bool isOlder(uint32_t lhs, uint32_t rhs)
        {
            sparta_assert(lhs != rhs);
            sparta_assert(lhs < num_entries_ && rhs < num_entries_,
                          "Cannot compare age on an index outside the bounds of the array");
            return  array_[lhs].age_abs_id < array_[rhs].age_abs_id;
        }
 
        void enableCollection(TreeNode* parent)
        {
            // Create the collector instance of the appropriate type.
            sparta_assert(parent != nullptr);
            collector_.
                reset(new collection::IterableCollector<FullArrayType,
                                                        SchedulingPhase::Collection, true>
                      (parent, name_, this, capacity()));
 
            if constexpr (ArrayT == ArrayType::AGED) {
                age_collector_.reset(new collection::IterableCollector<AgedArrayCollectorProxy>
                                     (parent, name_ + "_age_ordered",
                                      &aged_array_col_, capacity()));
            }
        }
 
    private:
 
        class AgedArrayCollectorProxy
        {
        public:
            typedef uint32_t size_type;
 
            AgedArrayCollectorProxy(FullArrayType * array) : array_(array) { }
 
            typedef FullArrayType::iterator iterator;
 
            FullArrayType::iterator begin() const {
                return array_->abegin();
            }
 
            FullArrayType::iterator end() const {
                return array_->aend();
            }
 
            uint32_t size() const {
                return array_->size();
            }
 
        private:
            FullArrayType * array_ = nullptr;
        };
 
        const AgedList & getInternalAgedList_() const
        {
            sparta_assert(ArrayT == ArrayType::AGED);
            return aged_list_;
        }
 
        void updateRelativeAge_()
        {
            sparta_assert(ArrayT == ArrayType::AGED);
 
            // Since our data_list_ always adds new items to the
            // front.  The oldest data is actually kept at the end of
            // the list.  We can iterate from the end to find the nth
            // oldest item.
            auto it = aged_list_.rbegin();
            uint32_t idx = invalid_entry_;
            const uint32_t size = aged_list_.size();
            for(uint32_t i = 0; i < size; ++i)
            {
                idx = *it;
                ++it;
                // Double check that it's a valid index.
                sparta_assert(isValid(idx));
                // Upate the relaive age ID
                array_[idx].age_rel_id = i;
            }
        }
 
        template<typename U>
        void writeImpl_(const uint32_t idx, U&& dat)
        {
            sparta_assert(idx < num_entries_,
                        "Cannot write to an index outside the bounds of the array.");
 
            // We're overwriting an entry, clear valid and age information.
            if(SPARTA_EXPECT_FALSE(isValid(idx)))
            {
                --num_valid_;
                if constexpr (ArrayT == ArrayType::AGED) {
                    aged_list_.erase(array_[idx].list_pointer);
                }
            }
 
            // Since we are not timed. Write the data and validate it,
            // then do pipeline collection.
            new (array_.get() + idx) ArrayPosition(std::forward<U>(dat));
            valid_index_set_.insert(idx);
 
            // Timestamp the entry in the array, for fast age comparison between two indexes.
            array_[idx].age_abs_id = next_age_abs_id_;
            ++next_age_abs_id_;
 
            // Validate the entry and increase valids
            array_[idx].valid = true;
            ++num_valid_;
 
            // Maintain our age order if we are an aged array.
            if constexpr (ArrayT == ArrayType::AGED)
            {
                // To maintain aged items, add the index to the front
                // of a list.
                aged_list_.push_front(idx);
                array_[idx].list_pointer = aged_list_.begin();
                // Update the relative age IDs
                updateRelativeAge_();
            }
 
            // Update occupancy counter.
            if(utilization_)
            {
                utilization_->setValue(num_valid_);
            }
        }
 
        const std::string name_;
 
        struct DeleteToFree_{
            void operator()(void * x){
                free(x);
            }
        };
 
        // The size of our array.
        const size_type num_entries_;
        const uint32_t invalid_entry_{num_entries_ + 1};
 
        // The number of valid positions after last update.
        size_type num_valid_;
 
        // A vector that holds all of our data, contains valid and
        // invalid data.
        std::unique_ptr<ArrayPosition[], DeleteToFree_> array_ = nullptr;
 
        // Set to hold valid indexes at a time
        std::unordered_set<uint32_t> valid_index_set_ {};
 
        // The aged list.
        AgedList aged_list_;
        AgedArrayCollectorProxy aged_array_col_{this};
 
        // A counter used to assign a unique age id to every newly
        // written valid entry to the array for fast age comparisons
        // between indexes.
        uint64_t next_age_abs_id_;
 
        // Counters
        std::unique_ptr<sparta::CycleHistogramStandalone> utilization_;
 
        // Collectors
        std::unique_ptr<collection::IterableCollector<FullArrayType,
                                                      SchedulingPhase::Collection,
                                                      true>> collector_;
        std::unique_ptr<collection::IterableCollector<AgedArrayCollectorProxy> > age_collector_;
    };
 
    template<class DataT, ArrayType ArrayT>
    Array<DataT, ArrayT>::Array(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),
        num_entries_(num_entries),
        num_valid_(0),
        next_age_abs_id_(0)
    {
        // Set up some vector's of a default size
        // to work as the underlying implementation structures of our array.
        array_.reset(static_cast<ArrayPosition *>(malloc(sizeof(ArrayPosition) * num_entries_)));
 
        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));
        }
    }
 
}