Switch to potentially-sparse net users array

This uses a new data structure for net.users that allows gaps, so
removing a port from a net is no longer an O(n) operation on the number
of users the net has.

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

3 files changed, 14 insertions, 22 deletions

diff --git a/fpga_interchange/arch.cc b/fpga_interchange/arch.cc
index 917af85e..a5e802d3 100644
--- a/fpga_interchange/arch.cc
+++ b/fpga_interchange/arch.cc
@@ -1377,7 +1377,7 @@ void Arch::merge_constant_nets()
             }
 
             NPNR_ASSERT(net->driver.port == gnd_cell_port);
-            std::vector<PortRef> users_copy = net->users;
+            indexed_store<PortRef> users_copy = net->users;
             for (const PortRef &port_ref : users_copy) {
                 IdString cell = port_ref.cell->name;
                 disconnectPort(cell, port_ref.port);
@@ -1400,7 +1400,7 @@ void Arch::merge_constant_nets()
             }
 
             NPNR_ASSERT(net->driver.port == vcc_cell_port);
-            std::vector<PortRef> users_copy = net->users;
+            indexed_store<PortRef> users_copy = net->users;
             for (const PortRef &port_ref : users_copy) {
                 IdString cell = port_ref.cell->name;
                 disconnectPort(cell, port_ref.port);
diff --git a/fpga_interchange/arch_pack_clusters.cc b/fpga_interchange/arch_pack_clusters.cc
index 31e0522b..97a3e1a5 100644
--- a/fpga_interchange/arch_pack_clusters.cc
+++ b/fpga_interchange/arch_pack_clusters.cc
@@ -945,10 +945,10 @@ void Arch::prepare_cluster(const ClusterPOD *cluster, uint32_t index)
                 if (port_info.type == PORT_OUT) {
                     exclude_nets.insert(port_info.net->name);
                     auto &users = port_info.net->users;
-                    if (users.size() != 1)
+                    if (users.entries() != 1)
                         continue;
 
-                    CellInfo *user_cell = users[0].cell;
+                    CellInfo *user_cell = (*users.begin()).cell;
                     if (user_cell == nullptr)
                         continue;
 
@@ -978,7 +978,7 @@ void Arch::prepare_cluster(const ClusterPOD *cluster, uint32_t index)
                 } else if (port_info.type == PORT_IN) {
                     auto &driver = port_info.net->driver;
                     auto &users = port_info.net->users;
-                    if (users.size() != 1)
+                    if (users.entries() != 1)
                         continue;
 
                     CellInfo *driver_cell = driver.cell;
diff --git a/fpga_interchange/globals.cc b/fpga_interchange/globals.cc
index ed9f73a6..6efd1d89 100644
--- a/fpga_interchange/globals.cc
+++ b/fpga_interchange/globals.cc
@@ -41,8 +41,8 @@ struct GlobalVist
 
 // This is our main global routing implementation. It is used both to actually route globals; and also to discover if
 // global buffers have available short routes from their source for auto-placement
-static int route_global_arc(Context *ctx, NetInfo *net, size_t usr_idx, size_t phys_port_idx, int max_hops,
-                            bool dry_run)
+static int route_global_arc(Context *ctx, NetInfo *net, store_index<PortRef> usr_idx, size_t phys_port_idx,
+                            int max_hops, bool dry_run)
 {
     auto &usr = net->users.at(usr_idx);
     WireId src = ctx->getNetinfoSourceWire(net);
@@ -51,7 +51,7 @@ static int route_global_arc(Context *ctx, NetInfo *net, size_t usr_idx, size_t p
         if (dry_run)
             return -1;
         else
-            log_error("Arc %d.%d (%s.%s) of net %s has no sink wire!\n", int(usr_idx), int(phys_port_idx),
+            log_error("Arc %d.%d (%s.%s) of net %s has no sink wire!\n", usr_idx.idx(), int(phys_port_idx),
                       ctx->nameOf(usr.cell), ctx->nameOf(usr.port), ctx->nameOf(net));
     }
     // Consider any existing routing put in place by the site router, etc
@@ -188,14 +188,6 @@ void Arch::place_globals()
             // Ignore if there is no driver; or the driver is not placed
             if (net->driver.cell == nullptr || net->driver.cell->bel == BelId())
                 continue;
-            size_t user_idx = 0;
-            bool found_user = false;
-            for (user_idx = 0; user_idx < net->users.size(); user_idx++)
-                if (net->users.at(user_idx).cell == ci && net->users.at(user_idx).port == pin_name) {
-                    found_user = true;
-                    break;
-                }
-            NPNR_ASSERT(found_user);
 
             // TODO: substantial performance improvements are probably possible, although of questionable benefit given
             // the low number of globals in a typical device...
@@ -213,7 +205,7 @@ void Arch::place_globals()
                 if (!isBelLocationValid(bel))
                     goto fail;
                 // Check distance
-                distance = route_global_arc(ctx, net, user_idx, 0, pin.max_hops, true);
+                distance = route_global_arc(ctx, net, port.user_idx, 0, pin.max_hops, true);
                 if (distance != -1 && distance < shortest_distance) {
                     best_bel = bel;
                     shortest_distance = distance;
@@ -262,16 +254,16 @@ void Arch::route_globals()
             int total_sinks = 0;
             int global_sinks = 0;
 
-            for (size_t i = 0; i < net->users.size(); i++) {
-                auto &usr = net->users.at(i);
-                for (size_t j = 0; j < ctx->getNetinfoSinkWireCount(net, usr); j++) {
-                    int result = route_global_arc(ctx, net, i, j, pin.max_hops, false);
+            for (auto usr : net->users.enumerate()) {
+                for (size_t j = 0; j < ctx->getNetinfoSinkWireCount(net, usr.value); j++) {
+                    int result = route_global_arc(ctx, net, usr.index, j, pin.max_hops, false);
                     ++total_sinks;
                     if (result != -1)
                         ++global_sinks;
                     if ((result == -1) && pin.force_routing)
                         log_error("Failed to route arc %d.%d (%s.%s) of net %s using dedicated global routing!\n",
-                                  int(i), int(j), ctx->nameOf(usr.cell), ctx->nameOf(usr.port), ctx->nameOf(net));
+                                  usr.index.idx(), int(j), ctx->nameOf(usr.value.cell), ctx->nameOf(usr.value.port),
+                                  ctx->nameOf(net));
                 }
             }