From cbb9b5d9f04509260b8cea935a0441f63f33bc32 Mon Sep 17 00:00:00 2001
From: Andrew Kelley <andrew@ziglang.org>
Date: Fri, 6 Oct 2023 23:58:53 -0700
Subject: std: add unstable sorting to array hash maps

closes #17426
---
 lib/std/array_hash_map.zig | 33 ++++++++++++++++++++++++++++++---
 1 file changed, 30 insertions(+), 3 deletions(-)

(limited to 'lib/std/array_hash_map.zig')

diff --git a/lib/std/array_hash_map.zig b/lib/std/array_hash_map.zig
index 1bb85a255d..75a86f63f6 100644
--- a/lib/std/array_hash_map.zig
+++ b/lib/std/array_hash_map.zig
@@ -1229,14 +1229,41 @@ pub fn ArrayHashMapUnmanaged(
         /// Sorts the entries and then rebuilds the index.
         /// `sort_ctx` must have this method:
         /// `fn lessThan(ctx: @TypeOf(ctx), a_index: usize, b_index: usize) bool`
+        /// Uses a stable sorting algorithm.
         pub inline fn sort(self: *Self, sort_ctx: anytype) void {
             if (@sizeOf(ByIndexContext) != 0)
                 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call sortContext instead.");
-            return self.sortContext(sort_ctx, undefined);
+            return sortContextInternal(self, .stable, sort_ctx, undefined);
         }
 
-        pub fn sortContext(self: *Self, sort_ctx: anytype, ctx: Context) void {
-            self.entries.sort(sort_ctx);
+        /// Sorts the entries and then rebuilds the index.
+        /// `sort_ctx` must have this method:
+        /// `fn lessThan(ctx: @TypeOf(ctx), a_index: usize, b_index: usize) bool`
+        /// Uses an unstable sorting algorithm.
+        pub inline fn sortUnstable(self: *Self, sort_ctx: anytype) void {
+            if (@sizeOf(ByIndexContext) != 0)
+                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call sortUnstableContext instead.");
+            return self.sortContextInternal(.unstable, sort_ctx, undefined);
+        }
+
+        pub inline fn sortContext(self: *Self, sort_ctx: anytype, ctx: Context) void {
+            return sortContextInternal(self, .stable, sort_ctx, ctx);
+        }
+
+        pub inline fn sortUnstableContext(self: *Self, sort_ctx: anytype, ctx: Context) void {
+            return sortContextInternal(self, .unstable, sort_ctx, ctx);
+        }
+
+        fn sortContextInternal(
+            self: *Self,
+            comptime mode: std.sort.Mode,
+            sort_ctx: anytype,
+            ctx: Context,
+        ) void {
+            switch (mode) {
+                .stable => self.entries.sort(sort_ctx),
+                .unstable => self.entries.sortUnstable(sort_ctx),
+            }
             const header = self.index_header orelse return;
             header.reset();
             self.insertAllEntriesIntoNewHeader(if (store_hash) {} else ctx, header);
-- 
cgit v1.2.3