aboutsummaryrefslogtreecommitdiffstats
path: root/common
diff options
context:
space:
mode:
Diffstat (limited to 'common')
-rw-r--r--common/archcheck.cc18
-rw-r--r--common/base_arch.h18
-rw-r--r--common/basectx.h27
-rw-r--r--common/chain_utils.h4
-rw-r--r--common/command.cc4
-rw-r--r--common/command.h2
-rw-r--r--common/constraints.h4
-rw-r--r--common/context.cc4
-rw-r--r--common/context.h2
-rw-r--r--common/fast_bels.h4
-rw-r--r--common/hash_table.h63
-rw-r--r--common/hashlib.h1196
-rw-r--r--common/idstring.h12
-rw-r--r--common/idstringlist.h21
-rw-r--r--common/log.cc2
-rw-r--r--common/log.h20
-rw-r--r--common/nextpnr_base_types.h17
-rw-r--r--common/nextpnr_types.h23
-rw-r--r--common/place_common.cc24
-rw-r--r--common/placer1.cc63
-rw-r--r--common/placer_heap.cc85
-rw-r--r--common/placer_heap.h4
-rw-r--r--common/pybindings.cc14
-rw-r--r--common/router1.cc63
-rw-r--r--common/router2.cc19
-rw-r--r--common/sdf.cc8
-rw-r--r--common/timing.cc61
-rw-r--r--common/timing.h61
-rw-r--r--common/timing_opt.cc24
-rw-r--r--common/timing_opt.h2
-rw-r--r--common/util.h41
31 files changed, 1451 insertions, 459 deletions
diff --git a/common/archcheck.cc b/common/archcheck.cc
index f46db95c..89a61007 100644
--- a/common/archcheck.cc
+++ b/common/archcheck.cc
@@ -108,7 +108,7 @@ void archcheck_locs(const Context *ctx)
for (int x = 0; x < ctx->getGridDimX(); x++)
for (int y = 0; y < ctx->getGridDimY(); y++) {
dbg("> %d %d\n", x, y);
- std::unordered_set<int> usedz;
+ pool<int> usedz;
for (int z = 0; z < ctx->getTileBelDimZ(x, y); z++) {
BelId bel = ctx->getBelByLocation(Loc(x, y, z));
@@ -162,10 +162,10 @@ struct LruWireCacheMap
// list is oldest wire in cache.
std::list<WireId> last_access_list;
// Quick wire -> list element lookup.
- std::unordered_map<WireId, std::list<WireId>::iterator> last_access_map;
+ dict<WireId, std::list<WireId>::iterator> last_access_map;
- std::unordered_map<PipId, WireId> pips_downhill;
- std::unordered_map<PipId, WireId> pips_uphill;
+ dict<PipId, WireId> pips_downhill;
+ dict<PipId, WireId> pips_uphill;
void removeWireFromCache(WireId wire_to_remove)
{
@@ -255,8 +255,8 @@ void archcheck_conn(const Context *ctx)
log_info("Checking all wires...\n");
#ifndef USING_LRU_CACHE
- std::unordered_map<PipId, WireId> pips_downhill;
- std::unordered_map<PipId, WireId> pips_uphill;
+ dict<PipId, WireId> pips_downhill;
+ dict<PipId, WireId> pips_uphill;
#endif
for (WireId wire : ctx->getWires()) {
@@ -347,7 +347,7 @@ void archcheck_buckets(const Context *ctx)
for (BelBucketId bucket : ctx->getBelBuckets()) {
// Find out which cell types are in this bucket.
- std::unordered_set<IdString> cell_types_in_bucket;
+ pool<IdString> cell_types_in_bucket;
for (IdString cell_type : ctx->getCellTypes()) {
if (ctx->getBelBucketForCellType(cell_type) == bucket) {
cell_types_in_bucket.insert(cell_type);
@@ -356,9 +356,9 @@ void archcheck_buckets(const Context *ctx)
// Make sure that all cell types in this bucket have at least one
// BelId they can be placed at.
- std::unordered_set<IdString> cell_types_unused;
+ pool<IdString> cell_types_unused;
- std::unordered_set<BelId> bels_in_bucket;
+ pool<BelId> bels_in_bucket;
for (BelId bel : ctx->getBelsInBucket(bucket)) {
BelBucketId bucket2 = ctx->getBelBucketForBel(bel);
log_assert(bucket == bucket2);
diff --git a/common/base_arch.h b/common/base_arch.h
index fbafee99..457e6582 100644
--- a/common/base_arch.h
+++ b/common/base_arch.h
@@ -148,7 +148,7 @@ template <typename R> struct BaseArch : ArchAPI<R>
virtual char getNameDelimiter() const override { return ' '; }
// Bel methods
- virtual uint32_t getBelChecksum(BelId bel) const override { return uint32_t(std::hash<BelId>()(bel)); }
+ virtual uint32_t getBelChecksum(BelId bel) const override { return bel.hash(); }
virtual void bindBel(BelId bel, CellInfo *cell, PlaceStrength strength) override
{
NPNR_ASSERT(bel != BelId());
@@ -196,7 +196,7 @@ template <typename R> struct BaseArch : ArchAPI<R>
{
return empty_if_possible<typename R::WireAttrsRangeT>();
}
- virtual uint32_t getWireChecksum(WireId wire) const override { return uint32_t(std::hash<WireId>()(wire)); }
+ virtual uint32_t getWireChecksum(WireId wire) const override { return wire.hash(); }
virtual void bindWire(WireId wire, NetInfo *net, PlaceStrength strength) override
{
@@ -244,7 +244,7 @@ template <typename R> struct BaseArch : ArchAPI<R>
{
return empty_if_possible<typename R::PipAttrsRangeT>();
}
- virtual uint32_t getPipChecksum(PipId pip) const override { return uint32_t(std::hash<PipId>()(pip)); }
+ virtual uint32_t getPipChecksum(PipId pip) const override { return pip.hash(); }
virtual void bindPip(PipId pip, NetInfo *net, PlaceStrength strength) override
{
NPNR_ASSERT(pip != PipId());
@@ -441,23 +441,23 @@ template <typename R> struct BaseArch : ArchAPI<R>
// --------------------------------------------------------------
// These structures are used to provide default implementations of bel/wire/pip binding. Arches might want to
- // replace them with their own, for example to use faster access structures than unordered_map. Arches might also
+ // replace them with their own, for example to use faster access structures than dict. Arches might also
// want to add extra checks around these functions
- std::unordered_map<BelId, CellInfo *> base_bel2cell;
- std::unordered_map<WireId, NetInfo *> base_wire2net;
- std::unordered_map<PipId, NetInfo *> base_pip2net;
+ dict<BelId, CellInfo *> base_bel2cell;
+ dict<WireId, NetInfo *> base_wire2net;
+ dict<PipId, NetInfo *> base_pip2net;
// For the default cell/bel bucket implementations
std::vector<IdString> cell_types;
std::vector<BelBucketId> bel_buckets;
- std::unordered_map<BelBucketId, std::vector<BelId>> bucket_bels;
+ dict<BelBucketId, std::vector<BelId>> bucket_bels;
// Arches that want to use the default cell types and bel buckets *must* call these functions in their constructor
bool cell_types_initialised = false;
bool bel_buckets_initialised = false;
void init_cell_types()
{
- std::unordered_set<IdString> bel_types;
+ pool<IdString> bel_types;
for (auto bel : this->getBels())
bel_types.insert(this->getBelType(bel));
std::copy(bel_types.begin(), bel_types.end(), std::back_inserter(cell_types));
diff --git a/common/basectx.h b/common/basectx.h
index fccd12af..12f63f98 100644
--- a/common/basectx.h
+++ b/common/basectx.h
@@ -28,6 +28,7 @@
#include <boost/thread.hpp>
#endif
+#include "hashlib.h"
#include "idstring.h"
#include "nextpnr_namespaces.h"
#include "nextpnr_types.h"
@@ -59,29 +60,29 @@ struct BaseCtx
mutable StrRingBuffer log_strs;
// Project settings and config switches
- std::unordered_map<IdString, Property> settings;
+ dict<IdString, Property> settings;
// Placed nets and cells.
- std::unordered_map<IdString, std::unique_ptr<NetInfo>> nets;
- std::unordered_map<IdString, std::unique_ptr<CellInfo>> cells;
+ dict<IdString, std::unique_ptr<NetInfo>> nets;
+ dict<IdString, std::unique_ptr<CellInfo>> cells;
// Hierarchical (non-leaf) cells by full path
- std::unordered_map<IdString, HierarchicalCell> hierarchy;
+ dict<IdString, HierarchicalCell> hierarchy;
// This is the root of the above structure
IdString top_module;
// Aliases for nets, which may have more than one name due to assignments and hierarchy
- std::unordered_map<IdString, IdString> net_aliases;
+ dict<IdString, IdString> net_aliases;
// Top-level ports
- std::unordered_map<IdString, PortInfo> ports;
- std::unordered_map<IdString, CellInfo *> port_cells;
+ dict<IdString, PortInfo> ports;
+ dict<IdString, CellInfo *> port_cells;
// Floorplanning regions
- std::unordered_map<IdString, std::unique_ptr<Region>> region;
+ dict<IdString, std::unique_ptr<Region>> region;
// Context meta data
- std::unordered_map<IdString, Property> attrs;
+ dict<IdString, Property> attrs;
Context *as_ctx = nullptr;
@@ -186,10 +187,10 @@ struct BaseCtx
bool allUiReload = true;
bool frameUiReload = false;
- std::unordered_set<BelId> belUiReload;
- std::unordered_set<WireId> wireUiReload;
- std::unordered_set<PipId> pipUiReload;
- std::unordered_set<GroupId> groupUiReload;
+ pool<BelId> belUiReload;
+ pool<WireId> wireUiReload;
+ pool<PipId> pipUiReload;
+ pool<GroupId> groupUiReload;
void refreshUi() { allUiReload = true; }
diff --git a/common/chain_utils.h b/common/chain_utils.h
index 300d96a1..1bd95c9e 100644
--- a/common/chain_utils.h
+++ b/common/chain_utils.h
@@ -37,10 +37,10 @@ std::vector<CellChain> find_chains(const Context *ctx, F1 cell_type_predicate, F
{
std::set<IdString> chained;
std::vector<CellChain> chains;
- for (auto cell : sorted(ctx->cells)) {
+ for (auto &cell : ctx->cells) {
if (chained.find(cell.first) != chained.end())
continue;
- CellInfo *ci = cell.second;
+ CellInfo *ci = cell.second.get();
if (cell_type_predicate(ctx, ci)) {
CellInfo *start = ci;
CellInfo *prev_start = ci;
diff --git a/common/command.cc b/common/command.cc
index f48d6adf..27e59260 100644
--- a/common/command.cc
+++ b/common/command.cc
@@ -458,7 +458,7 @@ int CommandHandler::exec()
if (executeBeforeContext())
return 0;
- std::unordered_map<std::string, Property> values;
+ dict<std::string, Property> values;
std::unique_ptr<Context> ctx = createContext(values);
setupContext(ctx.get());
setupArchContext(ctx.get());
@@ -475,7 +475,7 @@ int CommandHandler::exec()
std::unique_ptr<Context> CommandHandler::load_json(std::string filename)
{
- std::unordered_map<std::string, Property> values;
+ dict<std::string, Property> values;
std::unique_ptr<Context> ctx = createContext(values);
setupContext(ctx.get());
setupArchContext(ctx.get());
diff --git a/common/command.h b/common/command.h
index 36b6d8ab..ba606ea2 100644
--- a/common/command.h
+++ b/common/command.h
@@ -42,7 +42,7 @@ class CommandHandler
protected:
virtual void setupArchContext(Context *ctx) = 0;
- virtual std::unique_ptr<Context> createContext(std::unordered_map<std::string, Property> &values) = 0;
+ virtual std::unique_ptr<Context> createContext(dict<std::string, Property> &values) = 0;
virtual po::options_description getArchOptions() = 0;
virtual void validate(){};
virtual void customAfterLoad(Context *ctx){};
diff --git a/common/constraints.h b/common/constraints.h
index 9ec8372d..65abf12c 100644
--- a/common/constraints.h
+++ b/common/constraints.h
@@ -21,11 +21,11 @@
#define CONSTRAINTS_H
#include <cstdint>
-#include <unordered_map>
#include <vector>
#include "archdefs.h"
#include "exclusive_state_groups.h"
+#include "hashlib.h"
#include "idstring.h"
#include "nextpnr_namespaces.h"
@@ -53,7 +53,7 @@ template <std::size_t StateCount, typename StateType = int8_t, typename CountTyp
};
typedef ExclusiveStateGroup<StateCount, StateType, CountType> TagState;
- std::unordered_map<uint32_t, std::vector<typename TagState::Definition>> definitions;
+ dict<uint32_t, std::vector<typename TagState::Definition>> definitions;
template <typename ConstraintRange> void bindBel(TagState *tags, const ConstraintRange constraints);
diff --git a/common/context.cc b/common/context.cc
index 05c1e094..115b333a 100644
--- a/common/context.cc
+++ b/common/context.cc
@@ -389,8 +389,8 @@ struct FixupHierarchyWorker
// Update hierarchy structure for nets and cells that have hiercell set
void rebuild_hierarchy()
{
- for (auto cell : sorted(ctx->cells)) {
- CellInfo *ci = cell.second;
+ for (auto &cell : ctx->cells) {
+ CellInfo *ci = cell.second.get();
if (ci->hierpath == IdString())
ci->hierpath = ctx->top_module;
auto &hc = ctx->hierarchy.at(ci->hierpath);
diff --git a/common/context.h b/common/context.h
index a5553422..102dc221 100644
--- a/common/context.h
+++ b/common/context.h
@@ -50,7 +50,7 @@ struct Context : Arch, DeterministicRNG
// provided by router1.cc
bool checkRoutedDesign() const;
bool getActualRouteDelay(WireId src_wire, WireId dst_wire, delay_t *delay = nullptr,
- std::unordered_map<WireId, PipId> *route = nullptr, bool useEstimate = true);
+ dict<WireId, PipId> *route = nullptr, bool useEstimate = true);
// --------------------------------------------------------------
// call after changing hierpath or adding/removing nets and cells
diff --git a/common/fast_bels.h b/common/fast_bels.h
index 0425f92a..b49c4c6c 100644
--- a/common/fast_bels.h
+++ b/common/fast_bels.h
@@ -178,10 +178,10 @@ struct FastBels
const bool check_bel_available;
const int minBelsForGridPick;
- std::unordered_map<IdString, TypeData> cell_types;
+ dict<IdString, TypeData> cell_types;
std::vector<std::unique_ptr<FastBelsData>> fast_bels_by_cell_type;
- std::unordered_map<BelBucketId, TypeData> partition_types;
+ dict<BelBucketId, TypeData> partition_types;
std::vector<std::unique_ptr<FastBelsData>> fast_bels_by_partition_type;
};
diff --git a/common/hash_table.h b/common/hash_table.h
deleted file mode 100644
index 21ca8887..00000000
--- a/common/hash_table.h
+++ /dev/null
@@ -1,63 +0,0 @@
-/*
- * nextpnr -- Next Generation Place and Route
- *
- * Copyright (C) 2021 Symbiflow Authors
- *
- * 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 HASH_TABLE_H
-#define HASH_TABLE_H
-
-#if defined(USE_ABSEIL)
-#include <absl/container/flat_hash_map.h>
-#include <absl/container/flat_hash_set.h>
-#else
-#include <unordered_map>
-#include <unordered_set>
-#endif
-
-#include <boost/functional/hash.hpp>
-
-#include "nextpnr_namespaces.h"
-
-NEXTPNR_NAMESPACE_BEGIN
-
-namespace HashTables {
-#if defined(USE_ABSEIL)
-template <typename Key, typename Value, typename Hash = std::hash<Key>>
-using HashMap = absl::flat_hash_map<Key, Value, Hash>;
-template <typename Value, typename Hash = std::hash<Value>> using HashSet = absl::flat_hash_set<Value, Hash>;
-#else
-template <typename Key, typename Value, typename Hash = std::hash<Key>>
-using HashMap = std::unordered_map<Key, Value, Hash>;
-template <typename Value, typename Hash = std::hash<Value>> using HashSet = std::unordered_set<Value, Hash>;
-#endif
-
-}; // namespace HashTables
-
-struct PairHash
-{
- template <typename T1, typename T2> std::size_t operator()(const std::pair<T1, T2> &idp) const noexcept
- {
- std::size_t seed = 0;
- boost::hash_combine(seed, std::hash<T1>()(idp.first));
- boost::hash_combine(seed, std::hash<T2>()(idp.second));
- return seed;
- }
-};
-
-NEXTPNR_NAMESPACE_END
-
-#endif /* HASH_TABLE_H */
diff --git a/common/hashlib.h b/common/hashlib.h
new file mode 100644
index 00000000..063df78f
--- /dev/null
+++ b/common/hashlib.h
@@ -0,0 +1,1196 @@
+// This is free and unencumbered software released into the public domain.
+//
+// Anyone is free to copy, modify, publish, use, compile, sell, or
+// distribute this software, either in source code form or as a compiled
+// binary, for any purpose, commercial or non-commercial, and by any
+// means.
+
+// -------------------------------------------------------
+// Written by Claire Xen <claire@clairexen.net> in 2014
+// -------------------------------------------------------
+
+#ifndef HASHLIB_H
+#define HASHLIB_H
+
+#include <algorithm>
+#include <stdexcept>
+#include <string>
+#include <vector>
+
+#include "nextpnr_assertions.h"
+#include "nextpnr_namespaces.h"
+
+NEXTPNR_NAMESPACE_BEGIN
+
+const int hashtable_size_trigger = 2;
+const int hashtable_size_factor = 3;
+
+// The XOR version of DJB2
+inline unsigned int mkhash(unsigned int a, unsigned int b) { return ((a << 5) + a) ^ b; }
+
+// traditionally 5381 is used as starting value for the djb2 hash
+const unsigned int mkhash_init = 5381;
+
+// The ADD version of DJB2
+// (use this version for cache locality in b)
+inline unsigned int mkhash_add(unsigned int a, unsigned int b) { return ((a << 5) + a) + b; }
+
+inline unsigned int mkhash_xorshift(unsigned int a)
+{
+ if (sizeof(a) == 4) {
+ a ^= a << 13;
+ a ^= a >> 17;
+ a ^= a << 5;
+ } else if (sizeof(a) == 8) {
+ a ^= a << 13;
+ a ^= a >> 7;
+ a ^= a << 17;
+ } else
+ NPNR_ASSERT_FALSE("mkhash_xorshift() only implemented for 32 bit and 64 bit ints");
+ return a;
+}
+
+template <typename T> struct hash_ops
+{
+ static inline bool cmp(const T &a, const T &b) { return a == b; }
+ static inline unsigned int hash(const T &a) { return a.hash(); }
+};
+
+struct hash_int_ops
+{
+ template <typename T> static inline bool cmp(T a, T b) { return a == b; }
+};
+
+template <> struct hash_ops<bool> : hash_int_ops
+{
+ static inline unsigned int hash(bool a) { return a ? 1 : 0; }
+};
+template <> struct hash_ops<int32_t> : hash_int_ops
+{
+ static inline unsigned int hash(int32_t a) { return a; }
+};
+template <> struct hash_ops<int64_t> : hash_int_ops
+{
+ static inline unsigned int hash(int64_t a) { return mkhash((unsigned int)(a), (unsigned int)(a >> 32)); }
+};
+
+template <> struct hash_ops<uint32_t> : hash_int_ops
+{
+ static inline unsigned int hash(uint32_t a) { return a; }
+};
+template <> struct hash_ops<uint64_t> : hash_int_ops
+{
+ static inline unsigned int hash(uint64_t a) { return mkhash((unsigned int)(a), (unsigned int)(a >> 32)); }
+};
+
+template <> struct hash_ops<std::string>
+{
+ static inline bool cmp(const std::string &a, const std::string &b) { return a == b; }
+ static inline unsigned int hash(const std::string &a)
+ {
+ unsigned int v = 0;
+ for (auto c : a)
+ v = mkhash(v, c);
+ return v;
+ }
+};
+
+template <typename P, typename Q> struct hash_ops<std::pair<P, Q>>
+{
+ static inline bool cmp(std::pair<P, Q> a, std::pair<P, Q> b) { return a == b; }
+ static inline unsigned int hash(std::pair<P, Q> a)
+ {
+ return mkhash(hash_ops<P>::hash(a.first), hash_ops<Q>::hash(a.second));
+ }
+};
+
+template <typename... T> struct hash_ops<std::tuple<T...>>
+{
+ static inline bool cmp(std::tuple<T...> a, std::tuple<T...> b) { return a == b; }
+ template <size_t I = 0>
+ static inline typename std::enable_if<I == sizeof...(T), unsigned int>::type hash(std::tuple<T...>)
+ {
+ return mkhash_init;
+ }
+ template <size_t I = 0>
+ static inline typename std::enable_if<I != sizeof...(T), unsigned int>::type hash(std::tuple<T...> a)
+ {
+ typedef hash_ops<typename std::tuple_element<I, std::tuple<T...>>::type> element_ops_t;
+ return mkhash(hash<I + 1>(a), element_ops_t::hash(std::get<I>(a)));
+ }
+};
+
+template <typename T> struct hash_ops<std::vector<T>>
+{
+ static inline bool cmp(std::vector<T> a, std::vector<T> b) { return a == b; }
+ static inline unsigned int hash(std::vector<T> a)
+ {
+ unsigned int h = mkhash_init;
+ for (auto k : a)
+ h = mkhash(h, hash_ops<T>::hash(k));
+ return h;
+ }
+};
+
+struct hash_cstr_ops
+{
+ static inline bool cmp(const char *a, const char *b)
+ {
+ for (int i = 0; a[i] || b[i]; i++)
+ if (a[i] != b[i])
+ return false;
+ return true;
+ }
+ static inline unsigned int hash(const char *a)
+ {
+ unsigned int hash = mkhash_init;
+ while (*a)
+ hash = mkhash(hash, *(a++));
+ return hash;
+ }
+};
+
+struct hash_ptr_ops
+{
+ static inline bool cmp(const void *a, const void *b) { return a == b; }
+ static inline unsigned int hash(const void *a) { return (uintptr_t)a; }
+};
+
+struct hash_obj_ops
+{
+ static inline bool cmp(const void *a, const void *b) { return a == b; }
+ template <typename T> static inline unsigned int hash(const T *a) { return a ? a->hash() : 0; }
+};
+
+template <typename T> inline unsigned int mkhash(const T &v) { return hash_ops<T>().hash(v); }
+
+inline int hashtable_size(int min_size)
+{
+ static std::vector<int> zero_and_some_primes = {
+ 0, 23, 29, 37, 47, 59, 79, 101, 127, 163,
+ 211, 269, 337, 431, 541, 677, 853, 1069, 1361, 1709,
+ 2137, 2677, 3347, 4201, 5261, 6577, 8231, 10289, 12889, 16127,
+ 20161, 25219, 31531, 39419, 49277, 61603, 77017, 96281, 120371, 150473,
+ 188107, 235159, 293957, 367453, 459317, 574157, 717697, 897133, 1121423, 1401791,
+ 1752239, 2190299, 2737937, 3422429, 4278037, 5347553, 6684443, 8355563, 10444457, 13055587,
+ 16319519, 20399411, 25499291, 31874149, 39842687, 49803361, 62254207, 77817767, 97272239, 121590311,
+ 151987889, 189984863, 237481091, 296851369, 371064217};
+
+ for (auto p : zero_and_some_primes)
+ if (p >= min_size)
+ return p;
+
+ if (sizeof(int) == 4)
+ throw std::length_error("hash table exceeded maximum size. use a ILP64 abi for larger tables.");
+
+ for (auto p : zero_and_some_primes)
+ if (100129 * p > min_size)
+ return 100129 * p;
+
+ throw std::length_error("hash table exceeded maximum size.");
+}
+
+template <typename K, typename T, typename OPS = hash_ops<K>> class dict;
+template <typename K, int offset = 0, typename OPS = hash_ops<K>> class idict;
+template <typename K, typename OPS = hash_ops<K>> class pool;
+template <typename K, typename OPS = hash_ops<K>> class mfp;
+
+template <typename K, typename T, typename OPS> class dict
+{
+ struct entry_t
+ {
+ std::pair<K, T> udata;
+ int next;
+
+ entry_t() {}
+ entry_t(const std::pair<K, T> &udata, int next) : udata(udata), next(next) {}
+ entry_t(std::pair<K, T> &&udata, int next) : udata(std::move(udata)), next(next) {}
+ bool operator<(const entry_t &other) const { return udata.first < other.udata.first; }
+ };
+
+ std::vector<int> hashtable;
+ std::vector<entry_t> entries;
+ OPS ops;
+
+#ifdef NDEBUG
+ static inline void do_assert(bool) {}
+#else
+ static inline void do_assert(bool cond) { NPNR_ASSERT(cond); }
+#endif
+
+ int do_hash(const K &key) const
+ {
+ unsigned int hash = 0;
+ if (!hashtable.empty())
+ hash = ops.hash(key) % (unsigned int)(hashtable.size());
+ return hash;
+ }
+
+ void do_rehash()
+ {
+ hashtable.clear();
+ hashtable.resize(hashtable_size(entries.capacity() * hashtable_size_factor), -1);
+
+ for (int i = 0; i < int(entries.size()); i++) {
+ do_assert(-1 <= entries[i].next && entries[i].next < int(entries.size()));
+ int hash = do_hash(entries[i].udata.first);
+ entries[i].next = hashtable[hash];
+ hashtable[hash] = i;
+ }
+ }
+
+ int do_erase(int index, int hash)
+ {
+ do_assert(index < int(entries.size()));
+ if (hashtable.empty() || index < 0)
+ return 0;
+
+ int k = hashtable[hash];
+ do_assert(0 <= k && k < int(entries.size()));
+
+ if (k == index) {
+ hashtable[hash] = entries[index].next;
+ } else {
+ while (entries[k].next != index) {
+ k = entries[k].next;
+ do_assert(0 <= k && k < int(entries.size()));
+ }
+ entries[k].next = entries[index].next;
+ }
+
+ int back_idx = entries.size() - 1;
+
+ if (index != back_idx) {
+ int back_hash = do_hash(entries[back_idx].udata.first);
+
+ k = hashtable[back_hash];
+ do_assert(0 <= k && k < int(entries.size()));
+
+ if (k == back_idx) {
+ hashtable[back_hash] = index;
+ } else {
+ while (entries[k].next != back_idx) {
+ k = entries[k].next;
+ do_assert(0 <= k && k < int(entries.size()));
+ }
+ entries[k].next = index;
+ }
+
+ entries[index] = std::move(entries[back_idx]);
+ }
+
+ entries.pop_back();
+
+ if (entries.empty())
+ hashtable.clear();
+
+ return 1;
+ }
+
+ int do_lookup(const K &key, int &hash) const
+ {
+ if (hashtable.empty())
+ return -1;
+
+ if (entries.size() * hashtable_size_trigger > hashtable.size()) {
+ ((dict *)this)->do_rehash();
+ hash = do_hash(key);
+ }
+
+ int index = hashtable[hash];
+
+ while (index >= 0 && !ops.cmp(entries[index].udata.first, key)) {
+ index = entries[index].next;
+ do_assert(-1 <= index && index < int(entries.size()));
+ }
+
+ return index;
+ }
+
+ int do_insert(const K &key, int &hash)
+ {
+ if (hashtable.empty()) {
+ entries.emplace_back(std::pair<K, T>(key, T()), -1);
+ do_rehash();
+ hash = do_hash(key);
+ } else {
+ entries.emplace_back(std::pair<K, T>(key, T()), hashtable[hash]);
+ hashtable[hash] = entries.size() - 1;
+ }
+ return entries.size() - 1;
+ }
+
+ int do_insert(const std::pair<K, T> &value, int &hash)
+ {
+ if (hashtable.empty()) {
+ entries.emplace_back(value, -1);
+ do_rehash();
+ hash = do_hash(value.first);
+ } else {
+ entries.emplace_back(value, hashtable[hash]);
+ hashtable[hash] = entries.size() - 1;
+ }
+ return entries.size() - 1;
+ }
+
+ int do_insert(std::pair<K, T> &&rvalue, int &hash)
+ {
+ if (hashtable.empty()) {
+ auto key = rvalue.first;
+ entries.emplace_back(std::forward<std::pair<K, T>>(rvalue), -1);
+ do_rehash();
+ hash = do_hash(key);
+ } else {
+ entries.emplace_back(std::forward<std::pair<K, T>>(rvalue), hashtable[hash]);
+ hashtable[hash] = entries.size() - 1;
+ }
+ return entries.size() - 1;
+ }
+
+ public:
+ using key_type = K;
+ using mapped_type = T;
+ using value_type = std::pair<K, T>;
+
+ class const_iterator : public std::iterator<std::forward_iterator_tag, std::pair<K, T>>
+ {
+ friend class dict;
+
+ protected:
+ const dict *ptr;
+ int index;
+ const_iterator(const dict *ptr, int index) : ptr(ptr), index(index) {}
+
+ public:
+ const_iterator() {}
+ const_iterator operator++()
+ {
+ index--;
+ return *this;
+ }
+ const_iterator operator+=(int amt)
+ {
+ index -= amt;
+ return *this;
+ }
+ bool operator<(const const_iterator &other) const { return index > other.index; }
+ bool operator==(const const_iterator &other) const { return index == other.index; }
+ bool operator!=(const const_iterator &other) const { return index != other.index; }
+ const std::pair<K, T> &operator*() const { return ptr->entries[index].udata; }
+ const std::pair<K, T> *operator->() const { return &ptr->entries[index].udata; }
+ };
+
+ class iterator : public std::iterator<std::forward_iterator_tag, std::pair<K, T>>
+ {
+ friend class dict;
+
+ protected:
+ dict *ptr;
+ int index;
+ iterator(dict *ptr, int index) : ptr(ptr), index(index) {}
+
+ public:
+ iterator() {}
+ iterator operator++()
+ {
+ index--;
+ return *this;
+ }
+ iterator operator+=(int amt)
+ {
+ index -= amt;
+ return *this;
+ }
+ bool operator<(const iterator &other) const { return index > other.index; }
+ bool operator==(const iterator &other) const { return index == other.index; }
+ bool operator!=(const iterator &other) const { return index != other.index; }
+ std::pair<K, T> &operator*() { return ptr->entries[index].udata; }
+ std::pair<K, T> *operator->() { return &ptr->entries[index].udata; }
+ const std::pair<K, T> &operator*() const { return ptr->entries[index].udata; }
+ const std::pair<K, T> *operator->() const { return &ptr->entries[index].udata; }
+ operator const_iterator() const { return const_iterator(ptr, index); }
+ };
+
+ dict() {}
+
+ dict(const dict &other)
+ {
+ entries = other.entries;
+ do_rehash();
+ }
+
+ dict(dict &&other) { swap(other); }
+
+ dict &operator=(const dict &other)
+ {
+ entries = other.entries;
+ do_rehash();
+ return *this;
+ }
+
+ dict &operator=(dict &&other)
+ {
+ clear();
+ swap(other);
+ return *this;
+ }
+
+ dict(const std::initializer_list<std::pair<K, T>> &list)
+ {
+ for (auto &it : list)
+ insert(it);
+ }
+
+ template <class InputIterator> dict(InputIterator first, InputIterator last) { insert(first, last); }
+
+ template <class InputIterator> void insert(InputIterator first, InputIterator last)
+ {
+ for (; first != last; ++first)
+ insert(*first);
+ }
+
+ std::pair<iterator, bool> insert(const K &key)
+ {
+ int hash = do_hash(key);
+ int i = do_lookup(key, hash);
+ if (i >= 0)
+ return std::pair<iterator, bool>(iterator(this, i), false);
+ i = do_insert(key, hash);
+ return std::pair<iterator, bool>(iterator(this, i), true);
+ }
+
+ std::pair<iterator, bool> insert(const std::pair<K, T> &value)
+ {
+ int hash = do_hash(value.first);
+ int i = do_lookup(value.first, hash);
+ if (i >= 0)
+ return std::pair<iterator, bool>(iterator(this, i), false);
+ i = do_insert(value, hash);
+ return std::pair<iterator, bool>(iterator(this, i), true);
+ }
+
+ std::pair<iterator, bool> insert(std::pair<K, T> &&rvalue)
+ {
+ int hash = do_hash(rvalue.first);
+ int i = do_lookup(rvalue.first, hash);
+ if (i >= 0)
+ return std::pair<iterator, bool>(iterator(this, i), false);
+ i = do_insert(std::forward<std::pair<K, T>>(rvalue), hash);
+ return std::pair<iterator, bool>(iterator(this, i), true);
+ }
+
+ std::pair<iterator, bool> emplace(K const &key, T const &value)
+ {
+ int hash = do_hash(key);
+ int i = do_lookup(key, hash);
+ if (i >= 0)
+ return std::pair<iterator, bool>(iterator(this, i), false);
+ i = do_insert(std::make_pair(key, value), hash);
+ return std::pair<iterator, bool>(iterator(this, i), true);
+ }
+
+ std::pair<iterator, bool> emplace(K const &key, T &&rvalue)
+ {
+ int hash = do_hash(key);
+ int i = do_lookup(key, hash);
+ if (i >= 0)
+ return std::pair<iterator, bool>(iterator(this, i), false);
+ i = do_insert(std::make_pair(key, std::forward<T>(rvalue)), hash);
+ return std::pair<iterator, bool>(iterator(this, i), true);
+ }
+
+ std::pair<iterator, bool> emplace(K &&rkey, T const &value)
+ {
+ int hash = do_hash(rkey);
+ int i = do_lookup(rkey, hash);
+ if (i >= 0)
+ return std::pair<iterator, bool>(iterator(this, i), false);
+ i = do_insert(std::make_pair(std::forward<K>(rkey), value), hash);
+ return std::pair<iterator, bool>(iterator(this, i), true);
+ }
+
+ std::pair<iterator, bool> emplace(K &&rkey, T &&rvalue)
+ {
+ int hash = do_hash(rkey);
+ int i = do_lookup(rkey, hash);
+ if (i >= 0)
+ return std::pair<iterator, bool>(iterator(this, i), false);
+ i = do_insert(std::make_pair(std::forward<K>(rkey), std::forward<T>(rvalue)), hash);
+ return std::pair<iterator, bool>(iterator(this, i), true);
+ }
+
+ int erase(const K &key)
+ {
+ int hash = do_hash(key);
+ int index = do_lookup(key, hash);
+ return do_erase(index, hash);
+ }
+
+ iterator erase(iterator it)
+ {
+ int hash = do_hash(it->first);
+ do_erase(it.index, hash);
+ return ++it;
+ }
+
+ int count(const K &key) const
+ {
+ int hash = do_hash(key);
+ int i = do_lookup(key, hash);
+ return i < 0 ? 0 : 1;
+ }
+
+ int count(const K &key, const_iterator it) const
+ {
+ int hash = do_hash(key);
+ int i = do_lookup(key, hash);
+ return i < 0 || i > it.index ? 0 : 1;
+ }
+
+ iterator find(const K &key)
+ {
+ int hash = do_hash(key);
+ int i = do_lookup(key, hash);
+ if (i < 0)
+ return end();
+ return iterator(this, i);
+ }
+
+ const_iterator find(const K &key) const
+ {
+ int hash = do_hash(key);
+ int i = do_lookup(key, hash);
+ if (i < 0)
+ return end();
+ return const_iterator(this, i);
+ }
+
+ T &at(const K &key)
+ {
+ int hash = do_hash(key);
+ int i = do_lookup(key, hash);
+ if (i < 0)
+ throw std::out_of_range("dict::at()");
+ return entries[i].udata.second;
+ }
+
+ const T &at(const K &key) const
+ {
+ int hash = do_hash(key);
+ int i = do_lookup(key, hash);
+ if (i < 0)
+ throw std::out_of_range("dict::at()");
+ return entries[i].udata.second;
+ }
+
+ const T &at(const K &key, const T &defval) const
+ {
+ int hash = do_hash(key);
+ int i = do_lookup(key, hash);
+ if (i < 0)
+ return defval;
+ return entries[i].udata.second;
+ }
+
+ T &operator[](const K &key)
+ {
+ int hash = do_hash(key);
+ int i = do_lookup(key, hash);
+ if (i < 0)
+ i = do_insert(std::pair<K, T>(key, T()), hash);
+ return entries[i].udata.second;
+ }
+
+ template <typename Compare = std::less<K>> void sort(Compare comp = Compare())
+ {
+ std::sort(entries.begin(), entries.end(),
+ [comp](const entry_t &a, const entry_t &b) { return comp(b.udata.first, a.udata.first); });
+ do_rehash();
+ }
+
+ void swap(dict &other)
+ {
+ hashtable.swap(other.hashtable);
+ entries.swap(other.entries);
+ }
+
+ bool operator==(const dict &other) const
+ {
+ if (size() != other.size())
+ return false;
+ for (auto &it : entries) {
+ auto oit = other.find(it.udata.first);
+ if (oit == other.end() || !(oit->second == it.udata.second))
+ return false;
+ }
+ return true;
+ }
+
+ bool operator!=(const dict &other) const { return !operator==(other); }
+
+ unsigned int hash() const
+ {
+ unsigned int h = mkhash_init;
+ for (auto &entry : entries) {
+ h ^= hash_ops<K>::hash(entry.udata.first);
+ h ^= hash_ops<T>::hash(entry.udata.second);
+ }
+ return h;
+ }
+
+ void reserve(size_t n) { entries.reserve(n); }
+ size_t size() const { return entries.size(); }
+ bool empty() const { return entries.empty(); }
+ void clear()
+ {
+ hashtable.clear();
+ entries.clear();
+ }
+
+ iterator begin() { return iterator(this, int(entries.size()) - 1); }
+ iterator element(int n) { return iterator(this, int(entries.size()) - 1 - n); }
+ iterator end() { return iterator(nullptr, -1); }
+
+ const_iterator begin() const { return const_iterator(this, int(entries.size()) - 1); }
+ const_iterator element(int n) const { return const_iterator(this, int(entries.size()) - 1 - n); }
+ const_iterator end() const { return const_iterator(nullptr, -1); }
+};
+
+template <typename K, typename OPS> class pool
+{
+ template <typename, int, typename> friend class idict;
+
+ protected:
+ struct entry_t
+ {
+ K udata;
+ int next;
+
+ entry_t() {}
+ entry_t(const K &udata, int next) : udata(udata), next(next) {}
+ entry_t(K &&udata, int next) : udata(std::move(udata)), next(next) {}
+ };
+
+ std::vector<int> hashtable;
+ std::vector<entry_t> entries;
+ OPS ops;
+
+#ifdef NDEBUG
+ static inline void do_assert(bool) {}
+#else
+ static inline void do_assert(bool cond) { NPNR_ASSERT(cond); }
+#endif
+
+ int do_hash(const K &key) const
+ {
+ unsigned int hash = 0;
+ if (!hashtable.empty())
+ hash = ops.hash(key) % (unsigned int)(hashtable.size());
+ return hash;
+ }
+
+ void do_rehash()
+ {
+ hashtable.clear();
+ hashtable.resize(hashtable_size(entries.capacity() * hashtable_size_factor), -1);
+
+ for (int i = 0; i < int(entries.size()); i++) {
+ do_assert(-1 <= entries[i].next && entries[i].next < int(entries.size()));
+ int hash = do_hash(entries[i].udata);
+ entries[i].next = hashtable[hash];
+ hashtable[hash] = i;
+ }
+ }
+
+ int do_erase(int index, int hash)
+ {
+ do_assert(index < int(entries.size()));
+ if (hashtable.empty() || index < 0)
+ return 0;
+
+ int k = hashtable[hash];
+ if (k == index) {
+ hashtable[hash] = entries[index].next;
+ } else {
+ while (entries[k].next != index) {
+ k = entries[k].next;
+ do_assert(0 <= k && k < int(entries.size()));
+ }
+ entries[k].next = entries[index].next;
+ }
+
+ int back_idx = entries.size() - 1;
+
+ if (index != back_idx) {
+ int back_hash = do_hash(entries[back_idx].udata);
+
+ k = hashtable[back_hash];
+ if (k == back_idx) {
+ hashtable[back_hash] = index;
+ } else {
+ while (entries[k].next != back_idx) {
+ k = entries[k].next;
+ do_assert(0 <= k && k < int(entries.size()));
+ }
+ entries[k].next = index;
+ }
+
+ entries[index] = std::move(entries[back_idx]);
+ }
+
+ entries.pop_back();
+
+ if (entries.empty())
+ hashtable.clear();
+
+ return 1;
+ }
+
+ int do_lookup(const K &key, int &hash) const
+ {
+ if (hashtable.empty())
+ return -1;
+
+ if (entries.size() * hashtable_size_trigger > hashtable.size()) {
+ ((pool *)this)->do_rehash();
+ hash = do_hash(key);
+ }
+
+ int index = hashtable[hash];
+
+ while (index >= 0 && !ops.cmp(entries[index].udata, key)) {
+ index = entries[index].next;
+ do_assert(-1 <= index && index < int(entries.size()));
+ }
+
+ return index;
+ }
+
+ int do_insert(const K &value, int &hash)
+ {
+ if (hashtable.empty()) {
+ entries.emplace_back(value, -1);
+ do_rehash();
+ hash = do_hash(value);
+ } else {
+ entries.emplace_back(value, hashtable[hash]);
+ hashtable[hash] = entries.size() - 1;
+ }
+ return entries.size() - 1;
+ }
+
+ int do_insert(K &&rvalue, int &hash)
+ {
+ if (hashtable.empty()) {
+ entries.emplace_back(std::forward<K>(rvalue), -1);
+ do_rehash();
+ hash = do_hash(rvalue);
+ } else {
+ entries.emplace_back(std::forward<K>(rvalue), hashtable[hash]);
+ hashtable[hash] = entries.size() - 1;
+ }
+ return entries.size() - 1;
+ }
+
+ public:
+ class const_iterator : public std::iterator<std::forward_iterator_tag, K>
+ {
+ friend class pool;
+
+ protected:
+ const pool *ptr;
+ int index;
+ const_iterator(const pool *ptr, int index) : ptr(ptr), index(index) {}
+
+ public:
+ const_iterator() {}
+ const_iterator operator++()
+ {
+ index--;
+ return *this;
+ }
+ bool operator==(const const_iterator &other) const { return index == other.index; }
+ bool operator!=(const const_iterator &other) const { return index != other.index; }
+ const K &operator*() const { return ptr->entries[index].udata; }
+ const K *operator->() const { return &ptr->entries[index].udata; }
+ };
+
+ class iterator : public std::iterator<std::forward_iterator_tag, K>
+ {
+ friend class pool;
+
+ protected:
+ pool *ptr;
+ int index;
+ iterator(pool *ptr, int index) : ptr(ptr), index(index) {}
+
+ public:
+ iterator() {}
+ iterator operator++()
+ {
+ index--;
+ return *this;
+ }
+ bool operator==(const iterator &other) const { return index == other.index; }
+ bool operator!=(const iterator &other) const { return index != other.index; }
+ K &operator*() { return ptr->entries[index].udata; }
+ K *operator->() { return &ptr->entries[index].udata; }
+ const K &operator*() const { return ptr->entries[index].udata; }
+ const K *operator->() const { return &ptr->entries[index].udata; }
+ operator const_iterator() const { return const_iterator(ptr, index); }
+ };
+
+ pool() {}
+
+ pool(const pool &other)
+ {
+ entries = other.entries;
+ do_rehash();
+ }
+
+ pool(pool &&other) { swap(other); }
+
+ pool &operator=(const pool &other)
+ {
+ entries = other.entries;
+ do_rehash();
+ return *this;
+ }
+
+ pool &operator=(pool &&other)
+ {
+ clear();
+ swap(other);
+ return *this;
+ }
+
+ pool(const std::initializer_list<K> &list)
+ {
+ for (auto &it : list)
+ insert(it);
+ }
+
+ template <class InputIterator> pool(InputIterator first, InputIterator last) { insert(first, last); }
+
+ template <class InputIterator> void insert(InputIterator first, InputIterator last)
+ {
+ for (; first != last; ++first)
+ insert(*first);
+ }
+
+ std::pair<iterator, bool> insert(const K &value)
+ {
+ int hash = do_hash(value);
+ int i = do_lookup(value, hash);
+ if (i >= 0)
+ return std::pair<iterator, bool>(iterator(this, i), false);
+ i = do_insert(value, hash);
+ return std::pair<iterator, bool>(iterator(this, i), true);
+ }
+
+ std::pair<iterator, bool> insert(K &&rvalue)
+ {
+ int hash = do_hash(rvalue);
+ int i = do_lookup(rvalue, hash);
+ if (i >= 0)
+ return std::pair<iterator, bool>(iterator(this, i), false);
+ i = do_insert(std::forward<K>(rvalue), hash);
+ return std::pair<iterator, bool>(iterator(this, i), true);
+ }
+
+ template <typename... Args> std::pair<iterator, bool> emplace(Args &&...args)
+ {
+ return insert(K(std::forward<Args>(args)...));
+ }
+
+ int erase(const K &key)
+ {
+ int hash = do_hash(key);
+ int index = do_lookup(key, hash);
+ return do_erase(index, hash);
+ }
+
+ iterator erase(iterator it)
+ {
+ int hash = do_hash(*it);
+ do_erase(it.index, hash);
+ return ++it;
+ }
+
+ int count(const K &key) const
+ {
+ int hash = do_hash(key);
+ int i = do_lookup(key, hash);
+ return i < 0 ? 0 : 1;
+ }
+
+ int count(const K &key, const_iterator it) const
+ {
+ int hash = do_hash(key);
+ int i = do_lookup(key, hash);
+ return i < 0 || i > it.index ? 0 : 1;
+ }
+
+ iterator find(const K &key)
+ {
+ int hash = do_hash(key);
+ int i = do_lookup(key, hash);
+ if (i < 0)
+ return end();
+ return iterator(this, i);
+ }
+
+ const_iterator find(const K &key) const
+ {
+ int hash = do_hash(key);
+ int i = do_lookup(key, hash);
+ if (i < 0)
+ return end();
+ return const_iterator(this, i);
+ }
+
+ bool operator[](const K &key)
+ {
+ int hash = do_hash(key);
+ int i = do_lookup(key, hash);
+ return i >= 0;
+ }
+
+ template <typename Compare = std::less<K>> void sort(Compare comp = Compare())
+ {
+ std::sort(entries.begin(), entries.end(),
+ [comp](const entry_t &a, const entry_t &b) { return comp(b.udata, a.udata); });
+ do_rehash();
+ }
+
+ K pop()
+ {
+ iterator it = begin();
+ K ret = *it;
+ erase(it);
+ return ret;
+ }
+
+ void swap(pool &other)
+ {
+ hashtable.swap(other.hashtable);
+ entries.swap(other.entries);
+ }
+
+ bool operator==(const pool &other) const
+ {
+ if (size() != other.size())
+ return false;
+ for (auto &it : entries)
+ if (!other.count(it.udata))
+ return false;
+ return true;
+ }
+
+ bool operator!=(const pool &other) const { return !operator==(other); }
+
+ bool hash() const
+ {
+ unsigned int hashval = mkhash_init;
+ for (auto &it : entries)
+ hashval ^= ops.hash(it.udata);
+ return hashval;
+ }
+
+ void reserve(size_t n) { entries.reserve(n); }
+ size_t size() const { return entries.size(); }
+ bool empty() const { return entries.empty(); }
+ void clear()
+ {
+ hashtable.clear();
+ entries.clear();
+ }
+
+ iterator begin() { return iterator(this, int(entries.size()) - 1); }
+ iterator element(int n) { return iterator(this, int(entries.size()) - 1 - n); }
+ iterator end() { return iterator(nullptr, -1); }
+
+ const_iterator begin() const { return const_iterator(this, int(entries.size()) - 1); }
+ const_iterator element(int n) const { return const_iterator(this, int(entries.size()) - 1 - n); }
+ const_iterator end() const { return const_iterator(nullptr, -1); }
+};
+
+template <typename K, int offset, typename OPS> class idict
+{
+ pool<K, OPS> database;
+
+ public:
+ class const_iterator : public std::iterator<std::forward_iterator_tag, K>
+ {
+ friend class idict;
+
+ protected:
+ const idict &container;
+ int index;
+ const_iterator(const idict &container, int index) : container(container), index(index) {}
+
+ public:
+ const_iterator() {}
+ const_iterator operator++()
+ {
+ index++;
+ return *this;
+ }
+ bool operator==(const const_iterator &other) const { return index == other.index; }
+ bool operator!=(const const_iterator &other) const { return index != other.index; }
+ const K &operator*() const { return container[index]; }
+ const K *operator->() const { return &container[index]; }
+ };
+
+ int operator()(const K &key)
+ {
+ int hash = database.do_hash(key);
+ int i = database.do_lookup(key, hash);
+ if (i < 0)
+ i = database.do_insert(key, hash);
+ return i + offset;
+ }
+
+ int at(const K &key) const
+ {
+ int hash = database.do_hash(key);
+ int i = database.do_lookup(key, hash);
+ if (i < 0)
+ throw std::out_of_range("idict::at()");
+ return i + offset;
+ }
+
+ int at(const K &key, int defval) const
+ {
+ int hash = database.do_hash(key);
+ int i = database.do_lookup(key, hash);
+ if (i < 0)
+ return defval;
+ return i + offset;
+ }
+
+ int count(const K &key) const
+ {
+ int hash = database.do_hash(key);
+ int i = database.do_lookup(key, hash);
+ return i < 0 ? 0 : 1;
+ }
+
+ void expect(const K &key, int i)
+ {
+ int j = (*this)(key);
+ if (i != j)
+ throw std::out_of_range("idict::expect()");
+ }
+
+ const K &operator[](int index) const { return database.entries.at(index - offset).udata; }
+
+ void swap(idict &other) { database.swap(other.database); }
+
+ void reserve(size_t n) { database.reserve(n); }
+ size_t size() const { return database.size(); }
+ bool empty() const { return database.empty(); }
+ void clear() { database.clear(); }
+
+ const_iterator begin() const { return const_iterator(*this, offset); }
+ const_iterator element(int n) const { return const_iterator(*this, n); }
+ const_iterator end() const { return const_iterator(*this, offset + size()); }
+};
+
+template <typename K, typename OPS> class mfp
+{
+ mutable idict<K, 0, OPS> database;
+ mutable std::vector<int> parents;
+
+ public:
+ typedef typename idict<K, 0, OPS>::const_iterator const_iterator;
+
+ int operator()(const K &key) const
+ {
+ int i = database(key);
+ parents.resize(database.size(), -1);
+ return i;
+ }
+
+ const K &operator[](int index) const { return database[index]; }
+
+ int ifind(int i) const
+ {
+ int p = i, k = i;
+
+ while (parents[p] != -1)
+ p = parents[p];
+
+ while (k != p) {
+ int next_k = parents[k];
+ parents[k] = p;
+ k = next_k;
+ }
+
+ return p;
+ }
+
+ void imerge(int i, int j)
+ {
+ i = ifind(i);
+ j = ifind(j);
+
+ if (i != j)
+ parents[i] = j;
+ }
+
+ void ipromote(int i)
+ {
+ int k = i;
+
+ while (k != -1) {
+ int next_k = parents[k];
+ parents[k] = i;
+ k = next_k;
+ }
+
+ parents[i] = -1;
+ }
+
+ int lookup(const K &a) const { return ifind((*this)(a)); }
+
+ const K &find(const K &a) const
+ {
+ int i = database.at(a, -1);
+ if (i < 0)
+ return a;
+ return (*this)[ifind(i)];
+ }
+
+ void merge(const K &a, const K &b) { imerge((*this)(a), (*this)(b)); }
+
+ void promote(const K &a)
+ {
+ int i = database.at(a, -1);
+ if (i >= 0)
+ ipromote(i);
+ }
+
+ void swap(mfp &other)
+ {
+ database.swap(other.database);
+ parents.swap(other.parents);
+ }
+
+ void reserve(size_t n) { database.reserve(n); }
+ size_t size() const { return database.size(); }
+ bool empty() const { return database.empty(); }
+ void clear()
+ {
+ database.clear();
+ parents.clear();
+ }
+
+ const_iterator begin() const { return database.begin(); }
+ const_iterator element(int n) const { return database.element(n); }
+ const_iterator end() const { return database.end(); }
+};
+
+NEXTPNR_NAMESPACE_END
+
+#endif
diff --git a/common/idstring.h b/common/idstring.h
index c3ccbc6b..5a7719fa 100644
--- a/common/idstring.h
+++ b/common/idstring.h
@@ -56,18 +56,10 @@ struct IdString
bool operator!=(const IdString &other) const { return index != other.index; }
bool empty() const { return index == 0; }
+
+ unsigned int hash() const { return index; }
};
NEXTPNR_NAMESPACE_END
-namespace std {
-template <> struct hash<NEXTPNR_NAMESPACE_PREFIX IdString>
-{
- std::size_t operator()(const NEXTPNR_NAMESPACE_PREFIX IdString &obj) const noexcept
- {
- return std::hash<int>()(obj.index);
- }
-};
-} // namespace std
-
#endif /* IDSTRING_H */
diff --git a/common/idstringlist.h b/common/idstringlist.h
index 24a46731..f101ecca 100644
--- a/common/idstringlist.h
+++ b/common/idstringlist.h
@@ -22,6 +22,7 @@
#define IDSTRING_LIST_H
#include <boost/functional/hash.hpp>
+#include "hashlib.h"
#include "idstring.h"
#include "nextpnr_namespaces.h"
#include "sso_array.h"
@@ -67,22 +68,16 @@ struct IdStringList
static IdStringList concat(IdStringList a, IdStringList b);
IdStringList slice(size_t s, size_t e) const;
-};
-
-NEXTPNR_NAMESPACE_END
-namespace std {
-template <> struct hash<NEXTPNR_NAMESPACE_PREFIX IdStringList>
-{
- std::size_t operator()(const NEXTPNR_NAMESPACE_PREFIX IdStringList &obj) const noexcept
+ unsigned int hash() const
{
- std::size_t seed = 0;
- boost::hash_combine(seed, hash<size_t>()(obj.size()));
- for (auto &id : obj)
- boost::hash_combine(seed, hash<NEXTPNR_NAMESPACE_PREFIX IdString>()(id));
- return seed;
+ unsigned int h = mkhash_init;
+ for (const auto &val : ids)
+ h = mkhash(h, val.hash());
+ return h;
}
};
-} // namespace std
+
+NEXTPNR_NAMESPACE_END
#endif /* IDSTRING_LIST_H */
diff --git a/common/log.cc b/common/log.cc
index 01aec79a..a429d172 100644
--- a/common/log.cc
+++ b/common/log.cc
@@ -38,7 +38,7 @@ log_write_type log_write_function = nullptr;
std::string log_last_error;
void (*log_error_atexit)() = NULL;
-std::unordered_map<LogLevel, int> message_count_by_level;
+dict<LogLevel, int, loglevel_hash_ops> message_count_by_level;
static int log_newline_count = 0;
bool had_nonfatal_error = false;
diff --git a/common/log.h b/common/log.h
index 7dfdf165..e9237446 100644
--- a/common/log.h
+++ b/common/log.h
@@ -26,8 +26,8 @@
#include <stdarg.h>
#include <stdio.h>
#include <string>
-#include <unordered_map>
#include <vector>
+#include "hashlib.h"
#include "nextpnr_namespaces.h"
NEXTPNR_NAMESPACE_BEGIN
@@ -51,13 +51,19 @@ enum class LogLevel
ALWAYS_MSG
};
+struct loglevel_hash_ops
+{
+ static inline bool cmp(LogLevel a, LogLevel b) { return a == b; }
+ static inline unsigned int hash(LogLevel a) { return unsigned(a); }
+};
+
extern std::vector<std::pair<std::ostream *, LogLevel>> log_streams;
extern log_write_type log_write_function;
extern std::string log_last_error;
extern void (*log_error_atexit)();
extern bool had_nonfatal_error;
-extern std::unordered_map<LogLevel, int> message_count_by_level;
+extern dict<LogLevel, int, loglevel_hash_ops> message_count_by_level;
std::string stringf(const char *fmt, ...);
std::string vstringf(const char *fmt, va_list ap);
@@ -83,14 +89,4 @@ static inline void log_assert_worker(bool cond, const char *expr, const char *fi
NEXTPNR_NAMESPACE_END
-namespace std {
-template <> struct hash<NEXTPNR_NAMESPACE_PREFIX LogLevel>
-{
- std::size_t operator()(const NEXTPNR_NAMESPACE_PREFIX LogLevel &loglevel) const noexcept
- {
- return std::hash<int>()((int)loglevel);
- }
-};
-} // namespace std
-
#endif
diff --git a/common/nextpnr_base_types.h b/common/nextpnr_base_types.h
index 1a15bfcb..1707559b 100644
--- a/common/nextpnr_base_types.h
+++ b/common/nextpnr_base_types.h
@@ -30,6 +30,7 @@
#include <boost/functional/hash.hpp>
#include <string>
+#include "hashlib.h"
#include "idstring.h"
#include "nextpnr_namespaces.h"
@@ -89,6 +90,7 @@ struct Loc
bool operator==(const Loc &other) const { return (x == other.x) && (y == other.y) && (z == other.z); }
bool operator!=(const Loc &other) const { return (x != other.x) || (y != other.y) || (z != other.z); }
+ unsigned int hash() const { return mkhash(x, mkhash(y, z)); }
};
struct ArcBounds
@@ -128,19 +130,4 @@ enum PlaceStrength
NEXTPNR_NAMESPACE_END
-namespace std {
-template <> struct hash<NEXTPNR_NAMESPACE_PREFIX Loc>
-{
- std::size_t operator()(const NEXTPNR_NAMESPACE_PREFIX Loc &obj) const noexcept
- {
- std::size_t seed = 0;
- boost::hash_combine(seed, hash<int>()(obj.x));
- boost::hash_combine(seed, hash<int>()(obj.y));
- boost::hash_combine(seed, hash<int>()(obj.z));
- return seed;
- }
-};
-
-} // namespace std
-
#endif /* NEXTPNR_BASE_TYPES_H */
diff --git a/common/nextpnr_types.h b/common/nextpnr_types.h
index 67e60c50..4770f8ae 100644
--- a/common/nextpnr_types.h
+++ b/common/nextpnr_types.h
@@ -28,6 +28,7 @@
#include <unordered_set>
#include "archdefs.h"
+#include "hashlib.h"
#include "nextpnr_base_types.h"
#include "nextpnr_namespaces.h"
#include "property.h"
@@ -56,9 +57,9 @@ struct Region
bool constr_wires = false;
bool constr_pips = false;
- std::unordered_set<BelId> bels;
- std::unordered_set<WireId> wires;
- std::unordered_set<Loc> piplocs;
+ pool<BelId> bels;
+ pool<WireId> wires;
+ pool<Loc> piplocs;
};
struct PipMap
@@ -128,10 +129,10 @@ struct NetInfo : ArchNetInfo
PortRef driver;
std::vector<PortRef> users;
- std::unordered_map<IdString, Property> attrs;
+ dict<IdString, Property> attrs;
// wire -> uphill_pip
- std::unordered_map<WireId, PipMap> wires;
+ dict<WireId, PipMap> wires;
std::vector<IdString> aliases; // entries in net_aliases that point to this net
@@ -159,8 +160,8 @@ struct CellInfo : ArchCellInfo
IdString name, type, hierpath;
int32_t udata;
- std::unordered_map<IdString, PortInfo> ports;
- std::unordered_map<IdString, Property> attrs, params;
+ dict<IdString, PortInfo> ports;
+ dict<IdString, Property> attrs, params;
BelId bel;
PlaceStrength belStrength = STRENGTH_NONE;
@@ -232,13 +233,13 @@ struct HierarchicalCell
{
IdString name, type, parent, fullpath;
// Name inside cell instance -> global name
- std::unordered_map<IdString, IdString> leaf_cells, nets;
+ dict<IdString, IdString> leaf_cells, nets;
// Global name -> name inside cell instance
- std::unordered_map<IdString, IdString> leaf_cells_by_gname, nets_by_gname;
+ dict<IdString, IdString> leaf_cells_by_gname, nets_by_gname;
// Cell port to net
- std::unordered_map<IdString, HierarchicalPort> ports;
+ dict<IdString, HierarchicalPort> ports;
// Name inside cell instance -> global name
- std::unordered_map<IdString, IdString> hier_cells;
+ dict<IdString, IdString> hier_cells;
};
NEXTPNR_NAMESPACE_END
diff --git a/common/place_common.cc b/common/place_common.cc
index 7cbeca65..9a6c6158 100644
--- a/common/place_common.cc
+++ b/common/place_common.cc
@@ -178,8 +178,8 @@ class ConstraintLegaliseWorker
private:
Context *ctx;
std::set<IdString> rippedCells;
- std::unordered_map<IdString, Loc> oldLocations;
- std::unordered_map<ClusterId, std::vector<CellInfo *>> cluster2cells;
+ dict<IdString, Loc> oldLocations;
+ dict<ClusterId, std::vector<CellInfo *>> cluster2cells;
class IncreasingDiameterSearch
{
@@ -227,10 +227,10 @@ class ConstraintLegaliseWorker
int sign = 0;
};
- typedef std::unordered_map<IdString, Loc> CellLocations;
+ typedef dict<IdString, Loc> CellLocations;
// Check if a location would be suitable for a cell and all its constrained children
- bool valid_loc_for(const CellInfo *cell, Loc loc, CellLocations &solution, std::unordered_set<Loc> &usedLocations)
+ bool valid_loc_for(const CellInfo *cell, Loc loc, CellLocations &solution, pool<Loc> &usedLocations)
{
BelId locBel = ctx->getBelByLocation(loc);
if (locBel == BelId())
@@ -324,7 +324,7 @@ class ConstraintLegaliseWorker
}
CellLocations solution;
- std::unordered_set<Loc> used;
+ pool<Loc> used;
if (valid_loc_for(cell, rootLoc, solution, used)) {
for (auto cp : solution) {
// First unbind all cells
@@ -377,9 +377,9 @@ class ConstraintLegaliseWorker
public:
ConstraintLegaliseWorker(Context *ctx) : ctx(ctx)
{
- for (auto cell : sorted(ctx->cells)) {
+ for (auto &cell : ctx->cells) {
if (cell.second->cluster != ClusterId())
- cluster2cells[cell.second->cluster].push_back(cell.second);
+ cluster2cells[cell.second->cluster].push_back(cell.second.get());
}
};
@@ -414,11 +414,11 @@ class ConstraintLegaliseWorker
int legalise_constraints()
{
log_info("Legalising relative constraints...\n");
- for (auto cell : sorted(ctx->cells)) {
+ for (auto &cell : ctx->cells) {
oldLocations[cell.first] = ctx->getBelLocation(cell.second->bel);
}
- for (auto cell : sorted(ctx->cells)) {
- bool res = legalise_cell(cell.second);
+ for (auto &cell : ctx->cells) {
+ bool res = legalise_cell(cell.second.get());
if (!res) {
log_error("failed to place chain starting at cell '%s'\n", cell.first.c_str(ctx));
return -1;
@@ -434,8 +434,8 @@ class ConstraintLegaliseWorker
}
}
auto score = print_stats("replacing ripped up cells");
- for (auto cell : sorted(ctx->cells))
- if (get_constraints_distance(ctx, cell.second) != 0)
+ for (auto &cell : ctx->cells)
+ if (get_constraints_distance(ctx, cell.second.get()) != 0)
log_error("constraint satisfaction check failed for cell '%s' at Bel '%s'\n", cell.first.c_str(ctx),
ctx->nameOfBel(cell.second->bel));
return score;
diff --git a/common/placer1.cc b/common/placer1.cc
index a3e7a696..a832e08f 100644
--- a/common/placer1.cc
+++ b/common/placer1.cc
@@ -46,19 +46,6 @@
#include "timing.h"
#include "util.h"
-namespace std {
-template <> struct hash<std::pair<NEXTPNR_NAMESPACE_PREFIX IdString, std::size_t>>
-{
- std::size_t operator()(const std::pair<NEXTPNR_NAMESPACE_PREFIX IdString, std::size_t> &idp) const noexcept
- {
- std::size_t seed = 0;
- boost::hash_combine(seed, hash<NEXTPNR_NAMESPACE_PREFIX IdString>()(idp.first));
- boost::hash_combine(seed, hash<std::size_t>()(idp.second));
- return seed;
- }
-};
-} // namespace std
-
NEXTPNR_NAMESPACE_BEGIN
class SAPlacer
@@ -87,8 +74,8 @@ class SAPlacer
}
diameter = std::max(max_x, max_y) + 1;
- std::unordered_set<IdString> cell_types_in_use;
- for (auto cell : sorted(ctx->cells)) {
+ pool<IdString> cell_types_in_use;
+ for (auto &cell : ctx->cells) {
IdString cell_type = cell.second->type;
cell_types_in_use.insert(cell_type);
}
@@ -108,8 +95,8 @@ class SAPlacer
net.second->udata = n++;
net_by_udata.push_back(net.second.get());
}
- for (auto &region : sorted(ctx->region)) {
- Region *r = region.second;
+ for (auto &region : ctx->region) {
+ Region *r = region.second.get();
BoundingBox bb;
if (r->constr_bels) {
bb.x0 = std::numeric_limits<int>::max();
@@ -360,12 +347,12 @@ class SAPlacer
// Only increase temperature if something was moved
autoplaced.clear();
chain_basis.clear();
- for (auto cell : sorted(ctx->cells)) {
+ for (auto &cell : ctx->cells) {
if (cell.second->belStrength <= STRENGTH_STRONG && cell.second->cluster != ClusterId() &&
- ctx->getClusterRootCell(cell.second->cluster) == cell.second)
- chain_basis.push_back(cell.second);
+ ctx->getClusterRootCell(cell.second->cluster) == cell.second.get())
+ chain_basis.push_back(cell.second.get());
else if (cell.second->belStrength < STRENGTH_STRONG)
- autoplaced.push_back(cell.second);
+ autoplaced.push_back(cell.second.get());
}
// temp = post_legalise_temp;
// diameter = std::min<int>(M, diameter * post_legalise_dia_scale);
@@ -421,8 +408,8 @@ class SAPlacer
}
}
}
- for (auto cell : sorted(ctx->cells))
- if (get_constraints_distance(ctx, cell.second) != 0)
+ for (auto &cell : ctx->cells)
+ if (get_constraints_distance(ctx, cell.second.get()) != 0)
log_error("constraint satisfaction check failed for cell '%s' at Bel '%s'\n", cell.first.c_str(ctx),
ctx->nameOfBel(cell.second->bel));
timing_analysis(ctx);
@@ -629,7 +616,7 @@ class SAPlacer
bool try_swap_chain(CellInfo *cell, BelId newBase)
{
std::vector<std::pair<CellInfo *, Loc>> cell_rel;
- std::unordered_set<IdString> cells;
+ pool<IdString> cells;
std::vector<std::pair<CellInfo *, BelId>> moves_made;
std::vector<std::pair<CellInfo *, BelId>> dest_bels;
double delta = 0;
@@ -831,8 +818,8 @@ class SAPlacer
// Set up the cost maps
void setup_costs()
{
- for (auto net : sorted(ctx->nets)) {
- NetInfo *ni = net.second;
+ for (auto &net : ctx->nets) {
+ NetInfo *ni = net.second.get();
if (ignore_net(ni))
continue;
net_bounds[ni->udata] = get_net_bounds(ni);
@@ -1065,7 +1052,7 @@ class SAPlacer
mc.already_changed_arcs[pn->udata][i] = true;
}
} else if (port.second.type == PORT_IN) {
- auto usr = fast_port_to_user.at(&port.second);
+ auto usr = fast_port_to_user.at(std::make_pair(cell->name, port.first));
if (!mc.already_changed_arcs[pn->udata][usr]) {
mc.changed_arcs.emplace_back(std::make_pair(pn->udata, usr));
mc.already_changed_arcs[pn->udata][usr] = true;
@@ -1118,11 +1105,11 @@ class SAPlacer
// Build the cell port -> user index
void build_port_index()
{
- for (auto net : sorted(ctx->nets)) {
- NetInfo *ni = net.second;
+ for (auto &net : ctx->nets) {
+ NetInfo *ni = net.second.get();
for (size_t i = 0; i < ni->users.size(); i++) {
auto &usr = ni->users.at(i);
- fast_port_to_user[&(usr.cell->ports.at(usr.port))] = i;
+ fast_port_to_user[std::make_pair(usr.cell->name, usr.port)] = i;
}
}
}
@@ -1130,13 +1117,13 @@ class SAPlacer
// Simple routeability driven placement
const int large_cell_thresh = 50;
int total_net_share = 0;
- std::vector<std::vector<std::unordered_map<IdString, int>>> nets_by_tile;
+ std::vector<std::vector<dict<IdString, int>>> nets_by_tile;
void setup_nets_by_tile()
{
total_net_share = 0;
- nets_by_tile.resize(max_x + 1, std::vector<std::unordered_map<IdString, int>>(max_y + 1));
- for (auto cell : sorted(ctx->cells)) {
- CellInfo *ci = cell.second;
+ nets_by_tile.resize(max_x + 1, std::vector<dict<IdString, int>>(max_y + 1));
+ for (auto &cell : ctx->cells) {
+ CellInfo *ci = cell.second.get();
if (int(ci->ports.size()) > large_cell_thresh)
continue;
Loc loc = ctx->getBelLocation(ci->bel);
@@ -1194,7 +1181,7 @@ class SAPlacer
std::vector<std::vector<double>> net_arc_tcost;
// Fast lookup for cell port to net user index
- std::unordered_map<const PortInfo *, size_t> fast_port_to_user;
+ dict<std::pair<IdString, IdString>, size_t> fast_port_to_user;
// Wirelength and timing cost at last and current iteration
wirelen_t last_wirelen_cost, curr_wirelen_cost;
@@ -1207,10 +1194,10 @@ class SAPlacer
bool improved = false;
int n_move, n_accept;
int diameter = 35, max_x = 1, max_y = 1;
- std::unordered_map<IdString, std::tuple<int, int>> bel_types;
- std::unordered_map<IdString, BoundingBox> region_bounds;
+ dict<IdString, std::tuple<int, int>> bel_types;
+ dict<IdString, BoundingBox> region_bounds;
FastBels fast_bels;
- std::unordered_set<BelId> locked_bels;
+ pool<BelId> locked_bels;
std::vector<NetInfo *> net_by_udata;
std::vector<decltype(NetInfo::udata)> old_udata;
bool require_legal = true;
diff --git a/common/placer_heap.cc b/common/placer_heap.cc
index 2f7c7ccb..f1419bdb 100644
--- a/common/placer_heap.cc
+++ b/common/placer_heap.cc
@@ -43,7 +43,6 @@
#include <numeric>
#include <queue>
#include <tuple>
-#include <unordered_map>
#include "fast_bels.h"
#include "log.h"
#include "nextpnr.h"
@@ -146,9 +145,9 @@ class HeAPPlacer
tmg.setup_only = true;
tmg.setup();
- for (auto cell : sorted(ctx->cells))
+ for (auto &cell : ctx->cells)
if (cell.second->cluster != ClusterId())
- cluster2cells[cell.second->cluster].push_back(cell.second);
+ cluster2cells[cell.second->cluster].push_back(cell.second.get());
}
bool place()
@@ -188,14 +187,14 @@ class HeAPPlacer
std::vector<std::tuple<CellInfo *, BelId, PlaceStrength>> solution;
- std::vector<std::unordered_set<BelBucketId>> heap_runs;
- std::unordered_set<BelBucketId> all_buckets;
- std::unordered_map<BelBucketId, int> bucket_count;
+ std::vector<pool<BelBucketId>> heap_runs;
+ pool<BelBucketId> all_buckets;
+ dict<BelBucketId, int> bucket_count;
for (auto cell : place_cells) {
BelBucketId bucket = ctx->getBelBucketForCellType(cell->type);
if (!all_buckets.count(bucket)) {
- heap_runs.push_back(std::unordered_set<BelBucketId>{bucket});
+ heap_runs.push_back(pool<BelBucketId>{bucket});
all_buckets.insert(bucket);
}
bucket_count[bucket]++;
@@ -253,9 +252,9 @@ class HeAPPlacer
for (const auto &group : cfg.cellGroups)
CutSpreader(this, group).run();
- for (auto type : sorted(run))
+ for (auto type : run)
if (std::all_of(cfg.cellGroups.begin(), cfg.cellGroups.end(),
- [type](const std::unordered_set<BelBucketId> &grp) { return !grp.count(type); }))
+ [type](const pool<BelBucketId> &grp) { return !grp.count(type); }))
CutSpreader(this, {type}).run();
// Run strict legalisation to find a valid bel for all cells
@@ -283,8 +282,8 @@ class HeAPPlacer
stalled = 0;
// Save solution
solution.clear();
- for (auto cell : sorted(ctx->cells)) {
- solution.emplace_back(cell.second, cell.second->bel, cell.second->belStrength);
+ for (auto &cell : ctx->cells) {
+ solution.emplace_back(cell.second.get(), cell.second->bel, cell.second->belStrength);
}
} else {
++stalled;
@@ -311,10 +310,10 @@ class HeAPPlacer
ctx->bindBel(bel, cell, strength);
}
- for (auto cell : sorted(ctx->cells)) {
+ for (auto &cell : ctx->cells) {
if (cell.second->bel == BelId())
log_error("Found unbound cell %s\n", cell.first.c_str(ctx));
- if (ctx->getBoundBelCell(cell.second->bel) != cell.second)
+ if (ctx->getBoundBelCell(cell.second->bel) != cell.second.get())
log_error("Found cell %s with mismatched binding\n", cell.first.c_str(ctx));
if (ctx->debug)
log_info("AP soln: %s -> %s\n", cell.first.c_str(ctx), ctx->nameOfBel(cell.second->bel));
@@ -360,7 +359,7 @@ class HeAPPlacer
int max_x = 0, max_y = 0;
FastBels fast_bels;
- std::unordered_map<IdString, std::tuple<int, int>> bel_types;
+ dict<IdString, std::tuple<int, int>> bel_types;
TimingAnalyser tmg;
@@ -370,7 +369,7 @@ class HeAPPlacer
int x0 = 0, x1 = 0, y0 = 0, y1 = 0;
};
- std::unordered_map<IdString, BoundingBox> constraint_region_bounds;
+ dict<IdString, BoundingBox> constraint_region_bounds;
// In some cases, we can't use bindBel because we allow overlap in the earlier stages. So we use this custom
// structure instead
@@ -381,7 +380,7 @@ class HeAPPlacer
double rawx, rawy;
bool locked, global;
};
- std::unordered_map<IdString, CellLocation> cell_locs;
+ dict<IdString, CellLocation> cell_locs;
// The set of cells that we will actually place. This excludes locked cells and children cells of macros/chains
// (only the root of each macro is placed.)
std::vector<CellInfo *> place_cells;
@@ -390,8 +389,8 @@ class HeAPPlacer
// cells of a certain type)
std::vector<CellInfo *> solve_cells;
- std::unordered_map<ClusterId, std::vector<CellInfo *>> cluster2cells;
- std::unordered_map<ClusterId, int> chain_size;
+ dict<ClusterId, std::vector<CellInfo *>> cluster2cells;
+ dict<ClusterId, int> chain_size;
// Performance counting
double solve_time = 0, cl_time = 0, sl_time = 0;
@@ -448,9 +447,9 @@ class HeAPPlacer
max_y = std::max(max_y, loc.y);
}
- std::unordered_set<IdString> cell_types_in_use;
- std::unordered_set<BelBucketId> buckets_in_use;
- for (auto cell : sorted(ctx->cells)) {
+ pool<IdString> cell_types_in_use;
+ pool<BelBucketId> buckets_in_use;
+ for (auto &cell : ctx->cells) {
IdString cell_type = cell.second->type;
cell_types_in_use.insert(cell_type);
BelBucketId bucket = ctx->getBelBucketForCellType(cell_type);
@@ -465,8 +464,8 @@ class HeAPPlacer
}
// Determine bounding boxes of region constraints
- for (auto &region : sorted(ctx->region)) {
- Region *r = region.second;
+ for (auto &region : ctx->region) {
+ Region *r = region.second.get();
BoundingBox bb;
if (r->constr_bels) {
bb.x0 = std::numeric_limits<int>::max();
@@ -515,13 +514,13 @@ class HeAPPlacer
// FIXME: Are there better approaches to the initial placement (e.g. greedy?)
void seed_placement()
{
- std::unordered_set<IdString> cell_types;
+ pool<IdString> cell_types;
for (const auto &cell : ctx->cells) {
cell_types.insert(cell.second->type);
}
- std::unordered_set<BelId> bels_used;
- std::unordered_map<IdString, std::deque<BelId>> available_bels;
+ pool<BelId> bels_used;
+ dict<IdString, std::deque<BelId>> available_bels;
for (auto bel : ctx->getBels()) {
if (!ctx->checkBelAvail(bel)) {
@@ -539,8 +538,8 @@ class HeAPPlacer
ctx->shuffle(t.second.begin(), t.second.end());
}
- for (auto cell : sorted(ctx->cells)) {
- CellInfo *ci = cell.second;
+ for (auto &cell : ctx->cells) {
+ CellInfo *ci = cell.second.get();
if (ci->bel != BelId()) {
Loc loc = ctx->getBelLocation(ci->bel);
cell_locs[cell.first].x = loc.x;
@@ -591,7 +590,7 @@ class HeAPPlacer
cell_locs[cell.first].global = ctx->getBelGlobalBuf(bel);
// FIXME
- if (has_connectivity(cell.second) && !cfg.ioBufTypes.count(ci->type)) {
+ if (has_connectivity(cell.second.get()) && !cfg.ioBufTypes.count(ci->type)) {
bels_used.insert(bel);
place_cells.push_back(ci);
placed = true;
@@ -612,12 +611,12 @@ class HeAPPlacer
}
// Setup the cells to be solved, returns the number of rows
- int setup_solve_cells(std::unordered_set<BelBucketId> *buckets = nullptr)
+ int setup_solve_cells(pool<BelBucketId> *buckets = nullptr)
{
int row = 0;
solve_cells.clear();
// First clear the udata of all cells
- for (auto cell : sorted(ctx->cells))
+ for (auto &cell : ctx->cells)
cell.second->udata = dont_solve;
// Then update cells to be placed, which excludes cell children
for (auto cell : place_cells) {
@@ -671,8 +670,8 @@ class HeAPPlacer
es.reset();
- for (auto net : sorted(ctx->nets)) {
- NetInfo *ni = net.second;
+ for (auto &net : ctx->nets) {
+ NetInfo *ni = net.second.get();
if (ni->driver.cell == nullptr)
continue;
if (ni->users.empty())
@@ -783,8 +782,8 @@ class HeAPPlacer
wirelen_t total_hpwl()
{
wirelen_t hpwl = 0;
- for (auto net : sorted(ctx->nets)) {
- NetInfo *ni = net.second;
+ for (auto &net : ctx->nets) {
+ NetInfo *ni = net.second.get();
if (ni->driver.cell == nullptr)
continue;
CellLocation &drvloc = cell_locs.at(ni->driver.cell->name);
@@ -809,8 +808,8 @@ class HeAPPlacer
auto startt = std::chrono::high_resolution_clock::now();
// Unbind all cells placed in this solution
- for (auto cell : sorted(ctx->cells)) {
- CellInfo *ci = cell.second;
+ for (auto &cell : ctx->cells) {
+ CellInfo *ci = cell.second.get();
if (ci->bel != BelId() &&
(ci->udata != dont_solve ||
(ci->cluster != ClusterId() && ctx->getClusterRootCell(ci->cluster)->udata != dont_solve)))
@@ -1106,11 +1105,11 @@ class HeAPPlacer
class CutSpreader
{
public:
- CutSpreader(HeAPPlacer *p, const std::unordered_set<BelBucketId> &buckets) : p(p), ctx(p->ctx), buckets(buckets)
+ CutSpreader(HeAPPlacer *p, const pool<BelBucketId> &buckets) : p(p), ctx(p->ctx), buckets(buckets)
{
// Get fast BELs data for all buckets being Cut/Spread.
size_t idx = 0;
- for (BelBucketId bucket : sorted(buckets)) {
+ for (BelBucketId bucket : buckets) {
type_index[bucket] = idx;
FastBels::FastBelsData *fast_bels;
p->fast_bels.getBelsForBelBucket(bucket, &fast_bels);
@@ -1198,8 +1197,8 @@ class HeAPPlacer
private:
HeAPPlacer *p;
Context *ctx;
- std::unordered_set<BelBucketId> buckets;
- std::unordered_map<BelBucketId, size_t> type_index;
+ pool<BelBucketId> buckets;
+ dict<BelBucketId, size_t> type_index;
std::vector<std::vector<std::vector<int>>> occupancy;
std::vector<std::vector<int>> groups;
std::vector<std::vector<ChainExtent>> chaines;
@@ -1208,7 +1207,7 @@ class HeAPPlacer
std::vector<std::vector<std::vector<std::vector<BelId>>> *> fb;
std::vector<SpreaderRegion> regions;
- std::unordered_set<int> merged_regions;
+ pool<int> merged_regions;
// Cells at a location, sorted by real (not integer) x and y
std::vector<std::vector<std::vector<CellInfo *>>> cells_at_location;
@@ -1490,7 +1489,7 @@ class HeAPPlacer
}
}
if (!changed) {
- for (auto bucket : sorted(buckets)) {
+ for (auto bucket : buckets) {
if (reg.cells > reg.bels) {
IdString bucket_name = ctx->getBelBucketName(bucket);
log_error("Failed to expand region (%d, %d) |_> (%d, %d) of %d %ss\n", reg.x0, reg.y0,
diff --git a/common/placer_heap.h b/common/placer_heap.h
index 00913062..9b3c3ed0 100644
--- a/common/placer_heap.h
+++ b/common/placer_heap.h
@@ -46,10 +46,10 @@ struct PlacerHeapCfg
int spread_scale_x, spread_scale_y;
// These cell types will be randomly locked to prevent singular matrices
- std::unordered_set<IdString> ioBufTypes;
+ pool<IdString> ioBufTypes;
// These cell types are part of the same unit (e.g. slices split into
// components) so will always be spread together
- std::vector<std::unordered_set<BelBucketId>> cellGroups;
+ std::vector<pool<BelBucketId>> cellGroups;
};
extern bool placer_heap(Context *ctx, PlacerHeapCfg cfg);
diff --git a/common/pybindings.cc b/common/pybindings.cc
index 504074e1..00ebe66e 100644
--- a/common/pybindings.cc
+++ b/common/pybindings.cc
@@ -164,10 +164,10 @@ PYBIND11_EMBEDDED_MODULE(MODULE_NAME, m)
.def("maxFallDelay", &DelayQuad::maxFallDelay)
.def("delayPair", &DelayQuad::delayPair);
- typedef std::unordered_map<IdString, Property> AttrMap;
- typedef std::unordered_map<IdString, PortInfo> PortMap;
- typedef std::unordered_map<IdString, IdString> IdIdMap;
- typedef std::unordered_map<IdString, std::unique_ptr<Region>> RegionMap;
+ typedef dict<IdString, Property> AttrMap;
+ typedef dict<IdString, PortInfo> PortMap;
+ typedef dict<IdString, IdString> IdIdMap;
+ typedef dict<IdString, std::unique_ptr<Region>> RegionMap;
py::class_<BaseCtx>(m, "BaseCtx");
@@ -218,9 +218,9 @@ PYBIND11_EMBEDDED_MODULE(MODULE_NAME, m)
pass_through<PortType>>::def_wrap(pi_cls, "type");
typedef std::vector<PortRef> PortRefVector;
- typedef std::unordered_map<WireId, PipMap> WireMap;
- typedef std::unordered_set<BelId> BelSet;
- typedef std::unordered_set<WireId> WireSet;
+ typedef dict<WireId, PipMap> WireMap;
+ typedef pool<BelId> BelSet;
+ typedef pool<WireId> WireSet;
auto ni_cls = py::class_<ContextualWrapper<NetInfo &>>(m, "NetInfo");
readwrite_wrapper<NetInfo &, decltype(&NetInfo::name), &NetInfo::name, conv_to_str<IdString>,
diff --git a/common/router1.cc b/common/router1.cc
index 11107a40..374f7455 100644
--- a/common/router1.cc
+++ b/common/router1.cc
@@ -49,16 +49,13 @@ struct arc_key
: net_info->name < other.net_info->name;
}
- struct Hash
+ unsigned int hash() const
{
- std::size_t operator()(const arc_key &arg) const noexcept
- {
- std::size_t seed = std::hash<NetInfo *>()(arg.net_info);
- seed ^= std::hash<int>()(arg.user_idx) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
- seed ^= std::hash<int>()(arg.phys_idx) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
- return seed;
- }
- };
+ std::size_t seed = std::hash<NetInfo *>()(net_info);
+ seed ^= std::hash<int>()(user_idx) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
+ seed ^= std::hash<int>()(phys_idx) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
+ return seed;
+ }
};
struct arc_entry
@@ -107,15 +104,15 @@ struct Router1
const Router1Cfg &cfg;
std::priority_queue<arc_entry, std::vector<arc_entry>, arc_entry::Less> arc_queue;
- std::unordered_map<WireId, std::unordered_set<arc_key, arc_key::Hash>> wire_to_arcs;
- std::unordered_map<arc_key, std::unordered_set<WireId>, arc_key::Hash> arc_to_wires;
- std::unordered_set<arc_key, arc_key::Hash> queued_arcs;
+ dict<WireId, pool<arc_key>> wire_to_arcs;
+ dict<arc_key, pool<WireId>> arc_to_wires;
+ pool<arc_key> queued_arcs;
- std::unordered_map<WireId, QueuedWire> visited;
+ dict<WireId, QueuedWire> visited;
std::priority_queue<QueuedWire, std::vector<QueuedWire>, QueuedWire::Greater> queue;
- std::unordered_map<WireId, int> wireScores;
- std::unordered_map<NetInfo *, int> netScores;
+ dict<WireId, int> wireScores;
+ dict<NetInfo *, int, hash_ptr_ops> netScores;
int arcs_with_ripup = 0;
int arcs_without_ripup = 0;
@@ -295,11 +292,11 @@ struct Router1
void check()
{
- std::unordered_set<arc_key, arc_key::Hash> valid_arcs;
+ pool<arc_key> valid_arcs;
for (auto &net_it : ctx->nets) {
NetInfo *net_info = net_it.second.get();
- std::unordered_set<WireId> valid_wires_for_net;
+ pool<WireId> valid_wires_for_net;
if (skip_net(net_info))
continue;
@@ -357,8 +354,8 @@ struct Router1
void setup()
{
- std::unordered_map<WireId, NetInfo *> src_to_net;
- std::unordered_map<WireId, arc_key> dst_to_arc;
+ dict<WireId, NetInfo *> src_to_net;
+ dict<WireId, arc_key> dst_to_arc;
std::vector<IdString> net_names;
for (auto &net_it : ctx->nets)
@@ -472,7 +469,7 @@ struct Router1
// unbind wires that are currently used exclusively by this arc
- std::unordered_set<WireId> old_arc_wires;
+ pool<WireId> old_arc_wires;
old_arc_wires.swap(arc_to_wires[arc]);
for (WireId wire : old_arc_wires) {
@@ -720,7 +717,7 @@ struct Router1
// bind resulting route (and maybe unroute other nets)
- std::unordered_set<WireId> unassign_wires = arc_to_wires[arc];
+ pool<WireId> unassign_wires = arc_to_wires[arc];
WireId cursor = dst_wire;
delay_t accumulated_path_delay = 0;
@@ -919,10 +916,10 @@ bool Context::checkRoutedDesign() const
struct ExtraWireInfo
{
int order_num = 0;
- std::unordered_set<WireId> children;
+ pool<WireId> children;
};
- std::unordered_map<WireId, ExtraWireInfo> db;
+ dict<WireId, std::unique_ptr<ExtraWireInfo>> db;
for (auto &it : net_info->wires) {
WireId w = it.first;
@@ -930,7 +927,7 @@ bool Context::checkRoutedDesign() const
if (p != PipId()) {
log_assert(ctx->getPipDstWire(p) == w);
- db[ctx->getPipSrcWire(p)].children.insert(w);
+ db.emplace(ctx->getPipSrcWire(p), std::make_unique<ExtraWireInfo>()).first->second->children.insert(w);
}
}
@@ -948,7 +945,7 @@ bool Context::checkRoutedDesign() const
found_unrouted = true;
}
- std::unordered_map<WireId, int> dest_wires;
+ dict<WireId, int> dest_wires;
for (int user_idx = 0; user_idx < int(net_info->users.size()); user_idx++) {
for (auto dst_wire : ctx->getNetinfoSinkWires(net_info, net_info->users[user_idx])) {
log_assert(dst_wire != WireId());
@@ -963,10 +960,10 @@ bool Context::checkRoutedDesign() const
}
std::function<void(WireId, int)> setOrderNum;
- std::unordered_set<WireId> logged_wires;
+ pool<WireId> logged_wires;
setOrderNum = [&](WireId w, int num) {
- auto &db_entry = db[w];
+ auto &db_entry = *db.emplace(w, std::make_unique<ExtraWireInfo>()).first->second;
if (db_entry.order_num != 0) {
found_loop = true;
log(" %*s=> loop\n", 2 * num, "");
@@ -998,10 +995,10 @@ bool Context::checkRoutedDesign() const
}
setOrderNum(src_wire, 1);
- std::unordered_set<WireId> dangling_wires;
+ pool<WireId> dangling_wires;
for (auto &it : db) {
- auto &db_entry = it.second;
+ auto &db_entry = *it.second;
if (db_entry.order_num == 0)
dangling_wires.insert(it.first);
}
@@ -1010,10 +1007,10 @@ bool Context::checkRoutedDesign() const
if (dangling_wires.empty()) {
log(" no dangling wires.\n");
} else {
- std::unordered_set<WireId> root_wires = dangling_wires;
+ pool<WireId> root_wires = dangling_wires;
for (WireId w : dangling_wires) {
- for (WireId c : db[w].children)
+ for (WireId c : db[w]->children)
root_wires.erase(c);
}
@@ -1064,8 +1061,8 @@ bool Context::checkRoutedDesign() const
return true;
}
-bool Context::getActualRouteDelay(WireId src_wire, WireId dst_wire, delay_t *delay,
- std::unordered_map<WireId, PipId> *route, bool useEstimate)
+bool Context::getActualRouteDelay(WireId src_wire, WireId dst_wire, delay_t *delay, dict<WireId, PipId> *route,
+ bool useEstimate)
{
// FIXME
return false;
diff --git a/common/router2.cc b/common/router2.cc
index 2156ce28..e1d3e75b 100644
--- a/common/router2.cc
+++ b/common/router2.cc
@@ -35,7 +35,6 @@
#include <fstream>
#include <queue>
-#include "hash_table.h"
#include "log.h"
#include "nextpnr.h"
#include "router1.h"
@@ -131,8 +130,8 @@ struct Router2
nets.resize(ctx->nets.size());
nets_by_udata.resize(ctx->nets.size());
size_t i = 0;
- for (auto net : sorted(ctx->nets)) {
- NetInfo *ni = net.second;
+ for (auto &net : ctx->nets) {
+ NetInfo *ni = net.second.get();
ni->udata = i;
nets_by_udata.at(i) = ni;
nets.at(i).arcs.resize(ni->users.size());
@@ -198,7 +197,7 @@ struct Router2
}
}
- HashTables::HashMap<WireId, int> wire_to_idx;
+ dict<WireId, int> wire_to_idx;
std::vector<PerWireData> flat_wires;
PerWireData &wire_data(WireId w) { return flat_wires[wire_to_idx.at(w)]; }
@@ -231,8 +230,8 @@ struct Router2
flat_wires.push_back(pwd);
}
- for (auto net_pair : sorted(ctx->nets)) {
- auto *net = net_pair.second;
+ for (auto &net_pair : ctx->nets) {
+ auto *net = net_pair.second.get();
auto &nd = nets.at(net->udata);
for (size_t usr = 0; usr < net->users.size(); usr++) {
auto &ad = nd.arcs.at(usr);
@@ -284,7 +283,7 @@ struct Router2
std::priority_queue<QueuedWire, std::vector<QueuedWire>, QueuedWire::Greater> queue;
// Special case where one net has multiple logical arcs to the same physical sink
- std::unordered_set<WireId> processed_sinks;
+ pool<WireId> processed_sinks;
// Backwards routing
std::queue<int> backwards_queue;
@@ -465,7 +464,7 @@ struct Router2
bool did_something = false;
WireId src = ctx->getNetinfoSourceWire(net);
for (auto sink : ctx->getNetinfoSinkWires(net, net->users.at(i))) {
- std::unordered_set<WireId> rsv;
+ pool<WireId> rsv;
WireId cursor = sink;
bool done = false;
if (ctx->debug)
@@ -1083,7 +1082,7 @@ struct Router2
void write_wiretype_heatmap(std::ostream &out)
{
- std::unordered_map<IdString, std::vector<int>> cong_by_type;
+ dict<IdString, std::vector<int>> cong_by_type;
size_t max_cong = 0;
// Build histogram
for (auto &wd : flat_wires) {
@@ -1099,7 +1098,7 @@ struct Router2
for (size_t i = 0; i <= max_cong; i++)
out << "bound=" << i << ",";
out << std::endl;
- for (auto &ty : sorted_ref(cong_by_type)) {
+ for (auto &ty : cong_by_type) {
out << ctx->nameOf(ty.first) << ",";
for (int count : ty.second)
out << count << ",";
diff --git a/common/sdf.cc b/common/sdf.cc
index 5c3d0a5a..814bf09a 100644
--- a/common/sdf.cc
+++ b/common/sdf.cc
@@ -254,9 +254,9 @@ void Context::writeSDF(std::ostream &out, bool cvc_mode) const
return rf;
};
- for (auto cell : sorted(cells)) {
+ for (const auto &cell : cells) {
Cell sc;
- const CellInfo *ci = cell.second;
+ const CellInfo *ci = cell.second.get();
sc.instance = ci->name.str(this);
sc.celltype = ci->type.str(this);
for (auto port : ci->ports) {
@@ -313,8 +313,8 @@ void Context::writeSDF(std::ostream &out, bool cvc_mode) const
wr.cells.push_back(sc);
}
- for (auto net : sorted(nets)) {
- NetInfo *ni = net.second;
+ for (auto &net : nets) {
+ NetInfo *ni = net.second.get();
if (ni->driver.cell == nullptr)
continue;
for (auto &usr : ni->users) {
diff --git a/common/timing.cc b/common/timing.cc
index ef5977de..1670bc7d 100644
--- a/common/timing.cc
+++ b/common/timing.cc
@@ -23,7 +23,6 @@
#include <boost/range/adaptor/reversed.hpp>
#include <deque>
#include <map>
-#include <unordered_map>
#include <utility>
#include "log.h"
#include "util.h"
@@ -52,17 +51,17 @@ void TimingAnalyser::run()
void TimingAnalyser::init_ports()
{
// Per cell port structures
- for (auto cell : sorted(ctx->cells)) {
- CellInfo *ci = cell.second;
- for (auto port : sorted_ref(ci->ports)) {
+ for (auto &cell : ctx->cells) {
+ CellInfo *ci = cell.second.get();
+ for (auto &port : ci->ports) {
auto &data = ports[CellPortKey(ci->name, port.first)];
data.type = port.second.type;
data.cell_port = CellPortKey(ci->name, port.first);
}
}
// Cell port to net port mapping
- for (auto net : sorted(ctx->nets)) {
- NetInfo *ni = net.second;
+ for (auto &net : ctx->nets) {
+ NetInfo *ni = net.second.get();
if (ni->driver.cell != nullptr)
ports[CellPortKey(ni->driver)].net_port = NetPortKey(ni->name);
for (size_t i = 0; i < ni->users.size(); i++)
@@ -138,8 +137,8 @@ void TimingAnalyser::get_cell_delays()
void TimingAnalyser::get_route_delays()
{
- for (auto net : sorted(ctx->nets)) {
- NetInfo *ni = net.second;
+ for (auto &net : ctx->nets) {
+ NetInfo *ni = net.second.get();
if (ni->driver.cell == nullptr || ni->driver.cell->bel == BelId())
continue;
for (auto &usr : ni->users) {
@@ -272,7 +271,7 @@ void TimingAnalyser::setup_port_domains()
void TimingAnalyser::reset_times()
{
for (auto &port : ports) {
- auto do_reset = [&](std::unordered_map<domain_id_t, ArrivReqTime> &times) {
+ auto do_reset = [&](dict<domain_id_t, ArrivReqTime> &times) {
for (auto &t : times) {
t.second.value = init_delay;
t.second.path_length = 0;
@@ -426,7 +425,7 @@ void TimingAnalyser::walk_backward()
void TimingAnalyser::print_fmax()
{
// Temporary testing code for comparison only
- std::unordered_map<int, double> domain_fmax;
+ dict<int, double> domain_fmax;
for (auto p : topological_order) {
auto &pd = ports.at(p);
for (auto &req : pd.required) {
@@ -591,6 +590,7 @@ struct ClockEvent
ClockEdge edge;
bool operator==(const ClockEvent &other) const { return clock == other.clock && edge == other.edge; }
+ unsigned int hash() const { return mkhash(clock.hash(), int(edge)); }
};
struct ClockPair
@@ -598,37 +598,10 @@ struct ClockPair
ClockEvent start, end;
bool operator==(const ClockPair &other) const { return start == other.start && end == other.end; }
+ unsigned int hash() const { return mkhash(start.hash(), end.hash()); }
};
} // namespace
-NEXTPNR_NAMESPACE_END
-namespace std {
-
-template <> struct hash<NEXTPNR_NAMESPACE_PREFIX ClockEvent>
-{
- std::size_t operator()(const NEXTPNR_NAMESPACE_PREFIX ClockEvent &obj) const noexcept
- {
- std::size_t seed = 0;
- boost::hash_combine(seed, hash<NEXTPNR_NAMESPACE_PREFIX IdString>()(obj.clock));
- boost::hash_combine(seed, hash<int>()(int(obj.edge)));
- return seed;
- }
-};
-
-template <> struct hash<NEXTPNR_NAMESPACE_PREFIX ClockPair>
-{
- std::size_t operator()(const NEXTPNR_NAMESPACE_PREFIX ClockPair &obj) const noexcept
- {
- std::size_t seed = 0;
- boost::hash_combine(seed, hash<NEXTPNR_NAMESPACE_PREFIX ClockEvent>()(obj.start));
- boost::hash_combine(seed, hash<NEXTPNR_NAMESPACE_PREFIX ClockEvent>()(obj.start));
- return seed;
- }
-};
-
-} // namespace std
-NEXTPNR_NAMESPACE_BEGIN
-
typedef std::vector<const PortRef *> PortRefVector;
typedef std::map<int, unsigned> DelayFrequency;
@@ -639,7 +612,7 @@ struct CriticalPath
delay_t path_period;
};
-typedef std::unordered_map<ClockPair, CriticalPath> CriticalPathMap;
+typedef dict<ClockPair, CriticalPath> CriticalPathMap;
struct Timing
{
@@ -660,7 +633,7 @@ struct Timing
delay_t min_remaining_budget;
bool false_startpoint = false;
std::vector<delay_t> min_required;
- std::unordered_map<ClockEvent, delay_t> arrival_time;
+ dict<ClockEvent, delay_t> arrival_time;
};
Timing(Context *ctx, bool net_delays, bool update, CriticalPathMap *crit_path = nullptr,
@@ -677,14 +650,14 @@ struct Timing
// First, compute the topological order of nets to walk through the circuit, assuming it is a _acyclic_ graph
// TODO(eddieh): Handle the case where it is cyclic, e.g. combinatorial loops
std::vector<NetInfo *> topological_order;
- std::unordered_map<const NetInfo *, std::unordered_map<ClockEvent, TimingData>> net_data;
+ dict<const NetInfo *, dict<ClockEvent, TimingData>, hash_ptr_ops> net_data;
// In lieu of deleting edges from the graph, simply count the number of fanins to each output port
- std::unordered_map<const PortInfo *, unsigned> port_fanin;
+ dict<const PortInfo *, unsigned, hash_ptr_ops> port_fanin;
std::vector<IdString> input_ports;
std::vector<const PortInfo *> output_ports;
- std::unordered_set<IdString> ooc_port_nets;
+ pool<IdString> ooc_port_nets;
// In out-of-context mode, top-level inputs look floating but aren't
if (bool_or_default(ctx->settings, ctx->id("arch.ooc"))) {
@@ -880,7 +853,7 @@ struct Timing
}
}
- std::unordered_map<ClockPair, std::pair<delay_t, NetInfo *>> crit_nets;
+ dict<ClockPair, std::pair<delay_t, NetInfo *>> crit_nets;
// Now go backwards topologically to determine the minimum path slack, and to distribute all path slack evenly
// between all nets on the path
diff --git a/common/timing.h b/common/timing.h
index 133bd4eb..974bb26b 100644
--- a/common/timing.h
+++ b/common/timing.h
@@ -35,15 +35,7 @@ struct CellPortKey
port = pr.port;
}
IdString cell, port;
- struct Hash
- {
- inline std::size_t operator()(const CellPortKey &arg) const noexcept
- {
- std::size_t seed = std::hash<IdString>()(arg.cell);
- seed ^= std::hash<IdString>()(arg.port) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
- return seed;
- }
- };
+ unsigned int hash() const { return mkhash(cell.hash(), port.hash()); }
inline bool operator==(const CellPortKey &other) const { return (cell == other.cell) && (port == other.port); }
inline bool operator!=(const CellPortKey &other) const { return (cell != other.cell) || (port != other.port); }
inline bool operator<(const CellPortKey &other) const
@@ -69,15 +61,8 @@ struct NetPortKey
return idx;
}
- struct Hash
- {
- std::size_t operator()(const NetPortKey &arg) const noexcept
- {
- std::size_t seed = std::hash<IdString>()(arg.net);
- seed ^= std::hash<size_t>()(arg.idx) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
- return seed;
- }
- };
+ unsigned int hash() const { return mkhash(net.hash(), idx); }
+
inline bool operator==(const NetPortKey &other) const { return (net == other.net) && (idx == other.idx); }
};
@@ -89,15 +74,8 @@ struct ClockDomainKey
// probably also need something here to deal with constraints
inline bool is_async() const { return clock == IdString(); }
- struct Hash
- {
- std::size_t operator()(const ClockDomainKey &arg) const noexcept
- {
- std::size_t seed = std::hash<IdString>()(arg.clock);
- seed ^= std::hash<int>()(int(arg.edge)) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
- return seed;
- }
- };
+ unsigned int hash() const { return mkhash(clock.hash(), int(edge)); }
+
inline bool operator==(const ClockDomainKey &other) const { return (clock == other.clock) && (edge == other.edge); }
};
@@ -111,15 +89,7 @@ struct ClockDomainPairKey
{
return (launch == other.launch) && (capture == other.capture);
}
- struct Hash
- {
- std::size_t operator()(const ClockDomainPairKey &arg) const noexcept
- {
- std::size_t seed = std::hash<domain_id_t>()(arg.launch);
- seed ^= std::hash<domain_id_t>()(arg.capture) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
- return seed;
- }
- };
+ unsigned int hash() const { return mkhash(launch, capture); }
};
struct TimingAnalyser
@@ -223,16 +193,17 @@ struct TimingAnalyser
NetPortKey net_port;
PortType type;
// per domain timings
- std::unordered_map<domain_id_t, ArrivReqTime> arrival;
- std::unordered_map<domain_id_t, ArrivReqTime> required;
- std::unordered_map<domain_id_t, PortDomainPairData> domain_pairs;
+ dict<domain_id_t, ArrivReqTime> arrival;
+ dict<domain_id_t, ArrivReqTime> required;
+ dict<domain_id_t, PortDomainPairData> domain_pairs;
// cell timing arcs to (outputs)/from (inputs) from this port
std::vector<CellArc> cell_arcs;
// routing delay into this port (input ports only)
- DelayPair route_delay;
+ DelayPair route_delay{0};
// worst criticality and slack across domain pairs
- float worst_crit;
- delay_t worst_setup_slack, worst_hold_slack;
+ float worst_crit = 0;
+ delay_t worst_setup_slack = std::numeric_limits<delay_t>::max(),
+ worst_hold_slack = std::numeric_limits<delay_t>::max();
};
struct PerDomain
@@ -260,9 +231,9 @@ struct TimingAnalyser
void copy_domains(const CellPortKey &from, const CellPortKey &to, bool backwards);
- std::unordered_map<CellPortKey, PerPort, CellPortKey::Hash> ports;
- std::unordered_map<ClockDomainKey, domain_id_t, ClockDomainKey::Hash> domain_to_id;
- std::unordered_map<ClockDomainPairKey, domain_id_t, ClockDomainPairKey::Hash> pair_to_id;
+ dict<CellPortKey, PerPort> ports;
+ dict<ClockDomainKey, domain_id_t> domain_to_id;
+ dict<ClockDomainPairKey, domain_id_t> pair_to_id;
std::vector<PerDomain> domains;
std::vector<PerDomainPair> domain_pairs;
diff --git a/common/timing_opt.cc b/common/timing_opt.cc
index 854cbc5b..da4907b6 100644
--- a/common/timing_opt.cc
+++ b/common/timing_opt.cc
@@ -35,8 +35,6 @@
#include "timing.h"
#include "util.h"
-#include "hash_table.h"
-
NEXTPNR_NAMESPACE_BEGIN
class TimingOptimiser
@@ -68,8 +66,8 @@ class TimingOptimiser
void setup_delay_limits()
{
max_net_delay.clear();
- for (auto net : sorted(ctx->nets)) {
- NetInfo *ni = net.second;
+ for (auto &net : ctx->nets) {
+ NetInfo *ni = net.second.get();
if (ni->driver.cell == nullptr)
continue;
for (auto usr : ni->users) {
@@ -167,7 +165,7 @@ class TimingOptimiser
BelId curr = cell->bel;
Loc curr_loc = ctx->getBelLocation(curr);
int found_count = 0;
- cell_neighbour_bels[cell->name] = std::unordered_set<BelId>{};
+ cell_neighbour_bels[cell->name] = pool<BelId>{};
for (int dy = -d; dy <= d; dy++) {
for (int dx = -d; dx <= d; dx++) {
// Go through all the Bels at this location
@@ -239,7 +237,7 @@ class TimingOptimiser
std::vector<std::pair<NetInfo *, int>> crit_nets;
std::vector<IdString> netnames;
std::transform(ctx->nets.begin(), ctx->nets.end(), std::back_inserter(netnames),
- [](const std::pair<const IdString, std::unique_ptr<NetInfo>> &kv) { return kv.first; });
+ [](const std::pair<IdString, std::unique_ptr<NetInfo>> &kv) { return kv.first; });
ctx->sorted_shuffle(netnames);
for (auto net : netnames) {
if (crit_nets.size() >= max_count)
@@ -267,7 +265,7 @@ class TimingOptimiser
}
NPNR_ASSERT_FALSE("port user not found on net");
};
- std::unordered_set<PortRef *> used_ports;
+ pool<PortRef *, hash_ptr_ops> used_ports;
for (auto crit_net : crit_nets) {
@@ -439,10 +437,10 @@ class TimingOptimiser
}
// Actual BFS path optimisation algorithm
- std::unordered_map<IdString, std::unordered_map<BelId, delay_t>> cumul_costs;
- std::unordered_map<std::pair<IdString, BelId>, std::pair<IdString, BelId>, PairHash> backtrace;
+ dict<IdString, dict<BelId, delay_t>> cumul_costs;
+ dict<std::pair<IdString, BelId>, std::pair<IdString, BelId>> backtrace;
std::queue<std::pair<int, BelId>> visit;
- std::unordered_set<std::pair<int, BelId>, PairHash> to_visit;
+ pool<std::pair<int, BelId>> to_visit;
for (auto startbel : cell_neighbour_bels[path_cells.front()]) {
// Swap for legality check
@@ -568,10 +566,10 @@ class TimingOptimiser
// Current candidate Bels for cells (linked in both direction>
std::vector<IdString> path_cells;
- std::unordered_map<IdString, std::unordered_set<BelId>> cell_neighbour_bels;
- std::unordered_map<BelId, std::unordered_set<IdString>> bel_candidate_cells;
+ dict<IdString, pool<BelId>> cell_neighbour_bels;
+ dict<BelId, pool<IdString>> bel_candidate_cells;
// Map cell ports to net delay limit
- std::unordered_map<std::pair<IdString, IdString>, delay_t, PairHash> max_net_delay;
+ dict<std::pair<IdString, IdString>, delay_t> max_net_delay;
Context *ctx;
TimingOptCfg cfg;
TimingAnalyser tmg;
diff --git a/common/timing_opt.h b/common/timing_opt.h
index 775d9596..46bf3500 100644
--- a/common/timing_opt.h
+++ b/common/timing_opt.h
@@ -29,7 +29,7 @@ struct TimingOptCfg
// The timing optimiser will *only* optimise cells of these types
// Normally these would only be logic cells (or tiles if applicable), the algorithm makes little sense
// for other cell types
- std::unordered_set<IdString> cellTypes;
+ pool<IdString> cellTypes;
};
extern bool timing_opt(Context *ctx, TimingOptCfg cfg);
diff --git a/common/util.h b/common/util.h
index 540646c7..542bd395 100644
--- a/common/util.h
+++ b/common/util.h
@@ -55,7 +55,7 @@ std::string str_or_default(const Container &ct, const KeyType &key, std::string
};
template <typename KeyType>
-std::string str_or_default(const std::unordered_map<KeyType, Property> &ct, const KeyType &key, std::string def = "")
+std::string str_or_default(const dict<KeyType, Property> &ct, const KeyType &key, std::string def = "")
{
auto found = ct.find(key);
if (found == ct.end())
@@ -78,8 +78,7 @@ template <typename Container, typename KeyType> int int_or_default(const Contain
return std::stoi(found->second);
};
-template <typename KeyType>
-int int_or_default(const std::unordered_map<KeyType, Property> &ct, const KeyType &key, int def = 0)
+template <typename KeyType> int int_or_default(const dict<KeyType, Property> &ct, const KeyType &key, int def = 0)
{
auto found = ct.find(key);
if (found == ct.end())
@@ -103,42 +102,6 @@ bool bool_or_default(const Container &ct, const KeyType &key, bool def = false)
return bool(int_or_default(ct, key, int(def)));
};
-// Wrap an unordered_map, and allow it to be iterated over sorted by key
-template <typename K, typename V> std::map<K, V *> sorted(const std::unordered_map<K, std::unique_ptr<V>> &orig)
-{
- std::map<K, V *> retVal;
- for (auto &item : orig)
- retVal.emplace(std::make_pair(item.first, item.second.get()));
- return retVal;
-};
-
-// Wrap an unordered_map, and allow it to be iterated over sorted by key
-template <typename K, typename V> std::map<K, V &> sorted_ref(std::unordered_map<K, V> &orig)
-{
- std::map<K, V &> retVal;
- for (auto &item : orig)
- retVal.emplace(std::make_pair(item.first, std::ref(item.second)));
- return retVal;
-};
-
-// Wrap an unordered_map, and allow it to be iterated over sorted by key
-template <typename K, typename V> std::map<K, const V &> sorted_cref(const std::unordered_map<K, V> &orig)
-{
- std::map<K, const V &> retVal;
- for (auto &item : orig)
- retVal.emplace(std::make_pair(item.first, std::ref(item.second)));
- return retVal;
-};
-
-// Wrap an unordered_set, and allow it to be iterated over sorted by key
-template <typename K> std::set<K> sorted(const std::unordered_set<K> &orig)
-{
- std::set<K> retVal;
- for (auto &item : orig)
- retVal.insert(item);
- return retVal;
-};
-
// Return a net if port exists, or nullptr
inline const NetInfo *get_net_or_empty(const CellInfo *cell, const IdString port)
{
generated by cgit v1.2.3 (git 2.25.1) at 2025-04-15 17:00:45 +0000