From 434a9737bb459189b463c8768454ea6c0e151406 Mon Sep 17 00:00:00 2001 From: gatecat Date: Sat, 26 Feb 2022 15:11:33 +0000 Subject: Add indexed_store container type Signed-off-by: gatecat --- common/indexed_store.h | 266 +++++++++++++++++++++++++++++++++++++++++++++++++ common/nextpnr_types.h | 1 + 2 files changed, 267 insertions(+) create mode 100644 common/indexed_store.h 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 + * + * 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 +#include +#include + +#include "nextpnr_assertions.h" +#include "nextpnr_namespaces.h" + +NEXTPNR_NAMESPACE_BEGIN + +template 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 &other) const { return m_index == other.m_index; } + bool operator!=(const store_index &other) const { return m_index != other.m_index; } + bool operator<(const store_index &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 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(storage); } + inline const T &obj() const { return reinterpret_cast(storage); } + friend class indexed_store; + + public: + slot() : active(false), next_free(std::numeric_limits::max()){}; + slot(slot &&other) : active(other.active), next_free(other.next_free) + { + if (active) + ::new (static_cast(&storage)) T(std::move(other.obj())); + }; + + template void create(Args &&...args) + { + NPNR_ASSERT(!active); + active = true; + ::new (static_cast(&storage)) T(std::forward(args)...); + } + bool empty() const { return !active; } + T &get() + { + NPNR_ASSERT(active); + return reinterpret_cast(storage); + } + const T &get() const + { + NPNR_ASSERT(active); + return reinterpret_cast(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 slots; + int32_t first_free = 0; + int32_t active_count = 0; + + public: + // Create a new entry and return its index + template store_index add(Args &&...args) + { + ++active_count; + if (first_free == int32_t(slots.size())) { + slots.emplace_back(); + slots.back().create(std::forward(args)...); + ++first_free; + return store_index(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)...); + return store_index(idx); + } + } + + // Remove an entry at an index + void remove(store_index 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 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 idx) { return slots.at(idx.m_index).get(); } + const T &at(store_index idx) const { return slots.at(idx.m_index).get(); } + T &operator[](store_index idx) { return slots.at(idx.m_index).get(); } + const T &operator[](store_index 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(index)); } + template 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(index)); } + template 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 struct enumerated_item + { + enumerated_item(int32_t index, T &value) : index(index), value(value){}; + store_index> index; + S &value; + }; + + template class enumerated_iterator + { + private: + It base; + + public: + enumerated_iterator(const It &base) : base(base){}; + inline bool operator!=(const enumerated_iterator &other) const { return other.base != base; } + inline bool operator==(const enumerated_iterator &other) const { return other.base == base; } + inline enumerated_iterator operator++() + { + ++base; + return *this; + } + inline enumerated_iterator operator++(int) + { + iterator prior(*this); + ++base; + return prior; + } + enumerated_item operator*() { return enumerated_item{base.index, *base}; } + }; + + template struct enumerated_range + { + enumerated_range(const It &begin, const It &end) : m_begin(begin), m_end(end){}; + enumerated_iterator m_begin, m_end; + enumerated_iterator begin() { return m_begin; } + enumerated_iterator end() { return m_end; } + }; + + enumerated_range enumerate() { return enumerated_range{begin(), end()}; } + enumerated_range enumerate() const { return enumerated_range{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" -- cgit v1.2.3