ArchData.hpp

// <ArchData.hpp> -*- C++ -*-
 
#pragma once
 
#include <iostream>
#include <ios>
#include <iomanip>
#include <algorithm>
#include <math.h>
#include <list>
#include <cstring>
#include <unordered_map>
 
#include "sparta/utils/StaticInit.hpp"
#include "sparta/simulation/TreeNode.hpp"
#include "sparta/utils/TieredMap.hpp"
#include "sparta/utils/Utils.hpp"
#include "sparta/utils/ByteOrder.hpp"
#include "sparta/functional/ArchDataSegment.hpp"
#include "sparta/utils/SpartaException.hpp"
#include "sparta/utils/SpartaAssert.hpp"
 
 
namespace sparta
{
    class ArchData
    {
        ArchData(const ArchData &) = delete;
        ArchData(ArchData &&) = delete;
        ArchData& operator=(const ArchData &) = delete;
        ArchData& operator=(ArchData &&) = delete;
 
    public:
 
        friend class SpartaStaticInitializer;
 
        class Line;
 
 
        typedef ArchDataSegment::offset_type offset_type; 
        typedef offset_type line_idx_type; 
        typedef std::vector<ArchDataSegment*> SegmentList; 
 
        typedef std::list<Line*> LineList; 
        typedef TieredMap<line_idx_type, Line*> LineMap;
 
        typedef std::unordered_map<ArchDataSegment::ident_type, ArchDataSegment*> LayoutHelperMap;
 
        typedef std::vector<ArchDataSegment*> LayoutHelperVector;
 
 
 
        static const offset_type DEFAULT_LINE_SIZE = 512; // //! Default line size in bytes of an ArchData line.
 
        static const offset_type MAX_LINE_SIZE = 0x80000000;
 
        static const uint64_t DEFAULT_INITIAL_FILL = 0xcc;
 
        static const uint16_t DEFAULT_INITIAL_FILL_SIZE = 1;
 
        static const line_idx_type INVALID_LINE_IDX = std::numeric_limits<line_idx_type>::max();
 
 
 
        static void fillValue(uint8_t* buf, uint32_t size, uint64_t fill, uint16_t fill_val_size, uint16_t fill_pattern_offset=0) {
            switch(fill_val_size) {
                case 1:
                    memset(buf, fill, size); // Initialze with fill_val_size (pattern offset does not matter)
                    break;
                case 2:
                    fillWith_<uint16_t>(buf, size, static_cast<uint16_t>(fill), fill_pattern_offset);
                    break;
                case 4:
                    fillWith_<uint32_t>(buf, size, static_cast<uint32_t>(fill), fill_pattern_offset);
                    break;
                case 8:
                    fillWith_<uint64_t>(buf, size, static_cast<uint64_t>(fill), fill_pattern_offset);
                    break;
                default:
                    throw SpartaException("Failed to fill ArchData Line with fill value ")
                        << std::hex << fill << " because fill value size was " << std::dec
                        << fill_val_size;
            }
        }
 
        class Line
        {
        public:
 
            static constexpr char QUICK_CHECKPOINT_PREFIX[] = "<L>"; 
            static const uint32_t QUICK_CHECKPOINT_OFFSET_SIZE = 7; 
 
            Line(line_idx_type idx,
                 offset_type offset,
                 offset_type size,
                 uint64_t initial,
                 uint32_t initial_val_size,
                 uint8_t* pool_ptr=0) :
                idx_(idx),
                offset_(offset),
                size_(size),
                is_pool_(pool_ptr != 0),
                dirty_(true)
            {
                sparta_assert(size > 0);
                sparta_assert(isPowerOf2(size));
 
                if(is_pool_){
                    data_ = pool_ptr;
                }else{
                    alloc_data_.reset(new uint8_t[size]);
                    data_ = alloc_data_.get();
                    sparta_assert(data_ != 0);
                }
 
                fillWithInitial(initial, initial_val_size);
            }
 
            Line(const Line &) = delete;
            Line(Line&&) = delete;
            Line & operator=(const Line &) = delete;
 
            void updateFrom(const Line& other)
            {
                sparta_assert(size_ == other.size_);
                memcpy(data_, other.data_, size_);
                dirty_ = true;
            }
 
            void flagDirty() {
                dirty_ = true;
            }
 
            void fillWithInitial(uint64_t initial, uint32_t initial_val_size) {
                ArchData::fillValue(data_, size_, initial, initial_val_size, 0);
            }
 
