Skip to content
Standard libraryZig 0.17.0Official documentation
Sourcestd/hash_map.zig

Source line 1

std.hash_map.Alignment

alias

Source line 9

Alias of std.mem.Alignment

std.hash_map.Allocator

alias

Source line 7

Alias of std.mem.Allocator

std.hash_map.assert

alias

Source line 3

Alias of std.debug.assert

std.hash_map.AutoContext

type-function

Source line 54

pub fn AutoContext(comptime K: type) type

Parameters

K: type

std.hash_map.AutoContext.eql

constant

Source line 57

std.hash_map.AutoContext.hash

constant

Source line 56

std.hash_map.autoHash

alias

Source line 4

Alias of std.hash.autoHash

std.hash_map.AutoHashMap

type-function

Source line 46

pub fn AutoHashMap(comptime K: type, comptime V: type) type

Parameters

K: type
V: type

Fields

unmanaged: Unmanaged
allocator: Allocator
ctx: Context

std.hash_map.AutoHashMapUnmanaged

type-function

Source line 50

pub fn AutoHashMapUnmanaged(comptime K: type, comptime V: type) type

Parameters

K: type
V: type

std.hash_map.builtin

constant

Source line 2

std.hash_map.Custom

type-function

Source line 507

fn Custom( comptime K: type, comptime V: type, comptime Context: type, comptime max_load_percentage: u64, ) type

Parameters

K: type
V: type
Context: type
max_load_percentage: u64

Fields

metadata: ?[*]Metadata = null

Pointer to the metadata.

size: Size = 0

Current number of elements in the hashmap.

available: Size = 0

Number of available slots before a grow is needed to satisfy the max_load_percentage.

pointer_stability: std.debug.SafetyLock = .{}

Used to detect memory safety violations.

std.hash_map.Custom.allocate

function

Source line 1462

fn allocate(self: *Self, allocator: Allocator, new_capacity: Size) Allocator.Error!void

Parameters

self: *Self
allocator: Allocator
new_capacity: Size

Errors

OutOfMemory

std.hash_map.Custom.capacity

function

Source line 798

pub fn capacity(self: Self) Size

Parameters

self: Self

std.hash_map.Custom.capacityForSize

function

Source line 737

fn capacityForSize(size: Size) Size

Parameters

size: Size

std.hash_map.Custom.clearAndFree

function

Source line 774

pub fn clearAndFree(self: *Self, allocator: Allocator) void

Parameters

self: *Self
allocator: Allocator

std.hash_map.Custom.clearRetainingCapacity

function

Source line 764

pub fn clearRetainingCapacity(self: *Self) void

Parameters

self: *Self

std.hash_map.Custom.clone

function

Source line 1302

pub fn clone(self: Self, allocator: Allocator) Allocator.Error!Self

Parameters

self: Self
allocator: Allocator

Errors

OutOfMemory

std.hash_map.Custom.cloneContext

function

Source line 1307

pub fn cloneContext(self: Self, allocator: Allocator, new_ctx: anytype) Allocator.Error!HashMapUnmanaged(K, V, @TypeOf(new_ctx), max_load_percentage)

Parameters

self: Self
allocator: Allocator

Errors

OutOfMemory

std.hash_map.Custom.contains

function

Source line 1217

Return true if there is a value associated with key in the map.

pub fn contains(self: Self, key: K) bool

Parameters

self: Self
key: K

std.hash_map.Custom.containsAdapted

function

Source line 1225

pub fn containsAdapted(self: Self, key: anytype, ctx: anytype) bool

Parameters

self: Self

std.hash_map.Custom.containsContext

function

Source line 1222

pub fn containsContext(self: Self, key: K, ctx: Context) bool

Parameters

self: Self
key: K
ctx: Context

std.hash_map.Custom.count

function

Source line 782

pub fn count(self: Self) Size

Parameters

self: Self

std.hash_map.Custom.dbHelper

function

Source line 1525

This function is used in the debugger pretty formatters in lib/lldb/ to fetch the header type to facilitate fancy debug printing for this type.

fn dbHelper(self: *Self, hdr: *Header, entry: *Entry) void

Parameters

self: *Self
hdr: *Header
entry: *Entry

std.hash_map.Custom.deallocate

function

Source line 1496

fn deallocate(self: *Self, allocator: Allocator) void

Parameters

self: *Self
allocator: Allocator

std.hash_map.Custom.deinit

function

Source line 731

pub fn deinit(self: *Self, allocator: Allocator) void

Parameters

self: *Self
allocator: Allocator

std.hash_map.Custom.empty

constant

Source line 545

A map containing no keys or values.

Self

std.hash_map.Custom.ensureTotalCapacity

function

Source line 743

pub fn ensureTotalCapacity(self: *Self, allocator: Allocator, new_size: Size) Allocator.Error!void

Parameters

self: *Self
allocator: Allocator
new_size: Size

Errors

OutOfMemory

std.hash_map.Custom.ensureTotalCapacityContext

function

Source line 748

pub fn ensureTotalCapacityContext(self: *Self, allocator: Allocator, new_size: Size, ctx: Context) Allocator.Error!void

Parameters

self: *Self
allocator: Allocator
new_size: Size
ctx: Context

Errors

OutOfMemory

std.hash_map.Custom.ensureUnusedCapacity

function

Source line 755

pub fn ensureUnusedCapacity(self: *Self, allocator: Allocator, additional_size: Size) Allocator.Error!void

Parameters

self: *Self
allocator: Allocator
additional_size: Size

Errors

OutOfMemory

std.hash_map.Custom.ensureUnusedCapacityContext

function

Source line 760

pub fn ensureUnusedCapacityContext(self: *Self, allocator: Allocator, additional_size: Size, ctx: Context) Allocator.Error!void

Parameters

self: *Self
allocator: Allocator
additional_size: Size
ctx: Context

Errors

OutOfMemory

std.hash_map.Custom.Entry

container

Source line 558

Fields

key_ptr: *K
value_ptr: *V

std.hash_map.Custom.fetchPut

function

Source line 900

Inserts a new Entry into the hash map, returning the previous one, if any.

pub fn fetchPut(self: *Self, allocator: Allocator, key: K, value: V) Allocator.Error!?KV

Parameters

self: *Self
allocator: Allocator
key: K
value: V

Errors

OutOfMemory

std.hash_map.Custom.fetchPutAssumeCapacity

function

Source line 920

Inserts a new Entry into the hash map, returning the previous one, if any. If insertion happens, asserts there is enough capacity without allocating.

pub fn fetchPutAssumeCapacity(self: *Self, key: K, value: V) ?KV

Parameters

self: *Self
key: K
value: V

std.hash_map.Custom.fetchPutAssumeCapacityContext

function

Source line 925

pub fn fetchPutAssumeCapacityContext(self: *Self, key: K, value: V, ctx: Context) ?KV

Parameters

self: *Self
key: K
value: V
ctx: Context

std.hash_map.Custom.fetchPutContext

function

Source line 905

pub fn fetchPutContext(self: *Self, allocator: Allocator, key: K, value: V, ctx: Context) Allocator.Error!?KV

Parameters

self: *Self
allocator: Allocator
key: K
value: V
ctx: Context

Errors

OutOfMemory

std.hash_map.Custom.fetchRemove

function

Source line 940

If there is an Entry with a matching key, it is deleted from the hash map, and then returned from this function.

pub fn fetchRemove(self: *Self, key: K) ?KV

Parameters

self: *Self
key: K

std.hash_map.Custom.fetchRemoveAdapted

function

Source line 948

pub fn fetchRemoveAdapted(self: *Self, key: anytype, ctx: anytype) ?KV

Parameters

self: *Self

std.hash_map.Custom.fetchRemoveContext

function

Source line 945

pub fn fetchRemoveContext(self: *Self, key: K, ctx: Context) ?KV

Parameters

self: *Self
key: K
ctx: Context

std.hash_map.Custom.FieldIterator

type-function

Source line 665

fn FieldIterator(comptime T: type) type

Parameters

T: type

Fields

len: usize
metadata: [*]const Metadata
items: [*]T

std.hash_map.Custom.FieldIterator.next

function

Source line 671

pub fn next(self: *@This()) ?*T

Parameters

self: *@This()

std.hash_map.Custom.get

function

Source line 1082

Get a copy of the value associated with key, if present.

pub fn get(self: Self, key: K) ?V

Parameters

self: Self
key: K

std.hash_map.Custom.getAdapted

function

Source line 1090

pub fn getAdapted(self: Self, key: anytype, ctx: anytype) ?V

Parameters

self: Self

std.hash_map.Custom.getContext

function

Source line 1087

pub fn getContext(self: Self, key: K, ctx: Context) ?V

Parameters

self: Self
key: K
ctx: Context

std.hash_map.Custom.getEntry

function

Source line 1004

pub fn getEntry(self: Self, key: K) ?Entry

Parameters

self: Self
key: K

std.hash_map.Custom.getEntryAdapted

function

Source line 1012

pub fn getEntryAdapted(self: Self, key: anytype, ctx: anytype) ?Entry

Parameters

self: Self

std.hash_map.Custom.getEntryContext

function

Source line 1009

pub fn getEntryContext(self: Self, key: K, ctx: Context) ?Entry

Parameters

self: Self
key: K
ctx: Context

std.hash_map.Custom.getIndex

function

Source line 968

Find the index containing the data for the given key.

fn getIndex(self: Self, key: anytype, ctx: anytype) ?usize

Parameters

self: Self

std.hash_map.Custom.getKey

function

Source line 1050

Get a copy of the actual key associated with adapted key, if present.

pub fn getKey(self: Self, key: K) ?K

Parameters

self: Self
key: K

std.hash_map.Custom.getKeyAdapted

function

Source line 1058

pub fn getKeyAdapted(self: Self, key: anytype, ctx: anytype) ?K

Parameters

self: Self

std.hash_map.Custom.getKeyContext

function

Source line 1055

pub fn getKeyContext(self: Self, key: K, ctx: Context) ?K

Parameters

self: Self
key: K
ctx: Context

std.hash_map.Custom.getKeyPtr

function

Source line 1034

Get an optional pointer to the actual key associated with adapted key, if present.

pub fn getKeyPtr(self: Self, key: K) ?*K

Parameters

self: Self
key: K

std.hash_map.Custom.getKeyPtrAdapted

function

Source line 1042

pub fn getKeyPtrAdapted(self: Self, key: anytype, ctx: anytype) ?*K

Parameters

self: Self

std.hash_map.Custom.getKeyPtrContext

function

Source line 1039

pub fn getKeyPtrContext(self: Self, key: K, ctx: Context) ?*K

Parameters

self: Self
key: K
ctx: Context

std.hash_map.Custom.getOrPut

function

Source line 1097

pub fn getOrPut(self: *Self, allocator: Allocator, key: K) Allocator.Error!GetOrPutResult

Parameters

self: *Self
allocator: Allocator
key: K

Errors

OutOfMemory

std.hash_map.Custom.getOrPutAdapted

function

Source line 1109

pub fn getOrPutAdapted(self: *Self, allocator: Allocator, key: anytype, key_ctx: anytype) Allocator.Error!GetOrPutResult

Parameters

self: *Self
allocator: Allocator

Errors

OutOfMemory

std.hash_map.Custom.getOrPutAssumeCapacity

function

Source line 1133

pub fn getOrPutAssumeCapacity(self: *Self, key: K) GetOrPutResult

Parameters

self: *Self
key: K

std.hash_map.Custom.getOrPutAssumeCapacityAdapted

function

Source line 1145

pub fn getOrPutAssumeCapacityAdapted(self: *Self, key: anytype, ctx: anytype) GetOrPutResult

Parameters

self: *Self

std.hash_map.Custom.getOrPutAssumeCapacityContext

function

Source line 1138

pub fn getOrPutAssumeCapacityContext(self: *Self, key: K, ctx: Context) GetOrPutResult

Parameters

self: *Self
key: K
ctx: Context

std.hash_map.Custom.getOrPutContext

function

Source line 1102

pub fn getOrPutContext(self: *Self, allocator: Allocator, key: K, ctx: Context) Allocator.Error!GetOrPutResult

Parameters

self: *Self
allocator: Allocator
key: K
ctx: Context

Errors

OutOfMemory

std.hash_map.Custom.getOrPutContextAdapted

function

Source line 1114

pub fn getOrPutContextAdapted(self: *Self, allocator: Allocator, key: anytype, key_ctx: anytype, ctx: Context) Allocator.Error!GetOrPutResult

Parameters

self: *Self
allocator: Allocator
ctx: Context

Errors

OutOfMemory

std.hash_map.Custom.GetOrPutResult

container

Source line 687

Fields

key_ptr: *K
value_ptr: *V
found_existing: bool

std.hash_map.Custom.getOrPutValue

function

Source line 1202

pub fn getOrPutValue(self: *Self, allocator: Allocator, key: K, value: V) Allocator.Error!Entry

Parameters

self: *Self
allocator: Allocator
key: K
value: V

Errors

OutOfMemory

std.hash_map.Custom.getOrPutValueContext

function

Source line 1207

pub fn getOrPutValueContext(self: *Self, allocator: Allocator, key: K, value: V, ctx: Context) Allocator.Error!Entry

Parameters

self: *Self
allocator: Allocator
key: K
value: V
ctx: Context

Errors

OutOfMemory

std.hash_map.Custom.getPtr

function

Source line 1066

Get an optional pointer to the value associated with key, if present.

pub fn getPtr(self: Self, key: K) ?*V

Parameters

self: Self
key: K

std.hash_map.Custom.getPtrAdapted

function

Source line 1074

pub fn getPtrAdapted(self: Self, key: anytype, ctx: anytype) ?*V

Parameters

self: Self

std.hash_map.Custom.getPtrContext

function

Source line 1071

pub fn getPtrContext(self: Self, key: K, ctx: Context) ?*V

Parameters

self: Self
key: K
ctx: Context

std.hash_map.Custom.grow

function

Source line 1430

fn grow(self: *Self, allocator: Allocator, new_capacity: Size, ctx: Context) Allocator.Error!void

Parameters

self: *Self
allocator: Allocator
new_capacity: Size
ctx: Context

Errors

OutOfMemory

std.hash_map.Custom.growIfNeeded

function

Source line 1296

fn growIfNeeded(self: *Self, allocator: Allocator, new_count: Size, ctx: Context) Allocator.Error!void

Parameters

self: *Self
allocator: Allocator
new_count: Size
ctx: Context

Errors

OutOfMemory

std.hash_map.Custom.Hash

type

Source line 556

std.hash_map.Custom.header

function

Source line 786

fn header(self: Self) *Header

Parameters

self: Self

std.hash_map.Custom.Header

container

Source line 568

Fields

values: [*]V
keys: [*]K
capacity: Size

std.hash_map.Custom.initMetadatas

function

