Merge pull request #718 from YosysHQ/gatecat/hashlib

Moving from unordered_{map, set} to hashlib

10 files changed, 52 insertions, 76 deletions

diff --git a/mistral/arch.cc b/mistral/arch.cc
index cfa3e8b3..70e8f806 100644
--- a/mistral/arch.cc
+++ b/mistral/arch.cc
@@ -375,8 +375,8 @@ void Arch::assign_default_pinmap(CellInfo *cell)
 
 void Arch::assignArchInfo()
 {
-    for (auto cell : sorted(cells)) {
-        CellInfo *ci = cell.second;
+    for (auto &cell : cells) {
+        CellInfo *ci = cell.second.get();
         if (is_comb_cell(ci->type))
             assign_comb_info(ci);
         else if (ci->type == id_MISTRAL_FF)
diff --git a/mistral/arch.h b/mistral/arch.h
index ee2c84a3..1a42530a 100644
--- a/mistral/arch.h
+++ b/mistral/arch.h
@@ -85,7 +85,7 @@ struct BelInfo
     // For cases where we need to determine an original block index, due to multiple bels at the same tile this
     // might not be the same as the nextpnr z-coordinate
     int block_index;
-    std::unordered_map<IdString, PinInfo> pins;
+    dict<IdString, PinInfo> pins;
     // Info for different kinds of bels
     union
     {
@@ -153,7 +153,7 @@ struct UpDownhillPipRange
     UpDownhillPipIterator b, e;
 
     UpDownhillPipRange(const std::vector<WireId> &v, WireId other_wire, bool is_uphill)
-            : b(v.cbegin(), other_wire, is_uphill), e(v.cend(), other_wire, is_uphill){};
+            : b(v.begin(), other_wire, is_uphill), e(v.end(), other_wire, is_uphill){};
 
     UpDownhillPipIterator begin() const { return b; }
     UpDownhillPipIterator end() const { return e; }
@@ -161,7 +161,7 @@ struct UpDownhillPipRange
 
 // This iterates over the list of wires, and for each wire yields its uphill pips, as an efficient way of going over
 // all the pips in the device
-using WireMapIterator = std::unordered_map<WireId, WireInfo>::const_iterator;
+using WireMapIterator = dict<WireId, WireInfo>::const_iterator;
 struct AllPipIterator
 {
     WireMapIterator base, end;
@@ -196,8 +196,7 @@ struct AllPipRange
 {
     AllPipIterator b, e;
 
-    AllPipRange(const std::unordered_map<WireId, WireInfo> &wires)
-            : b(wires.cbegin(), wires.cend(), -1), e(wires.cend(), wires.cend(), 0)
+    AllPipRange(const dict<WireId, WireInfo> &wires) : b(wires.begin(), wires.end(), -1), e(wires.end(), wires.end(), 0)
     {
         // Starting the begin iterator at index -1 and incrementing it ensures we skip over the first wire if it has no
         // uphill pips
@@ -211,7 +210,7 @@ struct AllPipRange
 // This transforms a map to a range of keys, used as the wire iterator
 template <typename T> struct key_range
 {
-    key_range(const T &t) : b(t.cbegin()), e(t.cend()){};
+    key_range(const T &t) : b(t.begin()), e(t.end()){};
     typename T::const_iterator b, e;
 
     struct xformed_iterator : public T::const_iterator
@@ -224,7 +223,7 @@ template <typename T> struct key_range
     xformed_iterator end() const { return xformed_iterator(e); }
 };
 
-using AllWireRange = key_range<std::unordered_map<WireId, WireInfo>>;
+using AllWireRange = key_range<dict<WireId, WireInfo>>;
 
 struct ArchRanges : BaseArchRanges
 {
@@ -489,7 +488,7 @@ struct Arch : BaseArch<ArchRanges>
     static const std::string defaultRouter;
     static const std::vector<std::string> availableRouters;
 
-    std::unordered_map<WireId, WireInfo> wires;
+    dict<WireId, WireInfo> wires;
 
     // List of LABs
     std::vector<LABInfo> labs;
@@ -499,13 +498,13 @@ struct Arch : BaseArch<ArchRanges>
 
     // Conversion between numbers and rnode types and IdString, for fast wire name implementation
     std::vector<IdString> int2id;
-    std::unordered_map<IdString, int> id2int;
+    dict<IdString, int> id2int;
 
     std::vector<IdString> rn_t2id;
-    std::unordered_map<IdString, CycloneV::rnode_type_t> id2rn_t;
+    dict<IdString, CycloneV::rnode_type_t> id2rn_t;
 
     // This structure is only used for nextpnr-created wires
-    std::unordered_map<IdStringList, WireId> npnr_wirebyname;
+    dict<IdStringList, WireId> npnr_wirebyname;
 
     std::vector<std::vector<BelInfo>> bels_by_tile;
     std::vector<BelId> all_bels;
@@ -525,18 +524,18 @@ struct Arch : BaseArch<ArchRanges>
     // -------------------------------------------------
 
     void assign_default_pinmap(CellInfo *cell);
-    static const std::unordered_map<IdString, IdString> comb_pinmap;
+    static const dict<IdString, IdString> comb_pinmap;
 
     // -------------------------------------------------
 
-    typedef std::unordered_map<IdString, CellPinStyle> CellPinsData;            // pins.cc
-    static const std::unordered_map<IdString, CellPinsData> cell_pins_db;       // pins.cc
+    typedef dict<IdString, CellPinStyle> CellPinsData;                          // pins.cc
+    static const dict<IdString, CellPinsData> cell_pins_db;                     // pins.cc
     CellPinStyle get_cell_pin_style(const CellInfo *cell, IdString port) const; // pins.cc
 
     // -------------------------------------------------
 
     // List of IO constraints, used by QSF parser
-    std::unordered_map<IdString, std::unordered_map<IdString, Property>> io_attr;
+    dict<IdString, dict<IdString, Property>> io_attr;
     void read_qsf(std::istream &in); // qsf.cc
 
     // -------------------------------------------------
diff --git a/mistral/arch_pybindings.cc b/mistral/arch_pybindings.cc
index 23716c93..c44a1fab 100644
--- a/mistral/arch_pybindings.cc
+++ b/mistral/arch_pybindings.cc
@@ -50,10 +50,10 @@ void arch_wrap_python(py::module &m)
     fn_wrapper_2a<Context, decltype(&Context::compute_lut_mask), &Context::compute_lut_mask, pass_through<uint64_t>,
                   pass_through<uint32_t>, pass_through<uint8_t>>::def_wrap(ctx_cls, "compute_lut_mask");
 
-    typedef std::unordered_map<IdString, std::unique_ptr<CellInfo>> CellMap;
-    typedef std::unordered_map<IdString, std::unique_ptr<NetInfo>> NetMap;
-    typedef std::unordered_map<IdString, IdString> AliasMap;
-    typedef std::unordered_map<IdString, HierarchicalCell> HierarchyMap;
+    typedef dict<IdString, std::unique_ptr<CellInfo>> CellMap;
+    typedef dict<IdString, std::unique_ptr<NetInfo>> NetMap;
+    typedef dict<IdString, IdString> AliasMap;
+    typedef dict<IdString, HierarchicalCell> HierarchyMap;
 
     auto belpin_cls = py::class_<ContextualWrapper<BelPin>>(m, "BelPin");
     readonly_wrapper<BelPin, decltype(&BelPin::bel), &BelPin::bel, conv_to_str<BelId>>::def_wrap(belpin_cls, "bel");
diff --git a/mistral/archdefs.h b/mistral/archdefs.h
index 60bdcfeb..8b4256ab 100644
--- a/mistral/archdefs.h
+++ b/mistral/archdefs.h
@@ -20,15 +20,16 @@
 #ifndef MISTRAL_ARCHDEFS_H
 #define MISTRAL_ARCHDEFS_H
 
-#include <boost/functional/hash.hpp>
-
 #include "base_clusterinfo.h"
 #include "cyclonev.h"
 
+#include "hashlib.h"
 #include "idstring.h"
 #include "nextpnr_assertions.h"
 #include "nextpnr_namespaces.h"
 
+#include <limits>
+
 NEXTPNR_NAMESPACE_BEGIN
 
 using mistral::CycloneV;
@@ -84,6 +85,7 @@ struct BelId
     bool operator==(const BelId &other) const { return pos == other.pos && z == other.z; }
     bool operator!=(const BelId &other) const { return pos != other.pos || z != other.z; }
     bool operator<(const BelId &other) const { return pos < other.pos || (pos == other.pos && z < other.z); }
+    unsigned int hash() const { return mkhash(pos, z); }
 };
 
 static constexpr auto invalid_rnode = std::numeric_limits<CycloneV::rnode_t>::max();
@@ -104,6 +106,7 @@ struct WireId
     bool operator==(const WireId &other) const { return node == other.node; }
     bool operator!=(const WireId &other) const { return node != other.node; }
     bool operator<(const WireId &other) const { return node < other.node; }
+    unsigned int hash() const { return unsigned(node); }
 };
 
 struct PipId
@@ -115,6 +118,7 @@ struct PipId
     bool operator==(const PipId &other) const { return src == other.src && dst == other.dst; }
     bool operator!=(const PipId &other) const { return src != other.src || dst != other.dst; }
     bool operator<(const PipId &other) const { return dst < other.dst || (dst == other.dst && src < other.src); }
+    unsigned int hash() const { return mkhash(src, dst); }
 };
 
 typedef IdString DecalId;
@@ -199,38 +203,11 @@ struct ArchCellInfo : BaseClusterInfo
         } ffInfo;
     };
 
-    std::unordered_map<IdString, ArchPinInfo> pin_data;
+    dict<IdString, ArchPinInfo> pin_data;
 
     CellPinState get_pin_state(IdString pin) const;
 };
 
 NEXTPNR_NAMESPACE_END
 
-namespace std {
-template <> struct hash<NEXTPNR_NAMESPACE_PREFIX BelId>
-{
-    std::size_t operator()(const NEXTPNR_NAMESPACE_PREFIX BelId &bel) const noexcept
-    {
-        return hash<uint32_t>()((static_cast<uint32_t>(bel.pos) << 16) | bel.z);
-    }
-};
-
-template <> struct hash<NEXTPNR_NAMESPACE_PREFIX WireId>
-{
-    std::size_t operator()(const NEXTPNR_NAMESPACE_PREFIX WireId &wire) const noexcept
-    {
-        return hash<uint32_t>()(wire.node);
-    }
-};
-
-template <> struct hash<NEXTPNR_NAMESPACE_PREFIX PipId>
-{
-    std::size_t operator()(const NEXTPNR_NAMESPACE_PREFIX PipId &pip) const noexcept
-    {
-        return hash<uint64_t>()((uint64_t(pip.dst) << 32) | pip.src);
-    }
-};
-
-} // namespace std
-
 #endif
diff --git a/mistral/bitstream.cc b/mistral/bitstream.cc
index 340ba6b9..0e8b9c85 100644
--- a/mistral/bitstream.cc
+++ b/mistral/bitstream.cc
@@ -156,9 +156,9 @@ struct MistralBitgen
 
     void write_routing()
     {
-        for (auto net : sorted(ctx->nets)) {
-            NetInfo *ni = net.second;
-            for (auto wire : sorted_ref(ni->wires)) {
+        for (auto &net : ctx->nets) {
+            NetInfo *ni = net.second.get();
+            for (auto &wire : ni->wires) {
                 PipId pip = wire.second.pip;
                 if (pip == PipId())
                     continue;
@@ -200,8 +200,8 @@ struct MistralBitgen
 
     void write_cells()
     {
-        for (auto cell : sorted(ctx->cells)) {
-            CellInfo *ci = cell.second;
+        for (auto &cell : ctx->cells) {
+            CellInfo *ci = cell.second.get();
             Loc loc = ctx->getBelLocation(ci->bel);
             int bi = ctx->bel_data(ci->bel).block_index;
             if (ctx->is_io_cell(ci->type))
diff --git a/mistral/lab.cc b/mistral/lab.cc
index abd0fec3..56bc604a 100644
--- a/mistral/lab.cc
+++ b/mistral/lab.cc
@@ -718,7 +718,7 @@ void Arch::reassign_alm_inputs(uint32_t lab, uint8_t alm)
         //  - C, E0, and F0 are exclusive to the top LUT5 secion
         //  - D, E1, and F1 are exclusive to the bottom LUT5 section
         // First find up to two shared inputs
-        std::unordered_map<IdString, int> shared_nets;
+        dict<IdString, int> shared_nets;
         if (luts[0] && luts[1]) {
             for (int i = 0; i < luts[0]->combInfo.lut_input_count; i++) {
                 for (int j = 0; j < luts[1]->combInfo.lut_input_count; j++) {
@@ -826,7 +826,7 @@ void Arch::reassign_alm_inputs(uint32_t lab, uint8_t alm)
 
 // This default cell-bel pin mapping is used to provide estimates during placement only. It will have errors and
 // overlaps and a correct mapping will be resolved twixt placement and routing
-const std::unordered_map<IdString, IdString> Arch::comb_pinmap = {
+const dict<IdString, IdString> Arch::comb_pinmap = {
         {id_A, id_F0}, // fastest input first
         {id_B, id_E0}, {id_C, id_D}, {id_D, id_C},       {id_D0, id_C},       {id_D1, id_B},
         {id_E, id_B},  {id_F, id_A}, {id_Q, id_COMBOUT}, {id_SO, id_COMBOUT},
diff --git a/mistral/main.cc b/mistral/main.cc
index 7b4f9594..0afba3d8 100644
--- a/mistral/main.cc
+++ b/mistral/main.cc
@@ -33,7 +33,7 @@ class MistralCommandHandler : public CommandHandler
   public:
     MistralCommandHandler(int argc, char **argv);
     virtual ~MistralCommandHandler(){};
-    std::unique_ptr<Context> createContext(std::unordered_map<std::string, Property> &values) override;
+    std::unique_ptr<Context> createContext(dict<std::string, Property> &values) override;
     void setupArchContext(Context *ctx) override{};
     void customBitstream(Context *ctx) override;
     void customAfterLoad(Context *ctx) override;
@@ -71,7 +71,7 @@ void MistralCommandHandler::customBitstream(Context *ctx)
     }
 }
 
-std::unique_ptr<Context> MistralCommandHandler::createContext(std::unordered_map<std::string, Property> &values)
+std::unique_ptr<Context> MistralCommandHandler::createContext(dict<std::string, Property> &values)
 {
     ArchArgs chipArgs;
     if (!vm.count("mistral")) {
diff --git a/mistral/pack.cc b/mistral/pack.cc
index 90fbfd78..98ab22bf 100644
--- a/mistral/pack.cc
+++ b/mistral/pack.cc
@@ -133,8 +133,8 @@ struct MistralPacker
         // Remove unused inverters and high/low drivers
         std::vector<IdString> trim_cells;
         std::vector<IdString> trim_nets;
-        for (auto cell : sorted(ctx->cells)) {
-            CellInfo *ci = cell.second;
+        for (auto &cell : ctx->cells) {
+            CellInfo *ci = cell.second.get();
             if (ci->type != id_MISTRAL_NOT && ci->type != id_GND && ci->type != id_VCC)
                 continue;
             IdString port = (ci->type == id_MISTRAL_NOT) ? id_Q : id_Y;
@@ -161,15 +161,15 @@ struct MistralPacker
     void pack_constants()
     {
         // Iterate through cells
-        for (auto cell : sorted(ctx->cells)) {
-            CellInfo *ci = cell.second;
+        for (auto &cell : ctx->cells) {
+            CellInfo *ci = cell.second.get();
             // Skip certain cells at this point
             if (ci->type != id_MISTRAL_NOT && ci->type != id_GND && ci->type != id_VCC)
-                process_inv_constants(cell.second);
+                process_inv_constants(ci);
         }
         // Special case - SDATA can only be trimmed if SLOAD is low
-        for (auto cell : sorted(ctx->cells)) {
-            CellInfo *ci = cell.second;
+        for (auto &cell : ctx->cells) {
+            CellInfo *ci = cell.second.get();
             if (ci->type != id_MISTRAL_FF)
                 continue;
             if (ci->get_pin_state(id_SLOAD) != PIN_0)
@@ -185,7 +185,7 @@ struct MistralPacker
         // Find the actual IO buffer corresponding to a port; and copy attributes across to it
         // Note that this relies on Yosys to do IO buffer inference, to avoid tristate issues once we get to synthesised
         // JSON. In all cases the nextpnr-inserted IO buffers are removed as redundant.
-        for (auto &port : sorted_ref(ctx->ports)) {
+        for (auto &port : ctx->ports) {
             if (!ctx->cells.count(port.first))
                 log_error("Port '%s' doesn't seem to have a corresponding top level IO\n", ctx->nameOf(port.first));
             CellInfo *ci = ctx->cells.at(port.first).get();
@@ -256,8 +256,8 @@ struct MistralPacker
         // Step 0: deal with top level inserted IO buffers
         prepare_io();
         // Stage 1: apply constraints
-        for (auto cell : sorted(ctx->cells)) {
-            CellInfo *ci = cell.second;
+        for (auto &cell : ctx->cells) {
+            CellInfo *ci = cell.second.get();
             // Iterate through all IO buffer primitives
             if (!ctx->is_io_cell(ci->type))
                 continue;
@@ -286,8 +286,8 @@ struct MistralPacker
 
     void constrain_carries()
     {
-        for (auto cell : sorted(ctx->cells)) {
-            CellInfo *ci = cell.second;
+        for (auto &cell : ctx->cells) {
+            CellInfo *ci = cell.second.get();
             if (ci->type != id_MISTRAL_ALUT_ARITH)
                 continue;
             const NetInfo *cin = get_net_or_empty(ci, id_CI);
@@ -332,8 +332,8 @@ struct MistralPacker
             }
         }
         // Check we reached all the cells in the above pass
-        for (auto cell : sorted(ctx->cells)) {
-            CellInfo *ci = cell.second;
+        for (auto &cell : ctx->cells) {
+            CellInfo *ci = cell.second.get();
             if (ci->type != id_MISTRAL_ALUT_ARITH)
                 continue;
             if (ci->cluster == ClusterId())
diff --git a/mistral/pins.cc b/mistral/pins.cc
index c3637115..51cb83c4 100644
--- a/mistral/pins.cc
+++ b/mistral/pins.cc
@@ -23,7 +23,7 @@
 
 NEXTPNR_NAMESPACE_BEGIN
 
-const std::unordered_map<IdString, Arch::CellPinsData> Arch::cell_pins_db = {
+const dict<IdString, Arch::CellPinsData> Arch::cell_pins_db = {
         // For combinational cells, inversion and tieing can be implemented by manipulating the LUT function
         {id_MISTRAL_ALUT2, {{{}, PINSTYLE_COMB}}},
         {id_MISTRAL_ALUT3, {{{}, PINSTYLE_COMB}}},
diff --git a/mistral/qsf.cc b/mistral/qsf.cc
index 9a128595..88f51b1b 100644
--- a/mistral/qsf.cc
+++ b/mistral/qsf.cc
@@ -34,7 +34,7 @@ struct QsfOption
     bool required;    // error out if this option isn't passed
 };
 
-typedef std::unordered_map<std::string, std::vector<std::string>> option_map_t;
+typedef dict<std::string, std::vector<std::string>> option_map_t;
 
 struct QsfCommand
 {