FastList.hpp

Go to the documentation of this file.

// <FastList.hpp> -*- C++ -*-
 
 
#pragma once
 
#include <vector>
#include <limits>
#include <iostream>
#include <exception>
#include <iterator>
#include <cinttypes>
#include <cassert>
#include <cstddef>
#include <type_traits>
 
#include "sparta/utils/IteratorTraits.hpp"
#include "sparta/utils/SpartaAssert.hpp"
 
namespace sparta::utils
{
    template <class DataT>
    class FastList
    {
        struct Node
        {
            using NodeIdx = int;
 
            // Where this node is in the vector
            const NodeIdx index;
 
            // Points to the next element or the next free
            // element if this node has been removed.
            NodeIdx next = -1;
 
            // Points to the previous element.
            NodeIdx prev = -1;
 
            // Stores the memory for an instance of 'T'.
            // Use placement new to construct the object and
            // manually invoke its dtor as necessary.
            alignas(DataT) std::byte type_storage[sizeof(DataT)];
 
            Node(NodeIdx _index) :
                index(_index)
            {}
        };
 
        typename Node::NodeIdx advanceNode_(typename Node::NodeIdx node_idx) const {
            typename Node::NodeIdx ret_idx = (node_idx == -1 ? -1 : nodes_[node_idx].next);
            return ret_idx;
        }
 
        auto getStorage(typename Node::NodeIdx node_idx) {
            return &nodes_[node_idx].type_storage;
        }
 
        auto getStorage(typename Node::NodeIdx node_idx) const {
            return &nodes_[node_idx].type_storage;
        }
 
    public:
        using value_type = DataT; 
 
        template<bool is_const = true>
        class NodeIterator : public sparta::utils::IteratorTraits<std::forward_iterator_tag, value_type>
        {
            typedef std::conditional_t<is_const, const value_type &, value_type &> RefIteratorType;
            typedef std::conditional_t<is_const, const value_type *, value_type *> PtrIteratorType;
            typedef std::conditional_t<is_const, const FastList *, FastList *>     FastListPtrType;
        public:
 
            NodeIterator() = default;
 
            NodeIterator(const NodeIterator<false> & iter) :
                flist_(iter.flist_),
                node_idx_(iter.node_idx_)
            {}
 
            bool isValid() const { return (node_idx_ != -1); }
 
            PtrIteratorType operator->()       {
                assert(isValid());
                return reinterpret_cast<PtrIteratorType>(flist_->getStorage(node_idx_));
            }
 
            PtrIteratorType operator->() const {
                assert(isValid());
                return reinterpret_cast<PtrIteratorType>(flist_->getStorage(node_idx_));
            }
 
            RefIteratorType operator* ()       {
                assert(isValid());
                return *reinterpret_cast<PtrIteratorType>(flist_->getStorage(node_idx_));
            }
 
            RefIteratorType operator* () const {
                assert(isValid());
                return *reinterpret_cast<PtrIteratorType>(flist_->getStorage(node_idx_));
            }
 
            int getIndex() const { return node_idx_; }
 
            NodeIterator & operator++()
            {
                assert(isValid());
                node_idx_ = flist_->advanceNode_(node_idx_);
                return *this;
            }
 
            NodeIterator operator++(int)
            {
                NodeIterator orig = *this;
                assert(isValid());
                node_idx_ = flist_->advanceNode_(node_idx_);
                return orig;
            }
 
            bool operator!=(const NodeIterator &rhs)
            {
                return (rhs.flist_ != flist_) ||
                    (rhs.node_idx_ != node_idx_);
            }
 
            bool operator==(const NodeIterator & node) const noexcept {
                return (node.flist_ == flist_) && (node.node_idx_ == node_idx_);
            }
 
            NodeIterator& operator=(const NodeIterator &rhs) = default;
            NodeIterator& operator=(      NodeIterator &&rhs) = default;
 
        private:
            friend class FastList<DataT>;
 
            NodeIterator(FastListPtrType flist, typename Node::NodeIdx node_idx) :
                flist_(flist),
                node_idx_(node_idx)
            { }
 
