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

Source line 1

std.array_hash_map.Allocator

alias

Source line 9

Alias of std.mem.Allocator

std.array_hash_map.ArrayHashMap

alias

Source line 45

Deprecated; use Custom.

Alias of std.array_hash_map.Custom

std.array_hash_map.assert

alias

Source line 3

Alias of std.debug.assert

std.array_hash_map.Auto

type-function

Source line 15

An ArrayHashMap with default hash and equal functions.

See AutoContext for a description of the hash and equal implementations.

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

Parameters

K: type
V: type

Fields

entries: DataList = .{}

It is permitted to access this field directly. After any modification to the keys, consider calling reIndex.

index_header: ?*IndexHeader = null

When entries length is less than linear_scan_max, this remains null. Once entries length grows big enough, this field is allocated. There is an IndexHeader followed by an array of Index(I) structs, where I is defined by how many total indexes there are.

pointer_stability: std.debug.SafetyLock = .{}

Used to detect memory safety violations.

std.array_hash_map.AutoContext

type-function

Source line 2217

pub fn AutoContext(comptime K: type) type

Parameters

K: type

std.array_hash_map.AutoContext.eql

constant

Source line 2220

std.array_hash_map.AutoContext.hash

constant

Source line 2219

std.array_hash_map.autoEqlIsCheap

function

Source line 2249

pub fn autoEqlIsCheap(comptime K: type) bool

Parameters

K: type

std.array_hash_map.autoHash

alias

Source line 7

Alias of std.hash.autoHash

std.array_hash_map.capacityIndexSize

function

Source line 1560

fn capacityIndexSize(bit_index: u8) usize

Parameters

bit_index: u8

std.array_hash_map.capacityIndexType

function

Source line 1551

fn capacityIndexType(bit_index: u8) CapacityIndexType

Parameters

bit_index: u8

std.array_hash_map.CapacityIndexType

container

Source line 1549

Fields

u8
u16
u32

std.array_hash_map.Custom

type-function

Source line 70

A hash table of keys and values, each stored sequentially.

Insertion order is preserved. In general, this data structure supports the same operations as std.ArrayList.

Deletion operations:

  • swapRemove - O(1)
  • orderedRemove - O(N)

Modifying the hash map while iterating is allowed, however, one must understand the (well defined) behavior when mixing insertions and deletions with iteration.

This type does not store an Allocator field - the Allocator must be passed in with each function call that requires it.

Can be initialized directly using the default field values.

This type is designed to have low overhead for small numbers of entries. When store_hash is false and the number of entries in the map is less than 9, the overhead cost of using ArrayHashMap rather than std.ArrayList is only a single pointer-sized integer.

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

pub fn Custom( comptime K: type, comptime V: type, comptime Context: type, comptime store_hash: bool, ) type

Parameters

K: type
V: type
Context: type

A namespace that provides these two functions:

  • pub fn hash(self, K) u32
  • pub fn eql(self, K, K, usize) bool

The final usize in the eql function represents the index of the key that's already inside the map.

store_hash: bool

When false, this data structure is biased towards cheap eql functions and avoids storing each key's hash in the table. Setting store_hash to true incurs more memory cost but limits eql to being called only once per insertion/deletion (provided there are no hash collisions).

Fields

entries: DataList = .{}

It is permitted to access this field directly. After any modification to the keys, consider calling reIndex.

index_header: ?*IndexHeader = null

When entries length is less than linear_scan_max, this remains null. Once entries length grows big enough, this field is allocated. There is an IndexHeader followed by an array of Index(I) structs, where I is defined by how many total indexes there are.

pointer_stability: std.debug.SafetyLock = .{}

Used to detect memory safety violations.

std.array_hash_map.Custom.ByIndexContext

type

Source line 151

Some functions require a context only if hashes are not stored. To keep the api simple, this type is only used internally.

std.array_hash_map.Custom.capacity

function

Source line 456

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) usize

Parameters

self: Self

std.array_hash_map.Custom.checkedEql

function

Source line 1483

fn checkedEql(ctx: anytype, a: anytype, b: K, b_index: usize) bool

Parameters

b: K
b_index: usize

std.array_hash_map.Custom.checkedHash

function

Source line 1477

fn checkedHash(ctx: anytype, key: anytype) u32

std.array_hash_map.Custom.clearAndFree

function

Source line 233

Clears the map and releases the backing allocation

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

Parameters

self: *Self
gpa: Allocator

std.array_hash_map.Custom.clearRetainingCapacity

function

Source line 218

Clears the map but retains the backing allocation for future use.

pub fn clearRetainingCapacity(self: *Self) void

Parameters

self: *Self

std.array_hash_map.Custom.clone

function

Source line 833

Create a copy of the hash map which can be modified separately. The copy uses the same context as this instance, but is allocated with the provided allocator.

pub fn clone(self: Self, gpa: Allocator) Oom!Self

Parameters

self: Self
gpa: Allocator

Errors

OutOfMemory Error

std.array_hash_map.Custom.cloneContext

function

Source line 838

pub fn cloneContext(self: Self, gpa: Allocator, ctx: Context) Oom!Self

Parameters

self: Self
gpa: Allocator
ctx: Context

Errors

OutOfMemory Error

std.array_hash_map.Custom.contains

function

Source line 664

Check whether a key is stored in the map

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

Parameters

self: Self
key: K

std.array_hash_map.Custom.containsAdapted

function

Source line 672

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

Parameters

self: Self

std.array_hash_map.Custom.containsContext

function

Source line 669

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

Parameters

self: Self
key: K
ctx: Context

std.array_hash_map.Custom.count

function

Source line 245

Returns the number of KV pairs stored in this map.

pub fn count(self: Self) usize

Parameters

self: Self

std.array_hash_map.Custom.Data

container

Source line 123

The Data type used for the MultiArrayList backing this map

Fields

hash: Hash
key: K
value: V

std.array_hash_map.Custom.DataList

type

Source line 130

The MultiArrayList type backing this map

std.array_hash_map.Custom.deinit

function

Source line 190

Frees the backing allocation and leaves the map in an undefined state. Note that this does not free keys or values. You must take care of that before calling this function, if it is needed.

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

Parameters

self: *Self
gpa: Allocator

std.array_hash_map.Custom.dumpIndex

function

Source line 1525

fn dumpIndex(header: *IndexHeader, comptime I: type) void

Parameters

header: *IndexHeader
I: type

std.array_hash_map.Custom.dumpState

function

Source line 1489

fn dumpState(self: Self, comptime keyFmt: []const u8, comptime valueFmt: []const u8) void

Parameters

self: Self
keyFmt: []const u8
valueFmt: []const u8

std.array_hash_map.Custom.dumpStateContext

function

Source line 1494

fn dumpStateContext(self: Self, comptime keyFmt: []const u8, comptime valueFmt: []const u8, ctx: Context) void

Parameters

self: Self
keyFmt: []const u8
valueFmt: []const u8
ctx: Context

std.array_hash_map.Custom.empty

constant

Source line 102

A map containing no keys or values.

Self

std.array_hash_map.Custom.ensureTotalCapacity

function

Source line 412

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

pub fn ensureTotalCapacity(self: *Self, gpa: Allocator, new_capacity: usize) Oom!void

Parameters

self: *Self
gpa: Allocator
new_capacity: usize

Errors

OutOfMemory Error

std.array_hash_map.Custom.ensureTotalCapacityContext

function

Source line 417

pub fn ensureTotalCapacityContext(self: *Self, gpa: Allocator, new_capacity: usize, ctx: Context) Oom!void

Parameters

self: *Self
gpa: Allocator
new_capacity: usize
ctx: Context

Errors

OutOfMemory Error

std.array_hash_map.Custom.ensureUnusedCapacity

function

Source line 436

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, gpa: Allocator, additional_capacity: usize, ) Oom!void

Parameters

self: *Self
gpa: Allocator
additional_capacity: usize

Errors

OutOfMemory Error

std.array_hash_map.Custom.ensureUnusedCapacityContext

function

Source line 445

pub fn ensureUnusedCapacityContext( self: *Self, gpa: Allocator, additional_capacity: usize, ctx: Context, ) Oom!void

Parameters

self: *Self
gpa: Allocator
additional_capacity: usize
ctx: Context

Errors

OutOfMemory Error

std.array_hash_map.Custom.Entry

container

Source line 111

Modifying the key is allowed only if it does not change the hash. Modifying the value is allowed. Entry pointers become invalid whenever this ArrayHashMap is modified, unless ensureTotalCapacity/ensureUnusedCapacity was previously used.

Fields

key_ptr: *K
value_ptr: *V

std.array_hash_map.Custom.fetchOrderedRemove

function

Source line 704

If there is an Entry with a matching key, it is deleted from the hash map, and then returned from this function. The entry is removed from the underlying array by shifting all elements forward thereby maintaining the current ordering.

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

Parameters

self: *Self
key: K

std.array_hash_map.Custom.fetchOrderedRemoveAdapted

function

Source line 712

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

Parameters

self: *Self

std.array_hash_map.Custom.fetchOrderedRemoveContext

function

Source line 709

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

Parameters

self: *Self
key: K
ctx: Context

std.array_hash_map.Custom.fetchOrderedRemoveContextAdapted

function

Source line 717

pub fn fetchOrderedRemoveContextAdapted(self: *Self, key: anytype, key_ctx: anytype, ctx: Context) ?KV

Parameters

self: *Self
ctx: Context

std.array_hash_map.Custom.fetchPut

function

Source line 516

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

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

Parameters

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

Errors

OutOfMemory Error

std.array_hash_map.Custom.fetchPutAssumeCapacity

function

Source line 536

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.array_hash_map.Custom.fetchPutAssumeCapacityContext

function

Source line 541

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

Parameters

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

std.array_hash_map.Custom.fetchPutContext

function

Source line 521

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

Parameters

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

Errors

OutOfMemory Error

std.array_hash_map.Custom.fetchRemoveByKey

function

Source line 1060

fn fetchRemoveByKey( self: *Self, key: anytype, key_ctx: anytype, ctx: ByIndexContext, comptime removal_type: RemovalType, ) ?KV

Parameters

self: *Self
ctx: ByIndexContext
removal_type: RemovalType

std.array_hash_map.Custom.fetchRemoveByKeyGeneric

function

Source line 1095

fn fetchRemoveByKeyGeneric( self: *Self, key: anytype, key_ctx: anytype, ctx: ByIndexContext, header: *IndexHeader, comptime I: type, comptime removal_type: RemovalType, ) ?KV

Parameters

self: *Self
ctx: ByIndexContext
header: *IndexHeader
I: type
removal_type: RemovalType

std.array_hash_map.Custom.fetchSwapRemove

function

Source line 680

If there is an Entry with a matching key, it is deleted from the hash map, and then returned from this function. The entry is removed from the underlying array by swapping it with the last element.

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

Parameters

self: *Self
key: K

std.array_hash_map.Custom.fetchSwapRemoveAdapted

function

Source line 688

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

Parameters

self: *Self

std.array_hash_map.Custom.fetchSwapRemoveContext

function

Source line 685

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

Parameters

self: *Self
key: K
ctx: Context

std.array_hash_map.Custom.fetchSwapRemoveContextAdapted

function

Source line 693

pub fn fetchSwapRemoveContextAdapted(self: *Self, key: anytype, key_ctx: anytype, ctx: Context) ?KV

Parameters

self: *Self
ctx: Context

std.array_hash_map.Custom.get

function

Source line 608

Find the value associated with a key

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

Parameters

self: Self
key: K

std.array_hash_map.Custom.getAdapted

function

Source line 616

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

Parameters

self: Self

std.array_hash_map.Custom.getContext

function

Source line 613

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

Parameters

self: Self
key: K
ctx: Context

std.array_hash_map.Custom.getEntry

function

Source line 555

Finds pointers to the key and value storage associated with a key.

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

Parameters

self: Self
key: K

std.array_hash_map.Custom.getEntryAdapted

function

Source line 563

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

Parameters

self: Self

std.array_hash_map.Custom.getEntryContext

function

Source line 560

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

Parameters

self: Self
key: K
ctx: Context

std.array_hash_map.Custom.getIndex

function

Source line 573

Finds the index in the entries array where a key is stored

pub fn getIndex(self: Self, key: K) ?usize

Parameters

self: Self
key: K

std.array_hash_map.Custom.getIndexAdapted

function

Source line 581

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

Parameters

self: Self

std.array_hash_map.Custom.getIndexContext

function

Source line 578

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

Parameters

self: Self
key: K
ctx: Context

std.array_hash_map.Custom.getIndexWithHeaderGeneric

function

Source line 601

fn getIndexWithHeaderGeneric(self: Self, key: anytype, ctx: anytype, header: *IndexHeader, comptime I: type) ?usize

Parameters

self: Self
header: *IndexHeader
I: type

std.array_hash_map.Custom.getKey

function

Source line 636

Find the actual key associated with an adapted key

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

Parameters

self: Self
key: K

std.array_hash_map.Custom.getKeyAdapted

function

Source line 644

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

Parameters

self: Self

std.array_hash_map.Custom.getKeyContext

function

Source line 641

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

Parameters

self: Self
key: K
ctx: Context

std.array_hash_map.Custom.getKeyPtr

function

Source line 650

Find a pointer to the actual key associated with an adapted key

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

Parameters

self: Self
key: K

std.array_hash_map.Custom.getKeyPtrAdapted

function

Source line 658

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

Parameters

self: Self

std.array_hash_map.Custom.getKeyPtrContext

function

Source line 655

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

Parameters

self: Self
key: K
ctx: Context

std.array_hash_map.Custom.getOrPut

function

Source line 301

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

pub fn getOrPut(self: *Self, gpa: Allocator, key: K) Oom!GetOrPutResult

Parameters

self: *Self
gpa: Allocator
key: K

Errors

OutOfMemory Error

std.array_hash_map.Custom.getOrPutAdapted

function

Source line 313

pub fn getOrPutAdapted(self: *Self, gpa: Allocator, key: anytype, key_ctx: anytype) Oom!GetOrPutResult

Parameters

self: *Self
gpa: Allocator

Errors

OutOfMemory Error

std.array_hash_map.Custom.getOrPutAssumeCapacity

function

Source line 340

If there is an existing item with key, then the result Entry pointer points to it, and found_existing is true. Otherwise, puts a new item with undefined value, and the Entry pointer points 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.array_hash_map.Custom.getOrPutAssumeCapacityAdapted

function

Source line 359

If there is an existing item with key, then the result 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 both the key and the 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.array_hash_map.Custom.getOrPutAssumeCapacityContext

function

Source line 345

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

Parameters

self: *Self
key: K
ctx: Context

std.array_hash_map.Custom.getOrPutContext

function

Source line 306

pub fn getOrPutContext(self: *Self, gpa: Allocator, key: K, ctx: Context) Oom!GetOrPutResult

Parameters

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

Errors

OutOfMemory Error

std.array_hash_map.Custom.getOrPutContextAdapted

function

Source line 318

pub fn getOrPutContextAdapted(self: *Self, gpa: Allocator, key: anytype, key_ctx: anytype, ctx: Context) Oom!GetOrPutResult