            template <typename StorageT>
            void restore(StorageT& in) {
                in.copyLineBytes((char*)data_, size_);
                dirty_ = false;
            }
 
            template <typename StorageT>
            void save(StorageT& out) {
                out.writeLineBytes((char*)data_, size_);
                dirty_ = false;
            }
 
            line_idx_type getIdx() const {
                return idx_;
            }
 
            offset_type getOffset() const {
                return offset_;
            }
 
            offset_type getLayoutSize() const {
                return size_;
            }
 
            bool isDirty() const {
                return dirty_;
            }
 
 
            template <typename T, ByteOrder BO>
            T read(offset_type offset, uint32_t idx=0) const {
                offset_type loc = offset + (idx*sizeof(T));
                sparta_assert(loc + sizeof(T) <= size_,
                              "Read at ArchData::line offset 0x" << std::hex
                              << loc << " with size " << std::dec << sizeof(T) << " B");
 
                uint8_t* d = data_ + loc;
 
                T val = *reinterpret_cast<T*>(d);
                return reorder<T,BO>(val);
            }
 
            void read(offset_type offset, offset_type size, uint8_t* data) const {
                sparta_assert(offset + size <= size_,
                              "Read on ArchData::line offset 0x" << std::hex
                              << offset << " with size " << std::dec << size << " B");
 
                memcpy(data, data_ + offset, size);
            }
 
            template <typename T, ByteOrder BO>
            void write(offset_type offset, const T& t, uint32_t idx=0) {
                offset_type loc = offset + (idx*sizeof(T));
                sparta_assert(loc + sizeof(T) <= size_,
                              "Write on ArchData::line offset 0x" << std::hex
                              << loc << " with size " << std::dec << sizeof(T) << " B");
 
                uint8_t* d = data_ + loc;
 
                dirty_ = true;
                T& val = *reinterpret_cast<T*>(d);
                val = reorder<T,BO>(t);
            }
 
            void write(offset_type offset, offset_type size, const uint8_t* data) const {
                sparta_assert(offset + size <= size_,
                              "Read on ArchData::line offset 0x" << std::hex
                              << offset << " with size " << std::dec << size << " B");
 
                memcpy(data_ + offset, data, size);
                dirty_ = true;
            }
 
 
            const uint8_t* getDataPointer(offset_type offset) const {
                return data_ + offset;
            }
 
            uint8_t* getRawDataPtr(const offset_type offset) { return (data_ + offset); }
 
        private:
 
            line_idx_type idx_;  
            offset_type offset_; 
            offset_type size_;   
            bool is_pool_;       
            mutable bool dirty_; 
            uint8_t * data_ = nullptr;   
            std::unique_ptr<uint8_t[]> alloc_data_;      
 
        }; // class Line
 
 
 
        ArchData(TreeNode* owner_node=nullptr,
                 offset_type line_size=DEFAULT_LINE_SIZE,
                 uint64_t initial=DEFAULT_INITIAL_FILL,
                 uint16_t initial_val_size=DEFAULT_INITIAL_FILL_SIZE,
                 bool can_free_lines=true) :
            owner_node_(owner_node),
            line_size_(line_size),
            initial_(initial),
            initial_val_size_(initial_val_size),
            line_lsb_(0),
            line_mask_(0),
            num_lines_laid_out_(0),
            size_(0),
            is_laid_out_(false),
            layout_padding_waste_(0),
            layout_line_waste_(0),
            can_free_lines_(can_free_lines)
        {
            sparta_assert(initial_val_size_ > 0 && initial_val_size_ <= 8 && isPowerOf2(initial_val_size_),
                          "ArchData initial_val_size type must be a power of 2 between 1 and 8 inclusive, is "
                          << initial_val_size_);
            sparta_assert((initial_val_size_ == 8) || (initial >> (uint64_t)(8*initial_val_size_) == 0),
                          "ArchData initial val has nonzero bits above initial_val_size. initial val: "
                          << std::hex << initial_ << " initial_val_size:" << std::dec << initial_val_size_);
 
            if(line_size >= 1){
                sparta_assert(line_size <= MAX_LINE_SIZE);
                double tmp = log2(line_size);
                if(tmp != floor(tmp)){
                    SpartaException ex("line_size must be a power of 2, is ");
                    ex << line_size;
                    throw ex;
                }
                line_lsb_ = (offset_type)tmp;
                line_mask_ = ~((1 << line_lsb_) - 1);
 
                sparta_assert((1ul << line_lsb_) == line_size);
            }else{
                line_lsb_ = sizeof(offset_type) * 8;
                line_mask_ = (offset_type)0;
            }
 
            if(owner_node_){
                owner_node_->associateArchData_(this);
            }
 
            all_archdatas_->push_back(this);
        }
 