            FastListPtrType flist_ = nullptr;
            typename Node::NodeIdx node_idx_ = -1;
        };
 
        FastList(size_t size) :
            FastList(size, size)
        {}
 
        FastList(size_t initial_size, size_t max_size) :
            max_size_(max_size)
        {
            sparta_assert(initial_size != 0,
                          "Cannot create a sparta::utils::FastList of size 0");
            sparta_assert(initial_size <= max_size,
                          "sparta::utils::FastList initial size " << initial_size <<
                          " is larger than its max size " << max_size);
            // -1 is the end/free sentinel, so the ceiling must fit in NodeIdx.
            sparta_assert(max_size <= static_cast<size_t>(std::numeric_limits<typename Node::NodeIdx>::max()),
                          "sparta::utils::FastList max size " << max_size <<
                          " exceeds the addressable node index range");
            int node_idx = 0;
            nodes_.reserve(max_size_);
            for(size_t i = 0; i < initial_size; ++i) {
                Node n(node_idx);
                n.prev = node_idx - 1;
                n.next = node_idx + 1;
                ++node_idx;
                nodes_.emplace_back(n);
            }
            nodes_.back().next = -1;
        }
 
        ~FastList() { clear(); }
 
        using iterator       = NodeIterator<false>;  
        using const_iterator = NodeIterator<true>;   
 
        iterator begin() {
            return iterator(this, first_node_);
        }
 
        const_iterator begin() const {
            return const_iterator(this, first_node_);
        }
 
        iterator       end()       { return iterator(this, -1); }
 
        const_iterator end() const { return const_iterator(this, -1); }
 
        DataT & front() { return *begin(); }
 
        const DataT & front() const { return *begin(); }
 
        bool   empty()    const { return size_ == 0; }
 
        size_t size()     const { return size_; };
 
        size_t max_size() const { return max_size_; };
 
        // Modifiers
        void clear() noexcept {
            const auto my_end = end();
            for(auto it = begin(); it != my_end;) {
                erase(it++);
            }
        }
 
        iterator erase(const const_iterator & entry)
        {
            const auto node_idx = entry.getIndex();
            auto & node_to_erase = nodes_[node_idx];
            reinterpret_cast<DataT*>(&node_to_erase.type_storage)->~DataT();
            int next_elem = -1;
 
            if(first_node_ == node_idx) {
                first_node_ = node_to_erase.next;
            }
            if(last_node_ == node_idx) {
                last_node_ = node_to_erase.prev;
            }
 
            if(SPARTA_EXPECT_FALSE(node_to_erase.next != -1))
            {
                auto & next_node = nodes_[node_to_erase.next];
                next_node.prev = node_to_erase.prev;
                next_elem = node_to_erase.next;
            }
 
            if(SPARTA_EXPECT_FALSE(node_to_erase.prev != -1))
            {
                auto & prev_node = nodes_[node_to_erase.prev];
                prev_node.next = node_to_erase.next;
            }
 
            node_to_erase.prev = -1;
            node_to_erase.next = -1;
            if(SPARTA_EXPECT_TRUE(free_head_ != -1)) {
                nodes_[free_head_].prev = node_idx;
                node_to_erase.next = free_head_;
            }
            free_head_ = node_idx;
            --size_;
            return iterator(this, next_elem);
        }
 
        template<class ...ArgsT>
        iterator emplace(const const_iterator & pos, ArgsT&&...args)
        {
            ensureFreeNode_();
            const auto index_pos = pos.getIndex();
 
            // If the index pos is -1, it's either end() or begin() on
            // an empty list.  Just emplace_back (or front, don't matter)
            if(index_pos == -1) {
                return emplace_back(std::forward<ArgsT>(args)...);
            }
 
            auto & new_node = nodes_[free_head_];
            free_head_ = new_node.next;
            new (&new_node.type_storage) DataT(args...);
            // Update pointers.  Start with a clean slate
            new_node.next = -1;
            new_node.prev = -1;
 
            // Insert before the given pt
            auto & insert_pt = nodes_[index_pos];
            new_node.next = insert_pt.index;
            new_node.prev = insert_pt.prev;
            insert_pt.prev = new_node.index;
            if(new_node.prev != -1) {
                // update the previous node's next
                nodes_[new_node.prev].next = new_node.index;
            }
 
            if((first_node_ == index_pos) || (first_node_ == -1))
            {
                first_node_ = new_node.index;
            }
            ++size_;
 
            return iterator(this, new_node.index);
        }
 
