Type Function ArrayHashMapWithAllocator [src]
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.
See ArrayHashMapUnmanaged for a variant of this data structure that accepts an
Allocator as a parameter when needed rather than storing it.
Prototype
pub fn ArrayHashMapWithAllocator( comptime K: type, comptime V: type, comptime Context: type, comptime store_hash: bool, ) type Parameters
K: typeV: typeContext: typeA 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: boolWhen 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).
Source
pub fn ArrayHashMapWithAllocator(
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 {
unmanaged: Unmanaged,
allocator: Allocator,
ctx: Context,
/// The ArrayHashMapUnmanaged type using the same settings as this managed map.
pub const Unmanaged = ArrayHashMapUnmanaged(K, V, Context, store_hash);
/// Pointers to a key and value in the backing store of this map.
/// 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 = Unmanaged.Entry;
/// A KV pair which has been copied out of the backing store
pub const KV = Unmanaged.KV;
/// The Data type used for the MultiArrayList backing this map
pub const Data = Unmanaged.Data;
/// The MultiArrayList type backing this map
pub const DataList = Unmanaged.DataList;
/// The stored hash type, either u32 or void.
pub const Hash = Unmanaged.Hash;
/// 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 = Unmanaged.GetOrPutResult;
/// An Iterator over Entry pointers.
pub const Iterator = Unmanaged.Iterator;
const Self = @This();
/// Create an ArrayHashMap instance which will use a specified allocator.
pub fn init(allocator: Allocator) Self {
if (@sizeOf(Context) != 0)
@compileError("Cannot infer context " ++ @typeName(Context) ++ ", call initContext instead.");
return initContext(allocator, undefined);
}
pub fn initContext(allocator: Allocator, ctx: Context) Self {
return .{
.unmanaged = .empty,
.allocator = allocator,
.ctx = ctx,
};
}
/// 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) void {
self.unmanaged.deinit(self.allocator);
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.
///
/// An additional call to `lockPointers` in such state also triggers an
/// assertion.
///
/// `unlockPointers` returns the hash map to the previous state.
pub fn lockPointers(self: *Self) void {
self.unmanaged.lockPointers();
}
/// Undoes a call to `lockPointers`.
pub fn unlockPointers(self: *Self) void {
self.unmanaged.unlockPointers();
}
/// Clears the map but retains the backing allocation for future use.
pub fn clearRetainingCapacity(self: *Self) void {
return self.unmanaged.clearRetainingCapacity();
}
/// Clears the map and releases the backing allocation
pub fn clearAndFree(self: *Self) void {
return self.unmanaged.clearAndFree(self.allocator);
}
/// Returns the number of KV pairs stored in this map.
pub fn count(self: Self) usize {
return self.unmanaged.count();
}
/// 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.unmanaged.keys();
}
/// 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.unmanaged.values();
}
/// Returns an iterator over the pairs in this map.
/// Modifying the map may invalidate this iterator.
pub fn iterator(self: *const Self) Iterator {
return self.unmanaged.iterator();
}
/// 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, key: K) !GetOrPutResult {
return self.unmanaged.getOrPutContext(self.allocator, key, self.ctx);
}
pub fn getOrPutAdapted(self: *Self, key: anytype, ctx: anytype) !GetOrPutResult {
return self.unmanaged.getOrPutContextAdapted(self.allocator, key, ctx, self.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 {
return self.unmanaged.getOrPutAssumeCapacityContext(key, self.ctx);
}
pub fn getOrPutAssumeCapacityAdapted(self: *Self, key: anytype, ctx: anytype) GetOrPutResult {
return self.unmanaged.getOrPutAssumeCapacityAdapted(key, ctx);
}
pub fn getOrPutValue(self: *Self, key: K, value: V) !GetOrPutResult {
return self.unmanaged.getOrPutValueContext(self.allocator, key, value, self.ctx);
}
/// Increases capacity, guaranteeing that insertions up until the
/// `expected_count` will not cause an allocation, and therefore cannot fail.
pub fn ensureTotalCapacity(self: *Self, new_capacity: usize) !void {
return self.unmanaged.ensureTotalCapacityContext(self.allocator, new_capacity, self.ctx);
}
/// Increases capacity, guaranteeing that insertions up until
/// `additional_count` **more** items will not cause an allocation, and
/// therefore cannot fail.
pub fn ensureUnusedCapacity(self: *Self, additional_count: usize) !void {
return self.unmanaged.ensureUnusedCapacityContext(self.allocator, additional_count, self.ctx);
}
/// Returns the number of total elements which may be present before it is
/// no longer guaranteed that no allocations will be performed.
pub fn capacity(self: Self) usize {
return self.unmanaged.capacity();
}
/// Clobbers any existing data. To detect if a put would clobber
/// existing data, see `getOrPut`.
pub fn put(self: *Self, key: K, value: V) !void {
return self.unmanaged.putContext(self.allocator, key, value, self.ctx);
}
/// Inserts a key-value pair into the hash map, asserting that no previous
/// entry with the same key is already present
pub fn putNoClobber(self: *Self, key: K, value: V) !void {
return self.unmanaged.putNoClobberContext(self.allocator, key, value, self.ctx);
}
/// Asserts there is enough capacity to store the new key-value pair.
/// Clobbers any existing data. To detect if a put would clobber
/// existing data, see `getOrPutAssumeCapacity`.
pub fn putAssumeCapacity(self: *Self, key: K, value: V) void {
return self.unmanaged.putAssumeCapacityContext(key, value, self.ctx);
}
/// Asserts there is enough capacity to store the new key-value pair.
/// Asserts that it does not clobber any existing data.
/// To detect if a put would clobber existing data, see `getOrPutAssumeCapacity`.
pub fn putAssumeCapacityNoClobber(self: *Self, key: K, value: V) void {
return self.unmanaged.putAssumeCapacityNoClobberContext(key, value, self.ctx);
}
/// Inserts a new `Entry` into the hash map, returning the previous one, if any.
pub fn fetchPut(self: *Self, key: K, value: V) !?KV {
return self.unmanaged.fetchPutContext(self.allocator, key, value, self.ctx);
}
/// Inserts a new `Entry` into the hash map, returning the previous one, if any.
/// If insertion happuns, asserts there is enough capacity without allocating.
pub fn fetchPutAssumeCapacity(self: *Self, key: K, value: V) ?KV {
return self.unmanaged.fetchPutAssumeCapacityContext(key, value, self.ctx);
}
/// Finds pointers to the key and value storage associated with a key.
pub fn getEntry(self: Self, key: K) ?Entry {
return self.unmanaged.getEntryContext(key, self.ctx);
}
pub fn getEntryAdapted(self: Self, key: anytype, ctx: anytype) ?Entry {
return self.unmanaged.getEntryAdapted(key, ctx);
}
/// Finds the index in the `entries` array where a key is stored
pub fn getIndex(self: Self, key: K) ?usize {
return self.unmanaged.getIndexContext(key, self.ctx);
}
pub fn getIndexAdapted(self: Self, key: anytype, ctx: anytype) ?usize {
return self.unmanaged.getIndexAdapted(key, ctx);
}
/// Find the value associated with a key
pub fn get(self: Self, key: K) ?V {
return self.unmanaged.getContext(key, self.ctx);
}
pub fn getAdapted(self: Self, key: anytype, ctx: anytype) ?V {
return self.unmanaged.getAdapted(key, ctx);
}
/// Find a pointer to the value associated with a key
pub fn getPtr(self: Self, key: K) ?*V {
return self.unmanaged.getPtrContext(key, self.ctx);
}
pub fn getPtrAdapted(self: Self, key: anytype, ctx: anytype) ?*V {
return self.unmanaged.getPtrAdapted(key, ctx);
}
/// Find the actual key associated with an adapted key
pub fn getKey(self: Self, key: K) ?K {
return self.unmanaged.getKeyContext(key, self.ctx);
}
pub fn getKeyAdapted(self: Self, key: anytype, ctx: anytype) ?K {
return self.unmanaged.getKeyAdapted(key, ctx);
}
/// Find a pointer to the actual key associated with an adapted key
pub fn getKeyPtr(self: Self, key: K) ?*K {
return self.unmanaged.getKeyPtrContext(key, self.ctx);
}
pub fn getKeyPtrAdapted(self: Self, key: anytype, ctx: anytype) ?*K {
return self.unmanaged.getKeyPtrAdapted(key, ctx);
}
/// Check whether a key is stored in the map
pub fn contains(self: Self, key: K) bool {
return self.unmanaged.containsContext(key, self.ctx);
}
pub fn containsAdapted(self: Self, key: anytype, ctx: anytype) bool {
return self.unmanaged.containsAdapted(key, ctx);
}
/// If there is an `Entry` with a matching key, it is deleted from
/// the hash map, and 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 {
return self.unmanaged.fetchSwapRemoveContext(key, self.ctx);
}
pub fn fetchSwapRemoveAdapted(self: *Self, key: anytype, ctx: anytype) ?KV {
return self.unmanaged.fetchSwapRemoveContextAdapted(key, ctx, self.ctx);
}
/// 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 {
return self.unmanaged.fetchOrderedRemoveContext(key, self.ctx);
}
pub fn fetchOrderedRemoveAdapted(self: *Self, key: anytype, ctx: anytype) ?KV {
return self.unmanaged.fetchOrderedRemoveContextAdapted(key, ctx, self.ctx);
}
/// 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 {
return self.unmanaged.swapRemoveContext(key, self.ctx);
}
pub fn swapRemoveAdapted(self: *Self, key: anytype, ctx: anytype) bool {
return self.unmanaged.swapRemoveContextAdapted(key, ctx, self.ctx);
}
/// 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 {
return self.unmanaged.orderedRemoveContext(key, self.ctx);
}
pub fn orderedRemoveAdapted(self: *Self, key: anytype, ctx: anytype) bool {
return self.unmanaged.orderedRemoveContextAdapted(key, ctx, self.ctx);
}
/// 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 {
self.unmanaged.swapRemoveAtContext(index, self.ctx);
}
/// 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 {
self.unmanaged.orderedRemoveAtContext(index, self.ctx);
}
/// Create a copy of the hash map which can be modified separately.
/// The copy uses the same context and allocator as this instance.
pub fn clone(self: Self) !Self {
var other = try self.unmanaged.cloneContext(self.allocator, self.ctx);
return other.promoteContext(self.allocator, self.ctx);
}
/// Create a copy of the hash map which can be modified separately.
/// The copy uses the same context as this instance, but the specified
/// allocator.
pub fn cloneWithAllocator(self: Self, allocator: Allocator) !Self {
var other = try self.unmanaged.cloneContext(allocator, self.ctx);
return other.promoteContext(allocator, self.ctx);
}
/// Create a copy of the hash map which can be modified separately.
/// The copy uses the same allocator as this instance, but the
/// specified context.
pub fn cloneWithContext(self: Self, ctx: anytype) !ArrayHashMap(K, V, @TypeOf(ctx), store_hash) {
var other = try self.unmanaged.cloneContext(self.allocator, ctx);
return other.promoteContext(self.allocator, ctx);
}
/// Create a copy of the hash map which can be modified separately.
/// The copy uses the specified allocator and context.
pub fn cloneWithAllocatorAndContext(self: Self, allocator: Allocator, ctx: anytype) !ArrayHashMap(K, V, @TypeOf(ctx), store_hash) {
var other = try self.unmanaged.cloneContext(allocator, ctx);
return other.promoteContext(allocator, ctx);
}
/// Set the map to an empty state, making deinitialization a no-op, and
/// returning a copy of the original.
pub fn move(self: *Self) Self {
self.unmanaged.pointer_stability.assertUnlocked();
const result = self.*;
self.unmanaged = .empty;
return result;
}
/// 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) !void {
return self.unmanaged.reIndexContext(self.allocator, self.ctx);
}
/// Sorts the entries and then rebuilds the index.
/// `sort_ctx` must have this method:
/// `fn lessThan(ctx: @TypeOf(ctx), a_index: usize, b_index: usize) bool`
pub fn sort(self: *Self, sort_ctx: anytype) void {
return self.unmanaged.sortContext(sort_ctx, self.ctx);
}
/// 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 {
return self.unmanaged.shrinkRetainingCapacityContext(new_len, self.ctx);
}
/// 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, new_len: usize) void {
return self.unmanaged.shrinkAndFreeContext(self.allocator, new_len, self.ctx);
}
/// Removes the last inserted `Entry` in the hash map and returns it if count is nonzero.
/// Otherwise returns null.
pub fn pop(self: *Self) ?KV {
return self.unmanaged.popContext(self.ctx);
}
};
}