        virtual ~ArchData() {
 
            // Deregister self. This exists in case of failed construction
            if(owner_node_){
                owner_node_->disassociateArchData_(this);
            }
 
            // Remove from all_archdatas_
            auto itr = std::find(all_archdatas_->begin(), all_archdatas_->end(), this);
            sparta_abort(itr != all_archdatas_->end());
            all_archdatas_->erase(itr);
 
            // Do not delete segments!
            // It should be save for subclasses to free their registered
            // segments in their destructors.
 
            // Free all lines which are allocated
            for(LineMap::iterator eitr = line_map_.begin(); eitr != line_map_.end(); ++eitr){
                delete *eitr;
            }
        }
 
 
 
        void registerSegment(ArchDataSegment* seg) {
            if(is_laid_out_){
                throw SpartaException("This ArchData has already been laid out. New segments cannot be registered (segment id=")
                    << seg->getLayoutID() << ')';
            }
 
            checkDataSize(seg->getLayoutSize()); // Validate size of segment against size of a Line in this ArchData
 
            for(const ArchDataSegment* ls : seg_list_){
                if(ls == seg){
                    throw SpartaException("Segment @")
                        << std::hex << (void*)seg << " with id=0x" << seg->getLayoutID() << " already exists in ArchData @"
                        << (void*)this << std::dec;
                }
                if(seg->getLayoutID() != ArchDataSegment::INVALID_ID && ls->getLayoutID() == seg->getLayoutID()){
                    throw SpartaException("Segment id=")
                        << std::hex << "0x" << seg->getLayoutID() << " already exists in ArchData @"
                        << (void*)this << std::dec;
                }
            }
 
            seg_list_.push_back(seg);
        }
 
        const SegmentList getSegments() const { return seg_list_; }
 
        uint32_t getNumSegments() const { return seg_list_.size(); }
 
 
 
        void layout() {
 
            if(is_laid_out_){
                throw SpartaException("This ArchData has already been laid out");
            }
 
            LayoutHelperMap helper_map; // Map for lookup by ID
            LayoutHelperMap::const_iterator it;
 
            for(ArchDataSegment* seg : seg_list_){
                ArchDataSegment::ident_type lid = seg->getLayoutID();
                if(lid != ArchDataSegment::INVALID_ID){
                    // If ID is valid, add to helper map
                    it = helper_map.find(seg->getLayoutID());
                    if(it != helper_map.end()){
                        throw SpartaException("Found duplicate Segment id=")
                            << it->first << " in the same ArchData @" << (void*)this;
                    }
 
                    helper_map[seg->getLayoutID()] = seg; // Need to resolve IDs to names quickly
                }
            }
 
            for(ArchDataSegment*& seg : seg_list_){
                // Note: Segments being layed out are always less than the size
                // of a single line. This is enforced in registerSegment
                placeSegment_(seg, helper_map);
            }
 
            is_laid_out_ = true; // Disallow another layout of this ArchData
 
            // Write initial values for each segment
            for(ArchDataSegment* ls : seg_list_){
                ls->writeInitial();
            }
        }
 
        void layoutRange(offset_type size) {
 
            if(is_laid_out_){
                throw SpartaException("This ArchData has already been laid out");
            }
 
            if(seg_list_.size() != 0){
                throw SpartaException("This ArchData has ")
                    << seg_list_.size() << " segments so it cannot be layed out using layoutRange";
            }
 
            size_ = size; // Simply set the size an allow internal structures to use it
            is_laid_out_ = true; // Disallow another layout of this ArchData
        }
 
        Line& getLine(offset_type offset) {
            sparta_assert(containsAddress(offset),
                          "Cannot access this ArchData at offset: 0x"
                          << std::hex << offset << " ArchData size= "
                          << size_ << " B.");
 
            line_idx_type ln_idx = getLineIndex(offset);
            Line* ln;
            //LineMap::iterator lnitr;
            //if((lnitr = line_map_.find(ln_idx)) == line_map_.end()){
            LineMap::pair_t* lnitr;
            if((lnitr = line_map_.find(ln_idx)) == nullptr){
                ln = allocateLine_(ln_idx); // Adds to line
            }else{
                ln = lnitr->second;
                if(ln->getOffset() > offset){
                    ln = line_map_.find(ln_idx)->second;
                }
            }
            return *ln;
        }
 
