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>

4 files changed, 8 insertions, 7 deletions

diff --git a/generic/cells.cc b/generic/cells.cc
index 76d6474f..e4a24767 100644
--- a/generic/cells.cc
+++ b/generic/cells.cc
@@ -121,7 +121,7 @@ void nxio_to_iob(Context *ctx, CellInfo *nxio, CellInfo *iob, pool<IdString> &to
         tbuf->movePortTo(ctx->id("A"), iob, ctx->id("I"));
         tbuf->movePortTo(ctx->id("E"), iob, ctx->id("EN"));
 
-        if (donet->users.size() > 1) {
+        if (donet->users.entries() > 1) {
             for (auto user : donet->users)
                 log_info("     remaining tristate user: %s.%s\n", user.cell->name.c_str(ctx), user.port.c_str(ctx));
             log_error("unsupported tristate IO pattern for IO buffer '%s', "
diff --git a/generic/pack.cc b/generic/pack.cc
index cb3f5897..428d6642 100644
--- a/generic/pack.cc
+++ b/generic/pack.cc
@@ -124,9 +124,10 @@ static void set_net_constant(const Context *ctx, NetInfo *orig, NetInfo *constne
                 log_info("%s user %s\n", orig->name.c_str(ctx), uc->name.c_str(ctx));
             if ((is_lut(ctx, uc) || is_lc(ctx, uc)) && (user.port.str(ctx).at(0) == 'I') && !constval) {
                 uc->ports[user.port].net = nullptr;
+                uc->ports[user.port].user_idx = {};
             } else {
                 uc->ports[user.port].net = constnet;
-                constnet->users.push_back(user);
+                uc->ports[user.port].user_idx = constnet->users.add(user);
             }
         }
     }
@@ -224,8 +225,8 @@ static void pack_io(Context *ctx)
                          ci->type.c_str(ctx), ci->name.c_str(ctx));
                 NetInfo *net = iob->ports.at(ctx->id("PAD")).net;
                 if (((ci->type == ctx->id("$nextpnr_ibuf") || ci->type == ctx->id("$nextpnr_iobuf")) &&
-                     net->users.size() > 1) ||
-                    (ci->type == ctx->id("$nextpnr_obuf") && (net->users.size() > 2 || net->driver.cell != nullptr)))
+                     net->users.entries() > 1) ||
+                    (ci->type == ctx->id("$nextpnr_obuf") && (net->users.entries() > 2 || net->driver.cell != nullptr)))
                     log_error("PAD of %s '%s' connected to more than a single top level IO.\n", iob->type.c_str(ctx),
                               iob->name.c_str(ctx));
 
diff --git a/generic/viaduct/okami/okami.cc b/generic/viaduct/okami/okami.cc
index bcb34e84..864bdb45 100644
--- a/generic/viaduct/okami/okami.cc
+++ b/generic/viaduct/okami/okami.cc
@@ -511,7 +511,7 @@ struct OkamiImpl : ViaductAPI
         const auto &ff_data = fast_cell_info.at(ff->flat_index);
         // In our example arch; the FF D can either be driven from LUT F or LUT I3
         // so either; FF D must equal LUT F or LUT I3 must be unused
-        if (ff_data.ff_d == lut_data.lut_f && lut_data.lut_f->users.size() == 1)
+        if (ff_data.ff_d == lut_data.lut_f && lut_data.lut_f->users.entries() == 1)
             return true;
         // Can't route FF and LUT output separately
         return false;
diff --git a/generic/viaduct_helpers.cc b/generic/viaduct_helpers.cc
index 10c3b802..a92d0de1 100644
--- a/generic/viaduct_helpers.cc
+++ b/generic/viaduct_helpers.cc
@@ -96,7 +96,7 @@ int ViaductHelpers::constrain_cell_pairs(const pool<CellTypePort> &src_ports, co
                 continue;
             if (!src_ports.count(CellTypePort(ci.type, port.first)))
                 continue;
-            if (!allow_fanout && port.second.net->users.size() > 1)
+            if (!allow_fanout && port.second.net->users.entries() > 1)
                 continue;
             for (auto &usr : port.second.net->users) {
                 if (!sink_ports.count(CellTypePort(usr)))
@@ -151,7 +151,7 @@ void ViaductHelpers::replace_constants(CellTypePort vcc_driver, CellTypePort gnd
         NetInfo *replace = (ni.driver.cell->type == ctx->id("VCC")) ? vcc_net : gnd_net;
         for (auto &usr : ni.users) {
             usr.cell->ports.at(usr.port).net = replace;
-            replace->users.push_back(usr);
+            usr.cell->ports.at(usr.port).user_idx = replace->users.add(usr);
         }
         trim_cells.push_back(ni.driver.cell->name);
         trim_nets.push_back(ni.name);