        template<class ...ArgsT>
        iterator emplace_front(ArgsT&&...args)
        {
            ensureFreeNode_();
 
            auto & new_node = nodes_[free_head_];
            free_head_ = new_node.next;
            new (&new_node.type_storage) DataT(args...);
 
            // Update pointers.  Start with a clean slate
            new_node.next = -1;
            new_node.prev = -1;
            if(SPARTA_EXPECT_TRUE(first_node_ != -1))
            {
                auto & old_first = nodes_[first_node_];
                old_first.prev = new_node.index;
                new_node.next = old_first.index;
            }
            first_node_ = new_node.index;
            if(SPARTA_EXPECT_FALSE(last_node_ == -1)) {
                last_node_ = first_node_;
            }
 
            ++size_;
            return iterator(this, new_node.index);
        }
 
        template<class ...ArgsT>
        iterator emplace_back(ArgsT&&...args) {
            ensureFreeNode_();
 
            auto & new_node = nodes_[free_head_];
            free_head_ = new_node.next;
            new (&new_node.type_storage) DataT(args...);
 
            // Update pointers.  Start with a clean slate
            new_node.next = -1;
            new_node.prev = -1;
            if(SPARTA_EXPECT_TRUE(last_node_ != -1))
            {
                auto & old_last = nodes_[last_node_];
                old_last.next = new_node.index;
                new_node.prev = old_last.index;
            }
            last_node_ = new_node.index;
            if(SPARTA_EXPECT_FALSE(first_node_ == -1)) {
                first_node_ = last_node_;
            }
 
            ++size_;
            return iterator(this, new_node.index);
        }
 
        template<class ...ArgsT>
        iterator insert(const const_iterator & pos, ArgsT&&...args) {
            return emplace(pos, args...);
        }
 
        void pop_back() {
            sparta_assert(last_node_ != -1,
                          "Can't pop_back on an empty list");
            erase(iterator(this, last_node_));
        }
 
        void pop_front() {
            sparta_assert(first_node_ != -1,
                          "Can't pop_front on an empty list");
            erase(iterator(this, first_node_));
        }
 
    private:
 
        // Friendly printer
        friend std::ostream & operator<<(std::ostream & os, const FastList<DataT> & fl)
        {
            int next_node = fl.first_node_;
            if(next_node == -1) {
                os << "<empty>" << std::endl;
            }
            else {
                int index = fl.size_ - 1;
                do
                {
                    const auto & n = fl.nodes_[next_node];
                    os << index << " elem="    << *reinterpret_cast<const DataT*>(&n.type_storage)
                       << " n.next=" << n.next
                       << " n.prev=" << n.prev << std::endl;
                    next_node = n.next;
                    --index;
                } while(next_node != -1);
            }
            return os;
        }
 
        void ensureFreeNode_() {
            if(SPARTA_EXPECT_TRUE(free_head_ != -1)) { return; }
            sparta_assert(nodes_.size() < max_size_,
                          "FastList is out of element room (max_size=" << max_size_ << ")");
            // Never reallocates: the ctor reserved max_size_.
            const typename Node::NodeIdx new_idx =
                static_cast<typename Node::NodeIdx>(nodes_.size());
            nodes_.emplace_back(new_idx);
            free_head_ = new_idx;
        }
 
        // Stores all the nodes.
        std::vector<Node> nodes_;
        const size_t max_size_;  
 
        int free_head_  = 0;  
        int first_node_ = -1; 
        int last_node_  = -1; 
        size_t size_    = 0;  
    };
}