        const Line* tryGetLine(offset_type offset) const {
            sparta_assert(containsAddress(offset),
                          "Cannot access this ArchData at offset: 0x"
                          << std::hex << offset << " ArchData size= "
                          << size_ << " B.");
 
            line_idx_type ln_idx = getLineIndex(offset);
            //LineMap::const_iterator lnitr;
            //if((lnitr = line_map_.find(ln_idx)) == line_map_.end()){
            const LineMap::pair_t* lnitr;
            if((lnitr = line_map_.find(ln_idx)) == nullptr){
                return nullptr;
            }
            return lnitr->second;
        }
 
 
        const LineMap& getLineMap() const {
            if(false == is_laid_out_){
                throw SpartaException("Cannot get ArchData lines map until layout completes");
            }
            return line_map_;
        }
 
        void clean() {
            if(false == is_laid_out_){
                throw SpartaException("Cannot clear ArchData until layout completes");
            }
 
            if(canFreeLines()){
                // Delete all lines allocated first (map contains pointers to lines)
                for(LineMap::iterator itr = line_map_.begin(); itr != line_map_.end(); ++itr){
                    delete *itr;
                }
 
                // Delete all structures within the map
                line_map_.clear();
            }else{
                // Overwrite all lines with initial bytes
                for(LineMap::iterator itr = line_map_.begin(); itr != line_map_.end(); ++itr){
                    (*itr)->fillWithInitial(initial_, initial_val_size_);
                }
 
            }
        }
 
        void reset() {
            clean(); // Checks for is_laid_out_
 
            // Write initial values for each segment
            for(ArchDataSegment* ls : seg_list_){
                ls->writeInitial();
            }
        }
 
        offset_type getLineSize() const {
            return line_size_;
        }
 
        line_idx_type getNumAllocatedLines() const {
            return line_map_.size();
        }
 
        line_idx_type getLineIndex(offset_type offset) const {
            return offset >> line_lsb_;
        }
 
        offset_type getLineOffset(line_idx_type idx) const {
            return line_size_ * idx;
        }
 
        bool canFreeLines() const { return can_free_lines_; }
 
 
 
        void checkCanAccess(offset_type offset, offset_type bytes) const {
            checkInSingleLine(offset, bytes);
            sparta_assert(offset + bytes <= size_,
                          "Generic access validity test on ArchData::line offset 0x" << std::hex
                          << offset << " with size " << std::dec << bytes << " B");
        }
 
        bool containsAddress(offset_type offset) const noexcept {
            return offset < size_;
        }
 
        void checkDataSize(offset_type size) const {
            static_assert(std::is_unsigned<offset_type>::value == true);
            if(size == 0){
                throw SpartaException("Segment size (")
                    << size << ") must be larger than 0 and less than line size ("
                    << line_size_ << ")";
            }
            if(line_size_ != 0 && size > line_size_){
                throw SpartaException("Segment size (")
                    << size << ") exceeds that of an ArchData line (" << line_size_ << ")";
            }
        }
 
        void checkSegment(offset_type offset, offset_type size) const {
 
            checkDataSize(size);
 
            checkInSingleLine(offset, size);
 
            if(__builtin_expect((offset + size) > size_, 0)){
                throw SpartaException("Segment end (0x")
                    << std::hex << offset+size << ") extends pased end of ArchData (0x"
                    << size_ << ") by " << std::dec << (offset + size) - size_ << " B";
            }
        }
 
        void checkInSingleLine(offset_type offset, offset_type size) const {
            if(__builtin_expect((offset + size) - (offset & line_mask_) > line_size_, 0)){
                throw SpartaException("Segment spans multiple ArchData lines: from ")
                    << getLineIndex(offset) << " to " << getLineIndex(offset+size-1);
            }
        }
 
 
 
        virtual void updateFrom(const ArchData& other)
        {
            // Iterate through the other's line map...
            for (LineMap::const_iterator itr = other.line_map_.begin(); itr != other.line_map_.end(); ++itr) {
                const Line* other_ln = *itr;
                if (other_ln != nullptr) {
                    // Attempt to find a corresponding line in this
                    line_idx_type other_idx = other_ln->getIdx();
                    LineMap::pair_t* pln = line_map_.find(other_idx);
                    if (pln != nullptr) {
                        // Found corresponding line, copy over the data
                        pln->second->updateFrom(*other_ln);
                    } else {
                        // Allocate a new line in this
                        Line* ln = allocateLine_(other_idx);
                        ln->updateFrom(*other_ln);
                    }
                }
            }
        }
 
 
 
