aboutsummaryrefslogtreecommitdiff
path: root/lib/std/hash_map.zig
diff options
context:
space:
mode:
Diffstat (limited to 'lib/std/hash_map.zig')
-rw-r--r--lib/std/hash_map.zig1097
1 files changed, 872 insertions, 225 deletions
diff --git a/lib/std/hash_map.zig b/lib/std/hash_map.zig
index 62f577de1a..3a3c30bdf8 100644
--- a/lib/std/hash_map.zig
+++ b/lib/std/hash_map.zig
@@ -15,7 +15,7 @@ const trait = meta.trait;
const Allocator = mem.Allocator;
const Wyhash = std.hash.Wyhash;
-pub fn getAutoHashFn(comptime K: type) (fn (K) u64) {
+pub fn getAutoHashFn(comptime K: type, comptime Context: type) (fn (Context, K) u64) {
comptime {
assert(@hasDecl(std, "StringHashMap")); // detect when the following message needs updated
if (K == []const u8) {
@@ -28,7 +28,7 @@ pub fn getAutoHashFn(comptime K: type) (fn (K) u64) {
}
return struct {
- fn hash(key: K) u64 {
+ fn hash(ctx: Context, key: K) u64 {
if (comptime trait.hasUniqueRepresentation(K)) {
return Wyhash.hash(0, std.mem.asBytes(&key));
} else {
@@ -40,31 +40,51 @@ pub fn getAutoHashFn(comptime K: type) (fn (K) u64) {
}.hash;
}
-pub fn getAutoEqlFn(comptime K: type) (fn (K, K) bool) {
+pub fn getAutoEqlFn(comptime K: type, comptime Context: type) (fn (Context, K, K) bool) {
return struct {
- fn eql(a: K, b: K) bool {
+ fn eql(ctx: Context, a: K, b: K) bool {
return meta.eql(a, b);
}
}.eql;
}
pub fn AutoHashMap(comptime K: type, comptime V: type) type {
- return HashMap(K, V, getAutoHashFn(K), getAutoEqlFn(K), default_max_load_percentage);
+ return HashMap(K, V, AutoContext(K), default_max_load_percentage);
}
pub fn AutoHashMapUnmanaged(comptime K: type, comptime V: type) type {
- return HashMapUnmanaged(K, V, getAutoHashFn(K), getAutoEqlFn(K), default_max_load_percentage);
+ return HashMapUnmanaged(K, V, AutoContext(K), default_max_load_percentage);
+}
+
+pub fn AutoContext(comptime K: type) type {
+ return struct {
+ pub const hash = getAutoHashFn(K, @This());
+ pub const eql = getAutoEqlFn(K, @This());
+ };
}
/// Builtin hashmap for strings as keys.
+/// Key memory is managed by the caller. Keys and values
+/// will not automatically be freed.
pub fn StringHashMap(comptime V: type) type {
- return HashMap([]const u8, V, hashString, eqlString, default_max_load_percentage);
+ return HashMap([]const u8, V, StringContext, default_max_load_percentage);
}
+/// Key memory is managed by the caller. Keys and values
+/// will not automatically be freed.
pub fn StringHashMapUnmanaged(comptime V: type) type {
- return HashMapUnmanaged([]const u8, V, hashString, eqlString, default_max_load_percentage);
+ return HashMapUnmanaged([]const u8, V, StringContext, default_max_load_percentage);
}
+pub const StringContext = struct {
+ pub fn hash(self: @This(), s: []const u8) u64 {
+ return hashString(s);
+ }
+ pub fn eql(self: @This(), a: []const u8, b: []const u8) bool {
+ return eqlString(a, b);
+ }
+};
+
pub fn eqlString(a: []const u8, b: []const u8) bool {
return mem.eql(u8, a, b);
}
@@ -78,6 +98,222 @@ pub const DefaultMaxLoadPercentage = default_max_load_percentage;
pub const default_max_load_percentage = 80;
+/// This function issues a compile error with a helpful message if there
+/// is a problem with the provided context type. A context must have the following
+/// member functions:
+/// - hash(self, PseudoKey) Hash
+/// - eql(self, PseudoKey, Key) bool
+/// If you are passing a context to a *Adapted function, PseudoKey is the type
+/// of the key parameter. Otherwise, when creating a HashMap or HashMapUnmanaged
+/// type, PseudoKey = Key = K.
+pub fn verifyContext(comptime RawContext: type, comptime PseudoKey: type, comptime Key: type, comptime Hash: type) void {
+ comptime {
+ var allow_const_ptr = false;
+ var allow_mutable_ptr = false;
+ // Context is the actual namespace type. RawContext may be a pointer to Context.
+ var Context = RawContext;
+ // Make sure the context is a namespace type which may have member functions
+ switch (@typeInfo(Context)) {
+ .Struct, .Union, .Enum => {},
+ // Special-case .Opaque for a better error message
+ .Opaque => @compileError("Hash context must be a type with hash and eql member functions. Cannot use "++@typeName(Context)++" because it is opaque. Use a pointer instead."),
+ .Pointer => |ptr| {
+ if (ptr.size != .One) {
+ @compileError("Hash context must be a type with hash and eql member functions. Cannot use "++@typeName(Context)++" because it is not a single pointer.");
+ }
+ Context = ptr.child;
+ allow_const_ptr = true;
+ allow_mutable_ptr = !ptr.is_const;
+ switch (@typeInfo(Context)) {
+ .Struct, .Union, .Enum, .Opaque => {},
+ else => @compileError("Hash context must be a type with hash and eql member functions. Cannot use "++@typeName(Context)),
+ }
+ },
+ else => @compileError("Hash context must be a type with hash and eql member functions. Cannot use "++@typeName(Context)),
+ }
+
+ // Keep track of multiple errors so we can report them all.
+ var errors: []const u8 = "";
+
+ // Put common errors here, they will only be evaluated
+ // if the error is actually triggered.
+ const lazy = struct {
+ const prefix = "\n ";
+ const deep_prefix = prefix ++ " ";
+ const hash_signature = "fn (self, "++@typeName(PseudoKey)++") "++@typeName(Hash);
+ const eql_signature = "fn (self, "++@typeName(PseudoKey)++", "++@typeName(Key)++") bool";
+ const err_invalid_hash_signature = prefix ++ @typeName(Context) ++ ".hash must be " ++ hash_signature ++
+ deep_prefix ++ "but is actually " ++ @typeName(@TypeOf(Context.hash));
+ const err_invalid_eql_signature = prefix ++ @typeName(Context) ++ ".eql must be " ++ eql_signature ++
+ deep_prefix ++ "but is actually " ++ @typeName(@TypeOf(Context.eql));
+ };
+
+ // Verify Context.hash(self, PseudoKey) => Hash
+ if (@hasDecl(Context, "hash")) {
+ const hash = Context.hash;
+ const info = @typeInfo(@TypeOf(hash));
+ if (info == .Fn) {
+ const func = info.Fn;
+ if (func.args.len != 2) {
+ errors = errors ++ lazy.err_invalid_hash_signature;
+ } else {
+ var emitted_signature = false;
+ if (func.args[0].arg_type) |Self| {
+ if (Self == Context) {
+ // pass, this is always fine.
+ } else if (Self == *const Context) {
+ if (!allow_const_ptr) {
+ if (!emitted_signature) {
+ errors = errors ++ lazy.err_invalid_hash_signature;
+ emitted_signature = true;
+ }
+ errors = errors ++ lazy.deep_prefix ++ "First parameter must be "++@typeName(Context)++", but is "++@typeName(Self);
+ errors = errors ++ lazy.deep_prefix ++ "Note: Cannot be a pointer because it is passed by value.";
+ }
+ } else if (Self == *Context) {
+ if (!allow_mutable_ptr) {
+ if (!emitted_signature) {
+ errors = errors ++ lazy.err_invalid_hash_signature;
+ emitted_signature = true;
+ }
+ if (!allow_const_ptr) {
+ errors = errors ++ lazy.deep_prefix ++ "First parameter must be "++@typeName(Context)++", but is "++@typeName(Self);
+ errors = errors ++ lazy.deep_prefix ++ "Note: Cannot be a pointer because it is passed by value.";
+ } else {
+ errors = errors ++ lazy.deep_prefix ++ "First parameter must be "++@typeName(Context)++" or "++@typeName(*const Context)++", but is "++@typeName(Self);
+ errors = errors ++ lazy.deep_prefix ++ "Note: Cannot be non-const because it is passed by const pointer.";
+ }
+ }
+ } else {
+ if (!emitted_signature) {
+ errors = errors ++ lazy.err_invalid_hash_signature;
+ emitted_signature = true;
+ }
+ errors = errors ++ lazy.deep_prefix ++ "First parameter must be "++@typeName(Context);
+ if (allow_const_ptr) {
+ errors = errors++" or "++@typeName(*const Context);
+ if (allow_mutable_ptr) {
+ errors = errors++" or "++@typeName(*Context);
+ }
+ }
+ errors = errors++", but is "++@typeName(Self);
+ }
+ }
+ if (func.args[1].arg_type != null and func.args[1].arg_type.? != PseudoKey) {
+ if (!emitted_signature) {
+ errors = errors ++ lazy.err_invalid_hash_signature;
+ emitted_signature = true;
+ }
+ errors = errors ++ lazy.deep_prefix ++ "Second parameter must be "++@typeName(PseudoKey)++", but is "++@typeName(func.args[1].arg_type.?);
+ }
+ if (func.return_type != null and func.return_type.? != Hash) {
+ if (!emitted_signature) {
+ errors = errors ++ lazy.err_invalid_hash_signature;
+ emitted_signature = true;
+ }
+ errors = errors ++ lazy.deep_prefix ++ "Return type must be "++@typeName(Hash)++", but was "++@typeName(func.return_type.?);
+ }
+ // If any of these are generic (null), we cannot verify them.
+ // The call sites check the return type, but cannot check the
+ // parameters. This may cause compile errors with generic hash/eql functions.
+ }
+ } else {
+ errors = errors ++ lazy.err_invalid_hash_signature;
+ }
+ } else {
+ errors = errors ++ lazy.prefix ++ @typeName(Context) ++ " must declare a hash function with signature " ++ lazy.hash_signature;
+ }
+
+ // Verify Context.eql(self, PseudoKey, Key) => bool
+ if (@hasDecl(Context, "eql")) {
+ const eql = Context.eql;
+ const info = @typeInfo(@TypeOf(eql));
+ if (info == .Fn) {
+ const func = info.Fn;
+ if (func.args.len != 3) {
+ errors = errors ++ lazy.err_invalid_eql_signature;
+ } else {
+ var emitted_signature = false;
+ if (func.args[0].arg_type) |Self| {
+ if (Self == Context) {
+ // pass, this is always fine.
+ } else if (Self == *const Context) {
+ if (!allow_const_ptr) {
+ if (!emitted_signature) {
+ errors = errors ++ lazy.err_invalid_eql_signature;
+ emitted_signature = true;
+ }
+ errors = errors ++ lazy.deep_prefix ++ "First parameter must be "++@typeName(Context)++", but is "++@typeName(Self);
+ errors = errors ++ lazy.deep_prefix ++ "Note: Cannot be a pointer because it is passed by value.";
+ }
+ } else if (Self == *Context) {
+ if (!allow_mutable_ptr) {
+ if (!emitted_signature) {
+ errors = errors ++ lazy.err_invalid_eql_signature;
+ emitted_signature = true;
+ }
+ if (!allow_const_ptr) {
+ errors = errors ++ lazy.deep_prefix ++ "First parameter must be "++@typeName(Context)++", but is "++@typeName(Self);
+ errors = errors ++ lazy.deep_prefix ++ "Note: Cannot be a pointer because it is passed by value.";
+ } else {
+ errors = errors ++ lazy.deep_prefix ++ "First parameter must be "++@typeName(Context)++" or "++@typeName(*const Context)++", but is "++@typeName(Self);
+ errors = errors ++ lazy.deep_prefix ++ "Note: Cannot be non-const because it is passed by const pointer.";
+ }
+ }
+ } else {
+ if (!emitted_signature) {
+ errors = errors ++ lazy.err_invalid_eql_signature;
+ emitted_signature = true;
+ }
+ errors = errors ++ lazy.deep_prefix ++ "First parameter must be "++@typeName(Context);
+ if (allow_const_ptr) {
+ errors = errors++" or "++@typeName(*const Context);
+ if (allow_mutable_ptr) {
+ errors = errors++" or "++@typeName(*Context);
+ }
+ }
+ errors = errors++", but is "++@typeName(Self);
+ }
+ }
+ if (func.args[1].arg_type.? != PseudoKey) {
+ if (!emitted_signature) {
+ errors = errors ++ lazy.err_invalid_eql_signature;
+ emitted_signature = true;
+ }
+ errors = errors ++ lazy.deep_prefix ++ "Second parameter must be "++@typeName(PseudoKey)++", but is "++@typeName(func.args[1].arg_type.?);
+ }
+ if (func.args[2].arg_type.? != Key) {
+ if (!emitted_signature) {
+ errors = errors ++ lazy.err_invalid_eql_signature;
+ emitted_signature = true;
+ }
+ errors = errors ++ lazy.deep_prefix ++ "Third parameter must be "++@typeName(Key)++", but is "++@typeName(func.args[2].arg_type.?);
+ }
+ if (func.return_type.? != bool) {
+ if (!emitted_signature) {
+ errors = errors ++ lazy.err_invalid_eql_signature;
+ emitted_signature = true;
+ }
+ errors = errors ++ lazy.deep_prefix ++ "Return type must be bool, but was "++@typeName(func.return_type.?);
+ }
+ // If any of these are generic (null), we cannot verify them.
+ // The call sites check the return type, but cannot check the
+ // parameters. This may cause compile errors with generic hash/eql functions.
+ }
+ } else {
+ errors = errors ++ lazy.err_invalid_eql_signature;
+ }
+ } else {
+ errors = errors ++ lazy.prefix ++ @typeName(Context) ++ " must declare a eql function with signature " ++ lazy.eql_signature;
+ }
+
+ if (errors.len != 0) {
+ // errors begins with a newline (from lazy.prefix)
+ @compileError("Problems found with hash context type "++@typeName(Context)++":"++errors);
+ }
+ }
+}
+
/// General purpose hash table.
/// No order is guaranteed and any modification invalidates live iterators.
/// It provides fast operations (lookup, insertion, deletion) with quite high
@@ -86,83 +322,167 @@ pub const default_max_load_percentage = 80;
/// field, see `HashMapUnmanaged`.
/// If iterating over the table entries is a strong usecase and needs to be fast,
/// prefer the alternative `std.ArrayHashMap`.
+/// Context must be a struct type with two member functions:
+/// hash(self, K) u64
+/// eql(self, K, K) bool
+/// Adapted variants of many functions are provided. These variants
+/// take a pseudo key instead of a key. Their context must have the functions:
+/// hash(self, PseudoKey) u64
+/// eql(self, PseudoKey, K) bool
pub fn HashMap(
comptime K: type,
comptime V: type,
- comptime hashFn: fn (key: K) u64,
- comptime eqlFn: fn (a: K, b: K) bool,
+ comptime Context: type,
comptime max_load_percentage: u64,
) type {
+ comptime verifyContext(Context, K, K, u64);
return struct {
unmanaged: Unmanaged,
allocator: *Allocator,
+ ctx: Context,
- pub const Unmanaged = HashMapUnmanaged(K, V, hashFn, eqlFn, max_load_percentage);
+ /// The type of the unmanaged hash map underlying this wrapper
+ pub const Unmanaged = HashMapUnmanaged(K, V, Context, max_load_percentage);
+ /// An entry, containing pointers to a key and value stored in the map
pub const Entry = Unmanaged.Entry;
+ /// A copy of a key and value which are no longer in the map
+ pub const KV = Unmanaged.KV;
+ /// The integer type that is the result of hashing
pub const Hash = Unmanaged.Hash;
+ /// The iterator type returned by iterator()
pub const Iterator = Unmanaged.Iterator;
+
+ pub const KeyIterator = Unmanaged.KeyIterator;
+ pub const ValueIterator = Unmanaged.ValueIterator;
+
+ /// The integer type used to store the size of the map
pub const Size = Unmanaged.Size;
+ /// The type returned from getOrPut and variants
pub const GetOrPutResult = Unmanaged.GetOrPutResult;
const Self = @This();
+ /// Create a managed hash map with an empty context.
+ /// If the context is not zero-sized, you must use
+ /// initContext(allocator, ctx) instead.
pub fn init(allocator: *Allocator) Self {
+ if (@sizeOf(Context) != 0) {
+ @compileError("Context must be specified! Call initContext(allocator, ctx) instead.");
+ }
+ return .{
+ .unmanaged = .{},
+ .allocator = allocator,
+ .ctx = undefined, // ctx is zero-sized so this is safe.
+ };
+ }
+
+ /// Create a managed hash map with a context
+ pub fn initContext(allocator: *Allocator, ctx: Context) Self {
return .{
.unmanaged = .{},
.allocator = allocator,
+ .ctx = ctx,
};
}
+ /// Release the backing array and invalidate this map.
+ /// This does *not* deinit keys, values, or the context!
+ /// If your keys or values need to be released, ensure
+ /// that that is done before calling this function.
pub fn deinit(self: *Self) void {
self.unmanaged.deinit(self.allocator);
self.* = undefined;
}
+ /// Empty the map, but keep the backing allocation for future use.
+ /// This does *not* free keys or values! Be sure to
+ /// release them if they need deinitialization before
+ /// calling this function.
pub fn clearRetainingCapacity(self: *Self) void {
return self.unmanaged.clearRetainingCapacity();
}
+ /// Empty the map and release the backing allocation.
+ /// This does *not* free keys or values! Be sure to
+ /// release them if they need deinitialization before
+ /// calling this function.
pub fn clearAndFree(self: *Self) void {
return self.unmanaged.clearAndFree(self.allocator);
}
+ /// Return the number of items in the map.
pub fn count(self: Self) Size {
return self.unmanaged.count();
}
+ /// Create an iterator over the entries in the map.
+ /// The iterator is invalidated if the map is modified.
pub fn iterator(self: *const Self) Iterator {
return self.unmanaged.iterator();
}
+ /// Create an iterator over the keys in the map.
+ /// The iterator is invalidated if the map is modified.
+ pub fn keyIterator(self: *const Self) KeyIterator {
+ return self.unmanaged.keyIterator();
+ }
+
+ /// Create an iterator over the values in the map.
+ /// The iterator is invalidated if the map is modified.
+ pub fn valueIterator(self: *const Self) ValueIterator {
+ return self.unmanaged.valueIterator();
+ }
+
/// 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.
+ /// `Entry` pointers point 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 `Entry` pointers point to it. Caller should then initialize
/// the value (but not the key).
pub fn getOrPut(self: *Self, key: K) !GetOrPutResult {
- return self.unmanaged.getOrPut(self.allocator, key);
+ return self.unmanaged.getOrPutContext(self.allocator, key, self.ctx);
+ }
+
+ /// If key exists this function cannot fail.
+ /// If there is an existing item with `key`, then the result
+ /// `Entry` pointers point to it, and found_existing is true.
+ /// Otherwise, puts a new item with undefined key and value, and
+ /// the `Entry` pointers point to it. Caller must then initialize
+ /// the key and value.
+ pub fn getOrPutAdapted(self: *Self, key: anytype, ctx: anytype) !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.
+ /// `Entry` pointers point 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 `Entry` pointers point to it. Caller should then initialize
/// the value (but not the key).
/// If a new entry needs to be stored, this function asserts there
/// is enough capacity to store it.
pub fn getOrPutAssumeCapacity(self: *Self, key: K) GetOrPutResult {
- return self.unmanaged.getOrPutAssumeCapacity(key);
+ return self.unmanaged.getOrPutAssumeCapacityContext(key, self.ctx);
+ }
+
+ /// 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 value, and
+ /// the `Entry` pointers point to it. Caller must then initialize
+ /// the key and value.
+ /// If a new entry needs to be stored, this function asserts there
+ /// is enough capacity to store it.
+ pub fn getOrPutAssumeCapacityAdapted(self: *Self, key: anytype, ctx: anytype) GetOrPutResult {
+ return self.unmanaged.getOrPutAssumeCapacityAdapted(self.allocator, key, ctx);
}
- pub fn getOrPutValue(self: *Self, key: K, value: V) !*Entry {
- return self.unmanaged.getOrPutValue(self.allocator, key, value);
+ pub fn getOrPutValue(self: *Self, key: K, value: V) !Entry {
+ return self.unmanaged.getOrPutValueContext(self.allocator, key, value, self.ctx);
}
/// Increases capacity, guaranteeing that insertions up until the
/// `expected_count` will not cause an allocation, and therefore cannot fail.
pub fn ensureCapacity(self: *Self, expected_count: Size) !void {
- return self.unmanaged.ensureCapacity(self.allocator, expected_count);
+ return self.unmanaged.ensureCapacityContext(self.allocator, expected_count, self.ctx);
}
/// Returns the number of total elements which may be present before it is
@@ -174,67 +494,114 @@ pub fn HashMap(
/// 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.put(self.allocator, key, value);
+ 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.putNoClobber(self.allocator, key, value);
+ 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.putAssumeCapacity(key, value);
+ 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.putAssumeCapacityNoClobber(key, value);
+ 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) !?Entry {
- return self.unmanaged.fetchPut(self.allocator, key, value);
+ 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) ?Entry {
- return self.unmanaged.fetchPutAssumeCapacity(key, value);
+ pub fn fetchPutAssumeCapacity(self: *Self, key: K, value: V) ?KV {
+ return self.unmanaged.fetchPutAssumeCapacityContext(key, value, self.ctx);
}
+ /// Removes a value from the map and returns the removed kv pair.
+ pub fn fetchRemove(self: *Self, key: K) ?KV {
+ return self.unmanaged.fetchRemoveContext(key, self.ctx);
+ }
+
+ pub fn fetchRemoveAdapted(self: *Self, key: anytype, ctx: anytype) ?KV {
+ return self.unmanaged.fetchRemoveAdapted(key, ctx);
+ }
+
+ /// Finds the value associated with a key in the map
pub fn get(self: Self, key: K) ?V {
- return self.unmanaged.get(key);
+ return self.unmanaged.getContext(key, self.ctx);
+ }
+ pub fn getAdapted(self: Self, key: anytype, ctx: anytype) ?V {
+ return self.unmanaged.getAdapted(key, ctx);
+ }
+
+ pub fn getPtr(self: Self, key: K) ?*V {
+ return self.unmanaged.getPtrContext(key, self.ctx);
+ }
+ pub fn getPtrAdapted(self: Self, key: anytype, ctx: anytype) ?*V {
+ return self.unmanaged.getPtrAdapted(key, self.ctx);
+ }
+
+ /// Finds the key and value associated with a key in the map
+ pub fn getEntry(self: Self, key: K) ?Entry {
+ return self.unmanaged.getEntryContext(key, self.ctx);
}
- pub fn getEntry(self: Self, key: K) ?*Entry {
- return self.unmanaged.getEntry(key);
+ pub fn getEntryAdapted(self: Self, key: anytype, ctx: anytype) ?Entry {
+ return self.unmanaged.getEntryAdapted(key, ctx);
}
+ /// Check if the map contains a key
pub fn contains(self: Self, key: K) bool {
- return self.unmanaged.contains(key);
+ 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.
- pub fn remove(self: *Self, key: K) ?Entry {
- return self.unmanaged.remove(key);
+ pub fn remove(self: *Self, key: K) bool {
+ return self.unmanaged.removeContext(key, self.ctx);
}
- /// Asserts there is an `Entry` with matching key, deletes it from the hash map,
- /// and discards it.
- pub fn removeAssertDiscard(self: *Self, key: K) void {
- return self.unmanaged.removeAssertDiscard(key);
+ pub fn removeAdapted(self: *Self, key: anytype, ctx: anytype) bool {
+ return self.unmanaged.removeAdapted(key, ctx);
}
+ /// Creates a copy of this map, using the same allocator
pub fn clone(self: Self) !Self {
- var other = try self.unmanaged.clone(self.allocator);
- return other.promote(self.allocator);
+ var other = try self.unmanaged.cloneContext(self.allocator, self.ctx);
+ return other.promoteContext(self.allocator, self.ctx);
+ }
+
+ /// Creates a copy of this map, using a specified allocator
+ pub fn cloneWithAllocator(self: Self, new_allocator: *Allocator) !Self {
+ var other = try self.unmanaged.cloneContext(new_allocator, self.ctx);
+ return other.promoteContext(new_allocator, self.ctx);
+ }
+
+ /// Creates a copy of this map, using a specified context
+ pub fn cloneWithContext(self: Self, new_ctx: anytype) !HashMap(K, V, @TypeOf(new_ctx), max_load_percentage) {
+ var other = try self.unmanaged.cloneContext(self.allocator, new_ctx);
+ return other.promoteContext(self.allocator, new_ctx);
+ }
+
+ /// Creates a copy of this map, using a specified allocator and context
+ pub fn cloneWithAllocatorAndContext(new_allocator: *Allocator, new_ctx: anytype) !HashMap(K, V, @TypeOf(new_ctx), max_load_percentage) {
+ var other = try self.unmanaged.cloneContext(new_allocator, new_ctx);
+ return other.promoteContext(new_allocator, new_ctx);
}
};
}
@@ -251,11 +618,12 @@ pub fn HashMap(
pub fn HashMapUnmanaged(
comptime K: type,
comptime V: type,
- hashFn: fn (key: K) u64,
- eqlFn: fn (a: K, b: K) bool,
+ comptime Context: type,
comptime max_load_percentage: u64,
) type {
- comptime assert(max_load_percentage > 0 and max_load_percentage < 100);
+ if (max_load_percentage <= 0 or max_load_percentage >= 100)
+ @compileError("max_load_percentage must be between 0 and 100.");
+ comptime verifyContext(Context, K, K, u64);
return struct {
const Self = @This();
@@ -284,19 +652,25 @@ pub fn HashMapUnmanaged(
const minimal_capacity = 8;
// This hashmap is specially designed for sizes that fit in a u32.
- const Size = u32;
+ pub const Size = u32;
// u64 hashes guarantee us that the fingerprint bits will never be used
// to compute the index of a slot, maximizing the use of entropy.
- const Hash = u64;
+ pub const Hash = u64;
pub const Entry = struct {
+ key_ptr: *K,
+ value_ptr: *V,
+ };
+
+ pub const KV = struct {
key: K,
value: V,
};
const Header = packed struct {
- entries: [*]Entry,
+ values: [*]V,
+ keys: [*]K,
capacity: Size,
};
@@ -353,11 +727,11 @@ pub fn HashMapUnmanaged(
assert(@alignOf(Metadata) == 1);
}
- const Iterator = struct {
+ pub const Iterator = struct {
hm: *const Self,
index: Size = 0,
- pub fn next(it: *Iterator) ?*Entry {
+ pub fn next(it: *Iterator) ?Entry {
assert(it.index <= it.hm.capacity());
if (it.hm.size == 0) return null;
@@ -370,9 +744,10 @@ pub fn HashMapUnmanaged(
it.index += 1;
}) {
if (metadata[0].isUsed()) {
- const entry = &it.hm.entries()[it.index];
+ const key = &it.hm.keys()[it.index];
+ const value = &it.hm.values()[it.index];
it.index += 1;
- return entry;
+ return Entry{ .key_ptr = key, .value_ptr = value };
}
}
@@ -380,17 +755,50 @@ pub fn HashMapUnmanaged(
}
};
+ pub const KeyIterator = FieldIterator(K);
+ pub const ValueIterator = FieldIterator(V);
+
+ fn FieldIterator(comptime T: type) type {
+ return struct {
+ len: usize,
+ metadata: [*]const Metadata,
+ items: [*]T,
+
+ pub fn next(self: *@This()) ?*T {
+ while (self.len > 0) {
+ self.len -= 1;
+ const used = self.metadata[0].isUsed();
+ const item = &self.items[0];
+ self.metadata += 1;
+ self.items += 1;
+ if (used) {
+ return item;
+ }
+ }
+ return null;
+ }
+ };
+ }
+
pub const GetOrPutResult = struct {
- entry: *Entry,
+ key_ptr: *K,
+ value_ptr: *V,
found_existing: bool,
};
- pub const Managed = HashMap(K, V, hashFn, eqlFn, max_load_percentage);
+ pub const Managed = HashMap(K, V, Context, max_load_percentage);
pub fn promote(self: Self, allocator: *Allocator) Managed {
+ if (@sizeOf(Context) != 0)
+ @compileError("Cannot infer context "++@typeName(Context)++", call promoteContext instead.");
+ return promoteContext(self, allocator, undefined);
+ }
+
+ pub fn promoteContext(self: Self, allocator: *Allocator, ctx: Context) Managed {
return .{
.unmanaged = self,
.allocator = allocator,
+ .ctx = ctx,
};
}
@@ -403,26 +811,6 @@ pub fn HashMapUnmanaged(
self.* = undefined;
}
- fn deallocate(self: *Self, allocator: *Allocator) void {
- if (self.metadata == null) return;
-
- const cap = self.capacity();
- const meta_size = @sizeOf(Header) + cap * @sizeOf(Metadata);
-
- const alignment = @alignOf(Entry) - 1;
- const entries_size = @as(usize, cap) * @sizeOf(Entry) + alignment;
-
- const total_size = meta_size + entries_size;
-
- var slice: []u8 = undefined;
- slice.ptr = @intToPtr([*]u8, @ptrToInt(self.header()));
- slice.len = total_size;
- allocator.free(slice);
-
- self.metadata = null;
- self.available = 0;
- }
-
fn capacityForSize(size: Size) Size {
var new_cap = @truncate(u32, (@as(u64, size) * 100) / max_load_percentage + 1);
new_cap = math.ceilPowerOfTwo(u32, new_cap) catch unreachable;
@@ -430,8 +818,13 @@ pub fn HashMapUnmanaged(
}
pub fn ensureCapacity(self: *Self, allocator: *Allocator, new_size: Size) !void {
+ if (@sizeOf(Context) != 0)
+ @compileError("Cannot infer context "++@typeName(Context)++", call ensureCapacityContext instead.");
+ return ensureCapacityContext(self, allocator, new_size, undefined);
+ }
+ pub fn ensureCapacityContext(self: *Self, allocator: *Allocator, new_size: Size, ctx: Context) !void {
if (new_size > self.size)
- try self.growIfNeeded(allocator, new_size - self.size);
+ try self.growIfNeeded(allocator, new_size - self.size, ctx);
}
pub fn clearRetainingCapacity(self: *Self) void {
@@ -456,8 +849,12 @@ pub fn HashMapUnmanaged(
return @ptrCast(*Header, @ptrCast([*]Header, self.metadata.?) - 1);
}
- fn entries(self: *const Self) [*]Entry {
- return self.header().entries;
+ fn keys(self: *const Self) [*]K {
+ return self.header().keys;
+ }
+
+ fn values(self: *const Self) [*]V {
+ return self.header().values;
}
pub fn capacity(self: *const Self) Size {
@@ -470,28 +867,75 @@ pub fn HashMapUnmanaged(
return .{ .hm = self };
}
+ pub fn keyIterator(self: *const Self) KeyIterator {
+ if (self.metadata) |metadata| {
+ return .{
+ .len = self.capacity(),
+ .metadata = metadata,
+ .items = self.keys(),
+ };
+ } else {
+ return .{
+ .len = 0,
+ .metadata = undefined,
+ .items = undefined,
+ };
+ }
+ }
+
+ pub fn valueIterator(self: *const Self) ValueIterator {
+ if (self.metadata) |metadata| {
+ return .{
+ .len = self.capacity(),
+ .metadata = metadata,
+ .items = self.values(),
+ };
+ } else {
+ return .{
+ .len = 0,
+ .metadata = undefined,
+ .items = undefined,
+ };
+ }
+ }
+
/// Insert an entry in the map. Assumes it is not already present.
pub fn putNoClobber(self: *Self, allocator: *Allocator, key: K, value: V) !void {
- assert(!self.contains(key));
- try self.growIfNeeded(allocator, 1);
+ if (@sizeOf(Context) != 0)
+ @compileError("Cannot infer context "++@typeName(Context)++", call putNoClobberContext instead.");
+ return self.putNoClobberContext(allocator, key, value, undefined);
+ }
+ pub fn putNoClobberContext(self: *Self, allocator: *Allocator, key: K, value: V, ctx: Context) !void {
+ assert(!self.containsContext(key, ctx));
+ try self.growIfNeeded(allocator, 1, ctx);
- self.putAssumeCapacityNoClobber(key, value);
+ self.putAssumeCapacityNoClobberContext(key, value, ctx);
}
/// Asserts there is enough capacity to store the new key-value pair.
/// Clobbers any existing data. To detect if a put would clobber
/// existing data, see `getOrPutAssumeCapacity`.
pub fn putAssumeCapacity(self: *Self, key: K, value: V) void {
- const gop = self.getOrPutAssumeCapacity(key);
- gop.entry.value = value;
+ if (@sizeOf(Context) != 0)
+ @compileError("Cannot infer context "++@typeName(Context)++", call putAssumeCapacityContext instead.");
+ return self.putAssumeCapacityContext(key, value, undefined);
+ }
+ pub fn putAssumeCapacityContext(self: *Self, key: K, value: V, ctx: Context) void {
+ const gop = self.getOrPutAssumeCapacityContext(key, ctx);
+ gop.value_ptr.* = value;
}
/// Insert an entry in the map. Assumes it is not already present,
/// and that no allocation is needed.
pub fn putAssumeCapacityNoClobber(self: *Self, key: K, value: V) void {
- assert(!self.contains(key));
+ if (@sizeOf(Context) != 0)
+ @compileError("Cannot infer context "++@typeName(Context)++", call putAssumeCapacityNoClobberContext instead.");
+ return self.putAssumeCapacityNoClobberContext(key, value, undefined);
+ }
+ pub fn putAssumeCapacityNoClobberContext(self: *Self, key: K, value: V, ctx: Context) void {
+ assert(!self.containsContext(key, ctx));
- const hash = hashFn(key);
+ const hash = ctx.hash(key);
const mask = self.capacity() - 1;
var idx = @truncate(usize, hash & mask);
@@ -508,40 +952,102 @@ pub fn HashMapUnmanaged(
const fingerprint = Metadata.takeFingerprint(hash);
metadata[0].fill(fingerprint);
- self.entries()[idx] = Entry{ .key = key, .value = value };
+ self.keys()[idx] = key;
+ self.values()[idx] = value;
self.size += 1;
}
/// Inserts a new `Entry` into the hash map, returning the previous one, if any.
- pub fn fetchPut(self: *Self, allocator: *Allocator, key: K, value: V) !?Entry {
- const gop = try self.getOrPut(allocator, key);
- var result: ?Entry = null;
+ pub fn fetchPut(self: *Self, allocator: *Allocator, key: K, value: V) !?KV {
+ if (@sizeOf(Context) != 0)
+ @compileError("Cannot infer context "++@typeName(Context)++", call fetchPutContext instead.");
+ return self.fetchPutContext(allocator, key, value, undefined);
+ }
+ pub fn fetchPutContext(self: *Self, allocator: *Allocator, key: K, value: V, ctx: Context) !?KV {
+ const gop = try self.getOrPutContext(allocator, key, ctx);
+ var result: ?KV = null;
if (gop.found_existing) {
- result = gop.entry.*;
+ result = KV{
+ .key = gop.key_ptr.*,
+ .value = gop.value_ptr.*,
+ };
}
- gop.entry.value = value;
+ 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) ?Entry {
- const gop = self.getOrPutAssumeCapacity(key);
- var result: ?Entry = null;
+ 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 = gop.entry.*;
+ result = KV{
+ .key = gop.key_ptr.*,
+ .value = gop.value_ptr.*,
+ };
}
- gop.entry.value = value;
+ gop.value_ptr.* = value;
return result;
}
- pub fn getEntry(self: Self, key: K) ?*Entry {
+ /// If there is an `Entry` with a matching key, it is deleted from
+ /// the hash map, and then returned from this function.
+ pub fn fetchRemove(self: *Self, key: K) ?KV {
+ if (@sizeOf(Context) != 0)
+ @compileError("Cannot infer context "++@typeName(Context)++", call fetchRemoveContext instead.");
+ return self.fetchRemoveContext(key, undefined);
+ }
+ pub fn fetchRemoveContext(self: *Self, key: K, ctx: Context) ?KV {
+ return self.fetchRemoveAdapted(key, ctx);
+ }
+ pub fn fetchRemoveAdapted(self: *Self, key: anytype, ctx: anytype) ?KV {
+ if (self.getIndex(key, ctx)) |idx| {
+ const old_key = &self.keys()[idx];
+ const old_val = &self.values()[idx];
+ const result = KV{
+ .key = old_key.*,
+ .value = old_val.*,
+ };
+ self.metadata.?[idx].remove();
+ old_key.* = undefined;
+ old_val.* = undefined;
+ self.size -= 1;
+ return result;
+ }
+
+ return null;
+ }
+
+ /// Find the index containing the data for the given key.
+ /// Whether this function returns null is almost always
+ /// branched on after this function returns, and this function
+ /// returns null/not null from separate code paths. We
+ /// want the optimizer to remove that branch and instead directly
+ /// fuse the basic blocks after the branch to the basic blocks
+ /// from this function. To encourage that, this function is
+ /// marked as inline.
+ fn getIndex(self: Self, key: anytype, ctx: anytype) callconv(.Inline) ?usize {
+ comptime verifyContext(@TypeOf(ctx), @TypeOf(key), K, Hash);
+
if (self.size == 0) {
return null;
}
- const hash = hashFn(key);
+ // If you get a compile error on this line, it means that your generic hash
+ // function is invalid for these parameters.
+ const hash = ctx.hash(key);
+ // verifyContext can't verify the return type of generic hash functions,
+ // so we need to double-check it here.
+ if (@TypeOf(hash) != Hash) {
+ @compileError("Context "++@typeName(@TypeOf(ctx))++" has a generic hash function that returns the wrong type! "++@typeName(Hash)++" was expected, but found "++@typeName(@TypeOf(hash)));
+ }
const mask = self.capacity() - 1;
const fingerprint = Metadata.takeFingerprint(hash);
var idx = @truncate(usize, hash & mask);
@@ -549,11 +1055,20 @@ pub fn HashMapUnmanaged(
var metadata = self.metadata.? + idx;
while (metadata[0].isUsed() or metadata[0].isTombstone()) {
if (metadata[0].isUsed() and metadata[0].fingerprint == fingerprint) {
- const entry = &self.entries()[idx];
- if (eqlFn(entry.key, key)) {
- return entry;
+ const test_key = &self.keys()[idx];
+ // If you get a compile error on this line, it means that your generic eql
+ // function is invalid for these parameters.
+ const eql = ctx.eql(key, test_key.*);
+ // verifyContext can't verify the return type of generic eql functions,
+ // so we need to double-check it here.
+ if (@TypeOf(eql) != bool) {
+ @compileError("Context "++@typeName(@TypeOf(ctx))++" has a generic eql function that returns the wrong type! bool was expected, but found "++@typeName(@TypeOf(eql)));
+ }
+ if (eql) {
+ return idx;
}
}
+
idx = (idx + 1) & mask;
metadata = self.metadata.? + idx;
}
@@ -561,46 +1076,122 @@ pub fn HashMapUnmanaged(
return null;
}
+ pub fn getEntry(self: Self, key: K) ?Entry {
+ if (@sizeOf(Context) != 0)
+ @compileError("Cannot infer context "++@typeName(Context)++", call getEntryContext instead.");
+ return self.getEntryContext(key, undefined);
+ }
+ pub fn getEntryContext(self: Self, key: K, ctx: Context) ?Entry {
+ return self.getEntryAdapted(key, ctx);
+ }
+ pub fn getEntryAdapted(self: Self, key: anytype, ctx: anytype) ?Entry {
+ if (self.getIndex(key, ctx)) |idx| {
+ return Entry{
+ .key_ptr = &self.keys()[idx],
+ .value_ptr = &self.values()[idx],
+ };
+ }
+ return null;
+ }
+
/// Insert an entry if the associated key is not already present, otherwise update preexisting value.
pub fn put(self: *Self, allocator: *Allocator, key: K, value: V) !void {
- const result = try self.getOrPut(allocator, key);
- result.entry.value = value;
+ if (@sizeOf(Context) != 0)
+ @compileError("Cannot infer context "++@typeName(Context)++", call putContext instead.");
+ return self.putContext(allocator, key, value, undefined);
+ }
+ pub fn putContext(self: *Self, allocator: *Allocator, key: K, value: V, ctx: Context) !void {
+ const result = try self.getOrPutContext(allocator, key, ctx);
+ result.value_ptr.* = value;
}
/// Get an optional pointer to the value associated with key, if present.
- pub fn get(self: Self, key: K) ?V {
- if (self.size == 0) {
- return null;
+ pub fn getPtr(self: Self, key: K) ?*V {
+ if (@sizeOf(Context) != 0)
+ @compileError("Cannot infer context "++@typeName(Context)++", call getPtrContext instead.");
+ return self.getPtrContext(key, undefined);
+ }
+ pub fn getPtrContext(self: Self, key: K, ctx: Context) ?*V {
+ return self.getPtrAdapted(key, ctx);
+ }
+ pub fn getPtrAdapted(self: Self, key: anytype, ctx: anytype) ?*V {
+ if (self.getIndex(key, ctx)) |idx| {
+ return &self.values()[idx];
}
+ return null;
+ }
- const hash = hashFn(key);
- const mask = self.capacity() - 1;
- const fingerprint = Metadata.takeFingerprint(hash);
- var idx = @truncate(usize, hash & mask);
-
- var metadata = self.metadata.? + idx;
- while (metadata[0].isUsed() or metadata[0].isTombstone()) {
- if (metadata[0].isUsed() and metadata[0].fingerprint == fingerprint) {
- const entry = &self.entries()[idx];
- if (eqlFn(entry.key, key)) {
- return entry.value;
- }
- }
- idx = (idx + 1) & mask;
- metadata = self.metadata.? + idx;
+ /// Get a copy of the value associated with key, if present.
+ pub fn get(self: Self, key: K) ?V {
+ if (@sizeOf(Context) != 0)
+ @compileError("Cannot infer context "++@typeName(Context)++", call getContext instead.");
+ return self.getContext(key, undefined);
+ }
+ pub fn getContext(self: Self, key: K, ctx: Context) ?V {
+ return self.getAdapted(key, ctx);
+ }
+ pub fn getAdapted(self: Self, key: anytype, ctx: anytype) ?V {
+ if (self.getIndex(key, ctx)) |idx| {
+ return self.values()[idx];
}
-
return null;
}
pub fn getOrPut(self: *Self, allocator: *Allocator, key: K) !GetOrPutResult {
- try self.growIfNeeded(allocator, 1);
-
- return self.getOrPutAssumeCapacity(key);
+ if (@sizeOf(Context) != 0)
+ @compileError("Cannot infer context "++@typeName(Context)++", call getOrPutContext instead.");
+ return self.getOrPutContext(allocator, key, undefined);
+ }
+ pub fn getOrPutContext(self: *Self, allocator: *Allocator, key: K, ctx: Context) !GetOrPutResult {
+ const gop = try self.getOrPutContextAdapted(allocator, key, ctx, ctx);
+ if (!gop.found_existing) {
+ gop.key_ptr.* = key;
+ }
+ return gop;
+ }
+ pub fn getOrPutAdapted(self: *Self, allocator: *Allocator, key: anytype, key_ctx: anytype) !GetOrPutResult {
+ if (@sizeOf(Context) != 0)
+ @compileError("Cannot infer context "++@typeName(Context)++", call getOrPutContextAdapted instead.");
+ return self.getOrPutContextAdapted(allocator, key, key_ctx, undefined);
+ }
+ pub fn getOrPutContextAdapted(self: *Self, allocator: *Allocator, key: anytype, key_ctx: anytype, ctx: Context) !GetOrPutResult {
+ self.growIfNeeded(allocator, 1, ctx) catch |err| {
+ // If allocation fails, try to do the lookup anyway.
+ // If we find an existing item, we can return it.
+ // Otherwise return the error, we could not add another.
+ const index = self.getIndex(key, key_ctx) orelse return err;
+ return GetOrPutResult{
+ .key_ptr = &self.keys()[index],
+ .value_ptr = &self.values()[index],
+ .found_existing = true,
+ };
+ };
+ return self.getOrPutAssumeCapacityAdapted(key, key_ctx);
}
pub fn getOrPutAssumeCapacity(self: *Self, key: K) GetOrPutResult {
- const hash = hashFn(key);
+ if (@sizeOf(Context) != 0)
+ @compileError("Cannot infer context "++@typeName(Context)++", call getOrPutAssumeCapacityContext instead.");
+ return self.getOrPutAssumeCapacityContext(key, undefined);
+ }
+ pub fn getOrPutAssumeCapacityContext(self: *Self, key: K, ctx: Context) GetOrPutResult {
+ const result = self.getOrPutAssumeCapacityAdapted(key, ctx);
+ if (!result.found_existing) {
+ result.key_ptr.* = key;
+ }
+ return result;
+ }
+ pub fn getOrPutAssumeCapacityAdapted(self: *Self, key: anytype, ctx: anytype) GetOrPutResult {
+ comptime verifyContext(@TypeOf(ctx), @TypeOf(key), K, Hash);
+
+ // If you get a compile error on this line, it means that your generic hash
+ // function is invalid for these parameters.
+ const hash = ctx.hash(key);
+ // verifyContext can't verify the return type of generic hash functions,
+ // so we need to double-check it here.
+ if (@TypeOf(hash) != Hash) {
+ @compileError("Context "++@typeName(@TypeOf(ctx))++" has a generic hash function that returns the wrong type! "++@typeName(Hash)++" was expected, but found "++@typeName(@TypeOf(hash)));
+ }
const mask = self.capacity() - 1;
const fingerprint = Metadata.takeFingerprint(hash);
var idx = @truncate(usize, hash & mask);
@@ -609,9 +1200,21 @@ pub fn HashMapUnmanaged(
var metadata = self.metadata.? + idx;
while (metadata[0].isUsed() or metadata[0].isTombstone()) {
if (metadata[0].isUsed() and metadata[0].fingerprint == fingerprint) {
- const entry = &self.entries()[idx];
- if (eqlFn(entry.key, key)) {
- return GetOrPutResult{ .entry = entry, .found_existing = true };
+ const test_key = &self.keys()[idx];
+ // If you get a compile error on this line, it means that your generic eql
+ // function is invalid for these parameters.
+ const eql = ctx.eql(key, test_key.*);
+ // verifyContext can't verify the return type of generic eql functions,
+ // so we need to double-check it here.
+ if (@TypeOf(eql) != bool) {
+ @compileError("Context "++@typeName(@TypeOf(ctx))++" has a generic eql function that returns the wrong type! bool was expected, but found "++@typeName(@TypeOf(eql)));
+ }
+ if (eql) {
+ return GetOrPutResult{
+ .key_ptr = test_key,
+ .value_ptr = &self.values()[idx],
+ .found_existing = true,
+ };
}
} else if (first_tombstone_idx == self.capacity() and metadata[0].isTombstone()) {
first_tombstone_idx = idx;
@@ -631,79 +1234,67 @@ pub fn HashMapUnmanaged(
}
metadata[0].fill(fingerprint);
- const entry = &self.entries()[idx];
- entry.* = .{ .key = key, .value = undefined };
+ const new_key = &self.keys()[idx];
+ const new_value = &self.values()[idx];
+ new_key.* = key;
+ new_value.* = undefined;
self.size += 1;
- return GetOrPutResult{ .entry = entry, .found_existing = false };
+ return GetOrPutResult{
+ .key_ptr = new_key,
+ .value_ptr = new_value,
+ .found_existing = false,
+ };
}
- pub fn getOrPutValue(self: *Self, allocator: *Allocator, key: K, value: V) !*Entry {
- const res = try self.getOrPut(allocator, key);
- if (!res.found_existing) res.entry.value = value;
- return res.entry;
+ pub fn getOrPutValue(self: *Self, allocator: *Allocator, key: K, value: V) !Entry {
+ if (@sizeOf(Context) != 0)
+ @compileError("Cannot infer context "++@typeName(Context)++", call getOrPutValueContext instead.");
+ return self.getOrPutValueContext(allocator, key, value, undefined);
+ }
+ pub fn getOrPutValueContext(self: *Self, allocator: *Allocator, key: K, value: V, ctx: Context) !Entry {
+ const res = try self.getOrPutAdapted(allocator, key, ctx);
+ if (!res.found_existing) {
+ res.key_ptr.* = key;
+ res.value_ptr.* = value;
+ }
+ return Entry{ .key_ptr = res.key_ptr, .value_ptr = res.value_ptr };
}
/// Return true if there is a value associated with key in the map.
pub fn contains(self: *const Self, key: K) bool {
- return self.get(key) != null;
+ if (@sizeOf(Context) != 0)
+ @compileError("Cannot infer context "++@typeName(Context)++", call containsContext instead.");
+ return self.containsContext(key, undefined);
}
-
- /// If there is an `Entry` with a matching key, it is deleted from
- /// the hash map, and then returned from this function.
- pub fn remove(self: *Self, key: K) ?Entry {
- if (self.size == 0) return null;
-
- const hash = hashFn(key);
- const mask = self.capacity() - 1;
- const fingerprint = Metadata.takeFingerprint(hash);
- var idx = @truncate(usize, hash & mask);
-
- var metadata = self.metadata.? + idx;
- while (metadata[0].isUsed() or metadata[0].isTombstone()) {
- if (metadata[0].isUsed() and metadata[0].fingerprint == fingerprint) {
- const entry = &self.entries()[idx];
- if (eqlFn(entry.key, key)) {
- const removed_entry = entry.*;
- metadata[0].remove();
- entry.* = undefined;
- self.size -= 1;
- return removed_entry;
- }
- }
- idx = (idx + 1) & mask;
- metadata = self.metadata.? + idx;
- }
-
- return null;
+ pub fn containsContext(self: *const Self, key: K, ctx: Context) bool {
+ return self.containsAdapted(key, ctx);
+ }
+ pub fn containsAdapted(self: *const Self, key: anytype, ctx: anytype) bool {
+ return self.getIndex(key, ctx) != null;
}
- /// Asserts there is an `Entry` with matching key, deletes it from the hash map,
- /// and discards it.
- pub fn removeAssertDiscard(self: *Self, key: K) void {
- assert(self.contains(key));
-
- const hash = hashFn(key);
- const mask = self.capacity() - 1;
- const fingerprint = Metadata.takeFingerprint(hash);
- var idx = @truncate(usize, hash & mask);
-
- var metadata = self.metadata.? + idx;
- while (metadata[0].isUsed() or metadata[0].isTombstone()) {
- if (metadata[0].isUsed() and metadata[0].fingerprint == fingerprint) {
- const entry = &self.entries()[idx];
- if (eqlFn(entry.key, key)) {
- metadata[0].remove();
- entry.* = undefined;
- self.size -= 1;
- return;
- }
- }
- idx = (idx + 1) & mask;
- metadata = self.metadata.? + idx;
+ /// If there is an `Entry` with a matching key, it is deleted from
+ /// the hash map, and this function returns true. Otherwise this
+ /// function returns false.
+ pub fn remove(self: *Self, key: K) bool {
+ if (@sizeOf(Context) != 0)
+ @compileError("Cannot infer context "++@typeName(Context)++", call removeContext instead.");
+ return self.removeContext(key, undefined);
+ }
+ pub fn removeContext(self: *Self, key: K, ctx: Context) bool {
+ return self.removeAdapted(key, ctx);
+ }
+ pub fn removeAdapted(self: *Self, key: anytype, ctx: anytype) bool {
+ if (self.getIndex(key, ctx)) |idx| {
+ self.metadata.?[idx].remove();
+ self.keys()[idx] = undefined;
+ self.values()[idx] = undefined;
+ self.size -= 1;
+ return true;
}
- unreachable;
+ return false;
}
fn initMetadatas(self: *Self) void {
@@ -718,14 +1309,19 @@ pub fn HashMapUnmanaged(
return @truncate(Size, max_load - self.available);
}
- fn growIfNeeded(self: *Self, allocator: *Allocator, new_count: Size) !void {
+ fn growIfNeeded(self: *Self, allocator: *Allocator, new_count: Size, ctx: Context) !void {
if (new_count > self.available) {
- try self.grow(allocator, capacityForSize(self.load() + new_count));
+ try self.grow(allocator, capacityForSize(self.load() + new_count), ctx);
}
}
pub fn clone(self: Self, allocator: *Allocator) !Self {
- var other = Self{};
+ if (@sizeOf(Context) != 0)
+ @compileError("Cannot infer context "++@typeName(Context)++", call cloneContext instead.");
+ return self.cloneContext(allocator, @as(Context, undefined));
+ }
+ pub fn cloneContext(self: Self, allocator: *Allocator, new_ctx: anytype) !HashMapUnmanaged(K, V, @TypeOf(new_ctx), max_load_percentage) {
+ var other = HashMapUnmanaged(K, V, @TypeOf(new_ctx), max_load_percentage){};
if (self.size == 0)
return other;
@@ -736,11 +1332,11 @@ pub fn HashMapUnmanaged(
var i: Size = 0;
var metadata = self.metadata.?;
- var entr = self.entries();
+ var keys_ptr = self.keys();
+ var values_ptr = self.values();
while (i < self.capacity()) : (i += 1) {
if (metadata[i].isUsed()) {
- const entry = &entr[i];
- other.putAssumeCapacityNoClobber(entry.key, entry.value);
+ other.putAssumeCapacityNoClobberContext(keys_ptr[i], values_ptr[i], new_ctx);
if (other.size == self.size)
break;
}
@@ -749,7 +1345,8 @@ pub fn HashMapUnmanaged(
return other;
}
- fn grow(self: *Self, allocator: *Allocator, new_capacity: Size) !void {
+ fn grow(self: *Self, allocator: *Allocator, new_capacity: Size, ctx: Context) !void {
+ @setCold(true);
const new_cap = std.math.max(new_capacity, minimal_capacity);
assert(new_cap > self.capacity());
assert(std.math.isPowerOfTwo(new_cap));
@@ -764,11 +1361,11 @@ pub fn HashMapUnmanaged(
const old_capacity = self.capacity();
var i: Size = 0;
var metadata = self.metadata.?;
- var entr = self.entries();
+ var keys_ptr = self.keys();
+ var values_ptr = self.values();
while (i < old_capacity) : (i += 1) {
if (metadata[i].isUsed()) {
- const entry = &entr[i];
- map.putAssumeCapacityNoClobber(entry.key, entry.value);
+ map.putAssumeCapacityNoClobberContext(keys_ptr[i], values_ptr[i], ctx);
if (map.size == self.size)
break;
}
@@ -780,26 +1377,64 @@ pub fn HashMapUnmanaged(
}
fn allocate(self: *Self, allocator: *Allocator, new_capacity: Size) !void {
+ const header_align = @alignOf(Header);
+ const key_align = if (@sizeOf(K) == 0) 1 else @alignOf(K);
+ const val_align = if (@sizeOf(V) == 0) 1 else @alignOf(V);
+ const max_align = comptime math.max3(header_align, key_align, val_align);
+
const meta_size = @sizeOf(Header) + new_capacity * @sizeOf(Metadata);
+ comptime assert(@alignOf(Metadata) == 1);
+
+ const keys_start = std.mem.alignForward(meta_size, key_align);
+ const keys_end = keys_start + new_capacity * @sizeOf(K);
- const alignment = @alignOf(Entry) - 1;
- const entries_size = @as(usize, new_capacity) * @sizeOf(Entry) + alignment;
+ const vals_start = std.mem.alignForward(keys_end, val_align);
+ const vals_end = vals_start + new_capacity * @sizeOf(V);
- const total_size = meta_size + entries_size;
+ const total_size = std.mem.alignForward(vals_end, max_align);
- const slice = try allocator.alignedAlloc(u8, @alignOf(Header), total_size);
+ const slice = try allocator.alignedAlloc(u8, max_align, total_size);
const ptr = @ptrToInt(slice.ptr);
const metadata = ptr + @sizeOf(Header);
- var entry_ptr = ptr + meta_size;
- entry_ptr = (entry_ptr + alignment) & ~@as(usize, alignment);
- assert(entry_ptr + @as(usize, new_capacity) * @sizeOf(Entry) <= ptr + total_size);
const hdr = @intToPtr(*Header, ptr);
- hdr.entries = @intToPtr([*]Entry, entry_ptr);
+ if (@sizeOf([*]V) != 0) {
+ hdr.values = @intToPtr([*]V, ptr + vals_start);
+ }
+ if (@sizeOf([*]K) != 0) {
+ hdr.keys = @intToPtr([*]K, ptr + keys_start);
+ }
hdr.capacity = new_capacity;
self.metadata = @intToPtr([*]Metadata, metadata);
}
+
+ fn deallocate(self: *Self, allocator: *Allocator) void {
+ if (self.metadata == null) return;
+
+ const header_align = @alignOf(Header);
+ const key_align = if (@sizeOf(K) == 0) 1 else @alignOf(K);
+ const val_align = if (@sizeOf(V) == 0) 1 else @alignOf(V);
+ const max_align = comptime math.max3(header_align, key_align, val_align);
+
+ const cap = self.capacity();
+ const meta_size = @sizeOf(Header) + cap * @sizeOf(Metadata);
+ comptime assert(@alignOf(Metadata) == 1);
+
+ const keys_start = std.mem.alignForward(meta_size, key_align);
+ const keys_end = keys_start + cap * @sizeOf(K);
+
+ const vals_start = std.mem.alignForward(keys_end, val_align);
+ const vals_end = vals_start + cap * @sizeOf(V);
+
+ const total_size = std.mem.alignForward(vals_end, max_align);
+
+ const slice = @intToPtr([*]align(max_align) u8, @ptrToInt(self.header()))[0..total_size];
+ allocator.free(slice);
+
+ self.metadata = null;
+ self.available = 0;
+ }
};
}
@@ -822,14 +1457,14 @@ test "std.hash_map basic usage" {
var sum: u32 = 0;
var it = map.iterator();
while (it.next()) |kv| {
- sum += kv.key;
+ sum += kv.key_ptr.*;
}
- try expect(sum == total);
+ try expectEqual(total, sum);
i = 0;
sum = 0;
while (i < count) : (i += 1) {
- try expectEqual(map.get(i).?, i);
+ try expectEqual(i, map.get(i).?);
sum += map.get(i).?;
}
try expectEqual(total, sum);
@@ -903,7 +1538,7 @@ test "std.hash_map grow" {
i = 0;
var it = map.iterator();
while (it.next()) |kv| {
- try expectEqual(kv.key, kv.value);
+ try expectEqual(kv.key_ptr.*, kv.value_ptr.*);
i += 1;
}
try expectEqual(i, growTo);
@@ -931,9 +1566,9 @@ test "std.hash_map clone" {
defer b.deinit();
try expectEqual(b.count(), 3);
- try expectEqual(b.get(1), 1);
- try expectEqual(b.get(2), 2);
- try expectEqual(b.get(3), 3);
+ try expectEqual(b.get(1).?, 1);
+ try expectEqual(b.get(2).?, 2);
+ try expectEqual(b.get(3).?, 3);
}
test "std.hash_map ensureCapacity with existing elements" {
@@ -975,8 +1610,8 @@ test "std.hash_map remove" {
try expectEqual(map.count(), 10);
var it = map.iterator();
while (it.next()) |kv| {
- try expectEqual(kv.key, kv.value);
- try expect(kv.key % 3 != 0);
+ try expectEqual(kv.key_ptr.*, kv.value_ptr.*);
+ try expect(kv.key_ptr.* % 3 != 0);
}
i = 0;
@@ -1146,7 +1781,7 @@ test "std.hash_map putAssumeCapacity" {
i = 0;
var sum = i;
while (i < 20) : (i += 1) {
- sum += map.get(i).?;
+ sum += map.getPtr(i).?.*;
}
try expectEqual(sum, 190);
@@ -1201,33 +1836,34 @@ test "std.hash_map basic hash map usage" {
const gop1 = try map.getOrPut(5);
try testing.expect(gop1.found_existing == true);
- try testing.expect(gop1.entry.value == 55);
- gop1.entry.value = 77;
- try testing.expect(map.getEntry(5).?.value == 77);
+ try testing.expect(gop1.value_ptr.* == 55);
+ gop1.value_ptr.* = 77;
+ try testing.expect(map.getEntry(5).?.value_ptr.* == 77);
const gop2 = try map.getOrPut(99);
try testing.expect(gop2.found_existing == false);
- gop2.entry.value = 42;
- try testing.expect(map.getEntry(99).?.value == 42);
+ gop2.value_ptr.* = 42;
+ try testing.expect(map.getEntry(99).?.value_ptr.* == 42);
const gop3 = try map.getOrPutValue(5, 5);
- try testing.expect(gop3.value == 77);
+ try testing.expect(gop3.value_ptr.* == 77);
const gop4 = try map.getOrPutValue(100, 41);
- try testing.expect(gop4.value == 41);
+ try testing.expect(gop4.value_ptr.* == 41);
try testing.expect(map.contains(2));
- try testing.expect(map.getEntry(2).?.value == 22);
+ try testing.expect(map.getEntry(2).?.value_ptr.* == 22);
try testing.expect(map.get(2).? == 22);
- const rmv1 = map.remove(2);
+ const rmv1 = map.fetchRemove(2);
try testing.expect(rmv1.?.key == 2);
try testing.expect(rmv1.?.value == 22);
- try testing.expect(map.remove(2) == null);
+ try testing.expect(map.fetchRemove(2) == null);
+ try testing.expect(map.remove(2) == false);
try testing.expect(map.getEntry(2) == null);
try testing.expect(map.get(2) == null);
- map.removeAssertDiscard(3);
+ try testing.expect(map.remove(3) == true);
}
test "std.hash_map clone" {
@@ -1247,3 +1883,14 @@ test "std.hash_map clone" {
try testing.expect(copy.get(i).? == i * 10);
}
}
+
+test "compile everything" {
+ std.testing.refAllDecls(AutoHashMap(i32, i32));
+ std.testing.refAllDecls(StringHashMap([]const u8));
+ std.testing.refAllDecls(AutoHashMap(i32, void));
+ std.testing.refAllDecls(StringHashMap(u0));
+ std.testing.refAllDecls(AutoHashMapUnmanaged(i32, i32));
+ std.testing.refAllDecls(StringHashMapUnmanaged([]const u8));
+ std.testing.refAllDecls(AutoHashMapUnmanaged(i32, void));
+ std.testing.refAllDecls(StringHashMapUnmanaged(u0));
+}
generated by cgit v1.2.3 (git 2.39.1) at 2025-12-28 13:21:11 +0000