Source line 1284

fn initMetadatas(self: *Self) void

Parameters

self: *Self

std.hash_map.Custom.isUnderMaxLoadPercentage

function

Source line 727

fn isUnderMaxLoadPercentage(size: Size, cap: Size) bool

Parameters

size: Size
cap: Size

std.hash_map.Custom.iterator

function

Source line 804

pub fn iterator(self: *const Self) Iterator

Parameters

self: *const Self

std.hash_map.Custom.Iterator

container

Source line 634

Fields

hm: *const Self
index: Size = 0

std.hash_map.Custom.Iterator.next

function

Source line 638

pub fn next(it: *Iterator) ?Entry

Parameters

it: *Iterator

std.hash_map.Custom.keyIterator

function

Source line 808

pub fn keyIterator(self: Self) KeyIterator

Parameters

self: Self

std.hash_map.Custom.KeyIterator

type

Source line 662

std.hash_map.Custom.keys

function

Source line 790

fn keys(self: Self) [*]K

Parameters

self: Self

std.hash_map.Custom.KV

container

Source line 563

Fields

key: K
value: V

std.hash_map.Custom.load

function

Source line 1290

fn load(self: Self) Size

Parameters

self: Self

std.hash_map.Custom.lockPointers

function

Source line 718

Puts the hash map into a state where any method call that would cause an existing key or value pointer to become invalidated will instead trigger an assertion.

lockPointers may be called multiple times. This allows multiple independent users of the hash map to keep it locked simultaneously.

unlockPointers restores the hash map to its previous state when called the same number of times as lockPointers.

pub fn lockPointers(self: *Self) void

Parameters

self: *Self

std.hash_map.Custom.Managed

type

Source line 693

std.hash_map.Custom.Metadata

container

Source line 588

Metadata for a slot. It can be in three states: empty, used or tombstone. Tombstones indicate that an entry was previously used, they are a simple way to handle removal. To this state, we add 7 bits from the slot's key hash. These are used as a fast way to disambiguate between entries without having to use the equality function. If two fingerprints are different, we know that we don't have to compare the keys at all. The 7 bits are the highest ones from a 64 bit hash. This way, not only we use the log2(capacity) lowest bits from the hash to determine a slot index, but we use 7 more bits to quickly resolve collisions when multiple elements with different hashes end up wanting to be in the same slot. Not using the equality function means we don't have to read into the entries array, likely avoiding a cache miss and a potentially costly function call.

Fields

fingerprint: FingerPrint = free
used: u1 = 0

std.hash_map.Custom.Metadata.fill

function

Source line 618

pub fn fill(self: *Metadata, fp: FingerPrint) void

Parameters

self: *Metadata
fp: FingerPrint

std.hash_map.Custom.Metadata.FingerPrint

type

Source line 589

std.hash_map.Custom.Metadata.free

constant

Source line 591

FingerPrint

std.hash_map.Custom.Metadata.isFree

function

Source line 608

pub fn isFree(self: Metadata) bool

Parameters

self: Metadata

std.hash_map.Custom.Metadata.isTombstone

function

Source line 604

pub fn isTombstone(self: Metadata) bool

Parameters

self: Metadata

std.hash_map.Custom.Metadata.isUsed

function

Source line 600

pub fn isUsed(self: Metadata) bool

Parameters

self: Metadata

std.hash_map.Custom.Metadata.remove

function

Source line 623

pub fn remove(self: *Metadata) void

Parameters

self: *Metadata

std.hash_map.Custom.Metadata.slot_free

constant

Source line 597

u8

std.hash_map.Custom.Metadata.slot_tombstone

constant

Source line 598

u8

std.hash_map.Custom.Metadata.takeFingerprint

function

Source line 612

pub fn takeFingerprint(hash: Hash) FingerPrint

Parameters

hash: Hash

std.hash_map.Custom.Metadata.tombstone

constant

Source line 592

FingerPrint

std.hash_map.Custom.minimal_capacity

constant

Source line 542

Capacity of the first grow when bootstrapping the hashmap.

std.hash_map.Custom.move

function

Source line 1334

Set the map to an empty state, making deinitialization a no-op, and returning a copy of the original.

pub fn move(self: *Self) Self

Parameters

self: *Self

std.hash_map.Custom.promote

function

Source line 695

pub fn promote(self: Self, allocator: Allocator) Managed

Parameters

self: Self
allocator: Allocator

std.hash_map.Custom.promoteContext

function

Source line 701

pub fn promoteContext(self: Self, allocator: Allocator, ctx: Context) Managed

Parameters

self: Self
allocator: Allocator
ctx: Context

std.hash_map.Custom.put

function

Source line 1023

Insert an entry if the associated key is not already present, otherwise update preexisting value.

pub fn put(self: *Self, allocator: Allocator, key: K, value: V) Allocator.Error!void

Parameters

self: *Self
allocator: Allocator
key: K
value: V

Errors

OutOfMemory

std.hash_map.Custom.putAssumeCapacity

function

Source line 858

Asserts there is enough capacity to store the new key-value pair. Clobbers any existing data. To detect if a put would clobber existing data, see getOrPutAssumeCapacity.

pub fn putAssumeCapacity(self: *Self, key: K, value: V) void

Parameters

self: *Self
key: K
value: V

std.hash_map.Custom.putAssumeCapacityContext

function

Source line 863

pub fn putAssumeCapacityContext(self: *Self, key: K, value: V, ctx: Context) void

Parameters

self: *Self
key: K
value: V
ctx: Context

std.hash_map.Custom.putAssumeCapacityNoClobber

function

Source line 870

Insert an entry in the map. Assumes it is not already present, and that no allocation is needed.

pub fn putAssumeCapacityNoClobber(self: *Self, key: K, value: V) void

Parameters

self: *Self
key: K
value: V

std.hash_map.Custom.putAssumeCapacityNoClobberContext

function

Source line 875

pub fn putAssumeCapacityNoClobberContext(self: *Self, key: K, value: V, ctx: Context) void

Parameters

self: *Self
key: K
value: V
ctx: Context

std.hash_map.Custom.putContext

function

Source line 1028

pub fn putContext(self: *Self, allocator: Allocator, key: K, value: V, ctx: Context) Allocator.Error!void

Parameters

self: *Self
allocator: Allocator
key: K
value: V
ctx: Context

Errors

OutOfMemory

std.hash_map.Custom.putNoClobber

function

Source line 841

Insert an entry in the map. Assumes it is not already present.

pub fn putNoClobber(self: *Self, allocator: Allocator, key: K, value: V) Allocator.Error!void

Parameters

self: *Self
allocator: Allocator
key: K
value: V

Errors

OutOfMemory

std.hash_map.Custom.putNoClobberContext

function

Source line 846

pub fn putNoClobberContext(self: *Self, allocator: Allocator, key: K, value: V, ctx: Context) Allocator.Error!void

Parameters

self: *Self
allocator: Allocator
key: K
value: V
ctx: Context

Errors

OutOfMemory

std.hash_map.Custom.rehash

function

Source line 1352

Rehash the map, in-place.

Over time, due to the current tombstone-based implementation, a HashMap could become fragmented due to the buildup of tombstone entries that causes a performance degradation due to excessive probing. The kind of pattern that might cause this is a long-lived HashMap with repeated inserts and deletes.

After this function is called, there will be no tombstones in the HashMap, each of the entries is rehashed and any existing key/value pointers into the HashMap are invalidated.

pub fn rehash(self: *Self, ctx: anytype) void

Parameters

self: *Self

std.hash_map.Custom.remove

function

Source line 1243

If there is an Entry with a matching key, it is deleted from the hash map, and this function returns true. Otherwise this function returns false.

TODO: answer the question in these doc comments, does this increase the unused capacity by one?

pub fn remove(self: *Self, key: K) bool

Parameters

self: *Self
key: K

std.hash_map.Custom.removeAdapted

function

Source line 1257

TODO: answer the question in these doc comments, does this increase the unused capacity by one?

pub fn removeAdapted(self: *Self, key: anytype, ctx: anytype) bool

Parameters

self: *Self

std.hash_map.Custom.removeByIndex

function

Source line 1229

fn removeByIndex(self: *Self, idx: usize) void

Parameters

self: *Self
idx: usize

std.hash_map.Custom.removeByPtr

function

Source line 1272

Delete the entry with key pointed to by key_ptr from the hash map. key_ptr is assumed to be a valid pointer to a key that is present in the hash map.

TODO: answer the question in these doc comments, does this increase the unused capacity by one?

pub fn removeByPtr(self: *Self, key_ptr: *K) void

Parameters

self: *Self
key_ptr: *K

std.hash_map.Custom.removeContext

function

Source line 1251

TODO: answer the question in these doc comments, does this increase the unused capacity by one?

pub fn removeContext(self: *Self, key: K, ctx: Context) bool

Parameters

self: *Self
key: K
ctx: Context

std.hash_map.Custom.Self

alias

Source line 516

Alias of std.hash_map.Custom

std.hash_map.Custom.Size

type

Source line 552

std.hash_map.Custom.unlockPointers

function

Source line 723

Undoes one call to lockPointers.

pub fn unlockPointers(self: *Self) void

Parameters

self: *Self

std.hash_map.Custom.valueIterator

function

Source line 824

pub fn valueIterator(self: Self) ValueIterator

Parameters

self: Self

std.hash_map.Custom.ValueIterator

type

Source line 663

std.hash_map.Custom.values

function

Source line 794

fn values(self: Self) [*]V

Parameters

self: Self

std.hash_map.default_max_load_percentage

constant

Source line 118

std.hash_map.eql

function

Source line 2020

fn eql(self: @This(), adapted_key: []const u8, test_key: u64) bool

Parameters

self: @This()
adapted_key: []const u8
test_key: u64

std.hash_map.eqlString

function

Source line 85

pub fn eqlString(a: []const u8, b: []const u8) bool

Parameters

a: []const u8
b: []const u8

std.hash_map.expect

alias

Source line 1542

Alias of std.testing.expect

std.hash_map.expectEqual

alias

Source line 1543

Alias of std.testing.expectEqual

std.hash_map.getAutoEqlFn

function

Source line 37

pub fn getAutoEqlFn(comptime K: type, comptime Context: type) (fn (Context, K, K) bool)

Parameters

K: type
Context: type

std.hash_map.getAutoEqlFn.eql

function

Source line 39

fn eql(ctx: Context, a: K, b: K) bool

Parameters

ctx: Context
a: K
b: K

std.hash_map.getAutoHashFn

function

Source line 11

pub fn getAutoHashFn(comptime K: type, comptime Context: type) (fn (Context, K) u64)

Parameters

K: type
Context: type

std.hash_map.getAutoHashFn.hash

function

Source line 24

fn hash(ctx: Context, key: K) u64

Parameters

ctx: Context
key: K

std.hash_map.hash

function

Source line 2024

fn hash(self: @This(), adapted_key: []const u8) u64

Parameters

self: @This()
adapted_key: []const u8

std.hash_map.HashMap

type-function

Source line 135

General purpose hash table. No order is guaranteed and any modification invalidates live iterators. It provides fast operations (lookup, insertion, deletion) with quite high load factors (up to 80% by default) for low memory usage. For a hash map that can be initialized directly that does not store an Allocator field, see HashMapUnmanaged. If iterating over the table entries is a strong usecase and needs to be fast, prefer the alternative std.ArrayHashMap. Context must be a struct type with two member functions: hash(self, K) u64 eql(self, K, K) bool Adapted variants of many functions are provided. These variants take a pseudo key instead of a key. Their context must have the functions: hash(self, PseudoKey) u64 eql(self, PseudoKey, K) bool

pub fn HashMap( comptime K: type, comptime V: type, comptime Context: type, comptime max_load_percentage: u64, ) type

Parameters

K: type
V: type
Context: type
max_load_percentage: u64

Fields

unmanaged: Unmanaged
allocator: Allocator
ctx: Context

std.hash_map.HashMap.capacity

function

Source line 317

Returns the number of total elements which may be present before it is no longer guaranteed that no allocations will be performed.

pub fn capacity(self: Self) Size

Parameters

self: Self

std.hash_map.HashMap.clearAndFree

function

Source line 229

Empty the map and release the backing allocation. This does not free keys or values! Be sure to release them if they need deinitialization before calling this function.

pub fn clearAndFree(self: *Self) void

Parameters

self: *Self

std.hash_map.HashMap.clearRetainingCapacity

function

Source line 221

Empty the map, but keep the backing allocation for future use. This does not free keys or values! Be sure to release them if they need deinitialization before calling this function.

pub fn clearRetainingCapacity(self: *Self) void

Parameters

self: *Self

std.hash_map.HashMap.clone

function

Source line 442

Creates a copy of this map, using the same allocator

pub fn clone(self: Self) Allocator.Error!Self

Parameters

self: Self

Errors

OutOfMemory

std.hash_map.HashMap.cloneWithAllocator

function

Source line 448

Creates a copy of this map, using a specified allocator

pub fn cloneWithAllocator(self: Self, new_allocator: Allocator) Allocator.Error!Self

Parameters

self: Self
new_allocator: Allocator

Errors

OutOfMemory

std.hash_map.HashMap.cloneWithAllocatorAndContext

function

Source line 460

Creates a copy of this map, using a specified allocator and context.

pub fn cloneWithAllocatorAndContext( self: Self, new_allocator: Allocator, new_ctx: anytype, ) Allocator.Error!HashMap(K, V, @TypeOf(new_ctx), max_load_percentage)

Parameters

self: Self
new_allocator: Allocator

Errors

OutOfMemory

std.hash_map.HashMap.cloneWithContext

function

Source line 454

Creates a copy of this map, using a specified context

pub fn cloneWithContext(self: Self, new_ctx: anytype) Allocator.Error!HashMap(K, V, @TypeOf(new_ctx), max_load_percentage)

Parameters

self: Self

Errors

OutOfMemory

std.hash_map.HashMap.contains

function

Source line 407

Check if the map contains a key

pub fn contains(self: Self, key: K) bool

Parameters

self: Self
key: K

std.hash_map.HashMap.containsAdapted

function

Source line 411

pub fn containsAdapted(self: Self, key: anytype, ctx: anytype) bool

Parameters

self: Self

std.hash_map.HashMap.count

function

Source line 234

Return the number of items in the map.

pub fn count(self: Self) Size

Parameters

self: Self

std.hash_map.HashMap.deinit

function

Source line 212

Release the backing array and invalidate this map. This does not deinit keys, values, or the context! If your keys or values need to be released, ensure that that is done before calling this function.

pub fn deinit(self: *Self) void

Parameters

self: *Self

std.hash_map.HashMap.ensureTotalCapacity

function

Source line 304

Increases capacity, guaranteeing that insertions up until the expected_count will not cause an allocation, and therefore cannot fail.