        template <typename StorageT>
        void save(StorageT& out) {
            // Iterate lines and restore
            sparta_assert(out.good(),
                          "Saving delta checkpoint to bad ostream for " << getOwnerNode()->getLocation());
 
            for(LineMap::iterator itr = line_map_.begin(); itr != line_map_.end(); ++itr){
                Line* ln = *itr;
                if(ln != nullptr && ln->isDirty()){
                    out.beginLine(ln->getIdx());
                    ln->save(out);
                }
            }
            out.endArchData();
        }
 
        template <typename StorageT>
        void saveAll(StorageT& out) {
            sparta_assert(out.good(),
                          "Saving delta checkpoint to bad ostream for " << getOwnerNode()->getLocation());
 
            for(LineMap::iterator itr = line_map_.begin(); itr != line_map_.end(); ++itr){
                Line* ln = *itr;
                if(ln != nullptr){
                    out.beginLine(ln->getIdx());
                    ln->save(out);
                }
            }
            out.endArchData();
        }
 
        template <typename StorageT>
        void restore(StorageT& in) {
            // Iterate lines and restore
            sparta_assert(in.good(),
                          "Encountered bad checkpoint data (invalid stream) for " << getOwnerNode()->getLocation());
 
            while(1){
                line_idx_type ln_idx = in.getNextRestoreLine();
                if(ln_idx == INVALID_LINE_IDX){
                    break; // Done with this ArchData
                }
                Line& ln = getLine(ln_idx * line_size_);
                ln.restore(in);
            }
        }
 
        template <typename StorageT>
        void restoreAll(StorageT& in) {
            // Fresh, empty state, ready to be overwritten
            clean();
 
            restore(in);
        }
 
 
 
        const TreeNode* getOwnerNode() const { return owner_node_; }
 
        void setOwnerNode(TreeNode *node)
        {
            sparta_assert(owner_node_ == nullptr, "Owner already set");
 
            owner_node_ = node;
            if (owner_node_) {
                owner_node_->associateArchData_(this);
            }
        }
 
        bool isLaidOut() const { return is_laid_out_; }
 
        offset_type getSize() const {
            if(false == is_laid_out_){
                throw SpartaException("Cannot get layout size until layout completes");
            }
            return size_;
        }
 
        uint64_t getInitial() const {
            return initial_;
        }
 
        uint32_t getInitialValSize() const {
            return initial_val_size_;
        }
 
        uint32_t getTotalWaste() const {
            return layout_padding_waste_ + layout_line_waste_;
        }
 
        uint32_t getPaddingWaste() const {
            return layout_padding_waste_;
        }
 
        uint32_t getLineWaste() const {
            return layout_line_waste_;
        }
 
        static bool compareSegmentOffsets(const ArchDataSegment* s1, const ArchDataSegment* s2){
            if(s1->getOffset() < s2->getOffset()){
                return true; // S1 < S2
            }else if(s1->getOffset() > s2->getOffset()){
                return false; // S1 > S2
            }
 
            if(s1->getLayoutSize() >= s2->getLayoutSize()){
                return true; // S1 larger than or equal in size to S2 so it should be considered before
            }
            return false; // S1 is smaller than S2, so it should be considered after
        }
 
        void dumpLayout(std::ostream& o) const {
            if(false == is_laid_out_){
                throw SpartaException("Cannot dump ArchData layout until layout completes");
            }
 
            SegmentList sorted = seg_list_;
            std::sort(sorted.begin(), sorted.end(), compareSegmentOffsets);
 
            offset_type last_line_off = 0; // offset of last line
            offset_type last_end = 0; // end of last segment (expected start of next)
 
            dumpLayout_(o, sorted, last_line_off, last_end, true);
        }
 
        std::vector<std::string> getLineStates() const {
            std::vector<std::string> result;
            for(LineMap::const_iterator itr = line_map_.begin(); itr != line_map_.end(); ++itr){
                const Line* ln = *itr;
                std::stringstream state;
                state << std::setw(5) << std::hex << ln->getIdx()
                      << ":";
                if(ln != 0){
                    if(ln->isDirty()){
                        state << 'd';
                    }else{
                        state << 'c';
                    }
                }else{
                    state << '!';
                }
                result.push_back(state.str());
            }
            return result;
        }
 
        uint64_t getNumTiers() const {
            return line_map_.getNumTiers();
        }
 
 
 
        static const std::vector<const ArchData*> getAllArchDatas() {
            return *all_archdatas_;
        }
 
 
    private:
 