Parameters

self: *Self
gpa: Allocator
ctx: Context

Errors

OutOfMemory Error

std.array_hash_map.Custom.getOrPutInternal

function

Source line 1283

Must ensureTotalCapacity/ensureUnusedCapacity before calling this.

fn getOrPutInternal(self: *Self, key: anytype, ctx: anytype, header: *IndexHeader, comptime I: type) GetOrPutResult

Parameters

self: *Self
header: *IndexHeader
I: type

std.array_hash_map.Custom.GetOrPutResult

container

Source line 142

getOrPut variants return this structure, with pointers to the backing store and a flag to indicate whether an existing entry was found. Modifying the key is allowed only if it does not change the hash. Modifying the value is allowed. Entry pointers become invalid whenever this ArrayHashMap is modified, unless ensureTotalCapacity/ensureUnusedCapacity was previously used.

Fields

key_ptr: *K
value_ptr: *V
found_existing: bool
index: usize

std.array_hash_map.Custom.getOrPutValue

function

Source line 396

pub fn getOrPutValue(self: *Self, gpa: Allocator, key: K, value: V) Oom!GetOrPutResult

Parameters

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

Errors

OutOfMemory Error

std.array_hash_map.Custom.getOrPutValueContext

function

Source line 401

pub fn getOrPutValueContext(self: *Self, gpa: Allocator, key: K, value: V, ctx: Context) Oom!GetOrPutResult

Parameters

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

Errors

OutOfMemory Error

std.array_hash_map.Custom.getPtr

function

Source line 622

Find a pointer to the value associated with a key

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

Parameters

self: Self
key: K

std.array_hash_map.Custom.getPtrAdapted

function

Source line 630

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

Parameters

self: Self

std.array_hash_map.Custom.getPtrContext

function

Source line 627

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

Parameters

self: Self
key: K
ctx: Context

std.array_hash_map.Custom.getSlotByIndex

function

Source line 1255

fn getSlotByIndex(self: *Self, entry_index: usize, ctx: ByIndexContext, header: *IndexHeader, comptime I: type, indexes: []Index(I)) usize

Parameters

self: *Self
entry_index: usize
ctx: ByIndexContext
header: *IndexHeader
I: type
indexes: []Index(I)

std.array_hash_map.Custom.getSlotByKey

function

Source line 1393

fn getSlotByKey(self: Self, key: anytype, ctx: anytype, header: *IndexHeader, comptime I: type, indexes: []Index(I)) ?usize

Parameters

self: Self
header: *IndexHeader
I: type
indexes: []Index(I)

std.array_hash_map.Custom.Hash

type

Source line 133

The stored hash type, either u32 or void.

std.array_hash_map.Custom.init

function

Source line 167

pub fn init(gpa: Allocator, key_list: []const K, value_list: []const V) Oom!Self

Parameters

gpa: Allocator
key_list: []const K
value_list: []const V

Errors

OutOfMemory Error

std.array_hash_map.Custom.insertAllEntriesIntoNewHeader

function

Source line 1421

fn insertAllEntriesIntoNewHeader(self: *Self, ctx: ByIndexContext, header: *IndexHeader) void

Parameters

self: *Self
ctx: ByIndexContext
header: *IndexHeader

std.array_hash_map.Custom.insertAllEntriesIntoNewHeaderGeneric

function

Source line 1428

fn insertAllEntriesIntoNewHeaderGeneric(self: *Self, ctx: ByIndexContext, header: *IndexHeader, comptime I: type) void

Parameters

self: *Self
ctx: ByIndexContext
header: *IndexHeader
I: type

std.array_hash_map.Custom.insertEntryIntoNewHeader

function

Source line 1438

fn insertEntryIntoNewHeader(header: *IndexHeader, h: u32, i: usize) void

Parameters

header: *IndexHeader
h: u32
i: usize

std.array_hash_map.Custom.insertEntryIntoNewHeaderGeneric

function

Source line 1445

fn insertEntryIntoNewHeaderGeneric(header: *IndexHeader, h: u32, i: usize, comptime I: type) void

Parameters

header: *IndexHeader
h: u32
i: usize
I: type

std.array_hash_map.Custom.iterator

function

Source line 265

Returns an iterator over the pairs in this map. Modifying the map may invalidate this iterator.

pub fn iterator(self: Self) Iterator

Parameters

self: Self

std.array_hash_map.Custom.Iterator

container

Source line 273

Fields

keys: [*]K
values: [*]V
len: u32
index: u32 = 0

std.array_hash_map.Custom.Iterator.next

function

Source line 279

pub fn next(it: *Iterator) ?Entry

Parameters

it: *Iterator

std.array_hash_map.Custom.Iterator.reset

function

Source line 290

Reset the iterator to the initial index

pub fn reset(it: *Iterator) void

Parameters

it: *Iterator

std.array_hash_map.Custom.keys

function

Source line 253

Returns the backing array of keys in this map. Modifying the map may invalidate this array. Modifying this array in a way that changes key hashes or key equality puts the map into an unusable state until reIndex is called.

pub fn keys(self: Self) []K

Parameters

self: Self

std.array_hash_map.Custom.KV

container

Source line 117

A KV pair which has been copied out of the backing store

Fields

key: K
value: V

std.array_hash_map.Custom.linear_scan_max

constant

Source line 155

std.array_hash_map.Custom.lockPointers

function

Source line 208

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.array_hash_map.Custom.move

function

Source line 855

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.array_hash_map.Custom.Oom

alias

Source line 165

Alias of std.mem.Allocator.Error

std.array_hash_map.Custom.orderedRemove

function

Source line 752

If there is an Entry with a matching key, it is deleted from the hash map. The entry is removed from the underlying array by shifting all elements forward, thereby maintaining the current ordering. Returns true if an entry was removed, false otherwise.

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

Parameters

self: *Self
key: K

std.array_hash_map.Custom.orderedRemoveAdapted

function

Source line 760

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

Parameters

self: *Self

std.array_hash_map.Custom.orderedRemoveAt

function

Source line 791

Deletes the item at the specified index in entries from the hash map. The entry is removed from the underlying array by shifting all elements forward, thereby maintaining the current ordering.

pub fn orderedRemoveAt(self: *Self, index: usize) void

Parameters

self: *Self
index: usize

std.array_hash_map.Custom.orderedRemoveAtContext

function

Source line 796

pub fn orderedRemoveAtContext(self: *Self, index: usize, ctx: Context) void

Parameters

self: *Self
index: usize
ctx: Context

std.array_hash_map.Custom.orderedRemoveAtMany

function

Source line 811

Remove the entries indexed by sorted_indexes. The indexes to be removed correspond to state before deletion.

This operation is O(N).

Asserts that each index to be removed is in bounds.

Invalidates key and element pointers beyond the first deleted index.

pub fn orderedRemoveAtMany(self: *Self, gpa: Allocator, sorted_indexes: []const usize) Oom!void

Parameters

self: *Self
gpa: Allocator
sorted_indexes: []const usize

Errors

OutOfMemory Error

std.array_hash_map.Custom.orderedRemoveAtManyContext

function

Source line 817

pub fn orderedRemoveAtManyContext( self: *Self, gpa: Allocator, sorted_indexes: []const usize, ctx: Context, ) Oom!void

Parameters

self: *Self
gpa: Allocator
sorted_indexes: []const usize
ctx: Context

Errors

OutOfMemory Error

std.array_hash_map.Custom.orderedRemoveContext

function

Source line 757

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

Parameters

self: *Self
key: K
ctx: Context

std.array_hash_map.Custom.orderedRemoveContextAdapted

function

Source line 765

pub fn orderedRemoveContextAdapted(self: *Self, key: anytype, key_ctx: anytype, ctx: Context) bool

Parameters

self: *Self
ctx: Context

std.array_hash_map.Custom.pop

function

Source line 1040

Removes the last inserted Entry in the hash map and returns it. Otherwise returns null.

pub fn pop(self: *Self) ?KV

Parameters

self: *Self

std.array_hash_map.Custom.popContext

function

Source line 1045

pub fn popContext(self: *Self, ctx: Context) ?KV

Parameters

self: *Self
ctx: Context

std.array_hash_map.Custom.put

function

Source line 465

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

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

Parameters

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

Errors

OutOfMemory Error

std.array_hash_map.Custom.putAssumeCapacity

function

Source line 491

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.array_hash_map.Custom.putAssumeCapacityContext

function

Source line 496

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

Parameters

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

std.array_hash_map.Custom.putAssumeCapacityNoClobber

function

Source line 504

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.array_hash_map.Custom.putAssumeCapacityNoClobberContext

function

Source line 509

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

Parameters

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

std.array_hash_map.Custom.putContext

function

Source line 470

pub fn putContext(self: *Self, gpa: Allocator, key: K, value: V, ctx: Context) Oom!void

Parameters

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

Errors

OutOfMemory Error

std.array_hash_map.Custom.putNoClobber

function

Source line 477

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, gpa: Allocator, key: K, value: V) Oom!void

Parameters

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

Errors

OutOfMemory Error

std.array_hash_map.Custom.putNoClobberContext

function

Source line 482

pub fn putNoClobberContext(self: *Self, gpa: Allocator, key: K, value: V, ctx: Context) Oom!void

Parameters

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

Errors

OutOfMemory Error

std.array_hash_map.Custom.rebuildIndex

function

Source line 911

fn rebuildIndex(self: *Self, gpa: Allocator, ctx: Context) Oom!void

Parameters

self: *Self
gpa: Allocator
ctx: Context

Errors

OutOfMemory Error

std.array_hash_map.Custom.reIndex

function

Source line 872

Recomputes stored hashes and rebuilds the key indexes. If the underlying keys have been modified directly, call this method to recompute the denormalized metadata necessary for the operation of the methods of this map that lookup entries by key.

One use case for this is directly calling entries.resize() to grow the underlying storage, and then setting the keys and values directly without going through the methods of this map.

The time complexity of this operation is O(n).

pub fn reIndex(self: *Self, gpa: Allocator) Oom!void

Parameters

self: *Self
gpa: Allocator

Errors

OutOfMemory Error

std.array_hash_map.Custom.reIndexContext

function

Source line 878

pub fn reIndexContext(self: *Self, gpa: Allocator, ctx: Context) Oom!void

Parameters

self: *Self
gpa: Allocator
ctx: Context

Errors

OutOfMemory Error

std.array_hash_map.Custom.reinit

function

Source line 175

An empty value_list may be passed, in which case the values array becomes undefined.

pub fn reinit(self: *Self, gpa: Allocator, key_list: []const K, value_list: []const V) Oom!void

Parameters

self: *Self
gpa: Allocator
key_list: []const K
value_list: []const V

Errors

OutOfMemory Error

std.array_hash_map.Custom.RemovalType

container

Source line 160

Fields

swap
ordered

std.array_hash_map.Custom.removeByIndex

function

Source line 1153

fn removeByIndex(self: *Self, entry_index: usize, ctx: ByIndexContext, comptime removal_type: RemovalType) void

Parameters

self: *Self
entry_index: usize
ctx: ByIndexContext
removal_type: RemovalType

std.array_hash_map.Custom.removeByIndexGeneric

function

Source line 1168

fn removeByIndexGeneric(self: *Self, entry_index: usize, ctx: ByIndexContext, header: *IndexHeader, comptime I: type, comptime removal_type: RemovalType) void

Parameters

self: *Self
entry_index: usize
ctx: ByIndexContext
header: *IndexHeader
I: type
removal_type: RemovalType

std.array_hash_map.Custom.removeByKey

function

Source line 1115

fn removeByKey( self: *Self, key: anytype, key_ctx: anytype, ctx: ByIndexContext, comptime removal_type: RemovalType, ) bool

Parameters

self: *Self
ctx: ByIndexContext
removal_type: RemovalType

std.array_hash_map.Custom.removeByKeyGeneric

function

Source line 1146

fn removeByKeyGeneric(self: *Self, key: anytype, key_ctx: anytype, ctx: ByIndexContext, header: *IndexHeader, comptime I: type, comptime removal_type: RemovalType) bool

Parameters

self: *Self
ctx: ByIndexContext
header: *IndexHeader
I: type
removal_type: RemovalType

std.array_hash_map.Custom.removeFromArrayAndUpdateIndex

function

Source line 1174

fn removeFromArrayAndUpdateIndex(self: *Self, entry_index: usize, ctx: ByIndexContext, header: *IndexHeader, comptime I: type, indexes: []Index(I), comptime removal_type: RemovalType) void

Parameters

self: *Self
entry_index: usize
ctx: ByIndexContext
header: *IndexHeader
I: type
indexes: []Index(I)
removal_type: RemovalType

std.array_hash_map.Custom.removeFromIndexByIndex

function

Source line 1214

fn removeFromIndexByIndex(self: *Self, entry_index: usize, ctx: ByIndexContext, header: *IndexHeader) void

Parameters

self: *Self
entry_index: usize
ctx: ByIndexContext
header: *IndexHeader

std.array_hash_map.Custom.removeFromIndexByIndexGeneric

function

Source line 1221

fn removeFromIndexByIndexGeneric(self: *Self, entry_index: usize, ctx: ByIndexContext, header: *IndexHeader, comptime I: type, indexes: []Index(I)) void

Parameters

self: *Self
entry_index: usize
ctx: ByIndexContext
header: *IndexHeader
I: type
indexes: []Index(I)

std.array_hash_map.Custom.removeFromIndexByKey

function

Source line 1226

fn removeFromIndexByKey(self: *Self, key: anytype, ctx: anytype, header: *IndexHeader, comptime I: type, indexes: []Index(I)) ?usize

Parameters

self: *Self
header: *IndexHeader
I: type
indexes: []Index(I)

std.array_hash_map.Custom.removeSlot

function

Source line 1233

fn removeSlot(removed_slot: usize, header: *IndexHeader, comptime I: type, indexes: []Index(I)) void

Parameters

removed_slot: usize
header: *IndexHeader
I: type
indexes: []Index(I)

std.array_hash_map.Custom.Self

alias

Source line 153

Alias of std.array_hash_map.Custom

std.array_hash_map.Custom.setKey

function

Source line 890

Modify an entry's key without reordering any entries.

pub fn setKey(self: *Self, index: usize, new_key: K) void

Parameters

self: *Self
index: usize
new_key: K

std.array_hash_map.Custom.setKeyContext

function

Source line 896

pub fn setKeyContext(self: *Self, index: usize, new_key: K, ctx: Context) void

Parameters

self: *Self
index: usize
new_key: K
ctx: Context

std.array_hash_map.Custom.shrinkAndFree

function

Source line 1009

Shrinks the underlying Entry array to new_len elements and discards any associated index entries. Reduces allocated capacity.

Asserts the discarded entries remain initialized and capable of performing hash and equality checks. It is a bug to call this function if the discarded entries require deinitialization. For that use case, shrinkRetainingCapacity can be used instead.

pub fn shrinkAndFree(self: *Self, gpa: Allocator, new_len: usize) void

Parameters

self: *Self
gpa: Allocator
new_len: usize