pub fn ensureTotalCapacity(self: *Self, expected_count: Size) Allocator.Error!void

Parameters

self: *Self
expected_count: Size

Errors

OutOfMemory

std.hash_map.HashMap.ensureUnusedCapacity

function

Source line 311

Increases capacity, guaranteeing that insertions up until additional_count more items will not cause an allocation, and therefore cannot fail.

pub fn ensureUnusedCapacity(self: *Self, additional_count: Size) Allocator.Error!void

Parameters

self: *Self
additional_count: Size

Errors

OutOfMemory

std.hash_map.HashMap.Entry

constant

Source line 149

An entry, containing pointers to a key and value stored in the map

std.hash_map.HashMap.fetchPut

function

Source line 348

Inserts a new Entry into the hash map, returning the previous one, if any.

pub fn fetchPut(self: *Self, key: K, value: V) Allocator.Error!?KV

Parameters

self: *Self
key: K
value: V

Errors

OutOfMemory

std.hash_map.HashMap.fetchPutAssumeCapacity

function

Source line 354

Inserts a new Entry into the hash map, returning the previous one, if any. If insertion happens, asserts there is enough capacity without allocating.

pub fn fetchPutAssumeCapacity(self: *Self, key: K, value: V) ?KV

Parameters

self: *Self
key: K
value: V

std.hash_map.HashMap.fetchRemove

function

Source line 359

Removes a value from the map and returns the removed kv pair.

pub fn fetchRemove(self: *Self, key: K) ?KV

Parameters

self: *Self
key: K

std.hash_map.HashMap.fetchRemoveAdapted

function

Source line 363

pub fn fetchRemoveAdapted(self: *Self, key: anytype, ctx: anytype) ?KV

Parameters

self: *Self

std.hash_map.HashMap.get

function

Source line 368

Finds the value associated with a key in the map

pub fn get(self: Self, key: K) ?V

Parameters

self: Self
key: K

std.hash_map.HashMap.getAdapted

function

Source line 371

pub fn getAdapted(self: Self, key: anytype, ctx: anytype) ?V

Parameters

self: Self

std.hash_map.HashMap.getEntry

function

Source line 398

Finds the key and value associated with a key in the map

pub fn getEntry(self: Self, key: K) ?Entry

Parameters

self: Self
key: K

std.hash_map.HashMap.getEntryAdapted

function

Source line 402

pub fn getEntryAdapted(self: Self, key: anytype, ctx: anytype) ?Entry

Parameters

self: Self

std.hash_map.HashMap.getKey

function

Source line 383

Finds the actual key associated with an adapted key in the map

pub fn getKey(self: Self, key: K) ?K

Parameters

self: Self
key: K

std.hash_map.HashMap.getKeyAdapted

function

Source line 386

pub fn getKeyAdapted(self: Self, key: anytype, ctx: anytype) ?K

Parameters

self: Self

std.hash_map.HashMap.getKeyPtr

function

Source line 390

pub fn getKeyPtr(self: Self, key: K) ?*K

Parameters

self: Self
key: K

std.hash_map.HashMap.getKeyPtrAdapted

function

Source line 393

pub fn getKeyPtrAdapted(self: Self, key: anytype, ctx: anytype) ?*K

Parameters

self: Self

std.hash_map.HashMap.getOrPut

function

Source line 262

If key exists this function cannot fail. If there is an existing item with key, then the result's Entry pointers point to it, and found_existing is true. Otherwise, puts a new item with undefined value, and the Entry pointers point to it. Caller should then initialize the value (but not the key).

pub fn getOrPut(self: *Self, key: K) Allocator.Error!GetOrPutResult

Parameters

self: *Self
key: K

Errors

OutOfMemory

std.hash_map.HashMap.getOrPutAdapted

function

Source line 272

If key exists this function cannot fail. If there is an existing item with key, then the result's Entry pointers point to it, and found_existing is true. Otherwise, puts a new item with undefined key and value, and the Entry pointers point to it. Caller must then initialize the key and value.

pub fn getOrPutAdapted(self: *Self, key: anytype, ctx: anytype) Allocator.Error!GetOrPutResult

Parameters

self: *Self

Errors

OutOfMemory

std.hash_map.HashMap.getOrPutAssumeCapacity

function

Source line 283

If there is an existing item with key, then the result's Entry pointers point to it, and found_existing is true. Otherwise, puts a new item with undefined value, and the Entry pointers point to it. Caller should then initialize the value (but not the key). If a new entry needs to be stored, this function asserts there is enough capacity to store it.

pub fn getOrPutAssumeCapacity(self: *Self, key: K) GetOrPutResult

Parameters

self: *Self
key: K

std.hash_map.HashMap.getOrPutAssumeCapacityAdapted

function

Source line 294

If there is an existing item with key, then the result's Entry pointers point to it, and found_existing is true. Otherwise, puts a new item with undefined value, and the Entry pointers point to it. Caller must then initialize the key and value. If a new entry needs to be stored, this function asserts there is enough capacity to store it.

pub fn getOrPutAssumeCapacityAdapted(self: *Self, key: anytype, ctx: anytype) GetOrPutResult

Parameters

self: *Self

std.hash_map.HashMap.GetOrPutResult

constant

Source line 163

The type returned from getOrPut and variants

std.hash_map.HashMap.getOrPutValue

function

Source line 298

pub fn getOrPutValue(self: *Self, key: K, value: V) Allocator.Error!Entry

Parameters

self: *Self
key: K
value: V

Errors

OutOfMemory

std.hash_map.HashMap.getPtr

function

Source line 375

pub fn getPtr(self: Self, key: K) ?*V

Parameters

self: Self
key: K

std.hash_map.HashMap.getPtrAdapted

function

Source line 378

pub fn getPtrAdapted(self: Self, key: anytype, ctx: anytype) ?*V

Parameters

self: Self

std.hash_map.HashMap.Hash

constant

Source line 153

The integer type that is the result of hashing

std.hash_map.HashMap.init

function

Source line 170

Create a managed hash map with an empty context. If the context is not zero-sized, you must use initContext(allocator, ctx) instead.

pub fn init(allocator: Allocator) Self

Parameters

allocator: Allocator

std.hash_map.HashMap.initContext

function

Source line 182

Create a managed hash map with a context

pub fn initContext(allocator: Allocator, ctx: Context) Self

Parameters

allocator: Allocator
ctx: Context

std.hash_map.HashMap.iterator

function

Source line 240

Create an iterator over the entries in the map. The iterator is invalidated if the map is modified.

pub fn iterator(self: *const Self) Iterator

Parameters

self: *const Self

std.hash_map.HashMap.Iterator

constant

Source line 155

The iterator type returned by iterator()

std.hash_map.HashMap.keyIterator

function

Source line 246

Create an iterator over the keys in the map. The iterator is invalidated if the map is modified.

pub fn keyIterator(self: Self) KeyIterator

Parameters

self: Self

std.hash_map.HashMap.KeyIterator

constant

Source line 157

std.hash_map.HashMap.KV

constant

Source line 151

A copy of a key and value which are no longer in the map

std.hash_map.HashMap.lockPointers

function

Source line 199

Puts the hash map into a state where any method call that would cause an existing key or value pointer to become invalidated will instead trigger an assertion.

lockPointers may be called multiple times. This allows multiple independent users of the hash map to keep it locked simultaneously.

unlockPointers restores the hash map to its previous state when called the same number of times as lockPointers.

pub fn lockPointers(self: *Self) void

Parameters

self: *Self

std.hash_map.HashMap.move

function

Source line 471

Set the map to an empty state, making deinitialization a no-op, and returning a copy of the original.

pub fn move(self: *Self) Self

Parameters

self: *Self

std.hash_map.HashMap.put

function

Source line 323

Clobbers any existing data. To detect if a put would clobber existing data, see getOrPut.

pub fn put(self: *Self, key: K, value: V) Allocator.Error!void

Parameters

self: *Self
key: K
value: V

Errors

OutOfMemory

std.hash_map.HashMap.putAssumeCapacity

function

Source line 336

Asserts there is enough capacity to store the new key-value pair. Clobbers any existing data. To detect if a put would clobber existing data, see getOrPutAssumeCapacity.

pub fn putAssumeCapacity(self: *Self, key: K, value: V) void

Parameters

self: *Self
key: K
value: V

std.hash_map.HashMap.putAssumeCapacityNoClobber

function

Source line 343

Asserts there is enough capacity to store the new key-value pair. Asserts that it does not clobber any existing data. To detect if a put would clobber existing data, see getOrPutAssumeCapacity.

pub fn putAssumeCapacityNoClobber(self: *Self, key: K, value: V) void

Parameters

self: *Self
key: K
value: V

std.hash_map.HashMap.putNoClobber

function

Source line 329

Inserts a key-value pair into the hash map, asserting that no previous entry with the same key is already present

pub fn putNoClobber(self: *Self, key: K, value: V) Allocator.Error!void

Parameters

self: *Self
key: K
value: V

Errors

OutOfMemory

std.hash_map.HashMap.rehash

function

Source line 489

Rehash the map, in-place.

Over time, due to the current tombstone-based implementation, a HashMap could become fragmented due to the buildup of tombstone entries that causes a performance degradation due to excessive probing. The kind of pattern that might cause this is a long-lived HashMap with repeated inserts and deletes.

After this function is called, there will be no tombstones in the HashMap, each of the entries is rehashed and any existing key/value pointers into the HashMap are invalidated.

pub fn rehash(self: *Self) void

Parameters

self: *Self

std.hash_map.HashMap.remove

function

Source line 421

If there is an Entry with a matching key, it is deleted from the hash map, and this function returns true. Otherwise this function returns false.

TODO: answer the question in these doc comments, does this increase the unused capacity by one?

pub fn remove(self: *Self, key: K) bool

Parameters

self: *Self
key: K

std.hash_map.HashMap.removeAdapted

function

Source line 427

TODO: answer the question in these doc comments, does this increase the unused capacity by one?

pub fn removeAdapted(self: *Self, key: anytype, ctx: anytype) bool

Parameters

self: *Self

std.hash_map.HashMap.removeByPtr

function

Source line 437

Delete the entry with key pointed to by key_ptr from the hash map. key_ptr is assumed to be a valid pointer to a key that is present in the hash map.

TODO: answer the question in these doc comments, does this increase the unused capacity by one?

pub fn removeByPtr(self: *Self, key_ptr: *K) void

Parameters

self: *Self
key_ptr: *K

std.hash_map.HashMap.Self

alias

Source line 165

Alias of std.hash_map.HashMap

std.hash_map.HashMap.Size

constant

Source line 161

The integer type used to store the size of the map

std.hash_map.HashMap.unlockPointers

function

Source line 204

Undoes one call to lockPointers.

pub fn unlockPointers(self: *Self) void

Parameters

self: *Self

std.hash_map.HashMap.Unmanaged

type

Source line 147

The type of the unmanaged hash map underlying this wrapper

std.hash_map.HashMap.valueIterator

function

Source line 252

Create an iterator over the values in the map. The iterator is invalidated if the map is modified.

pub fn valueIterator(self: Self) ValueIterator

Parameters

self: Self

std.hash_map.HashMap.ValueIterator

constant

Source line 158

std.hash_map.HashMapUnmanaged

alias

Source line 506

A HashMap based on open addressing and linear probing. A lookup or modification typically incurs only 2 cache misses. No order is guaranteed and any modification invalidates live iterators. It achieves good performance with quite high load factors (by default, grow is triggered at 80% full) and only one byte of overhead per element. The struct itself is only 16 bytes for a small footprint. This comes at the price of handling size with u32, which should be reasonable enough for almost all uses. Deletions are achieved with tombstones.

Default initialization of this struct is deprecated; use .empty instead.

Alias of std.hash_map.Custom

std.hash_map.hashString

function

Source line 89

pub fn hashString(s: []const u8) u64

Parameters

s: []const u8

std.hash_map.math

alias

Source line 5

Alias of std.math

std.hash_map.mem

alias

Source line 6

Alias of std.mem

std.hash_map.std

alias

Source line 1

Alias of std

std.hash_map.StringContext

namespace

Source line 74

std.hash_map.StringContext.eql

function

Source line 79

pub fn eql(self: @This(), a: []const u8, b: []const u8) bool

Parameters

self: @This()
a: []const u8
b: []const u8

std.hash_map.StringContext.hash

function

Source line 75

pub fn hash(self: @This(), s: []const u8) u64

Parameters

self: @This()
s: []const u8

std.hash_map.StringHashMap

type-function

Source line 64

Builtin hashmap for strings as keys. Key memory is managed by the caller. Keys and values will not automatically be freed.

pub fn StringHashMap(comptime V: type) type

Parameters

V: type

Fields

unmanaged: Unmanaged
allocator: Allocator
ctx: Context

std.hash_map.StringHashMapUnmanaged

type-function

Source line 70

Key memory is managed by the caller. Keys and values will not automatically be freed.

pub fn StringHashMapUnmanaged(comptime V: type) type

Parameters

V: type

std.hash_map.StringIndexAdapter

container

Source line 105

Fields

bytes: *const std.ArrayList(u8)

std.hash_map.StringIndexAdapter.eql

function

Source line 108

pub fn eql(ctx: @This(), a: []const u8, b: u32) bool

Parameters

ctx: @This()
a: []const u8
b: u32

std.hash_map.StringIndexAdapter.hash

function

Source line 112

pub fn hash(_: @This(), adapted_key: []const u8) u64

Parameters

_: @This()
adapted_key: []const u8

std.hash_map.StringIndexContext

container

Source line 93

Fields

bytes: *const std.ArrayList(u8)

std.hash_map.StringIndexContext.eql

function

Source line 96

pub fn eql(_: @This(), a: u32, b: u32) bool

Parameters

_: @This()
a: u32
b: u32

std.hash_map.StringIndexContext.hash

function

Source line 100

pub fn hash(ctx: @This(), key: u32) u64

Parameters

ctx: @This()
key: u32

std.hash_map.testing

alias

Source line 1541

Alias of std.testing

std.hash_map.Wyhash

alias

Source line 8

Alias of std.hash.Wyhash

Source code

std/hash_map.zig

const std = @import("std.zig");
const builtin = @import("builtin");
const assert = std.debug.assert;
const autoHash = std.hash.autoHash;
const math = std.math;
const mem = std.mem;
const Allocator = mem.Allocator;
const Wyhash = std.hash.Wyhash;
const Alignment = std.mem.Alignment;