        template <typename FillT>
        static void fillWith_(uint8_t* buf, uint32_t size, FillT fill, uint16_t buf_offset=0) {
            sparta_assert(buf != nullptr,
                          "Null buf given");
            sparta_assert(buf_offset < sizeof(FillT),
                          "Cannot have a buf_offset larger than FillT size. Must be buffer offset % fill size");
 
            // Realign the pattern so it coincides with the misalignment of buf
            const FillT shifted_fill = (fill >> (buf_offset * 8)) | (fill << ((sizeof(FillT) - buf_offset) * 8));
 
            // Handle case where buf is smaller than fill pattern
            if(sizeof(FillT) >= size) {
                // Line size is 1,2,4 bytes and fill value is same size or
                // smaller. Just copy what will fit
                memcpy(buf, static_cast<const void*>(&shifted_fill), size);
                return;
            }
 
            uint8_t* ptr = buf;
 
            // Address of first byte followinf buf which is not written
            const uint8_t* const end = buf + size;
            sparta_assert(end > buf,
                          "buf (" << (void*)buf << ") was too large and adding size (" << size << ") rolled over to 0");
 
            // Stop point before writing last, partial value
            const uint8_t* const stop = end - sizeof(FillT);
 
            // Write entire fill pattern up until stop point to prevent overrun
            while(ptr < stop) {
                // Line size is > fill value size. Since line size is power
                // of 2, a line size greater than some power of two integer size is guaranteed
                // to fit a whole number of that integer
                memcpy(static_cast<void*>(ptr), static_cast<const void*>(&shifted_fill), sizeof(FillT));
                ptr += sizeof(FillT);
                sparta_assert(ptr >= buf, "ptr overflowed when adding fill size (" << sizeof(FillT) << ")");
            }
 
            // Write remainder of buffer size
            int32_t rem = end - ptr;
            sparta_assert(rem <= (int32_t)sizeof(FillT) && rem >= 0,
                          "fillWith_ remainder size was 0x" << std::hex << rem
                          << " ptr=" << (void*)ptr << " end=" << (const void*)end
                          << " sizeof(FillT)=" << sizeof(FillT));
            sparta_assert(ptr != nullptr,
                          "Somehow encountered a null pointer during arithmetic based on a pointer at " << (void*) buf);
 
            if(rem > 0) {
                // Remaining size is 1,2, or 4 bytes and rem fill value is same size or
                // smaller. Just copy what will fit
 
                memcpy(static_cast<void*>(ptr), static_cast<const void*>(&shifted_fill), rem);
            }
        }
 
        void dumpLayout_(std::ostream& o,
                         SegmentList& sorted,
                         offset_type last_line_off,
                         offset_type last_end,
                         bool show_line_nums) const {
 
            // Print first line start
            if(show_line_nums){
                o << 'x' << std::hex << std::setw(5) << std::right << (last_end & line_mask_) << ": " << std::dec;
            }else{
                o << "     \": "; // no line num (implies same as above)
            }
 
            SegmentList::const_iterator it;
            std::vector<ArchDataSegment*> nestings;
            for(it = sorted.begin(); it != sorted.end(); ++it){
                offset_type off = (*it)->getOffset();
 
                // End line of offset moved to next
                if(last_line_off != (off & line_mask_)){
                    // Print skipped bytes at end of the line
                    dumpSkippedBytes_(o, (off & line_mask_) - last_end, true, true);
                    o << std::endl;
 
                    // Handle nestings
                    if(nestings.size() > 0){
                        dumpLayout_(o, nestings, last_line_off, last_line_off, false);
                    }
                    nestings.clear();
 
                    // Print new line start
                    if(show_line_nums){
                        o << 'x' << std::hex << std::setw(5) << std::right << (last_end & line_mask_) << ": " << std::dec;
                    }else{
                        o << "     \": "; // no line num (implies same as above)
                    }
 
                    last_line_off = (off & line_mask_);
                    last_end = last_line_off;
                }
 
                if(off < last_end){
                    nestings.push_back(*it);
                    continue; // Do not print, duplicate (nested)
                }else{
                    // Print skipped bytes betweeen last seg and this
                    offset_type jump = off - last_end;
                    dumpSkippedBytes_(o, jump, false, false);
                }
 
                offset_type size = (*it)->getLayoutSize();
                if(size == 1){
                    o << "|"; // Only 1B
                }else if(size == 2){
                    o << "|2"; // Only 2B
                }else{
                    o << "|";
                    for(offset_type i=1; i<size; ++i){
                        if(i == (offset_type)(size/2)){
                            o << std::left << std::dec;
                            if(size >= 1000){
                                o << std::setw(4) << size; // 4-char size
                            }else if(size >= 100){
                                o << std::setw(3) << size; // 3-char size
                            }else if(size >= 10){
                                o << std::setw(2) << size; // 2-char size
                            }else{
                                o << std::setw(1) << size; // 1-char size
                            }
                        }else{
                            if(size >= 1000 && (i > (size/2)+1 && i < (size/2)+3)){
                                // More than 4 digits printed for size. Skip
                            }else if(size >= 100 && (i > (size/2)+1 && i < (size/2)+2)){
                                // Print nothing. 3-digit size was just printed
                            }else if(size >= 10 && i == (size/2)+1){
                                // Print nothing. 2-digit size was just printed
                            }else{
                                o << '-'; // 1 char per byte.
                            }
                        }
                    } // for( ... size ... )
                } // else // if(size == 1)
 
                last_end = off + size;
            }
 
            // Complete final line
            if((last_end & ~line_mask_) == 0){
                o << '|' << std::endl;
            }else{
                // Print skipped bytes at end of the line
                offset_type leftover = line_size_ - (last_end & ~line_mask_);
                dumpSkippedBytes_(o, leftover, true, true);
                o << std::endl;
            }
 
            // Handle nestings on final line
            if(nestings.size() > 0){
                dumpLayout_(o, nestings, last_line_off, last_line_off, false);
            }
            nestings.clear();
        }
 
