macho: use array hashmaps for quick lookups

as containers for unresolved and tentative definitions when resolving
symbols.

1 files changed, 24 insertions, 45 deletions

diff --git a/src/link/MachO.zig b/src/link/MachO.zig
index 26a581a22a..d78f0dc942 100644
--- a/src/link/MachO.zig
+++ b/src/link/MachO.zig
@@ -2094,8 +2094,8 @@ fn writeStubHelperCommon(self: *MachO) !void {
 fn resolveSymbolsInObject(
     self: *MachO,
     object_id: u16,
-    tentatives: *std.ArrayList(u32),
-    unresolved: *std.ArrayList(u32),
+    tentatives: *std.AutoArrayHashMap(u32, void),
+    unresolved: *std.AutoArrayHashMap(u32, void),
 ) !void {
     const object = &self.objects.items[object_id];
 
@@ -2176,14 +2176,9 @@ fn resolveSymbolsInObject(
                         return error.MultipleSymbolDefinitions;
                     }
                     if (symbolIsWeakDef(sym) or symbolIsPext(sym)) continue; // Current symbol is weak, so skip it.
+
                     if (symbolIsTentative(global.*)) {
-                        var i: usize = 0;
-                        while (i < tentatives.items.len) : (i += 1) {
-                            if (tentatives.items[i] == resolv.where_index) {
-                                _ = tentatives.swapRemove(i);
-                                break;
-                            }
-                        }
+                        _ = tentatives.fetchSwapRemove(resolv.where_index);
                     }
 
                     // Otherwise, update the resolver and the global symbol.
@@ -2202,14 +2197,7 @@ fn resolveSymbolsInObject(
                         .n_desc = 0,
                         .n_value = 0,
                     };
-
-                    var i: usize = 0;
-                    while (i < unresolved.items.len) : (i += 1) {
-                        if (unresolved.items[i] == resolv.where_index) {
-                            _ = unresolved.swapRemove(i);
-                            break;
-                        }
-                    }
+                    _ = unresolved.fetchSwapRemove(resolv.where_index);
                 },
             }
 
@@ -2243,7 +2231,7 @@ fn resolveSymbolsInObject(
                     .where_index = global_sym_index,
                     .file = object_id,
                 });
-                try tentatives.append(global_sym_index);
+                _ = try tentatives.getOrPut(global_sym_index);
                 continue;
             };
 
@@ -2267,7 +2255,7 @@ fn resolveSymbolsInObject(
                         .n_desc = sym.n_desc,
                         .n_value = sym.n_value,
                     });
-                    try tentatives.append(global_sym_index);
+                    _ = try tentatives.getOrPut(global_sym_index);
                     resolv.* = .{
                         .where = .global,
                         .where_index = global_sym_index,
@@ -2280,13 +2268,7 @@ fn resolveSymbolsInObject(
                         .n_desc = 0,
                         .n_value = 0,
                     };
-                    var i: usize = 0;
-                    while (i < unresolved.items.len) : (i += 1) {
-                        if (unresolved.items[i] == resolv.where_index) {
-                            _ = unresolved.swapRemove(i);
-                            break;
-                        }
-                    }
+                    _ = unresolved.fetchSwapRemove(resolv.where_index);
                 },
             }
         } else {
@@ -2306,16 +2288,16 @@ fn resolveSymbolsInObject(
                 .where_index = undef_sym_index,
                 .file = object_id,
             });
-            try unresolved.append(undef_sym_index);
+            _ = try unresolved.getOrPut(undef_sym_index);
         }
     }
 }
 
 fn resolveSymbols(self: *MachO) !void {
-    var tentatives = std.ArrayList(u32).init(self.base.allocator);
+    var tentatives = std.AutoArrayHashMap(u32, void).init(self.base.allocator);
     defer tentatives.deinit();
 
-    var unresolved = std.ArrayList(u32).init(self.base.allocator);
+    var unresolved = std.AutoArrayHashMap(u32, void).init(self.base.allocator);
     defer unresolved.deinit();
 
     // First pass, resolve symbols in provided objects.
@@ -2325,8 +2307,8 @@ fn resolveSymbols(self: *MachO) !void {
 
     // Second pass, resolve symbols in static libraries.
     var next_sym: usize = 0;
-    loop: while (next_sym < unresolved.items.len) {
-        const sym = self.undefs.items[unresolved.items[next_sym]];
+    loop: while (next_sym < unresolved.count()) {
+        const sym = self.undefs.items[unresolved.keys()[next_sym]];
         const sym_name = self.getString(sym.n_strx);
 
         for (self.archives.items) |archive| {
@@ -2350,7 +2332,10 @@ fn resolveSymbols(self: *MachO) !void {
 
     // Convert any tentative definition into a regular symbol and allocate
     // text blocks for each tentative defintion.
-    while (tentatives.popOrNull()) |index| {
+    var tentatives_count: usize = 0;
+    const ntentatives = tentatives.count();
+    while (tentatives_count < ntentatives) : (tentatives_count += 1) {
+        const index = tentatives.pop().key;
         const sym = &self.globals.items[index];
         const match: MatchingSection = blk: {
             if (self.common_section_index == null) {
@@ -2430,12 +2415,12 @@ fn resolveSymbols(self: *MachO) !void {
             .where = .undef,
             .where_index = undef_sym_index,
         });
-        try unresolved.append(undef_sym_index);
+        _ = try unresolved.getOrPut(undef_sym_index);
     }
 
     next_sym = 0;
-    loop: while (next_sym < unresolved.items.len) {
-        const sym = self.undefs.items[unresolved.items[next_sym]];
+    loop: while (next_sym < unresolved.count()) {
+        const sym = self.undefs.items[unresolved.keys()[next_sym]];
         const sym_name = self.getString(sym.n_strx);
 
         for (self.dylibs.items) |dylib, id| {
@@ -2452,7 +2437,7 @@ fn resolveSymbols(self: *MachO) !void {
             undef.n_type |= macho.N_EXT;
             undef.n_desc = @intCast(u16, ordinal + 1) * macho.N_SYMBOL_RESOLVER;
 
-            _ = unresolved.swapRemove(next_sym);
+            _ = unresolved.fetchSwapRemove(resolv.where_index);
 
             continue :loop;
         }
@@ -2486,13 +2471,7 @@ fn resolveSymbols(self: *MachO) !void {
         nlist.n_desc = macho.N_WEAK_DEF;
         try self.globals.append(self.base.allocator, nlist);
 
-        var i: usize = 0;
-        while (i < unresolved.items.len) : (i += 1) {
-            if (unresolved.items[i] == resolv.where_index) {
-                _ = unresolved.swapRemove(i);
-                break;
-            }
-        }
+        _ = unresolved.fetchSwapRemove(resolv.where_index);
 
         undef.* = .{
             .n_strx = 0,
@@ -2526,7 +2505,7 @@ fn resolveSymbols(self: *MachO) !void {
         }
     }
 
-    for (unresolved.items) |index| {
+    for (unresolved.keys()) |index| {
         const sym = self.undefs.items[index];
         const sym_name = self.getString(sym.n_strx);
         const resolv = self.symbol_resolver.get(sym.n_strx) orelse unreachable;
@@ -2535,7 +2514,7 @@ fn resolveSymbols(self: *MachO) !void {
         log.err("  first referenced in '{s}'", .{self.objects.items[resolv.file].name});
     }
 
-    if (unresolved.items.len > 0)
+    if (unresolved.count() > 0)
         return error.UndefinedSymbolReference;
 }