1const std = @import("std.zig");
2const debug = std.debug;
3const assert = debug.assert;
4const testing = std.testing;
5const math = std.math;
6const mem = std.mem;
7const autoHash = std.hash.autoHash;
8const Wyhash = std.hash.Wyhash;
9const Allocator = mem.Allocator;
10const hash_map = @This();
11
12/// An `ArrayHashMap` with default hash and equal functions.
13///
14/// See `AutoContext` for a description of the hash and equal implementations.
15pub fn Auto(comptime K: type, comptime V: type) type {
16 return Custom(K, V, AutoContext(K), !autoEqlIsCheap(K));
17}
18
19/// An `ArrayHashMap` with strings as keys.
20pub fn String(comptime V: type) type {
21 return Custom([]const u8, V, StringContext, true);
22}
23
24pub const StringContext = struct {
25 pub fn hash(self: @This(), s: []const u8) u32 {
26 _ = self;
27 return hashString(s);
28 }
29 pub fn eql(self: @This(), a: []const u8, b: []const u8, b_index: usize) bool {
30 _ = self;
31 _ = b_index;
32 return eqlString(a, b);
33 }
34};
35
36pub fn eqlString(a: []const u8, b: []const u8) bool {
37 return mem.eql(u8, a, b);
38}
39
40pub fn hashString(s: []const u8) u32 {
41 return @truncate(std.hash.Wyhash.hash(0, s));
42}
43
44/// Deprecated; use `Custom`.
45pub const ArrayHashMap = Custom;
46
47/// A hash table of keys and values, each stored sequentially.
48///
49/// Insertion order is preserved. In general, this data structure supports the same
50/// operations as `std.ArrayList`.
51///
52/// Deletion operations:
53/// * `swapRemove` - O(1)
54/// * `orderedRemove` - O(N)
55///
56/// Modifying the hash map while iterating is allowed, however, one must understand
57/// the (well defined) behavior when mixing insertions and deletions with iteration.
58///
59/// This type does not store an `Allocator` field - the `Allocator` must be passed in
60/// with each function call that requires it.
61///
62/// Can be initialized directly using the default field values.
63///
64/// This type is designed to have low overhead for small numbers of entries. When
65/// `store_hash` is `false` and the number of entries in the map is less than 9,
66/// the overhead cost of using `ArrayHashMap` rather than `std.ArrayList` is
67/// only a single pointer-sized integer.
68///
69/// Default initialization of this struct is deprecated; use `.empty` instead.
70pub fn Custom(
71 comptime K: type,
72 comptime V: type,
73 /// A namespace that provides these two functions:
74 /// * `pub fn hash(self, K) u32`
75 /// * `pub fn eql(self, K, K, usize) bool`
76 ///
77 /// The final `usize` in the `eql` function represents the index of the key
78 /// that's already inside the map.
79 comptime Context: type,
80 /// When `false`, this data structure is biased towards cheap `eql`
81 /// functions and avoids storing each key's hash in the table. Setting
82 /// `store_hash` to `true` incurs more memory cost but limits `eql` to
83 /// being called only once per insertion/deletion (provided there are no
84 /// hash collisions).
85 comptime store_hash: bool,
86) type {
87 return struct {
88 /// It is permitted to access this field directly.
89 /// After any modification to the keys, consider calling `reIndex`.
90 entries: DataList = .{},
91
92 /// When entries length is less than `linear_scan_max`, this remains `null`.
93 /// Once entries length grows big enough, this field is allocated. There is
94 /// an IndexHeader followed by an array of Index(I) structs, where I is defined
95 /// by how many total indexes there are.
96 index_header: ?*IndexHeader = null,
97
98 /// Used to detect memory safety violations.
99 pointer_stability: std.debug.SafetyLock = .{},
100
101 /// A map containing no keys or values.
102 pub const empty: Self = .{
103 .entries = .{},
104 .index_header = null,
105 };
106
107 /// Modifying the key is allowed only if it does not change the hash.
108 /// Modifying the value is allowed.
109 /// Entry pointers become invalid whenever this ArrayHashMap is modified,
110 /// unless `ensureTotalCapacity`/`ensureUnusedCapacity` was previously used.
111 pub const Entry = struct {
112 key_ptr: *K,
113 value_ptr: *V,
114 };
115
116 /// A KV pair which has been copied out of the backing store
117 pub const KV = struct {
118 key: K,
119 value: V,
120 };
121
122 /// The Data type used for the MultiArrayList backing this map
123 pub const Data = struct {
124 hash: Hash,
125 key: K,
126 value: V,
127 };
128
129 /// The MultiArrayList type backing this map
130 pub const DataList = std.MultiArrayList(Data);
131
132 /// The stored hash type, either u32 or void.
133 pub const Hash = if (store_hash) u32 else void;
134
135 /// getOrPut variants return this structure, with pointers
136 /// to the backing store and a flag to indicate whether an
137 /// existing entry was found.
138 /// Modifying the key is allowed only if it does not change the hash.
139 /// Modifying the value is allowed.
140 /// Entry pointers become invalid whenever this ArrayHashMap is modified,
141 /// unless `ensureTotalCapacity`/`ensureUnusedCapacity` was previously used.
142 pub const GetOrPutResult = struct {
143 key_ptr: *K,
144 value_ptr: *V,
145 found_existing: bool,
146 index: usize,
147 };
148
149 /// Some functions require a context only if hashes are not stored.
150 /// To keep the api simple, this type is only used internally.
151 const ByIndexContext = if (store_hash) void else Context;
152
153 const Self = @This();
154
155 const linear_scan_max = @as(comptime_int, @max(1, @as(comptime_int, @min(
156 std.atomic.cache_line / @as(comptime_int, @max(1, @sizeOf(Hash))),
157 std.atomic.cache_line / @as(comptime_int, @max(1, @sizeOf(K))),
158 ))));
159
160 const RemovalType = enum {
161 swap,
162 ordered,
163 };
164
165 const Oom = Allocator.Error;
166
167 pub fn init(gpa: Allocator, key_list: []const K, value_list: []const V) Oom!Self {
168 var self: Self = .{};
169 errdefer self.deinit(gpa);
170 try self.reinit(gpa, key_list, value_list);
171 return self;
172 }
173
174 /// An empty `value_list` may be passed, in which case the values array becomes `undefined`.
175 pub fn reinit(self: *Self, gpa: Allocator, key_list: []const K, value_list: []const V) Oom!void {
176 try self.entries.resize(gpa, key_list.len);
177 @memcpy(self.keys(), key_list);
178 if (value_list.len == 0) {
179 @memset(self.values(), undefined);
180 } else {
181 assert(key_list.len == value_list.len);
182 @memcpy(self.values(), value_list);
183 }
184 try self.reIndex(gpa);
185 }
186
187 /// Frees the backing allocation and leaves the map in an undefined state.
188 /// Note that this does not free keys or values. You must take care of that
189 /// before calling this function, if it is needed.
190 pub fn deinit(self: *Self, gpa: Allocator) void {
191 self.pointer_stability.assertUnlocked();
192 self.entries.deinit(gpa);
193 if (self.index_header) |header| {
194 header.free(gpa);
195 }
196 self.* = undefined;
197 }
198
199 /// Puts the hash map into a state where any method call that would
200 /// cause an existing key or value pointer to become invalidated will
201 /// instead trigger an assertion.
202 ///
203 /// An additional call to `lockPointers` in such state also triggers an
204 /// assertion.
205 ///
206 /// `unlockPointers` returns the hash map to the previous state.
207 pub fn lockPointers(self: *Self) void {
208 self.pointer_stability.lock();
209 }
210
211 /// Undoes a call to `lockPointers`.
212 pub fn unlockPointers(self: *Self) void {
213 self.pointer_stability.unlock();
214 }
215
216 /// Clears the map but retains the backing allocation for future use.
217 pub fn clearRetainingCapacity(self: *Self) void {
218 self.pointer_stability.lock();
219 defer self.pointer_stability.unlock();
220
221 self.entries.len = 0;
222 if (self.index_header) |header| {
223 switch (header.capacityIndexType()) {
224 .u8 => @memset(header.indexes(u8), Index(u8).empty),
225 .u16 => @memset(header.indexes(u16), Index(u16).empty),
226 .u32 => @memset(header.indexes(u32), Index(u32).empty),
227 }
228 }
229 }
230
231 /// Clears the map and releases the backing allocation
232 pub fn clearAndFree(self: *Self, gpa: Allocator) void {
233 self.pointer_stability.lock();
234 defer self.pointer_stability.unlock();
235
236 self.entries.shrinkAndFree(gpa, 0);
237 if (self.index_header) |header| {
238 header.free(gpa);
239 self.index_header = null;
240 }
241 }
242
243 /// Returns the number of KV pairs stored in this map.
244 pub fn count(self: Self) usize {
245 return self.entries.len;
246 }
247
248 /// Returns the backing array of keys in this map. Modifying the map may
249 /// invalidate this array. Modifying this array in a way that changes
250 /// key hashes or key equality puts the map into an unusable state until
251 /// `reIndex` is called.
252 pub fn keys(self: Self) []K {
253 return self.entries.items(.key);
254 }
255 /// Returns the backing array of values in this map. Modifying the map
256 /// may invalidate this array. It is permitted to modify the values in
257 /// this array.
258 pub fn values(self: Self) []V {
259 return self.entries.items(.value);
260 }
261
262 /// Returns an iterator over the pairs in this map.
263 /// Modifying the map may invalidate this iterator.
264 pub fn iterator(self: Self) Iterator {
265 const slice = self.entries.slice();
266 return .{
267 .keys = slice.items(.key).ptr,
268 .values = slice.items(.value).ptr,
269 .len = @as(u32, @intCast(slice.len)),
270 };
271 }
272 pub const Iterator = struct {
273 keys: [*]K,
274 values: [*]V,
275 len: u32,
276 index: u32 = 0,
277
278 pub fn next(it: *Iterator) ?Entry {
279 if (it.index >= it.len) return null;
280 const result = Entry{
281 .key_ptr = &it.keys[it.index],
282 .value_ptr = &it.values[it.index],
283 };
284 it.index += 1;
285 return result;
286 }
287
288 /// Reset the iterator to the initial index
289 pub fn reset(it: *Iterator) void {
290 it.index = 0;
291 }
292 };
293
294 /// If key exists this function cannot fail.
295 /// If there is an existing item with `key`, then the result
296 /// `Entry` pointer points to it, and found_existing is true.
297 /// Otherwise, puts a new item with undefined value, and
298 /// the `Entry` pointer points to it. Caller should then initialize
299 /// the value (but not the key).
300 pub fn getOrPut(self: *Self, gpa: Allocator, key: K) Oom!GetOrPutResult {
301 if (@sizeOf(Context) != 0)
302 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getOrPutContext instead.");
303 return self.getOrPutContext(gpa, key, undefined);
304 }
305 pub fn getOrPutContext(self: *Self, gpa: Allocator, key: K, ctx: Context) Oom!GetOrPutResult {
306 const gop = try self.getOrPutContextAdapted(gpa, key, ctx, ctx);
307 if (!gop.found_existing) {
308 gop.key_ptr.* = key;
309 }
310 return gop;
311 }
312 pub fn getOrPutAdapted(self: *Self, gpa: Allocator, key: anytype, key_ctx: anytype) Oom!GetOrPutResult {
313 if (@sizeOf(Context) != 0)
314 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getOrPutContextAdapted instead.");
315 return self.getOrPutContextAdapted(gpa, key, key_ctx, undefined);
316 }
317 pub fn getOrPutContextAdapted(self: *Self, gpa: Allocator, key: anytype, key_ctx: anytype, ctx: Context) Oom!GetOrPutResult {
318 self.ensureTotalCapacityContext(gpa, self.entries.len + 1, ctx) catch |err| {
319 // "If key exists this function cannot fail."
320 const index = self.getIndexAdapted(key, key_ctx) orelse return err;
321 const slice = self.entries.slice();
322 return GetOrPutResult{
323 .key_ptr = &slice.items(.key)[index],
324 .value_ptr = &slice.items(.value)[index],
325 .found_existing = true,
326 .index = index,
327 };
328 };
329 return self.getOrPutAssumeCapacityAdapted(key, key_ctx);
330 }
331
332 /// If there is an existing item with `key`, then the result
333 /// `Entry` pointer points to it, and found_existing is true.
334 /// Otherwise, puts a new item with undefined value, and
335 /// the `Entry` pointer points to it. Caller should then initialize
336 /// the value (but not the key).
337 /// If a new entry needs to be stored, this function asserts there
338 /// is enough capacity to store it.
339 pub fn getOrPutAssumeCapacity(self: *Self, key: K) GetOrPutResult {
340 if (@sizeOf(Context) != 0)
341 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getOrPutAssumeCapacityContext instead.");
342 return self.getOrPutAssumeCapacityContext(key, undefined);
343 }
344 pub fn getOrPutAssumeCapacityContext(self: *Self, key: K, ctx: Context) GetOrPutResult {
345 const gop = self.getOrPutAssumeCapacityAdapted(key, ctx);
346 if (!gop.found_existing) {
347 gop.key_ptr.* = key;
348 }
349 return gop;
350 }
351 /// If there is an existing item with `key`, then the result
352 /// `Entry` pointers point to it, and found_existing is true.
353 /// Otherwise, puts a new item with undefined key and value, and
354 /// the `Entry` pointers point to it. Caller must then initialize
355 /// both the key and the value.
356 /// If a new entry needs to be stored, this function asserts there
357 /// is enough capacity to store it.
358 pub fn getOrPutAssumeCapacityAdapted(self: *Self, key: anytype, ctx: anytype) GetOrPutResult {
359 const header = self.index_header orelse {
360 // Linear scan.
361 const h = if (store_hash) checkedHash(ctx, key) else {};
362 const slice = self.entries.slice();
363 const hashes_array = slice.items(.hash);
364 const keys_array = slice.items(.key);
365 for (keys_array, 0..) |*item_key, i| {
366 if (hashes_array[i] == h and checkedEql(ctx, key, item_key.*, i)) {
367 return GetOrPutResult{
368 .key_ptr = item_key,
369 .value_ptr = &slice.items(.value)[i],
370 .found_existing = true,
371 .index = i,
372 };
373 }
374 }
375
376 const index = self.entries.addOneAssumeCapacity();
377 // The slice length changed, so we directly index the pointer.
378 if (store_hash) hashes_array.ptr[index] = h;
379
380 return GetOrPutResult{
381 .key_ptr = &keys_array.ptr[index],
382 .value_ptr = &slice.items(.value).ptr[index],
383 .found_existing = false,
384 .index = index,
385 };
386 };
387
388 switch (header.capacityIndexType()) {
389 .u8 => return self.getOrPutInternal(key, ctx, header, u8),
390 .u16 => return self.getOrPutInternal(key, ctx, header, u16),
391 .u32 => return self.getOrPutInternal(key, ctx, header, u32),
392 }
393 }
394
395 pub fn getOrPutValue(self: *Self, gpa: Allocator, key: K, value: V) Oom!GetOrPutResult {
396 if (@sizeOf(Context) != 0)
397 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getOrPutValueContext instead.");
398 return self.getOrPutValueContext(gpa, key, value, undefined);
399 }
400 pub fn getOrPutValueContext(self: *Self, gpa: Allocator, key: K, value: V, ctx: Context) Oom!GetOrPutResult {
401 const res = try self.getOrPutContextAdapted(gpa, key, ctx, ctx);
402 if (!res.found_existing) {
403 res.key_ptr.* = key;
404 res.value_ptr.* = value;
405 }
406 return res;
407 }
408
409 /// Increases capacity, guaranteeing that insertions up until the
410 /// `expected_count` will not cause an allocation, and therefore cannot fail.
411 pub fn ensureTotalCapacity(self: *Self, gpa: Allocator, new_capacity: usize) Oom!void {
412 if (@sizeOf(ByIndexContext) != 0)
413 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call ensureTotalCapacityContext instead.");
414 return self.ensureTotalCapacityContext(gpa, new_capacity, undefined);
415 }
416 pub fn ensureTotalCapacityContext(self: *Self, gpa: Allocator, new_capacity: usize, ctx: Context) Oom!void {
417 self.pointer_stability.lock();
418 defer self.pointer_stability.unlock();
419
420 try self.entries.ensureTotalCapacity(gpa, new_capacity);
421 if (new_capacity <= linear_scan_max) return;
422 if (self.index_header) |header| if (new_capacity <= header.capacity()) return;
423
424 const new_bit_index = try IndexHeader.findBitIndex(new_capacity);
425 const new_header = try IndexHeader.alloc(gpa, new_bit_index);
426
427 if (self.index_header) |old_header| old_header.free(gpa);
428 self.insertAllEntriesIntoNewHeader(if (store_hash) {} else ctx, new_header);
429 self.index_header = new_header;
430 }
431
432 /// Increases capacity, guaranteeing that insertions up until
433 /// `additional_count` **more** items will not cause an allocation, and
434 /// therefore cannot fail.
435 pub fn ensureUnusedCapacity(
436 self: *Self,
437 gpa: Allocator,
438 additional_capacity: usize,
439 ) Oom!void {
440 if (@sizeOf(Context) != 0)
441 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call ensureTotalCapacityContext instead.");
442 return self.ensureUnusedCapacityContext(gpa, additional_capacity, undefined);
443 }
444 pub fn ensureUnusedCapacityContext(
445 self: *Self,
446 gpa: Allocator,
447 additional_capacity: usize,
448 ctx: Context,
449 ) Oom!void {
450 return self.ensureTotalCapacityContext(gpa, self.count() + additional_capacity, ctx);
451 }
452
453 /// Returns the number of total elements which may be present before it is
454 /// no longer guaranteed that no allocations will be performed.
455 pub fn capacity(self: Self) usize {
456 const entry_cap = self.entries.capacity;
457 const header = self.index_header orelse return @min(linear_scan_max, entry_cap);
458 const indexes_cap = header.capacity();
459 return @min(entry_cap, indexes_cap);
460 }
461
462 /// Clobbers any existing data. To detect if a put would clobber
463 /// existing data, see `getOrPut`.
464 pub fn put(self: *Self, gpa: Allocator, key: K, value: V) Oom!void {
465 if (@sizeOf(Context) != 0)
466 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call putContext instead.");
467 return self.putContext(gpa, key, value, undefined);
468 }
469 pub fn putContext(self: *Self, gpa: Allocator, key: K, value: V, ctx: Context) Oom!void {
470 const result = try self.getOrPutContext(gpa, key, ctx);
471 result.value_ptr.* = value;
472 }
473
474 /// Inserts a key-value pair into the hash map, asserting that no previous
475 /// entry with the same key is already present
476 pub fn putNoClobber(self: *Self, gpa: Allocator, key: K, value: V) Oom!void {
477 if (@sizeOf(Context) != 0)
478 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call putNoClobberContext instead.");
479 return self.putNoClobberContext(gpa, key, value, undefined);
480 }
481 pub fn putNoClobberContext(self: *Self, gpa: Allocator, key: K, value: V, ctx: Context) Oom!void {
482 const result = try self.getOrPutContext(gpa, key, ctx);
483 assert(!result.found_existing);
484 result.value_ptr.* = value;
485 }
486
487 /// Asserts there is enough capacity to store the new key-value pair.
488 /// Clobbers any existing data. To detect if a put would clobber
489 /// existing data, see `getOrPutAssumeCapacity`.
490 pub fn putAssumeCapacity(self: *Self, key: K, value: V) void {
491 if (@sizeOf(Context) != 0)
492 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call putAssumeCapacityContext instead.");
493 return self.putAssumeCapacityContext(key, value, undefined);
494 }
495 pub fn putAssumeCapacityContext(self: *Self, key: K, value: V, ctx: Context) void {
496 const result = self.getOrPutAssumeCapacityContext(key, ctx);
497 result.value_ptr.* = value;
498 }
499
500 /// Asserts there is enough capacity to store the new key-value pair.
501 /// Asserts that it does not clobber any existing data.
502 /// To detect if a put would clobber existing data, see `getOrPutAssumeCapacity`.
503 pub fn putAssumeCapacityNoClobber(self: *Self, key: K, value: V) void {
504 if (@sizeOf(Context) != 0)
505 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call putAssumeCapacityNoClobberContext instead.");
506 return self.putAssumeCapacityNoClobberContext(key, value, undefined);
507 }
508 pub fn putAssumeCapacityNoClobberContext(self: *Self, key: K, value: V, ctx: Context) void {
509 const result = self.getOrPutAssumeCapacityContext(key, ctx);
510 assert(!result.found_existing);
511 result.value_ptr.* = value;
512 }
513
514 /// Inserts a new `Entry` into the hash map, returning the previous one, if any.
515 pub fn fetchPut(self: *Self, gpa: Allocator, key: K, value: V) Oom!?KV {
516 if (@sizeOf(Context) != 0)
517 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call fetchPutContext instead.");
518 return self.fetchPutContext(gpa, key, value, undefined);
519 }
520 pub fn fetchPutContext(self: *Self, gpa: Allocator, key: K, value: V, ctx: Context) Oom!?KV {
521 const gop = try self.getOrPutContext(gpa, key, ctx);
522 var result: ?KV = null;
523 if (gop.found_existing) {
524 result = KV{
525 .key = gop.key_ptr.*,
526 .value = gop.value_ptr.*,
527 };
528 }
529 gop.value_ptr.* = value;
530 return result;
531 }
532
533 /// Inserts a new `Entry` into the hash map, returning the previous one, if any.
534 /// If insertion happens, asserts there is enough capacity without allocating.
535 pub fn fetchPutAssumeCapacity(self: *Self, key: K, value: V) ?KV {
536 if (@sizeOf(Context) != 0)
537 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call fetchPutAssumeCapacityContext instead.");
538 return self.fetchPutAssumeCapacityContext(key, value, undefined);
539 }
540 pub fn fetchPutAssumeCapacityContext(self: *Self, key: K, value: V, ctx: Context) ?KV {
541 const gop = self.getOrPutAssumeCapacityContext(key, ctx);
542 var result: ?KV = null;
543 if (gop.found_existing) {
544 result = KV{
545 .key = gop.key_ptr.*,
546 .value = gop.value_ptr.*,
547 };
548 }
549 gop.value_ptr.* = value;
550 return result;
551 }
552
553 /// Finds pointers to the key and value storage associated with a key.
554 pub fn getEntry(self: Self, key: K) ?Entry {
555 if (@sizeOf(Context) != 0)
556 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getEntryContext instead.");
557 return self.getEntryContext(key, undefined);
558 }
559 pub fn getEntryContext(self: Self, key: K, ctx: Context) ?Entry {
560 return self.getEntryAdapted(key, ctx);
561 }
562 pub fn getEntryAdapted(self: Self, key: anytype, ctx: anytype) ?Entry {
563 const index = self.getIndexAdapted(key, ctx) orelse return null;
564 const slice = self.entries.slice();
565 return Entry{
566 .key_ptr = &slice.items(.key)[index],
567 .value_ptr = &slice.items(.value)[index],
568 };
569 }
570
571 /// Finds the index in the `entries` array where a key is stored
572 pub fn getIndex(self: Self, key: K) ?usize {
573 if (@sizeOf(Context) != 0)
574 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getIndexContext instead.");
575 return self.getIndexContext(key, undefined);
576 }
577 pub fn getIndexContext(self: Self, key: K, ctx: Context) ?usize {
578 return self.getIndexAdapted(key, ctx);
579 }
580 pub fn getIndexAdapted(self: Self, key: anytype, ctx: anytype) ?usize {
581 const header = self.index_header orelse {
582 // Linear scan.
583 const h = if (store_hash) checkedHash(ctx, key) else {};
584 const slice = self.entries.slice();
585 const hashes_array = slice.items(.hash);
586 const keys_array = slice.items(.key);
587 for (keys_array, 0..) |*item_key, i| {
588 if (hashes_array[i] == h and checkedEql(ctx, key, item_key.*, i)) {
589 return i;
590 }
591 }
592 return null;
593 };
594 switch (header.capacityIndexType()) {
595 .u8 => return self.getIndexWithHeaderGeneric(key, ctx, header, u8),
596 .u16 => return self.getIndexWithHeaderGeneric(key, ctx, header, u16),
597 .u32 => return self.getIndexWithHeaderGeneric(key, ctx, header, u32),
598 }
599 }
600 fn getIndexWithHeaderGeneric(self: Self, key: anytype, ctx: anytype, header: *IndexHeader, comptime I: type) ?usize {
601 const indexes = header.indexes(I);
602 const slot = self.getSlotByKey(key, ctx, header, I, indexes) orelse return null;
603 return indexes[slot].entry_index;
604 }
605
606 /// Find the value associated with a key
607 pub fn get(self: Self, key: K) ?V {
608 if (@sizeOf(Context) != 0)
609 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getContext instead.");
610 return self.getContext(key, undefined);
611 }
612 pub fn getContext(self: Self, key: K, ctx: Context) ?V {
613 return self.getAdapted(key, ctx);
614 }
615 pub fn getAdapted(self: Self, key: anytype, ctx: anytype) ?V {
616 const index = self.getIndexAdapted(key, ctx) orelse return null;
617 return self.values()[index];
618 }
619
620 /// Find a pointer to the value associated with a key
621 pub fn getPtr(self: Self, key: K) ?*V {
622 if (@sizeOf(Context) != 0)
623 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getPtrContext instead.");
624 return self.getPtrContext(key, undefined);
625 }
626 pub fn getPtrContext(self: Self, key: K, ctx: Context) ?*V {
627 return self.getPtrAdapted(key, ctx);
628 }
629 pub fn getPtrAdapted(self: Self, key: anytype, ctx: anytype) ?*V {
630 const index = self.getIndexAdapted(key, ctx) orelse return null;
631 return &self.values()[index];
632 }
633
634 /// Find the actual key associated with an adapted key
635 pub fn getKey(self: Self, key: K) ?K {
636 if (@sizeOf(Context) != 0)
637 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getKeyContext instead.");
638 return self.getKeyContext(key, undefined);
639 }
640 pub fn getKeyContext(self: Self, key: K, ctx: Context) ?K {
641 return self.getKeyAdapted(key, ctx);
642 }
643 pub fn getKeyAdapted(self: Self, key: anytype, ctx: anytype) ?K {
644 const index = self.getIndexAdapted(key, ctx) orelse return null;
645 return self.keys()[index];
646 }
647
648 /// Find a pointer to the actual key associated with an adapted key
649 pub fn getKeyPtr(self: Self, key: K) ?*K {
650 if (@sizeOf(Context) != 0)
651 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getKeyPtrContext instead.");
652 return self.getKeyPtrContext(key, undefined);
653 }
654 pub fn getKeyPtrContext(self: Self, key: K, ctx: Context) ?*K {
655 return self.getKeyPtrAdapted(key, ctx);
656 }
657 pub fn getKeyPtrAdapted(self: Self, key: anytype, ctx: anytype) ?*K {
658 const index = self.getIndexAdapted(key, ctx) orelse return null;
659 return &self.keys()[index];
660 }
661
662 /// Check whether a key is stored in the map
663 pub fn contains(self: Self, key: K) bool {
664 if (@sizeOf(Context) != 0)
665 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call containsContext instead.");
666 return self.containsContext(key, undefined);
667 }
668 pub fn containsContext(self: Self, key: K, ctx: Context) bool {
669 return self.containsAdapted(key, ctx);
670 }
671 pub fn containsAdapted(self: Self, key: anytype, ctx: anytype) bool {
672 return self.getIndexAdapted(key, ctx) != null;
673 }
674
675 /// If there is an `Entry` with a matching key, it is deleted from
676 /// the hash map, and then returned from this function. The entry is
677 /// removed from the underlying array by swapping it with the last
678 /// element.
679 pub fn fetchSwapRemove(self: *Self, key: K) ?KV {
680 if (@sizeOf(Context) != 0)
681 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call fetchSwapRemoveContext instead.");
682 return self.fetchSwapRemoveContext(key, undefined);
683 }
684 pub fn fetchSwapRemoveContext(self: *Self, key: K, ctx: Context) ?KV {
685 return self.fetchSwapRemoveContextAdapted(key, ctx, ctx);
686 }
687 pub fn fetchSwapRemoveAdapted(self: *Self, key: anytype, ctx: anytype) ?KV {
688 if (@sizeOf(ByIndexContext) != 0)
689 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call fetchSwapRemoveContextAdapted instead.");
690 return self.fetchSwapRemoveContextAdapted(key, ctx, undefined);
691 }
692 pub fn fetchSwapRemoveContextAdapted(self: *Self, key: anytype, key_ctx: anytype, ctx: Context) ?KV {
693 self.pointer_stability.lock();
694 defer self.pointer_stability.unlock();
695
696 return self.fetchRemoveByKey(key, key_ctx, if (store_hash) {} else ctx, .swap);
697 }
698
699 /// If there is an `Entry` with a matching key, it is deleted from
700 /// the hash map, and then returned from this function. The entry is
701 /// removed from the underlying array by shifting all elements forward
702 /// thereby maintaining the current ordering.
703 pub fn fetchOrderedRemove(self: *Self, key: K) ?KV {
704 if (@sizeOf(Context) != 0)
705 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call fetchOrderedRemoveContext instead.");
706 return self.fetchOrderedRemoveContext(key, undefined);
707 }
708 pub fn fetchOrderedRemoveContext(self: *Self, key: K, ctx: Context) ?KV {
709 return self.fetchOrderedRemoveContextAdapted(key, ctx, ctx);
710 }
711 pub fn fetchOrderedRemoveAdapted(self: *Self, key: anytype, ctx: anytype) ?KV {
712 if (@sizeOf(ByIndexContext) != 0)
713 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call fetchOrderedRemoveContextAdapted instead.");
714 return self.fetchOrderedRemoveContextAdapted(key, ctx, undefined);
715 }
716 pub fn fetchOrderedRemoveContextAdapted(self: *Self, key: anytype, key_ctx: anytype, ctx: Context) ?KV {
717 self.pointer_stability.lock();
718 defer self.pointer_stability.unlock();
719
720 return self.fetchRemoveByKey(key, key_ctx, if (store_hash) {} else ctx, .ordered);
721 }
722
723 /// If there is an `Entry` with a matching key, it is deleted from
724 /// the hash map. The entry is removed from the underlying array
725 /// by swapping it with the last element. Returns true if an entry
726 /// was removed, false otherwise.
727 pub fn swapRemove(self: *Self, key: K) bool {
728 if (@sizeOf(Context) != 0)
729 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call swapRemoveContext instead.");
730 return self.swapRemoveContext(key, undefined);
731 }
732 pub fn swapRemoveContext(self: *Self, key: K, ctx: Context) bool {
733 return self.swapRemoveContextAdapted(key, ctx, ctx);
734 }
735 pub fn swapRemoveAdapted(self: *Self, key: anytype, ctx: anytype) bool {
736 if (@sizeOf(ByIndexContext) != 0)
737 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call swapRemoveContextAdapted instead.");
738 return self.swapRemoveContextAdapted(key, ctx, undefined);
739 }
740 pub fn swapRemoveContextAdapted(self: *Self, key: anytype, key_ctx: anytype, ctx: Context) bool {
741 self.pointer_stability.lock();
742 defer self.pointer_stability.unlock();
743
744 return self.removeByKey(key, key_ctx, if (store_hash) {} else ctx, .swap);
745 }
746
747 /// If there is an `Entry` with a matching key, it is deleted from
748 /// the hash map. The entry is removed from the underlying array
749 /// by shifting all elements forward, thereby maintaining the
750 /// current ordering. Returns true if an entry was removed, false otherwise.
751 pub fn orderedRemove(self: *Self, key: K) bool {
752 if (@sizeOf(Context) != 0)
753 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call orderedRemoveContext instead.");
754 return self.orderedRemoveContext(key, undefined);
755 }
756 pub fn orderedRemoveContext(self: *Self, key: K, ctx: Context) bool {
757 return self.orderedRemoveContextAdapted(key, ctx, ctx);
758 }
759 pub fn orderedRemoveAdapted(self: *Self, key: anytype, ctx: anytype) bool {
760 if (@sizeOf(ByIndexContext) != 0)
761 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call orderedRemoveContextAdapted instead.");
762 return self.orderedRemoveContextAdapted(key, ctx, undefined);
763 }
764 pub fn orderedRemoveContextAdapted(self: *Self, key: anytype, key_ctx: anytype, ctx: Context) bool {
765 self.pointer_stability.lock();
766 defer self.pointer_stability.unlock();
767
768 return self.removeByKey(key, key_ctx, if (store_hash) {} else ctx, .ordered);
769 }
770
771 /// Deletes the item at the specified index in `entries` from
772 /// the hash map. The entry is removed from the underlying array
773 /// by swapping it with the last element.
774 pub fn swapRemoveAt(self: *Self, index: usize) void {
775 if (@sizeOf(ByIndexContext) != 0)
776 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call swapRemoveAtContext instead.");
777 return self.swapRemoveAtContext(index, undefined);
778 }
779 pub fn swapRemoveAtContext(self: *Self, index: usize, ctx: Context) void {
780 self.pointer_stability.lock();
781 defer self.pointer_stability.unlock();
782
783 self.removeByIndex(index, if (store_hash) {} else ctx, .swap);
784 }
785
786 /// Deletes the item at the specified index in `entries` from
787 /// the hash map. The entry is removed from the underlying array
788 /// by shifting all elements forward, thereby maintaining the
789 /// current ordering.
790 pub fn orderedRemoveAt(self: *Self, index: usize) void {
791 if (@sizeOf(ByIndexContext) != 0)
792 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call orderedRemoveAtContext instead.");
793 return self.orderedRemoveAtContext(index, undefined);
794 }
795 pub fn orderedRemoveAtContext(self: *Self, index: usize, ctx: Context) void {
796 self.pointer_stability.lock();
797 defer self.pointer_stability.unlock();
798
799 self.removeByIndex(index, if (store_hash) {} else ctx, .ordered);
800 }
801
802 /// Remove the entries indexed by `sorted_indexes`. The indexes to be
803 /// removed correspond to state before deletion.
804 ///
805 /// This operation is O(N).
806 ///
807 /// Asserts that each index to be removed is in bounds.
808 ///
809 /// Invalidates key and element pointers beyond the first deleted index.
810 pub fn orderedRemoveAtMany(self: *Self, gpa: Allocator, sorted_indexes: []const usize) Oom!void {
811 if (@sizeOf(ByIndexContext) != 0)
812 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call orderedRemoveAtContext instead.");
813 return self.orderedRemoveAtManyContext(gpa, sorted_indexes, undefined);
814 }
815
816 pub fn orderedRemoveAtManyContext(
817 self: *Self,
818 gpa: Allocator,
819 sorted_indexes: []const usize,
820 ctx: Context,
821 ) Oom!void {
822 self.pointer_stability.lock();
823 defer self.pointer_stability.unlock();
824
825 self.entries.orderedRemoveMany(sorted_indexes);
826 try self.reIndexContext(gpa, ctx);
827 }
828
829 /// Create a copy of the hash map which can be modified separately.
830 /// The copy uses the same context as this instance, but is allocated
831 /// with the provided allocator.
832 pub fn clone(self: Self, gpa: Allocator) Oom!Self {
833 if (@sizeOf(ByIndexContext) != 0)
834 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call cloneContext instead.");
835 return self.cloneContext(gpa, undefined);
836 }
837 pub fn cloneContext(self: Self, gpa: Allocator, ctx: Context) Oom!Self {
838 var other: Self = .{};
839 other.entries = try self.entries.clone(gpa);
840 errdefer other.entries.deinit(gpa);
841
842 if (self.index_header) |header| {
843 // TODO: I'm pretty sure this could be memcpy'd instead of
844 // doing all this work.
845 const new_header = try IndexHeader.alloc(gpa, header.bit_index);
846 other.insertAllEntriesIntoNewHeader(if (store_hash) {} else ctx, new_header);
847 other.index_header = new_header;
848 }
849 return other;
850 }
851
852 /// Set the map to an empty state, making deinitialization a no-op, and
853 /// returning a copy of the original.
854 pub fn move(self: *Self) Self {
855 self.pointer_stability.assertUnlocked();
856 const result = self.*;
857 self.* = .empty;
858 return result;
859 }
860
861 /// Recomputes stored hashes and rebuilds the key indexes. If the
862 /// underlying keys have been modified directly, call this method to
863 /// recompute the denormalized metadata necessary for the operation of
864 /// the methods of this map that lookup entries by key.
865 ///
866 /// One use case for this is directly calling `entries.resize()` to grow
867 /// the underlying storage, and then setting the `keys` and `values`
868 /// directly without going through the methods of this map.
869 ///
870 /// The time complexity of this operation is O(n).
871 pub fn reIndex(self: *Self, gpa: Allocator) Oom!void {
872 if (@sizeOf(ByIndexContext) != 0)
873 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call reIndexContext instead.");
874 return self.reIndexContext(gpa, undefined);
875 }
876
877 pub fn reIndexContext(self: *Self, gpa: Allocator, ctx: Context) Oom!void {
878 // Recompute all hashes.
879 if (store_hash) {
880 for (self.keys(), self.entries.items(.hash)) |key, *hash| {
881 const h = checkedHash(ctx, key);
882 hash.* = h;
883 }
884 }
885 try rebuildIndex(self, gpa, ctx);
886 }
887
888 /// Modify an entry's key without reordering any entries.
889 pub fn setKey(self: *Self, index: usize, new_key: K) void {
890 if (@sizeOf(ByIndexContext) != 0)
891 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call setKeyContext instead.");
892 return setKeyContext(self, index, new_key, undefined);
893 }
894
895 pub fn setKeyContext(self: *Self, index: usize, new_key: K, ctx: Context) void {
896 if (self.index_header) |header| {
897 self.removeFromIndexByIndex(index, if (store_hash) {} else ctx, header);
898
899 self.entries.items(.key)[index] = new_key;
900 const h = checkedHash(ctx, new_key);
901 if (store_hash) self.entries.items(.hash)[index] = h;
902
903 insertEntryIntoNewHeader(header, h, index);
904 } else {
905 self.entries.items(.key)[index] = new_key;
906 if (store_hash) self.entries.items(.hash)[index] = checkedHash(ctx, new_key);
907 }
908 }
909
910 fn rebuildIndex(self: *Self, gpa: Allocator, ctx: Context) Oom!void {
911 if (self.entries.capacity <= linear_scan_max) return;
912
913 // We're going to rebuild the index header and replace the existing one (if any). The
914 // indexes should sized such that they will be at most 60% full.
915 const bit_index = try IndexHeader.findBitIndex(self.entries.capacity);
916 const new_header = try IndexHeader.alloc(gpa, bit_index);
917 if (self.index_header) |header| header.free(gpa);
918 self.insertAllEntriesIntoNewHeader(if (store_hash) {} else ctx, new_header);
919 self.index_header = new_header;
920 }
921
922 /// Sorts the entries and then rebuilds the index.
923 /// `sort_ctx` must have this method:
924 /// `fn lessThan(ctx: @TypeOf(ctx), a_index: usize, b_index: usize) bool`
925 /// Uses a stable sorting algorithm.
926 pub inline fn sort(self: *Self, sort_ctx: anytype) void {
927 if (@sizeOf(ByIndexContext) != 0)
928 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call sortContext instead.");
929 return sortContextInternal(self, .stable, sort_ctx, undefined);
930 }
931
932 /// Sorts the entries and then rebuilds the index.
933 /// `sort_ctx` must have this method:
934 /// `fn lessThan(ctx: @TypeOf(ctx), a_index: usize, b_index: usize) bool`
935 /// Uses an unstable sorting algorithm.
936 pub inline fn sortUnstable(self: *Self, sort_ctx: anytype) void {
937 if (@sizeOf(ByIndexContext) != 0)
938 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call sortUnstableContext instead.");
939 return self.sortContextInternal(.unstable, sort_ctx, undefined);
940 }
941
942 pub inline fn sortContext(self: *Self, sort_ctx: anytype, ctx: Context) void {
943 return sortContextInternal(self, .stable, sort_ctx, ctx);
944 }
945
946 pub inline fn sortUnstableContext(self: *Self, sort_ctx: anytype, ctx: Context) void {
947 return sortContextInternal(self, .unstable, sort_ctx, ctx);
948 }
949
950 fn sortContextInternal(
951 self: *Self,
952 comptime mode: std.sort.Mode,
953 sort_ctx: anytype,
954 ctx: Context,
955 ) void {
956 self.pointer_stability.lock();
957 defer self.pointer_stability.unlock();
958
959 switch (mode) {
960 .stable => self.entries.sort(sort_ctx),
961 .unstable => self.entries.sortUnstable(sort_ctx),
962 }
963 const header = self.index_header orelse return;
964 header.reset();
965 self.insertAllEntriesIntoNewHeader(if (store_hash) {} else ctx, header);
966 }
967
968 /// Shrinks the underlying `Entry` array to `new_len` elements and
969 /// discards any associated index entries. Keeps capacity the same.
970 ///
971 /// Asserts the discarded entries remain initialized and capable of
972 /// performing hash and equality checks. Any deinitialization of
973 /// discarded entries must take place *after* calling this function.
974 pub fn shrinkRetainingCapacity(self: *Self, new_len: usize) void {
975 if (@sizeOf(ByIndexContext) != 0)
976 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call shrinkRetainingCapacityContext instead.");
977 return self.shrinkRetainingCapacityContext(new_len, undefined);
978 }
979
980 /// Shrinks the underlying `Entry` array to `new_len` elements and
981 /// discards any associated index entries. Keeps capacity the same.
982 ///
983 /// Asserts the discarded entries remain initialized and capable of
984 /// performing hash and equality checks. Any deinitialization of
985 /// discarded entries must take place *after* calling this function.
986 pub fn shrinkRetainingCapacityContext(self: *Self, new_len: usize, ctx: Context) void {
987 self.pointer_stability.lock();
988 defer self.pointer_stability.unlock();
989
990 // Remove index entries from the new length onwards.
991 // Explicitly choose to ONLY remove index entries and not the underlying array list
992 // entries as we're going to remove them in the subsequent shrink call.
993 if (self.index_header) |header| {
994 var i: usize = new_len;
995 while (i < self.entries.len) : (i += 1)
996 self.removeFromIndexByIndex(i, if (store_hash) {} else ctx, header);
997 }
998 self.entries.shrinkRetainingCapacity(new_len);
999 }
1000
1001 /// Shrinks the underlying `Entry` array to `new_len` elements and
1002 /// discards any associated index entries. Reduces allocated capacity.
1003 ///
1004 /// Asserts the discarded entries remain initialized and capable of
1005 /// performing hash and equality checks. It is a bug to call this
1006 /// function if the discarded entries require deinitialization. For
1007 /// that use case, `shrinkRetainingCapacity` can be used instead.
1008 pub fn shrinkAndFree(self: *Self, gpa: Allocator, new_len: usize) void {
1009 if (@sizeOf(ByIndexContext) != 0)
1010 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call shrinkAndFreeContext instead.");
1011 return self.shrinkAndFreeContext(gpa, new_len, undefined);
1012 }
1013
1014 /// Shrinks the underlying `Entry` array to `new_len` elements and
1015 /// discards any associated index entries. Reduces allocated capacity.
1016 ///
1017 /// Asserts the discarded entries remain initialized and capable of
1018 /// performing hash and equality checks. It is a bug to call this
1019 /// function if the discarded entries require deinitialization. For
1020 /// that use case, `shrinkRetainingCapacityContext` can be used
1021 /// instead.
1022 pub fn shrinkAndFreeContext(self: *Self, gpa: Allocator, new_len: usize, ctx: Context) void {
1023 self.pointer_stability.lock();
1024 defer self.pointer_stability.unlock();
1025
1026 // Remove index entries from the new length onwards.
1027 // Explicitly choose to ONLY remove index entries and not the underlying array list
1028 // entries as we're going to remove them in the subsequent shrink call.
1029 if (self.index_header) |header| {
1030 var i: usize = new_len;
1031 while (i < self.entries.len) : (i += 1)
1032 self.removeFromIndexByIndex(i, if (store_hash) {} else ctx, header);
1033 }
1034 self.entries.shrinkAndFree(gpa, new_len);
1035 }
1036
1037 /// Removes the last inserted `Entry` in the hash map and returns it.
1038 /// Otherwise returns null.
1039 pub fn pop(self: *Self) ?KV {
1040 if (@sizeOf(ByIndexContext) != 0)
1041 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call popContext instead.");
1042 return self.popContext(undefined);
1043 }
1044 pub fn popContext(self: *Self, ctx: Context) ?KV {
1045 if (self.entries.len == 0) return null;
1046 self.pointer_stability.lock();
1047 defer self.pointer_stability.unlock();
1048
1049 const item = self.entries.get(self.entries.len - 1);
1050 if (self.index_header) |header|
1051 self.removeFromIndexByIndex(self.entries.len - 1, if (store_hash) {} else ctx, header);
1052 self.entries.len -= 1;
1053 return .{
1054 .key = item.key,
1055 .value = item.value,
1056 };
1057 }
1058
1059 fn fetchRemoveByKey(
1060 self: *Self,
1061 key: anytype,
1062 key_ctx: anytype,
1063 ctx: ByIndexContext,
1064 comptime removal_type: RemovalType,
1065 ) ?KV {
1066 const header = self.index_header orelse {
1067 // Linear scan.
1068 const key_hash = if (store_hash) key_ctx.hash(key) else {};
1069 const slice = self.entries.slice();
1070 const hashes_array = if (store_hash) slice.items(.hash) else {};
1071 const keys_array = slice.items(.key);
1072 for (keys_array, 0..) |*item_key, i| {
1073 const hash_match = if (store_hash) hashes_array[i] == key_hash else true;
1074 if (hash_match and key_ctx.eql(key, item_key.*, i)) {
1075 const removed_entry: KV = .{
1076 .key = keys_array[i],
1077 .value = slice.items(.value)[i],
1078 };
1079 switch (removal_type) {
1080 .swap => self.entries.swapRemove(i),
1081 .ordered => self.entries.orderedRemove(i),
1082 }
1083 return removed_entry;
1084 }
1085 }
1086 return null;
1087 };
1088 return switch (header.capacityIndexType()) {
1089 .u8 => self.fetchRemoveByKeyGeneric(key, key_ctx, ctx, header, u8, removal_type),
1090 .u16 => self.fetchRemoveByKeyGeneric(key, key_ctx, ctx, header, u16, removal_type),
1091 .u32 => self.fetchRemoveByKeyGeneric(key, key_ctx, ctx, header, u32, removal_type),
1092 };
1093 }
1094 fn fetchRemoveByKeyGeneric(
1095 self: *Self,
1096 key: anytype,
1097 key_ctx: anytype,
1098 ctx: ByIndexContext,
1099 header: *IndexHeader,
1100 comptime I: type,
1101 comptime removal_type: RemovalType,
1102 ) ?KV {
1103 const indexes = header.indexes(I);
1104 const entry_index = self.removeFromIndexByKey(key, key_ctx, header, I, indexes) orelse return null;
1105 const slice = self.entries.slice();
1106 const removed_entry: KV = .{
1107 .key = slice.items(.key)[entry_index],
1108 .value = slice.items(.value)[entry_index],
1109 };
1110 self.removeFromArrayAndUpdateIndex(entry_index, ctx, header, I, indexes, removal_type);
1111 return removed_entry;
1112 }
1113
1114 fn removeByKey(
1115 self: *Self,
1116 key: anytype,
1117 key_ctx: anytype,
1118 ctx: ByIndexContext,
1119 comptime removal_type: RemovalType,
1120 ) bool {
1121 const header = self.index_header orelse {
1122 // Linear scan.
1123 const key_hash = if (store_hash) key_ctx.hash(key) else {};
1124 const slice = self.entries.slice();
1125 const hashes_array = if (store_hash) slice.items(.hash) else {};
1126 const keys_array = slice.items(.key);
1127 for (keys_array, 0..) |*item_key, i| {
1128 const hash_match = if (store_hash) hashes_array[i] == key_hash else true;
1129 if (hash_match and key_ctx.eql(key, item_key.*, i)) {
1130 switch (removal_type) {
1131 .swap => self.entries.swapRemove(i),
1132 .ordered => self.entries.orderedRemove(i),
1133 }
1134 return true;
1135 }
1136 }
1137 return false;
1138 };
1139 return switch (header.capacityIndexType()) {
1140 .u8 => self.removeByKeyGeneric(key, key_ctx, ctx, header, u8, removal_type),
1141 .u16 => self.removeByKeyGeneric(key, key_ctx, ctx, header, u16, removal_type),
1142 .u32 => self.removeByKeyGeneric(key, key_ctx, ctx, header, u32, removal_type),
1143 };
1144 }
1145 fn removeByKeyGeneric(self: *Self, key: anytype, key_ctx: anytype, ctx: ByIndexContext, header: *IndexHeader, comptime I: type, comptime removal_type: RemovalType) bool {
1146 const indexes = header.indexes(I);
1147 const entry_index = self.removeFromIndexByKey(key, key_ctx, header, I, indexes) orelse return false;
1148 self.removeFromArrayAndUpdateIndex(entry_index, ctx, header, I, indexes, removal_type);
1149 return true;
1150 }
1151
1152 fn removeByIndex(self: *Self, entry_index: usize, ctx: ByIndexContext, comptime removal_type: RemovalType) void {
1153 assert(entry_index < self.entries.len);
1154 const header = self.index_header orelse {
1155 switch (removal_type) {
1156 .swap => self.entries.swapRemove(entry_index),
1157 .ordered => self.entries.orderedRemove(entry_index),
1158 }
1159 return;
1160 };
1161 switch (header.capacityIndexType()) {
1162 .u8 => self.removeByIndexGeneric(entry_index, ctx, header, u8, removal_type),
1163 .u16 => self.removeByIndexGeneric(entry_index, ctx, header, u16, removal_type),
1164 .u32 => self.removeByIndexGeneric(entry_index, ctx, header, u32, removal_type),
1165 }
1166 }
1167 fn removeByIndexGeneric(self: *Self, entry_index: usize, ctx: ByIndexContext, header: *IndexHeader, comptime I: type, comptime removal_type: RemovalType) void {
1168 const indexes = header.indexes(I);
1169 self.removeFromIndexByIndexGeneric(entry_index, ctx, header, I, indexes);
1170 self.removeFromArrayAndUpdateIndex(entry_index, ctx, header, I, indexes, removal_type);
1171 }
1172
1173 fn removeFromArrayAndUpdateIndex(self: *Self, entry_index: usize, ctx: ByIndexContext, header: *IndexHeader, comptime I: type, indexes: []Index(I), comptime removal_type: RemovalType) void {
1174 const last_index = self.entries.len - 1; // overflow => remove from empty map
1175 switch (removal_type) {
1176 .swap => {
1177 if (last_index != entry_index) {
1178 // Because of the swap remove, now we need to update the index that was
1179 // pointing to the last entry and is now pointing to this removed item slot.
1180 self.updateEntryIndex(header, last_index, entry_index, ctx, I, indexes);
1181 }
1182 // updateEntryIndex reads from the old entry index,
1183 // so it needs to run before removal.
1184 self.entries.swapRemove(entry_index);
1185 },
1186 .ordered => {
1187 var i: usize = entry_index;
1188 while (i < last_index) : (i += 1) {
1189 // Because of the ordered remove, everything from the entry index onwards has
1190 // been shifted forward so we'll need to update the index entries.
1191 self.updateEntryIndex(header, i + 1, i, ctx, I, indexes);
1192 }
1193 // updateEntryIndex reads from the old entry index,
1194 // so it needs to run before removal.
1195 self.entries.orderedRemove(entry_index);
1196 },
1197 }
1198 }
1199
1200 fn updateEntryIndex(
1201 self: *Self,
1202 header: *IndexHeader,
1203 old_entry_index: usize,
1204 new_entry_index: usize,
1205 ctx: ByIndexContext,
1206 comptime I: type,
1207 indexes: []Index(I),
1208 ) void {
1209 const slot = self.getSlotByIndex(old_entry_index, ctx, header, I, indexes);
1210 indexes[slot].entry_index = @as(I, @intCast(new_entry_index));
1211 }
1212
1213 fn removeFromIndexByIndex(self: *Self, entry_index: usize, ctx: ByIndexContext, header: *IndexHeader) void {
1214 switch (header.capacityIndexType()) {
1215 .u8 => self.removeFromIndexByIndexGeneric(entry_index, ctx, header, u8, header.indexes(u8)),
1216 .u16 => self.removeFromIndexByIndexGeneric(entry_index, ctx, header, u16, header.indexes(u16)),
1217 .u32 => self.removeFromIndexByIndexGeneric(entry_index, ctx, header, u32, header.indexes(u32)),
1218 }
1219 }
1220 fn removeFromIndexByIndexGeneric(self: *Self, entry_index: usize, ctx: ByIndexContext, header: *IndexHeader, comptime I: type, indexes: []Index(I)) void {
1221 const slot = self.getSlotByIndex(entry_index, ctx, header, I, indexes);
1222 removeSlot(slot, header, I, indexes);
1223 }
1224
1225 fn removeFromIndexByKey(self: *Self, key: anytype, ctx: anytype, header: *IndexHeader, comptime I: type, indexes: []Index(I)) ?usize {
1226 const slot = self.getSlotByKey(key, ctx, header, I, indexes) orelse return null;
1227 const removed_entry_index = indexes[slot].entry_index;
1228 removeSlot(slot, header, I, indexes);
1229 return removed_entry_index;
1230 }
1231
1232 fn removeSlot(removed_slot: usize, header: *IndexHeader, comptime I: type, indexes: []Index(I)) void {
1233 const start_index = removed_slot +% 1;
1234 const end_index = start_index +% indexes.len;
1235
1236 var last_slot = removed_slot;
1237 var index: usize = start_index;
1238 while (index != end_index) : (index +%= 1) {
1239 const slot = header.constrainIndex(index);
1240 const slot_data = indexes[slot];
1241 if (slot_data.isEmpty() or slot_data.distance_from_start_index == 0) {
1242 indexes[last_slot].setEmpty();
1243 return;
1244 }
1245 indexes[last_slot] = .{
1246 .entry_index = slot_data.entry_index,
1247 .distance_from_start_index = slot_data.distance_from_start_index - 1,
1248 };
1249 last_slot = slot;
1250 }
1251 unreachable;
1252 }
1253
1254 fn getSlotByIndex(self: *Self, entry_index: usize, ctx: ByIndexContext, header: *IndexHeader, comptime I: type, indexes: []Index(I)) usize {
1255 const slice = self.entries.slice();
1256 const h = if (store_hash) slice.items(.hash)[entry_index] else checkedHash(ctx, slice.items(.key)[entry_index]);
1257 const start_index = safeTruncate(usize, h);
1258 const end_index = start_index +% indexes.len;
1259
1260 var index = start_index;
1261 var distance_from_start_index: I = 0;
1262 while (index != end_index) : ({
1263 index +%= 1;
1264 distance_from_start_index += 1;
1265 }) {
1266 const slot = header.constrainIndex(index);
1267 const slot_data = indexes[slot];
1268
1269 // This is the fundamental property of the array hash map index. If this
1270 // assert fails, it probably means that the entry was not in the index.
1271 assert(!slot_data.isEmpty());
1272 assert(slot_data.distance_from_start_index >= distance_from_start_index);
1273
1274 if (slot_data.entry_index == entry_index) {
1275 return slot;
1276 }
1277 }
1278 unreachable;
1279 }
1280
1281 /// Must `ensureTotalCapacity`/`ensureUnusedCapacity` before calling this.
1282 fn getOrPutInternal(self: *Self, key: anytype, ctx: anytype, header: *IndexHeader, comptime I: type) GetOrPutResult {
1283 const slice = self.entries.slice();
1284 const hashes_array = if (store_hash) slice.items(.hash) else {};
1285 const keys_array = slice.items(.key);
1286 const values_array = slice.items(.value);
1287 const indexes = header.indexes(I);
1288
1289 const h = checkedHash(ctx, key);
1290 const start_index = safeTruncate(usize, h);
1291 const end_index = start_index +% indexes.len;
1292
1293 var index = start_index;
1294 var distance_from_start_index: I = 0;
1295 while (index != end_index) : ({
1296 index +%= 1;
1297 distance_from_start_index += 1;
1298 }) {
1299 var slot = header.constrainIndex(index);
1300 var slot_data = indexes[slot];
1301
1302 // If the slot is empty, there can be no more items in this run.
1303 // We didn't find a matching item, so this must be new.
1304 // Put it in the empty slot.
1305 if (slot_data.isEmpty()) {
1306 const new_index = self.entries.addOneAssumeCapacity();
1307 indexes[slot] = .{
1308 .distance_from_start_index = distance_from_start_index,
1309 .entry_index = @as(I, @intCast(new_index)),
1310 };
1311
1312 // update the hash if applicable
1313 if (store_hash) hashes_array.ptr[new_index] = h;
1314
1315 return .{
1316 .found_existing = false,
1317 .key_ptr = &keys_array.ptr[new_index],
1318 .value_ptr = &values_array.ptr[new_index],
1319 .index = new_index,
1320 };
1321 }
1322
1323 // This pointer survives the following append because we call
1324 // entries.ensureTotalCapacity before getOrPutInternal.
1325 const i = slot_data.entry_index;
1326 const hash_match = if (store_hash) h == hashes_array[i] else true;
1327 if (hash_match and checkedEql(ctx, key, keys_array[i], i)) {
1328 return .{
1329 .found_existing = true,
1330 .key_ptr = &keys_array[slot_data.entry_index],
1331 .value_ptr = &values_array[slot_data.entry_index],
1332 .index = slot_data.entry_index,
1333 };
1334 }
1335
1336 // If the entry is closer to its target than our current distance,
1337 // the entry we are looking for does not exist. It would be in
1338 // this slot instead if it was here. So stop looking, and switch
1339 // to insert mode.
1340 if (slot_data.distance_from_start_index < distance_from_start_index) {
1341 // In this case, we did not find the item. We will put a new entry.
1342 // However, we will use this index for the new entry, and move
1343 // the previous index down the line, to keep the max distance_from_start_index
1344 // as small as possible.
1345 const new_index = self.entries.addOneAssumeCapacity();
1346 if (store_hash) hashes_array.ptr[new_index] = h;
1347 indexes[slot] = .{
1348 .entry_index = @as(I, @intCast(new_index)),
1349 .distance_from_start_index = distance_from_start_index,
1350 };
1351 distance_from_start_index = slot_data.distance_from_start_index;
1352 var displaced_index = slot_data.entry_index;
1353
1354 // Find somewhere to put the index we replaced by shifting
1355 // following indexes backwards.
1356 index +%= 1;
1357 distance_from_start_index += 1;
1358 while (index != end_index) : ({
1359 index +%= 1;
1360 distance_from_start_index += 1;
1361 }) {
1362 slot = header.constrainIndex(index);
1363 slot_data = indexes[slot];
1364 if (slot_data.isEmpty()) {
1365 indexes[slot] = .{
1366 .entry_index = displaced_index,
1367 .distance_from_start_index = distance_from_start_index,
1368 };
1369 return .{
1370 .found_existing = false,
1371 .key_ptr = &keys_array.ptr[new_index],
1372 .value_ptr = &values_array.ptr[new_index],
1373 .index = new_index,
1374 };
1375 }
1376
1377 if (slot_data.distance_from_start_index < distance_from_start_index) {
1378 indexes[slot] = .{
1379 .entry_index = displaced_index,
1380 .distance_from_start_index = distance_from_start_index,
1381 };
1382 displaced_index = slot_data.entry_index;
1383 distance_from_start_index = slot_data.distance_from_start_index;
1384 }
1385 }
1386 unreachable;
1387 }
1388 }
1389 unreachable;
1390 }
1391
1392 fn getSlotByKey(self: Self, key: anytype, ctx: anytype, header: *IndexHeader, comptime I: type, indexes: []Index(I)) ?usize {
1393 const slice = self.entries.slice();
1394 const hashes_array = if (store_hash) slice.items(.hash) else {};
1395 const keys_array = slice.items(.key);
1396 const h = checkedHash(ctx, key);
1397
1398 const start_index = safeTruncate(usize, h);
1399 const end_index = start_index +% indexes.len;
1400
1401 var index = start_index;
1402 var distance_from_start_index: I = 0;
1403 while (index != end_index) : ({
1404 index +%= 1;
1405 distance_from_start_index += 1;
1406 }) {
1407 const slot = header.constrainIndex(index);
1408 const slot_data = indexes[slot];
1409 if (slot_data.isEmpty() or slot_data.distance_from_start_index < distance_from_start_index)
1410 return null;
1411
1412 const i = slot_data.entry_index;
1413 const hash_match = if (store_hash) h == hashes_array[i] else true;
1414 if (hash_match and checkedEql(ctx, key, keys_array[i], i))
1415 return slot;
1416 }
1417 unreachable;
1418 }
1419
1420 fn insertAllEntriesIntoNewHeader(self: *Self, ctx: ByIndexContext, header: *IndexHeader) void {
1421 switch (header.capacityIndexType()) {
1422 .u8 => return self.insertAllEntriesIntoNewHeaderGeneric(ctx, header, u8),
1423 .u16 => return self.insertAllEntriesIntoNewHeaderGeneric(ctx, header, u16),
1424 .u32 => return self.insertAllEntriesIntoNewHeaderGeneric(ctx, header, u32),
1425 }
1426 }
1427 fn insertAllEntriesIntoNewHeaderGeneric(self: *Self, ctx: ByIndexContext, header: *IndexHeader, comptime I: type) void {
1428 const slice = self.entries.slice();
1429 const items = if (store_hash) slice.items(.hash) else slice.items(.key);
1430
1431 for (items, 0..) |hash_or_key, i| {
1432 const h = if (store_hash) hash_or_key else checkedHash(ctx, hash_or_key);
1433 insertEntryIntoNewHeaderGeneric(header, h, i, I);
1434 }
1435 }
1436
1437 fn insertEntryIntoNewHeader(header: *IndexHeader, h: u32, i: usize) void {
1438 switch (header.capacityIndexType()) {
1439 .u8 => insertEntryIntoNewHeaderGeneric(header, h, i, u8),
1440 .u16 => insertEntryIntoNewHeaderGeneric(header, h, i, u16),
1441 .u32 => insertEntryIntoNewHeaderGeneric(header, h, i, u32),
1442 }
1443 }
1444 fn insertEntryIntoNewHeaderGeneric(header: *IndexHeader, h: u32, i: usize, comptime I: type) void {
1445 const indexes = header.indexes(I);
1446 const start_index = safeTruncate(usize, h);
1447 const end_index = start_index +% indexes.len;
1448 var index = start_index;
1449 var entry_index: I = @intCast(i);
1450 var distance_from_start_index: I = 0;
1451 while (index != end_index) : ({
1452 index +%= 1;
1453 distance_from_start_index += 1;
1454 }) {
1455 const slot = header.constrainIndex(index);
1456 const next_index = indexes[slot];
1457 if (next_index.isEmpty()) {
1458 indexes[slot] = .{
1459 .distance_from_start_index = distance_from_start_index,
1460 .entry_index = entry_index,
1461 };
1462 return;
1463 }
1464 if (next_index.distance_from_start_index < distance_from_start_index) {
1465 indexes[slot] = .{
1466 .distance_from_start_index = distance_from_start_index,
1467 .entry_index = entry_index,
1468 };
1469 distance_from_start_index = next_index.distance_from_start_index;
1470 entry_index = next_index.entry_index;
1471 }
1472 }
1473 unreachable;
1474 }
1475
1476 fn checkedHash(ctx: anytype, key: anytype) u32 {
1477 // If you get a compile error on the next line, it means that your
1478 // generic hash function doesn't accept your key.
1479 return ctx.hash(key);
1480 }
1481
1482 fn checkedEql(ctx: anytype, a: anytype, b: K, b_index: usize) bool {
1483 // If you get a compile error on the next line, it means that your
1484 // generic eql function doesn't accept (self, adapt key, K, index).
1485 return ctx.eql(a, b, b_index);
1486 }
1487
1488 fn dumpState(self: Self, comptime keyFmt: []const u8, comptime valueFmt: []const u8) void {
1489 if (@sizeOf(ByIndexContext) != 0)
1490 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call dumpStateContext instead.");
1491 self.dumpStateContext(keyFmt, valueFmt, undefined);
1492 }
1493 fn dumpStateContext(self: Self, comptime keyFmt: []const u8, comptime valueFmt: []const u8, ctx: Context) void {
1494 const p = std.debug.print;
1495 p("{s}:\n", .{@typeName(Self)});
1496 const slice = self.entries.slice();
1497 const hash_status = if (store_hash) "stored" else "computed";
1498 p(" len={} capacity={} hashes {s}\n", .{ slice.len, slice.capacity, hash_status });
1499 var i: usize = 0;
1500 const mask: u32 = if (self.index_header) |header| header.mask() else ~@as(u32, 0);
1501 while (i < slice.len) : (i += 1) {
1502 const hash = if (store_hash) slice.items(.hash)[i] else checkedHash(ctx, slice.items(.key)[i]);
1503 if (store_hash) {
1504 p(
1505 " [{}]: key=" ++ keyFmt ++ " value=" ++ valueFmt ++ " hash=0x{x} slot=[0x{x}]\n",
1506 .{ i, slice.items(.key)[i], slice.items(.value)[i], hash, hash & mask },
1507 );
1508 } else {
1509 p(
1510 " [{}]: key=" ++ keyFmt ++ " value=" ++ valueFmt ++ " slot=[0x{x}]\n",
1511 .{ i, slice.items(.key)[i], slice.items(.value)[i], hash & mask },
1512 );
1513 }
1514 }
1515 if (self.index_header) |header| {
1516 p("\n", .{});
1517 switch (header.capacityIndexType()) {
1518 .u8 => dumpIndex(header, u8),
1519 .u16 => dumpIndex(header, u16),
1520 .u32 => dumpIndex(header, u32),
1521 }
1522 }
1523 }
1524 fn dumpIndex(header: *IndexHeader, comptime I: type) void {
1525 const p = std.debug.print;
1526 p(" index len=0x{x} type={}\n", .{ header.length(), header.capacityIndexType() });
1527 const indexes = header.indexes(I);
1528 if (indexes.len == 0) return;
1529 var is_empty = false;
1530 for (indexes, 0..) |idx, i| {
1531 if (idx.isEmpty()) {
1532 is_empty = true;
1533 } else {
1534 if (is_empty) {
1535 is_empty = false;
1536 p(" ...\n", .{});
1537 }
1538 p(" [0x{x}]: [{}] +{}\n", .{ i, idx.entry_index, idx.distance_from_start_index });
1539 }
1540 }
1541 if (is_empty) {
1542 p(" ...\n", .{});
1543 }
1544 }
1545 };
1546}
1547
1548const CapacityIndexType = enum { u8, u16, u32 };
1549
1550fn capacityIndexType(bit_index: u8) CapacityIndexType {
1551 if (bit_index <= 8)
1552 return .u8;
1553 if (bit_index <= 16)
1554 return .u16;
1555 assert(bit_index <= 32);
1556 return .u32;
1557}
1558
1559fn capacityIndexSize(bit_index: u8) usize {
1560 switch (capacityIndexType(bit_index)) {
1561 .u8 => return @sizeOf(Index(u8)),
1562 .u16 => return @sizeOf(Index(u16)),
1563 .u32 => return @sizeOf(Index(u32)),
1564 }
1565}
1566
1567/// @truncate fails if the target type is larger than the
1568/// target value. This causes problems when one of the types
1569/// is usize, which may be larger or smaller than u32 on different
1570/// systems. This version of truncate is safe to use if either
1571/// parameter has dynamic size, and will perform widening conversion
1572/// when needed. Both arguments must have the same signedness.
1573fn safeTruncate(comptime T: type, val: anytype) T {
1574 if (@bitSizeOf(T) >= @bitSizeOf(@TypeOf(val)))
1575 return val;
1576 return @as(T, @truncate(val));
1577}
1578
1579/// A single entry in the lookup acceleration structure. These structs
1580/// are found in an array after the IndexHeader. Hashes index into this
1581/// array, and linear probing is used for collisions.
1582fn Index(comptime I: type) type {
1583 return extern struct {
1584 const Self = @This();
1585
1586 /// The index of this entry in the backing store. If the index is
1587 /// empty, this is empty_sentinel.
1588 entry_index: I,
1589
1590 /// The distance between this slot and its ideal placement. This is
1591 /// used to keep maximum scan length small. This value is undefined
1592 /// if the index is empty.
1593 distance_from_start_index: I,
1594
1595 /// The special entry_index value marking an empty slot.
1596 const empty_sentinel = ~@as(I, 0);
1597
1598 /// A constant empty index
1599 const empty = Self{
1600 .entry_index = empty_sentinel,
1601 .distance_from_start_index = undefined,
1602 };
1603
1604 /// Checks if a slot is empty
1605 fn isEmpty(idx: Self) bool {
1606 return idx.entry_index == empty_sentinel;
1607 }
1608
1609 /// Sets a slot to empty
1610 fn setEmpty(idx: *Self) void {
1611 idx.entry_index = empty_sentinel;
1612 idx.distance_from_start_index = undefined;
1613 }
1614 };
1615}
1616
1617/// the byte size of the index must fit in a usize. This is a power of two
1618/// length * the size of an Index(u32). The index is 8 bytes (3 bits repr)
1619/// and max_usize + 1 is not representable, so we need to subtract out 4 bits.
1620const max_representable_index_len = @bitSizeOf(usize) - 4;
1621const max_bit_index = @min(32, max_representable_index_len);
1622const min_bit_index = 5;
1623const max_capacity = (1 << max_bit_index) - 1;
1624const index_capacities = blk: {
1625 var caps: [max_bit_index + 1]u32 = undefined;
1626 for (caps[0..max_bit_index], 0..) |*item, i| {
1627 item.* = (1 << i) * 3 / 5;
1628 }
1629 caps[max_bit_index] = max_capacity;
1630 break :blk caps;
1631};
1632
1633/// This struct is trailed by two arrays of length indexes_len
1634/// of integers, whose integer size is determined by indexes_len.
1635/// These arrays are indexed by constrainIndex(hash). The
1636/// entryIndexes array contains the index in the dense backing store
1637/// where the entry's data can be found. Entries which are not in
1638/// use have their index value set to emptySentinel(I).
1639/// The entryDistances array stores the distance between an entry
1640/// and its ideal hash bucket. This is used when adding elements
1641/// to balance the maximum scan length.
1642const IndexHeader = struct {
1643 /// This field tracks the total number of items in the arrays following
1644 /// this header. It is the bit index of the power of two number of indices.
1645 /// This value is between min_bit_index and max_bit_index, inclusive.
1646 bit_index: u8 align(@alignOf(u32)),
1647
1648 /// Map from an incrementing index to an index slot in the attached arrays.
1649 fn constrainIndex(header: IndexHeader, i: usize) usize {
1650 // This is an optimization for modulo of power of two integers;
1651 // it requires `indexes_len` to always be a power of two.
1652 return @as(usize, @intCast(i & header.mask()));
1653 }
1654
1655 /// Returns the attached array of indexes. I must match the type
1656 /// returned by capacityIndexType.
1657 fn indexes(header: *IndexHeader, comptime I: type) []Index(I) {
1658 const start_ptr: [*]Index(I) = @ptrCast(@alignCast(@as([*]u8, @ptrCast(header)) + @sizeOf(IndexHeader)));
1659 return start_ptr[0..header.length()];
1660 }
1661
1662 /// Returns the type used for the index arrays.
1663 fn capacityIndexType(header: IndexHeader) CapacityIndexType {
1664 return hash_map.capacityIndexType(header.bit_index);
1665 }
1666
1667 fn capacity(self: IndexHeader) u32 {
1668 return index_capacities[self.bit_index];
1669 }
1670 fn length(self: IndexHeader) usize {
1671 return @as(usize, 1) << @as(math.Log2Int(usize), @intCast(self.bit_index));
1672 }
1673 fn mask(self: IndexHeader) u32 {
1674 return @as(u32, @intCast(self.length() - 1));
1675 }
1676
1677 fn findBitIndex(desired_capacity: usize) Allocator.Error!u8 {
1678 if (desired_capacity > max_capacity) return error.OutOfMemory;
1679 var new_bit_index: u8 = @intCast(std.math.log2_int_ceil(usize, desired_capacity));
1680 if (desired_capacity > index_capacities[new_bit_index]) new_bit_index += 1;
1681 if (new_bit_index < min_bit_index) new_bit_index = min_bit_index;
1682 assert(desired_capacity <= index_capacities[new_bit_index]);
1683 return new_bit_index;
1684 }
1685
1686 /// Allocates an index header, and fills the entryIndexes array with empty.
1687 /// The distance array contents are undefined.
1688 fn alloc(gpa: Allocator, new_bit_index: u8) Allocator.Error!*IndexHeader {
1689 const len = @as(usize, 1) << @as(math.Log2Int(usize), @intCast(new_bit_index));
1690 const index_size = hash_map.capacityIndexSize(new_bit_index);
1691 const nbytes = @sizeOf(IndexHeader) + index_size * len;
1692 const bytes = try gpa.alignedAlloc(u8, .of(IndexHeader), nbytes);
1693 @memset(bytes[@sizeOf(IndexHeader)..], 0xff);
1694 const result: *IndexHeader = @ptrCast(@alignCast(bytes.ptr));
1695 result.* = .{
1696 .bit_index = new_bit_index,
1697 };
1698 return result;
1699 }
1700
1701 /// Releases the memory for a header and its associated arrays.
1702 fn free(header: *IndexHeader, gpa: Allocator) void {
1703 const index_size = hash_map.capacityIndexSize(header.bit_index);
1704 const ptr: [*]align(@alignOf(IndexHeader)) u8 = @ptrCast(header);
1705 const slice = ptr[0 .. @sizeOf(IndexHeader) + header.length() * index_size];
1706 gpa.free(slice);
1707 }
1708
1709 /// Puts an IndexHeader into the state that it would be in after being freshly allocated.
1710 fn reset(header: *IndexHeader) void {
1711 const index_size = hash_map.capacityIndexSize(header.bit_index);
1712 const ptr: [*]align(@alignOf(IndexHeader)) u8 = @ptrCast(header);
1713 const nbytes = @sizeOf(IndexHeader) + header.length() * index_size;
1714 @memset(ptr[@sizeOf(IndexHeader)..nbytes], 0xff);
1715 }
1716
1717 // Verify that the header has sufficient alignment to produce aligned arrays.
1718 comptime {
1719 if (@alignOf(u32) > @alignOf(IndexHeader))
1720 @compileError("IndexHeader must have a larger alignment than its indexes!");
1721 }
1722};
1723
1724test "basic hash map usage" {
1725 const gpa = testing.allocator;
1726
1727 var map: Auto(i32, i32) = .empty;
1728 defer map.deinit(gpa);
1729
1730 try testing.expect((try map.fetchPut(gpa, 1, 11)) == null);
1731 try testing.expect((try map.fetchPut(gpa, 2, 22)) == null);
1732 try testing.expect((try map.fetchPut(gpa, 3, 33)) == null);
1733 try testing.expect((try map.fetchPut(gpa, 4, 44)) == null);
1734
1735 try map.putNoClobber(gpa, 5, 55);
1736 try testing.expect((try map.fetchPut(gpa, 5, 66)).?.value == 55);
1737 try testing.expect((try map.fetchPut(gpa, 5, 55)).?.value == 66);
1738
1739 const gop1 = try map.getOrPut(gpa, 5);
1740 try testing.expect(gop1.found_existing == true);
1741 try testing.expect(gop1.value_ptr.* == 55);
1742 try testing.expect(gop1.index == 4);
1743 gop1.value_ptr.* = 77;
1744 try testing.expect(map.getEntry(5).?.value_ptr.* == 77);
1745
1746 const gop2 = try map.getOrPut(gpa, 99);
1747 try testing.expect(gop2.found_existing == false);
1748 try testing.expect(gop2.index == 5);
1749 gop2.value_ptr.* = 42;
1750 try testing.expect(map.getEntry(99).?.value_ptr.* == 42);
1751
1752 const gop3 = try map.getOrPutValue(gpa, 5, 5);
1753 try testing.expect(gop3.value_ptr.* == 77);
1754
1755 const gop4 = try map.getOrPutValue(gpa, 100, 41);
1756 try testing.expect(gop4.value_ptr.* == 41);
1757
1758 try testing.expect(map.contains(2));
1759 try testing.expect(map.getEntry(2).?.value_ptr.* == 22);
1760 try testing.expect(map.get(2).? == 22);
1761
1762 const rmv1 = map.fetchSwapRemove(2);
1763 try testing.expect(rmv1.?.key == 2);
1764 try testing.expect(rmv1.?.value == 22);
1765 try testing.expect(map.fetchSwapRemove(2) == null);
1766 try testing.expect(map.swapRemove(2) == false);
1767 try testing.expect(map.getEntry(2) == null);
1768 try testing.expect(map.get(2) == null);
1769
1770 // Since we've used `swapRemove` above, the index of this entry should remain unchanged.
1771 try testing.expect(map.getIndex(100).? == 1);
1772 const gop5 = try map.getOrPut(gpa, 5);
1773 try testing.expect(gop5.found_existing == true);
1774 try testing.expect(gop5.value_ptr.* == 77);
1775 try testing.expect(gop5.index == 4);
1776
1777 // Whereas, if we do an `orderedRemove`, it should move the index forward one spot.
1778 const rmv2 = map.fetchOrderedRemove(100);
1779 try testing.expect(rmv2.?.key == 100);
1780 try testing.expect(rmv2.?.value == 41);
1781 try testing.expect(map.fetchOrderedRemove(100) == null);
1782 try testing.expect(map.orderedRemove(100) == false);
1783 try testing.expect(map.getEntry(100) == null);
1784 try testing.expect(map.get(100) == null);
1785 const gop6 = try map.getOrPut(gpa, 5);
1786 try testing.expect(gop6.found_existing == true);
1787 try testing.expect(gop6.value_ptr.* == 77);
1788 try testing.expect(gop6.index == 3);
1789
1790 try testing.expect(map.swapRemove(3));
1791}
1792
1793test "iterator hash map" {
1794 const gpa = testing.allocator;
1795
1796 var reset_map: Auto(i32, i32) = .empty;
1797 defer reset_map.deinit(gpa);
1798
1799 // test ensureTotalCapacity with a 0 parameter
1800 try reset_map.ensureTotalCapacity(gpa, 0);
1801
1802 try reset_map.putNoClobber(gpa, 0, 11);
1803 try reset_map.putNoClobber(gpa, 1, 22);
1804 try reset_map.putNoClobber(gpa, 2, 33);
1805
1806 const keys = [_]i32{
1807 0, 2, 1,
1808 };
1809
1810 const values = [_]i32{
1811 11, 33, 22,
1812 };
1813
1814 var buffer = [_]i32{
1815 0, 0, 0,
1816 };
1817
1818 var it = reset_map.iterator();
1819 const first_entry = it.next().?;
1820 it.reset();
1821
1822 var count: usize = 0;
1823 while (it.next()) |entry| : (count += 1) {
1824 buffer[@as(usize, @intCast(entry.key_ptr.*))] = entry.value_ptr.*;
1825 }
1826 try testing.expect(count == 3);
1827 try testing.expect(it.next() == null);
1828
1829 for (buffer, 0..) |_, i| {
1830 try testing.expect(buffer[@as(usize, @intCast(keys[i]))] == values[i]);
1831 }
1832
1833 it.reset();
1834 count = 0;
1835 while (it.next()) |entry| {
1836 buffer[@as(usize, @intCast(entry.key_ptr.*))] = entry.value_ptr.*;
1837 count += 1;
1838 if (count >= 2) break;
1839 }
1840
1841 for (buffer[0..2], 0..) |_, i| {
1842 try testing.expect(buffer[@as(usize, @intCast(keys[i]))] == values[i]);
1843 }
1844
1845 it.reset();
1846 const entry = it.next().?;
1847 try testing.expect(entry.key_ptr.* == first_entry.key_ptr.*);
1848 try testing.expect(entry.value_ptr.* == first_entry.value_ptr.*);
1849}
1850
1851test "ensure capacity" {
1852 const gpa = testing.allocator;
1853
1854 var map: Auto(i32, i32) = .empty;
1855 defer map.deinit(gpa);
1856
1857 try map.ensureTotalCapacity(gpa, 20);
1858 const initial_capacity = map.capacity();
1859 try testing.expect(initial_capacity >= 20);
1860 var i: i32 = 0;
1861 while (i < 20) : (i += 1) {
1862 try testing.expect(map.fetchPutAssumeCapacity(i, i + 10) == null);
1863 }
1864 // shouldn't resize from putAssumeCapacity
1865 try testing.expect(initial_capacity == map.capacity());
1866}
1867
1868test "ensure capacity leak" {
1869 try testing.checkAllAllocationFailures(std.testing.allocator, struct {
1870 pub fn f(allocator: Allocator) !void {
1871 var map: Auto(i32, i32) = .empty;
1872 defer map.deinit(allocator);
1873
1874 var i: i32 = 0;
1875 // put more than `linear_scan_max` in so index_header gets allocated.
1876 while (i <= 20) : (i += 1) try map.put(allocator, i, i);
1877 }
1878 }.f, .{});
1879}
1880
1881test "big map" {
1882 const gpa = testing.allocator;
1883
1884 var map: Auto(i32, i32) = .empty;
1885 defer map.deinit(gpa);
1886
1887 var i: i32 = 0;
1888 while (i < 8) : (i += 1) {
1889 try map.put(gpa, i, i + 10);
1890 }
1891
1892 i = 0;
1893 while (i < 8) : (i += 1) {
1894 try testing.expectEqual(@as(?i32, i + 10), map.get(i));
1895 }
1896 while (i < 16) : (i += 1) {
1897 try testing.expectEqual(@as(?i32, null), map.get(i));
1898 }
1899
1900 i = 4;
1901 while (i < 12) : (i += 1) {
1902 try map.put(gpa, i, i + 12);
1903 }
1904
1905 i = 0;
1906 while (i < 4) : (i += 1) {
1907 try testing.expectEqual(@as(?i32, i + 10), map.get(i));
1908 }
1909 while (i < 12) : (i += 1) {
1910 try testing.expectEqual(@as(?i32, i + 12), map.get(i));
1911 }
1912 while (i < 16) : (i += 1) {
1913 try testing.expectEqual(@as(?i32, null), map.get(i));
1914 }
1915
1916 i = 0;
1917 while (i < 4) : (i += 1) {
1918 try testing.expect(map.orderedRemove(i));
1919 }
1920 while (i < 8) : (i += 1) {
1921 try testing.expect(map.swapRemove(i));
1922 }
1923
1924 i = 0;
1925 while (i < 8) : (i += 1) {
1926 try testing.expectEqual(@as(?i32, null), map.get(i));
1927 }
1928 while (i < 12) : (i += 1) {
1929 try testing.expectEqual(@as(?i32, i + 12), map.get(i));
1930 }
1931 while (i < 16) : (i += 1) {
1932 try testing.expectEqual(@as(?i32, null), map.get(i));
1933 }
1934}
1935
1936test "clone" {
1937 const gpa = testing.allocator;
1938
1939 var original: Auto(i32, i32) = .empty;
1940 defer original.deinit(gpa);
1941
1942 // put more than `linear_scan_max` so we can test that the index header is properly cloned
1943 var i: u8 = 0;
1944 while (i < 10) : (i += 1) {
1945 try original.putNoClobber(gpa, i, i * 10);
1946 }
1947
1948 var copy = try original.clone(gpa);
1949 defer copy.deinit(gpa);
1950
1951 i = 0;
1952 while (i < 10) : (i += 1) {
1953 try testing.expect(original.get(i).? == i * 10);
1954 try testing.expect(copy.get(i).? == i * 10);
1955 try testing.expect(original.getPtr(i).? != copy.getPtr(i).?);
1956 }
1957
1958 while (i < 20) : (i += 1) {
1959 try testing.expect(original.get(i) == null);
1960 try testing.expect(copy.get(i) == null);
1961 }
1962}
1963
1964test "shrink" {
1965 const gpa = testing.allocator;
1966
1967 var map: Auto(i32, i32) = .empty;
1968 defer map.deinit(gpa);
1969
1970 // This test is more interesting if we insert enough entries to allocate the index header.
1971 const num_entries = 200;
1972 var i: i32 = 0;
1973 while (i < num_entries) : (i += 1)
1974 try testing.expect((try map.fetchPut(gpa, i, i * 10)) == null);
1975
1976 try testing.expect(map.index_header != null);
1977 try testing.expect(map.count() == num_entries);
1978
1979 // Test `shrinkRetainingCapacity`.
1980 map.shrinkRetainingCapacity(17);
1981 try testing.expect(map.count() == 17);
1982 try testing.expect(map.capacity() >= num_entries);
1983 i = 0;
1984 while (i < num_entries) : (i += 1) {
1985 const gop = try map.getOrPut(gpa, i);
1986 if (i < 17) {
1987 try testing.expect(gop.found_existing == true);
1988 try testing.expect(gop.value_ptr.* == i * 10);
1989 } else try testing.expect(gop.found_existing == false);
1990 }
1991
1992 // Test `shrinkAndFree`.
1993 map.shrinkAndFree(gpa, 15);
1994 try testing.expect(map.count() == 15);
1995 try testing.expect(map.capacity() == 15);
1996 i = 0;
1997 while (i < num_entries) : (i += 1) {
1998 const gop = try map.getOrPut(gpa, i);
1999 if (i < 15) {
2000 try testing.expect(gop.found_existing == true);
2001 try testing.expect(gop.value_ptr.* == i * 10);
2002 } else try testing.expect(gop.found_existing == false);
2003 }
2004}
2005
2006test "pop()" {
2007 const gpa = testing.allocator;
2008
2009 var map: Auto(i32, i32) = .empty;
2010 defer map.deinit(gpa);
2011
2012 // Insert just enough entries so that the map expands. Afterwards,
2013 // pop all entries out of the map.
2014
2015 var i: i32 = 0;
2016 while (i < 9) : (i += 1) {
2017 try testing.expect((try map.fetchPut(gpa, i, i)) == null);
2018 }
2019
2020 while (map.pop()) |pop| {
2021 try testing.expect(pop.key == i - 1 and pop.value == i - 1);
2022 i -= 1;
2023 }
2024
2025 try testing.expect(map.count() == 0);
2026}
2027
2028test "reIndex" {
2029 const gpa = testing.allocator;
2030
2031 var map: Custom(i32, i32, AutoContext(i32), true) = .empty;
2032 defer map.deinit(gpa);
2033
2034 // Populate via the API.
2035 const num_indexed_entries = 200;
2036 var i: i32 = 0;
2037 while (i < num_indexed_entries) : (i += 1)
2038 try testing.expect((try map.fetchPut(gpa, i, i * 10)) == null);
2039
2040 // Make sure we allocated an index header.
2041 try testing.expect(map.index_header != null);
2042
2043 // Now write to the arrays directly.
2044 const num_unindexed_entries = 20;
2045 try map.entries.resize(std.testing.allocator, num_indexed_entries + num_unindexed_entries);
2046 for (map.keys()[num_indexed_entries..], map.values()[num_indexed_entries..], num_indexed_entries..) |*key, *value, j| {
2047 key.* = @intCast(j);
2048 value.* = @intCast(j * 10);
2049 }
2050
2051 // After reindexing, we should see everything.
2052 try map.reIndex(gpa);
2053 i = 0;
2054 while (i < num_indexed_entries + num_unindexed_entries) : (i += 1) {
2055 const gop = try map.getOrPut(gpa, i);
2056 try testing.expect(gop.found_existing == true);
2057 try testing.expect(gop.value_ptr.* == i * 10);
2058 try testing.expect(gop.index == i);
2059 }
2060}
2061
2062test "auto store_hash" {
2063 const HasCheapEql = Auto(i32, i32);
2064 const HasExpensiveEql = Auto([32]i32, i32);
2065 try testing.expect(@FieldType(HasCheapEql.Data, "hash") == void);
2066 try testing.expect(@FieldType(HasExpensiveEql.Data, "hash") != void);
2067}
2068
2069test "sort" {
2070 const gpa = testing.allocator;
2071
2072 var map: Auto(i32, i32) = .empty;
2073 defer map.deinit(gpa);
2074
2075 for ([_]i32{ 8, 3, 12, 10, 2, 4, 9, 5, 6, 13, 14, 15, 16, 1, 11, 17, 7 }) |x| {
2076 try map.put(gpa, x, x * 3);
2077 }
2078
2079 const C = struct {
2080 keys: []i32,
2081
2082 pub fn lessThan(ctx: @This(), a_index: usize, b_index: usize) bool {
2083 return ctx.keys[a_index] < ctx.keys[b_index];
2084 }
2085 };
2086
2087 map.sort(C{ .keys = map.keys() });
2088
2089 var x: i32 = 1;
2090 for (map.keys(), 0..) |key, i| {
2091 try testing.expect(key == x);
2092 try testing.expect(map.values()[i] == x * 3);
2093 x += 1;
2094 }
2095}
2096
2097test "0 sized key" {
2098 const gpa = testing.allocator;
2099
2100 var map: Auto(u0, i32) = .empty;
2101 defer map.deinit(gpa);
2102
2103 try testing.expectEqual(map.get(0), null);
2104
2105 try map.put(gpa, 0, 5);
2106 try testing.expectEqual(map.get(0), 5);
2107
2108 try map.put(gpa, 0, 10);
2109 try testing.expectEqual(map.get(0), 10);
2110
2111 try testing.expectEqual(map.swapRemove(0), true);
2112 try testing.expectEqual(map.get(0), null);
2113}
2114
2115test "0 sized key and 0 sized value" {
2116 const gpa = testing.allocator;
2117
2118 var map: Auto(u0, u0) = .empty;
2119 defer map.deinit(gpa);
2120
2121 try testing.expectEqual(map.get(0), null);
2122
2123 try map.put(gpa, 0, 0);
2124 try testing.expectEqual(map.get(0), 0);
2125
2126 try testing.expectEqual(map.swapRemove(0), true);
2127 try testing.expectEqual(map.get(0), null);
2128}
2129
2130test "setKey storehash true" {
2131 const gpa = std.testing.allocator;
2132
2133 var map: Custom(i32, i32, AutoContext(i32), true) = .empty;
2134 defer map.deinit(gpa);
2135
2136 try map.put(gpa, 12, 34);
2137 try map.put(gpa, 56, 78);
2138
2139 map.setKey(0, 42);
2140 try testing.expectEqual(2, map.count());
2141 try testing.expectEqual(false, map.contains(12));
2142 try testing.expectEqual(34, map.get(42));
2143 try testing.expectEqual(78, map.get(56));
2144}
2145
2146test "setKey storehash false" {
2147 const gpa = std.testing.allocator;
2148
2149 var map: Custom(i32, i32, AutoContext(i32), false) = .empty;
2150 defer map.deinit(gpa);
2151
2152 try map.put(gpa, 12, 34);
2153 try map.put(gpa, 56, 78);
2154
2155 map.setKey(0, 42);
2156 try testing.expectEqual(2, map.count());
2157 try testing.expectEqual(false, map.contains(12));
2158 try testing.expectEqual(34, map.get(42));
2159 try testing.expectEqual(78, map.get(56));
2160}
2161
2162test "setKey storehash false with index" {
2163 const gpa = std.testing.allocator;
2164
2165 const T = Custom(usize, usize, AutoContext(usize), false);
2166
2167 var map: T = .empty;
2168 defer map.deinit(gpa);
2169
2170 for (0..T.linear_scan_max + 1) |i| try map.put(gpa, i, i);
2171
2172 map.setKey(0, 42);
2173 try testing.expectEqual(T.linear_scan_max + 1, map.count());
2174 try testing.expectEqual(false, map.contains(0));
2175 try testing.expectEqual(0, map.get(42));
2176
2177 for (1..T.linear_scan_max + 1) |i| try testing.expectEqual(i, map.get(i));
2178}
2179
2180test "setKey storehash true with index" {
2181 const gpa = std.testing.allocator;
2182
2183 const T = Custom(usize, usize, AutoContext(usize), false);
2184
2185 var map: Custom(usize, usize, AutoContext(usize), true) = .empty;
2186 defer map.deinit(gpa);
2187
2188 for (0..T.linear_scan_max + 1) |i| try map.put(gpa, i, i);
2189
2190 map.setKey(0, 42);
2191 try testing.expectEqual(T.linear_scan_max + 1, map.count());
2192 try testing.expectEqual(false, map.contains(0));
2193 try testing.expectEqual(0, map.get(42));
2194
2195 for (1..T.linear_scan_max + 1) |i| try testing.expectEqual(i, map.get(i));
2196}
2197
2198pub fn getHashPtrAddrFn(comptime K: type, comptime Context: type) (fn (Context, K) u32) {
2199 return struct {
2200 fn hash(ctx: Context, key: K) u32 {
2201 _ = ctx;
2202 return getAutoHashFn(usize, void)({}, @intFromPtr(key));
2203 }
2204 }.hash;
2205}
2206
2207pub fn getTrivialEqlFn(comptime K: type, comptime Context: type) (fn (Context, K, K) bool) {
2208 return struct {
2209 fn eql(ctx: Context, a: K, b: K) bool {
2210 _ = ctx;
2211 return a == b;
2212 }
2213 }.eql;
2214}
2215
2216pub fn AutoContext(comptime K: type) type {
2217 return struct {
2218 pub const hash = getAutoHashFn(K, @This());
2219 pub const eql = getAutoEqlFn(K, @This());
2220 };
2221}
2222
2223pub fn getAutoHashFn(comptime K: type, comptime Context: type) (fn (Context, K) u32) {
2224 return struct {
2225 fn hash(ctx: Context, key: K) u32 {
2226 _ = ctx;
2227 if (std.meta.hasUniqueRepresentation(K)) {
2228 return @truncate(Wyhash.hash(0, std.mem.asBytes(&key)));
2229 } else {
2230 var hasher = Wyhash.init(0);
2231 autoHash(&hasher, key);
2232 return @truncate(hasher.final());
2233 }
2234 }
2235 }.hash;
2236}
2237
2238pub fn getAutoEqlFn(comptime K: type, comptime Context: type) (fn (Context, K, K, usize) bool) {
2239 return struct {
2240 fn eql(ctx: Context, a: K, b: K, b_index: usize) bool {
2241 _ = b_index;
2242 _ = ctx;
2243 return std.meta.eql(a, b);
2244 }
2245 }.eql;
2246}
2247
2248pub fn autoEqlIsCheap(comptime K: type) bool {
2249 return switch (@typeInfo(K)) {
2250 .bool,
2251 .int,
2252 .float,
2253 .pointer,
2254 .comptime_float,
2255 .comptime_int,
2256 .@"enum",
2257 .@"fn",
2258 .error_set,
2259 .@"anyframe",
2260 .enum_literal,
2261 => true,
2262 else => false,
2263 };
2264}
2265
2266pub fn getAutoHashStratFn(comptime K: type, comptime Context: type, comptime strategy: std.hash.Strategy) (fn (Context, K) u32) {
2267 return struct {
2268 fn hash(ctx: Context, key: K) u32 {
2269 _ = ctx;
2270 var hasher = Wyhash.init(0);
2271 std.hash.autoHashStrat(&hasher, key, strategy);
2272 return @as(u32, @truncate(hasher.final()));
2273 }
2274 }.hash;
2275}
2276
2277test "orderedRemoveAtMany" {
2278 const gpa = testing.allocator;
2279
2280 var map: Auto(usize, void) = .empty;
2281 defer map.deinit(gpa);
2282
2283 for (0..10) |n| {
2284 try map.put(gpa, n, {});
2285 }
2286
2287 try map.orderedRemoveAtMany(gpa, &.{ 1, 5, 5, 7, 9 });
2288 try testing.expectEqualSlices(usize, &.{ 0, 2, 3, 4, 6, 8 }, map.keys());
2289
2290 try map.orderedRemoveAtMany(gpa, &.{0});
2291 try testing.expectEqualSlices(usize, &.{ 2, 3, 4, 6, 8 }, map.keys());
2292
2293 try map.orderedRemoveAtMany(gpa, &.{});
2294 try testing.expectEqualSlices(usize, &.{ 2, 3, 4, 6, 8 }, map.keys());
2295
2296 try map.orderedRemoveAtMany(gpa, &.{ 1, 2, 3, 4 });
2297 try testing.expectEqualSlices(usize, &.{2}, map.keys());
2298
2299 try map.orderedRemoveAtMany(gpa, &.{0});
2300 try testing.expectEqualSlices(usize, &.{}, map.keys());
2301}