        void dumpSkippedBytes_(std::ostream& o,
                               offset_type num,
                               bool condense,
                               bool end_row) const {
            if(num == 0){
                // Print nothing yet
            }else if(num == 1){
                o << '/';
            }else if(num <= 16 || !condense){
                o << '|';
                for(offset_type i=1; i < num; ++i){
                    //o << "+";
                    o << " ";
                }
            }else{
                //o << "|+++" << std::dec << num << " ";
                o << "|+  " << std::dec << num << " ";
            }
 
            if(end_row){
                o << '|';
            }
        }
 
        Line* allocateLine_(line_idx_type idx) {
            if(idx * line_size_ > size_){
                throw SpartaException("Cannot allocate Line at idx ")
                    << idx
                    << " because idx*line_size is 0x"
                    << std::hex << (idx * line_size_)
                    << "and the current ArchData size is only 0x" << size_;
            }
 
            // This test introduces a bit of overhead and should be removed
#ifndef NDEBUG
            //if(line_map_.find(idx) != line_map_.end()){
            if(line_map_.find(idx) != nullptr){
                throw SpartaException("Line is already allocated at index ") << idx;
            }
#endif // NDEBUG
 
            // Allocate infinite-length lines
            if(0 == line_size_){
                if(idx != 0){
                    throw SpartaException("Cannot allocate a line at index other than 0 when ArchData line size is 0 (infinite)");
                }
                sparta_assert(line_map_.size() == 0); // Cannot yet have a line
 
                Line* ln = new Line(0, 0, size_, initial_, initial_val_size_);
                //lines_.push_back(ln);
                line_map_[0] = ln;
                return ln;
            }
 
            // Allocate finite-length lines
            offset_type ln_off = getLineOffset(idx);
 
            // Always use the full line size instead of trying to compute the
            // bytes leftover. When a line is being allocated, we may not know
            // the full size.
            Line* ln = new Line(idx, ln_off, line_size_, initial_, initial_val_size_);
            //LineList::iterator lnitr = lines_.begin();
            //for(; lnitr != lines_.end(); ++lnitr){
            //    if((*lnitr)->getIdx() > idx){
            //        break;
            //    }
            //}
            //lines_.insert(lnitr, ln);
            line_map_[idx] = ln;
            return ln;
        }
 
 
        void placeSegment_(ArchDataSegment* seg,
                           LayoutHelperMap& helper_map,
                           uint32_t depth=0) {
 
            sparta_assert(seg != 0); // Segment should never be NULL
 
            if(seg->isPlaced()){
                /*
                  for(uint32_t i=0; i<depth; ++i){ std::cout << " "; }
                  std::cout << "seg " << std::dec << seg->getLayoutID() << " is already placed @ 0x"
                  << std::hex << seg->getOffset() << std::dec << std::endl;
                */
                return; // Done
            }
 
 
            offset_type placement = 0; // Where to place the segment in the whole ArchData (calculated below)
            const offset_type size = seg->getLayoutSize(); // Size of the segment
            LayoutHelperMap::iterator it;
 
            if(seg->getSubsetOf() != ArchDataSegment::INVALID_ID){
                // Place within another segment (subset)
 
                ArchDataSegment::ident_type sub_of = seg->getSubsetOf();
 
                //for(uint32_t i=0; i<depth; ++i){ std::cout << " "; }
                //std::cout << "seg " << std::dec << seg->getLayoutID() << " is subset @ +0x"
                //          << std::hex << seg->getSubsetOffset() << "; attempting to place base: "
                //          << std::dec << sub_of << std::endl;
 
                // Find parent
                it = helper_map.find(sub_of);
                if(it == helper_map.end()){
                    throw SpartaException("A Segment with identifier ")
                        << seg->getLayoutID() << " claimed to be a "
                        << "subset of Segment with identifier "
                        << sub_of << ", which does not exist in this ArchData";
                }
                ArchDataSegment* parent_seg = it->second;
                sparta_assert(parent_seg->getLayoutID() == sub_of); // Parent must match expected ID
 
                // Place parent first
                placeSegment_(it->second, helper_map, depth+1);
                sparta_assert(parent_seg->isPlaced()); // Parent must be placed at this point
 
                if(seg->getLayoutSize() + seg->getSubsetOffset() > parent_seg->getLayoutSize()){
                    throw SpartaException("Segment id=")
                        << seg->getLayoutID() << " had size 0x" << std::hex << seg->getLayoutSize()
                        << " and subset offset 0x" << std::hex << seg->getSubsetOffset()
                        << " which makes it larger than the parent id=" << std::dec
                        << parent_seg->getLayoutID() << " with size " << std::hex
                        << parent_seg->getLayoutSize() << " of which it is a child";
                }
                placement = parent_seg->getOffset() + seg->getSubsetOffset();
            }else{
                // Place at the root (not subset)
 
                // Word-alignment is probably important for reinterpret casting
                // Pad to the next word. size_ refers to ArchData size and offset of
                // next data.
                // Note that this only applies to segments placed at the root.
                if(size_ % HOST_INT_SIZE != 0){
                    offset_type delta = HOST_INT_SIZE - (size_ % HOST_INT_SIZE);
                    layout_padding_waste_ += delta;
                    size_ += delta;
                }
 
                // Ensure there is an ArchData line of appropriate size.
                // NOTE that segments CANNOT span lines.
                offset_type start_line_addr = size_ & line_mask_;
                offset_type end_line_addr = (size_ + size - 1) & line_mask_;
                if(start_line_addr != end_line_addr){
                    // Needs to be moved to the next line
                    sparta_assert(end_line_addr > start_line_addr); // Cannot allow overflow of offset_type. TODO: Test overflow case?
 
                    offset_type next = (size_ & line_mask_) + line_size_; // start of next line
                    layout_line_waste_ += next - size_; // Waste some bytes
 
                    // std::cout << "Exceeds lines at offset 0x" << std::hex << size_ << std::dec << " + " << size << " B" << std::endl;
 
                    size_ = next;
                    //lines_.push_back(0); // NULL pointer
                    ++num_lines_laid_out_;
                }else if(start_line_addr >= num_lines_laid_out_ * line_size_){//(lines_.size() * line_size_)){
                    // Starts naturally on a new line
                    sparta_assert((size_ & ~line_mask_) == 0); // Must start at beginning of line
 
                    // std::cout << "Added next line at offset 0x" << std::hex << size_ << std::dec << std::endl;
 
                    //lines_.push_back(0); // NULL pointer
                    ++num_lines_laid_out_;
                }
 
                placement = size_;
                size_ += size; // Increase size so that the segment can be placed.
                sparta_assert((placement % HOST_INT_SIZE) == 0); // Just to be sure
            }
 
            seg->place(placement);
 
        }
 
    private:
 
        TreeNode *owner_node_ = nullptr;
 
        offset_type   line_size_;
 
        const uint64_t initial_;
 
        const uint32_t initial_val_size_;
 
        offset_type   line_lsb_;
 
        offset_type   line_mask_;
 
        uint32_t      num_lines_laid_out_;
 
        LineMap       line_map_;
 
        SegmentList   seg_list_;
 
        offset_type   size_;
 
        bool          is_laid_out_;
 
        uint32_t      layout_padding_waste_;
 
        uint32_t      layout_line_waste_;
 
        bool          can_free_lines_;
 
        static std::vector<const ArchData*> *all_archdatas_;
 
    }; // class ArchData
 
} // namespace sparta
 
 
#define SPARTA_ARCHDATA_BODY