std.array_hash_map.Custom.shrinkAndFreeContext

function

Source line 1023

Shrinks the underlying Entry array to new_len elements and discards any associated index entries. Reduces allocated capacity.

Asserts the discarded entries remain initialized and capable of performing hash and equality checks. It is a bug to call this function if the discarded entries require deinitialization. For that use case, shrinkRetainingCapacityContext can be used instead.

pub fn shrinkAndFreeContext(self: *Self, gpa: Allocator, new_len: usize, ctx: Context) void

Parameters

self: *Self
gpa: Allocator
new_len: usize
ctx: Context

std.array_hash_map.Custom.shrinkRetainingCapacity

function

Source line 975

Shrinks the underlying Entry array to new_len elements and discards any associated index entries. Keeps capacity the same.

Asserts the discarded entries remain initialized and capable of performing hash and equality checks. Any deinitialization of discarded entries must take place after calling this function.

pub fn shrinkRetainingCapacity(self: *Self, new_len: usize) void

Parameters

self: *Self
new_len: usize

std.array_hash_map.Custom.shrinkRetainingCapacityContext

function

Source line 987

Shrinks the underlying Entry array to new_len elements and discards any associated index entries. Keeps capacity the same.

Asserts the discarded entries remain initialized and capable of performing hash and equality checks. Any deinitialization of discarded entries must take place after calling this function.

pub fn shrinkRetainingCapacityContext(self: *Self, new_len: usize, ctx: Context) void

Parameters

self: *Self
new_len: usize
ctx: Context

std.array_hash_map.Custom.sort

function

Source line 927

Sorts the entries and then rebuilds the index. sort_ctx must have this method: fn lessThan(ctx: @TypeOf(ctx), a_index: usize, b_index: usize) bool Uses a stable sorting algorithm.

pub inline fn sort(self: *Self, sort_ctx: anytype) void

Parameters

self: *Self

std.array_hash_map.Custom.sortContext

function

Source line 943

pub inline fn sortContext(self: *Self, sort_ctx: anytype, ctx: Context) void

Parameters

self: *Self
ctx: Context

std.array_hash_map.Custom.sortContextInternal

function

Source line 951

fn sortContextInternal( self: *Self, comptime mode: std.sort.Mode, sort_ctx: anytype, ctx: Context, ) void

Parameters

self: *Self
mode: std.sort.Mode
ctx: Context

std.array_hash_map.Custom.sortUnstable

function

Source line 937

Sorts the entries and then rebuilds the index. sort_ctx must have this method: fn lessThan(ctx: @TypeOf(ctx), a_index: usize, b_index: usize) bool Uses an unstable sorting algorithm.

pub inline fn sortUnstable(self: *Self, sort_ctx: anytype) void

Parameters

self: *Self

std.array_hash_map.Custom.sortUnstableContext

function

Source line 947

pub inline fn sortUnstableContext(self: *Self, sort_ctx: anytype, ctx: Context) void

Parameters

self: *Self
ctx: Context

std.array_hash_map.Custom.swapRemove

function

Source line 728

If there is an Entry with a matching key, it is deleted from the hash map. The entry is removed from the underlying array by swapping it with the last element. Returns true if an entry was removed, false otherwise.

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

Parameters

self: *Self
key: K

std.array_hash_map.Custom.swapRemoveAdapted

function

Source line 736

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

Parameters

self: *Self

std.array_hash_map.Custom.swapRemoveAt

function

Source line 775

Deletes the item at the specified index in entries from the hash map. The entry is removed from the underlying array by swapping it with the last element.

pub fn swapRemoveAt(self: *Self, index: usize) void

Parameters

self: *Self
index: usize

std.array_hash_map.Custom.swapRemoveAtContext

function

Source line 780

pub fn swapRemoveAtContext(self: *Self, index: usize, ctx: Context) void

Parameters

self: *Self
index: usize
ctx: Context

std.array_hash_map.Custom.swapRemoveContext

function

Source line 733

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

Parameters

self: *Self
key: K
ctx: Context

std.array_hash_map.Custom.swapRemoveContextAdapted

function

Source line 741

pub fn swapRemoveContextAdapted(self: *Self, key: anytype, key_ctx: anytype, ctx: Context) bool

Parameters

self: *Self
ctx: Context

std.array_hash_map.Custom.unlockPointers

function

Source line 213

Undoes one call to lockPointers.

pub fn unlockPointers(self: *Self) void

Parameters

self: *Self

std.array_hash_map.Custom.updateEntryIndex

function

Source line 1201

fn updateEntryIndex( self: *Self, header: *IndexHeader, old_entry_index: usize, new_entry_index: usize, ctx: ByIndexContext, comptime I: type, indexes: []Index(I), ) void

Parameters

self: *Self
header: *IndexHeader
old_entry_index: usize
new_entry_index: usize
ctx: ByIndexContext
I: type
indexes: []Index(I)

std.array_hash_map.Custom.values

function

Source line 259

Returns the backing array of values in this map. Modifying the map may invalidate this array. It is permitted to modify the values in this array.

pub fn values(self: Self) []V

Parameters

self: Self

std.array_hash_map.debug

alias

Source line 2

Alias of std.debug

std.array_hash_map.eqlString

function

Source line 36

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

Parameters

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

std.array_hash_map.f

function

Source line 1871

pub fn f(allocator: Allocator) !void

Parameters

allocator: Allocator

std.array_hash_map.getAutoEqlFn

function

Source line 2239

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

Parameters

K: type
Context: type

std.array_hash_map.getAutoEqlFn.eql

function

Source line 2241

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

Parameters

ctx: Context
a: K
b: K
b_index: usize

std.array_hash_map.getAutoHashFn

function

Source line 2224

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

Parameters

K: type
Context: type

std.array_hash_map.getAutoHashFn.hash

function

Source line 2226

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

Parameters

ctx: Context
key: K

std.array_hash_map.getAutoHashStratFn

function

Source line 2267

pub fn getAutoHashStratFn(comptime K: type, comptime Context: type, comptime strategy: std.hash.Strategy) (fn (Context, K) u32)

Parameters

K: type
Context: type
strategy: std.hash.Strategy

std.array_hash_map.getAutoHashStratFn.hash

function

Source line 2269

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

Parameters

ctx: Context
key: K

std.array_hash_map.getHashPtrAddrFn

function

Source line 2199

pub fn getHashPtrAddrFn(comptime K: type, comptime Context: type) (fn (Context, K) u32)

Parameters

K: type
Context: type

std.array_hash_map.getHashPtrAddrFn.hash

function

Source line 2201

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

Parameters

ctx: Context
key: K

std.array_hash_map.getTrivialEqlFn

function

Source line 2208

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

Parameters

K: type
Context: type

std.array_hash_map.getTrivialEqlFn.eql

function

Source line 2210

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

Parameters

ctx: Context
a: K
b: K

std.array_hash_map.hash_map

alias

Source line 10

Alias of std.array_hash_map

std.array_hash_map.hashString

function

Source line 40

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

Parameters

s: []const u8

std.array_hash_map.Index

type-function

Source line 1583

A single entry in the lookup acceleration structure. These structs are found in an array after the IndexHeader. Hashes index into this array, and linear probing is used for collisions.

fn Index(comptime I: type) type

Parameters

I: type

Fields

entry_index: I

The index of this entry in the backing store. If the index is empty, this is empty_sentinel.

distance_from_start_index: I

The distance between this slot and its ideal placement. This is used to keep maximum scan length small. This value is undefined if the index is empty.

std.array_hash_map.index_capacities

constant

Source line 1625

std.array_hash_map.Index.empty

constant

Source line 1600

A constant empty index

std.array_hash_map.Index.empty_sentinel

constant

Source line 1597

The special entry_index value marking an empty slot.

std.array_hash_map.Index.isEmpty

function

Source line 1606

Checks if a slot is empty

fn isEmpty(idx: Self) bool

Parameters

idx: Self

std.array_hash_map.Index.Self

alias

Source line 1585

Alias of std.array_hash_map.Index

std.array_hash_map.Index.setEmpty

function

Source line 1611

Sets a slot to empty

fn setEmpty(idx: *Self) void

Parameters

idx: *Self

std.array_hash_map.IndexHeader

container

Source line 1643

This struct is trailed by two arrays of length indexes_len of integers, whose integer size is determined by indexes_len. These arrays are indexed by constrainIndex(hash). The entryIndexes array contains the index in the dense backing store where the entry's data can be found. Entries which are not in use have their index value set to emptySentinel(I). The entryDistances array stores the distance between an entry and its ideal hash bucket. This is used when adding elements to balance the maximum scan length.

Fields

bit_index: u8 align(@alignOf(u32))

This field tracks the total number of items in the arrays following this header. It is the bit index of the power of two number of indices. This value is between min_bit_index and max_bit_index, inclusive.

std.array_hash_map.IndexHeader.alloc

function

Source line 1689

Allocates an index header, and fills the entryIndexes array with empty. The distance array contents are undefined.

fn alloc(gpa: Allocator, new_bit_index: u8) Allocator.Error!*IndexHeader

Parameters

gpa: Allocator
new_bit_index: u8

Errors

OutOfMemory

std.array_hash_map.IndexHeader.capacity

function

Source line 1668

fn capacity(self: IndexHeader) u32

Parameters

self: IndexHeader

std.array_hash_map.IndexHeader.capacityIndexType

function

Source line 1664

Returns the type used for the index arrays.

fn capacityIndexType(header: IndexHeader) CapacityIndexType

Parameters

header: IndexHeader

std.array_hash_map.IndexHeader.constrainIndex

function

Source line 1650

Map from an incrementing index to an index slot in the attached arrays.

fn constrainIndex(header: IndexHeader, i: usize) usize

Parameters

header: IndexHeader
i: usize

std.array_hash_map.IndexHeader.findBitIndex

function

Source line 1678

fn findBitIndex(desired_capacity: usize) Allocator.Error!u8

Parameters

desired_capacity: usize

Errors

OutOfMemory

std.array_hash_map.IndexHeader.free

function

Source line 1703

Releases the memory for a header and its associated arrays.

fn free(header: *IndexHeader, gpa: Allocator) void

Parameters

header: *IndexHeader
gpa: Allocator

std.array_hash_map.IndexHeader.indexes

function

Source line 1658

Returns the attached array of indexes. I must match the type returned by capacityIndexType.

fn indexes(header: *IndexHeader, comptime I: type) []Index(I)

Parameters

header: *IndexHeader
I: type

std.array_hash_map.IndexHeader.length

function

Source line 1671

fn length(self: IndexHeader) usize

Parameters

self: IndexHeader

std.array_hash_map.IndexHeader.mask

function

Source line 1674

fn mask(self: IndexHeader) u32

Parameters

self: IndexHeader

std.array_hash_map.IndexHeader.reset

function

Source line 1711

Puts an IndexHeader into the state that it would be in after being freshly allocated.

fn reset(header: *IndexHeader) void

Parameters

header: *IndexHeader

std.array_hash_map.lessThan

function

Source line 2083

pub fn lessThan(ctx: @This(), a_index: usize, b_index: usize) bool

Parameters

ctx: @This()
a_index: usize
b_index: usize

std.array_hash_map.math

alias

Source line 5

Alias of std.math

std.array_hash_map.max_bit_index

constant

Source line 1622

std.array_hash_map.max_capacity

constant

Source line 1624

std.array_hash_map.max_representable_index_len

constant

Source line 1621

the byte size of the index must fit in a usize. This is a power of two length * the size of an Index(u32). The index is 8 bytes (3 bits repr) and max_usize + 1 is not representable, so we need to subtract out 4 bits.

std.array_hash_map.mem

alias

Source line 6

Alias of std.mem

std.array_hash_map.min_bit_index

constant

Source line 1623

std.array_hash_map.safeTruncate

function

Source line 1574

@truncate fails if the target type is larger than the target value. This causes problems when one of the types is usize, which may be larger or smaller than u32 on different systems. This version of truncate is safe to use if either parameter has dynamic size, and will perform widening conversion when needed. Both arguments must have the same signedness.

fn safeTruncate(comptime T: type, val: anytype) T

Parameters

T: type

std.array_hash_map.std

alias

Source line 1

Alias of std

std.array_hash_map.String

type-function

Source line 20

An ArrayHashMap with strings as keys.

pub fn String(comptime V: type) type

Parameters

V: type

Fields

entries: DataList = .{}

It is permitted to access this field directly. After any modification to the keys, consider calling reIndex.

index_header: ?*IndexHeader = null

When entries length is less than linear_scan_max, this remains null. Once entries length grows big enough, this field is allocated. There is an IndexHeader followed by an array of Index(I) structs, where I is defined by how many total indexes there are.

pointer_stability: std.debug.SafetyLock = .{}

Used to detect memory safety violations.

std.array_hash_map.StringContext

namespace

Source line 24

std.array_hash_map.StringContext.eql

function

Source line 29

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

Parameters

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

std.array_hash_map.StringContext.hash

function

Source line 25

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

Parameters

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

std.array_hash_map.testing

alias

Source line 4

Alias of std.testing

std.array_hash_map.Wyhash

alias

Source line 8

Alias of std.hash.Wyhash

Source code

std/array_hash_map.zig

const std = @import("std.zig");
const debug = std.debug;
const assert = debug.assert;
const testing = std.testing;
const math = std.math;
const mem = std.mem;
const autoHash = std.hash.autoHash;
const Wyhash = std.hash.Wyhash;
const Allocator = mem.Allocator;
const hash_map = @This();

/// An `ArrayHashMap` with default hash and equal functions.
///
/// See `AutoContext` for a description of the hash and equal implementations.
pub fn Auto(comptime K: type, comptime V: type) type {
    return Custom(K, V, AutoContext(K), !autoEqlIsCheap(K));
}

/// An `ArrayHashMap` with strings as keys.
pub fn String(comptime V: type) type {
    return Custom([]const u8, V, StringContext, true);
}

