1const std = @import("std.zig");
2const builtin = @import("builtin");
3const assert = std.debug.assert;
4const autoHash = std.hash.autoHash;
5const math = std.math;
6const mem = std.mem;
7const Allocator = mem.Allocator;
8const Wyhash = std.hash.Wyhash;
9const Alignment = std.mem.Alignment;
10
11pub fn getAutoHashFn(comptime K: type, comptime Context: type) (fn (Context, K) u64) {
12 comptime {
13 assert(@hasDecl(std, "StringHashMap")); // detect when the following message needs updated
14 if (K == []const u8) {
15 @compileError("std.hash.autoHash does not allow slices here (" ++
16 @typeName(K) ++
17 ") because the intent is unclear. " ++
18 "Consider using std.StringHashMap for hashing the contents of []const u8. " ++
19 "Alternatively, consider using std.hash.autoHashStrat or providing your own hash function instead.");
20 }
21 }
22
23 return struct {
24 fn hash(ctx: Context, key: K) u64 {
25 _ = ctx;
26 if (std.meta.hasUniqueRepresentation(K)) {
27 return Wyhash.hash(0, std.mem.asBytes(&key));
28 } else {
29 var hasher = Wyhash.init(0);
30 autoHash(&hasher, key);
31 return hasher.final();
32 }
33 }
34 }.hash;
35}
36
37pub fn getAutoEqlFn(comptime K: type, comptime Context: type) (fn (Context, K, K) bool) {
38 return struct {
39 fn eql(ctx: Context, a: K, b: K) bool {
40 _ = ctx;
41 return std.meta.eql(a, b);
42 }
43 }.eql;
44}
45
46pub fn AutoHashMap(comptime K: type, comptime V: type) type {
47 return HashMap(K, V, AutoContext(K), default_max_load_percentage);
48}
49
50pub fn AutoHashMapUnmanaged(comptime K: type, comptime V: type) type {
51 return HashMapUnmanaged(K, V, AutoContext(K), default_max_load_percentage);
52}
53
54pub fn AutoContext(comptime K: type) type {
55 return struct {
56 pub const hash = getAutoHashFn(K, @This());
57 pub const eql = getAutoEqlFn(K, @This());
58 };
59}
60
61/// Builtin hashmap for strings as keys.
62/// Key memory is managed by the caller. Keys and values
63/// will not automatically be freed.
64pub fn StringHashMap(comptime V: type) type {
65 return HashMap([]const u8, V, StringContext, default_max_load_percentage);
66}
67
68/// Key memory is managed by the caller. Keys and values
69/// will not automatically be freed.
70pub fn StringHashMapUnmanaged(comptime V: type) type {
71 return HashMapUnmanaged([]const u8, V, StringContext, default_max_load_percentage);
72}
73
74pub const StringContext = struct {
75 pub fn hash(self: @This(), s: []const u8) u64 {
76 _ = self;
77 return hashString(s);
78 }
79 pub fn eql(self: @This(), a: []const u8, b: []const u8) bool {
80 _ = self;
81 return eqlString(a, b);
82 }
83};
84
85pub fn eqlString(a: []const u8, b: []const u8) bool {
86 return mem.eql(u8, a, b);
87}
88
89pub fn hashString(s: []const u8) u64 {
90 return std.hash.Wyhash.hash(0, s);
91}
92
93pub const StringIndexContext = struct {
94 bytes: *const std.ArrayList(u8),
95
96 pub fn eql(_: @This(), a: u32, b: u32) bool {
97 return a == b;
98 }
99
100 pub fn hash(ctx: @This(), key: u32) u64 {
101 return hashString(mem.sliceTo(ctx.bytes.items[key..], 0));
102 }
103};
104
105pub const StringIndexAdapter = struct {
106 bytes: *const std.ArrayList(u8),
107
108 pub fn eql(ctx: @This(), a: []const u8, b: u32) bool {
109 return mem.eql(u8, a, mem.sliceTo(ctx.bytes.items[b..], 0));
110 }
111
112 pub fn hash(_: @This(), adapted_key: []const u8) u64 {
113 assert(mem.findScalar(u8, adapted_key, 0) == null);
114 return hashString(adapted_key);
115 }
116};
117
118pub const default_max_load_percentage = 80;
119
120/// General purpose hash table.
121/// No order is guaranteed and any modification invalidates live iterators.
122/// It provides fast operations (lookup, insertion, deletion) with quite high
123/// load factors (up to 80% by default) for low memory usage.
124/// For a hash map that can be initialized directly that does not store an Allocator
125/// field, see `HashMapUnmanaged`.
126/// If iterating over the table entries is a strong usecase and needs to be fast,
127/// prefer the alternative `std.ArrayHashMap`.
128/// Context must be a struct type with two member functions:
129/// hash(self, K) u64
130/// eql(self, K, K) bool
131/// Adapted variants of many functions are provided. These variants
132/// take a pseudo key instead of a key. Their context must have the functions:
133/// hash(self, PseudoKey) u64
134/// eql(self, PseudoKey, K) bool
135pub fn HashMap(
136 comptime K: type,
137 comptime V: type,
138 comptime Context: type,
139 comptime max_load_percentage: u64,
140) type {
141 return struct {
142 unmanaged: Unmanaged,
143 allocator: Allocator,
144 ctx: Context,
145
146 /// The type of the unmanaged hash map underlying this wrapper
147 pub const Unmanaged = HashMapUnmanaged(K, V, Context, max_load_percentage);
148 /// An entry, containing pointers to a key and value stored in the map
149 pub const Entry = Unmanaged.Entry;
150 /// A copy of a key and value which are no longer in the map
151 pub const KV = Unmanaged.KV;
152 /// The integer type that is the result of hashing
153 pub const Hash = Unmanaged.Hash;
154 /// The iterator type returned by iterator()
155 pub const Iterator = Unmanaged.Iterator;
156
157 pub const KeyIterator = Unmanaged.KeyIterator;
158 pub const ValueIterator = Unmanaged.ValueIterator;
159
160 /// The integer type used to store the size of the map
161 pub const Size = Unmanaged.Size;
162 /// The type returned from getOrPut and variants
163 pub const GetOrPutResult = Unmanaged.GetOrPutResult;
164
165 const Self = @This();
166
167 /// Create a managed hash map with an empty context.
168 /// If the context is not zero-sized, you must use
169 /// initContext(allocator, ctx) instead.
170 pub fn init(allocator: Allocator) Self {
171 if (@sizeOf(Context) != 0) {
172 @compileError("Context must be specified! Call initContext(allocator, ctx) instead.");
173 }
174 return .{
175 .unmanaged = .empty,
176 .allocator = allocator,
177 .ctx = undefined, // ctx is zero-sized so this is safe.
178 };
179 }
180
181 /// Create a managed hash map with a context
182 pub fn initContext(allocator: Allocator, ctx: Context) Self {
183 return .{
184 .unmanaged = .empty,
185 .allocator = allocator,
186 .ctx = ctx,
187 };
188 }
189
190 /// Puts the hash map into a state where any method call that would
191 /// cause an existing key or value pointer to become invalidated will
192 /// instead trigger an assertion.
193 ///
194 /// An additional call to `lockPointers` in such state also triggers an
195 /// assertion.
196 ///
197 /// `unlockPointers` returns the hash map to the previous state.
198 pub fn lockPointers(self: *Self) void {
199 self.unmanaged.lockPointers();
200 }
201
202 /// Undoes a call to `lockPointers`.
203 pub fn unlockPointers(self: *Self) void {
204 self.unmanaged.unlockPointers();
205 }
206
207 /// Release the backing array and invalidate this map.
208 /// This does *not* deinit keys, values, or the context!
209 /// If your keys or values need to be released, ensure
210 /// that that is done before calling this function.
211 pub fn deinit(self: *Self) void {
212 self.unmanaged.deinit(self.allocator);
213 self.* = undefined;
214 }
215
216 /// Empty the map, but keep the backing allocation for future use.
217 /// This does *not* free keys or values! Be sure to
218 /// release them if they need deinitialization before
219 /// calling this function.
220 pub fn clearRetainingCapacity(self: *Self) void {
221 return self.unmanaged.clearRetainingCapacity();
222 }
223
224 /// Empty the map and release the backing allocation.
225 /// This does *not* free keys or values! Be sure to
226 /// release them if they need deinitialization before
227 /// calling this function.
228 pub fn clearAndFree(self: *Self) void {
229 return self.unmanaged.clearAndFree(self.allocator);
230 }
231
232 /// Return the number of items in the map.
233 pub fn count(self: Self) Size {
234 return self.unmanaged.count();
235 }
236
237 /// Create an iterator over the entries in the map.
238 /// The iterator is invalidated if the map is modified.
239 pub fn iterator(self: *const Self) Iterator {
240 return self.unmanaged.iterator();
241 }
242
243 /// Create an iterator over the keys in the map.
244 /// The iterator is invalidated if the map is modified.
245 pub fn keyIterator(self: Self) KeyIterator {
246 return self.unmanaged.keyIterator();
247 }
248
249 /// Create an iterator over the values in the map.
250 /// The iterator is invalidated if the map is modified.
251 pub fn valueIterator(self: Self) ValueIterator {
252 return self.unmanaged.valueIterator();
253 }
254
255 /// If key exists this function cannot fail.
256 /// If there is an existing item with `key`, then the result's
257 /// `Entry` pointers point to it, and found_existing is true.
258 /// Otherwise, puts a new item with undefined value, and
259 /// the `Entry` pointers point to it. Caller should then initialize
260 /// the value (but not the key).
261 pub fn getOrPut(self: *Self, key: K) Allocator.Error!GetOrPutResult {
262 return self.unmanaged.getOrPutContext(self.allocator, key, self.ctx);
263 }
264
265 /// If key exists this function cannot fail.
266 /// If there is an existing item with `key`, then the result's
267 /// `Entry` pointers point to it, and found_existing is true.
268 /// Otherwise, puts a new item with undefined key and value, and
269 /// the `Entry` pointers point to it. Caller must then initialize
270 /// the key and value.
271 pub fn getOrPutAdapted(self: *Self, key: anytype, ctx: anytype) Allocator.Error!GetOrPutResult {
272 return self.unmanaged.getOrPutContextAdapted(self.allocator, key, ctx, self.ctx);
273 }
274
275 /// If there is an existing item with `key`, then the result's
276 /// `Entry` pointers point to it, and found_existing is true.
277 /// Otherwise, puts a new item with undefined value, and
278 /// the `Entry` pointers point to it. Caller should then initialize
279 /// the value (but not the key).
280 /// If a new entry needs to be stored, this function asserts there
281 /// is enough capacity to store it.
282 pub fn getOrPutAssumeCapacity(self: *Self, key: K) GetOrPutResult {
283 return self.unmanaged.getOrPutAssumeCapacityContext(key, self.ctx);
284 }
285
286 /// If there is an existing item with `key`, then the result's
287 /// `Entry` pointers point to it, and found_existing is true.
288 /// Otherwise, puts a new item with undefined value, and
289 /// the `Entry` pointers point to it. Caller must then initialize
290 /// the key and value.
291 /// If a new entry needs to be stored, this function asserts there
292 /// is enough capacity to store it.
293 pub fn getOrPutAssumeCapacityAdapted(self: *Self, key: anytype, ctx: anytype) GetOrPutResult {
294 return self.unmanaged.getOrPutAssumeCapacityAdapted(key, ctx);
295 }
296
297 pub fn getOrPutValue(self: *Self, key: K, value: V) Allocator.Error!Entry {
298 return self.unmanaged.getOrPutValueContext(self.allocator, key, value, self.ctx);
299 }
300
301 /// Increases capacity, guaranteeing that insertions up until the
302 /// `expected_count` will not cause an allocation, and therefore cannot fail.
303 pub fn ensureTotalCapacity(self: *Self, expected_count: Size) Allocator.Error!void {
304 return self.unmanaged.ensureTotalCapacityContext(self.allocator, expected_count, self.ctx);
305 }
306
307 /// Increases capacity, guaranteeing that insertions up until
308 /// `additional_count` **more** items will not cause an allocation, and
309 /// therefore cannot fail.
310 pub fn ensureUnusedCapacity(self: *Self, additional_count: Size) Allocator.Error!void {
311 return self.unmanaged.ensureUnusedCapacityContext(self.allocator, additional_count, self.ctx);
312 }
313
314 /// Returns the number of total elements which may be present before it is
315 /// no longer guaranteed that no allocations will be performed.
316 pub fn capacity(self: Self) Size {
317 return self.unmanaged.capacity();
318 }
319
320 /// Clobbers any existing data. To detect if a put would clobber
321 /// existing data, see `getOrPut`.
322 pub fn put(self: *Self, key: K, value: V) Allocator.Error!void {
323 return self.unmanaged.putContext(self.allocator, key, value, self.ctx);
324 }
325
326 /// Inserts a key-value pair into the hash map, asserting that no previous
327 /// entry with the same key is already present
328 pub fn putNoClobber(self: *Self, key: K, value: V) Allocator.Error!void {
329 return self.unmanaged.putNoClobberContext(self.allocator, key, value, self.ctx);
330 }
331
332 /// Asserts there is enough capacity to store the new key-value pair.
333 /// Clobbers any existing data. To detect if a put would clobber
334 /// existing data, see `getOrPutAssumeCapacity`.
335 pub fn putAssumeCapacity(self: *Self, key: K, value: V) void {
336 return self.unmanaged.putAssumeCapacityContext(key, value, self.ctx);
337 }
338
339 /// Asserts there is enough capacity to store the new key-value pair.
340 /// Asserts that it does not clobber any existing data.
341 /// To detect if a put would clobber existing data, see `getOrPutAssumeCapacity`.
342 pub fn putAssumeCapacityNoClobber(self: *Self, key: K, value: V) void {
343 return self.unmanaged.putAssumeCapacityNoClobberContext(key, value, self.ctx);
344 }
345
346 /// Inserts a new `Entry` into the hash map, returning the previous one, if any.
347 pub fn fetchPut(self: *Self, key: K, value: V) Allocator.Error!?KV {
348 return self.unmanaged.fetchPutContext(self.allocator, key, value, self.ctx);
349 }
350
351 /// Inserts a new `Entry` into the hash map, returning the previous one, if any.
352 /// If insertion happens, asserts there is enough capacity without allocating.
353 pub fn fetchPutAssumeCapacity(self: *Self, key: K, value: V) ?KV {
354 return self.unmanaged.fetchPutAssumeCapacityContext(key, value, self.ctx);
355 }
356
357 /// Removes a value from the map and returns the removed kv pair.
358 pub fn fetchRemove(self: *Self, key: K) ?KV {
359 return self.unmanaged.fetchRemoveContext(key, self.ctx);
360 }
361
362 pub fn fetchRemoveAdapted(self: *Self, key: anytype, ctx: anytype) ?KV {
363 return self.unmanaged.fetchRemoveAdapted(key, ctx);
364 }
365
366 /// Finds the value associated with a key in the map
367 pub fn get(self: Self, key: K) ?V {
368 return self.unmanaged.getContext(key, self.ctx);
369 }
370 pub fn getAdapted(self: Self, key: anytype, ctx: anytype) ?V {
371 return self.unmanaged.getAdapted(key, ctx);
372 }
373
374 pub fn getPtr(self: Self, key: K) ?*V {
375 return self.unmanaged.getPtrContext(key, self.ctx);
376 }
377 pub fn getPtrAdapted(self: Self, key: anytype, ctx: anytype) ?*V {
378 return self.unmanaged.getPtrAdapted(key, ctx);
379 }
380
381 /// Finds the actual key associated with an adapted key in the map
382 pub fn getKey(self: Self, key: K) ?K {
383 return self.unmanaged.getKeyContext(key, self.ctx);
384 }
385 pub fn getKeyAdapted(self: Self, key: anytype, ctx: anytype) ?K {
386 return self.unmanaged.getKeyAdapted(key, ctx);
387 }
388
389 pub fn getKeyPtr(self: Self, key: K) ?*K {
390 return self.unmanaged.getKeyPtrContext(key, self.ctx);
391 }
392 pub fn getKeyPtrAdapted(self: Self, key: anytype, ctx: anytype) ?*K {
393 return self.unmanaged.getKeyPtrAdapted(key, ctx);
394 }
395
396 /// Finds the key and value associated with a key in the map
397 pub fn getEntry(self: Self, key: K) ?Entry {
398 return self.unmanaged.getEntryContext(key, self.ctx);
399 }
400
401 pub fn getEntryAdapted(self: Self, key: anytype, ctx: anytype) ?Entry {
402 return self.unmanaged.getEntryAdapted(key, ctx);
403 }
404
405 /// Check if the map contains a key
406 pub fn contains(self: Self, key: K) bool {
407 return self.unmanaged.containsContext(key, self.ctx);
408 }
409
410 pub fn containsAdapted(self: Self, key: anytype, ctx: anytype) bool {
411 return self.unmanaged.containsAdapted(key, ctx);
412 }
413
414 /// If there is an `Entry` with a matching key, it is deleted from
415 /// the hash map, and this function returns true. Otherwise this
416 /// function returns false.
417 ///
418 /// TODO: answer the question in these doc comments, does this
419 /// increase the unused capacity by one?
420 pub fn remove(self: *Self, key: K) bool {
421 return self.unmanaged.removeContext(key, self.ctx);
422 }
423
424 /// TODO: answer the question in these doc comments, does this
425 /// increase the unused capacity by one?
426 pub fn removeAdapted(self: *Self, key: anytype, ctx: anytype) bool {
427 return self.unmanaged.removeAdapted(key, ctx);
428 }
429
430 /// Delete the entry with key pointed to by key_ptr from the hash map.
431 /// key_ptr is assumed to be a valid pointer to a key that is present
432 /// in the hash map.
433 ///
434 /// TODO: answer the question in these doc comments, does this
435 /// increase the unused capacity by one?
436 pub fn removeByPtr(self: *Self, key_ptr: *K) void {
437 self.unmanaged.removeByPtr(key_ptr);
438 }
439
440 /// Creates a copy of this map, using the same allocator
441 pub fn clone(self: Self) Allocator.Error!Self {
442 var other = try self.unmanaged.cloneContext(self.allocator, self.ctx);
443 return other.promoteContext(self.allocator, self.ctx);
444 }
445
446 /// Creates a copy of this map, using a specified allocator
447 pub fn cloneWithAllocator(self: Self, new_allocator: Allocator) Allocator.Error!Self {
448 var other = try self.unmanaged.cloneContext(new_allocator, self.ctx);
449 return other.promoteContext(new_allocator, self.ctx);
450 }
451
452 /// Creates a copy of this map, using a specified context
453 pub fn cloneWithContext(self: Self, new_ctx: anytype) Allocator.Error!HashMap(K, V, @TypeOf(new_ctx), max_load_percentage) {
454 var other = try self.unmanaged.cloneContext(self.allocator, new_ctx);
455 return other.promoteContext(self.allocator, new_ctx);
456 }
457
458 /// Creates a copy of this map, using a specified allocator and context.
459 pub fn cloneWithAllocatorAndContext(
460 self: Self,
461 new_allocator: Allocator,
462 new_ctx: anytype,
463 ) Allocator.Error!HashMap(K, V, @TypeOf(new_ctx), max_load_percentage) {
464 var other = try self.unmanaged.cloneContext(new_allocator, new_ctx);
465 return other.promoteContext(new_allocator, new_ctx);
466 }
467
468 /// Set the map to an empty state, making deinitialization a no-op, and
469 /// returning a copy of the original.
470 pub fn move(self: *Self) Self {
471 self.unmanaged.pointer_stability.assertUnlocked();
472 const result = self.*;
473 self.unmanaged = .empty;
474 return result;
475 }
476
477 /// Rehash the map, in-place.
478 ///
479 /// Over time, due to the current tombstone-based implementation, a
480 /// HashMap could become fragmented due to the buildup of tombstone
481 /// entries that causes a performance degradation due to excessive
482 /// probing. The kind of pattern that might cause this is a long-lived
483 /// HashMap with repeated inserts and deletes.
484 ///
485 /// After this function is called, there will be no tombstones in
486 /// the HashMap, each of the entries is rehashed and any existing
487 /// key/value pointers into the HashMap are invalidated.
488 pub fn rehash(self: *Self) void {
489 self.unmanaged.rehash(self.ctx);
490 }
491 };
492}
493
494/// A HashMap based on open addressing and linear probing.
495/// A lookup or modification typically incurs only 2 cache misses.
496/// No order is guaranteed and any modification invalidates live iterators.
497/// It achieves good performance with quite high load factors (by default,
498/// grow is triggered at 80% full) and only one byte of overhead per element.
499/// The struct itself is only 16 bytes for a small footprint. This comes at
500/// the price of handling size with u32, which should be reasonable enough
501/// for almost all uses.
502/// Deletions are achieved with tombstones.
503///
504/// Default initialization of this struct is deprecated; use `.empty` instead.
505pub const HashMapUnmanaged = Custom;
506fn Custom(
507 comptime K: type,
508 comptime V: type,
509 comptime Context: type,
510 comptime max_load_percentage: u64,
511) type {
512 if (max_load_percentage <= 0 or max_load_percentage >= 100)
513 @compileError("max_load_percentage must be between 0 and 100.");
514 return struct {
515 const Self = @This();
516
517 // This is actually a midway pointer to the single buffer containing
518 // a `Header` field, the `Metadata`s and `Entry`s.
519 // At `-@sizeOf(Header)` is the Header field.
520 // At `sizeOf(Metadata) * capacity + offset`, which is pointed to by
521 // self.header().entries, is the array of entries.
522 // This means that the hashmap only holds one live allocation, to
523 // reduce memory fragmentation and struct size.
524 /// Pointer to the metadata.
525 metadata: ?[*]Metadata = null,
526
527 /// Current number of elements in the hashmap.
528 size: Size = 0,
529
530 // Having a countdown to grow reduces the number of instructions to
531 // execute when determining if the hashmap has enough capacity already.
532 /// Number of available slots before a grow is needed to satisfy the
533 /// `max_load_percentage`.
534 available: Size = 0,
535
536 /// Used to detect memory safety violations.
537 pointer_stability: std.debug.SafetyLock = .{},
538
539 // This is purely empirical and not a /very smart magic constant™/.
540 /// Capacity of the first grow when bootstrapping the hashmap.
541 const minimal_capacity = 8;
542
543 /// A map containing no keys or values.
544 pub const empty: Self = .{
545 .metadata = null,
546 .size = 0,
547 .available = 0,
548 };
549
550 // This hashmap is specially designed for sizes that fit in a u32.
551 pub const Size = u32;
552
553 // u64 hashes guarantee us that the fingerprint bits will never be used
554 // to compute the index of a slot, maximizing the use of entropy.
555 pub const Hash = u64;
556
557 pub const Entry = struct {
558 key_ptr: *K,
559 value_ptr: *V,
560 };
561
562 pub const KV = struct {
563 key: K,
564 value: V,
565 };
566
567 const Header = struct {
568 values: [*]V,
569 keys: [*]K,
570 capacity: Size,
571 };
572
573 /// Metadata for a slot. It can be in three states: empty, used or
574 /// tombstone. Tombstones indicate that an entry was previously used,
575 /// they are a simple way to handle removal.
576 /// To this state, we add 7 bits from the slot's key hash. These are
577 /// used as a fast way to disambiguate between entries without
578 /// having to use the equality function. If two fingerprints are
579 /// different, we know that we don't have to compare the keys at all.
580 /// The 7 bits are the highest ones from a 64 bit hash. This way, not
581 /// only we use the `log2(capacity)` lowest bits from the hash to determine
582 /// a slot index, but we use 7 more bits to quickly resolve collisions
583 /// when multiple elements with different hashes end up wanting to be in the same slot.
584 /// Not using the equality function means we don't have to read into
585 /// the entries array, likely avoiding a cache miss and a potentially
586 /// costly function call.
587 const Metadata = packed struct {
588 const FingerPrint = u7;
589
590 const free: FingerPrint = 0;
591 const tombstone: FingerPrint = 1;
592
593 fingerprint: FingerPrint = free,
594 used: u1 = 0,
595
596 const slot_free: u8 = @bitCast(Metadata{ .fingerprint = free });
597 const slot_tombstone: u8 = @bitCast(Metadata{ .fingerprint = tombstone });
598
599 pub fn isUsed(self: Metadata) bool {
600 return self.used == 1;
601 }
602
603 pub fn isTombstone(self: Metadata) bool {
604 return @as(u8, @bitCast(self)) == slot_tombstone;
605 }
606
607 pub fn isFree(self: Metadata) bool {
608 return @as(u8, @bitCast(self)) == slot_free;
609 }
610
611 pub fn takeFingerprint(hash: Hash) FingerPrint {
612 const hash_bits = @typeInfo(Hash).int.bits;
613 const fp_bits = @typeInfo(FingerPrint).int.bits;
614 return @as(FingerPrint, @truncate(hash >> (hash_bits - fp_bits)));
615 }
616
617 pub fn fill(self: *Metadata, fp: FingerPrint) void {
618 self.used = 1;
619 self.fingerprint = fp;
620 }
621
622 pub fn remove(self: *Metadata) void {
623 self.used = 0;
624 self.fingerprint = tombstone;
625 }
626 };
627
628 comptime {
629 assert(@sizeOf(Metadata) == 1);
630 assert(@alignOf(Metadata) == 1);
631 }
632
633 pub const Iterator = struct {
634 hm: *const Self,
635 index: Size = 0,
636
637 pub fn next(it: *Iterator) ?Entry {
638 assert(it.index <= it.hm.capacity());
639 if (it.hm.size == 0) return null;
640
641 const cap = it.hm.capacity();
642 const end = it.hm.metadata.? + cap;
643 var metadata = it.hm.metadata.? + it.index;
644
645 while (metadata != end) : ({
646 metadata += 1;
647 it.index += 1;
648 }) {
649 if (metadata[0].isUsed()) {
650 const key = &it.hm.keys()[it.index];
651 const value = &it.hm.values()[it.index];
652 it.index += 1;
653 return Entry{ .key_ptr = key, .value_ptr = value };
654 }
655 }
656
657 return null;
658 }
659 };
660
661 pub const KeyIterator = FieldIterator(K);
662 pub const ValueIterator = FieldIterator(V);
663
664 fn FieldIterator(comptime T: type) type {
665 return struct {
666 len: usize,
667 metadata: [*]const Metadata,
668 items: [*]T,
669
670 pub fn next(self: *@This()) ?*T {
671 while (self.len > 0) {
672 self.len -= 1;
673 const used = self.metadata[0].isUsed();
674 const item = &self.items[0];
675 self.metadata += 1;
676 self.items += 1;
677 if (used) {
678 return item;
679 }
680 }
681 return null;
682 }
683 };
684 }
685
686 pub const GetOrPutResult = struct {
687 key_ptr: *K,
688 value_ptr: *V,
689 found_existing: bool,
690 };
691
692 pub const Managed = HashMap(K, V, Context, max_load_percentage);
693
694 pub fn promote(self: Self, allocator: Allocator) Managed {
695 if (@sizeOf(Context) != 0)
696 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call promoteContext instead.");
697 return promoteContext(self, allocator, undefined);
698 }
699
700 pub fn promoteContext(self: Self, allocator: Allocator, ctx: Context) Managed {
701 return .{
702 .unmanaged = self,
703 .allocator = allocator,
704 .ctx = ctx,
705 };
706 }
707
708 /// Puts the hash map into a state where any method call that would
709 /// cause an existing key or value pointer to become invalidated will
710 /// instead trigger an assertion.
711 ///
712 /// An additional call to `lockPointers` in such state also triggers an
713 /// assertion.
714 ///
715 /// `unlockPointers` returns the hash map to the previous state.
716 pub fn lockPointers(self: *Self) void {
717 self.pointer_stability.lock();
718 }
719
720 /// Undoes a call to `lockPointers`.
721 pub fn unlockPointers(self: *Self) void {
722 self.pointer_stability.unlock();
723 }
724
725 fn isUnderMaxLoadPercentage(size: Size, cap: Size) bool {
726 return size * 100 < max_load_percentage * cap;
727 }
728
729 pub fn deinit(self: *Self, allocator: Allocator) void {
730 self.pointer_stability.assertUnlocked();
731 self.deallocate(allocator);
732 self.* = undefined;
733 }
734
735 fn capacityForSize(size: Size) Size {
736 var new_cap: u32 = @intCast((@as(u64, size) * 100) / max_load_percentage + 1);
737 new_cap = math.ceilPowerOfTwo(u32, new_cap) catch unreachable;
738 return new_cap;
739 }
740
741 pub fn ensureTotalCapacity(self: *Self, allocator: Allocator, new_size: Size) Allocator.Error!void {
742 if (@sizeOf(Context) != 0)
743 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call ensureTotalCapacityContext instead.");
744 return ensureTotalCapacityContext(self, allocator, new_size, undefined);
745 }
746 pub fn ensureTotalCapacityContext(self: *Self, allocator: Allocator, new_size: Size, ctx: Context) Allocator.Error!void {
747 self.pointer_stability.lock();
748 defer self.pointer_stability.unlock();
749 if (new_size > self.size)
750 try self.growIfNeeded(allocator, new_size - self.size, ctx);
751 }
752
753 pub fn ensureUnusedCapacity(self: *Self, allocator: Allocator, additional_size: Size) Allocator.Error!void {
754 if (@sizeOf(Context) != 0)
755 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call ensureUnusedCapacityContext instead.");
756 return ensureUnusedCapacityContext(self, allocator, additional_size, undefined);
757 }
758 pub fn ensureUnusedCapacityContext(self: *Self, allocator: Allocator, additional_size: Size, ctx: Context) Allocator.Error!void {
759 return ensureTotalCapacityContext(self, allocator, self.count() + additional_size, ctx);
760 }
761
762 pub fn clearRetainingCapacity(self: *Self) void {
763 self.pointer_stability.lock();
764 defer self.pointer_stability.unlock();
765 if (self.metadata) |_| {
766 self.initMetadatas();
767 self.size = 0;
768 self.available = @truncate((self.capacity() * max_load_percentage) / 100);
769 }
770 }
771
772 pub fn clearAndFree(self: *Self, allocator: Allocator) void {
773 self.pointer_stability.lock();
774 defer self.pointer_stability.unlock();
775 self.deallocate(allocator);
776 self.size = 0;
777 self.available = 0;
778 }
779
780 pub fn count(self: Self) Size {
781 return self.size;
782 }
783
784 fn header(self: Self) *Header {
785 return @ptrCast(@as([*]Header, @ptrCast(@alignCast(self.metadata.?))) - 1);
786 }
787
788 fn keys(self: Self) [*]K {
789 return self.header().keys;
790 }
791
792 fn values(self: Self) [*]V {
793 return self.header().values;
794 }
795
796 pub fn capacity(self: Self) Size {
797 if (self.metadata == null) return 0;
798
799 return self.header().capacity;
800 }
801
802 pub fn iterator(self: *const Self) Iterator {
803 return .{ .hm = self };
804 }
805
806 pub fn keyIterator(self: Self) KeyIterator {
807 if (self.metadata) |metadata| {
808 return .{
809 .len = self.capacity(),
810 .metadata = metadata,
811 .items = self.keys(),
812 };
813 } else {
814 return .{
815 .len = 0,
816 .metadata = undefined,
817 .items = undefined,
818 };
819 }
820 }
821
822 pub fn valueIterator(self: Self) ValueIterator {
823 if (self.metadata) |metadata| {
824 return .{
825 .len = self.capacity(),
826 .metadata = metadata,
827 .items = self.values(),
828 };
829 } else {
830 return .{
831 .len = 0,
832 .metadata = undefined,
833 .items = undefined,
834 };
835 }
836 }
837
838 /// Insert an entry in the map. Assumes it is not already present.
839 pub fn putNoClobber(self: *Self, allocator: Allocator, key: K, value: V) Allocator.Error!void {
840 if (@sizeOf(Context) != 0)
841 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call putNoClobberContext instead.");
842 return self.putNoClobberContext(allocator, key, value, undefined);
843 }
844 pub fn putNoClobberContext(self: *Self, allocator: Allocator, key: K, value: V, ctx: Context) Allocator.Error!void {
845 {
846 self.pointer_stability.lock();
847 defer self.pointer_stability.unlock();
848 try self.growIfNeeded(allocator, 1, ctx);
849 }
850 self.putAssumeCapacityNoClobberContext(key, value, ctx);
851 }
852
853 /// Asserts there is enough capacity to store the new key-value pair.
854 /// Clobbers any existing data. To detect if a put would clobber
855 /// existing data, see `getOrPutAssumeCapacity`.
856 pub fn putAssumeCapacity(self: *Self, key: K, value: V) void {
857 if (@sizeOf(Context) != 0)
858 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call putAssumeCapacityContext instead.");
859 return self.putAssumeCapacityContext(key, value, undefined);
860 }
861 pub fn putAssumeCapacityContext(self: *Self, key: K, value: V, ctx: Context) void {
862 const gop = self.getOrPutAssumeCapacityContext(key, ctx);
863 gop.value_ptr.* = value;
864 }
865
866 /// Insert an entry in the map. Assumes it is not already present,
867 /// and that no allocation is needed.
868 pub fn putAssumeCapacityNoClobber(self: *Self, key: K, value: V) void {
869 if (@sizeOf(Context) != 0)
870 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call putAssumeCapacityNoClobberContext instead.");
871 return self.putAssumeCapacityNoClobberContext(key, value, undefined);
872 }
873 pub fn putAssumeCapacityNoClobberContext(self: *Self, key: K, value: V, ctx: Context) void {
874 assert(!self.containsContext(key, ctx));
875
876 const hash: Hash = ctx.hash(key);
877 const mask = self.capacity() - 1;
878 var idx: usize = @truncate(hash & mask);
879
880 var metadata = self.metadata.? + idx;
881 while (metadata[0].isUsed()) {
882 idx = (idx + 1) & mask;
883 metadata = self.metadata.? + idx;
884 }
885
886 assert(self.available > 0);
887 self.available -= 1;
888
889 const fingerprint = Metadata.takeFingerprint(hash);
890 metadata[0].fill(fingerprint);
891 self.keys()[idx] = key;
892 self.values()[idx] = value;
893
894 self.size += 1;
895 }
896
897 /// Inserts a new `Entry` into the hash map, returning the previous one, if any.
898 pub fn fetchPut(self: *Self, allocator: Allocator, key: K, value: V) Allocator.Error!?KV {
899 if (@sizeOf(Context) != 0)
900 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call fetchPutContext instead.");
901 return self.fetchPutContext(allocator, key, value, undefined);
902 }
903 pub fn fetchPutContext(self: *Self, allocator: Allocator, key: K, value: V, ctx: Context) Allocator.Error!?KV {
904 const gop = try self.getOrPutContext(allocator, key, ctx);
905 var result: ?KV = null;
906 if (gop.found_existing) {
907 result = KV{
908 .key = gop.key_ptr.*,
909 .value = gop.value_ptr.*,
910 };
911 }
912 gop.value_ptr.* = value;
913 return result;
914 }
915
916 /// Inserts a new `Entry` into the hash map, returning the previous one, if any.
917 /// If insertion happens, asserts there is enough capacity without allocating.
918 pub fn fetchPutAssumeCapacity(self: *Self, key: K, value: V) ?KV {
919 if (@sizeOf(Context) != 0)
920 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call fetchPutAssumeCapacityContext instead.");
921 return self.fetchPutAssumeCapacityContext(key, value, undefined);
922 }
923 pub fn fetchPutAssumeCapacityContext(self: *Self, key: K, value: V, ctx: Context) ?KV {
924 const gop = self.getOrPutAssumeCapacityContext(key, ctx);
925 var result: ?KV = null;
926 if (gop.found_existing) {
927 result = KV{
928 .key = gop.key_ptr.*,
929 .value = gop.value_ptr.*,
930 };
931 }
932 gop.value_ptr.* = value;
933 return result;
934 }
935
936 /// If there is an `Entry` with a matching key, it is deleted from
937 /// the hash map, and then returned from this function.
938 pub fn fetchRemove(self: *Self, key: K) ?KV {
939 if (@sizeOf(Context) != 0)
940 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call fetchRemoveContext instead.");
941 return self.fetchRemoveContext(key, undefined);
942 }
943 pub fn fetchRemoveContext(self: *Self, key: K, ctx: Context) ?KV {
944 return self.fetchRemoveAdapted(key, ctx);
945 }
946 pub fn fetchRemoveAdapted(self: *Self, key: anytype, ctx: anytype) ?KV {
947 if (self.getIndex(key, ctx)) |idx| {
948 const old_key = &self.keys()[idx];
949 const old_val = &self.values()[idx];
950 const result = KV{
951 .key = old_key.*,
952 .value = old_val.*,
953 };
954 self.metadata.?[idx].remove();
955 old_key.* = undefined;
956 old_val.* = undefined;
957 self.size -= 1;
958 self.available += 1;
959 return result;
960 }
961
962 return null;
963 }
964
965 /// Find the index containing the data for the given key.
966 fn getIndex(self: Self, key: anytype, ctx: anytype) ?usize {
967 if (self.size == 0) {
968 // We use cold instead of unlikely to force a jump to this case,
969 // no matter the weight of the opposing side.
970 @branchHint(.cold);
971 return null;
972 }
973
974 // If you get a compile error on this line, it means that your generic hash
975 // function is invalid for these parameters.
976 const hash: Hash = ctx.hash(key);
977
978 const mask = self.capacity() - 1;
979 const fingerprint = Metadata.takeFingerprint(hash);
980 // Don't loop indefinitely when there are no empty slots.
981 var limit = self.capacity();
982 var idx = @as(usize, @truncate(hash & mask));
983
984 var metadata = self.metadata.? + idx;
985 while (!metadata[0].isFree() and limit != 0) {
986 if (metadata[0].isUsed() and metadata[0].fingerprint == fingerprint) {
987 const test_key = &self.keys()[idx];
988
989 if (ctx.eql(key, test_key.*)) {
990 return idx;
991 }
992 }
993
994 limit -= 1;
995 idx = (idx + 1) & mask;
996 metadata = self.metadata.? + idx;
997 }
998
999 return null;
1000 }
1001
1002 pub fn getEntry(self: Self, key: K) ?Entry {
1003 if (@sizeOf(Context) != 0)
1004 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getEntryContext instead.");
1005 return self.getEntryContext(key, undefined);
1006 }
1007 pub fn getEntryContext(self: Self, key: K, ctx: Context) ?Entry {
1008 return self.getEntryAdapted(key, ctx);
1009 }
1010 pub fn getEntryAdapted(self: Self, key: anytype, ctx: anytype) ?Entry {
1011 if (self.getIndex(key, ctx)) |idx| {
1012 return Entry{
1013 .key_ptr = &self.keys()[idx],
1014 .value_ptr = &self.values()[idx],
1015 };
1016 }
1017 return null;
1018 }
1019
1020 /// Insert an entry if the associated key is not already present, otherwise update preexisting value.
1021 pub fn put(self: *Self, allocator: Allocator, key: K, value: V) Allocator.Error!void {
1022 if (@sizeOf(Context) != 0)
1023 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call putContext instead.");
1024 return self.putContext(allocator, key, value, undefined);
1025 }
1026 pub fn putContext(self: *Self, allocator: Allocator, key: K, value: V, ctx: Context) Allocator.Error!void {
1027 const result = try self.getOrPutContext(allocator, key, ctx);
1028 result.value_ptr.* = value;
1029 }
1030
1031 /// Get an optional pointer to the actual key associated with adapted key, if present.
1032 pub fn getKeyPtr(self: Self, key: K) ?*K {
1033 if (@sizeOf(Context) != 0)
1034 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getKeyPtrContext instead.");
1035 return self.getKeyPtrContext(key, undefined);
1036 }
1037 pub fn getKeyPtrContext(self: Self, key: K, ctx: Context) ?*K {
1038 return self.getKeyPtrAdapted(key, ctx);
1039 }
1040 pub fn getKeyPtrAdapted(self: Self, key: anytype, ctx: anytype) ?*K {
1041 if (self.getIndex(key, ctx)) |idx| {
1042 return &self.keys()[idx];
1043 }
1044 return null;
1045 }
1046
1047 /// Get a copy of the actual key associated with adapted key, if present.
1048 pub fn getKey(self: Self, key: K) ?K {
1049 if (@sizeOf(Context) != 0)
1050 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getKeyContext instead.");
1051 return self.getKeyContext(key, undefined);
1052 }
1053 pub fn getKeyContext(self: Self, key: K, ctx: Context) ?K {
1054 return self.getKeyAdapted(key, ctx);
1055 }
1056 pub fn getKeyAdapted(self: Self, key: anytype, ctx: anytype) ?K {
1057 if (self.getIndex(key, ctx)) |idx| {
1058 return self.keys()[idx];
1059 }
1060 return null;
1061 }
1062
1063 /// Get an optional pointer to the value associated with key, if present.
1064 pub fn getPtr(self: Self, key: K) ?*V {
1065 if (@sizeOf(Context) != 0)
1066 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getPtrContext instead.");
1067 return self.getPtrContext(key, undefined);
1068 }
1069 pub fn getPtrContext(self: Self, key: K, ctx: Context) ?*V {
1070 return self.getPtrAdapted(key, ctx);
1071 }
1072 pub fn getPtrAdapted(self: Self, key: anytype, ctx: anytype) ?*V {
1073 if (self.getIndex(key, ctx)) |idx| {
1074 return &self.values()[idx];
1075 }
1076 return null;
1077 }
1078
1079 /// Get a copy of the value associated with key, if present.
1080 pub fn get(self: Self, key: K) ?V {
1081 if (@sizeOf(Context) != 0)
1082 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getContext instead.");
1083 return self.getContext(key, undefined);
1084 }
1085 pub fn getContext(self: Self, key: K, ctx: Context) ?V {
1086 return self.getAdapted(key, ctx);
1087 }
1088 pub fn getAdapted(self: Self, key: anytype, ctx: anytype) ?V {
1089 if (self.getIndex(key, ctx)) |idx| {
1090 return self.values()[idx];
1091 }
1092 return null;
1093 }
1094
1095 pub fn getOrPut(self: *Self, allocator: Allocator, key: K) Allocator.Error!GetOrPutResult {
1096 if (@sizeOf(Context) != 0)
1097 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getOrPutContext instead.");
1098 return self.getOrPutContext(allocator, key, undefined);
1099 }
1100 pub fn getOrPutContext(self: *Self, allocator: Allocator, key: K, ctx: Context) Allocator.Error!GetOrPutResult {
1101 const gop = try self.getOrPutContextAdapted(allocator, key, ctx, ctx);
1102 if (!gop.found_existing) {
1103 gop.key_ptr.* = key;
1104 }
1105 return gop;
1106 }
1107 pub fn getOrPutAdapted(self: *Self, allocator: Allocator, key: anytype, key_ctx: anytype) Allocator.Error!GetOrPutResult {
1108 if (@sizeOf(Context) != 0)
1109 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getOrPutContextAdapted instead.");
1110 return self.getOrPutContextAdapted(allocator, key, key_ctx, undefined);
1111 }
1112 pub fn getOrPutContextAdapted(self: *Self, allocator: Allocator, key: anytype, key_ctx: anytype, ctx: Context) Allocator.Error!GetOrPutResult {
1113 {
1114 self.pointer_stability.lock();
1115 defer self.pointer_stability.unlock();
1116 self.growIfNeeded(allocator, 1, ctx) catch |err| {
1117 // If allocation fails, try to do the lookup anyway.
1118 // If we find an existing item, we can return it.
1119 // Otherwise return the error, we could not add another.
1120 const index = self.getIndex(key, key_ctx) orelse return err;
1121 return GetOrPutResult{
1122 .key_ptr = &self.keys()[index],
1123 .value_ptr = &self.values()[index],
1124 .found_existing = true,
1125 };
1126 };
1127 }
1128 return self.getOrPutAssumeCapacityAdapted(key, key_ctx);
1129 }
1130
1131 pub fn getOrPutAssumeCapacity(self: *Self, key: K) GetOrPutResult {
1132 if (@sizeOf(Context) != 0)
1133 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getOrPutAssumeCapacityContext instead.");
1134 return self.getOrPutAssumeCapacityContext(key, undefined);
1135 }
1136 pub fn getOrPutAssumeCapacityContext(self: *Self, key: K, ctx: Context) GetOrPutResult {
1137 const result = self.getOrPutAssumeCapacityAdapted(key, ctx);
1138 if (!result.found_existing) {
1139 result.key_ptr.* = key;
1140 }
1141 return result;
1142 }
1143 pub fn getOrPutAssumeCapacityAdapted(self: *Self, key: anytype, ctx: anytype) GetOrPutResult {
1144
1145 // If you get a compile error on this line, it means that your generic hash
1146 // function is invalid for these parameters.
1147 const hash: Hash = ctx.hash(key);
1148
1149 const mask = self.capacity() - 1;
1150 const fingerprint = Metadata.takeFingerprint(hash);
1151 var limit = self.capacity();
1152 var idx = @as(usize, @truncate(hash & mask));
1153
1154 var first_tombstone_idx: usize = self.capacity(); // invalid index
1155 var metadata = self.metadata.? + idx;
1156 while (!metadata[0].isFree() and limit != 0) {
1157 if (metadata[0].isUsed() and metadata[0].fingerprint == fingerprint) {
1158 const test_key = &self.keys()[idx];
1159 // If you get a compile error on this line, it means that your generic eql
1160 // function is invalid for these parameters.
1161
1162 if (ctx.eql(key, test_key.*)) {
1163 return GetOrPutResult{
1164 .key_ptr = test_key,
1165 .value_ptr = &self.values()[idx],
1166 .found_existing = true,
1167 };
1168 }
1169 } else if (first_tombstone_idx == self.capacity() and metadata[0].isTombstone()) {
1170 first_tombstone_idx = idx;
1171 }
1172
1173 limit -= 1;
1174 idx = (idx + 1) & mask;
1175 metadata = self.metadata.? + idx;
1176 }
1177
1178 if (first_tombstone_idx < self.capacity()) {
1179 // Cheap try to lower probing lengths after deletions. Recycle a tombstone.
1180 idx = first_tombstone_idx;
1181 metadata = self.metadata.? + idx;
1182 }
1183 // We're using a slot previously free or a tombstone.
1184 self.available -= 1;
1185
1186 metadata[0].fill(fingerprint);
1187 const new_key = &self.keys()[idx];
1188 const new_value = &self.values()[idx];
1189 new_key.* = undefined;
1190 new_value.* = undefined;
1191 self.size += 1;
1192
1193 return GetOrPutResult{
1194 .key_ptr = new_key,
1195 .value_ptr = new_value,
1196 .found_existing = false,
1197 };
1198 }
1199
1200 pub fn getOrPutValue(self: *Self, allocator: Allocator, key: K, value: V) Allocator.Error!Entry {
1201 if (@sizeOf(Context) != 0)
1202 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getOrPutValueContext instead.");
1203 return self.getOrPutValueContext(allocator, key, value, undefined);
1204 }
1205 pub fn getOrPutValueContext(self: *Self, allocator: Allocator, key: K, value: V, ctx: Context) Allocator.Error!Entry {
1206 const res = try self.getOrPutAdapted(allocator, key, ctx);
1207 if (!res.found_existing) {
1208 res.key_ptr.* = key;
1209 res.value_ptr.* = value;
1210 }
1211 return Entry{ .key_ptr = res.key_ptr, .value_ptr = res.value_ptr };
1212 }
1213
1214 /// Return true if there is a value associated with key in the map.
1215 pub fn contains(self: Self, key: K) bool {
1216 if (@sizeOf(Context) != 0)
1217 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call containsContext instead.");
1218 return self.containsContext(key, undefined);
1219 }
1220 pub fn containsContext(self: Self, key: K, ctx: Context) bool {
1221 return self.containsAdapted(key, ctx);
1222 }
1223 pub fn containsAdapted(self: Self, key: anytype, ctx: anytype) bool {
1224 return self.getIndex(key, ctx) != null;
1225 }
1226
1227 fn removeByIndex(self: *Self, idx: usize) void {
1228 self.metadata.?[idx].remove();
1229 self.keys()[idx] = undefined;
1230 self.values()[idx] = undefined;
1231 self.size -= 1;
1232 self.available += 1;
1233 }
1234
1235 /// If there is an `Entry` with a matching key, it is deleted from
1236 /// the hash map, and this function returns true. Otherwise this
1237 /// function returns false.
1238 ///
1239 /// TODO: answer the question in these doc comments, does this
1240 /// increase the unused capacity by one?
1241 pub fn remove(self: *Self, key: K) bool {
1242 if (@sizeOf(Context) != 0)
1243 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call removeContext instead.");
1244 return self.removeContext(key, undefined);
1245 }
1246
1247 /// TODO: answer the question in these doc comments, does this
1248 /// increase the unused capacity by one?
1249 pub fn removeContext(self: *Self, key: K, ctx: Context) bool {
1250 return self.removeAdapted(key, ctx);
1251 }
1252
1253 /// TODO: answer the question in these doc comments, does this
1254 /// increase the unused capacity by one?
1255 pub fn removeAdapted(self: *Self, key: anytype, ctx: anytype) bool {
1256 if (self.getIndex(key, ctx)) |idx| {
1257 self.removeByIndex(idx);
1258 return true;
1259 }
1260
1261 return false;
1262 }
1263
1264 /// Delete the entry with key pointed to by key_ptr from the hash map.
1265 /// key_ptr is assumed to be a valid pointer to a key that is present
1266 /// in the hash map.
1267 ///
1268 /// TODO: answer the question in these doc comments, does this
1269 /// increase the unused capacity by one?
1270 pub fn removeByPtr(self: *Self, key_ptr: *K) void {
1271 // if @sizeOf(K) == 0 then there is at most one item in the hash
1272 // map, which is assumed to exist as key_ptr must be valid. This
1273 // item must be at index 0.
1274 const idx = if (@sizeOf(K) > 0)
1275 @as([*]K, @ptrCast(key_ptr)) - self.keys()
1276 else
1277 0;
1278
1279 self.removeByIndex(idx);
1280 }
1281
1282 fn initMetadatas(self: *Self) void {
1283 @memset(@as([*]u8, @ptrCast(self.metadata.?))[0 .. @sizeOf(Metadata) * self.capacity()], 0);
1284 }
1285
1286 // This counts the number of occupied slots (not counting tombstones), which is
1287 // what has to stay under the max_load_percentage of capacity.
1288 fn load(self: Self) Size {
1289 const max_load = (self.capacity() * max_load_percentage) / 100;
1290 assert(max_load >= self.available);
1291 return @as(Size, @truncate(max_load - self.available));
1292 }
1293
1294 fn growIfNeeded(self: *Self, allocator: Allocator, new_count: Size, ctx: Context) Allocator.Error!void {
1295 if (new_count > self.available) {
1296 try self.grow(allocator, capacityForSize(self.load() + new_count), ctx);
1297 }
1298 }
1299
1300 pub fn clone(self: Self, allocator: Allocator) Allocator.Error!Self {
1301 if (@sizeOf(Context) != 0)
1302 @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call cloneContext instead.");
1303 return self.cloneContext(allocator, @as(Context, undefined));
1304 }
1305 pub fn cloneContext(self: Self, allocator: Allocator, new_ctx: anytype) Allocator.Error!HashMapUnmanaged(K, V, @TypeOf(new_ctx), max_load_percentage) {
1306 var other: HashMapUnmanaged(K, V, @TypeOf(new_ctx), max_load_percentage) = .empty;
1307 if (self.size == 0)
1308 return other;
1309
1310 const new_cap = capacityForSize(self.size);
1311 try other.allocate(allocator, new_cap);
1312 other.initMetadatas();
1313 other.available = @truncate((new_cap * max_load_percentage) / 100);
1314
1315 var i: Size = 0;
1316 var metadata = self.metadata.?;
1317 const keys_ptr = self.keys();
1318 const values_ptr = self.values();
1319 while (i < self.capacity()) : (i += 1) {
1320 if (metadata[i].isUsed()) {
1321 other.putAssumeCapacityNoClobberContext(keys_ptr[i], values_ptr[i], new_ctx);
1322 if (other.size == self.size)
1323 break;
1324 }
1325 }
1326
1327 return other;
1328 }
1329
1330 /// Set the map to an empty state, making deinitialization a no-op, and
1331 /// returning a copy of the original.
1332 pub fn move(self: *Self) Self {
1333 self.pointer_stability.assertUnlocked();
1334 const result = self.*;
1335 self.* = .empty;
1336 return result;
1337 }
1338
1339 /// Rehash the map, in-place.
1340 ///
1341 /// Over time, due to the current tombstone-based implementation, a
1342 /// HashMap could become fragmented due to the buildup of tombstone
1343 /// entries that causes a performance degradation due to excessive
1344 /// probing. The kind of pattern that might cause this is a long-lived
1345 /// HashMap with repeated inserts and deletes.
1346 ///
1347 /// After this function is called, there will be no tombstones in
1348 /// the HashMap, each of the entries is rehashed and any existing
1349 /// key/value pointers into the HashMap are invalidated.
1350 pub fn rehash(self: *Self, ctx: anytype) void {
1351 const mask = self.capacity() - 1;
1352
1353 var metadata = self.metadata.?;
1354 var keys_ptr = self.keys();
1355 var values_ptr = self.values();
1356 var curr: Size = 0;
1357
1358 // While we are re-hashing every slot, we will use the
1359 // fingerprint to mark used buckets as being used and either free
1360 // (needing to be rehashed) or tombstone (already rehashed).
1361
1362 while (curr < self.capacity()) : (curr += 1) {
1363 metadata[curr].fingerprint = Metadata.free;
1364 }
1365
1366 // Now iterate over all the buckets, rehashing them
1367
1368 curr = 0;
1369 while (curr < self.capacity()) {
1370 if (!metadata[curr].isUsed()) {
1371 assert(metadata[curr].isFree());
1372 curr += 1;
1373 continue;
1374 }
1375
1376 const hash = ctx.hash(keys_ptr[curr]);
1377 const fingerprint = Metadata.takeFingerprint(hash);
1378 var idx = @as(usize, @truncate(hash & mask));
1379
1380 // For each bucket, rehash to an index:
1381 // 1) before the cursor, probed into a free slot, or
1382 // 2) equal to the cursor, no need to move, or
1383 // 3) ahead of the cursor, probing over already rehashed
1384
1385 while ((idx < curr and metadata[idx].isUsed()) or
1386 (idx > curr and metadata[idx].fingerprint == Metadata.tombstone))
1387 {
1388 idx = (idx + 1) & mask;
1389 }
1390
1391 if (idx < curr) {
1392 assert(metadata[idx].isFree());
1393 metadata[idx].fill(fingerprint);
1394 keys_ptr[idx] = keys_ptr[curr];
1395 values_ptr[idx] = values_ptr[curr];
1396
1397 metadata[curr].used = 0;
1398 assert(metadata[curr].isFree());
1399 keys_ptr[curr] = undefined;
1400 values_ptr[curr] = undefined;
1401
1402 curr += 1;
1403 } else if (idx == curr) {
1404 metadata[idx].fingerprint = fingerprint;
1405 curr += 1;
1406 } else {
1407 assert(metadata[idx].fingerprint != Metadata.tombstone);
1408 metadata[idx].fingerprint = Metadata.tombstone;
1409 if (metadata[idx].isUsed()) {
1410 std.mem.swap(K, &keys_ptr[curr], &keys_ptr[idx]);
1411 std.mem.swap(V, &values_ptr[curr], &values_ptr[idx]);
1412 } else {
1413 metadata[idx].used = 1;
1414 keys_ptr[idx] = keys_ptr[curr];
1415 values_ptr[idx] = values_ptr[curr];
1416
1417 metadata[curr].fingerprint = Metadata.free;
1418 metadata[curr].used = 0;
1419 keys_ptr[curr] = undefined;
1420 values_ptr[curr] = undefined;
1421
1422 curr += 1;
1423 }
1424 }
1425 }
1426 }
1427
1428 fn grow(self: *Self, allocator: Allocator, new_capacity: Size, ctx: Context) Allocator.Error!void {
1429 @branchHint(.cold);
1430 const new_cap = @max(new_capacity, minimal_capacity);
1431 assert(new_cap > self.capacity());
1432 assert(std.math.isPowerOfTwo(new_cap));
1433
1434 var map: Self = .{};
1435 try map.allocate(allocator, new_cap);
1436 errdefer comptime unreachable;
1437 map.pointer_stability.lock();
1438 map.initMetadatas();
1439 map.available = @truncate((new_cap * max_load_percentage) / 100);
1440
1441 if (self.size != 0) {
1442 const old_capacity = self.capacity();
1443 for (
1444 self.metadata.?[0..old_capacity],
1445 self.keys()[0..old_capacity],
1446 self.values()[0..old_capacity],
1447 ) |m, k, v| {
1448 if (!m.isUsed()) continue;
1449 map.putAssumeCapacityNoClobberContext(k, v, ctx);
1450 if (map.size == self.size) break;
1451 }
1452 }
1453
1454 self.size = 0;
1455 self.pointer_stability = .{};
1456 std.mem.swap(Self, self, &map);
1457 map.deinit(allocator);
1458 }
1459
1460 fn allocate(self: *Self, allocator: Allocator, new_capacity: Size) Allocator.Error!void {
1461 const header_align = @alignOf(Header);
1462 const key_align = if (@sizeOf(K) == 0) 1 else @alignOf(K);
1463 const val_align = if (@sizeOf(V) == 0) 1 else @alignOf(V);
1464 const max_align: Alignment = comptime .fromByteUnits(@max(header_align, key_align, val_align));
1465
1466 const new_cap: usize = new_capacity;
1467 const meta_size = @sizeOf(Header) + new_cap * @sizeOf(Metadata);
1468 comptime assert(@alignOf(Metadata) == 1);
1469
1470 const keys_start = std.mem.alignForward(usize, meta_size, key_align);
1471 const keys_end = keys_start + new_cap * @sizeOf(K);
1472
1473 const vals_start = std.mem.alignForward(usize, keys_end, val_align);
1474 const vals_end = vals_start + new_cap * @sizeOf(V);
1475
1476 const total_size = max_align.forward(vals_end);
1477
1478 const slice = try allocator.alignedAlloc(u8, max_align, total_size);
1479 const ptr: [*]u8 = @ptrCast(slice.ptr);
1480
1481 const metadata = ptr + @sizeOf(Header);
1482
1483 const hdr = @as(*Header, @ptrCast(@alignCast(ptr)));
1484 if (@sizeOf([*]V) != 0) {
1485 hdr.values = @ptrCast(@alignCast((ptr + vals_start)));
1486 }
1487 if (@sizeOf([*]K) != 0) {
1488 hdr.keys = @ptrCast(@alignCast((ptr + keys_start)));
1489 }
1490 hdr.capacity = new_capacity;
1491 self.metadata = @ptrCast(@alignCast(metadata));
1492 }
1493
1494 fn deallocate(self: *Self, allocator: Allocator) void {
1495 if (self.metadata == null) return;
1496
1497 const header_align = @alignOf(Header);
1498 const key_align = if (@sizeOf(K) == 0) 1 else @alignOf(K);
1499 const val_align = if (@sizeOf(V) == 0) 1 else @alignOf(V);
1500 const max_align = comptime @max(header_align, key_align, val_align);
1501
1502 const cap: usize = self.capacity();
1503 const meta_size = @sizeOf(Header) + cap * @sizeOf(Metadata);
1504 comptime assert(@alignOf(Metadata) == 1);
1505
1506 const keys_start = std.mem.alignForward(usize, meta_size, key_align);
1507 const keys_end = keys_start + cap * @sizeOf(K);
1508
1509 const vals_start = std.mem.alignForward(usize, keys_end, val_align);
1510 const vals_end = vals_start + cap * @sizeOf(V);
1511
1512 const total_size = std.mem.alignForward(usize, vals_end, max_align);
1513
1514 const slice = @as([*]align(max_align) u8, @ptrCast(@alignCast(self.header())))[0..total_size];
1515 allocator.free(slice);
1516
1517 self.metadata = null;
1518 self.available = 0;
1519 }
1520
1521 /// This function is used in the debugger pretty formatters in lib/lldb/ to fetch the
1522 /// header type to facilitate fancy debug printing for this type.
1523 fn dbHelper(self: *Self, hdr: *Header, entry: *Entry) void {
1524 _ = self;
1525 _ = hdr;
1526 _ = entry;
1527 }
1528
1529 comptime {
1530 if (!builtin.strip_debug_info) switch (builtin.zig_backend) {
1531 .stage2_llvm => _ = &dbHelper,
1532 .stage2_x86_64 => _ = @as(KV, undefined),
1533 else => {},
1534 };
1535 }
1536 };
1537}
1538
1539const testing = std.testing;
1540const expect = std.testing.expect;
1541const expectEqual = std.testing.expectEqual;
1542
1543test "basic usage" {
1544 var map = AutoHashMap(u32, u32).init(std.testing.allocator);
1545 defer map.deinit();
1546
1547 const count = 5;
1548 var i: u32 = 0;
1549 var total: u32 = 0;
1550 while (i < count) : (i += 1) {
1551 try map.put(i, i);
1552 total += i;
1553 }
1554
1555 var sum: u32 = 0;
1556 var it = map.iterator();
1557 while (it.next()) |kv| {
1558 sum += kv.key_ptr.*;
1559 }
1560 try expectEqual(total, sum);
1561
1562 i = 0;
1563 sum = 0;
1564 while (i < count) : (i += 1) {
1565 try expectEqual(i, map.get(i).?);
1566 sum += map.get(i).?;
1567 }
1568 try expectEqual(total, sum);
1569}
1570
1571test "ensureTotalCapacity" {
1572 var map = AutoHashMap(i32, i32).init(std.testing.allocator);
1573 defer map.deinit();
1574
1575 try map.ensureTotalCapacity(20);
1576 const initial_capacity = map.capacity();
1577 try testing.expect(initial_capacity >= 20);
1578 var i: i32 = 0;
1579 while (i < 20) : (i += 1) {
1580 try testing.expect(map.fetchPutAssumeCapacity(i, i + 10) == null);
1581 }
1582 // shouldn't resize from putAssumeCapacity
1583 try testing.expect(initial_capacity == map.capacity());
1584}
1585
1586test "ensureUnusedCapacity with tombstones" {
1587 var map = AutoHashMap(i32, i32).init(std.testing.allocator);
1588 defer map.deinit();
1589
1590 var i: i32 = 0;
1591 while (i < 100) : (i += 1) {
1592 try map.ensureUnusedCapacity(1);
1593 map.putAssumeCapacity(i, i);
1594 _ = map.remove(i);
1595 }
1596}
1597
1598test "clearRetainingCapacity" {
1599 var map = AutoHashMap(u32, u32).init(std.testing.allocator);
1600 defer map.deinit();
1601
1602 map.clearRetainingCapacity();
1603
1604 try map.put(1, 1);
1605 try expectEqual(map.get(1).?, 1);
1606 try expectEqual(map.count(), 1);
1607
1608 map.clearRetainingCapacity();
1609 map.putAssumeCapacity(1, 1);
1610 try expectEqual(map.get(1).?, 1);
1611 try expectEqual(map.count(), 1);
1612
1613 const cap = map.capacity();
1614 try expect(cap > 0);
1615
1616 map.clearRetainingCapacity();
1617 map.clearRetainingCapacity();
1618 try expectEqual(map.count(), 0);
1619 try expectEqual(map.capacity(), cap);
1620 try expect(!map.contains(1));
1621}
1622
1623test "grow" {
1624 var map = AutoHashMap(u32, u32).init(std.testing.allocator);
1625 defer map.deinit();
1626
1627 const growTo = 12456;
1628
1629 var i: u32 = 0;
1630 while (i < growTo) : (i += 1) {
1631 try map.put(i, i);
1632 }
1633 try expectEqual(map.count(), growTo);
1634
1635 i = 0;
1636 var it = map.iterator();
1637 while (it.next()) |kv| {
1638 try expectEqual(kv.key_ptr.*, kv.value_ptr.*);
1639 i += 1;
1640 }
1641 try expectEqual(i, growTo);
1642
1643 i = 0;
1644 while (i < growTo) : (i += 1) {
1645 try expectEqual(map.get(i).?, i);
1646 }
1647}
1648
1649test "clone" {
1650 var map = AutoHashMap(u32, u32).init(std.testing.allocator);
1651 defer map.deinit();
1652
1653 var a = try map.clone();
1654 defer a.deinit();
1655
1656 try expectEqual(a.count(), 0);
1657
1658 try a.put(1, 1);
1659 try a.put(2, 2);
1660 try a.put(3, 3);
1661
1662 var b = try a.clone();
1663 defer b.deinit();
1664
1665 try expectEqual(b.count(), 3);
1666 try expectEqual(b.get(1).?, 1);
1667 try expectEqual(b.get(2).?, 2);
1668 try expectEqual(b.get(3).?, 3);
1669
1670 var original = AutoHashMap(i32, i32).init(std.testing.allocator);
1671 defer original.deinit();
1672
1673 var i: u8 = 0;
1674 while (i < 10) : (i += 1) {
1675 try original.putNoClobber(i, i * 10);
1676 }
1677
1678 var copy = try original.clone();
1679 defer copy.deinit();
1680
1681 i = 0;
1682 while (i < 10) : (i += 1) {
1683 try testing.expect(copy.get(i).? == i * 10);
1684 }
1685}
1686
1687test "ensureTotalCapacity with existing elements" {
1688 var map = AutoHashMap(u32, u32).init(std.testing.allocator);
1689 defer map.deinit();
1690
1691 try map.put(0, 0);
1692 try expectEqual(map.count(), 1);
1693 try expectEqual(map.capacity(), @TypeOf(map).Unmanaged.minimal_capacity);
1694
1695 try map.ensureTotalCapacity(65);
1696 try expectEqual(map.count(), 1);
1697 try expectEqual(map.capacity(), 128);
1698}
1699
1700test "ensureTotalCapacity satisfies max load factor" {
1701 var map = AutoHashMap(u32, u32).init(std.testing.allocator);
1702 defer map.deinit();
1703
1704 try map.ensureTotalCapacity(127);
1705 try expectEqual(map.capacity(), 256);
1706}
1707
1708test "remove" {
1709 var map = AutoHashMap(u32, u32).init(std.testing.allocator);
1710 defer map.deinit();
1711
1712 var i: u32 = 0;
1713 while (i < 16) : (i += 1) {
1714 try map.put(i, i);
1715 }
1716
1717 i = 0;
1718 while (i < 16) : (i += 1) {
1719 if (i % 3 == 0) {
1720 _ = map.remove(i);
1721 }
1722 }
1723 try expectEqual(map.count(), 10);
1724 var it = map.iterator();
1725 while (it.next()) |kv| {
1726 try expectEqual(kv.key_ptr.*, kv.value_ptr.*);
1727 try expect(kv.key_ptr.* % 3 != 0);
1728 }
1729
1730 i = 0;
1731 while (i < 16) : (i += 1) {
1732 if (i % 3 == 0) {
1733 try expect(!map.contains(i));
1734 } else {
1735 try expectEqual(map.get(i).?, i);
1736 }
1737 }
1738}
1739
1740test "reverse removes" {
1741 var map = AutoHashMap(u32, u32).init(std.testing.allocator);
1742 defer map.deinit();
1743
1744 var i: u32 = 0;
1745 while (i < 16) : (i += 1) {
1746 try map.putNoClobber(i, i);
1747 }
1748
1749 i = 16;
1750 while (i > 0) : (i -= 1) {
1751 _ = map.remove(i - 1);
1752 try expect(!map.contains(i - 1));
1753 var j: u32 = 0;
1754 while (j < i - 1) : (j += 1) {
1755 try expectEqual(map.get(j).?, j);
1756 }
1757 }
1758
1759 try expectEqual(map.count(), 0);
1760}
1761
1762test "multiple removes on same metadata" {
1763 var map = AutoHashMap(u32, u32).init(std.testing.allocator);
1764 defer map.deinit();
1765
1766 var i: u32 = 0;
1767 while (i < 16) : (i += 1) {
1768 try map.put(i, i);
1769 }
1770
1771 _ = map.remove(7);
1772 _ = map.remove(15);
1773 _ = map.remove(14);
1774 _ = map.remove(13);
1775 try expect(!map.contains(7));
1776 try expect(!map.contains(15));
1777 try expect(!map.contains(14));
1778 try expect(!map.contains(13));
1779
1780 i = 0;
1781 while (i < 13) : (i += 1) {
1782 if (i == 7) {
1783 try expect(!map.contains(i));
1784 } else {
1785 try expectEqual(map.get(i).?, i);
1786 }
1787 }
1788
1789 try map.put(15, 15);
1790 try map.put(13, 13);
1791 try map.put(14, 14);
1792 try map.put(7, 7);
1793 i = 0;
1794 while (i < 16) : (i += 1) {
1795 try expectEqual(map.get(i).?, i);
1796 }
1797}
1798
1799test "put and remove loop in random order" {
1800 var map = AutoHashMap(u32, u32).init(std.testing.allocator);
1801 defer map.deinit();
1802
1803 var keys = std.array_list.Managed(u32).init(std.testing.allocator);
1804 defer keys.deinit();
1805
1806 const size = 32;
1807 const iterations = 100;
1808
1809 var i: u32 = 0;
1810 while (i < size) : (i += 1) {
1811 try keys.append(i);
1812 }
1813 var prng = std.Random.DefaultPrng.init(std.testing.random_seed);
1814 const random = prng.random();
1815
1816 while (i < iterations) : (i += 1) {
1817 random.shuffle(u32, keys.items);
1818
1819 for (keys.items) |key| {
1820 try map.put(key, key);
1821 }
1822 try expectEqual(map.count(), size);
1823
1824 for (keys.items) |key| {
1825 _ = map.remove(key);
1826 }
1827 try expectEqual(map.count(), 0);
1828 }
1829}
1830
1831test "remove many elements in random order" {
1832 const Map = AutoHashMap(u32, u32);
1833 const n = 1000 * 100;
1834 var map = Map.init(std.heap.page_allocator);
1835 defer map.deinit();
1836
1837 var keys = std.array_list.Managed(u32).init(std.heap.page_allocator);
1838 defer keys.deinit();
1839
1840 var i: u32 = 0;
1841 while (i < n) : (i += 1) {
1842 keys.append(i) catch unreachable;
1843 }
1844
1845 var prng = std.Random.DefaultPrng.init(std.testing.random_seed);
1846 const random = prng.random();
1847 random.shuffle(u32, keys.items);
1848
1849 for (keys.items) |key| {
1850 map.put(key, key) catch unreachable;
1851 }
1852
1853 random.shuffle(u32, keys.items);
1854 i = 0;
1855 while (i < n) : (i += 1) {
1856 const key = keys.items[i];
1857 _ = map.remove(key);
1858 }
1859}
1860
1861test "put" {
1862 var map = AutoHashMap(u32, u32).init(std.testing.allocator);
1863 defer map.deinit();
1864
1865 var i: u32 = 0;
1866 while (i < 16) : (i += 1) {
1867 try map.put(i, i);
1868 }
1869
1870 i = 0;
1871 while (i < 16) : (i += 1) {
1872 try expectEqual(map.get(i).?, i);
1873 }
1874
1875 i = 0;
1876 while (i < 16) : (i += 1) {
1877 try map.put(i, i * 16 + 1);
1878 }
1879
1880 i = 0;
1881 while (i < 16) : (i += 1) {
1882 try expectEqual(map.get(i).?, i * 16 + 1);
1883 }
1884}
1885
1886test "putAssumeCapacity" {
1887 var map = AutoHashMap(u32, u32).init(std.testing.allocator);
1888 defer map.deinit();
1889
1890 try map.ensureTotalCapacity(20);
1891 var i: u32 = 0;
1892 while (i < 20) : (i += 1) {
1893 map.putAssumeCapacityNoClobber(i, i);
1894 }
1895
1896 i = 0;
1897 var sum = i;
1898 while (i < 20) : (i += 1) {
1899 sum += map.getPtr(i).?.*;
1900 }
1901 try expectEqual(sum, 190);
1902
1903 i = 0;
1904 while (i < 20) : (i += 1) {
1905 map.putAssumeCapacity(i, 1);
1906 }
1907
1908 i = 0;
1909 sum = i;
1910 while (i < 20) : (i += 1) {
1911 sum += map.get(i).?;
1912 }
1913 try expectEqual(sum, 20);
1914}
1915
1916test "repeat putAssumeCapacity/remove" {
1917 var map = AutoHashMap(u32, u32).init(std.testing.allocator);
1918 defer map.deinit();
1919
1920 try map.ensureTotalCapacity(20);
1921 const limit = map.unmanaged.available;
1922
1923 var i: u32 = 0;
1924 while (i < limit) : (i += 1) {
1925 map.putAssumeCapacityNoClobber(i, i);
1926 }
1927
1928 // Repeatedly delete/insert an entry without resizing the map.
1929 // Put to different keys so entries don't land in the just-freed slot.
1930 i = 0;
1931 while (i < 10 * limit) : (i += 1) {
1932 try testing.expect(map.remove(i));
1933 if (i % 2 == 0) {
1934 map.putAssumeCapacityNoClobber(limit + i, i);
1935 } else {
1936 map.putAssumeCapacity(limit + i, i);
1937 }
1938 }
1939
1940 i = 9 * limit;
1941 while (i < 10 * limit) : (i += 1) {
1942 try expectEqual(map.get(limit + i), i);
1943 }
1944 try expectEqual(map.unmanaged.available, 0);
1945 try expectEqual(map.unmanaged.count(), limit);
1946}
1947
1948test "getOrPut" {
1949 var map = AutoHashMap(u32, u32).init(std.testing.allocator);
1950 defer map.deinit();
1951
1952 var i: u32 = 0;
1953 while (i < 10) : (i += 1) {
1954 try map.put(i * 2, 2);
1955 }
1956
1957 i = 0;
1958 while (i < 20) : (i += 1) {
1959 _ = try map.getOrPutValue(i, 1);
1960 }
1961
1962 i = 0;
1963 var sum = i;
1964 while (i < 20) : (i += 1) {
1965 sum += map.get(i).?;
1966 }
1967
1968 try expectEqual(sum, 30);
1969}
1970
1971test "basic hash map usage" {
1972 var map = AutoHashMap(i32, i32).init(std.testing.allocator);
1973 defer map.deinit();
1974
1975 try testing.expect((try map.fetchPut(1, 11)) == null);
1976 try testing.expect((try map.fetchPut(2, 22)) == null);
1977 try testing.expect((try map.fetchPut(3, 33)) == null);
1978 try testing.expect((try map.fetchPut(4, 44)) == null);
1979
1980 try map.putNoClobber(5, 55);
1981 try testing.expect((try map.fetchPut(5, 66)).?.value == 55);
1982 try testing.expect((try map.fetchPut(5, 55)).?.value == 66);
1983
1984 const gop1 = try map.getOrPut(5);
1985 try testing.expect(gop1.found_existing == true);
1986 try testing.expect(gop1.value_ptr.* == 55);
1987 gop1.value_ptr.* = 77;
1988 try testing.expect(map.getEntry(5).?.value_ptr.* == 77);
1989
1990 const gop2 = try map.getOrPut(99);
1991 try testing.expect(gop2.found_existing == false);
1992 gop2.value_ptr.* = 42;
1993 try testing.expect(map.getEntry(99).?.value_ptr.* == 42);
1994
1995 const gop3 = try map.getOrPutValue(5, 5);
1996 try testing.expect(gop3.value_ptr.* == 77);
1997
1998 const gop4 = try map.getOrPutValue(100, 41);
1999 try testing.expect(gop4.value_ptr.* == 41);
2000
2001 try testing.expect(map.contains(2));
2002 try testing.expect(map.getEntry(2).?.value_ptr.* == 22);
2003 try testing.expect(map.get(2).? == 22);
2004
2005 const rmv1 = map.fetchRemove(2);
2006 try testing.expect(rmv1.?.key == 2);
2007 try testing.expect(rmv1.?.value == 22);
2008 try testing.expect(map.fetchRemove(2) == null);
2009 try testing.expect(map.remove(2) == false);
2010 try testing.expect(map.getEntry(2) == null);
2011 try testing.expect(map.get(2) == null);
2012
2013 try testing.expect(map.remove(3) == true);
2014}
2015
2016test "getOrPutAdapted" {
2017 const AdaptedContext = struct {
2018 fn eql(self: @This(), adapted_key: []const u8, test_key: u64) bool {
2019 _ = self;
2020 return std.fmt.parseInt(u64, adapted_key, 10) catch unreachable == test_key;
2021 }
2022 fn hash(self: @This(), adapted_key: []const u8) u64 {
2023 _ = self;
2024 const key = std.fmt.parseInt(u64, adapted_key, 10) catch unreachable;
2025 return (AutoContext(u64){}).hash(key);
2026 }
2027 };
2028 var map = AutoHashMap(u64, u64).init(testing.allocator);
2029 defer map.deinit();
2030
2031 const keys = [_][]const u8{
2032 "1231",
2033 "4564",
2034 "7894",
2035 "1132",
2036 "65235",
2037 "95462",
2038 "0112305",
2039 "00658",
2040 "0",
2041 "2",
2042 };
2043
2044 var real_keys: [keys.len]u64 = undefined;
2045
2046 inline for (keys, 0..) |key_str, i| {
2047 const result = try map.getOrPutAdapted(key_str, AdaptedContext{});
2048 try testing.expect(!result.found_existing);
2049 real_keys[i] = std.fmt.parseInt(u64, key_str, 10) catch unreachable;
2050 result.key_ptr.* = real_keys[i];
2051 result.value_ptr.* = i * 2;
2052 }
2053
2054 try testing.expectEqual(map.count(), keys.len);
2055
2056 inline for (keys, 0..) |key_str, i| {
2057 const result = map.getOrPutAssumeCapacityAdapted(key_str, AdaptedContext{});
2058 try testing.expect(result.found_existing);
2059 try testing.expectEqual(real_keys[i], result.key_ptr.*);
2060 try testing.expectEqual(@as(u64, i) * 2, result.value_ptr.*);
2061 try testing.expectEqual(real_keys[i], map.getKeyAdapted(key_str, AdaptedContext{}).?);
2062 }
2063}
2064
2065test "ensureUnusedCapacity" {
2066 var map = AutoHashMap(u64, u64).init(testing.allocator);
2067 defer map.deinit();
2068
2069 try map.ensureUnusedCapacity(32);
2070 const capacity = map.capacity();
2071 try map.ensureUnusedCapacity(32);
2072
2073 // Repeated ensureUnusedCapacity() calls with no insertions between
2074 // should not change the capacity.
2075 try testing.expectEqual(capacity, map.capacity());
2076}
2077
2078test "removeByPtr" {
2079 var map = AutoHashMap(i32, u64).init(testing.allocator);
2080 defer map.deinit();
2081
2082 var i: i32 = undefined;
2083
2084 i = 0;
2085 while (i < 10) : (i += 1) {
2086 try map.put(i, 0);
2087 }
2088
2089 try testing.expect(map.count() == 10);
2090
2091 i = 0;
2092 while (i < 10) : (i += 1) {
2093 const key_ptr = map.getKeyPtr(i);
2094 try testing.expect(key_ptr != null);
2095
2096 if (key_ptr) |ptr| {
2097 map.removeByPtr(ptr);
2098 }
2099 }
2100
2101 try testing.expect(map.count() == 0);
2102}
2103
2104test "removeByPtr 0 sized key" {
2105 var map = AutoHashMap(u0, u64).init(testing.allocator);
2106 defer map.deinit();
2107
2108 try map.put(0, 0);
2109
2110 try testing.expect(map.count() == 1);
2111
2112 const key_ptr = map.getKeyPtr(0);
2113 try testing.expect(key_ptr != null);
2114
2115 if (key_ptr) |ptr| {
2116 map.removeByPtr(ptr);
2117 }
2118
2119 try testing.expect(map.count() == 0);
2120}
2121
2122test "repeat fetchRemove" {
2123 var map: AutoHashMapUnmanaged(u64, void) = .empty;
2124 defer map.deinit(testing.allocator);
2125
2126 try map.ensureTotalCapacity(testing.allocator, 4);
2127
2128 map.putAssumeCapacity(0, {});
2129 map.putAssumeCapacity(1, {});
2130 map.putAssumeCapacity(2, {});
2131 map.putAssumeCapacity(3, {});
2132
2133 // fetchRemove() should make slots available.
2134 var i: usize = 0;
2135 while (i < 10) : (i += 1) {
2136 try testing.expect(map.fetchRemove(3) != null);
2137 map.putAssumeCapacity(3, {});
2138 }
2139
2140 try testing.expect(map.get(0) != null);
2141 try testing.expect(map.get(1) != null);
2142 try testing.expect(map.get(2) != null);
2143 try testing.expect(map.get(3) != null);
2144}
2145
2146test "getOrPut allocation failure" {
2147 var map: std.StringHashMapUnmanaged(void) = .empty;
2148 try testing.expectError(error.OutOfMemory, map.getOrPut(std.testing.failing_allocator, "hello"));
2149}
2150
2151test "rehash" {
2152 var map = AutoHashMap(usize, usize).init(std.testing.allocator);
2153 defer map.deinit();
2154
2155 var prng = std.Random.DefaultPrng.init(0);
2156 const random = prng.random();
2157
2158 const count = 4 * random.intRangeLessThan(u32, 100_000, 500_000);
2159
2160 for (0..count) |i| {
2161 try map.put(i, i);
2162 if (i % 3 == 0) {
2163 try expectEqual(map.remove(i), true);
2164 }
2165 }
2166
2167 map.rehash();
2168
2169 try expectEqual(map.count(), count * 2 / 3);
2170
2171 for (0..count) |i| {
2172 if (i % 3 == 0) {
2173 try expectEqual(map.get(i), null);
2174 } else {
2175 try expectEqual(map.get(i).?, i);
2176 }
2177 }
2178}
2179
2180test "removeByPtr, key is array" {
2181 const gpa = testing.allocator;
2182
2183 var map: AutoHashMapUnmanaged([2]u32, u32) = .empty;
2184 defer map.deinit(gpa);
2185
2186 const key: [2]u32 = .{ 1, 2 };
2187 try map.put(gpa, key, 3);
2188
2189 try expectEqual(1, map.count());
2190 try expectEqual(3, map.get(key));
2191
2192 const key_ptr = map.getKeyPtr(key).?;
2193 map.removeByPtr(key_ptr);
2194
2195 try expectEqual(0, map.count());
2196 try expectEqual(null, map.get(key));
2197}