Add indexed_store container type

Signed-off-by: gatecat <gatecat@ds0.me>

2 files changed, 267 insertions, 0 deletions

diff --git a/common/indexed_store.h b/common/indexed_store.h
new file mode 100644
index 00000000..5579b039
--- /dev/null
+++ b/common/indexed_store.h
@@ -0,0 +1,266 @@
+/*
+ *  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 <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(); }
+    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() : active(false), next_free(std::numeric_limits<int32_t>::max()){};
+        slot(slot &&other) : active(other.active), next_free(other.next_free)
+        {
+            if (active)
+                ::new (static_cast<void *>(&storage)) T(std::move(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;
+    }
+
+    // Number of live entries
+    int32_t entries() const { return active_count; }
+
+    // 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
+    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 enumerated_iterator;
+    };
+    iterator begin() { return iterator{this, 0}; }
+    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 enumerated_iterator;
+    };
+    const_iterator begin() const { return const_iterator{this, 0}; }
+    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_const<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
diff --git a/common/nextpnr_types.h b/common/nextpnr_types.h
index cf93a071..4e5432ce 100644
--- a/common/nextpnr_types.h
+++ b/common/nextpnr_types.h
@@ -29,6 +29,7 @@
 
 #include "archdefs.h"
 #include "hashlib.h"
+#include "indexed_store.h"
 #include "nextpnr_base_types.h"
 #include "nextpnr_namespaces.h"
 #include "property.h"