nextpnr/common/kernel/indexed_store.h

/*
 *  nextpnr -- Next Generation Place and Route
 *
 *  Copyright (C) 2021-22  gatecat <gatecat@ds0.me>
 *
 *  Permission to use, copy, modify, and/or distribute this software for any
 *  purpose with or without fee is hereby granted, provided that the above
 *  copyright notice and this permission notice appear in all copies.
 *
 *  THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 *  WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 *  MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 *  ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 *  WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 *  ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 *  OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 *
 */

#ifndef INDEXED_STORE_H
#define INDEXED_STORE_H

#include <algorithm>
#include <limits>
#include <type_traits>
#include <vector>

#include "nextpnr_assertions.h"
#include "nextpnr_namespaces.h"

NEXTPNR_NAMESPACE_BEGIN

template <typename T> struct store_index
{
    int32_t m_index = -1;
    store_index() = default;
    explicit store_index(int32_t index) : m_index(index) {};
    int32_t idx() const { return m_index; }
    void set(int32_t index) { m_index = index; }
    bool empty() const { return m_index == -1; }
    bool operator==(const store_index<T> &other) const { return m_index == other.m_index; }
    bool operator!=(const store_index<T> &other) const { return m_index != other.m_index; }
    bool operator<(const store_index<T> &other) const { return m_index < other.m_index; }
    unsigned int hash() const { return m_index; }

    operator bool() const { return !empty(); }
    operator int() const = delete;
    bool operator!() const { return empty(); }
};