pub const StringContext = struct {
    pub fn hash(self: @This(), s: []const u8) u32 {
        _ = self;
        return hashString(s);
    }
    pub fn eql(self: @This(), a: []const u8, b: []const u8, b_index: usize) bool {
        _ = self;
        _ = b_index;
        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) u32 {
    return @truncate(std.hash.Wyhash.hash(0, s));
}

/// Deprecated; use `Custom`.
pub const ArrayHashMap = Custom;

/// A hash table of keys and values, each stored sequentially.
///
/// Insertion order is preserved. In general, this data structure supports the same
/// operations as `std.ArrayList`.
///
/// Deletion operations:
/// * `swapRemove` - O(1)
/// * `orderedRemove` - O(N)
///
/// Modifying the hash map while iterating is allowed, however, one must understand
/// the (well defined) behavior when mixing insertions and deletions with iteration.
///
/// This type does not store an `Allocator` field - the `Allocator` must be passed in
/// with each function call that requires it.
///
/// Can be initialized directly using the default field values.
///
/// This type is designed to have low overhead for small numbers of entries. When
/// `store_hash` is `false` and the number of entries in the map is less than 9,
/// the overhead cost of using `ArrayHashMap` rather than `std.ArrayList` is
/// only a single pointer-sized integer.
///
/// Default initialization of this struct is deprecated; use `.empty` instead.
pub fn Custom(
    comptime K: type,
    comptime V: type,
    /// A namespace that provides these two functions:
    /// * `pub fn hash(self, K) u32`
    /// * `pub fn eql(self, K, K, usize) bool`
    ///
    /// The final `usize` in the `eql` function represents the index of the key
    /// that's already inside the map.
    comptime Context: type,
    /// When `false`, this data structure is biased towards cheap `eql`
    /// functions and avoids storing each key's hash in the table. Setting
    /// `store_hash` to `true` incurs more memory cost but limits `eql` to
    /// being called only once per insertion/deletion (provided there are no
    /// hash collisions).
    comptime store_hash: bool,
) type {
    return struct {
        /// It is permitted to access this field directly.
        /// After any modification to the keys, consider calling `reIndex`.
        entries: DataList = .{},

        /// When entries length is less than `linear_scan_max`, this remains `null`.
        /// Once entries length grows big enough, this field is allocated. There is
        /// an IndexHeader followed by an array of Index(I) structs, where I is defined
        /// by how many total indexes there are.
        index_header: ?*IndexHeader = null,

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

        /// A map containing no keys or values.
        pub const empty: Self = .{
            .entries = .{},
            .index_header = null,
        };

        /// Modifying the key is allowed only if it does not change the hash.
        /// Modifying the value is allowed.
        /// Entry pointers become invalid whenever this ArrayHashMap is modified,
        /// unless `ensureTotalCapacity`/`ensureUnusedCapacity` was previously used.
        pub const Entry = struct {
            key_ptr: *K,
            value_ptr: *V,
        };

        /// A KV pair which has been copied out of the backing store
        pub const KV = struct {
            key: K,
            value: V,
        };

        /// The Data type used for the MultiArrayList backing this map
        pub const Data = struct {
            hash: Hash,
            key: K,
            value: V,
        };

        /// The MultiArrayList type backing this map
        pub const DataList = std.MultiArrayList(Data);

        /// The stored hash type, either u32 or void.
        pub const Hash = if (store_hash) u32 else void;

        /// getOrPut variants return this structure, with pointers
        /// to the backing store and a flag to indicate whether an
        /// existing entry was found.
        /// Modifying the key is allowed only if it does not change the hash.
        /// Modifying the value is allowed.
        /// Entry pointers become invalid whenever this ArrayHashMap is modified,
        /// unless `ensureTotalCapacity`/`ensureUnusedCapacity` was previously used.
        pub const GetOrPutResult = struct {
            key_ptr: *K,
            value_ptr: *V,
            found_existing: bool,
            index: usize,
        };

        /// Some functions require a context only if hashes are not stored.
        /// To keep the api simple, this type is only used internally.
        const ByIndexContext = if (store_hash) void else Context;

        const Self = @This();

        const linear_scan_max = @as(comptime_int, @max(1, @as(comptime_int, @min(
            std.atomic.cache_line / @as(comptime_int, @max(1, @sizeOf(Hash))),
            std.atomic.cache_line / @as(comptime_int, @max(1, @sizeOf(K))),
        ))));

        const RemovalType = enum {
            swap,
            ordered,
        };

        const Oom = Allocator.Error;

        pub fn init(gpa: Allocator, key_list: []const K, value_list: []const V) Oom!Self {
            var self: Self = .{};
            errdefer self.deinit(gpa);
            try self.reinit(gpa, key_list, value_list);
            return self;
        }

        /// An empty `value_list` may be passed, in which case the values array becomes `undefined`.
        pub fn reinit(self: *Self, gpa: Allocator, key_list: []const K, value_list: []const V) Oom!void {
            try self.entries.resize(gpa, key_list.len);
            @memcpy(self.keys(), key_list);
            if (value_list.len == 0) {
                @memset(self.values(), undefined);
            } else {
                assert(key_list.len == value_list.len);
                @memcpy(self.values(), value_list);
            }
            try self.reIndex(gpa);
        }

        /// Frees the backing allocation and leaves the map in an undefined state.
        /// Note that this does not free keys or values.  You must take care of that
        /// before calling this function, if it is needed.
        pub fn deinit(self: *Self, gpa: Allocator) void {
            self.pointer_stability.assertUnlocked();
            self.entries.deinit(gpa);
            if (self.index_header) |header| {
                header.free(gpa);
            }
            self.* = undefined;
        }

        /// 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();
        }

        /// Clears the map but retains the backing allocation for future use.
        pub fn clearRetainingCapacity(self: *Self) void {
            self.pointer_stability.lock();
            defer self.pointer_stability.unlock();

            self.entries.len = 0;
            if (self.index_header) |header| {
                switch (header.capacityIndexType()) {
                    .u8 => @memset(header.indexes(u8), Index(u8).empty),
                    .u16 => @memset(header.indexes(u16), Index(u16).empty),
                    .u32 => @memset(header.indexes(u32), Index(u32).empty),
                }
            }
        }

        /// Clears the map and releases the backing allocation
        pub fn clearAndFree(self: *Self, gpa: Allocator) void {
            self.pointer_stability.lock();
            defer self.pointer_stability.unlock();

            self.entries.shrinkAndFree(gpa, 0);
            if (self.index_header) |header| {
                header.free(gpa);
                self.index_header = null;
            }
        }

        /// Returns the number of KV pairs stored in this map.
        pub fn count(self: Self) usize {
            return self.entries.len;
        }

        /// Returns the backing array of keys in this map. Modifying the map may
        /// invalidate this array. Modifying this array in a way that changes
        /// key hashes or key equality puts the map into an unusable state until
        /// `reIndex` is called.
        pub fn keys(self: Self) []K {
            return self.entries.items(.key);
        }
        /// Returns the backing array of values in this map. Modifying the map
        /// may invalidate this array. It is permitted to modify the values in
        /// this array.
        pub fn values(self: Self) []V {
            return self.entries.items(.value);
        }

        /// Returns an iterator over the pairs in this map.
        /// Modifying the map may invalidate this iterator.
        pub fn iterator(self: Self) Iterator {
            const slice = self.entries.slice();
            return .{
                .keys = slice.items(.key).ptr,
                .values = slice.items(.value).ptr,
                .len = @as(u32, @intCast(slice.len)),
            };
        }
        pub const Iterator = struct {
            keys: [*]K,
            values: [*]V,
            len: u32,
            index: u32 = 0,

            pub fn next(it: *Iterator) ?Entry {
                if (it.index >= it.len) return null;
                const result = Entry{
                    .key_ptr = &it.keys[it.index],
                    .value_ptr = &it.values[it.index],
                };
                it.index += 1;
                return result;
            }

            /// Reset the iterator to the initial index
            pub fn reset(it: *Iterator) void {
                it.index = 0;
            }
        };

        /// If key exists this function cannot fail.
        /// If there is an existing item with `key`, then the result
        /// `Entry` pointer points to it, and found_existing is true.
        /// Otherwise, puts a new item with undefined value, and
        /// the `Entry` pointer points to it. Caller should then initialize
        /// the value (but not the key).
        pub fn getOrPut(self: *Self, gpa: Allocator, key: K) Oom!GetOrPutResult {
            if (@sizeOf(Context) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getOrPutContext instead.");
            return self.getOrPutContext(gpa, key, undefined);
        }
        pub fn getOrPutContext(self: *Self, gpa: Allocator, key: K, ctx: Context) Oom!GetOrPutResult {
            const gop = try self.getOrPutContextAdapted(gpa, key, ctx, ctx);
            if (!gop.found_existing) {
                gop.key_ptr.* = key;
            }
            return gop;
        }
        pub fn getOrPutAdapted(self: *Self, gpa: Allocator, key: anytype, key_ctx: anytype) Oom!GetOrPutResult {
            if (@sizeOf(Context) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getOrPutContextAdapted instead.");
            return self.getOrPutContextAdapted(gpa, key, key_ctx, undefined);
        }
        pub fn getOrPutContextAdapted(self: *Self, gpa: Allocator, key: anytype, key_ctx: anytype, ctx: Context) Oom!GetOrPutResult {
            self.ensureTotalCapacityContext(gpa, self.entries.len + 1, ctx) catch |err| {
                // "If key exists this function cannot fail."
                const index = self.getIndexAdapted(key, key_ctx) orelse return err;
                const slice = self.entries.slice();
                return GetOrPutResult{
                    .key_ptr = &slice.items(.key)[index],
                    .value_ptr = &slice.items(.value)[index],
                    .found_existing = true,
                    .index = index,
                };
            };
            return self.getOrPutAssumeCapacityAdapted(key, key_ctx);
        }

        /// If there is an existing item with `key`, then the result
        /// `Entry` pointer points to it, and found_existing is true.
        /// Otherwise, puts a new item with undefined value, and
        /// the `Entry` pointer points 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 {
            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 gop = self.getOrPutAssumeCapacityAdapted(key, ctx);
            if (!gop.found_existing) {
                gop.key_ptr.* = key;
            }
            return gop;
        }
        /// If there is an existing item with `key`, then the result
        /// `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
        /// both the key and the 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 {
            const header = self.index_header orelse {
                // Linear scan.
                const h = if (store_hash) checkedHash(ctx, key) else {};
                const slice = self.entries.slice();
                const hashes_array = slice.items(.hash);
                const keys_array = slice.items(.key);
                for (keys_array, 0..) |*item_key, i| {
                    if (hashes_array[i] == h and checkedEql(ctx, key, item_key.*, i)) {
                        return GetOrPutResult{
                            .key_ptr = item_key,
                            .value_ptr = &slice.items(.value)[i],
                            .found_existing = true,
                            .index = i,
                        };
                    }
                }

                const index = self.entries.addOneAssumeCapacity();
                // The slice length changed, so we directly index the pointer.
                if (store_hash) hashes_array.ptr[index] = h;

                return GetOrPutResult{
                    .key_ptr = &keys_array.ptr[index],
                    .value_ptr = &slice.items(.value).ptr[index],
                    .found_existing = false,
                    .index = index,
                };
            };

            switch (header.capacityIndexType()) {
                .u8 => return self.getOrPutInternal(key, ctx, header, u8),
                .u16 => return self.getOrPutInternal(key, ctx, header, u16),
                .u32 => return self.getOrPutInternal(key, ctx, header, u32),
            }
        }

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

        /// Increases capacity, guaranteeing that insertions up until the
        /// `expected_count` will not cause an allocation, and therefore cannot fail.
        pub fn ensureTotalCapacity(self: *Self, gpa: Allocator, new_capacity: usize) Oom!void {
            if (@sizeOf(ByIndexContext) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call ensureTotalCapacityContext instead.");
            return self.ensureTotalCapacityContext(gpa, new_capacity, undefined);
        }
        pub fn ensureTotalCapacityContext(self: *Self, gpa: Allocator, new_capacity: usize, ctx: Context) Oom!void {
            self.pointer_stability.lock();
            defer self.pointer_stability.unlock();

            try self.entries.ensureTotalCapacity(gpa, new_capacity);
            if (new_capacity <= linear_scan_max) return;
            if (self.index_header) |header| if (new_capacity <= header.capacity()) return;

            const new_bit_index = try IndexHeader.findBitIndex(new_capacity);
            const new_header = try IndexHeader.alloc(gpa, new_bit_index);

            if (self.index_header) |old_header| old_header.free(gpa);
            self.insertAllEntriesIntoNewHeader(if (store_hash) {} else ctx, new_header);
            self.index_header = new_header;
        }

        /// 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,
            gpa: Allocator,
            additional_capacity: usize,
        ) Oom!void {
            if (@sizeOf(Context) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call ensureTotalCapacityContext instead.");
            return self.ensureUnusedCapacityContext(gpa, additional_capacity, undefined);
        }
        pub fn ensureUnusedCapacityContext(
            self: *Self,
            gpa: Allocator,
            additional_capacity: usize,
            ctx: Context,
        ) Oom!void {
            return self.ensureTotalCapacityContext(gpa, self.count() + additional_capacity, 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) usize {
            const entry_cap = self.entries.capacity;
            const header = self.index_header orelse return @min(linear_scan_max, entry_cap);
            const indexes_cap = header.capacity();
            return @min(entry_cap, indexes_cap);
        }

        /// Clobbers any existing data. To detect if a put would clobber
        /// existing data, see `getOrPut`.
        pub fn put(self: *Self, gpa: Allocator, key: K, value: V) Oom!void {
            if (@sizeOf(Context) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call putContext instead.");
            return self.putContext(gpa, key, value, undefined);
        }
        pub fn putContext(self: *Self, gpa: Allocator, key: K, value: V, ctx: Context) Oom!void {
            const result = try self.getOrPutContext(gpa, key, ctx);
            result.value_ptr.* = value;
        }

        /// 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, gpa: Allocator, key: K, value: V) Oom!void {
            if (@sizeOf(Context) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call putNoClobberContext instead.");
            return self.putNoClobberContext(gpa, key, value, undefined);
        }
        pub fn putNoClobberContext(self: *Self, gpa: Allocator, key: K, value: V, ctx: Context) Oom!void {
            const result = try self.getOrPutContext(gpa, key, ctx);
            assert(!result.found_existing);
            result.value_ptr.* = value;
        }

        /// 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 result = self.getOrPutAssumeCapacityContext(key, ctx);
            result.value_ptr.* = value;
        }

        /// 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 {
            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 {
            const result = self.getOrPutAssumeCapacityContext(key, ctx);
            assert(!result.found_existing);
            result.value_ptr.* = value;
        }

        /// Inserts a new `Entry` into the hash map, returning the previous one, if any.
        pub fn fetchPut(self: *Self, gpa: Allocator, key: K, value: V) Oom!?KV {
            if (@sizeOf(Context) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call fetchPutContext instead.");
            return self.fetchPutContext(gpa, key, value, undefined);
        }
        pub fn fetchPutContext(self: *Self, gpa: Allocator, key: K, value: V, ctx: Context) Oom!?KV {
            const gop = try self.getOrPutContext(gpa, 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;
        }

        /// Finds pointers to the key and value storage associated with a key.
        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 {
            const index = self.getIndexAdapted(key, ctx) orelse return null;
            const slice = self.entries.slice();
            return Entry{
                .key_ptr = &slice.items(.key)[index],
                .value_ptr = &slice.items(.value)[index],
            };
        }

        /// Finds the index in the `entries` array where a key is stored
        pub fn getIndex(self: Self, key: K) ?usize {
            if (@sizeOf(Context) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getIndexContext instead.");
            return self.getIndexContext(key, undefined);
        }
        pub fn getIndexContext(self: Self, key: K, ctx: Context) ?usize {
            return self.getIndexAdapted(key, ctx);
        }
        pub fn getIndexAdapted(self: Self, key: anytype, ctx: anytype) ?usize {
            const header = self.index_header orelse {
                // Linear scan.
                const h = if (store_hash) checkedHash(ctx, key) else {};
                const slice = self.entries.slice();
                const hashes_array = slice.items(.hash);
                const keys_array = slice.items(.key);
                for (keys_array, 0..) |*item_key, i| {
                    if (hashes_array[i] == h and checkedEql(ctx, key, item_key.*, i)) {
                        return i;
                    }
                }
                return null;
            };
            switch (header.capacityIndexType()) {
                .u8 => return self.getIndexWithHeaderGeneric(key, ctx, header, u8),
                .u16 => return self.getIndexWithHeaderGeneric(key, ctx, header, u16),
                .u32 => return self.getIndexWithHeaderGeneric(key, ctx, header, u32),
            }
        }
        fn getIndexWithHeaderGeneric(self: Self, key: anytype, ctx: anytype, header: *IndexHeader, comptime I: type) ?usize {
            const indexes = header.indexes(I);
            const slot = self.getSlotByKey(key, ctx, header, I, indexes) orelse return null;
            return indexes[slot].entry_index;
        }

        /// Find the value associated with a key
        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 {
            const index = self.getIndexAdapted(key, ctx) orelse return null;
            return self.values()[index];
        }

        /// Find a pointer to the value associated with a key
        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 {
            const index = self.getIndexAdapted(key, ctx) orelse return null;
            return &self.values()[index];
        }

        /// Find the actual key associated with an adapted key
        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 {
            const index = self.getIndexAdapted(key, ctx) orelse return null;
            return self.keys()[index];
        }

        /// Find a pointer to the actual key associated with an adapted key
        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 {
            const index = self.getIndexAdapted(key, ctx) orelse return null;
            return &self.keys()[index];
        }

        /// Check whether a key is stored 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.getIndexAdapted(key, ctx) != null;
        }

        /// If there is an `Entry` with a matching key, it is deleted from
        /// the hash map, and then returned from this function. The entry is
        /// removed from the underlying array by swapping it with the last
        /// element.
        pub fn fetchSwapRemove(self: *Self, key: K) ?KV {
            if (@sizeOf(Context) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call fetchSwapRemoveContext instead.");
            return self.fetchSwapRemoveContext(key, undefined);
        }
        pub fn fetchSwapRemoveContext(self: *Self, key: K, ctx: Context) ?KV {
            return self.fetchSwapRemoveContextAdapted(key, ctx, ctx);
        }
        pub fn fetchSwapRemoveAdapted(self: *Self, key: anytype, ctx: anytype) ?KV {
            if (@sizeOf(ByIndexContext) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call fetchSwapRemoveContextAdapted instead.");
            return self.fetchSwapRemoveContextAdapted(key, ctx, undefined);
        }
        pub fn fetchSwapRemoveContextAdapted(self: *Self, key: anytype, key_ctx: anytype, ctx: Context) ?KV {
            self.pointer_stability.lock();
            defer self.pointer_stability.unlock();

            return self.fetchRemoveByKey(key, key_ctx, if (store_hash) {} else ctx, .swap);
        }

        /// If there is an `Entry` with a matching key, it is deleted from
        /// the hash map, and then returned from this function. The entry is
        /// removed from the underlying array by shifting all elements forward
        /// thereby maintaining the current ordering.
        pub fn fetchOrderedRemove(self: *Self, key: K) ?KV {
            if (@sizeOf(Context) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call fetchOrderedRemoveContext instead.");
            return self.fetchOrderedRemoveContext(key, undefined);
        }
        pub fn fetchOrderedRemoveContext(self: *Self, key: K, ctx: Context) ?KV {
            return self.fetchOrderedRemoveContextAdapted(key, ctx, ctx);
        }
        pub fn fetchOrderedRemoveAdapted(self: *Self, key: anytype, ctx: anytype) ?KV {
            if (@sizeOf(ByIndexContext) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call fetchOrderedRemoveContextAdapted instead.");
            return self.fetchOrderedRemoveContextAdapted(key, ctx, undefined);
        }
        pub fn fetchOrderedRemoveContextAdapted(self: *Self, key: anytype, key_ctx: anytype, ctx: Context) ?KV {
            self.pointer_stability.lock();
            defer self.pointer_stability.unlock();

            return self.fetchRemoveByKey(key, key_ctx, if (store_hash) {} else ctx, .ordered);
        }

        /// If there is an `Entry` with a matching key, it is deleted from
        /// the hash map. The entry is removed from the underlying array
        /// by swapping it with the last element.  Returns true if an entry
        /// was removed, false otherwise.
        pub fn swapRemove(self: *Self, key: K) bool {
            if (@sizeOf(Context) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call swapRemoveContext instead.");
            return self.swapRemoveContext(key, undefined);
        }
        pub fn swapRemoveContext(self: *Self, key: K, ctx: Context) bool {
            return self.swapRemoveContextAdapted(key, ctx, ctx);
        }
        pub fn swapRemoveAdapted(self: *Self, key: anytype, ctx: anytype) bool {
            if (@sizeOf(ByIndexContext) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call swapRemoveContextAdapted instead.");
            return self.swapRemoveContextAdapted(key, ctx, undefined);
        }
        pub fn swapRemoveContextAdapted(self: *Self, key: anytype, key_ctx: anytype, ctx: Context) bool {
            self.pointer_stability.lock();
            defer self.pointer_stability.unlock();

            return self.removeByKey(key, key_ctx, if (store_hash) {} else ctx, .swap);
        }

        /// If there is an `Entry` with a matching key, it is deleted from
        /// the hash map. The entry is removed from the underlying array
        /// by shifting all elements forward, thereby maintaining the
        /// current ordering.  Returns true if an entry was removed, false otherwise.
        pub fn orderedRemove(self: *Self, key: K) bool {
            if (@sizeOf(Context) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call orderedRemoveContext instead.");
            return self.orderedRemoveContext(key, undefined);
        }
        pub fn orderedRemoveContext(self: *Self, key: K, ctx: Context) bool {
            return self.orderedRemoveContextAdapted(key, ctx, ctx);
        }
        pub fn orderedRemoveAdapted(self: *Self, key: anytype, ctx: anytype) bool {
            if (@sizeOf(ByIndexContext) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call orderedRemoveContextAdapted instead.");
            return self.orderedRemoveContextAdapted(key, ctx, undefined);
        }
        pub fn orderedRemoveContextAdapted(self: *Self, key: anytype, key_ctx: anytype, ctx: Context) bool {
            self.pointer_stability.lock();
            defer self.pointer_stability.unlock();

            return self.removeByKey(key, key_ctx, if (store_hash) {} else ctx, .ordered);
        }

        /// Deletes the item at the specified index in `entries` from
        /// the hash map. The entry is removed from the underlying array
        /// by swapping it with the last element.
        pub fn swapRemoveAt(self: *Self, index: usize) void {
            if (@sizeOf(ByIndexContext) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call swapRemoveAtContext instead.");
            return self.swapRemoveAtContext(index, undefined);
        }
        pub fn swapRemoveAtContext(self: *Self, index: usize, ctx: Context) void {
            self.pointer_stability.lock();
            defer self.pointer_stability.unlock();

            self.removeByIndex(index, if (store_hash) {} else ctx, .swap);
        }

        /// Deletes the item at the specified index in `entries` from
        /// the hash map. The entry is removed from the underlying array
        /// by shifting all elements forward, thereby maintaining the
        /// current ordering.
        pub fn orderedRemoveAt(self: *Self, index: usize) void {
            if (@sizeOf(ByIndexContext) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call orderedRemoveAtContext instead.");
            return self.orderedRemoveAtContext(index, undefined);
        }
        pub fn orderedRemoveAtContext(self: *Self, index: usize, ctx: Context) void {
            self.pointer_stability.lock();
            defer self.pointer_stability.unlock();

            self.removeByIndex(index, if (store_hash) {} else ctx, .ordered);
        }

        /// Remove the entries indexed by `sorted_indexes`. The indexes to be
        /// removed correspond to state before deletion.
        ///
        /// This operation is O(N).
        ///
        /// Asserts that each index to be removed is in bounds.
        ///
        /// Invalidates key and element pointers beyond the first deleted index.
        pub fn orderedRemoveAtMany(self: *Self, gpa: Allocator, sorted_indexes: []const usize) Oom!void {
            if (@sizeOf(ByIndexContext) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call orderedRemoveAtContext instead.");
            return self.orderedRemoveAtManyContext(gpa, sorted_indexes, undefined);
        }

        pub fn orderedRemoveAtManyContext(
            self: *Self,
            gpa: Allocator,
            sorted_indexes: []const usize,
            ctx: Context,
        ) Oom!void {
            self.pointer_stability.lock();
            defer self.pointer_stability.unlock();

            self.entries.orderedRemoveMany(sorted_indexes);
            try self.reIndexContext(gpa, ctx);
        }

        /// Create a copy of the hash map which can be modified separately.
        /// The copy uses the same context as this instance, but is allocated
        /// with the provided allocator.
        pub fn clone(self: Self, gpa: Allocator) Oom!Self {
            if (@sizeOf(ByIndexContext) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call cloneContext instead.");
            return self.cloneContext(gpa, undefined);
        }
        pub fn cloneContext(self: Self, gpa: Allocator, ctx: Context) Oom!Self {
            var other: Self = .{};
            other.entries = try self.entries.clone(gpa);
            errdefer other.entries.deinit(gpa);

            if (self.index_header) |header| {
                // TODO: I'm pretty sure this could be memcpy'd instead of
                // doing all this work.
                const new_header = try IndexHeader.alloc(gpa, header.bit_index);
                other.insertAllEntriesIntoNewHeader(if (store_hash) {} else ctx, new_header);
                other.index_header = new_header;
            }
            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;
        }

        /// Recomputes stored hashes and rebuilds the key indexes. If the
        /// underlying keys have been modified directly, call this method to
        /// recompute the denormalized metadata necessary for the operation of
        /// the methods of this map that lookup entries by key.
        ///
        /// One use case for this is directly calling `entries.resize()` to grow
        /// the underlying storage, and then setting the `keys` and `values`
        /// directly without going through the methods of this map.
        ///
        /// The time complexity of this operation is O(n).
        pub fn reIndex(self: *Self, gpa: Allocator) Oom!void {
            if (@sizeOf(ByIndexContext) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call reIndexContext instead.");
            return self.reIndexContext(gpa, undefined);
        }

        pub fn reIndexContext(self: *Self, gpa: Allocator, ctx: Context) Oom!void {
            // Recompute all hashes.
            if (store_hash) {
                for (self.keys(), self.entries.items(.hash)) |key, *hash| {
                    const h = checkedHash(ctx, key);
                    hash.* = h;
                }
            }
            try rebuildIndex(self, gpa, ctx);
        }

        /// Modify an entry's key without reordering any entries.
        pub fn setKey(self: *Self, index: usize, new_key: K) void {
            if (@sizeOf(ByIndexContext) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call setKeyContext instead.");
            return setKeyContext(self, index, new_key, undefined);
        }

        pub fn setKeyContext(self: *Self, index: usize, new_key: K, ctx: Context) void {
            if (self.index_header) |header| {
                self.removeFromIndexByIndex(index, if (store_hash) {} else ctx, header);

                self.entries.items(.key)[index] = new_key;
                const h = checkedHash(ctx, new_key);
                if (store_hash) self.entries.items(.hash)[index] = h;

                insertEntryIntoNewHeader(header, h, index);
            } else {
                self.entries.items(.key)[index] = new_key;
                if (store_hash) self.entries.items(.hash)[index] = checkedHash(ctx, new_key);
            }
        }

        fn rebuildIndex(self: *Self, gpa: Allocator, ctx: Context) Oom!void {
            if (self.entries.capacity <= linear_scan_max) return;

            // We're going to rebuild the index header and replace the existing one (if any). The
            // indexes should sized such that they will be at most 60% full.
            const bit_index = try IndexHeader.findBitIndex(self.entries.capacity);
            const new_header = try IndexHeader.alloc(gpa, bit_index);
            if (self.index_header) |header| header.free(gpa);
            self.insertAllEntriesIntoNewHeader(if (store_hash) {} else ctx, new_header);
            self.index_header = new_header;
        }

        /// Sorts the entries and then rebuilds the index.
        /// `sort_ctx` must have this method:
        /// `fn lessThan(ctx: @TypeOf(ctx), a_index: usize, b_index: usize) bool`
        /// Uses a stable sorting algorithm.
        pub inline fn sort(self: *Self, sort_ctx: anytype) void {
            if (@sizeOf(ByIndexContext) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call sortContext instead.");
            return sortContextInternal(self, .stable, sort_ctx, undefined);
        }

        /// Sorts the entries and then rebuilds the index.
        /// `sort_ctx` must have this method:
        /// `fn lessThan(ctx: @TypeOf(ctx), a_index: usize, b_index: usize) bool`
        /// Uses an unstable sorting algorithm.
        pub inline fn sortUnstable(self: *Self, sort_ctx: anytype) void {
            if (@sizeOf(ByIndexContext) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call sortUnstableContext instead.");
            return self.sortContextInternal(.unstable, sort_ctx, undefined);
        }

        pub inline fn sortContext(self: *Self, sort_ctx: anytype, ctx: Context) void {
            return sortContextInternal(self, .stable, sort_ctx, ctx);
        }

        pub inline fn sortUnstableContext(self: *Self, sort_ctx: anytype, ctx: Context) void {
            return sortContextInternal(self, .unstable, sort_ctx, ctx);
        }

        fn sortContextInternal(
            self: *Self,
            comptime mode: std.sort.Mode,
            sort_ctx: anytype,
            ctx: Context,
        ) void {
            self.pointer_stability.lock();
            defer self.pointer_stability.unlock();

            switch (mode) {
                .stable => self.entries.sort(sort_ctx),
                .unstable => self.entries.sortUnstable(sort_ctx),
            }
            const header = self.index_header orelse return;
            header.reset();
            self.insertAllEntriesIntoNewHeader(if (store_hash) {} else ctx, header);
        }

        /// Shrinks the underlying `Entry` array to `new_len` elements and
        /// discards any associated index entries. Keeps capacity the same.
        ///
        /// Asserts the discarded entries remain initialized and capable of
        /// performing hash and equality checks. Any deinitialization of
        /// discarded entries must take place *after* calling this function.
        pub fn shrinkRetainingCapacity(self: *Self, new_len: usize) void {
            if (@sizeOf(ByIndexContext) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call shrinkRetainingCapacityContext instead.");
            return self.shrinkRetainingCapacityContext(new_len, undefined);
        }

        /// Shrinks the underlying `Entry` array to `new_len` elements and
        /// discards any associated index entries. Keeps capacity the same.
        ///
        /// Asserts the discarded entries remain initialized and capable of
        /// performing hash and equality checks. Any deinitialization of
        /// discarded entries must take place *after* calling this function.
        pub fn shrinkRetainingCapacityContext(self: *Self, new_len: usize, ctx: Context) void {
            self.pointer_stability.lock();
            defer self.pointer_stability.unlock();

            // Remove index entries from the new length onwards.
            // Explicitly choose to ONLY remove index entries and not the underlying array list
            // entries as we're going to remove them in the subsequent shrink call.
            if (self.index_header) |header| {
                var i: usize = new_len;
                while (i < self.entries.len) : (i += 1)
                    self.removeFromIndexByIndex(i, if (store_hash) {} else ctx, header);
            }
            self.entries.shrinkRetainingCapacity(new_len);
        }

        /// Shrinks the underlying `Entry` array to `new_len` elements and
        /// discards any associated index entries. Reduces allocated capacity.
        ///
        /// Asserts the discarded entries remain initialized and capable of
        /// performing hash and equality checks. It is a bug to call this
        /// function if the discarded entries require deinitialization. For
        /// that use case, `shrinkRetainingCapacity` can be used instead.
        pub fn shrinkAndFree(self: *Self, gpa: Allocator, new_len: usize) void {
            if (@sizeOf(ByIndexContext) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call shrinkAndFreeContext instead.");
            return self.shrinkAndFreeContext(gpa, new_len, undefined);
        }

        /// Shrinks the underlying `Entry` array to `new_len` elements and
        /// discards any associated index entries. Reduces allocated capacity.
        ///
        /// Asserts the discarded entries remain initialized and capable of
        /// performing hash and equality checks. It is a bug to call this
        /// function if the discarded entries require deinitialization. For
        /// that use case, `shrinkRetainingCapacityContext` can be used
        /// instead.
        pub fn shrinkAndFreeContext(self: *Self, gpa: Allocator, new_len: usize, ctx: Context) void {
            self.pointer_stability.lock();
            defer self.pointer_stability.unlock();

            // Remove index entries from the new length onwards.
            // Explicitly choose to ONLY remove index entries and not the underlying array list
            // entries as we're going to remove them in the subsequent shrink call.
            if (self.index_header) |header| {
                var i: usize = new_len;
                while (i < self.entries.len) : (i += 1)
                    self.removeFromIndexByIndex(i, if (store_hash) {} else ctx, header);
            }
            self.entries.shrinkAndFree(gpa, new_len);
        }

        /// Removes the last inserted `Entry` in the hash map and returns it.
        /// Otherwise returns null.
        pub fn pop(self: *Self) ?KV {
            if (@sizeOf(ByIndexContext) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call popContext instead.");
            return self.popContext(undefined);
        }
        pub fn popContext(self: *Self, ctx: Context) ?KV {
            if (self.entries.len == 0) return null;
            self.pointer_stability.lock();
            defer self.pointer_stability.unlock();

            const item = self.entries.get(self.entries.len - 1);
            if (self.index_header) |header|
                self.removeFromIndexByIndex(self.entries.len - 1, if (store_hash) {} else ctx, header);
            self.entries.len -= 1;
            return .{
                .key = item.key,
                .value = item.value,
            };
        }

        fn fetchRemoveByKey(
            self: *Self,
            key: anytype,
            key_ctx: anytype,
            ctx: ByIndexContext,
            comptime removal_type: RemovalType,
        ) ?KV {
            const header = self.index_header orelse {
                // Linear scan.
                const key_hash = if (store_hash) key_ctx.hash(key) else {};
                const slice = self.entries.slice();
                const hashes_array = if (store_hash) slice.items(.hash) else {};
                const keys_array = slice.items(.key);
                for (keys_array, 0..) |*item_key, i| {
                    const hash_match = if (store_hash) hashes_array[i] == key_hash else true;
                    if (hash_match and key_ctx.eql(key, item_key.*, i)) {
                        const removed_entry: KV = .{
                            .key = keys_array[i],
                            .value = slice.items(.value)[i],
                        };
                        switch (removal_type) {
                            .swap => self.entries.swapRemove(i),
                            .ordered => self.entries.orderedRemove(i),
                        }
                        return removed_entry;
                    }
                }
                return null;
            };
            return switch (header.capacityIndexType()) {
                .u8 => self.fetchRemoveByKeyGeneric(key, key_ctx, ctx, header, u8, removal_type),
                .u16 => self.fetchRemoveByKeyGeneric(key, key_ctx, ctx, header, u16, removal_type),
                .u32 => self.fetchRemoveByKeyGeneric(key, key_ctx, ctx, header, u32, removal_type),
            };
        }
        fn fetchRemoveByKeyGeneric(
            self: *Self,
            key: anytype,
            key_ctx: anytype,
            ctx: ByIndexContext,
            header: *IndexHeader,
            comptime I: type,
            comptime removal_type: RemovalType,
        ) ?KV {
            const indexes = header.indexes(I);
            const entry_index = self.removeFromIndexByKey(key, key_ctx, header, I, indexes) orelse return null;
            const slice = self.entries.slice();
            const removed_entry: KV = .{
                .key = slice.items(.key)[entry_index],
                .value = slice.items(.value)[entry_index],
            };
            self.removeFromArrayAndUpdateIndex(entry_index, ctx, header, I, indexes, removal_type);
            return removed_entry;
        }

        fn removeByKey(
            self: *Self,
            key: anytype,
            key_ctx: anytype,
            ctx: ByIndexContext,
            comptime removal_type: RemovalType,
        ) bool {
            const header = self.index_header orelse {
                // Linear scan.
                const key_hash = if (store_hash) key_ctx.hash(key) else {};
                const slice = self.entries.slice();
                const hashes_array = if (store_hash) slice.items(.hash) else {};
                const keys_array = slice.items(.key);
                for (keys_array, 0..) |*item_key, i| {
                    const hash_match = if (store_hash) hashes_array[i] == key_hash else true;
                    if (hash_match and key_ctx.eql(key, item_key.*, i)) {
                        switch (removal_type) {
                            .swap => self.entries.swapRemove(i),
                            .ordered => self.entries.orderedRemove(i),
                        }
                        return true;
                    }
                }
                return false;
            };
            return switch (header.capacityIndexType()) {
                .u8 => self.removeByKeyGeneric(key, key_ctx, ctx, header, u8, removal_type),
                .u16 => self.removeByKeyGeneric(key, key_ctx, ctx, header, u16, removal_type),
                .u32 => self.removeByKeyGeneric(key, key_ctx, ctx, header, u32, removal_type),
            };
        }
        fn removeByKeyGeneric(self: *Self, key: anytype, key_ctx: anytype, ctx: ByIndexContext, header: *IndexHeader, comptime I: type, comptime removal_type: RemovalType) bool {
            const indexes = header.indexes(I);
            const entry_index = self.removeFromIndexByKey(key, key_ctx, header, I, indexes) orelse return false;
            self.removeFromArrayAndUpdateIndex(entry_index, ctx, header, I, indexes, removal_type);
            return true;
        }

        fn removeByIndex(self: *Self, entry_index: usize, ctx: ByIndexContext, comptime removal_type: RemovalType) void {
            assert(entry_index < self.entries.len);
            const header = self.index_header orelse {
                switch (removal_type) {
                    .swap => self.entries.swapRemove(entry_index),
                    .ordered => self.entries.orderedRemove(entry_index),
                }
                return;
            };
            switch (header.capacityIndexType()) {
                .u8 => self.removeByIndexGeneric(entry_index, ctx, header, u8, removal_type),
                .u16 => self.removeByIndexGeneric(entry_index, ctx, header, u16, removal_type),
                .u32 => self.removeByIndexGeneric(entry_index, ctx, header, u32, removal_type),
            }
        }
        fn removeByIndexGeneric(self: *Self, entry_index: usize, ctx: ByIndexContext, header: *IndexHeader, comptime I: type, comptime removal_type: RemovalType) void {
            const indexes = header.indexes(I);
            self.removeFromIndexByIndexGeneric(entry_index, ctx, header, I, indexes);
            self.removeFromArrayAndUpdateIndex(entry_index, ctx, header, I, indexes, removal_type);
        }

        fn removeFromArrayAndUpdateIndex(self: *Self, entry_index: usize, ctx: ByIndexContext, header: *IndexHeader, comptime I: type, indexes: []Index(I), comptime removal_type: RemovalType) void {
            const last_index = self.entries.len - 1; // overflow => remove from empty map
            switch (removal_type) {
                .swap => {
                    if (last_index != entry_index) {
                        // Because of the swap remove, now we need to update the index that was
                        // pointing to the last entry and is now pointing to this removed item slot.
                        self.updateEntryIndex(header, last_index, entry_index, ctx, I, indexes);
                    }
                    // updateEntryIndex reads from the old entry index,
                    // so it needs to run before removal.
                    self.entries.swapRemove(entry_index);
                },
                .ordered => {
                    var i: usize = entry_index;
                    while (i < last_index) : (i += 1) {
                        // Because of the ordered remove, everything from the entry index onwards has
                        // been shifted forward so we'll need to update the index entries.
                        self.updateEntryIndex(header, i + 1, i, ctx, I, indexes);
                    }
                    // updateEntryIndex reads from the old entry index,
                    // so it needs to run before removal.
                    self.entries.orderedRemove(entry_index);
                },
            }
        }

        fn updateEntryIndex(
            self: *Self,
            header: *IndexHeader,
            old_entry_index: usize,
            new_entry_index: usize,
            ctx: ByIndexContext,
            comptime I: type,
            indexes: []Index(I),
        ) void {
            const slot = self.getSlotByIndex(old_entry_index, ctx, header, I, indexes);
            indexes[slot].entry_index = @as(I, @intCast(new_entry_index));
        }

        fn removeFromIndexByIndex(self: *Self, entry_index: usize, ctx: ByIndexContext, header: *IndexHeader) void {
            switch (header.capacityIndexType()) {
                .u8 => self.removeFromIndexByIndexGeneric(entry_index, ctx, header, u8, header.indexes(u8)),
                .u16 => self.removeFromIndexByIndexGeneric(entry_index, ctx, header, u16, header.indexes(u16)),
                .u32 => self.removeFromIndexByIndexGeneric(entry_index, ctx, header, u32, header.indexes(u32)),
            }
        }
        fn removeFromIndexByIndexGeneric(self: *Self, entry_index: usize, ctx: ByIndexContext, header: *IndexHeader, comptime I: type, indexes: []Index(I)) void {
            const slot = self.getSlotByIndex(entry_index, ctx, header, I, indexes);
            removeSlot(slot, header, I, indexes);
        }

        fn removeFromIndexByKey(self: *Self, key: anytype, ctx: anytype, header: *IndexHeader, comptime I: type, indexes: []Index(I)) ?usize {
            const slot = self.getSlotByKey(key, ctx, header, I, indexes) orelse return null;
            const removed_entry_index = indexes[slot].entry_index;
            removeSlot(slot, header, I, indexes);
            return removed_entry_index;
        }

        fn removeSlot(removed_slot: usize, header: *IndexHeader, comptime I: type, indexes: []Index(I)) void {
            const start_index = removed_slot +% 1;
            const end_index = start_index +% indexes.len;

            var last_slot = removed_slot;
            var index: usize = start_index;
            while (index != end_index) : (index +%= 1) {
                const slot = header.constrainIndex(index);
                const slot_data = indexes[slot];
                if (slot_data.isEmpty() or slot_data.distance_from_start_index == 0) {
                    indexes[last_slot].setEmpty();
                    return;
                }
                indexes[last_slot] = .{
                    .entry_index = slot_data.entry_index,
                    .distance_from_start_index = slot_data.distance_from_start_index - 1,
                };
                last_slot = slot;
            }
            unreachable;
        }

        fn getSlotByIndex(self: *Self, entry_index: usize, ctx: ByIndexContext, header: *IndexHeader, comptime I: type, indexes: []Index(I)) usize {
            const slice = self.entries.slice();
            const h = if (store_hash) slice.items(.hash)[entry_index] else checkedHash(ctx, slice.items(.key)[entry_index]);
            const start_index = safeTruncate(usize, h);
            const end_index = start_index +% indexes.len;

            var index = start_index;
            var distance_from_start_index: I = 0;
            while (index != end_index) : ({
                index +%= 1;
                distance_from_start_index += 1;
            }) {
                const slot = header.constrainIndex(index);
                const slot_data = indexes[slot];

                // This is the fundamental property of the array hash map index.  If this
                // assert fails, it probably means that the entry was not in the index.
                assert(!slot_data.isEmpty());
                assert(slot_data.distance_from_start_index >= distance_from_start_index);

                if (slot_data.entry_index == entry_index) {
                    return slot;
                }
            }
            unreachable;
        }

        /// Must `ensureTotalCapacity`/`ensureUnusedCapacity` before calling this.
        fn getOrPutInternal(self: *Self, key: anytype, ctx: anytype, header: *IndexHeader, comptime I: type) GetOrPutResult {
            const slice = self.entries.slice();
            const hashes_array = if (store_hash) slice.items(.hash) else {};
            const keys_array = slice.items(.key);
            const values_array = slice.items(.value);
            const indexes = header.indexes(I);

            const h = checkedHash(ctx, key);
            const start_index = safeTruncate(usize, h);
            const end_index = start_index +% indexes.len;

            var index = start_index;
            var distance_from_start_index: I = 0;
            while (index != end_index) : ({
                index +%= 1;
                distance_from_start_index += 1;
            }) {
                var slot = header.constrainIndex(index);
                var slot_data = indexes[slot];

                // If the slot is empty, there can be no more items in this run.
                // We didn't find a matching item, so this must be new.
                // Put it in the empty slot.
                if (slot_data.isEmpty()) {
                    const new_index = self.entries.addOneAssumeCapacity();
                    indexes[slot] = .{
                        .distance_from_start_index = distance_from_start_index,
                        .entry_index = @as(I, @intCast(new_index)),
                    };

                    // update the hash if applicable
                    if (store_hash) hashes_array.ptr[new_index] = h;

                    return .{
                        .found_existing = false,
                        .key_ptr = &keys_array.ptr[new_index],
                        .value_ptr = &values_array.ptr[new_index],
                        .index = new_index,
                    };
                }

                // This pointer survives the following append because we call
                // entries.ensureTotalCapacity before getOrPutInternal.
                const i = slot_data.entry_index;
                const hash_match = if (store_hash) h == hashes_array[i] else true;
                if (hash_match and checkedEql(ctx, key, keys_array[i], i)) {
                    return .{
                        .found_existing = true,
                        .key_ptr = &keys_array[slot_data.entry_index],
                        .value_ptr = &values_array[slot_data.entry_index],
                        .index = slot_data.entry_index,
                    };
                }

                // If the entry is closer to its target than our current distance,
                // the entry we are looking for does not exist.  It would be in
                // this slot instead if it was here.  So stop looking, and switch
                // to insert mode.
                if (slot_data.distance_from_start_index < distance_from_start_index) {
                    // In this case, we did not find the item. We will put a new entry.
                    // However, we will use this index for the new entry, and move
                    // the previous index down the line, to keep the max distance_from_start_index
                    // as small as possible.
                    const new_index = self.entries.addOneAssumeCapacity();
                    if (store_hash) hashes_array.ptr[new_index] = h;
                    indexes[slot] = .{
                        .entry_index = @as(I, @intCast(new_index)),
                        .distance_from_start_index = distance_from_start_index,
                    };
                    distance_from_start_index = slot_data.distance_from_start_index;
                    var displaced_index = slot_data.entry_index;

                    // Find somewhere to put the index we replaced by shifting
                    // following indexes backwards.
                    index +%= 1;
                    distance_from_start_index += 1;
                    while (index != end_index) : ({
                        index +%= 1;
                        distance_from_start_index += 1;
                    }) {
                        slot = header.constrainIndex(index);
                        slot_data = indexes[slot];
                        if (slot_data.isEmpty()) {
                            indexes[slot] = .{
                                .entry_index = displaced_index,
                                .distance_from_start_index = distance_from_start_index,
                            };
                            return .{
                                .found_existing = false,
                                .key_ptr = &keys_array.ptr[new_index],
                                .value_ptr = &values_array.ptr[new_index],
                                .index = new_index,
                            };
                        }

                        if (slot_data.distance_from_start_index < distance_from_start_index) {
                            indexes[slot] = .{
                                .entry_index = displaced_index,
                                .distance_from_start_index = distance_from_start_index,
                            };
                            displaced_index = slot_data.entry_index;
                            distance_from_start_index = slot_data.distance_from_start_index;
                        }
                    }
                    unreachable;
                }
            }
            unreachable;
        }

        fn getSlotByKey(self: Self, key: anytype, ctx: anytype, header: *IndexHeader, comptime I: type, indexes: []Index(I)) ?usize {
            const slice = self.entries.slice();
            const hashes_array = if (store_hash) slice.items(.hash) else {};
            const keys_array = slice.items(.key);
            const h = checkedHash(ctx, key);

            const start_index = safeTruncate(usize, h);
            const end_index = start_index +% indexes.len;

            var index = start_index;
            var distance_from_start_index: I = 0;
            while (index != end_index) : ({
                index +%= 1;
                distance_from_start_index += 1;
            }) {
                const slot = header.constrainIndex(index);
                const slot_data = indexes[slot];
                if (slot_data.isEmpty() or slot_data.distance_from_start_index < distance_from_start_index)
                    return null;

                const i = slot_data.entry_index;
                const hash_match = if (store_hash) h == hashes_array[i] else true;
                if (hash_match and checkedEql(ctx, key, keys_array[i], i))
                    return slot;
            }
            unreachable;
        }

        fn insertAllEntriesIntoNewHeader(self: *Self, ctx: ByIndexContext, header: *IndexHeader) void {
            switch (header.capacityIndexType()) {
                .u8 => return self.insertAllEntriesIntoNewHeaderGeneric(ctx, header, u8),
                .u16 => return self.insertAllEntriesIntoNewHeaderGeneric(ctx, header, u16),
                .u32 => return self.insertAllEntriesIntoNewHeaderGeneric(ctx, header, u32),
            }
        }
        fn insertAllEntriesIntoNewHeaderGeneric(self: *Self, ctx: ByIndexContext, header: *IndexHeader, comptime I: type) void {
            const slice = self.entries.slice();
            const items = if (store_hash) slice.items(.hash) else slice.items(.key);

            for (items, 0..) |hash_or_key, i| {
                const h = if (store_hash) hash_or_key else checkedHash(ctx, hash_or_key);
                insertEntryIntoNewHeaderGeneric(header, h, i, I);
            }
        }

        fn insertEntryIntoNewHeader(header: *IndexHeader, h: u32, i: usize) void {
            switch (header.capacityIndexType()) {
                .u8 => insertEntryIntoNewHeaderGeneric(header, h, i, u8),
                .u16 => insertEntryIntoNewHeaderGeneric(header, h, i, u16),
                .u32 => insertEntryIntoNewHeaderGeneric(header, h, i, u32),
            }
        }
        fn insertEntryIntoNewHeaderGeneric(header: *IndexHeader, h: u32, i: usize, comptime I: type) void {
            const indexes = header.indexes(I);
            const start_index = safeTruncate(usize, h);
            const end_index = start_index +% indexes.len;
            var index = start_index;
            var entry_index: I = @intCast(i);
            var distance_from_start_index: I = 0;
            while (index != end_index) : ({
                index +%= 1;
                distance_from_start_index += 1;
            }) {
                const slot = header.constrainIndex(index);
                const next_index = indexes[slot];
                if (next_index.isEmpty()) {
                    indexes[slot] = .{
                        .distance_from_start_index = distance_from_start_index,
                        .entry_index = entry_index,
                    };
                    return;
                }
                if (next_index.distance_from_start_index < distance_from_start_index) {
                    indexes[slot] = .{
                        .distance_from_start_index = distance_from_start_index,
                        .entry_index = entry_index,
                    };
                    distance_from_start_index = next_index.distance_from_start_index;
                    entry_index = next_index.entry_index;
                }
            }
            unreachable;
        }

        fn checkedHash(ctx: anytype, key: anytype) u32 {
            // If you get a compile error on the next line, it means that your
            // generic hash function doesn't accept your key.
            return ctx.hash(key);
        }

        fn checkedEql(ctx: anytype, a: anytype, b: K, b_index: usize) bool {
            // If you get a compile error on the next line, it means that your
            // generic eql function doesn't accept (self, adapt key, K, index).
            return ctx.eql(a, b, b_index);
        }

        fn dumpState(self: Self, comptime keyFmt: []const u8, comptime valueFmt: []const u8) void {
            if (@sizeOf(ByIndexContext) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call dumpStateContext instead.");
            self.dumpStateContext(keyFmt, valueFmt, undefined);
        }
        fn dumpStateContext(self: Self, comptime keyFmt: []const u8, comptime valueFmt: []const u8, ctx: Context) void {
            const p = std.debug.print;
            p("{s}:\n", .{@typeName(Self)});
            const slice = self.entries.slice();
            const hash_status = if (store_hash) "stored" else "computed";
            p("  len={} capacity={} hashes {s}\n", .{ slice.len, slice.capacity, hash_status });
            var i: usize = 0;
            const mask: u32 = if (self.index_header) |header| header.mask() else ~@as(u32, 0);
            while (i < slice.len) : (i += 1) {
                const hash = if (store_hash) slice.items(.hash)[i] else checkedHash(ctx, slice.items(.key)[i]);
                if (store_hash) {
                    p(
                        "  [{}]: key=" ++ keyFmt ++ " value=" ++ valueFmt ++ " hash=0x{x} slot=[0x{x}]\n",
                        .{ i, slice.items(.key)[i], slice.items(.value)[i], hash, hash & mask },
                    );
                } else {
                    p(
                        "  [{}]: key=" ++ keyFmt ++ " value=" ++ valueFmt ++ " slot=[0x{x}]\n",
                        .{ i, slice.items(.key)[i], slice.items(.value)[i], hash & mask },
                    );
                }
            }
            if (self.index_header) |header| {
                p("\n", .{});
                switch (header.capacityIndexType()) {
                    .u8 => dumpIndex(header, u8),
                    .u16 => dumpIndex(header, u16),
                    .u32 => dumpIndex(header, u32),
                }
            }
        }
        fn dumpIndex(header: *IndexHeader, comptime I: type) void {
            const p = std.debug.print;
            p("  index len=0x{x} type={}\n", .{ header.length(), header.capacityIndexType() });
            const indexes = header.indexes(I);
            if (indexes.len == 0) return;
            var is_empty = false;
            for (indexes, 0..) |idx, i| {
                if (idx.isEmpty()) {
                    is_empty = true;
                } else {
                    if (is_empty) {
                        is_empty = false;
                        p("  ...\n", .{});
                    }
                    p("  [0x{x}]: [{}] +{}\n", .{ i, idx.entry_index, idx.distance_from_start_index });
                }
            }
            if (is_empty) {
                p("  ...\n", .{});
            }
        }
    };
}

const CapacityIndexType = enum { u8, u16, u32 };

fn capacityIndexType(bit_index: u8) CapacityIndexType {
    if (bit_index <= 8)
        return .u8;
    if (bit_index <= 16)
        return .u16;
    assert(bit_index <= 32);
    return .u32;
}

fn capacityIndexSize(bit_index: u8) usize {
    switch (capacityIndexType(bit_index)) {
        .u8 => return @sizeOf(Index(u8)),
        .u16 => return @sizeOf(Index(u16)),
        .u32 => return @sizeOf(Index(u32)),
    }
}

/// @truncate fails if the target type is larger than the
/// target value.  This causes problems when one of the types
/// is usize, which may be larger or smaller than u32 on different
/// systems.  This version of truncate is safe to use if either
/// parameter has dynamic size, and will perform widening conversion
/// when needed.  Both arguments must have the same signedness.
fn safeTruncate(comptime T: type, val: anytype) T {
    if (@bitSizeOf(T) >= @bitSizeOf(@TypeOf(val)))
        return val;
    return @as(T, @truncate(val));
}

/// A single entry in the lookup acceleration structure.  These structs
/// are found in an array after the IndexHeader.  Hashes index into this
/// array, and linear probing is used for collisions.
fn Index(comptime I: type) type {
    return extern struct {
        const Self = @This();

        /// The index of this entry in the backing store.  If the index is
        /// empty, this is empty_sentinel.
        entry_index: I,

        /// The distance between this slot and its ideal placement.  This is
        /// used to keep maximum scan length small.  This value is undefined
        /// if the index is empty.
        distance_from_start_index: I,

        /// The special entry_index value marking an empty slot.
        const empty_sentinel = ~@as(I, 0);

        /// A constant empty index
        const empty = Self{
            .entry_index = empty_sentinel,
            .distance_from_start_index = undefined,
        };

        /// Checks if a slot is empty
        fn isEmpty(idx: Self) bool {
            return idx.entry_index == empty_sentinel;
        }

        /// Sets a slot to empty
        fn setEmpty(idx: *Self) void {
            idx.entry_index = empty_sentinel;
            idx.distance_from_start_index = undefined;
        }
    };
}

/// the byte size of the index must fit in a usize.  This is a power of two
/// length * the size of an Index(u32).  The index is 8 bytes (3 bits repr)
/// and max_usize + 1 is not representable, so we need to subtract out 4 bits.
const max_representable_index_len = @bitSizeOf(usize) - 4;
const max_bit_index = @min(32, max_representable_index_len);
const min_bit_index = 5;
const max_capacity = (1 << max_bit_index) - 1;
const index_capacities = blk: {
    var caps: [max_bit_index + 1]u32 = undefined;
    for (caps[0..max_bit_index], 0..) |*item, i| {
        item.* = (1 << i) * 3 / 5;
    }
    caps[max_bit_index] = max_capacity;
    break :blk caps;
};

/// This struct is trailed by two arrays of length indexes_len
/// of integers, whose integer size is determined by indexes_len.
/// These arrays are indexed by constrainIndex(hash).  The
/// entryIndexes array contains the index in the dense backing store
/// where the entry's data can be found.  Entries which are not in
/// use have their index value set to emptySentinel(I).
/// The entryDistances array stores the distance between an entry
/// and its ideal hash bucket.  This is used when adding elements
/// to balance the maximum scan length.
const IndexHeader = struct {
    /// This field tracks the total number of items in the arrays following
    /// this header.  It is the bit index of the power of two number of indices.
    /// This value is between min_bit_index and max_bit_index, inclusive.
    bit_index: u8 align(@alignOf(u32)),

    /// Map from an incrementing index to an index slot in the attached arrays.
    fn constrainIndex(header: IndexHeader, i: usize) usize {
        // This is an optimization for modulo of power of two integers;
        // it requires `indexes_len` to always be a power of two.
        return @as(usize, @intCast(i & header.mask()));
    }

    /// Returns the attached array of indexes.  I must match the type
    /// returned by capacityIndexType.
    fn indexes(header: *IndexHeader, comptime I: type) []Index(I) {
        const start_ptr: [*]Index(I) = @ptrCast(@alignCast(@as([*]u8, @ptrCast(header)) + @sizeOf(IndexHeader)));
        return start_ptr[0..header.length()];
    }

    /// Returns the type used for the index arrays.
    fn capacityIndexType(header: IndexHeader) CapacityIndexType {
        return hash_map.capacityIndexType(header.bit_index);
    }

    fn capacity(self: IndexHeader) u32 {
        return index_capacities[self.bit_index];
    }
    fn length(self: IndexHeader) usize {
        return @as(usize, 1) << @as(math.Log2Int(usize), @intCast(self.bit_index));
    }
    fn mask(self: IndexHeader) u32 {
        return @as(u32, @intCast(self.length() - 1));
    }

    fn findBitIndex(desired_capacity: usize) Allocator.Error!u8 {
        if (desired_capacity > max_capacity) return error.OutOfMemory;
        var new_bit_index: u8 = @intCast(std.math.log2_int_ceil(usize, desired_capacity));
        if (desired_capacity > index_capacities[new_bit_index]) new_bit_index += 1;
        if (new_bit_index < min_bit_index) new_bit_index = min_bit_index;
        assert(desired_capacity <= index_capacities[new_bit_index]);
        return new_bit_index;
    }

    /// Allocates an index header, and fills the entryIndexes array with empty.
    /// The distance array contents are undefined.
    fn alloc(gpa: Allocator, new_bit_index: u8) Allocator.Error!*IndexHeader {
        const len = @as(usize, 1) << @as(math.Log2Int(usize), @intCast(new_bit_index));
        const index_size = hash_map.capacityIndexSize(new_bit_index);
        const nbytes = @sizeOf(IndexHeader) + index_size * len;
        const bytes = try gpa.alignedAlloc(u8, .of(IndexHeader), nbytes);
        @memset(bytes[@sizeOf(IndexHeader)..], 0xff);
        const result: *IndexHeader = @ptrCast(@alignCast(bytes.ptr));
        result.* = .{
            .bit_index = new_bit_index,
        };
        return result;
    }

    /// Releases the memory for a header and its associated arrays.
    fn free(header: *IndexHeader, gpa: Allocator) void {
        const index_size = hash_map.capacityIndexSize(header.bit_index);
        const ptr: [*]align(@alignOf(IndexHeader)) u8 = @ptrCast(header);
        const slice = ptr[0 .. @sizeOf(IndexHeader) + header.length() * index_size];
        gpa.free(slice);
    }

    /// Puts an IndexHeader into the state that it would be in after being freshly allocated.
    fn reset(header: *IndexHeader) void {
        const index_size = hash_map.capacityIndexSize(header.bit_index);
        const ptr: [*]align(@alignOf(IndexHeader)) u8 = @ptrCast(header);
        const nbytes = @sizeOf(IndexHeader) + header.length() * index_size;
        @memset(ptr[@sizeOf(IndexHeader)..nbytes], 0xff);
    }

    // Verify that the header has sufficient alignment to produce aligned arrays.
    comptime {
        if (@alignOf(u32) > @alignOf(IndexHeader))
            @compileError("IndexHeader must have a larger alignment than its indexes!");
    }
};

test "basic hash map usage" {
    const gpa = testing.allocator;

    var map: Auto(i32, i32) = .empty;
    defer map.deinit(gpa);

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

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

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

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

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

    const gop4 = try map.getOrPutValue(gpa, 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.fetchSwapRemove(2);
    try testing.expect(rmv1.?.key == 2);
    try testing.expect(rmv1.?.value == 22);
    try testing.expect(map.fetchSwapRemove(2) == null);
    try testing.expect(map.swapRemove(2) == false);
    try testing.expect(map.getEntry(2) == null);
    try testing.expect(map.get(2) == null);

    // Since we've used `swapRemove` above, the index of this entry should remain unchanged.
    try testing.expect(map.getIndex(100).? == 1);
    const gop5 = try map.getOrPut(gpa, 5);
    try testing.expect(gop5.found_existing == true);
    try testing.expect(gop5.value_ptr.* == 77);
    try testing.expect(gop5.index == 4);

    // Whereas, if we do an `orderedRemove`, it should move the index forward one spot.
    const rmv2 = map.fetchOrderedRemove(100);
    try testing.expect(rmv2.?.key == 100);
    try testing.expect(rmv2.?.value == 41);
    try testing.expect(map.fetchOrderedRemove(100) == null);
    try testing.expect(map.orderedRemove(100) == false);
    try testing.expect(map.getEntry(100) == null);
    try testing.expect(map.get(100) == null);
    const gop6 = try map.getOrPut(gpa, 5);
    try testing.expect(gop6.found_existing == true);
    try testing.expect(gop6.value_ptr.* == 77);
    try testing.expect(gop6.index == 3);

    try testing.expect(map.swapRemove(3));
}

test "iterator hash map" {
    const gpa = testing.allocator;

    var reset_map: Auto(i32, i32) = .empty;
    defer reset_map.deinit(gpa);

    // test ensureTotalCapacity with a 0 parameter
    try reset_map.ensureTotalCapacity(gpa, 0);

    try reset_map.putNoClobber(gpa, 0, 11);
    try reset_map.putNoClobber(gpa, 1, 22);
    try reset_map.putNoClobber(gpa, 2, 33);

    const keys = [_]i32{
        0, 2, 1,
    };

    const values = [_]i32{
        11, 33, 22,
    };

    var buffer = [_]i32{
        0, 0, 0,
    };

    var it = reset_map.iterator();
    const first_entry = it.next().?;
    it.reset();

    var count: usize = 0;
    while (it.next()) |entry| : (count += 1) {
        buffer[@as(usize, @intCast(entry.key_ptr.*))] = entry.value_ptr.*;
    }
    try testing.expect(count == 3);
    try testing.expect(it.next() == null);

    for (buffer, 0..) |_, i| {
        try testing.expect(buffer[@as(usize, @intCast(keys[i]))] == values[i]);
    }

    it.reset();
    count = 0;
    while (it.next()) |entry| {
        buffer[@as(usize, @intCast(entry.key_ptr.*))] = entry.value_ptr.*;
        count += 1;
        if (count >= 2) break;
    }

    for (buffer[0..2], 0..) |_, i| {
        try testing.expect(buffer[@as(usize, @intCast(keys[i]))] == values[i]);
    }

    it.reset();
    const entry = it.next().?;
    try testing.expect(entry.key_ptr.* == first_entry.key_ptr.*);
    try testing.expect(entry.value_ptr.* == first_entry.value_ptr.*);
}

test "ensure capacity" {
    const gpa = testing.allocator;

    var map: Auto(i32, i32) = .empty;
    defer map.deinit(gpa);

    try map.ensureTotalCapacity(gpa, 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 "ensure capacity leak" {
    try testing.checkAllAllocationFailures(std.testing.allocator, struct {
        pub fn f(allocator: Allocator) !void {
            var map: Auto(i32, i32) = .empty;
            defer map.deinit(allocator);

            var i: i32 = 0;
            // put more than `linear_scan_max` in so index_header gets allocated.
            while (i <= 20) : (i += 1) try map.put(allocator, i, i);
        }
    }.f, .{});
}

test "big map" {
    const gpa = testing.allocator;

    var map: Auto(i32, i32) = .empty;
    defer map.deinit(gpa);

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

    i = 0;
    while (i < 8) : (i += 1) {
        try testing.expectEqual(@as(?i32, i + 10), map.get(i));
    }
    while (i < 16) : (i += 1) {
        try testing.expectEqual(@as(?i32, null), map.get(i));
    }

    i = 4;
    while (i < 12) : (i += 1) {
        try map.put(gpa, i, i + 12);
    }

    i = 0;
    while (i < 4) : (i += 1) {
        try testing.expectEqual(@as(?i32, i + 10), map.get(i));
    }
    while (i < 12) : (i += 1) {
        try testing.expectEqual(@as(?i32, i + 12), map.get(i));
    }
    while (i < 16) : (i += 1) {
        try testing.expectEqual(@as(?i32, null), map.get(i));
    }

    i = 0;
    while (i < 4) : (i += 1) {
        try testing.expect(map.orderedRemove(i));
    }
    while (i < 8) : (i += 1) {
        try testing.expect(map.swapRemove(i));
    }

    i = 0;
    while (i < 8) : (i += 1) {
        try testing.expectEqual(@as(?i32, null), map.get(i));
    }
    while (i < 12) : (i += 1) {
        try testing.expectEqual(@as(?i32, i + 12), map.get(i));
    }
    while (i < 16) : (i += 1) {
        try testing.expectEqual(@as(?i32, null), map.get(i));
    }
}

test "clone" {
    const gpa = testing.allocator;

    var original: Auto(i32, i32) = .empty;
    defer original.deinit(gpa);

    // put more than `linear_scan_max` so we can test that the index header is properly cloned
    var i: u8 = 0;
    while (i < 10) : (i += 1) {
        try original.putNoClobber(gpa, i, i * 10);
    }

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

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

    while (i < 20) : (i += 1) {
        try testing.expect(original.get(i) == null);
        try testing.expect(copy.get(i) == null);
    }
}

test "shrink" {
    const gpa = testing.allocator;

    var map: Auto(i32, i32) = .empty;
    defer map.deinit(gpa);

    // This test is more interesting if we insert enough entries to allocate the index header.
    const num_entries = 200;
    var i: i32 = 0;
    while (i < num_entries) : (i += 1)
        try testing.expect((try map.fetchPut(gpa, i, i * 10)) == null);

    try testing.expect(map.index_header != null);
    try testing.expect(map.count() == num_entries);

    // Test `shrinkRetainingCapacity`.
    map.shrinkRetainingCapacity(17);
    try testing.expect(map.count() == 17);
    try testing.expect(map.capacity() >= num_entries);
    i = 0;
    while (i < num_entries) : (i += 1) {
        const gop = try map.getOrPut(gpa, i);
        if (i < 17) {
            try testing.expect(gop.found_existing == true);
            try testing.expect(gop.value_ptr.* == i * 10);
        } else try testing.expect(gop.found_existing == false);
    }

    // Test `shrinkAndFree`.
    map.shrinkAndFree(gpa, 15);
    try testing.expect(map.count() == 15);
    try testing.expect(map.capacity() == 15);
    i = 0;
    while (i < num_entries) : (i += 1) {
        const gop = try map.getOrPut(gpa, i);
        if (i < 15) {
            try testing.expect(gop.found_existing == true);
            try testing.expect(gop.value_ptr.* == i * 10);
        } else try testing.expect(gop.found_existing == false);
    }
}

test "pop()" {
    const gpa = testing.allocator;

    var map: Auto(i32, i32) = .empty;
    defer map.deinit(gpa);

    // Insert just enough entries so that the map expands. Afterwards,
    // pop all entries out of the map.

    var i: i32 = 0;
    while (i < 9) : (i += 1) {
        try testing.expect((try map.fetchPut(gpa, i, i)) == null);
    }

    while (map.pop()) |pop| {
        try testing.expect(pop.key == i - 1 and pop.value == i - 1);
        i -= 1;
    }

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

test "reIndex" {
    const gpa = testing.allocator;

    var map: Custom(i32, i32, AutoContext(i32), true) = .empty;
    defer map.deinit(gpa);

    // Populate via the API.
    const num_indexed_entries = 200;
    var i: i32 = 0;
    while (i < num_indexed_entries) : (i += 1)
        try testing.expect((try map.fetchPut(gpa, i, i * 10)) == null);

    // Make sure we allocated an index header.
    try testing.expect(map.index_header != null);

    // Now write to the arrays directly.
    const num_unindexed_entries = 20;
    try map.entries.resize(std.testing.allocator, num_indexed_entries + num_unindexed_entries);
    for (map.keys()[num_indexed_entries..], map.values()[num_indexed_entries..], num_indexed_entries..) |*key, *value, j| {
        key.* = @intCast(j);
        value.* = @intCast(j * 10);
    }

    // After reindexing, we should see everything.
    try map.reIndex(gpa);
    i = 0;
    while (i < num_indexed_entries + num_unindexed_entries) : (i += 1) {
        const gop = try map.getOrPut(gpa, i);
        try testing.expect(gop.found_existing == true);
        try testing.expect(gop.value_ptr.* == i * 10);
        try testing.expect(gop.index == i);
    }
}

test "auto store_hash" {
    const HasCheapEql = Auto(i32, i32);
    const HasExpensiveEql = Auto([32]i32, i32);
    try testing.expect(@FieldType(HasCheapEql.Data, "hash") == void);
    try testing.expect(@FieldType(HasExpensiveEql.Data, "hash") != void);
}

test "sort" {
    const gpa = testing.allocator;

    var map: Auto(i32, i32) = .empty;
    defer map.deinit(gpa);

    for ([_]i32{ 8, 3, 12, 10, 2, 4, 9, 5, 6, 13, 14, 15, 16, 1, 11, 17, 7 }) |x| {
        try map.put(gpa, x, x * 3);
    }

    const C = struct {
        keys: []i32,

        pub fn lessThan(ctx: @This(), a_index: usize, b_index: usize) bool {
            return ctx.keys[a_index] < ctx.keys[b_index];
        }
    };

    map.sort(C{ .keys = map.keys() });

    var x: i32 = 1;
    for (map.keys(), 0..) |key, i| {
        try testing.expect(key == x);
        try testing.expect(map.values()[i] == x * 3);
        x += 1;
    }
}

test "0 sized key" {
    const gpa = testing.allocator;

    var map: Auto(u0, i32) = .empty;
    defer map.deinit(gpa);

    try testing.expectEqual(map.get(0), null);

    try map.put(gpa, 0, 5);
    try testing.expectEqual(map.get(0), 5);

    try map.put(gpa, 0, 10);
    try testing.expectEqual(map.get(0), 10);

    try testing.expectEqual(map.swapRemove(0), true);
    try testing.expectEqual(map.get(0), null);
}

test "0 sized key and 0 sized value" {
    const gpa = testing.allocator;

    var map: Auto(u0, u0) = .empty;
    defer map.deinit(gpa);

    try testing.expectEqual(map.get(0), null);

    try map.put(gpa, 0, 0);
    try testing.expectEqual(map.get(0), 0);

    try testing.expectEqual(map.swapRemove(0), true);
    try testing.expectEqual(map.get(0), null);
}

test "setKey storehash true" {
    const gpa = std.testing.allocator;

    var map: Custom(i32, i32, AutoContext(i32), true) = .empty;
    defer map.deinit(gpa);

    try map.put(gpa, 12, 34);
    try map.put(gpa, 56, 78);

    map.setKey(0, 42);
    try testing.expectEqual(2, map.count());
    try testing.expectEqual(false, map.contains(12));
    try testing.expectEqual(34, map.get(42));
    try testing.expectEqual(78, map.get(56));
}

test "setKey storehash false" {
    const gpa = std.testing.allocator;

    var map: Custom(i32, i32, AutoContext(i32), false) = .empty;
    defer map.deinit(gpa);

    try map.put(gpa, 12, 34);
    try map.put(gpa, 56, 78);

    map.setKey(0, 42);
    try testing.expectEqual(2, map.count());
    try testing.expectEqual(false, map.contains(12));
    try testing.expectEqual(34, map.get(42));
    try testing.expectEqual(78, map.get(56));
}

test "setKey storehash false with index" {
    const gpa = std.testing.allocator;

    const T = Custom(usize, usize, AutoContext(usize), false);

    var map: T = .empty;
    defer map.deinit(gpa);

    for (0..T.linear_scan_max + 1) |i| try map.put(gpa, i, i);

    map.setKey(0, 42);
    try testing.expectEqual(T.linear_scan_max + 1, map.count());
    try testing.expectEqual(false, map.contains(0));
    try testing.expectEqual(0, map.get(42));

    for (1..T.linear_scan_max + 1) |i| try testing.expectEqual(i, map.get(i));
}

test "setKey storehash true with index" {
    const gpa = std.testing.allocator;

    const T = Custom(usize, usize, AutoContext(usize), false);

    var map: Custom(usize, usize, AutoContext(usize), true) = .empty;
    defer map.deinit(gpa);

    for (0..T.linear_scan_max + 1) |i| try map.put(gpa, i, i);

    map.setKey(0, 42);
    try testing.expectEqual(T.linear_scan_max + 1, map.count());
    try testing.expectEqual(false, map.contains(0));
    try testing.expectEqual(0, map.get(42));

    for (1..T.linear_scan_max + 1) |i| try testing.expectEqual(i, map.get(i));
}

pub fn getHashPtrAddrFn(comptime K: type, comptime Context: type) (fn (Context, K) u32) {
    return struct {
        fn hash(ctx: Context, key: K) u32 {
            _ = ctx;
            return getAutoHashFn(usize, void)({}, @intFromPtr(key));
        }
    }.hash;
}

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

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

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

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

pub fn autoEqlIsCheap(comptime K: type) bool {
    return switch (@typeInfo(K)) {
        .bool,
        .int,
        .float,
        .pointer,
        .comptime_float,
        .comptime_int,
        .@"enum",
        .@"fn",
        .error_set,
        .@"anyframe",
        .enum_literal,
        => true,
        else => false,
    };
}

pub fn getAutoHashStratFn(comptime K: type, comptime Context: type, comptime strategy: std.hash.Strategy) (fn (Context, K) u32) {
    return struct {
        fn hash(ctx: Context, key: K) u32 {
            _ = ctx;
            var hasher = Wyhash.init(0);
            std.hash.autoHashStrat(&hasher, key, strategy);
            return @as(u32, @truncate(hasher.final()));
        }
    }.hash;
}

test "orderedRemoveAtMany" {
    const gpa = testing.allocator;

    var map: Auto(usize, void) = .empty;
    defer map.deinit(gpa);

    for (0..10) |n| {
        try map.put(gpa, n, {});
    }

    try map.orderedRemoveAtMany(gpa, &.{ 1, 5, 5, 7, 9 });
    try testing.expectEqualSlices(usize, &.{ 0, 2, 3, 4, 6, 8 }, map.keys());

    try map.orderedRemoveAtMany(gpa, &.{0});
    try testing.expectEqualSlices(usize, &.{ 2, 3, 4, 6, 8 }, map.keys());

    try map.orderedRemoveAtMany(gpa, &.{});
    try testing.expectEqualSlices(usize, &.{ 2, 3, 4, 6, 8 }, map.keys());

    try map.orderedRemoveAtMany(gpa, &.{ 1, 2, 3, 4 });
    try testing.expectEqualSlices(usize, &.{2}, map.keys());

    try map.orderedRemoveAtMany(gpa, &.{0});
    try testing.expectEqualSlices(usize, &.{}, map.keys());
}