pub fn getAutoHashFn(comptime K: type, comptime Context: type) (fn (Context, K) u64) {
    comptime {
        assert(@hasDecl(std, "StringHashMap")); // detect when the following message needs updated
        if (K == []const u8) {
            @compileError("std.hash.autoHash does not allow slices here (" ++
                @typeName(K) ++
                ") because the intent is unclear. " ++
                "Consider using std.StringHashMap for hashing the contents of []const u8. " ++
                "Alternatively, consider using std.hash.autoHashStrat or providing your own hash function instead.");
        }
    }

    return struct {
        fn hash(ctx: Context, key: K) u64 {
            _ = ctx;
            if (std.meta.hasUniqueRepresentation(K)) {
                return Wyhash.hash(0, std.mem.asBytes(&key));
            } else {
                var hasher = Wyhash.init(0);
                autoHash(&hasher, key);
                return hasher.final();
            }
        }
    }.hash;
}

pub fn getAutoEqlFn(comptime K: type, comptime Context: type) (fn (Context, K, K) bool) {
    return struct {
        fn eql(ctx: Context, a: K, b: K) bool {
            _ = ctx;
            return std.meta.eql(a, b);
        }
    }.eql;
}

pub fn AutoHashMap(comptime K: type, comptime V: type) type {
    return HashMap(K, V, AutoContext(K), default_max_load_percentage);
}

pub fn AutoHashMapUnmanaged(comptime K: type, comptime V: type) type {
    return HashMapUnmanaged(K, V, AutoContext(K), default_max_load_percentage);
}

pub fn AutoContext(comptime K: type) type {
    return struct {
        pub const hash = getAutoHashFn(K, @This());
        pub const eql = getAutoEqlFn(K, @This());
    };
}

/// Builtin hashmap for strings as keys.
/// Key memory is managed by the caller.  Keys and values
/// will not automatically be freed.
pub fn StringHashMap(comptime V: type) type {
    return HashMap([]const u8, V, StringContext, default_max_load_percentage);
}

/// Key memory is managed by the caller.  Keys and values
/// will not automatically be freed.
pub fn StringHashMapUnmanaged(comptime V: type) type {
    return HashMapUnmanaged([]const u8, V, StringContext, default_max_load_percentage);
}

pub const StringContext = struct {
    pub fn hash(self: @This(), s: []const u8) u64 {
        _ = self;
        return hashString(s);
    }
    pub fn eql(self: @This(), a: []const u8, b: []const u8) bool {
        _ = self;
        return eqlString(a, b);
    }
};

pub fn eqlString(a: []const u8, b: []const u8) bool {
    return mem.eql(u8, a, b);
}

pub fn hashString(s: []const u8) u64 {
    return std.hash.Wyhash.hash(0, s);
}

pub const StringIndexContext = struct {
    bytes: *const std.ArrayList(u8),

    pub fn eql(_: @This(), a: u32, b: u32) bool {
        return a == b;
    }

    pub fn hash(ctx: @This(), key: u32) u64 {
        return hashString(mem.sliceTo(ctx.bytes.items[key..], 0));
    }
};

pub const StringIndexAdapter = struct {
    bytes: *const std.ArrayList(u8),

    pub fn eql(ctx: @This(), a: []const u8, b: u32) bool {
        return mem.eql(u8, a, mem.sliceTo(ctx.bytes.items[b..], 0));
    }

    pub fn hash(_: @This(), adapted_key: []const u8) u64 {
        assert(mem.findScalar(u8, adapted_key, 0) == null);
        return hashString(adapted_key);
    }
};

pub const default_max_load_percentage = 80;

/// General purpose hash table.
/// No order is guaranteed and any modification invalidates live iterators.
/// It provides fast operations (lookup, insertion, deletion) with quite high
/// load factors (up to 80% by default) for low memory usage.
/// For a hash map that can be initialized directly that does not store an Allocator
/// field, see `HashMapUnmanaged`.
/// If iterating over the table entries is a strong usecase and needs to be fast,
/// prefer the alternative `std.ArrayHashMap`.
/// Context must be a struct type with two member functions:
///   hash(self, K) u64
///   eql(self, K, K) bool
/// Adapted variants of many functions are provided.  These variants
/// take a pseudo key instead of a key.  Their context must have the functions:
///   hash(self, PseudoKey) u64
///   eql(self, PseudoKey, K) bool
pub fn HashMap(
    comptime K: type,
    comptime V: type,
    comptime Context: type,
    comptime max_load_percentage: u64,
) type {
    return struct {
        unmanaged: Unmanaged,
        allocator: Allocator,
        ctx: Context,

        /// The type of the unmanaged hash map underlying this wrapper
        pub const Unmanaged = HashMapUnmanaged(K, V, Context, max_load_percentage);
        /// An entry, containing pointers to a key and value stored in the map
        pub const Entry = Unmanaged.Entry;
        /// A copy of a key and value which are no longer in the map
        pub const KV = Unmanaged.KV;
        /// The integer type that is the result of hashing
        pub const Hash = Unmanaged.Hash;
        /// The iterator type returned by iterator()
        pub const Iterator = Unmanaged.Iterator;

        pub const KeyIterator = Unmanaged.KeyIterator;
        pub const ValueIterator = Unmanaged.ValueIterator;

        /// The integer type used to store the size of the map
        pub const Size = Unmanaged.Size;
        /// The type returned from getOrPut and variants
        pub const GetOrPutResult = Unmanaged.GetOrPutResult;

        const Self = @This();

        /// Create a managed hash map with an empty context.
        /// If the context is not zero-sized, you must use
        /// initContext(allocator, ctx) instead.
        pub fn init(allocator: Allocator) Self {
            if (@sizeOf(Context) != 0) {
                @compileError("Context must be specified! Call initContext(allocator, ctx) instead.");
            }
            return .{
                .unmanaged = .empty,
                .allocator = allocator,
                .ctx = undefined, // ctx is zero-sized so this is safe.
            };
        }

        /// Create a managed hash map with a context
        pub fn initContext(allocator: Allocator, ctx: Context) Self {
            return .{
                .unmanaged = .empty,
                .allocator = allocator,
                .ctx = ctx,
            };
        }

        /// Puts the hash map into a state where any method call that would
        /// cause an existing key or value pointer to become invalidated will
        /// instead trigger an assertion.
        ///
        /// `lockPointers` may be called multiple times. This allows multiple
        /// independent users of the hash map to keep it locked simultaneously.
        ///
        /// `unlockPointers` restores the hash map to its previous state when
        /// called the same number of times as `lockPointers`.
        pub fn lockPointers(self: *Self) void {
            self.unmanaged.lockPointers();
        }

        /// Undoes one call to `lockPointers`.
        pub fn unlockPointers(self: *Self) void {
            self.unmanaged.unlockPointers();
        }

        /// Release the backing array and invalidate this map.
        /// This does *not* deinit keys, values, or the context!
        /// If your keys or values need to be released, ensure
        /// that that is done before calling this function.
        pub fn deinit(self: *Self) void {
            self.unmanaged.deinit(self.allocator);
            self.* = undefined;
        }

        /// Empty the map, but keep the backing allocation for future use.
        /// This does *not* free keys or values! Be sure to
        /// release them if they need deinitialization before
        /// calling this function.
        pub fn clearRetainingCapacity(self: *Self) void {
            return self.unmanaged.clearRetainingCapacity();
        }

        /// Empty the map and release the backing allocation.
        /// This does *not* free keys or values! Be sure to
        /// release them if they need deinitialization before
        /// calling this function.
        pub fn clearAndFree(self: *Self) void {
            return self.unmanaged.clearAndFree(self.allocator);
        }

        /// Return the number of items in the map.
        pub fn count(self: Self) Size {
            return self.unmanaged.count();
        }

        /// Create an iterator over the entries in the map.
        /// The iterator is invalidated if the map is modified.
        pub fn iterator(self: *const Self) Iterator {
            return self.unmanaged.iterator();
        }

        /// Create an iterator over the keys in the map.
        /// The iterator is invalidated if the map is modified.
        pub fn keyIterator(self: Self) KeyIterator {
            return self.unmanaged.keyIterator();
        }

        /// Create an iterator over the values in the map.
        /// The iterator is invalidated if the map is modified.
        pub fn valueIterator(self: Self) ValueIterator {
            return self.unmanaged.valueIterator();
        }

        /// If key exists this function cannot fail.
        /// If there is an existing item with `key`, then the result's
        /// `Entry` pointers point to it, and found_existing is true.
        /// Otherwise, puts a new item with undefined value, and
        /// the `Entry` pointers point to it. Caller should then initialize
        /// the value (but not the key).
        pub fn getOrPut(self: *Self, key: K) Allocator.Error!GetOrPutResult {
            return self.unmanaged.getOrPutContext(self.allocator, key, self.ctx);
        }

        /// If key exists this function cannot fail.
        /// If there is an existing item with `key`, then the result's
        /// `Entry` pointers point to it, and found_existing is true.
        /// Otherwise, puts a new item with undefined key and value, and
        /// the `Entry` pointers point to it. Caller must then initialize
        /// the key and value.
        pub fn getOrPutAdapted(self: *Self, key: anytype, ctx: anytype) Allocator.Error!GetOrPutResult {
            return self.unmanaged.getOrPutContextAdapted(self.allocator, key, ctx, self.ctx);
        }

        /// If there is an existing item with `key`, then the result's
        /// `Entry` pointers point to it, and found_existing is true.
        /// Otherwise, puts a new item with undefined value, and
        /// the `Entry` pointers point to it. Caller should then initialize
        /// the value (but not the key).
        /// If a new entry needs to be stored, this function asserts there
        /// is enough capacity to store it.
        pub fn getOrPutAssumeCapacity(self: *Self, key: K) GetOrPutResult {
            return self.unmanaged.getOrPutAssumeCapacityContext(key, self.ctx);
        }

        /// If there is an existing item with `key`, then the result's
        /// `Entry` pointers point to it, and found_existing is true.
        /// Otherwise, puts a new item with undefined value, and
        /// the `Entry` pointers point to it. Caller must then initialize
        /// the key and value.
        /// If a new entry needs to be stored, this function asserts there
        /// is enough capacity to store it.
        pub fn getOrPutAssumeCapacityAdapted(self: *Self, key: anytype, ctx: anytype) GetOrPutResult {
            return self.unmanaged.getOrPutAssumeCapacityAdapted(key, ctx);
        }

        pub fn getOrPutValue(self: *Self, key: K, value: V) Allocator.Error!Entry {
            return self.unmanaged.getOrPutValueContext(self.allocator, key, value, self.ctx);
        }

        /// Increases capacity, guaranteeing that insertions up until the
        /// `expected_count` will not cause an allocation, and therefore cannot fail.
        pub fn ensureTotalCapacity(self: *Self, expected_count: Size) Allocator.Error!void {
            return self.unmanaged.ensureTotalCapacityContext(self.allocator, expected_count, self.ctx);
        }

        /// Increases capacity, guaranteeing that insertions up until
        /// `additional_count` **more** items will not cause an allocation, and
        /// therefore cannot fail.
        pub fn ensureUnusedCapacity(self: *Self, additional_count: Size) Allocator.Error!void {
            return self.unmanaged.ensureUnusedCapacityContext(self.allocator, additional_count, self.ctx);
        }

        /// Returns the number of total elements which may be present before it is
        /// no longer guaranteed that no allocations will be performed.
        pub fn capacity(self: Self) Size {
            return self.unmanaged.capacity();
        }

        /// Clobbers any existing data. To detect if a put would clobber
        /// existing data, see `getOrPut`.
        pub fn put(self: *Self, key: K, value: V) Allocator.Error!void {
            return self.unmanaged.putContext(self.allocator, key, value, self.ctx);
        }

        /// Inserts a key-value pair into the hash map, asserting that no previous
        /// entry with the same key is already present
        pub fn putNoClobber(self: *Self, key: K, value: V) Allocator.Error!void {
            return self.unmanaged.putNoClobberContext(self.allocator, key, value, self.ctx);
        }

        /// Asserts there is enough capacity to store the new key-value pair.
        /// Clobbers any existing data. To detect if a put would clobber
        /// existing data, see `getOrPutAssumeCapacity`.
        pub fn putAssumeCapacity(self: *Self, key: K, value: V) void {
            return self.unmanaged.putAssumeCapacityContext(key, value, self.ctx);
        }

        /// Asserts there is enough capacity to store the new key-value pair.
        /// Asserts that it does not clobber any existing data.
        /// To detect if a put would clobber existing data, see `getOrPutAssumeCapacity`.
        pub fn putAssumeCapacityNoClobber(self: *Self, key: K, value: V) void {
            return self.unmanaged.putAssumeCapacityNoClobberContext(key, value, self.ctx);
        }

        /// Inserts a new `Entry` into the hash map, returning the previous one, if any.
        pub fn fetchPut(self: *Self, key: K, value: V) Allocator.Error!?KV {
            return self.unmanaged.fetchPutContext(self.allocator, key, value, self.ctx);
        }

        /// Inserts a new `Entry` into the hash map, returning the previous one, if any.
        /// If insertion happens, asserts there is enough capacity without allocating.
        pub fn fetchPutAssumeCapacity(self: *Self, key: K, value: V) ?KV {
            return self.unmanaged.fetchPutAssumeCapacityContext(key, value, self.ctx);
        }

        /// Removes a value from the map and returns the removed kv pair.
        pub fn fetchRemove(self: *Self, key: K) ?KV {
            return self.unmanaged.fetchRemoveContext(key, self.ctx);
        }

        pub fn fetchRemoveAdapted(self: *Self, key: anytype, ctx: anytype) ?KV {
            return self.unmanaged.fetchRemoveAdapted(key, ctx);
        }

        /// Finds the value associated with a key in the map
        pub fn get(self: Self, key: K) ?V {
            return self.unmanaged.getContext(key, self.ctx);
        }
        pub fn getAdapted(self: Self, key: anytype, ctx: anytype) ?V {
            return self.unmanaged.getAdapted(key, ctx);
        }

        pub fn getPtr(self: Self, key: K) ?*V {
            return self.unmanaged.getPtrContext(key, self.ctx);
        }
        pub fn getPtrAdapted(self: Self, key: anytype, ctx: anytype) ?*V {
            return self.unmanaged.getPtrAdapted(key, ctx);
        }

        /// Finds the actual key associated with an adapted key in the map
        pub fn getKey(self: Self, key: K) ?K {
            return self.unmanaged.getKeyContext(key, self.ctx);
        }
        pub fn getKeyAdapted(self: Self, key: anytype, ctx: anytype) ?K {
            return self.unmanaged.getKeyAdapted(key, ctx);
        }

        pub fn getKeyPtr(self: Self, key: K) ?*K {
            return self.unmanaged.getKeyPtrContext(key, self.ctx);
        }
        pub fn getKeyPtrAdapted(self: Self, key: anytype, ctx: anytype) ?*K {
            return self.unmanaged.getKeyPtrAdapted(key, ctx);
        }

        /// Finds the key and value associated with a key in the map
        pub fn getEntry(self: Self, key: K) ?Entry {
            return self.unmanaged.getEntryContext(key, self.ctx);
        }

        pub fn getEntryAdapted(self: Self, key: anytype, ctx: anytype) ?Entry {
            return self.unmanaged.getEntryAdapted(key, ctx);
        }

        /// Check if the map contains a key
        pub fn contains(self: Self, key: K) bool {
            return self.unmanaged.containsContext(key, self.ctx);
        }

        pub fn containsAdapted(self: Self, key: anytype, ctx: anytype) bool {
            return self.unmanaged.containsAdapted(key, ctx);
        }

        /// If there is an `Entry` with a matching key, it is deleted from
        /// the hash map, and this function returns true.  Otherwise this
        /// function returns false.
        ///
        /// TODO: answer the question in these doc comments, does this
        /// increase the unused capacity by one?
        pub fn remove(self: *Self, key: K) bool {
            return self.unmanaged.removeContext(key, self.ctx);
        }

        /// TODO: answer the question in these doc comments, does this
        /// increase the unused capacity by one?
        pub fn removeAdapted(self: *Self, key: anytype, ctx: anytype) bool {
            return self.unmanaged.removeAdapted(key, ctx);
        }

        /// Delete the entry with key pointed to by key_ptr from the hash map.
        /// key_ptr is assumed to be a valid pointer to a key that is present
        /// in the hash map.
        ///
        /// TODO: answer the question in these doc comments, does this
        /// increase the unused capacity by one?
        pub fn removeByPtr(self: *Self, key_ptr: *K) void {
            self.unmanaged.removeByPtr(key_ptr);
        }

        /// Creates a copy of this map, using the same allocator
        pub fn clone(self: Self) Allocator.Error!Self {
            var other = try self.unmanaged.cloneContext(self.allocator, self.ctx);
            return other.promoteContext(self.allocator, self.ctx);
        }

        /// Creates a copy of this map, using a specified allocator
        pub fn cloneWithAllocator(self: Self, new_allocator: Allocator) Allocator.Error!Self {
            var other = try self.unmanaged.cloneContext(new_allocator, self.ctx);
            return other.promoteContext(new_allocator, self.ctx);
        }

        /// Creates a copy of this map, using a specified context
        pub fn cloneWithContext(self: Self, new_ctx: anytype) Allocator.Error!HashMap(K, V, @TypeOf(new_ctx), max_load_percentage) {
            var other = try self.unmanaged.cloneContext(self.allocator, new_ctx);
            return other.promoteContext(self.allocator, new_ctx);
        }

        /// Creates a copy of this map, using a specified allocator and context.
        pub fn cloneWithAllocatorAndContext(
            self: Self,
            new_allocator: Allocator,
            new_ctx: anytype,
        ) Allocator.Error!HashMap(K, V, @TypeOf(new_ctx), max_load_percentage) {
            var other = try self.unmanaged.cloneContext(new_allocator, new_ctx);
            return other.promoteContext(new_allocator, new_ctx);
        }

        /// Set the map to an empty state, making deinitialization a no-op, and
        /// returning a copy of the original.
        pub fn move(self: *Self) Self {
            self.unmanaged.pointer_stability.assertUnlocked();
            const result = self.*;
            self.unmanaged = .empty;
            return result;
        }

        /// Rehash the map, in-place.
        ///
        /// Over time, due to the current tombstone-based implementation, a
        /// HashMap could become fragmented due to the buildup of tombstone
        /// entries that causes a performance degradation due to excessive
        /// probing. The kind of pattern that might cause this is a long-lived
        /// HashMap with repeated inserts and deletes.
        ///
        /// After this function is called, there will be no tombstones in
        /// the HashMap, each of the entries is rehashed and any existing
        /// key/value pointers into the HashMap are invalidated.
        pub fn rehash(self: *Self) void {
            self.unmanaged.rehash(self.ctx);
        }
    };
}