// "Slotted" indexed object store
template <typename T> class indexed_store
{
  private:
    // This should move to using std::optional at some point
    class slot
    {
      private:
        alignas(T) unsigned char storage[sizeof(T)];
        int32_t next_free;
        bool active;
        inline T &obj() { return reinterpret_cast<T &>(storage); }
        inline const T &obj() const { return reinterpret_cast<const T &>(storage); }
        friend class indexed_store<T>;

      public:
        slot() : next_free(std::numeric_limits<int32_t>::max()), active(false) {};
        slot(slot &&other) : next_free(other.next_free), active(other.active)
        {
            if (active)
                ::new (static_cast<void *>(&storage)) T(std::move(other.obj()));
        };

        slot(const slot &other) : next_free(other.next_free), active(other.active)
        {
            if (active)
                ::new (static_cast<void *>(&storage)) T(other.obj());
        };

        template <class... Args> void create(Args &&...args)
        {
            NPNR_ASSERT(!active);
            active = true;
            ::new (static_cast<void *>(&storage)) T(std::forward<Args &&>(args)...);
        }
        bool empty() const { return !active; }
        T &get()
        {
            NPNR_ASSERT(active);
            return reinterpret_cast<T &>(storage);
        }
        const T &get() const
        {
            NPNR_ASSERT(active);
            return reinterpret_cast<const T &>(storage);
        }
        void free(int32_t first_free)
        {
            NPNR_ASSERT(active);
            obj().~T();
            active = false;
            next_free = first_free;
        }
        ~slot()
        {
            if (active)
                obj().~T();
        }
    };

    std::vector<slot> slots;
    int32_t first_free = 0;
    int32_t active_count = 0;

  public:
    // Create a new entry and return its index
    template <class... Args> store_index<T> add(Args &&...args)
    {
        ++active_count;
        if (first_free == int32_t(slots.size())) {
            slots.emplace_back();
            slots.back().create(std::forward<Args &&>(args)...);
            ++first_free;
            return store_index<T>(int32_t(slots.size()) - 1);
        } else {
            int32_t idx = first_free;
            auto &slot = slots.at(idx);
            first_free = slot.next_free;
            slot.create(std::forward<Args &&>(args)...);
            return store_index<T>(idx);
        }
    }

    // Remove an entry at an index
    void remove(store_index<T> idx)
    {
        --active_count;
        slots.at(idx.m_index).free(first_free);
        first_free = idx.m_index;
    }

    void clear()
    {
        active_count = 0;
        first_free = 0;
        slots.clear();
    }

    // Number of live entries
    int32_t entries() const { return active_count; }
    bool empty() const { return (entries() == 0); }

    // Reserve a certain amount of space
    void reserve(int32_t size) { slots.reserve(size); }

    // Check if an index exists
    int32_t count(store_index<T> idx)
    {
        if (idx.m_index < 0 || idx.m_index >= int32_t(slots.size()))
            return 0;
        return slots.at(idx.m_index).empty() ? 0 : 1;
    }

    // Get an item by index
    T &at(store_index<T> idx) { return slots.at(idx.m_index).get(); }
    const T &at(store_index<T> idx) const { return slots.at(idx.m_index).get(); }
    T &operator[](store_index<T> idx) { return slots.at(idx.m_index).get(); }
    const T &operator[](store_index<T> idx) const { return slots.at(idx.m_index).get(); }

    // Total size of the container
    int32_t capacity() const { return int32_t(slots.size()); }

    // Iterate over items
    template <typename It, typename S> class enumerated_iterator;

    class iterator
    {
      private:
        indexed_store *base;
        int32_t index = 0;

      public:
        iterator(indexed_store *base, int32_t index) : base(base), index(index) {};
        inline bool operator!=(const iterator &other) const { return other.index != index; }
        inline bool operator==(const iterator &other) const { return other.index == index; }
        inline iterator operator++()
        {
            // skip over unused slots
            do {
                index++;
            } while (index < int32_t(base->slots.size()) && !base->slots.at(index).active);
            return *this;
        }
        inline iterator operator++(int)
        {
            iterator prior(*this);
            do {
                index++;
            } while (index < int32_t(base->slots.size()) && !base->slots.at(index).active);
            return prior;
        }
        T &operator*() { return base->at(store_index<T>(index)); }
        template <typename It, typename S> friend class indexed_store::enumerated_iterator;
    };
    iterator begin()
    {
        auto it = iterator{this, -1};
        ++it;
        return it;
    }
    iterator end() { return iterator{this, int32_t(slots.size())}; }

    class const_iterator
    {
      private:
        const indexed_store *base;
        int32_t index = 0;

      public:
        const_iterator(const indexed_store *base, int32_t index) : base(base), index(index) {};
        inline bool operator!=(const const_iterator &other) const { return other.index != index; }
        inline bool operator==(const const_iterator &other) const { return other.index == index; }
        inline const_iterator operator++()
        {
            // skip over unused slots
            do {
                index++;
            } while (index < int32_t(base->slots.size()) && !base->slots.at(index).active);
            return *this;
        }
        inline const_iterator operator++(int)
        {
            iterator prior(*this);
            do {
                index++;
            } while (index < int32_t(base->slots.size()) && !base->slots.at(index).active);
            return prior;
        }
        const T &operator*() { return base->at(store_index<T>(index)); }
        template <typename It, typename S> friend class indexed_store::enumerated_iterator;
    };
    const_iterator begin() const
    {
        auto it = const_iterator{this, -1};
        ++it;
        return it;
    }
    const_iterator end() const { return const_iterator{this, int32_t(slots.size())}; }

    template <typename S> struct enumerated_item
    {
        enumerated_item(int32_t index, T &value) : index(index), value(value) {};
        store_index<std::remove_cv_t<S>> index;
        S &value;
    };

    template <typename It, typename S> class enumerated_iterator
    {
      private:
        It base;

      public:
        enumerated_iterator(const It &base) : base(base) {};
        inline bool operator!=(const enumerated_iterator<It, S> &other) const { return other.base != base; }
        inline bool operator==(const enumerated_iterator<It, S> &other) const { return other.base == base; }
        inline enumerated_iterator<It, S> operator++()
        {
            ++base;
            return *this;
        }
        inline enumerated_iterator<It, S> operator++(int)
        {
            iterator prior(*this);
            ++base;
            return prior;
        }
        enumerated_item<S> operator*() { return enumerated_item<S>{base.index, *base}; }
    };

    template <typename It, typename S> struct enumerated_range
    {
        enumerated_range(const It &begin, const It &end) : m_begin(begin), m_end(end) {};
        enumerated_iterator<It, S> m_begin, m_end;
        enumerated_iterator<It, S> begin() { return m_begin; }
        enumerated_iterator<It, S> end() { return m_end; }
    };

    enumerated_range<iterator, T> enumerate() { return enumerated_range<iterator, T>{begin(), end()}; }
    enumerated_range<const_iterator, const T> enumerate() const
    {
        return enumerated_range<iterator, T>{begin(), end()};
    }
};

NEXTPNR_NAMESPACE_END

#endif