/// A HashMap based on open addressing and linear probing.
/// A lookup or modification typically incurs only 2 cache misses.
/// No order is guaranteed and any modification invalidates live iterators.
/// It achieves good performance with quite high load factors (by default,
/// grow is triggered at 80% full) and only one byte of overhead per element.
/// The struct itself is only 16 bytes for a small footprint. This comes at
/// the price of handling size with u32, which should be reasonable enough
/// for almost all uses.
/// Deletions are achieved with tombstones.
///
/// Default initialization of this struct is deprecated; use `.empty` instead.
pub const HashMapUnmanaged = Custom;
fn Custom(
    comptime K: type,
    comptime V: type,
    comptime Context: type,
    comptime max_load_percentage: u64,
) type {
    if (max_load_percentage <= 0 or max_load_percentage >= 100)
        @compileError("max_load_percentage must be between 0 and 100.");
    return struct {
        const Self = @This();

        // This is actually a midway pointer to the single buffer containing
        // a `Header` field, the `Metadata`s and `Entry`s.
        // At `-@sizeOf(Header)` is the Header field.
        // At `sizeOf(Metadata) * capacity + offset`, which is pointed to by
        // self.header().entries, is the array of entries.
        // This means that the hashmap only holds one live allocation, to
        // reduce memory fragmentation and struct size.
        /// Pointer to the metadata.
        metadata: ?[*]Metadata = null,

        /// Current number of elements in the hashmap.
        size: Size = 0,

        // Having a countdown to grow reduces the number of instructions to
        // execute when determining if the hashmap has enough capacity already.
        /// Number of available slots before a grow is needed to satisfy the
        /// `max_load_percentage`.
        available: Size = 0,

        /// Used to detect memory safety violations.
        pointer_stability: std.debug.SafetyLock = .{},

        // This is purely empirical and not a /very smart magic constant™/.
        /// Capacity of the first grow when bootstrapping the hashmap.
        const minimal_capacity = 8;

        /// A map containing no keys or values.
        pub const empty: Self = .{
            .metadata = null,
            .size = 0,
            .available = 0,
        };

        // This hashmap is specially designed for sizes that fit in a u32.
        pub const Size = u32;

        // u64 hashes guarantee us that the fingerprint bits will never be used
        // to compute the index of a slot, maximizing the use of entropy.
        pub const Hash = u64;

        pub const Entry = struct {
            key_ptr: *K,
            value_ptr: *V,
        };

        pub const KV = struct {
            key: K,
            value: V,
        };

        const Header = struct {
            values: [*]V,
            keys: [*]K,
            capacity: Size,
        };

        /// Metadata for a slot. It can be in three states: empty, used or
        /// tombstone. Tombstones indicate that an entry was previously used,
        /// they are a simple way to handle removal.
        /// To this state, we add 7 bits from the slot's key hash. These are
        /// used as a fast way to disambiguate between entries without
        /// having to use the equality function. If two fingerprints are
        /// different, we know that we don't have to compare the keys at all.
        /// The 7 bits are the highest ones from a 64 bit hash. This way, not
        /// only we use the `log2(capacity)` lowest bits from the hash to determine
        /// a slot index, but we use 7 more bits to quickly resolve collisions
        /// when multiple elements with different hashes end up wanting to be in the same slot.
        /// Not using the equality function means we don't have to read into
        /// the entries array, likely avoiding a cache miss and a potentially
        /// costly function call.
        const Metadata = packed struct {
            const FingerPrint = u7;

            const free: FingerPrint = 0;
            const tombstone: FingerPrint = 1;

            fingerprint: FingerPrint = free,
            used: u1 = 0,

            const slot_free: u8 = @bitCast(Metadata{ .fingerprint = free });
            const slot_tombstone: u8 = @bitCast(Metadata{ .fingerprint = tombstone });

            pub fn isUsed(self: Metadata) bool {
                return self.used == 1;
            }

            pub fn isTombstone(self: Metadata) bool {
                return @as(u8, @bitCast(self)) == slot_tombstone;
            }

            pub fn isFree(self: Metadata) bool {
                return @as(u8, @bitCast(self)) == slot_free;
            }

            pub fn takeFingerprint(hash: Hash) FingerPrint {
                const hash_bits = @typeInfo(Hash).int.bits;
                const fp_bits = @typeInfo(FingerPrint).int.bits;
                return @as(FingerPrint, @truncate(hash >> (hash_bits - fp_bits)));
            }

            pub fn fill(self: *Metadata, fp: FingerPrint) void {
                self.used = 1;
                self.fingerprint = fp;
            }

            pub fn remove(self: *Metadata) void {
                self.used = 0;
                self.fingerprint = tombstone;
            }
        };

        comptime {
            assert(@sizeOf(Metadata) == 1);
            assert(@alignOf(Metadata) == 1);
        }

        pub const Iterator = struct {
            hm: *const Self,
            index: Size = 0,

            pub fn next(it: *Iterator) ?Entry {
                assert(it.index <= it.hm.capacity());
                if (it.hm.size == 0) return null;

                const cap = it.hm.capacity();
                const end = it.hm.metadata.? + cap;
                var metadata = it.hm.metadata.? + it.index;

                while (metadata != end) : ({
                    metadata += 1;
                    it.index += 1;
                }) {
                    if (metadata[0].isUsed()) {
                        const key = &it.hm.keys()[it.index];
                        const value = &it.hm.values()[it.index];
                        it.index += 1;
                        return Entry{ .key_ptr = key, .value_ptr = value };
                    }
                }

                return null;
            }
        };

        pub const KeyIterator = FieldIterator(K);
        pub const ValueIterator = FieldIterator(V);

        fn FieldIterator(comptime T: type) type {
            return struct {
                len: usize,
                metadata: [*]const Metadata,
                items: [*]T,

                pub fn next(self: *@This()) ?*T {
                    while (self.len > 0) {
                        self.len -= 1;
                        const used = self.metadata[0].isUsed();
                        const item = &self.items[0];
                        self.metadata += 1;
                        self.items += 1;
                        if (used) {
                            return item;
                        }
                    }
                    return null;
                }
            };
        }

        pub const GetOrPutResult = struct {
            key_ptr: *K,
            value_ptr: *V,
            found_existing: bool,
        };

        pub const Managed = HashMap(K, V, Context, max_load_percentage);

        pub fn promote(self: Self, allocator: Allocator) Managed {
            if (@sizeOf(Context) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call promoteContext instead.");
            return promoteContext(self, allocator, undefined);
        }

        pub fn promoteContext(self: Self, allocator: Allocator, ctx: Context) Managed {
            return .{
                .unmanaged = self,
                .allocator = allocator,
                .ctx = ctx,
            };
        }

        /// Puts the hash map into a state where any method call that would
        /// cause an existing key or value pointer to become invalidated will
        /// instead trigger an assertion.
        ///
        /// `lockPointers` may be called multiple times. This allows multiple
        /// independent users of the hash map to keep it locked simultaneously.
        ///
        /// `unlockPointers` restores the hash map to its previous state when
        /// called the same number of times as `lockPointers`.
        pub fn lockPointers(self: *Self) void {
            self.pointer_stability.lockShared();
        }

        /// Undoes one call to `lockPointers`.
        pub fn unlockPointers(self: *Self) void {
            self.pointer_stability.unlockShared();
        }

        fn isUnderMaxLoadPercentage(size: Size, cap: Size) bool {
            return size * 100 < max_load_percentage * cap;
        }

        pub fn deinit(self: *Self, allocator: Allocator) void {
            self.pointer_stability.assertUnlocked();
            self.deallocate(allocator);
            self.* = undefined;
        }

        fn capacityForSize(size: Size) Size {
            var new_cap: u32 = @intCast((@as(u64, size) * 100) / max_load_percentage + 1);
            new_cap = math.ceilPowerOfTwo(u32, new_cap) catch unreachable;
            return new_cap;
        }

        pub fn ensureTotalCapacity(self: *Self, allocator: Allocator, new_size: Size) Allocator.Error!void {
            if (@sizeOf(Context) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call ensureTotalCapacityContext instead.");
            return ensureTotalCapacityContext(self, allocator, new_size, undefined);
        }
        pub fn ensureTotalCapacityContext(self: *Self, allocator: Allocator, new_size: Size, ctx: Context) Allocator.Error!void {
            self.pointer_stability.lock();
            defer self.pointer_stability.unlock();
            if (new_size > self.size)
                try self.growIfNeeded(allocator, new_size - self.size, ctx);
        }

        pub fn ensureUnusedCapacity(self: *Self, allocator: Allocator, additional_size: Size) Allocator.Error!void {
            if (@sizeOf(Context) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call ensureUnusedCapacityContext instead.");
            return ensureUnusedCapacityContext(self, allocator, additional_size, undefined);
        }
        pub fn ensureUnusedCapacityContext(self: *Self, allocator: Allocator, additional_size: Size, ctx: Context) Allocator.Error!void {
            return ensureTotalCapacityContext(self, allocator, self.count() + additional_size, ctx);
        }

        pub fn clearRetainingCapacity(self: *Self) void {
            self.pointer_stability.lock();
            defer self.pointer_stability.unlock();
            if (self.metadata) |_| {
                self.initMetadatas();
                self.size = 0;
                self.available = @truncate((self.capacity() * max_load_percentage) / 100);
            }
        }

        pub fn clearAndFree(self: *Self, allocator: Allocator) void {
            self.pointer_stability.lock();
            defer self.pointer_stability.unlock();
            self.deallocate(allocator);
            self.size = 0;
            self.available = 0;
        }

        pub fn count(self: Self) Size {
            return self.size;
        }

        fn header(self: Self) *Header {
            return @ptrCast(@as([*]Header, @ptrCast(@alignCast(self.metadata.?))) - 1);
        }

        fn keys(self: Self) [*]K {
            return self.header().keys;
        }

        fn values(self: Self) [*]V {
            return self.header().values;
        }

        pub fn capacity(self: Self) Size {
            if (self.metadata == null) return 0;

            return self.header().capacity;
        }

        pub fn iterator(self: *const Self) Iterator {
            return .{ .hm = self };
        }

        pub fn keyIterator(self: Self) KeyIterator {
            if (self.metadata) |metadata| {
                return .{
                    .len = self.capacity(),
                    .metadata = metadata,
                    .items = self.keys(),
                };
            } else {
                return .{
                    .len = 0,
                    .metadata = undefined,
                    .items = undefined,
                };
            }
        }

        pub fn valueIterator(self: Self) ValueIterator {
            if (self.metadata) |metadata| {
                return .{
                    .len = self.capacity(),
                    .metadata = metadata,
                    .items = self.values(),
                };
            } else {
                return .{
                    .len = 0,
                    .metadata = undefined,
                    .items = undefined,
                };
            }
        }

        /// Insert an entry in the map. Assumes it is not already present.
        pub fn putNoClobber(self: *Self, allocator: Allocator, key: K, value: V) Allocator.Error!void {
            if (@sizeOf(Context) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call putNoClobberContext instead.");
            return self.putNoClobberContext(allocator, key, value, undefined);
        }
        pub fn putNoClobberContext(self: *Self, allocator: Allocator, key: K, value: V, ctx: Context) Allocator.Error!void {
            {
                self.pointer_stability.lock();
                defer self.pointer_stability.unlock();
                try self.growIfNeeded(allocator, 1, ctx);
            }
            self.putAssumeCapacityNoClobberContext(key, value, ctx);
        }

        /// Asserts there is enough capacity to store the new key-value pair.
        /// Clobbers any existing data. To detect if a put would clobber
        /// existing data, see `getOrPutAssumeCapacity`.
        pub fn putAssumeCapacity(self: *Self, key: K, value: V) void {
            if (@sizeOf(Context) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call putAssumeCapacityContext instead.");
            return self.putAssumeCapacityContext(key, value, undefined);
        }
        pub fn putAssumeCapacityContext(self: *Self, key: K, value: V, ctx: Context) void {
            const gop = self.getOrPutAssumeCapacityContext(key, ctx);
            gop.value_ptr.* = value;
        }

        /// Insert an entry in the map. Assumes it is not already present,
        /// and that no allocation is needed.
        pub fn putAssumeCapacityNoClobber(self: *Self, key: K, value: V) void {
            if (@sizeOf(Context) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call putAssumeCapacityNoClobberContext instead.");
            return self.putAssumeCapacityNoClobberContext(key, value, undefined);
        }
        pub fn putAssumeCapacityNoClobberContext(self: *Self, key: K, value: V, ctx: Context) void {
            assert(!self.containsContext(key, ctx));

            const hash: Hash = ctx.hash(key);
            const mask = self.capacity() - 1;
            var idx: usize = @truncate(hash & mask);

            var metadata = self.metadata.? + idx;
            while (metadata[0].isUsed()) {
                idx = (idx + 1) & mask;
                metadata = self.metadata.? + idx;
            }

            assert(self.available > 0);
            self.available -= 1;

            const fingerprint = Metadata.takeFingerprint(hash);
            metadata[0].fill(fingerprint);
            self.keys()[idx] = key;
            self.values()[idx] = value;

            self.size += 1;
        }

        /// Inserts a new `Entry` into the hash map, returning the previous one, if any.
        pub fn fetchPut(self: *Self, allocator: Allocator, key: K, value: V) Allocator.Error!?KV {
            if (@sizeOf(Context) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call fetchPutContext instead.");
            return self.fetchPutContext(allocator, key, value, undefined);
        }
        pub fn fetchPutContext(self: *Self, allocator: Allocator, key: K, value: V, ctx: Context) Allocator.Error!?KV {
            const gop = try self.getOrPutContext(allocator, key, ctx);
            var result: ?KV = null;
            if (gop.found_existing) {
                result = KV{
                    .key = gop.key_ptr.*,
                    .value = gop.value_ptr.*,
                };
            }
            gop.value_ptr.* = value;
            return result;
        }

        /// Inserts a new `Entry` into the hash map, returning the previous one, if any.
        /// If insertion happens, asserts there is enough capacity without allocating.
        pub fn fetchPutAssumeCapacity(self: *Self, key: K, value: V) ?KV {
            if (@sizeOf(Context) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call fetchPutAssumeCapacityContext instead.");
            return self.fetchPutAssumeCapacityContext(key, value, undefined);
        }
        pub fn fetchPutAssumeCapacityContext(self: *Self, key: K, value: V, ctx: Context) ?KV {
            const gop = self.getOrPutAssumeCapacityContext(key, ctx);
            var result: ?KV = null;
            if (gop.found_existing) {
                result = KV{
                    .key = gop.key_ptr.*,
                    .value = gop.value_ptr.*,
                };
            }
            gop.value_ptr.* = value;
            return result;
        }

        /// If there is an `Entry` with a matching key, it is deleted from
        /// the hash map, and then returned from this function.
        pub fn fetchRemove(self: *Self, key: K) ?KV {
            if (@sizeOf(Context) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call fetchRemoveContext instead.");
            return self.fetchRemoveContext(key, undefined);
        }
        pub fn fetchRemoveContext(self: *Self, key: K, ctx: Context) ?KV {
            return self.fetchRemoveAdapted(key, ctx);
        }
        pub fn fetchRemoveAdapted(self: *Self, key: anytype, ctx: anytype) ?KV {
            if (self.getIndex(key, ctx)) |idx| {
                const old_key = &self.keys()[idx];
                const old_val = &self.values()[idx];
                const result = KV{
                    .key = old_key.*,
                    .value = old_val.*,
                };
                self.metadata.?[idx].remove();
                old_key.* = undefined;
                old_val.* = undefined;
                self.size -= 1;
                self.available += 1;
                return result;
            }

            return null;
        }

        /// Find the index containing the data for the given key.
        fn getIndex(self: Self, key: anytype, ctx: anytype) ?usize {
            if (self.size == 0) {
                // We use cold instead of unlikely to force a jump to this case,
                // no matter the weight of the opposing side.
                @branchHint(.cold);
                return null;
            }

            // If you get a compile error on this line, it means that your generic hash
            // function is invalid for these parameters.
            const hash: Hash = ctx.hash(key);

            const mask = self.capacity() - 1;
            const fingerprint = Metadata.takeFingerprint(hash);
            // Don't loop indefinitely when there are no empty slots.
            var limit = self.capacity();
            var idx = @as(usize, @truncate(hash & mask));

            var metadata = self.metadata.? + idx;
            while (!metadata[0].isFree() and limit != 0) {
                if (metadata[0].isUsed() and metadata[0].fingerprint == fingerprint) {
                    const test_key = &self.keys()[idx];

                    if (ctx.eql(key, test_key.*)) {
                        return idx;
                    }
                }

                limit -= 1;
                idx = (idx + 1) & mask;
                metadata = self.metadata.? + idx;
            }

            return null;
        }

        pub fn getEntry(self: Self, key: K) ?Entry {
            if (@sizeOf(Context) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getEntryContext instead.");
            return self.getEntryContext(key, undefined);
        }
        pub fn getEntryContext(self: Self, key: K, ctx: Context) ?Entry {
            return self.getEntryAdapted(key, ctx);
        }
        pub fn getEntryAdapted(self: Self, key: anytype, ctx: anytype) ?Entry {
            if (self.getIndex(key, ctx)) |idx| {
                return Entry{
                    .key_ptr = &self.keys()[idx],
                    .value_ptr = &self.values()[idx],
                };
            }
            return null;
        }

        /// Insert an entry if the associated key is not already present, otherwise update preexisting value.
        pub fn put(self: *Self, allocator: Allocator, key: K, value: V) Allocator.Error!void {
            if (@sizeOf(Context) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call putContext instead.");
            return self.putContext(allocator, key, value, undefined);
        }
        pub fn putContext(self: *Self, allocator: Allocator, key: K, value: V, ctx: Context) Allocator.Error!void {
            const result = try self.getOrPutContext(allocator, key, ctx);
            result.value_ptr.* = value;
        }

        /// Get an optional pointer to the actual key associated with adapted key, if present.
        pub fn getKeyPtr(self: Self, key: K) ?*K {
            if (@sizeOf(Context) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getKeyPtrContext instead.");
            return self.getKeyPtrContext(key, undefined);
        }
        pub fn getKeyPtrContext(self: Self, key: K, ctx: Context) ?*K {
            return self.getKeyPtrAdapted(key, ctx);
        }
        pub fn getKeyPtrAdapted(self: Self, key: anytype, ctx: anytype) ?*K {
            if (self.getIndex(key, ctx)) |idx| {
                return &self.keys()[idx];
            }
            return null;
        }

        /// Get a copy of the actual key associated with adapted key, if present.
        pub fn getKey(self: Self, key: K) ?K {
            if (@sizeOf(Context) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getKeyContext instead.");
            return self.getKeyContext(key, undefined);
        }
        pub fn getKeyContext(self: Self, key: K, ctx: Context) ?K {
            return self.getKeyAdapted(key, ctx);
        }
        pub fn getKeyAdapted(self: Self, key: anytype, ctx: anytype) ?K {
            if (self.getIndex(key, ctx)) |idx| {
                return self.keys()[idx];
            }
            return null;
        }

        /// Get an optional pointer to the value associated with key, if present.
        pub fn getPtr(self: Self, key: K) ?*V {
            if (@sizeOf(Context) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getPtrContext instead.");
            return self.getPtrContext(key, undefined);
        }
        pub fn getPtrContext(self: Self, key: K, ctx: Context) ?*V {
            return self.getPtrAdapted(key, ctx);
        }
        pub fn getPtrAdapted(self: Self, key: anytype, ctx: anytype) ?*V {
            if (self.getIndex(key, ctx)) |idx| {
                return &self.values()[idx];
            }
            return null;
        }

        /// Get a copy of the value associated with key, if present.
        pub fn get(self: Self, key: K) ?V {
            if (@sizeOf(Context) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getContext instead.");
            return self.getContext(key, undefined);
        }
        pub fn getContext(self: Self, key: K, ctx: Context) ?V {
            return self.getAdapted(key, ctx);
        }
        pub fn getAdapted(self: Self, key: anytype, ctx: anytype) ?V {
            if (self.getIndex(key, ctx)) |idx| {
                return self.values()[idx];
            }
            return null;
        }

        pub fn getOrPut(self: *Self, allocator: Allocator, key: K) Allocator.Error!GetOrPutResult {
            if (@sizeOf(Context) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getOrPutContext instead.");
            return self.getOrPutContext(allocator, key, undefined);
        }
        pub fn getOrPutContext(self: *Self, allocator: Allocator, key: K, ctx: Context) Allocator.Error!GetOrPutResult {
            const gop = try self.getOrPutContextAdapted(allocator, key, ctx, ctx);
            if (!gop.found_existing) {
                gop.key_ptr.* = key;
            }
            return gop;
        }
        pub fn getOrPutAdapted(self: *Self, allocator: Allocator, key: anytype, key_ctx: anytype) Allocator.Error!GetOrPutResult {
            if (@sizeOf(Context) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getOrPutContextAdapted instead.");
            return self.getOrPutContextAdapted(allocator, key, key_ctx, undefined);
        }
        pub fn getOrPutContextAdapted(self: *Self, allocator: Allocator, key: anytype, key_ctx: anytype, ctx: Context) Allocator.Error!GetOrPutResult {
            {
                self.pointer_stability.lock();
                defer self.pointer_stability.unlock();
                self.growIfNeeded(allocator, 1, ctx) catch |err| {
                    // If allocation fails, try to do the lookup anyway.
                    // If we find an existing item, we can return it.
                    // Otherwise return the error, we could not add another.
                    const index = self.getIndex(key, key_ctx) orelse return err;
                    return GetOrPutResult{
                        .key_ptr = &self.keys()[index],
                        .value_ptr = &self.values()[index],
                        .found_existing = true,
                    };
                };
            }
            return self.getOrPutAssumeCapacityAdapted(key, key_ctx);
        }

        pub fn getOrPutAssumeCapacity(self: *Self, key: K) GetOrPutResult {
            if (@sizeOf(Context) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getOrPutAssumeCapacityContext instead.");
            return self.getOrPutAssumeCapacityContext(key, undefined);
        }
        pub fn getOrPutAssumeCapacityContext(self: *Self, key: K, ctx: Context) GetOrPutResult {
            const result = self.getOrPutAssumeCapacityAdapted(key, ctx);
            if (!result.found_existing) {
                result.key_ptr.* = key;
            }
            return result;
        }
        pub fn getOrPutAssumeCapacityAdapted(self: *Self, key: anytype, ctx: anytype) GetOrPutResult {

            // If you get a compile error on this line, it means that your generic hash
            // function is invalid for these parameters.
            const hash: Hash = ctx.hash(key);

            const mask = self.capacity() - 1;
            const fingerprint = Metadata.takeFingerprint(hash);
            var limit = self.capacity();
            var idx = @as(usize, @truncate(hash & mask));

            var first_tombstone_idx: usize = self.capacity(); // invalid index
            var metadata = self.metadata.? + idx;
            while (!metadata[0].isFree() and limit != 0) {
                if (metadata[0].isUsed() and metadata[0].fingerprint == fingerprint) {
                    const test_key = &self.keys()[idx];
                    // If you get a compile error on this line, it means that your generic eql
                    // function is invalid for these parameters.

                    if (ctx.eql(key, test_key.*)) {
                        return GetOrPutResult{
                            .key_ptr = test_key,
                            .value_ptr = &self.values()[idx],
                            .found_existing = true,
                        };
                    }
                } else if (first_tombstone_idx == self.capacity() and metadata[0].isTombstone()) {
                    first_tombstone_idx = idx;
                }

                limit -= 1;
                idx = (idx + 1) & mask;
                metadata = self.metadata.? + idx;
            }

            if (first_tombstone_idx < self.capacity()) {
                // Cheap try to lower probing lengths after deletions. Recycle a tombstone.
                idx = first_tombstone_idx;
                metadata = self.metadata.? + idx;
            }
            // We're using a slot previously free or a tombstone.
            self.available -= 1;

            metadata[0].fill(fingerprint);
            const new_key = &self.keys()[idx];
            const new_value = &self.values()[idx];
            new_key.* = undefined;
            new_value.* = undefined;
            self.size += 1;

            return GetOrPutResult{
                .key_ptr = new_key,
                .value_ptr = new_value,
                .found_existing = false,
            };
        }

        pub fn getOrPutValue(self: *Self, allocator: Allocator, key: K, value: V) Allocator.Error!Entry {
            if (@sizeOf(Context) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getOrPutValueContext instead.");
            return self.getOrPutValueContext(allocator, key, value, undefined);
        }
        pub fn getOrPutValueContext(self: *Self, allocator: Allocator, key: K, value: V, ctx: Context) Allocator.Error!Entry {
            const res = try self.getOrPutAdapted(allocator, key, ctx);
            if (!res.found_existing) {
                res.key_ptr.* = key;
                res.value_ptr.* = value;
            }
            return Entry{ .key_ptr = res.key_ptr, .value_ptr = res.value_ptr };
        }

        /// Return true if there is a value associated with key in the map.
        pub fn contains(self: Self, key: K) bool {
            if (@sizeOf(Context) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call containsContext instead.");
            return self.containsContext(key, undefined);
        }
        pub fn containsContext(self: Self, key: K, ctx: Context) bool {
            return self.containsAdapted(key, ctx);
        }
        pub fn containsAdapted(self: Self, key: anytype, ctx: anytype) bool {
            return self.getIndex(key, ctx) != null;
        }

        fn removeByIndex(self: *Self, idx: usize) void {
            self.metadata.?[idx].remove();
            self.keys()[idx] = undefined;
            self.values()[idx] = undefined;
            self.size -= 1;
            self.available += 1;
        }

        /// If there is an `Entry` with a matching key, it is deleted from
        /// the hash map, and this function returns true.  Otherwise this
        /// function returns false.
        ///
        /// TODO: answer the question in these doc comments, does this
        /// increase the unused capacity by one?
        pub fn remove(self: *Self, key: K) bool {
            if (@sizeOf(Context) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call removeContext instead.");
            return self.removeContext(key, undefined);
        }

        /// TODO: answer the question in these doc comments, does this
        /// increase the unused capacity by one?
        pub fn removeContext(self: *Self, key: K, ctx: Context) bool {
            return self.removeAdapted(key, ctx);
        }

        /// TODO: answer the question in these doc comments, does this
        /// increase the unused capacity by one?
        pub fn removeAdapted(self: *Self, key: anytype, ctx: anytype) bool {
            if (self.getIndex(key, ctx)) |idx| {
                self.removeByIndex(idx);
                return true;
            }

            return false;
        }

        /// Delete the entry with key pointed to by key_ptr from the hash map.
        /// key_ptr is assumed to be a valid pointer to a key that is present
        /// in the hash map.
        ///
        /// TODO: answer the question in these doc comments, does this
        /// increase the unused capacity by one?
        pub fn removeByPtr(self: *Self, key_ptr: *K) void {
            // if @sizeOf(K) == 0 then there is at most one item in the hash
            // map, which is assumed to exist as key_ptr must be valid.  This
            // item must be at index 0.
            const idx = if (@sizeOf(K) > 0)
                @as([*]K, @ptrCast(key_ptr)) - self.keys()
            else
                0;

            self.removeByIndex(idx);
        }

        fn initMetadatas(self: *Self) void {
            @memset(@as([*]u8, @ptrCast(self.metadata.?))[0 .. @sizeOf(Metadata) * self.capacity()], 0);
        }

        // This counts the number of occupied slots (not counting tombstones), which is
        // what has to stay under the max_load_percentage of capacity.
        fn load(self: Self) Size {
            const max_load = (self.capacity() * max_load_percentage) / 100;
            assert(max_load >= self.available);
            return @as(Size, @truncate(max_load - self.available));
        }

        fn growIfNeeded(self: *Self, allocator: Allocator, new_count: Size, ctx: Context) Allocator.Error!void {
            if (new_count > self.available) {
                try self.grow(allocator, capacityForSize(self.load() + new_count), ctx);
            }
        }

        pub fn clone(self: Self, allocator: Allocator) Allocator.Error!Self {
            if (@sizeOf(Context) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call cloneContext instead.");
            return self.cloneContext(allocator, @as(Context, undefined));
        }
        pub fn cloneContext(self: Self, allocator: Allocator, new_ctx: anytype) Allocator.Error!HashMapUnmanaged(K, V, @TypeOf(new_ctx), max_load_percentage) {
            var other: HashMapUnmanaged(K, V, @TypeOf(new_ctx), max_load_percentage) = .empty;
            if (self.size == 0)
                return other;

            const new_cap = capacityForSize(self.size);
            try other.allocate(allocator, new_cap);
            other.initMetadatas();
            other.available = @truncate((new_cap * max_load_percentage) / 100);

            var i: Size = 0;
            var metadata = self.metadata.?;
            const keys_ptr = self.keys();
            const values_ptr = self.values();
            while (i < self.capacity()) : (i += 1) {
                if (metadata[i].isUsed()) {
                    other.putAssumeCapacityNoClobberContext(keys_ptr[i], values_ptr[i], new_ctx);
                    if (other.size == self.size)
                        break;
                }
            }

            return other;
        }

        /// Set the map to an empty state, making deinitialization a no-op, and
        /// returning a copy of the original.
        pub fn move(self: *Self) Self {
            self.pointer_stability.assertUnlocked();
            const result = self.*;
            self.* = .empty;
            return result;
        }

        /// Rehash the map, in-place.
        ///
        /// Over time, due to the current tombstone-based implementation, a
        /// HashMap could become fragmented due to the buildup of tombstone
        /// entries that causes a performance degradation due to excessive
        /// probing. The kind of pattern that might cause this is a long-lived
        /// HashMap with repeated inserts and deletes.
        ///
        /// After this function is called, there will be no tombstones in
        /// the HashMap, each of the entries is rehashed and any existing
        /// key/value pointers into the HashMap are invalidated.
        pub fn rehash(self: *Self, ctx: anytype) void {
            const mask = self.capacity() - 1;

            var metadata = self.metadata.?;
            var keys_ptr = self.keys();
            var values_ptr = self.values();
            var curr: Size = 0;

            // While we are re-hashing every slot, we will use the
            // fingerprint to mark used buckets as being used and either free
            // (needing to be rehashed) or tombstone (already rehashed).

            while (curr < self.capacity()) : (curr += 1) {
                metadata[curr].fingerprint = Metadata.free;
            }

            // Now iterate over all the buckets, rehashing them

            curr = 0;
            while (curr < self.capacity()) {
                if (!metadata[curr].isUsed()) {
                    assert(metadata[curr].isFree());
                    curr += 1;
                    continue;
                }

                const hash = ctx.hash(keys_ptr[curr]);
                const fingerprint = Metadata.takeFingerprint(hash);
                var idx = @as(usize, @truncate(hash & mask));

                // For each bucket, rehash to an index:
                // 1) before the cursor, probed into a free slot, or
                // 2) equal to the cursor, no need to move, or
                // 3) ahead of the cursor, probing over already rehashed

                while ((idx < curr and metadata[idx].isUsed()) or
                    (idx > curr and metadata[idx].fingerprint == Metadata.tombstone))
                {
                    idx = (idx + 1) & mask;
                }

                if (idx < curr) {
                    assert(metadata[idx].isFree());
                    metadata[idx].fill(fingerprint);
                    keys_ptr[idx] = keys_ptr[curr];
                    values_ptr[idx] = values_ptr[curr];

                    metadata[curr].used = 0;
                    assert(metadata[curr].isFree());
                    keys_ptr[curr] = undefined;
                    values_ptr[curr] = undefined;

                    curr += 1;
                } else if (idx == curr) {
                    metadata[idx].fingerprint = fingerprint;
                    curr += 1;
                } else {
                    assert(metadata[idx].fingerprint != Metadata.tombstone);
                    metadata[idx].fingerprint = Metadata.tombstone;
                    if (metadata[idx].isUsed()) {
                        std.mem.swap(K, &keys_ptr[curr], &keys_ptr[idx]);
                        std.mem.swap(V, &values_ptr[curr], &values_ptr[idx]);
                    } else {
                        metadata[idx].used = 1;
                        keys_ptr[idx] = keys_ptr[curr];
                        values_ptr[idx] = values_ptr[curr];

                        metadata[curr].fingerprint = Metadata.free;
                        metadata[curr].used = 0;
                        keys_ptr[curr] = undefined;
                        values_ptr[curr] = undefined;

                        curr += 1;
                    }
                }
            }
        }

        fn grow(self: *Self, allocator: Allocator, new_capacity: Size, ctx: Context) Allocator.Error!void {
            @branchHint(.cold);
            const new_cap = @max(new_capacity, minimal_capacity);
            assert(new_cap > self.capacity());
            assert(std.math.isPowerOfTwo(new_cap));

            var map: Self = .{};
            try map.allocate(allocator, new_cap);
            errdefer comptime unreachable;
            map.pointer_stability.lock();
            map.initMetadatas();
            map.available = @truncate((new_cap * max_load_percentage) / 100);

            if (self.size != 0) {
                const old_capacity = self.capacity();
                for (
                    self.metadata.?[0..old_capacity],
                    self.keys()[0..old_capacity],
                    self.values()[0..old_capacity],
                ) |m, k, v| {
                    if (!m.isUsed()) continue;
                    map.putAssumeCapacityNoClobberContext(k, v, ctx);
                    if (map.size == self.size) break;
                }
            }

            self.size = 0;
            self.pointer_stability = .{};
            std.mem.swap(Self, self, &map);
            map.deinit(allocator);
        }

        fn allocate(self: *Self, allocator: Allocator, new_capacity: Size) Allocator.Error!void {
            const header_align = @alignOf(Header);
            const key_align = if (@sizeOf(K) == 0) 1 else @alignOf(K);
            const val_align = if (@sizeOf(V) == 0) 1 else @alignOf(V);
            const max_align: Alignment = comptime .fromByteUnits(@max(header_align, key_align, val_align));

            const new_cap: usize = new_capacity;
            const meta_size = @sizeOf(Header) + new_cap * @sizeOf(Metadata);
            comptime assert(@alignOf(Metadata) == 1);

            const keys_start = std.mem.alignForward(usize, meta_size, key_align);
            const keys_end = keys_start + new_cap * @sizeOf(K);

            const vals_start = std.mem.alignForward(usize, keys_end, val_align);
            const vals_end = vals_start + new_cap * @sizeOf(V);

            const total_size = max_align.forward(vals_end);

            const slice = try allocator.alignedAlloc(u8, max_align, total_size);
            const ptr: [*]u8 = @ptrCast(slice.ptr);

            const metadata = ptr + @sizeOf(Header);

            const hdr = @as(*Header, @ptrCast(@alignCast(ptr)));
            if (@sizeOf([*]V) != 0) {
                hdr.values = @ptrCast(@alignCast((ptr + vals_start)));
            }
            if (@sizeOf([*]K) != 0) {
                hdr.keys = @ptrCast(@alignCast((ptr + keys_start)));
            }
            hdr.capacity = new_capacity;
            self.metadata = @ptrCast(@alignCast(metadata));
        }

        fn deallocate(self: *Self, allocator: Allocator) void {
            if (self.metadata == null) return;

            const header_align = @alignOf(Header);
            const key_align = if (@sizeOf(K) == 0) 1 else @alignOf(K);
            const val_align = if (@sizeOf(V) == 0) 1 else @alignOf(V);
            const max_align = comptime @max(header_align, key_align, val_align);

            const cap: usize = self.capacity();
            const meta_size = @sizeOf(Header) + cap * @sizeOf(Metadata);
            comptime assert(@alignOf(Metadata) == 1);

            const keys_start = std.mem.alignForward(usize, meta_size, key_align);
            const keys_end = keys_start + cap * @sizeOf(K);

            const vals_start = std.mem.alignForward(usize, keys_end, val_align);
            const vals_end = vals_start + cap * @sizeOf(V);

            const total_size = std.mem.alignForward(usize, vals_end, max_align);

            const slice = @as([*]align(max_align) u8, @ptrCast(@alignCast(self.header())))[0..total_size];
            allocator.free(slice);

            self.metadata = null;
            self.available = 0;
        }

        /// This function is used in the debugger pretty formatters in lib/lldb/ to fetch the
        /// header type to facilitate fancy debug printing for this type.
        fn dbHelper(self: *Self, hdr: *Header, entry: *Entry) void {
            _ = self;
            _ = hdr;
            _ = entry;
        }

        comptime {
            if (!builtin.strip_debug_info) switch (builtin.zig_backend) {
                .stage2_llvm => _ = &dbHelper,
                .stage2_x86_64 => _ = @as(KV, undefined),
                else => {},
            };
        }
    };
}

const testing = std.testing;
const expect = std.testing.expect;
const expectEqual = std.testing.expectEqual;

test "basic usage" {
    var map = AutoHashMap(u32, u32).init(std.testing.allocator);
    defer map.deinit();

    const count = 5;
    var i: u32 = 0;
    var total: u32 = 0;
    while (i < count) : (i += 1) {
        try map.put(i, i);
        total += i;
    }

    var sum: u32 = 0;
    var it = map.iterator();
    while (it.next()) |kv| {
        sum += kv.key_ptr.*;
    }
    try expectEqual(total, sum);

    i = 0;
    sum = 0;
    while (i < count) : (i += 1) {
        try expectEqual(i, map.get(i).?);
        sum += map.get(i).?;
    }
    try expectEqual(total, sum);
}

test "ensureTotalCapacity" {
    var map = AutoHashMap(i32, i32).init(std.testing.allocator);
    defer map.deinit();

    try map.ensureTotalCapacity(20);
    const initial_capacity = map.capacity();
    try testing.expect(initial_capacity >= 20);
    var i: i32 = 0;
    while (i < 20) : (i += 1) {
        try testing.expect(map.fetchPutAssumeCapacity(i, i + 10) == null);
    }
    // shouldn't resize from putAssumeCapacity
    try testing.expect(initial_capacity == map.capacity());
}

test "ensureUnusedCapacity with tombstones" {
    var map = AutoHashMap(i32, i32).init(std.testing.allocator);
    defer map.deinit();

    var i: i32 = 0;
    while (i < 100) : (i += 1) {
        try map.ensureUnusedCapacity(1);
        map.putAssumeCapacity(i, i);
        _ = map.remove(i);
    }
}

test "clearRetainingCapacity" {
    var map = AutoHashMap(u32, u32).init(std.testing.allocator);
    defer map.deinit();

    map.clearRetainingCapacity();

    try map.put(1, 1);
    try expectEqual(map.get(1).?, 1);
    try expectEqual(map.count(), 1);

    map.clearRetainingCapacity();
    map.putAssumeCapacity(1, 1);
    try expectEqual(map.get(1).?, 1);
    try expectEqual(map.count(), 1);

    const cap = map.capacity();
    try expect(cap > 0);

    map.clearRetainingCapacity();
    map.clearRetainingCapacity();
    try expectEqual(map.count(), 0);
    try expectEqual(map.capacity(), cap);
    try expect(!map.contains(1));
}

test "grow" {
    var map = AutoHashMap(u32, u32).init(std.testing.allocator);
    defer map.deinit();

    const growTo = 12456;

    var i: u32 = 0;
    while (i < growTo) : (i += 1) {
        try map.put(i, i);
    }
    try expectEqual(map.count(), growTo);

    i = 0;
    var it = map.iterator();
    while (it.next()) |kv| {
        try expectEqual(kv.key_ptr.*, kv.value_ptr.*);
        i += 1;
    }
    try expectEqual(i, growTo);

    i = 0;
    while (i < growTo) : (i += 1) {
        try expectEqual(map.get(i).?, i);
    }
}

test "clone" {
    var map = AutoHashMap(u32, u32).init(std.testing.allocator);
    defer map.deinit();

    var a = try map.clone();
    defer a.deinit();

    try expectEqual(a.count(), 0);

    try a.put(1, 1);
    try a.put(2, 2);
    try a.put(3, 3);

    var b = try a.clone();
    defer b.deinit();

    try expectEqual(b.count(), 3);
    try expectEqual(b.get(1).?, 1);
    try expectEqual(b.get(2).?, 2);
    try expectEqual(b.get(3).?, 3);

    var original = AutoHashMap(i32, i32).init(std.testing.allocator);
    defer original.deinit();

    var i: u8 = 0;
    while (i < 10) : (i += 1) {
        try original.putNoClobber(i, i * 10);
    }

    var copy = try original.clone();
    defer copy.deinit();

    i = 0;
    while (i < 10) : (i += 1) {
        try testing.expect(copy.get(i).? == i * 10);
    }
}

test "ensureTotalCapacity with existing elements" {
    var map = AutoHashMap(u32, u32).init(std.testing.allocator);
    defer map.deinit();

    try map.put(0, 0);
    try expectEqual(map.count(), 1);
    try expectEqual(map.capacity(), @TypeOf(map).Unmanaged.minimal_capacity);

    try map.ensureTotalCapacity(65);
    try expectEqual(map.count(), 1);
    try expectEqual(map.capacity(), 128);
}

test "ensureTotalCapacity satisfies max load factor" {
    var map = AutoHashMap(u32, u32).init(std.testing.allocator);
    defer map.deinit();

    try map.ensureTotalCapacity(127);
    try expectEqual(map.capacity(), 256);
}

test "remove" {
    var map = AutoHashMap(u32, u32).init(std.testing.allocator);
    defer map.deinit();

    var i: u32 = 0;
    while (i < 16) : (i += 1) {
        try map.put(i, i);
    }

    i = 0;
    while (i < 16) : (i += 1) {
        if (i % 3 == 0) {
            _ = map.remove(i);
        }
    }
    try expectEqual(map.count(), 10);
    var it = map.iterator();
    while (it.next()) |kv| {
        try expectEqual(kv.key_ptr.*, kv.value_ptr.*);
        try expect(kv.key_ptr.* % 3 != 0);
    }

    i = 0;
    while (i < 16) : (i += 1) {
        if (i % 3 == 0) {
            try expect(!map.contains(i));
        } else {
            try expectEqual(map.get(i).?, i);
        }
    }
}

test "reverse removes" {
    var map = AutoHashMap(u32, u32).init(std.testing.allocator);
    defer map.deinit();

    var i: u32 = 0;
    while (i < 16) : (i += 1) {
        try map.putNoClobber(i, i);
    }

    i = 16;
    while (i > 0) : (i -= 1) {
        _ = map.remove(i - 1);
        try expect(!map.contains(i - 1));
        var j: u32 = 0;
        while (j < i - 1) : (j += 1) {
            try expectEqual(map.get(j).?, j);
        }
    }

    try expectEqual(map.count(), 0);
}

test "multiple removes on same metadata" {
    var map = AutoHashMap(u32, u32).init(std.testing.allocator);
    defer map.deinit();

    var i: u32 = 0;
    while (i < 16) : (i += 1) {
        try map.put(i, i);
    }

    _ = map.remove(7);
    _ = map.remove(15);
    _ = map.remove(14);
    _ = map.remove(13);
    try expect(!map.contains(7));
    try expect(!map.contains(15));
    try expect(!map.contains(14));
    try expect(!map.contains(13));

    i = 0;
    while (i < 13) : (i += 1) {
        if (i == 7) {
            try expect(!map.contains(i));
        } else {
            try expectEqual(map.get(i).?, i);
        }
    }

    try map.put(15, 15);
    try map.put(13, 13);
    try map.put(14, 14);
    try map.put(7, 7);
    i = 0;
    while (i < 16) : (i += 1) {
        try expectEqual(map.get(i).?, i);
    }
}

test "put and remove loop in random order" {
    var map = AutoHashMap(u32, u32).init(std.testing.allocator);
    defer map.deinit();

    var keys = std.array_list.Managed(u32).init(std.testing.allocator);
    defer keys.deinit();

    const size = 32;
    const iterations = 100;

    var i: u32 = 0;
    while (i < size) : (i += 1) {
        try keys.append(i);
    }
    var prng = std.Random.DefaultPrng.init(std.testing.random_seed);
    const random = prng.random();

    while (i < iterations) : (i += 1) {
        random.shuffle(u32, keys.items);

        for (keys.items) |key| {
            try map.put(key, key);
        }
        try expectEqual(map.count(), size);

        for (keys.items) |key| {
            _ = map.remove(key);
        }
        try expectEqual(map.count(), 0);
    }
}

test "remove many elements in random order" {
    const Map = AutoHashMap(u32, u32);
    const n = 1000 * 100;
    var map = Map.init(std.heap.page_allocator);
    defer map.deinit();

    var keys = std.array_list.Managed(u32).init(std.heap.page_allocator);
    defer keys.deinit();

    var i: u32 = 0;
    while (i < n) : (i += 1) {
        keys.append(i) catch unreachable;
    }

    var prng = std.Random.DefaultPrng.init(std.testing.random_seed);
    const random = prng.random();
    random.shuffle(u32, keys.items);

    for (keys.items) |key| {
        map.put(key, key) catch unreachable;
    }

    random.shuffle(u32, keys.items);
    i = 0;
    while (i < n) : (i += 1) {
        const key = keys.items[i];
        _ = map.remove(key);
    }
}

test "put" {
    var map = AutoHashMap(u32, u32).init(std.testing.allocator);
    defer map.deinit();

    var i: u32 = 0;
    while (i < 16) : (i += 1) {
        try map.put(i, i);
    }

    i = 0;
    while (i < 16) : (i += 1) {
        try expectEqual(map.get(i).?, i);
    }

    i = 0;
    while (i < 16) : (i += 1) {
        try map.put(i, i * 16 + 1);
    }

    i = 0;
    while (i < 16) : (i += 1) {
        try expectEqual(map.get(i).?, i * 16 + 1);
    }
}

test "putAssumeCapacity" {
    var map = AutoHashMap(u32, u32).init(std.testing.allocator);
    defer map.deinit();

    try map.ensureTotalCapacity(20);
    var i: u32 = 0;
    while (i < 20) : (i += 1) {
        map.putAssumeCapacityNoClobber(i, i);
    }

    i = 0;
    var sum = i;
    while (i < 20) : (i += 1) {
        sum += map.getPtr(i).?.*;
    }
    try expectEqual(sum, 190);

    i = 0;
    while (i < 20) : (i += 1) {
        map.putAssumeCapacity(i, 1);
    }

    i = 0;
    sum = i;
    while (i < 20) : (i += 1) {
        sum += map.get(i).?;
    }
    try expectEqual(sum, 20);
}

test "repeat putAssumeCapacity/remove" {
    var map = AutoHashMap(u32, u32).init(std.testing.allocator);
    defer map.deinit();

    try map.ensureTotalCapacity(20);
    const limit = map.unmanaged.available;

    var i: u32 = 0;
    while (i < limit) : (i += 1) {
        map.putAssumeCapacityNoClobber(i, i);
    }

    // Repeatedly delete/insert an entry without resizing the map.
    // Put to different keys so entries don't land in the just-freed slot.
    i = 0;
    while (i < 10 * limit) : (i += 1) {
        try testing.expect(map.remove(i));
        if (i % 2 == 0) {
            map.putAssumeCapacityNoClobber(limit + i, i);
        } else {
            map.putAssumeCapacity(limit + i, i);
        }
    }

    i = 9 * limit;
    while (i < 10 * limit) : (i += 1) {
        try expectEqual(map.get(limit + i), i);
    }
    try expectEqual(map.unmanaged.available, 0);
    try expectEqual(map.unmanaged.count(), limit);
}

test "getOrPut" {
    var map = AutoHashMap(u32, u32).init(std.testing.allocator);
    defer map.deinit();

    var i: u32 = 0;
    while (i < 10) : (i += 1) {
        try map.put(i * 2, 2);
    }

    i = 0;
    while (i < 20) : (i += 1) {
        _ = try map.getOrPutValue(i, 1);
    }

    i = 0;
    var sum = i;
    while (i < 20) : (i += 1) {
        sum += map.get(i).?;
    }

    try expectEqual(sum, 30);
}

test "basic hash map usage" {
    var map = AutoHashMap(i32, i32).init(std.testing.allocator);
    defer map.deinit();

    try testing.expect((try map.fetchPut(1, 11)) == null);
    try testing.expect((try map.fetchPut(2, 22)) == null);
    try testing.expect((try map.fetchPut(3, 33)) == null);
    try testing.expect((try map.fetchPut(4, 44)) == null);

    try map.putNoClobber(5, 55);
    try testing.expect((try map.fetchPut(5, 66)).?.value == 55);
    try testing.expect((try map.fetchPut(5, 55)).?.value == 66);

    const gop1 = try map.getOrPut(5);
    try testing.expect(gop1.found_existing == true);
    try testing.expect(gop1.value_ptr.* == 55);
    gop1.value_ptr.* = 77;
    try testing.expect(map.getEntry(5).?.value_ptr.* == 77);

    const gop2 = try map.getOrPut(99);
    try testing.expect(gop2.found_existing == false);
    gop2.value_ptr.* = 42;
    try testing.expect(map.getEntry(99).?.value_ptr.* == 42);

    const gop3 = try map.getOrPutValue(5, 5);
    try testing.expect(gop3.value_ptr.* == 77);

    const gop4 = try map.getOrPutValue(100, 41);
    try testing.expect(gop4.value_ptr.* == 41);

    try testing.expect(map.contains(2));
    try testing.expect(map.getEntry(2).?.value_ptr.* == 22);
    try testing.expect(map.get(2).? == 22);

    const rmv1 = map.fetchRemove(2);
    try testing.expect(rmv1.?.key == 2);
    try testing.expect(rmv1.?.value == 22);
    try testing.expect(map.fetchRemove(2) == null);
    try testing.expect(map.remove(2) == false);
    try testing.expect(map.getEntry(2) == null);
    try testing.expect(map.get(2) == null);

    try testing.expect(map.remove(3) == true);
}

test "getOrPutAdapted" {
    const AdaptedContext = struct {
        fn eql(self: @This(), adapted_key: []const u8, test_key: u64) bool {
            _ = self;
            return std.fmt.parseInt(u64, adapted_key, 10) catch unreachable == test_key;
        }
        fn hash(self: @This(), adapted_key: []const u8) u64 {
            _ = self;
            const key = std.fmt.parseInt(u64, adapted_key, 10) catch unreachable;
            return (AutoContext(u64){}).hash(key);
        }
    };
    var map = AutoHashMap(u64, u64).init(testing.allocator);
    defer map.deinit();

    const keys = [_][]const u8{
        "1231",
        "4564",
        "7894",
        "1132",
        "65235",
        "95462",
        "0112305",
        "00658",
        "0",
        "2",
    };

    var real_keys: [keys.len]u64 = undefined;

    inline for (keys, 0..) |key_str, i| {
        const result = try map.getOrPutAdapted(key_str, AdaptedContext{});
        try testing.expect(!result.found_existing);
        real_keys[i] = std.fmt.parseInt(u64, key_str, 10) catch unreachable;
        result.key_ptr.* = real_keys[i];
        result.value_ptr.* = i * 2;
    }

    try testing.expectEqual(map.count(), keys.len);

    inline for (keys, 0..) |key_str, i| {
        const result = map.getOrPutAssumeCapacityAdapted(key_str, AdaptedContext{});
        try testing.expect(result.found_existing);
        try testing.expectEqual(real_keys[i], result.key_ptr.*);
        try testing.expectEqual(@as(u64, i) * 2, result.value_ptr.*);
        try testing.expectEqual(real_keys[i], map.getKeyAdapted(key_str, AdaptedContext{}).?);
    }
}

test "ensureUnusedCapacity" {
    var map = AutoHashMap(u64, u64).init(testing.allocator);
    defer map.deinit();

    try map.ensureUnusedCapacity(32);
    const capacity = map.capacity();
    try map.ensureUnusedCapacity(32);

    // Repeated ensureUnusedCapacity() calls with no insertions between
    // should not change the capacity.
    try testing.expectEqual(capacity, map.capacity());
}

test "removeByPtr" {
    var map = AutoHashMap(i32, u64).init(testing.allocator);
    defer map.deinit();

    var i: i32 = undefined;

    i = 0;
    while (i < 10) : (i += 1) {
        try map.put(i, 0);
    }

    try testing.expect(map.count() == 10);

    i = 0;
    while (i < 10) : (i += 1) {
        const key_ptr = map.getKeyPtr(i);
        try testing.expect(key_ptr != null);

        if (key_ptr) |ptr| {
            map.removeByPtr(ptr);
        }
    }

    try testing.expect(map.count() == 0);
}

test "removeByPtr 0 sized key" {
    var map = AutoHashMap(u0, u64).init(testing.allocator);
    defer map.deinit();

    try map.put(0, 0);

    try testing.expect(map.count() == 1);

    const key_ptr = map.getKeyPtr(0);
    try testing.expect(key_ptr != null);

    if (key_ptr) |ptr| {
        map.removeByPtr(ptr);
    }

    try testing.expect(map.count() == 0);
}

test "repeat fetchRemove" {
    var map: AutoHashMapUnmanaged(u64, void) = .empty;
    defer map.deinit(testing.allocator);

    try map.ensureTotalCapacity(testing.allocator, 4);

    map.putAssumeCapacity(0, {});
    map.putAssumeCapacity(1, {});
    map.putAssumeCapacity(2, {});
    map.putAssumeCapacity(3, {});

    // fetchRemove() should make slots available.
    var i: usize = 0;
    while (i < 10) : (i += 1) {
        try testing.expect(map.fetchRemove(3) != null);
        map.putAssumeCapacity(3, {});
    }

    try testing.expect(map.get(0) != null);
    try testing.expect(map.get(1) != null);
    try testing.expect(map.get(2) != null);
    try testing.expect(map.get(3) != null);
}

test "getOrPut allocation failure" {
    var map: std.StringHashMapUnmanaged(void) = .empty;
    try testing.expectError(error.OutOfMemory, map.getOrPut(std.testing.failing_allocator, "hello"));
}

test "rehash" {
    var map = AutoHashMap(usize, usize).init(std.testing.allocator);
    defer map.deinit();

    var prng = std.Random.DefaultPrng.init(0);
    const random = prng.random();

    const count = 4 * random.intRangeLessThan(u32, 100_000, 500_000);

    for (0..count) |i| {
        try map.put(i, i);
        if (i % 3 == 0) {
            try expectEqual(map.remove(i), true);
        }
    }

    map.rehash();

    try expectEqual(map.count(), count * 2 / 3);

    for (0..count) |i| {
        if (i % 3 == 0) {
            try expectEqual(map.get(i), null);
        } else {
            try expectEqual(map.get(i).?, i);
        }
    }
}

test "removeByPtr, key is array" {
    const gpa = testing.allocator;

    var map: AutoHashMapUnmanaged([2]u32, u32) = .empty;
    defer map.deinit(gpa);

    const key: [2]u32 = .{ 1, 2 };
    try map.put(gpa, key, 3);

    try expectEqual(1, map.count());
    try expectEqual(3, map.get(key));

    const key_ptr = map.getKeyPtr(key).?;
    map.removeByPtr(key_ptr);

    try expectEqual(0, map.count());
    try expectEqual(null, map.get(key));
}