2019-03-02 16:46:04 -05:00
|
|
|
const std = @import("std.zig");
|
2022-03-16 15:38:30 +01:00
|
|
|
const builtin = @import("builtin");
|
2023-08-06 14:18:50 -05:00
|
|
|
const assert = std.debug.assert;
|
2020-08-02 23:24:03 +02:00
|
|
|
const autoHash = std.hash.autoHash;
|
2017-12-23 22:08:53 -05:00
|
|
|
const math = std.math;
|
|
|
|
|
const mem = std.mem;
|
2016-05-08 16:05:41 -07:00
|
|
|
const Allocator = mem.Allocator;
|
2020-08-02 23:24:03 +02:00
|
|
|
const Wyhash = std.hash.Wyhash;
|
2025-04-11 17:55:25 -07:00
|
|
|
const Alignment = std.mem.Alignment;
|
2020-08-02 23:24:03 +02:00
|
|
|
|
2021-06-03 15:39:26 -05:00
|
|
|
pub fn getAutoHashFn(comptime K: type, comptime Context: type) (fn (Context, K) u64) {
|
2020-12-28 09:43:52 +08:00
|
|
|
comptime {
|
|
|
|
|
assert(@hasDecl(std, "StringHashMap")); // detect when the following message needs updated
|
|
|
|
|
if (K == []const u8) {
|
2024-09-01 22:10:34 -05:00
|
|
|
@compileError("std.hash.autoHash does not allow slices here (" ++
|
2020-12-28 09:43:52 +08:00
|
|
|
@typeName(K) ++
|
|
|
|
|
") because the intent is unclear. " ++
|
|
|
|
|
"Consider using std.StringHashMap for hashing the contents of []const u8. " ++
|
2024-09-01 22:10:34 -05:00
|
|
|
"Alternatively, consider using std.hash.autoHashStrat or providing your own hash function instead.");
|
2020-12-28 09:43:52 +08:00
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
2020-08-02 23:24:03 +02:00
|
|
|
return struct {
|
2021-06-03 15:39:26 -05:00
|
|
|
fn hash(ctx: Context, key: K) u64 {
|
2021-06-19 21:10:22 -04:00
|
|
|
_ = ctx;
|
2023-11-21 15:23:44 -07:00
|
|
|
if (std.meta.hasUniqueRepresentation(K)) {
|
2020-08-02 23:24:03 +02:00
|
|
|
return Wyhash.hash(0, std.mem.asBytes(&key));
|
|
|
|
|
} else {
|
|
|
|
|
var hasher = Wyhash.init(0);
|
|
|
|
|
autoHash(&hasher, key);
|
|
|
|
|
return hasher.final();
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
}.hash;
|
|
|
|
|
}
|
|
|
|
|
|
2021-06-03 15:39:26 -05:00
|
|
|
pub fn getAutoEqlFn(comptime K: type, comptime Context: type) (fn (Context, K, K) bool) {
|
2020-08-02 23:24:03 +02:00
|
|
|
return struct {
|
2021-06-03 15:39:26 -05:00
|
|
|
fn eql(ctx: Context, a: K, b: K) bool {
|
2021-06-19 21:10:22 -04:00
|
|
|
_ = ctx;
|
2023-11-21 15:23:44 -07:00
|
|
|
return std.meta.eql(a, b);
|
2020-08-02 23:24:03 +02:00
|
|
|
}
|
|
|
|
|
}.eql;
|
|
|
|
|
}
|
2016-05-08 16:05:41 -07:00
|
|
|
|
2018-08-03 17:22:17 -04:00
|
|
|
pub fn AutoHashMap(comptime K: type, comptime V: type) type {
|
2021-06-03 15:39:26 -05:00
|
|
|
return HashMap(K, V, AutoContext(K), default_max_load_percentage);
|
2018-08-03 17:22:17 -04:00
|
|
|
}
|
|
|
|
|
|
2020-07-06 06:10:03 +00:00
|
|
|
pub fn AutoHashMapUnmanaged(comptime K: type, comptime V: type) type {
|
2021-06-03 15:39:26 -05:00
|
|
|
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());
|
|
|
|
|
};
|
2020-07-06 06:10:03 +00:00
|
|
|
}
|
|
|
|
|
|
2019-08-22 22:46:37 +02:00
|
|
|
/// Builtin hashmap for strings as keys.
|
2021-06-03 15:39:26 -05:00
|
|
|
/// Key memory is managed by the caller. Keys and values
|
|
|
|
|
/// will not automatically be freed.
|
2019-08-22 22:46:37 +02:00
|
|
|
pub fn StringHashMap(comptime V: type) type {
|
2021-06-03 15:39:26 -05:00
|
|
|
return HashMap([]const u8, V, StringContext, default_max_load_percentage);
|
2019-08-22 22:46:37 +02:00
|
|
|
}
|
|
|
|
|
|
2021-06-03 15:39:26 -05:00
|
|
|
/// Key memory is managed by the caller. Keys and values
|
|
|
|
|
/// will not automatically be freed.
|
2020-07-13 00:34:02 +10:00
|
|
|
pub fn StringHashMapUnmanaged(comptime V: type) type {
|
2021-06-03 15:39:26 -05:00
|
|
|
return HashMapUnmanaged([]const u8, V, StringContext, default_max_load_percentage);
|
2020-07-13 00:34:02 +10:00
|
|
|
}
|
|
|
|
|
|
2021-06-03 15:39:26 -05:00
|
|
|
pub const StringContext = struct {
|
|
|
|
|
pub fn hash(self: @This(), s: []const u8) u64 {
|
2021-06-19 21:10:22 -04:00
|
|
|
_ = self;
|
2021-06-03 15:39:26 -05:00
|
|
|
return hashString(s);
|
|
|
|
|
}
|
|
|
|
|
pub fn eql(self: @This(), a: []const u8, b: []const u8) bool {
|
2021-06-19 21:10:22 -04:00
|
|
|
_ = self;
|
2021-06-03 15:39:26 -05:00
|
|
|
return eqlString(a, b);
|
|
|
|
|
}
|
|
|
|
|
};
|
|
|
|
|
|
2019-08-22 22:46:37 +02:00
|
|
|
pub fn eqlString(a: []const u8, b: []const u8) bool {
|
2019-09-03 23:56:04 +02:00
|
|
|
return mem.eql(u8, a, b);
|
2019-08-22 22:46:37 +02:00
|
|
|
}
|
|
|
|
|
|
2020-08-02 23:24:03 +02:00
|
|
|
pub fn hashString(s: []const u8) u64 {
|
|
|
|
|
return std.hash.Wyhash.hash(0, s);
|
2019-08-22 22:46:37 +02:00
|
|
|
}
|
|
|
|
|
|
2021-09-03 06:50:27 -07:00
|
|
|
pub const StringIndexContext = struct {
|
2025-11-20 23:46:23 +01:00
|
|
|
bytes: *const std.ArrayList(u8),
|
2021-09-03 06:50:27 -07:00
|
|
|
|
2024-02-21 16:21:14 +01:00
|
|
|
pub fn eql(_: @This(), a: u32, b: u32) bool {
|
2021-09-03 06:50:27 -07:00
|
|
|
return a == b;
|
|
|
|
|
}
|
|
|
|
|
|
2024-02-21 16:21:14 +01:00
|
|
|
pub fn hash(ctx: @This(), key: u32) u64 {
|
|
|
|
|
return hashString(mem.sliceTo(ctx.bytes.items[key..], 0));
|
2021-09-03 06:50:27 -07:00
|
|
|
}
|
|
|
|
|
};
|
|
|
|
|
|
|
|
|
|
pub const StringIndexAdapter = struct {
|
2025-11-20 23:46:23 +01:00
|
|
|
bytes: *const std.ArrayList(u8),
|
2021-09-03 06:50:27 -07:00
|
|
|
|
2024-02-21 16:21:14 +01:00
|
|
|
pub fn eql(ctx: @This(), a: []const u8, b: u32) bool {
|
|
|
|
|
return mem.eql(u8, a, mem.sliceTo(ctx.bytes.items[b..], 0));
|
2021-09-03 06:50:27 -07:00
|
|
|
}
|
|
|
|
|
|
2024-02-21 16:21:14 +01:00
|
|
|
pub fn hash(_: @This(), adapted_key: []const u8) u64 {
|
|
|
|
|
assert(mem.indexOfScalar(u8, adapted_key, 0) == null);
|
2021-09-03 06:50:27 -07:00
|
|
|
return hashString(adapted_key);
|
|
|
|
|
}
|
|
|
|
|
};
|
|
|
|
|
|
2021-01-30 14:56:36 +02:00
|
|
|
pub const default_max_load_percentage = 80;
|
2020-08-02 23:24:03 +02:00
|
|
|
|
|
|
|
|
/// General purpose hash table.
|
|
|
|
|
/// No order is guaranteed and any modification invalidates live iterators.
|
|
|
|
|
/// It provides fast operations (lookup, insertion, deletion) with quite high
|
2023-04-21 21:21:17 -07:00
|
|
|
/// load factors (up to 80% by default) for low memory usage.
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
/// For a hash map that can be initialized directly that does not store an Allocator
|
|
|
|
|
/// field, see `HashMapUnmanaged`.
|
2020-08-02 23:24:03 +02:00
|
|
|
/// If iterating over the table entries is a strong usecase and needs to be fast,
|
|
|
|
|
/// prefer the alternative `std.ArrayHashMap`.
|
2021-06-03 15:39:26 -05:00
|
|
|
/// 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
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
pub fn HashMap(
|
|
|
|
|
comptime K: type,
|
|
|
|
|
comptime V: type,
|
2021-06-03 15:39:26 -05:00
|
|
|
comptime Context: type,
|
2021-01-30 14:56:36 +02:00
|
|
|
comptime max_load_percentage: u64,
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
) type {
|
2018-11-13 05:08:37 -08:00
|
|
|
return struct {
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
unmanaged: Unmanaged,
|
2021-10-29 00:37:25 +01:00
|
|
|
allocator: Allocator,
|
2021-06-03 15:39:26 -05:00
|
|
|
ctx: Context,
|
2019-10-16 01:29:16 -04:00
|
|
|
|
2021-06-03 15:39:26 -05:00
|
|
|
/// 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
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
pub const Entry = Unmanaged.Entry;
|
2021-06-03 15:39:26 -05:00
|
|
|
/// 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
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
pub const Hash = Unmanaged.Hash;
|
2021-06-03 15:39:26 -05:00
|
|
|
/// The iterator type returned by iterator()
|
2020-08-02 23:24:03 +02:00
|
|
|
pub const Iterator = Unmanaged.Iterator;
|
2021-06-03 15:39:26 -05:00
|
|
|
|
|
|
|
|
pub const KeyIterator = Unmanaged.KeyIterator;
|
|
|
|
|
pub const ValueIterator = Unmanaged.ValueIterator;
|
|
|
|
|
|
|
|
|
|
/// The integer type used to store the size of the map
|
2020-08-02 23:24:03 +02:00
|
|
|
pub const Size = Unmanaged.Size;
|
2021-06-03 15:39:26 -05:00
|
|
|
/// The type returned from getOrPut and variants
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
pub const GetOrPutResult = Unmanaged.GetOrPutResult;
|
2018-08-03 17:22:17 -04:00
|
|
|
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
const Self = @This();
|
|
|
|
|
|
2021-06-03 15:39:26 -05:00
|
|
|
/// Create a managed hash map with an empty context.
|
|
|
|
|
/// If the context is not zero-sized, you must use
|
|
|
|
|
/// initContext(allocator, ctx) instead.
|
2021-10-29 00:37:25 +01:00
|
|
|
pub fn init(allocator: Allocator) Self {
|
2021-06-03 15:39:26 -05:00
|
|
|
if (@sizeOf(Context) != 0) {
|
|
|
|
|
@compileError("Context must be specified! Call initContext(allocator, ctx) instead.");
|
|
|
|
|
}
|
|
|
|
|
return .{
|
2024-09-02 22:32:21 +01:00
|
|
|
.unmanaged = .empty,
|
2021-06-03 15:39:26 -05:00
|
|
|
.allocator = allocator,
|
|
|
|
|
.ctx = undefined, // ctx is zero-sized so this is safe.
|
|
|
|
|
};
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
/// Create a managed hash map with a context
|
2021-10-29 00:37:25 +01:00
|
|
|
pub fn initContext(allocator: Allocator, ctx: Context) Self {
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
return .{
|
2024-09-02 22:32:21 +01:00
|
|
|
.unmanaged = .empty,
|
2017-04-06 05:34:04 -04:00
|
|
|
.allocator = allocator,
|
2021-06-03 15:39:26 -05:00
|
|
|
.ctx = ctx,
|
2017-12-22 00:50:30 -05:00
|
|
|
};
|
2016-05-09 15:07:38 -07:00
|
|
|
}
|
2016-05-08 16:05:41 -07:00
|
|
|
|
2024-03-16 15:45:10 -07:00
|
|
|
/// 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();
|
|
|
|
|
}
|
|
|
|
|
|
2021-06-03 15:39:26 -05:00
|
|
|
/// 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.
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
pub fn deinit(self: *Self) void {
|
|
|
|
|
self.unmanaged.deinit(self.allocator);
|
|
|
|
|
self.* = undefined;
|
2016-05-08 16:05:41 -07:00
|
|
|
}
|
|
|
|
|
|
2021-06-03 15:39:26 -05:00
|
|
|
/// 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.
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
pub fn clearRetainingCapacity(self: *Self) void {
|
|
|
|
|
return self.unmanaged.clearRetainingCapacity();
|
2016-05-08 16:05:41 -07:00
|
|
|
}
|
2016-05-09 15:07:38 -07:00
|
|
|
|
2021-06-03 15:39:26 -05:00
|
|
|
/// 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.
|
2020-07-09 21:51:55 -04:00
|
|
|
pub fn clearAndFree(self: *Self) void {
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
return self.unmanaged.clearAndFree(self.allocator);
|
|
|
|
|
}
|
|
|
|
|
|
2021-06-03 15:39:26 -05:00
|
|
|
/// Return the number of items in the map.
|
2020-09-08 10:41:05 -07:00
|
|
|
pub fn count(self: Self) Size {
|
2020-08-02 23:24:03 +02:00
|
|
|
return self.unmanaged.count();
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
}
|
|
|
|
|
|
2021-06-03 15:39:26 -05:00
|
|
|
/// Create an iterator over the entries in the map.
|
|
|
|
|
/// The iterator is invalidated if the map is modified.
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
pub fn iterator(self: *const Self) Iterator {
|
2020-08-02 23:24:03 +02:00
|
|
|
return self.unmanaged.iterator();
|
2018-05-03 23:54:33 +10:00
|
|
|
}
|
|
|
|
|
|
2021-06-03 15:39:26 -05:00
|
|
|
/// Create an iterator over the keys in the map.
|
|
|
|
|
/// The iterator is invalidated if the map is modified.
|
2024-05-16 18:56:35 -04:00
|
|
|
pub fn keyIterator(self: Self) KeyIterator {
|
2021-06-03 15:39:26 -05:00
|
|
|
return self.unmanaged.keyIterator();
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
/// Create an iterator over the values in the map.
|
|
|
|
|
/// The iterator is invalidated if the map is modified.
|
2024-05-16 18:56:35 -04:00
|
|
|
pub fn valueIterator(self: Self) ValueIterator {
|
2021-06-03 15:39:26 -05:00
|
|
|
return self.unmanaged.valueIterator();
|
|
|
|
|
}
|
|
|
|
|
|
2018-08-03 17:22:17 -04:00
|
|
|
/// If key exists this function cannot fail.
|
Fix simple doc mistakes. (#17624)
* Add missing period in Stack's description
This looks fine in the source, but looks bad when seen on the documentation website.
* Correct documentation for attachSegfaultHandler()
The description for attachSegfaultHandler() looks pretty bad without indicating that the stuff at the end is code
* Added missing 'the's in Queue.put's documentation
* Fixed several errors in Stack's documentation
`push()` and `pop()` were not styled as code
There was no period after `pop()`, which looks bad on the documentation.
* Fix multiple problems in base64.zig
Both "invalid"s in Base64.decoder were not capitalized.
Missing period in documentation of Base64DecoderWithIgnore.calcSizeUpperBound.
* Fix capitalization typos in bit_set.zig
In DynamicBitSetUnmanaged.deinit's and DynamicBitSet.deinit's documentation, "deinitializes" was uncapitalized.
* Fix typos in fifo.zig's documentation
Added a previously missing period to the end of the first line of LinearFifo.writableSlice's documentation.
Added missing periods to both lines of LinearFifo.pump's documentation.
* Fix typos in fmt.bufPrint's documentation
The starts of both lines were not capitalized.
* Fix minor documentation problems in fs/file.zig
Missing periods in documentation for Permissions.setReadOnly, PermissionsWindows.setReadOnly, MetadataUnix.created, MetadataLinux.created, and MetadataWindows.created.
* Fix a glaring typo in enums.zig
* Correct errors in fs.zig
* Fixed documentation problems in hash_map.zig
The added empty line in verify_context's documentation is needed, otherwise autodoc for some reason assumes that the list hasn't been terminated and continues reading off the rest of the documentation as if it were part of the second list item.
* Added lines between consecutive URLs in http.zig
Makes the documentation conform closer to what was intended.
* Fix wrongfully ended sentence in Uri.zig
* Handle wrongly entered comma in valgrind.zig.
* Add missing periods in wasm.zig's documentation
* Fix odd spacing in event/loop.zig
* Add missing period in http/Headers.zig
* Added missing period in io/limited_reader.zig
This isn't in the documentation due to what I guess is a limitation of autodoc, but it's clearly supposed to be. If it was, it would look pretty bad.
* Correct documentation in math/big/int.zig
* Correct formatting in math/big/rational.zig
* Create an actual link to ZIGNOR's paper.
* Fixed grammatical issues in sort/block.zig
This will not show up in the documentation currently.
* Fix typo in hash_map.zig
2023-10-21 17:24:55 -04:00
|
|
|
/// If there is an existing item with `key`, then the result's
|
2021-06-03 15:39:26 -05:00
|
|
|
/// `Entry` pointers point to it, and found_existing is true.
|
2018-08-03 17:22:17 -04:00
|
|
|
/// Otherwise, puts a new item with undefined value, and
|
2021-06-03 15:39:26 -05:00
|
|
|
/// the `Entry` pointers point to it. Caller should then initialize
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
/// the value (but not the key).
|
2022-02-27 22:24:00 +02:00
|
|
|
pub fn getOrPut(self: *Self, key: K) Allocator.Error!GetOrPutResult {
|
2021-06-03 15:39:26 -05:00
|
|
|
return self.unmanaged.getOrPutContext(self.allocator, key, self.ctx);
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
/// If key exists this function cannot fail.
|
Fix simple doc mistakes. (#17624)
* Add missing period in Stack's description
This looks fine in the source, but looks bad when seen on the documentation website.
* Correct documentation for attachSegfaultHandler()
The description for attachSegfaultHandler() looks pretty bad without indicating that the stuff at the end is code
* Added missing 'the's in Queue.put's documentation
* Fixed several errors in Stack's documentation
`push()` and `pop()` were not styled as code
There was no period after `pop()`, which looks bad on the documentation.
* Fix multiple problems in base64.zig
Both "invalid"s in Base64.decoder were not capitalized.
Missing period in documentation of Base64DecoderWithIgnore.calcSizeUpperBound.
* Fix capitalization typos in bit_set.zig
In DynamicBitSetUnmanaged.deinit's and DynamicBitSet.deinit's documentation, "deinitializes" was uncapitalized.
* Fix typos in fifo.zig's documentation
Added a previously missing period to the end of the first line of LinearFifo.writableSlice's documentation.
Added missing periods to both lines of LinearFifo.pump's documentation.
* Fix typos in fmt.bufPrint's documentation
The starts of both lines were not capitalized.
* Fix minor documentation problems in fs/file.zig
Missing periods in documentation for Permissions.setReadOnly, PermissionsWindows.setReadOnly, MetadataUnix.created, MetadataLinux.created, and MetadataWindows.created.
* Fix a glaring typo in enums.zig
* Correct errors in fs.zig
* Fixed documentation problems in hash_map.zig
The added empty line in verify_context's documentation is needed, otherwise autodoc for some reason assumes that the list hasn't been terminated and continues reading off the rest of the documentation as if it were part of the second list item.
* Added lines between consecutive URLs in http.zig
Makes the documentation conform closer to what was intended.
* Fix wrongfully ended sentence in Uri.zig
* Handle wrongly entered comma in valgrind.zig.
* Add missing periods in wasm.zig's documentation
* Fix odd spacing in event/loop.zig
* Add missing period in http/Headers.zig
* Added missing period in io/limited_reader.zig
This isn't in the documentation due to what I guess is a limitation of autodoc, but it's clearly supposed to be. If it was, it would look pretty bad.
* Correct documentation in math/big/int.zig
* Correct formatting in math/big/rational.zig
* Create an actual link to ZIGNOR's paper.
* Fixed grammatical issues in sort/block.zig
This will not show up in the documentation currently.
* Fix typo in hash_map.zig
2023-10-21 17:24:55 -04:00
|
|
|
/// If there is an existing item with `key`, then the result's
|
2021-06-03 15:39:26 -05:00
|
|
|
/// `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.
|
2022-02-27 22:24:00 +02:00
|
|
|
pub fn getOrPutAdapted(self: *Self, key: anytype, ctx: anytype) Allocator.Error!GetOrPutResult {
|
2021-06-03 15:39:26 -05:00
|
|
|
return self.unmanaged.getOrPutContextAdapted(self.allocator, key, ctx, self.ctx);
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
}
|
|
|
|
|
|
Fix simple doc mistakes. (#17624)
* Add missing period in Stack's description
This looks fine in the source, but looks bad when seen on the documentation website.
* Correct documentation for attachSegfaultHandler()
The description for attachSegfaultHandler() looks pretty bad without indicating that the stuff at the end is code
* Added missing 'the's in Queue.put's documentation
* Fixed several errors in Stack's documentation
`push()` and `pop()` were not styled as code
There was no period after `pop()`, which looks bad on the documentation.
* Fix multiple problems in base64.zig
Both "invalid"s in Base64.decoder were not capitalized.
Missing period in documentation of Base64DecoderWithIgnore.calcSizeUpperBound.
* Fix capitalization typos in bit_set.zig
In DynamicBitSetUnmanaged.deinit's and DynamicBitSet.deinit's documentation, "deinitializes" was uncapitalized.
* Fix typos in fifo.zig's documentation
Added a previously missing period to the end of the first line of LinearFifo.writableSlice's documentation.
Added missing periods to both lines of LinearFifo.pump's documentation.
* Fix typos in fmt.bufPrint's documentation
The starts of both lines were not capitalized.
* Fix minor documentation problems in fs/file.zig
Missing periods in documentation for Permissions.setReadOnly, PermissionsWindows.setReadOnly, MetadataUnix.created, MetadataLinux.created, and MetadataWindows.created.
* Fix a glaring typo in enums.zig
* Correct errors in fs.zig
* Fixed documentation problems in hash_map.zig
The added empty line in verify_context's documentation is needed, otherwise autodoc for some reason assumes that the list hasn't been terminated and continues reading off the rest of the documentation as if it were part of the second list item.
* Added lines between consecutive URLs in http.zig
Makes the documentation conform closer to what was intended.
* Fix wrongfully ended sentence in Uri.zig
* Handle wrongly entered comma in valgrind.zig.
* Add missing periods in wasm.zig's documentation
* Fix odd spacing in event/loop.zig
* Add missing period in http/Headers.zig
* Added missing period in io/limited_reader.zig
This isn't in the documentation due to what I guess is a limitation of autodoc, but it's clearly supposed to be. If it was, it would look pretty bad.
* Correct documentation in math/big/int.zig
* Correct formatting in math/big/rational.zig
* Create an actual link to ZIGNOR's paper.
* Fixed grammatical issues in sort/block.zig
This will not show up in the documentation currently.
* Fix typo in hash_map.zig
2023-10-21 17:24:55 -04:00
|
|
|
/// If there is an existing item with `key`, then the result's
|
2021-06-03 15:39:26 -05:00
|
|
|
/// `Entry` pointers point to it, and found_existing is true.
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
/// Otherwise, puts a new item with undefined value, and
|
2021-06-03 15:39:26 -05:00
|
|
|
/// the `Entry` pointers point to it. Caller should then initialize
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
/// 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 {
|
2021-06-03 15:39:26 -05:00
|
|
|
return self.unmanaged.getOrPutAssumeCapacityContext(key, self.ctx);
|
|
|
|
|
}
|
|
|
|
|
|
Fix simple doc mistakes. (#17624)
* Add missing period in Stack's description
This looks fine in the source, but looks bad when seen on the documentation website.
* Correct documentation for attachSegfaultHandler()
The description for attachSegfaultHandler() looks pretty bad without indicating that the stuff at the end is code
* Added missing 'the's in Queue.put's documentation
* Fixed several errors in Stack's documentation
`push()` and `pop()` were not styled as code
There was no period after `pop()`, which looks bad on the documentation.
* Fix multiple problems in base64.zig
Both "invalid"s in Base64.decoder were not capitalized.
Missing period in documentation of Base64DecoderWithIgnore.calcSizeUpperBound.
* Fix capitalization typos in bit_set.zig
In DynamicBitSetUnmanaged.deinit's and DynamicBitSet.deinit's documentation, "deinitializes" was uncapitalized.
* Fix typos in fifo.zig's documentation
Added a previously missing period to the end of the first line of LinearFifo.writableSlice's documentation.
Added missing periods to both lines of LinearFifo.pump's documentation.
* Fix typos in fmt.bufPrint's documentation
The starts of both lines were not capitalized.
* Fix minor documentation problems in fs/file.zig
Missing periods in documentation for Permissions.setReadOnly, PermissionsWindows.setReadOnly, MetadataUnix.created, MetadataLinux.created, and MetadataWindows.created.
* Fix a glaring typo in enums.zig
* Correct errors in fs.zig
* Fixed documentation problems in hash_map.zig
The added empty line in verify_context's documentation is needed, otherwise autodoc for some reason assumes that the list hasn't been terminated and continues reading off the rest of the documentation as if it were part of the second list item.
* Added lines between consecutive URLs in http.zig
Makes the documentation conform closer to what was intended.
* Fix wrongfully ended sentence in Uri.zig
* Handle wrongly entered comma in valgrind.zig.
* Add missing periods in wasm.zig's documentation
* Fix odd spacing in event/loop.zig
* Add missing period in http/Headers.zig
* Added missing period in io/limited_reader.zig
This isn't in the documentation due to what I guess is a limitation of autodoc, but it's clearly supposed to be. If it was, it would look pretty bad.
* Correct documentation in math/big/int.zig
* Correct formatting in math/big/rational.zig
* Create an actual link to ZIGNOR's paper.
* Fixed grammatical issues in sort/block.zig
This will not show up in the documentation currently.
* Fix typo in hash_map.zig
2023-10-21 17:24:55 -04:00
|
|
|
/// If there is an existing item with `key`, then the result's
|
2021-06-03 15:39:26 -05:00
|
|
|
/// `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 {
|
2023-01-02 03:35:56 -05:00
|
|
|
return self.unmanaged.getOrPutAssumeCapacityAdapted(key, ctx);
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
}
|
|
|
|
|
|
2022-02-27 22:24:00 +02:00
|
|
|
pub fn getOrPutValue(self: *Self, key: K, value: V) Allocator.Error!Entry {
|
2021-06-03 15:39:26 -05:00
|
|
|
return self.unmanaged.getOrPutValueContext(self.allocator, key, value, self.ctx);
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
}
|
|
|
|
|
|
|
|
|
|
/// Increases capacity, guaranteeing that insertions up until the
|
|
|
|
|
/// `expected_count` will not cause an allocation, and therefore cannot fail.
|
2022-02-27 22:24:00 +02:00
|
|
|
pub fn ensureTotalCapacity(self: *Self, expected_count: Size) Allocator.Error!void {
|
2021-07-07 00:38:10 -07:00
|
|
|
return self.unmanaged.ensureTotalCapacityContext(self.allocator, expected_count, self.ctx);
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
/// Increases capacity, guaranteeing that insertions up until
|
|
|
|
|
/// `additional_count` **more** items will not cause an allocation, and
|
|
|
|
|
/// therefore cannot fail.
|
2022-02-27 22:24:00 +02:00
|
|
|
pub fn ensureUnusedCapacity(self: *Self, additional_count: Size) Allocator.Error!void {
|
2021-07-07 00:38:10 -07:00
|
|
|
return self.unmanaged.ensureUnusedCapacityContext(self.allocator, additional_count, self.ctx);
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
}
|
|
|
|
|
|
|
|
|
|
/// Returns the number of total elements which may be present before it is
|
|
|
|
|
/// no longer guaranteed that no allocations will be performed.
|
2024-05-16 18:56:35 -04:00
|
|
|
pub fn capacity(self: Self) Size {
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
return self.unmanaged.capacity();
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
/// Clobbers any existing data. To detect if a put would clobber
|
|
|
|
|
/// existing data, see `getOrPut`.
|
2022-02-27 22:24:00 +02:00
|
|
|
pub fn put(self: *Self, key: K, value: V) Allocator.Error!void {
|
2021-06-03 15:39:26 -05:00
|
|
|
return self.unmanaged.putContext(self.allocator, key, value, self.ctx);
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
}
|
|
|
|
|
|
|
|
|
|
/// Inserts a key-value pair into the hash map, asserting that no previous
|
|
|
|
|
/// entry with the same key is already present
|
2022-02-27 22:24:00 +02:00
|
|
|
pub fn putNoClobber(self: *Self, key: K, value: V) Allocator.Error!void {
|
2021-06-03 15:39:26 -05:00
|
|
|
return self.unmanaged.putNoClobberContext(self.allocator, key, value, self.ctx);
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
}
|
|
|
|
|
|
|
|
|
|
/// 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 {
|
2021-06-03 15:39:26 -05:00
|
|
|
return self.unmanaged.putAssumeCapacityContext(key, value, self.ctx);
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
}
|
|
|
|
|
|
|
|
|
|
/// 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 {
|
2021-06-03 15:39:26 -05:00
|
|
|
return self.unmanaged.putAssumeCapacityNoClobberContext(key, value, self.ctx);
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
}
|
|
|
|
|
|
|
|
|
|
/// Inserts a new `Entry` into the hash map, returning the previous one, if any.
|
2022-02-27 22:24:00 +02:00
|
|
|
pub fn fetchPut(self: *Self, key: K, value: V) Allocator.Error!?KV {
|
2021-06-03 15:39:26 -05:00
|
|
|
return self.unmanaged.fetchPutContext(self.allocator, key, value, self.ctx);
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
}
|
|
|
|
|
|
|
|
|
|
/// Inserts a new `Entry` into the hash map, returning the previous one, if any.
|
Fix simple doc mistakes. (#17624)
* Add missing period in Stack's description
This looks fine in the source, but looks bad when seen on the documentation website.
* Correct documentation for attachSegfaultHandler()
The description for attachSegfaultHandler() looks pretty bad without indicating that the stuff at the end is code
* Added missing 'the's in Queue.put's documentation
* Fixed several errors in Stack's documentation
`push()` and `pop()` were not styled as code
There was no period after `pop()`, which looks bad on the documentation.
* Fix multiple problems in base64.zig
Both "invalid"s in Base64.decoder were not capitalized.
Missing period in documentation of Base64DecoderWithIgnore.calcSizeUpperBound.
* Fix capitalization typos in bit_set.zig
In DynamicBitSetUnmanaged.deinit's and DynamicBitSet.deinit's documentation, "deinitializes" was uncapitalized.
* Fix typos in fifo.zig's documentation
Added a previously missing period to the end of the first line of LinearFifo.writableSlice's documentation.
Added missing periods to both lines of LinearFifo.pump's documentation.
* Fix typos in fmt.bufPrint's documentation
The starts of both lines were not capitalized.
* Fix minor documentation problems in fs/file.zig
Missing periods in documentation for Permissions.setReadOnly, PermissionsWindows.setReadOnly, MetadataUnix.created, MetadataLinux.created, and MetadataWindows.created.
* Fix a glaring typo in enums.zig
* Correct errors in fs.zig
* Fixed documentation problems in hash_map.zig
The added empty line in verify_context's documentation is needed, otherwise autodoc for some reason assumes that the list hasn't been terminated and continues reading off the rest of the documentation as if it were part of the second list item.
* Added lines between consecutive URLs in http.zig
Makes the documentation conform closer to what was intended.
* Fix wrongfully ended sentence in Uri.zig
* Handle wrongly entered comma in valgrind.zig.
* Add missing periods in wasm.zig's documentation
* Fix odd spacing in event/loop.zig
* Add missing period in http/Headers.zig
* Added missing period in io/limited_reader.zig
This isn't in the documentation due to what I guess is a limitation of autodoc, but it's clearly supposed to be. If it was, it would look pretty bad.
* Correct documentation in math/big/int.zig
* Correct formatting in math/big/rational.zig
* Create an actual link to ZIGNOR's paper.
* Fixed grammatical issues in sort/block.zig
This will not show up in the documentation currently.
* Fix typo in hash_map.zig
2023-10-21 17:24:55 -04:00
|
|
|
/// If insertion happens, asserts there is enough capacity without allocating.
|
2021-06-03 15:39:26 -05:00
|
|
|
pub fn fetchPutAssumeCapacity(self: *Self, key: K, value: V) ?KV {
|
|
|
|
|
return self.unmanaged.fetchPutAssumeCapacityContext(key, value, self.ctx);
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
}
|
|
|
|
|
|
2021-06-03 15:39:26 -05:00
|
|
|
/// 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
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
pub fn get(self: Self, key: K) ?V {
|
2021-06-03 15:39:26 -05:00
|
|
|
return self.unmanaged.getContext(key, self.ctx);
|
|
|
|
|
}
|
2021-06-03 17:58:06 -05:00
|
|
|
pub fn getAdapted(self: Self, key: anytype, ctx: anytype) ?V {
|
2021-06-03 15:39:26 -05:00
|
|
|
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 {
|
2021-08-05 23:17:29 -07:00
|
|
|
return self.unmanaged.getPtrAdapted(key, ctx);
|
2021-06-03 15:39:26 -05:00
|
|
|
}
|
|
|
|
|
|
2021-08-30 21:32:34 -07:00
|
|
|
/// Finds the actual key associated with an adapted key in the map
|
|
|
|
|
pub fn getKey(self: Self, key: K) ?K {
|
|
|
|
|
return self.unmanaged.getKeyContext(key, self.ctx);
|
|
|
|
|
}
|
|
|
|
|
pub fn getKeyAdapted(self: Self, key: anytype, ctx: anytype) ?K {
|
|
|
|
|
return self.unmanaged.getKeyAdapted(key, ctx);
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
pub fn getKeyPtr(self: Self, key: K) ?*K {
|
|
|
|
|
return self.unmanaged.getKeyPtrContext(key, self.ctx);
|
|
|
|
|
}
|
|
|
|
|
pub fn getKeyPtrAdapted(self: Self, key: anytype, ctx: anytype) ?*K {
|
|
|
|
|
return self.unmanaged.getKeyPtrAdapted(key, ctx);
|
|
|
|
|
}
|
|
|
|
|
|
2021-06-03 15:39:26 -05:00
|
|
|
/// 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);
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
}
|
|
|
|
|
|
2021-06-03 15:39:26 -05:00
|
|
|
pub fn getEntryAdapted(self: Self, key: anytype, ctx: anytype) ?Entry {
|
|
|
|
|
return self.unmanaged.getEntryAdapted(key, ctx);
|
2020-08-02 23:24:03 +02:00
|
|
|
}
|
|
|
|
|
|
2021-06-03 15:39:26 -05:00
|
|
|
/// Check if the map contains a key
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
pub fn contains(self: Self, key: K) bool {
|
2021-06-03 15:39:26 -05:00
|
|
|
return self.unmanaged.containsContext(key, self.ctx);
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
pub fn containsAdapted(self: Self, key: anytype, ctx: anytype) bool {
|
|
|
|
|
return self.unmanaged.containsAdapted(key, ctx);
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
}
|
|
|
|
|
|
|
|
|
|
/// If there is an `Entry` with a matching key, it is deleted from
|
2022-02-18 14:02:01 +01:00
|
|
|
/// the hash map, and this function returns true. Otherwise this
|
|
|
|
|
/// function returns false.
|
2025-02-03 21:20:52 -08:00
|
|
|
///
|
|
|
|
|
/// TODO: answer the question in these doc comments, does this
|
|
|
|
|
/// increase the unused capacity by one?
|
2021-06-03 15:39:26 -05:00
|
|
|
pub fn remove(self: *Self, key: K) bool {
|
|
|
|
|
return self.unmanaged.removeContext(key, self.ctx);
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
}
|
|
|
|
|
|
2025-02-03 21:20:52 -08:00
|
|
|
/// TODO: answer the question in these doc comments, does this
|
|
|
|
|
/// increase the unused capacity by one?
|
2021-06-03 15:39:26 -05:00
|
|
|
pub fn removeAdapted(self: *Self, key: anytype, ctx: anytype) bool {
|
|
|
|
|
return self.unmanaged.removeAdapted(key, ctx);
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
}
|
|
|
|
|
|
2023-07-19 18:17:03 +01:00
|
|
|
/// Delete the entry with key pointed to by key_ptr from the hash map.
|
|
|
|
|
/// key_ptr is assumed to be a valid pointer to a key that is present
|
2021-11-15 12:54:14 +00:00
|
|
|
/// in the hash map.
|
2025-02-03 21:20:52 -08:00
|
|
|
///
|
|
|
|
|
/// TODO: answer the question in these doc comments, does this
|
|
|
|
|
/// increase the unused capacity by one?
|
2023-07-19 18:17:03 +01:00
|
|
|
pub fn removeByPtr(self: *Self, key_ptr: *K) void {
|
|
|
|
|
self.unmanaged.removeByPtr(key_ptr);
|
2021-11-15 12:54:14 +00:00
|
|
|
}
|
|
|
|
|
|
2021-06-03 15:39:26 -05:00
|
|
|
/// Creates a copy of this map, using the same allocator
|
2022-02-27 22:24:00 +02:00
|
|
|
pub fn clone(self: Self) Allocator.Error!Self {
|
2021-06-03 15:39:26 -05:00
|
|
|
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
|
2022-02-27 22:24:00 +02:00
|
|
|
pub fn cloneWithAllocator(self: Self, new_allocator: Allocator) Allocator.Error!Self {
|
2021-06-03 15:39:26 -05:00
|
|
|
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
|
2022-02-27 22:24:00 +02:00
|
|
|
pub fn cloneWithContext(self: Self, new_ctx: anytype) Allocator.Error!HashMap(K, V, @TypeOf(new_ctx), max_load_percentage) {
|
2021-06-03 15:39:26 -05:00
|
|
|
var other = try self.unmanaged.cloneContext(self.allocator, new_ctx);
|
|
|
|
|
return other.promoteContext(self.allocator, new_ctx);
|
|
|
|
|
}
|
|
|
|
|
|
2021-08-28 15:34:17 -07:00
|
|
|
/// Creates a copy of this map, using a specified allocator and context.
|
|
|
|
|
pub fn cloneWithAllocatorAndContext(
|
|
|
|
|
self: Self,
|
2021-10-29 00:37:25 +01:00
|
|
|
new_allocator: Allocator,
|
2021-08-28 15:34:17 -07:00
|
|
|
new_ctx: anytype,
|
2022-02-27 22:24:00 +02:00
|
|
|
) Allocator.Error!HashMap(K, V, @TypeOf(new_ctx), max_load_percentage) {
|
2021-06-03 15:39:26 -05:00
|
|
|
var other = try self.unmanaged.cloneContext(new_allocator, new_ctx);
|
|
|
|
|
return other.promoteContext(new_allocator, new_ctx);
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
}
|
2022-12-02 23:05:12 -07:00
|
|
|
|
|
|
|
|
/// 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 {
|
2024-03-16 15:45:10 -07:00
|
|
|
self.unmanaged.pointer_stability.assertUnlocked();
|
2022-12-02 23:05:12 -07:00
|
|
|
const result = self.*;
|
2024-09-02 22:32:21 +01:00
|
|
|
self.unmanaged = .empty;
|
2022-12-02 23:05:12 -07:00
|
|
|
return result;
|
|
|
|
|
}
|
2024-08-08 11:59:22 -07:00
|
|
|
|
|
|
|
|
/// Rehash the map, in-place.
|
|
|
|
|
///
|
|
|
|
|
/// Over time, due to the current tombstone-based implementation, a
|
|
|
|
|
/// HashMap could become fragmented due to the buildup of tombstone
|
|
|
|
|
/// entries that causes a performance degradation due to excessive
|
|
|
|
|
/// probing. The kind of pattern that might cause this is a long-lived
|
|
|
|
|
/// HashMap with repeated inserts and deletes.
|
|
|
|
|
///
|
|
|
|
|
/// After this function is called, there will be no tombstones in
|
|
|
|
|
/// the HashMap, each of the entries is rehashed and any existing
|
|
|
|
|
/// key/value pointers into the HashMap are invalidated.
|
|
|
|
|
pub fn rehash(self: *Self) void {
|
|
|
|
|
self.unmanaged.rehash(self.ctx);
|
|
|
|
|
}
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
};
|
|
|
|
|
}
|
|
|
|
|
|
2020-08-02 23:24:03 +02:00
|
|
|
/// A HashMap based on open addressing and linear probing.
|
Fix simple doc mistakes. (#17624)
* Add missing period in Stack's description
This looks fine in the source, but looks bad when seen on the documentation website.
* Correct documentation for attachSegfaultHandler()
The description for attachSegfaultHandler() looks pretty bad without indicating that the stuff at the end is code
* Added missing 'the's in Queue.put's documentation
* Fixed several errors in Stack's documentation
`push()` and `pop()` were not styled as code
There was no period after `pop()`, which looks bad on the documentation.
* Fix multiple problems in base64.zig
Both "invalid"s in Base64.decoder were not capitalized.
Missing period in documentation of Base64DecoderWithIgnore.calcSizeUpperBound.
* Fix capitalization typos in bit_set.zig
In DynamicBitSetUnmanaged.deinit's and DynamicBitSet.deinit's documentation, "deinitializes" was uncapitalized.
* Fix typos in fifo.zig's documentation
Added a previously missing period to the end of the first line of LinearFifo.writableSlice's documentation.
Added missing periods to both lines of LinearFifo.pump's documentation.
* Fix typos in fmt.bufPrint's documentation
The starts of both lines were not capitalized.
* Fix minor documentation problems in fs/file.zig
Missing periods in documentation for Permissions.setReadOnly, PermissionsWindows.setReadOnly, MetadataUnix.created, MetadataLinux.created, and MetadataWindows.created.
* Fix a glaring typo in enums.zig
* Correct errors in fs.zig
* Fixed documentation problems in hash_map.zig
The added empty line in verify_context's documentation is needed, otherwise autodoc for some reason assumes that the list hasn't been terminated and continues reading off the rest of the documentation as if it were part of the second list item.
* Added lines between consecutive URLs in http.zig
Makes the documentation conform closer to what was intended.
* Fix wrongfully ended sentence in Uri.zig
* Handle wrongly entered comma in valgrind.zig.
* Add missing periods in wasm.zig's documentation
* Fix odd spacing in event/loop.zig
* Add missing period in http/Headers.zig
* Added missing period in io/limited_reader.zig
This isn't in the documentation due to what I guess is a limitation of autodoc, but it's clearly supposed to be. If it was, it would look pretty bad.
* Correct documentation in math/big/int.zig
* Correct formatting in math/big/rational.zig
* Create an actual link to ZIGNOR's paper.
* Fixed grammatical issues in sort/block.zig
This will not show up in the documentation currently.
* Fix typo in hash_map.zig
2023-10-21 17:24:55 -04:00
|
|
|
/// A lookup or modification typically incurs only 2 cache misses.
|
2020-08-02 23:24:03 +02:00
|
|
|
/// No order is guaranteed and any modification invalidates live iterators.
|
|
|
|
|
/// It achieves good performance with quite high load factors (by default,
|
|
|
|
|
/// grow is triggered at 80% full) and only one byte of overhead per element.
|
|
|
|
|
/// The struct itself is only 16 bytes for a small footprint. This comes at
|
2023-04-30 18:02:08 +01:00
|
|
|
/// the price of handling size with u32, which should be reasonable enough
|
2020-08-02 23:24:03 +02:00
|
|
|
/// for almost all uses.
|
|
|
|
|
/// Deletions are achieved with tombstones.
|
2024-08-31 02:50:11 +01:00
|
|
|
///
|
|
|
|
|
/// Default initialization of this struct is deprecated; use `.empty` instead.
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
pub fn HashMapUnmanaged(
|
|
|
|
|
comptime K: type,
|
|
|
|
|
comptime V: type,
|
2021-06-03 15:39:26 -05:00
|
|
|
comptime Context: type,
|
2021-01-30 14:56:36 +02:00
|
|
|
comptime max_load_percentage: u64,
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
) type {
|
2021-06-03 15:39:26 -05:00
|
|
|
if (max_load_percentage <= 0 or max_load_percentage >= 100)
|
|
|
|
|
@compileError("max_load_percentage must be between 0 and 100.");
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
return struct {
|
2020-08-02 23:24:03 +02:00
|
|
|
const Self = @This();
|
|
|
|
|
|
|
|
|
|
// This is actually a midway pointer to the single buffer containing
|
|
|
|
|
// a `Header` field, the `Metadata`s and `Entry`s.
|
|
|
|
|
// At `-@sizeOf(Header)` is the Header field.
|
|
|
|
|
// At `sizeOf(Metadata) * capacity + offset`, which is pointed to by
|
|
|
|
|
// self.header().entries, is the array of entries.
|
|
|
|
|
// This means that the hashmap only holds one live allocation, to
|
|
|
|
|
// reduce memory fragmentation and struct size.
|
|
|
|
|
/// Pointer to the metadata.
|
|
|
|
|
metadata: ?[*]Metadata = null,
|
|
|
|
|
|
|
|
|
|
/// Current number of elements in the hashmap.
|
|
|
|
|
size: Size = 0,
|
|
|
|
|
|
|
|
|
|
// Having a countdown to grow reduces the number of instructions to
|
|
|
|
|
// execute when determining if the hashmap has enough capacity already.
|
|
|
|
|
/// Number of available slots before a grow is needed to satisfy the
|
2021-01-30 14:56:36 +02:00
|
|
|
/// `max_load_percentage`.
|
2020-08-02 23:24:03 +02:00
|
|
|
available: Size = 0,
|
|
|
|
|
|
2024-03-16 15:45:10 -07:00
|
|
|
/// Used to detect memory safety violations.
|
|
|
|
|
pointer_stability: std.debug.SafetyLock = .{},
|
|
|
|
|
|
2020-08-02 23:24:03 +02:00
|
|
|
// This is purely empirical and not a /very smart magic constant™/.
|
|
|
|
|
/// Capacity of the first grow when bootstrapping the hashmap.
|
2021-01-30 14:56:36 +02:00
|
|
|
const minimal_capacity = 8;
|
2020-08-02 23:24:03 +02:00
|
|
|
|
2024-08-31 02:50:11 +01:00
|
|
|
/// A map containing no keys or values.
|
|
|
|
|
pub const empty: Self = .{
|
|
|
|
|
.metadata = null,
|
|
|
|
|
.size = 0,
|
|
|
|
|
.available = 0,
|
|
|
|
|
};
|
|
|
|
|
|
2020-08-02 23:24:03 +02:00
|
|
|
// This hashmap is specially designed for sizes that fit in a u32.
|
2021-06-03 15:39:26 -05:00
|
|
|
pub const Size = u32;
|
2020-08-02 23:24:03 +02:00
|
|
|
|
|
|
|
|
// u64 hashes guarantee us that the fingerprint bits will never be used
|
|
|
|
|
// to compute the index of a slot, maximizing the use of entropy.
|
2021-06-03 15:39:26 -05:00
|
|
|
pub const Hash = u64;
|
2020-08-02 23:24:03 +02:00
|
|
|
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
pub const Entry = struct {
|
2021-06-03 15:39:26 -05:00
|
|
|
key_ptr: *K,
|
|
|
|
|
value_ptr: *V,
|
|
|
|
|
};
|
|
|
|
|
|
|
|
|
|
pub const KV = struct {
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
key: K,
|
|
|
|
|
value: V,
|
|
|
|
|
};
|
|
|
|
|
|
2022-02-28 10:20:29 +02:00
|
|
|
const Header = struct {
|
2021-06-03 15:39:26 -05:00
|
|
|
values: [*]V,
|
|
|
|
|
keys: [*]K,
|
2020-08-02 23:24:03 +02:00
|
|
|
capacity: Size,
|
|
|
|
|
};
|
|
|
|
|
|
|
|
|
|
/// Metadata for a slot. It can be in three states: empty, used or
|
|
|
|
|
/// tombstone. Tombstones indicate that an entry was previously used,
|
|
|
|
|
/// they are a simple way to handle removal.
|
2021-05-12 19:39:36 +02:00
|
|
|
/// To this state, we add 7 bits from the slot's key hash. These are
|
2020-08-02 23:24:03 +02:00
|
|
|
/// used as a fast way to disambiguate between entries without
|
|
|
|
|
/// having to use the equality function. If two fingerprints are
|
|
|
|
|
/// different, we know that we don't have to compare the keys at all.
|
2021-05-12 19:39:36 +02:00
|
|
|
/// The 7 bits are the highest ones from a 64 bit hash. This way, not
|
2020-08-02 23:24:03 +02:00
|
|
|
/// only we use the `log2(capacity)` lowest bits from the hash to determine
|
2021-05-12 19:39:36 +02:00
|
|
|
/// a slot index, but we use 7 more bits to quickly resolve collisions
|
|
|
|
|
/// when multiple elements with different hashes end up wanting to be in the same slot.
|
2020-08-02 23:24:03 +02:00
|
|
|
/// Not using the equality function means we don't have to read into
|
2021-05-12 19:39:36 +02:00
|
|
|
/// the entries array, likely avoiding a cache miss and a potentially
|
|
|
|
|
/// costly function call.
|
2020-08-02 23:24:03 +02:00
|
|
|
const Metadata = packed struct {
|
2021-05-12 19:39:36 +02:00
|
|
|
const FingerPrint = u7;
|
2020-08-02 23:24:03 +02:00
|
|
|
|
2021-05-12 19:39:36 +02:00
|
|
|
const free: FingerPrint = 0;
|
|
|
|
|
const tombstone: FingerPrint = 1;
|
|
|
|
|
|
|
|
|
|
fingerprint: FingerPrint = free,
|
2020-08-02 23:24:03 +02:00
|
|
|
used: u1 = 0,
|
|
|
|
|
|
2023-06-22 18:46:56 +01:00
|
|
|
const slot_free = @as(u8, @bitCast(Metadata{ .fingerprint = free }));
|
|
|
|
|
const slot_tombstone = @as(u8, @bitCast(Metadata{ .fingerprint = tombstone }));
|
2022-01-10 20:54:45 -08:00
|
|
|
|
2020-08-02 23:24:03 +02:00
|
|
|
pub fn isUsed(self: Metadata) bool {
|
|
|
|
|
return self.used == 1;
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
pub fn isTombstone(self: Metadata) bool {
|
2023-06-22 18:46:56 +01:00
|
|
|
return @as(u8, @bitCast(self)) == slot_tombstone;
|
2022-01-10 20:54:45 -08:00
|
|
|
}
|
|
|
|
|
|
|
|
|
|
pub fn isFree(self: Metadata) bool {
|
2023-06-22 18:46:56 +01:00
|
|
|
return @as(u8, @bitCast(self)) == slot_free;
|
2020-08-02 23:24:03 +02:00
|
|
|
}
|
|
|
|
|
|
|
|
|
|
pub fn takeFingerprint(hash: Hash) FingerPrint {
|
2024-08-28 02:35:53 +01:00
|
|
|
const hash_bits = @typeInfo(Hash).int.bits;
|
|
|
|
|
const fp_bits = @typeInfo(FingerPrint).int.bits;
|
2023-06-22 18:46:56 +01:00
|
|
|
return @as(FingerPrint, @truncate(hash >> (hash_bits - fp_bits)));
|
2020-08-02 23:24:03 +02:00
|
|
|
}
|
|
|
|
|
|
|
|
|
|
pub fn fill(self: *Metadata, fp: FingerPrint) void {
|
|
|
|
|
self.used = 1;
|
|
|
|
|
self.fingerprint = fp;
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
pub fn remove(self: *Metadata) void {
|
|
|
|
|
self.used = 0;
|
2021-05-12 19:39:36 +02:00
|
|
|
self.fingerprint = tombstone;
|
2020-08-02 23:24:03 +02:00
|
|
|
}
|
|
|
|
|
};
|
|
|
|
|
|
|
|
|
|
comptime {
|
|
|
|
|
assert(@sizeOf(Metadata) == 1);
|
|
|
|
|
assert(@alignOf(Metadata) == 1);
|
|
|
|
|
}
|
|
|
|
|
|
2021-06-03 15:39:26 -05:00
|
|
|
pub const Iterator = struct {
|
2020-08-02 23:24:03 +02:00
|
|
|
hm: *const Self,
|
|
|
|
|
index: Size = 0,
|
|
|
|
|
|
2021-06-03 15:39:26 -05:00
|
|
|
pub fn next(it: *Iterator) ?Entry {
|
2020-08-02 23:24:03 +02:00
|
|
|
assert(it.index <= it.hm.capacity());
|
|
|
|
|
if (it.hm.size == 0) return null;
|
|
|
|
|
|
|
|
|
|
const cap = it.hm.capacity();
|
|
|
|
|
const end = it.hm.metadata.? + cap;
|
|
|
|
|
var metadata = it.hm.metadata.? + it.index;
|
|
|
|
|
|
|
|
|
|
while (metadata != end) : ({
|
|
|
|
|
metadata += 1;
|
|
|
|
|
it.index += 1;
|
|
|
|
|
}) {
|
|
|
|
|
if (metadata[0].isUsed()) {
|
2021-06-03 15:39:26 -05:00
|
|
|
const key = &it.hm.keys()[it.index];
|
|
|
|
|
const value = &it.hm.values()[it.index];
|
2020-08-02 23:24:03 +02:00
|
|
|
it.index += 1;
|
2021-06-03 15:39:26 -05:00
|
|
|
return Entry{ .key_ptr = key, .value_ptr = value };
|
2020-08-02 23:24:03 +02:00
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
return null;
|
|
|
|
|
}
|
|
|
|
|
};
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
|
2021-06-03 15:39:26 -05:00
|
|
|
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;
|
|
|
|
|
}
|
|
|
|
|
};
|
|
|
|
|
}
|
|
|
|
|
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
pub const GetOrPutResult = struct {
|
2021-06-03 15:39:26 -05:00
|
|
|
key_ptr: *K,
|
|
|
|
|
value_ptr: *V,
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
found_existing: bool,
|
|
|
|
|
};
|
|
|
|
|
|
2021-06-03 15:39:26 -05:00
|
|
|
pub const Managed = HashMap(K, V, Context, max_load_percentage);
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
|
2021-10-29 00:37:25 +01:00
|
|
|
pub fn promote(self: Self, allocator: Allocator) Managed {
|
2021-06-03 15:39:26 -05:00
|
|
|
if (@sizeOf(Context) != 0)
|
2021-06-10 20:13:43 -07:00
|
|
|
@compileError("Cannot infer context " ++ @typeName(Context) ++ ", call promoteContext instead.");
|
2021-06-03 15:39:26 -05:00
|
|
|
return promoteContext(self, allocator, undefined);
|
|
|
|
|
}
|
|
|
|
|
|
2021-10-29 00:37:25 +01:00
|
|
|
pub fn promoteContext(self: Self, allocator: Allocator, ctx: Context) Managed {
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
return .{
|
|
|
|
|
.unmanaged = self,
|
|
|
|
|
.allocator = allocator,
|
2021-06-03 15:39:26 -05:00
|
|
|
.ctx = ctx,
|
2018-08-03 17:22:17 -04:00
|
|
|
};
|
|
|
|
|
}
|
|
|
|
|
|
2024-03-16 15:45:10 -07:00
|
|
|
/// 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.pointer_stability.lock();
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
/// Undoes a call to `lockPointers`.
|
|
|
|
|
pub fn unlockPointers(self: *Self) void {
|
|
|
|
|
self.pointer_stability.unlock();
|
|
|
|
|
}
|
|
|
|
|
|
2020-08-02 23:24:03 +02:00
|
|
|
fn isUnderMaxLoadPercentage(size: Size, cap: Size) bool {
|
2021-01-30 14:56:36 +02:00
|
|
|
return size * 100 < max_load_percentage * cap;
|
2020-08-02 23:24:03 +02:00
|
|
|
}
|
|
|
|
|
|
2021-10-29 00:37:25 +01:00
|
|
|
pub fn deinit(self: *Self, allocator: Allocator) void {
|
2024-03-16 15:45:10 -07:00
|
|
|
self.pointer_stability.assertUnlocked();
|
2020-08-02 23:24:03 +02:00
|
|
|
self.deallocate(allocator);
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
self.* = undefined;
|
|
|
|
|
}
|
2018-11-29 09:10:15 +01:00
|
|
|
|
2020-08-02 23:24:03 +02:00
|
|
|
fn capacityForSize(size: Size) Size {
|
2024-02-24 00:56:00 -05:00
|
|
|
var new_cap: u32 = @intCast((@as(u64, size) * 100) / max_load_percentage + 1);
|
2020-08-02 23:24:03 +02:00
|
|
|
new_cap = math.ceilPowerOfTwo(u32, new_cap) catch unreachable;
|
|
|
|
|
return new_cap;
|
2019-05-02 17:01:30 -07:00
|
|
|
}
|
|
|
|
|
|
2022-02-27 22:24:00 +02:00
|
|
|
pub fn ensureTotalCapacity(self: *Self, allocator: Allocator, new_size: Size) Allocator.Error!void {
|
2021-06-03 15:39:26 -05:00
|
|
|
if (@sizeOf(Context) != 0)
|
2021-07-07 00:38:10 -07:00
|
|
|
@compileError("Cannot infer context " ++ @typeName(Context) ++ ", call ensureTotalCapacityContext instead.");
|
|
|
|
|
return ensureTotalCapacityContext(self, allocator, new_size, undefined);
|
2021-06-03 15:39:26 -05:00
|
|
|
}
|
2022-02-27 22:24:00 +02:00
|
|
|
pub fn ensureTotalCapacityContext(self: *Self, allocator: Allocator, new_size: Size, ctx: Context) Allocator.Error!void {
|
2024-03-16 15:45:10 -07:00
|
|
|
self.pointer_stability.lock();
|
|
|
|
|
defer self.pointer_stability.unlock();
|
2020-08-02 23:24:03 +02:00
|
|
|
if (new_size > self.size)
|
2021-06-03 15:39:26 -05:00
|
|
|
try self.growIfNeeded(allocator, new_size - self.size, ctx);
|
2020-08-02 23:24:03 +02:00
|
|
|
}
|
2019-05-02 17:01:30 -07:00
|
|
|
|
2022-02-27 22:24:00 +02:00
|
|
|
pub fn ensureUnusedCapacity(self: *Self, allocator: Allocator, additional_size: Size) Allocator.Error!void {
|
2022-04-20 17:16:32 -07:00
|
|
|
if (@sizeOf(Context) != 0)
|
|
|
|
|
@compileError("Cannot infer context " ++ @typeName(Context) ++ ", call ensureUnusedCapacityContext instead.");
|
2021-07-07 00:38:10 -07:00
|
|
|
return ensureUnusedCapacityContext(self, allocator, additional_size, undefined);
|
|
|
|
|
}
|
2022-02-27 22:24:00 +02:00
|
|
|
pub fn ensureUnusedCapacityContext(self: *Self, allocator: Allocator, additional_size: Size, ctx: Context) Allocator.Error!void {
|
2021-07-12 18:32:02 +02:00
|
|
|
return ensureTotalCapacityContext(self, allocator, self.count() + additional_size, ctx);
|
2021-07-07 00:38:10 -07:00
|
|
|
}
|
|
|
|
|
|
2020-08-02 23:24:03 +02:00
|
|
|
pub fn clearRetainingCapacity(self: *Self) void {
|
2024-03-16 15:45:10 -07:00
|
|
|
self.pointer_stability.lock();
|
|
|
|
|
defer self.pointer_stability.unlock();
|
2020-08-02 23:24:03 +02:00
|
|
|
if (self.metadata) |_| {
|
|
|
|
|
self.initMetadatas();
|
|
|
|
|
self.size = 0;
|
2024-03-16 15:45:10 -07:00
|
|
|
self.available = @truncate((self.capacity() * max_load_percentage) / 100);
|
2017-01-05 03:40:04 -05:00
|
|
|
}
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
}
|
2019-05-02 17:01:30 -07:00
|
|
|
|
2021-10-29 00:37:25 +01:00
|
|
|
pub fn clearAndFree(self: *Self, allocator: Allocator) void {
|
2024-03-16 15:45:10 -07:00
|
|
|
self.pointer_stability.lock();
|
|
|
|
|
defer self.pointer_stability.unlock();
|
2020-08-02 23:24:03 +02:00
|
|
|
self.deallocate(allocator);
|
|
|
|
|
self.size = 0;
|
|
|
|
|
self.available = 0;
|
|
|
|
|
}
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
|
2024-05-16 18:56:35 -04:00
|
|
|
pub fn count(self: Self) Size {
|
2020-08-02 23:24:03 +02:00
|
|
|
return self.size;
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
}
|
|
|
|
|
|
2024-05-16 18:56:35 -04:00
|
|
|
fn header(self: Self) *Header {
|
2023-06-22 18:46:56 +01:00
|
|
|
return @ptrCast(@as([*]Header, @ptrCast(@alignCast(self.metadata.?))) - 1);
|
2018-08-03 17:22:17 -04:00
|
|
|
}
|
2016-05-08 16:05:41 -07:00
|
|
|
|
2024-05-16 18:56:35 -04:00
|
|
|
fn keys(self: Self) [*]K {
|
2021-06-03 15:39:26 -05:00
|
|
|
return self.header().keys;
|
|
|
|
|
}
|
|
|
|
|
|
2024-05-16 18:56:35 -04:00
|
|
|
fn values(self: Self) [*]V {
|
2021-06-03 15:39:26 -05:00
|
|
|
return self.header().values;
|
2019-05-02 17:42:38 -07:00
|
|
|
}
|
|
|
|
|
|
2024-05-16 18:56:35 -04:00
|
|
|
pub fn capacity(self: Self) Size {
|
2020-08-02 23:24:03 +02:00
|
|
|
if (self.metadata == null) return 0;
|
|
|
|
|
|
|
|
|
|
return self.header().capacity;
|
2019-06-12 23:39:53 -04:00
|
|
|
}
|
|
|
|
|
|
2020-08-02 23:24:03 +02:00
|
|
|
pub fn iterator(self: *const Self) Iterator {
|
|
|
|
|
return .{ .hm = self };
|
|
|
|
|
}
|
|
|
|
|
|
2024-05-16 18:56:35 -04:00
|
|
|
pub fn keyIterator(self: Self) KeyIterator {
|
2021-06-03 15:39:26 -05:00
|
|
|
if (self.metadata) |metadata| {
|
|
|
|
|
return .{
|
|
|
|
|
.len = self.capacity(),
|
|
|
|
|
.metadata = metadata,
|
|
|
|
|
.items = self.keys(),
|
|
|
|
|
};
|
|
|
|
|
} else {
|
|
|
|
|
return .{
|
|
|
|
|
.len = 0,
|
|
|
|
|
.metadata = undefined,
|
|
|
|
|
.items = undefined,
|
|
|
|
|
};
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
2024-05-16 18:56:35 -04:00
|
|
|
pub fn valueIterator(self: Self) ValueIterator {
|
2021-06-03 15:39:26 -05:00
|
|
|
if (self.metadata) |metadata| {
|
|
|
|
|
return .{
|
|
|
|
|
.len = self.capacity(),
|
|
|
|
|
.metadata = metadata,
|
|
|
|
|
.items = self.values(),
|
|
|
|
|
};
|
|
|
|
|
} else {
|
|
|
|
|
return .{
|
|
|
|
|
.len = 0,
|
|
|
|
|
.metadata = undefined,
|
|
|
|
|
.items = undefined,
|
|
|
|
|
};
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
2020-08-02 23:24:03 +02:00
|
|
|
/// Insert an entry in the map. Assumes it is not already present.
|
2022-02-27 22:24:00 +02:00
|
|
|
pub fn putNoClobber(self: *Self, allocator: Allocator, key: K, value: V) Allocator.Error!void {
|
2021-06-03 15:39:26 -05:00
|
|
|
if (@sizeOf(Context) != 0)
|
2021-06-10 20:13:43 -07:00
|
|
|
@compileError("Cannot infer context " ++ @typeName(Context) ++ ", call putNoClobberContext instead.");
|
2021-06-03 15:39:26 -05:00
|
|
|
return self.putNoClobberContext(allocator, key, value, undefined);
|
|
|
|
|
}
|
2022-02-27 22:24:00 +02:00
|
|
|
pub fn putNoClobberContext(self: *Self, allocator: Allocator, key: K, value: V, ctx: Context) Allocator.Error!void {
|
2024-03-16 15:45:10 -07:00
|
|
|
{
|
|
|
|
|
self.pointer_stability.lock();
|
|
|
|
|
defer self.pointer_stability.unlock();
|
|
|
|
|
try self.growIfNeeded(allocator, 1, ctx);
|
|
|
|
|
}
|
2021-06-03 15:39:26 -05:00
|
|
|
self.putAssumeCapacityNoClobberContext(key, value, ctx);
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
}
|
2018-08-03 17:22:17 -04:00
|
|
|
|
2020-11-11 00:01:40 +02:00
|
|
|
/// 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`.
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
pub fn putAssumeCapacity(self: *Self, key: K, value: V) void {
|
2021-06-03 15:39:26 -05:00
|
|
|
if (@sizeOf(Context) != 0)
|
2021-06-10 20:13:43 -07:00
|
|
|
@compileError("Cannot infer context " ++ @typeName(Context) ++ ", call putAssumeCapacityContext instead.");
|
2021-06-03 15:39:26 -05:00
|
|
|
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;
|
2016-12-18 19:40:26 -05:00
|
|
|
}
|
2016-05-08 16:05:41 -07:00
|
|
|
|
2020-08-02 23:24:03 +02:00
|
|
|
/// Insert an entry in the map. Assumes it is not already present,
|
|
|
|
|
/// and that no allocation is needed.
|
2020-05-12 01:02:48 -04:00
|
|
|
pub fn putAssumeCapacityNoClobber(self: *Self, key: K, value: V) void {
|
2021-06-03 15:39:26 -05:00
|
|
|
if (@sizeOf(Context) != 0)
|
2021-06-10 20:13:43 -07:00
|
|
|
@compileError("Cannot infer context " ++ @typeName(Context) ++ ", call putAssumeCapacityNoClobberContext instead.");
|
2021-06-03 15:39:26 -05:00
|
|
|
return self.putAssumeCapacityNoClobberContext(key, value, undefined);
|
|
|
|
|
}
|
|
|
|
|
pub fn putAssumeCapacityNoClobberContext(self: *Self, key: K, value: V, ctx: Context) void {
|
|
|
|
|
assert(!self.containsContext(key, ctx));
|
2020-08-02 23:24:03 +02:00
|
|
|
|
2025-01-06 05:37:30 -08:00
|
|
|
const hash: Hash = ctx.hash(key);
|
2020-08-02 23:24:03 +02:00
|
|
|
const mask = self.capacity() - 1;
|
2024-03-16 15:45:10 -07:00
|
|
|
var idx: usize = @truncate(hash & mask);
|
2020-08-02 23:24:03 +02:00
|
|
|
|
|
|
|
|
var metadata = self.metadata.? + idx;
|
|
|
|
|
while (metadata[0].isUsed()) {
|
|
|
|
|
idx = (idx + 1) & mask;
|
|
|
|
|
metadata = self.metadata.? + idx;
|
|
|
|
|
}
|
|
|
|
|
|
2021-12-14 13:25:23 -08:00
|
|
|
assert(self.available > 0);
|
|
|
|
|
self.available -= 1;
|
2020-08-02 23:24:03 +02:00
|
|
|
|
|
|
|
|
const fingerprint = Metadata.takeFingerprint(hash);
|
|
|
|
|
metadata[0].fill(fingerprint);
|
2021-06-03 15:39:26 -05:00
|
|
|
self.keys()[idx] = key;
|
|
|
|
|
self.values()[idx] = value;
|
2020-08-02 23:24:03 +02:00
|
|
|
|
|
|
|
|
self.size += 1;
|
2020-05-12 01:02:48 -04:00
|
|
|
}
|
|
|
|
|
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
/// Inserts a new `Entry` into the hash map, returning the previous one, if any.
|
2022-02-27 22:24:00 +02:00
|
|
|
pub fn fetchPut(self: *Self, allocator: Allocator, key: K, value: V) Allocator.Error!?KV {
|
2021-06-03 15:39:26 -05:00
|
|
|
if (@sizeOf(Context) != 0)
|
2021-06-10 20:13:43 -07:00
|
|
|
@compileError("Cannot infer context " ++ @typeName(Context) ++ ", call fetchPutContext instead.");
|
2021-06-03 15:39:26 -05:00
|
|
|
return self.fetchPutContext(allocator, key, value, undefined);
|
|
|
|
|
}
|
2022-02-27 22:24:00 +02:00
|
|
|
pub fn fetchPutContext(self: *Self, allocator: Allocator, key: K, value: V, ctx: Context) Allocator.Error!?KV {
|
2021-06-03 15:39:26 -05:00
|
|
|
const gop = try self.getOrPutContext(allocator, key, ctx);
|
|
|
|
|
var result: ?KV = null;
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
if (gop.found_existing) {
|
2021-06-03 15:39:26 -05:00
|
|
|
result = KV{
|
|
|
|
|
.key = gop.key_ptr.*,
|
|
|
|
|
.value = gop.value_ptr.*,
|
|
|
|
|
};
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
}
|
2021-06-03 15:39:26 -05:00
|
|
|
gop.value_ptr.* = value;
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
return result;
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
/// Inserts a new `Entry` into the hash map, returning the previous one, if any.
|
2020-07-04 22:25:49 +00:00
|
|
|
/// If insertion happens, asserts there is enough capacity without allocating.
|
2021-06-03 15:39:26 -05:00
|
|
|
pub fn fetchPutAssumeCapacity(self: *Self, key: K, value: V) ?KV {
|
|
|
|
|
if (@sizeOf(Context) != 0)
|
2021-06-10 20:13:43 -07:00
|
|
|
@compileError("Cannot infer context " ++ @typeName(Context) ++ ", call fetchPutAssumeCapacityContext instead.");
|
2021-06-03 15:39:26 -05:00
|
|
|
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;
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
if (gop.found_existing) {
|
2021-06-03 15:39:26 -05:00
|
|
|
result = KV{
|
|
|
|
|
.key = gop.key_ptr.*,
|
|
|
|
|
.value = gop.value_ptr.*,
|
|
|
|
|
};
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
}
|
2021-06-03 15:39:26 -05:00
|
|
|
gop.value_ptr.* = value;
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
return result;
|
|
|
|
|
}
|
|
|
|
|
|
2021-06-03 15:39:26 -05:00
|
|
|
/// 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)
|
2021-06-10 20:13:43 -07:00
|
|
|
@compileError("Cannot infer context " ++ @typeName(Context) ++ ", call fetchRemoveContext instead.");
|
2021-06-03 15:39:26 -05:00
|
|
|
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;
|
2023-06-09 12:52:36 -07:00
|
|
|
self.available += 1;
|
2021-06-03 15:39:26 -05:00
|
|
|
return result;
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
return null;
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
/// Find the index containing the data for the given key.
|
2024-12-15 03:41:56 -08:00
|
|
|
fn getIndex(self: Self, key: anytype, ctx: anytype) ?usize {
|
2020-08-02 23:24:03 +02:00
|
|
|
if (self.size == 0) {
|
2024-12-15 03:41:56 -08:00
|
|
|
// We use cold instead of unlikely to force a jump to this case,
|
|
|
|
|
// no matter the weight of the opposing side.
|
|
|
|
|
@branchHint(.cold);
|
2020-08-02 23:24:03 +02:00
|
|
|
return null;
|
|
|
|
|
}
|
2020-08-02 19:21:01 -07:00
|
|
|
|
2021-06-03 15:39:26 -05:00
|
|
|
// If you get a compile error on this line, it means that your generic hash
|
|
|
|
|
// function is invalid for these parameters.
|
2025-01-06 05:37:30 -08:00
|
|
|
const hash: Hash = ctx.hash(key);
|
|
|
|
|
|
2020-08-02 23:24:03 +02:00
|
|
|
const mask = self.capacity() - 1;
|
|
|
|
|
const fingerprint = Metadata.takeFingerprint(hash);
|
2021-12-17 16:56:43 -07:00
|
|
|
// Don't loop indefinitely when there are no empty slots.
|
|
|
|
|
var limit = self.capacity();
|
2023-06-22 18:46:56 +01:00
|
|
|
var idx = @as(usize, @truncate(hash & mask));
|
2020-08-02 23:24:03 +02:00
|
|
|
|
|
|
|
|
var metadata = self.metadata.? + idx;
|
2022-01-10 20:54:45 -08:00
|
|
|
while (!metadata[0].isFree() and limit != 0) {
|
2020-08-02 23:24:03 +02:00
|
|
|
if (metadata[0].isUsed() and metadata[0].fingerprint == fingerprint) {
|
2021-06-03 15:39:26 -05:00
|
|
|
const test_key = &self.keys()[idx];
|
2025-01-06 05:37:30 -08:00
|
|
|
|
|
|
|
|
if (ctx.eql(key, test_key.*)) {
|
2021-06-03 15:39:26 -05:00
|
|
|
return idx;
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
}
|
|
|
|
|
}
|
2021-06-03 15:39:26 -05:00
|
|
|
|
2021-12-17 16:56:43 -07:00
|
|
|
limit -= 1;
|
2020-08-02 23:24:03 +02:00
|
|
|
idx = (idx + 1) & mask;
|
|
|
|
|
metadata = self.metadata.? + idx;
|
2017-04-03 18:11:57 -04:00
|
|
|
}
|
2016-05-08 16:05:41 -07:00
|
|
|
|
2020-08-02 23:24:03 +02:00
|
|
|
return null;
|
2019-06-13 07:26:40 -04:00
|
|
|
}
|
|
|
|
|
|
2021-06-03 15:39:26 -05:00
|
|
|
pub fn getEntry(self: Self, key: K) ?Entry {
|
|
|
|
|
if (@sizeOf(Context) != 0)
|
2021-06-10 20:13:43 -07:00
|
|
|
@compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getEntryContext instead.");
|
2021-06-03 15:39:26 -05:00
|
|
|
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;
|
|
|
|
|
}
|
|
|
|
|
|
2020-08-02 23:24:03 +02:00
|
|
|
/// Insert an entry if the associated key is not already present, otherwise update preexisting value.
|
2022-02-27 22:24:00 +02:00
|
|
|
pub fn put(self: *Self, allocator: Allocator, key: K, value: V) Allocator.Error!void {
|
2021-06-03 15:39:26 -05:00
|
|
|
if (@sizeOf(Context) != 0)
|
2021-06-10 20:13:43 -07:00
|
|
|
@compileError("Cannot infer context " ++ @typeName(Context) ++ ", call putContext instead.");
|
2021-06-03 15:39:26 -05:00
|
|
|
return self.putContext(allocator, key, value, undefined);
|
|
|
|
|
}
|
2022-02-27 22:24:00 +02:00
|
|
|
pub fn putContext(self: *Self, allocator: Allocator, key: K, value: V, ctx: Context) Allocator.Error!void {
|
2021-06-03 15:39:26 -05:00
|
|
|
const result = try self.getOrPutContext(allocator, key, ctx);
|
|
|
|
|
result.value_ptr.* = value;
|
2018-01-17 00:22:33 -05:00
|
|
|
}
|
|
|
|
|
|
2021-08-30 21:32:34 -07:00
|
|
|
/// Get an optional pointer to the actual key associated with adapted key, if present.
|
|
|
|
|
pub fn getKeyPtr(self: Self, key: K) ?*K {
|
|
|
|
|
if (@sizeOf(Context) != 0)
|
|
|
|
|
@compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getKeyPtrContext instead.");
|
|
|
|
|
return self.getKeyPtrContext(key, undefined);
|
|
|
|
|
}
|
|
|
|
|
pub fn getKeyPtrContext(self: Self, key: K, ctx: Context) ?*K {
|
|
|
|
|
return self.getKeyPtrAdapted(key, ctx);
|
|
|
|
|
}
|
|
|
|
|
pub fn getKeyPtrAdapted(self: Self, key: anytype, ctx: anytype) ?*K {
|
|
|
|
|
if (self.getIndex(key, ctx)) |idx| {
|
|
|
|
|
return &self.keys()[idx];
|
|
|
|
|
}
|
|
|
|
|
return null;
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
/// Get a copy of the actual key associated with adapted key, if present.
|
|
|
|
|
pub fn getKey(self: Self, key: K) ?K {
|
|
|
|
|
if (@sizeOf(Context) != 0)
|
|
|
|
|
@compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getKeyContext instead.");
|
|
|
|
|
return self.getKeyContext(key, undefined);
|
|
|
|
|
}
|
|
|
|
|
pub fn getKeyContext(self: Self, key: K, ctx: Context) ?K {
|
|
|
|
|
return self.getKeyAdapted(key, ctx);
|
|
|
|
|
}
|
|
|
|
|
pub fn getKeyAdapted(self: Self, key: anytype, ctx: anytype) ?K {
|
|
|
|
|
if (self.getIndex(key, ctx)) |idx| {
|
|
|
|
|
return self.keys()[idx];
|
|
|
|
|
}
|
|
|
|
|
return null;
|
|
|
|
|
}
|
|
|
|
|
|
2020-08-02 23:24:03 +02:00
|
|
|
/// Get an optional pointer to the value associated with key, if present.
|
2021-06-03 15:39:26 -05:00
|
|
|
pub fn getPtr(self: Self, key: K) ?*V {
|
|
|
|
|
if (@sizeOf(Context) != 0)
|
2021-06-10 20:13:43 -07:00
|
|
|
@compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getPtrContext instead.");
|
2021-06-03 15:39:26 -05:00
|
|
|
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];
|
2020-08-02 23:24:03 +02:00
|
|
|
}
|
2021-06-03 15:39:26 -05:00
|
|
|
return null;
|
|
|
|
|
}
|
2020-08-02 23:24:03 +02:00
|
|
|
|
2021-06-03 15:39:26 -05:00
|
|
|
/// Get a copy of the value associated with key, if present.
|
|
|
|
|
pub fn get(self: Self, key: K) ?V {
|
|
|
|
|
if (@sizeOf(Context) != 0)
|
2021-06-10 20:13:43 -07:00
|
|
|
@compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getContext instead.");
|
2021-06-03 15:39:26 -05:00
|
|
|
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];
|
2018-05-10 00:29:49 -04:00
|
|
|
}
|
2020-08-02 23:24:03 +02:00
|
|
|
return null;
|
2019-06-12 23:39:53 -04:00
|
|
|
}
|
|
|
|
|
|
2022-02-27 22:24:00 +02:00
|
|
|
pub fn getOrPut(self: *Self, allocator: Allocator, key: K) Allocator.Error!GetOrPutResult {
|
2021-06-03 15:39:26 -05:00
|
|
|
if (@sizeOf(Context) != 0)
|
2021-06-10 20:13:43 -07:00
|
|
|
@compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getOrPutContext instead.");
|
2021-06-03 15:39:26 -05:00
|
|
|
return self.getOrPutContext(allocator, key, undefined);
|
|
|
|
|
}
|
2022-02-27 22:24:00 +02:00
|
|
|
pub fn getOrPutContext(self: *Self, allocator: Allocator, key: K, ctx: Context) Allocator.Error!GetOrPutResult {
|
2021-06-03 15:39:26 -05:00
|
|
|
const gop = try self.getOrPutContextAdapted(allocator, key, ctx, ctx);
|
|
|
|
|
if (!gop.found_existing) {
|
|
|
|
|
gop.key_ptr.* = key;
|
|
|
|
|
}
|
|
|
|
|
return gop;
|
|
|
|
|
}
|
2022-02-27 22:24:00 +02:00
|
|
|
pub fn getOrPutAdapted(self: *Self, allocator: Allocator, key: anytype, key_ctx: anytype) Allocator.Error!GetOrPutResult {
|
2021-06-03 15:39:26 -05:00
|
|
|
if (@sizeOf(Context) != 0)
|
2021-06-10 20:13:43 -07:00
|
|
|
@compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getOrPutContextAdapted instead.");
|
2021-06-03 15:39:26 -05:00
|
|
|
return self.getOrPutContextAdapted(allocator, key, key_ctx, undefined);
|
|
|
|
|
}
|
2022-02-27 22:24:00 +02:00
|
|
|
pub fn getOrPutContextAdapted(self: *Self, allocator: Allocator, key: anytype, key_ctx: anytype, ctx: Context) Allocator.Error!GetOrPutResult {
|
2024-03-16 15:45:10 -07:00
|
|
|
{
|
|
|
|
|
self.pointer_stability.lock();
|
|
|
|
|
defer self.pointer_stability.unlock();
|
|
|
|
|
self.growIfNeeded(allocator, 1, ctx) catch |err| {
|
|
|
|
|
// If allocation fails, try to do the lookup anyway.
|
|
|
|
|
// If we find an existing item, we can return it.
|
|
|
|
|
// Otherwise return the error, we could not add another.
|
|
|
|
|
const index = self.getIndex(key, key_ctx) orelse return err;
|
|
|
|
|
return GetOrPutResult{
|
|
|
|
|
.key_ptr = &self.keys()[index],
|
|
|
|
|
.value_ptr = &self.values()[index],
|
|
|
|
|
.found_existing = true,
|
|
|
|
|
};
|
2021-06-03 15:39:26 -05:00
|
|
|
};
|
2024-03-16 15:45:10 -07:00
|
|
|
}
|
2021-06-03 15:39:26 -05:00
|
|
|
return self.getOrPutAssumeCapacityAdapted(key, key_ctx);
|
2016-12-18 19:40:26 -05:00
|
|
|
}
|
2016-05-08 16:05:41 -07:00
|
|
|
|
2020-08-02 23:24:03 +02:00
|
|
|
pub fn getOrPutAssumeCapacity(self: *Self, key: K) GetOrPutResult {
|
2021-06-03 15:39:26 -05:00
|
|
|
if (@sizeOf(Context) != 0)
|
2021-06-10 20:13:43 -07:00
|
|
|
@compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getOrPutAssumeCapacityContext instead.");
|
2021-06-03 15:39:26 -05:00
|
|
|
return self.getOrPutAssumeCapacityContext(key, undefined);
|
|
|
|
|
}
|
|
|
|
|
pub fn getOrPutAssumeCapacityContext(self: *Self, key: K, ctx: Context) GetOrPutResult {
|
|
|
|
|
const result = self.getOrPutAssumeCapacityAdapted(key, ctx);
|
|
|
|
|
if (!result.found_existing) {
|
|
|
|
|
result.key_ptr.* = key;
|
|
|
|
|
}
|
|
|
|
|
return result;
|
|
|
|
|
}
|
|
|
|
|
pub fn getOrPutAssumeCapacityAdapted(self: *Self, key: anytype, ctx: anytype) GetOrPutResult {
|
|
|
|
|
|
|
|
|
|
// If you get a compile error on this line, it means that your generic hash
|
|
|
|
|
// function is invalid for these parameters.
|
2025-01-06 05:37:30 -08:00
|
|
|
const hash: Hash = ctx.hash(key);
|
|
|
|
|
|
2020-08-02 23:24:03 +02:00
|
|
|
const mask = self.capacity() - 1;
|
|
|
|
|
const fingerprint = Metadata.takeFingerprint(hash);
|
2021-12-17 16:56:43 -07:00
|
|
|
var limit = self.capacity();
|
2023-06-22 18:46:56 +01:00
|
|
|
var idx = @as(usize, @truncate(hash & mask));
|
2020-08-02 23:24:03 +02:00
|
|
|
|
|
|
|
|
var first_tombstone_idx: usize = self.capacity(); // invalid index
|
|
|
|
|
var metadata = self.metadata.? + idx;
|
2022-01-10 20:54:45 -08:00
|
|
|
while (!metadata[0].isFree() and limit != 0) {
|
2020-08-02 23:24:03 +02:00
|
|
|
if (metadata[0].isUsed() and metadata[0].fingerprint == fingerprint) {
|
2021-06-03 15:39:26 -05:00
|
|
|
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.
|
2025-01-06 05:37:30 -08:00
|
|
|
|
|
|
|
|
if (ctx.eql(key, test_key.*)) {
|
2021-06-03 15:39:26 -05:00
|
|
|
return GetOrPutResult{
|
|
|
|
|
.key_ptr = test_key,
|
|
|
|
|
.value_ptr = &self.values()[idx],
|
|
|
|
|
.found_existing = true,
|
|
|
|
|
};
|
2020-08-02 23:24:03 +02:00
|
|
|
}
|
|
|
|
|
} else if (first_tombstone_idx == self.capacity() and metadata[0].isTombstone()) {
|
|
|
|
|
first_tombstone_idx = idx;
|
|
|
|
|
}
|
2020-07-06 16:51:53 +03:00
|
|
|
|
2021-12-17 16:56:43 -07:00
|
|
|
limit -= 1;
|
2020-08-02 23:24:03 +02:00
|
|
|
idx = (idx + 1) & mask;
|
|
|
|
|
metadata = self.metadata.? + idx;
|
2018-08-01 16:26:37 -04:00
|
|
|
}
|
2020-08-02 23:24:03 +02:00
|
|
|
|
|
|
|
|
if (first_tombstone_idx < self.capacity()) {
|
|
|
|
|
// Cheap try to lower probing lengths after deletions. Recycle a tombstone.
|
|
|
|
|
idx = first_tombstone_idx;
|
|
|
|
|
metadata = self.metadata.? + idx;
|
|
|
|
|
}
|
2021-12-14 13:25:23 -08:00
|
|
|
// We're using a slot previously free or a tombstone.
|
|
|
|
|
self.available -= 1;
|
2020-08-02 23:24:03 +02:00
|
|
|
|
|
|
|
|
metadata[0].fill(fingerprint);
|
2021-06-03 15:39:26 -05:00
|
|
|
const new_key = &self.keys()[idx];
|
|
|
|
|
const new_value = &self.values()[idx];
|
2021-06-18 13:52:30 +08:00
|
|
|
new_key.* = undefined;
|
2021-06-03 15:39:26 -05:00
|
|
|
new_value.* = undefined;
|
2020-08-02 23:24:03 +02:00
|
|
|
self.size += 1;
|
|
|
|
|
|
2021-06-03 15:39:26 -05:00
|
|
|
return GetOrPutResult{
|
|
|
|
|
.key_ptr = new_key,
|
|
|
|
|
.value_ptr = new_value,
|
|
|
|
|
.found_existing = false,
|
|
|
|
|
};
|
2018-08-01 16:26:37 -04:00
|
|
|
}
|
|
|
|
|
|
2022-02-27 22:24:00 +02:00
|
|
|
pub fn getOrPutValue(self: *Self, allocator: Allocator, key: K, value: V) Allocator.Error!Entry {
|
2021-06-03 15:39:26 -05:00
|
|
|
if (@sizeOf(Context) != 0)
|
2021-06-10 20:13:43 -07:00
|
|
|
@compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getOrPutValueContext instead.");
|
2021-06-03 15:39:26 -05:00
|
|
|
return self.getOrPutValueContext(allocator, key, value, undefined);
|
|
|
|
|
}
|
2022-02-27 22:24:00 +02:00
|
|
|
pub fn getOrPutValueContext(self: *Self, allocator: Allocator, key: K, value: V, ctx: Context) Allocator.Error!Entry {
|
2021-06-03 15:39:26 -05:00
|
|
|
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 };
|
2020-08-02 23:24:03 +02:00
|
|
|
}
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
|
2020-08-02 23:24:03 +02:00
|
|
|
/// Return true if there is a value associated with key in the map.
|
2024-05-16 18:56:35 -04:00
|
|
|
pub fn contains(self: Self, key: K) bool {
|
2021-06-03 15:39:26 -05:00
|
|
|
if (@sizeOf(Context) != 0)
|
2021-06-10 20:13:43 -07:00
|
|
|
@compileError("Cannot infer context " ++ @typeName(Context) ++ ", call containsContext instead.");
|
2021-06-03 15:39:26 -05:00
|
|
|
return self.containsContext(key, undefined);
|
2020-08-02 23:24:03 +02:00
|
|
|
}
|
2024-05-16 18:56:35 -04:00
|
|
|
pub fn containsContext(self: Self, key: K, ctx: Context) bool {
|
2021-06-03 15:39:26 -05:00
|
|
|
return self.containsAdapted(key, ctx);
|
|
|
|
|
}
|
2024-05-16 18:56:35 -04:00
|
|
|
pub fn containsAdapted(self: Self, key: anytype, ctx: anytype) bool {
|
2021-06-03 15:39:26 -05:00
|
|
|
return self.getIndex(key, ctx) != null;
|
2016-05-08 16:05:41 -07:00
|
|
|
}
|
|
|
|
|
|
2021-11-15 12:54:14 +00:00
|
|
|
fn removeByIndex(self: *Self, idx: usize) void {
|
|
|
|
|
self.metadata.?[idx].remove();
|
|
|
|
|
self.keys()[idx] = undefined;
|
|
|
|
|
self.values()[idx] = undefined;
|
|
|
|
|
self.size -= 1;
|
|
|
|
|
self.available += 1;
|
|
|
|
|
}
|
|
|
|
|
|
2021-06-03 15:39:26 -05:00
|
|
|
/// 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.
|
2025-02-03 21:20:52 -08:00
|
|
|
///
|
|
|
|
|
/// TODO: answer the question in these doc comments, does this
|
|
|
|
|
/// increase the unused capacity by one?
|
2021-06-03 15:39:26 -05:00
|
|
|
pub fn remove(self: *Self, key: K) bool {
|
|
|
|
|
if (@sizeOf(Context) != 0)
|
2021-06-10 20:13:43 -07:00
|
|
|
@compileError("Cannot infer context " ++ @typeName(Context) ++ ", call removeContext instead.");
|
2021-06-03 15:39:26 -05:00
|
|
|
return self.removeContext(key, undefined);
|
|
|
|
|
}
|
2025-02-03 21:20:52 -08:00
|
|
|
|
|
|
|
|
/// TODO: answer the question in these doc comments, does this
|
|
|
|
|
/// increase the unused capacity by one?
|
2021-06-03 15:39:26 -05:00
|
|
|
pub fn removeContext(self: *Self, key: K, ctx: Context) bool {
|
|
|
|
|
return self.removeAdapted(key, ctx);
|
|
|
|
|
}
|
2025-02-03 21:20:52 -08:00
|
|
|
|
|
|
|
|
/// TODO: answer the question in these doc comments, does this
|
|
|
|
|
/// increase the unused capacity by one?
|
2021-06-03 15:39:26 -05:00
|
|
|
pub fn removeAdapted(self: *Self, key: anytype, ctx: anytype) bool {
|
|
|
|
|
if (self.getIndex(key, ctx)) |idx| {
|
2021-11-15 12:54:14 +00:00
|
|
|
self.removeByIndex(idx);
|
2021-06-03 15:39:26 -05:00
|
|
|
return true;
|
2016-12-18 19:40:26 -05:00
|
|
|
}
|
2020-08-02 23:24:03 +02:00
|
|
|
|
2021-06-03 15:39:26 -05:00
|
|
|
return false;
|
2016-05-08 16:05:41 -07:00
|
|
|
}
|
|
|
|
|
|
2023-07-19 18:17:03 +01:00
|
|
|
/// Delete the entry with key pointed to by key_ptr from the hash map.
|
|
|
|
|
/// key_ptr is assumed to be a valid pointer to a key that is present
|
2021-11-15 12:54:14 +00:00
|
|
|
/// in the hash map.
|
2025-02-03 21:20:52 -08:00
|
|
|
///
|
|
|
|
|
/// TODO: answer the question in these doc comments, does this
|
|
|
|
|
/// increase the unused capacity by one?
|
2023-07-19 18:17:03 +01:00
|
|
|
pub fn removeByPtr(self: *Self, key_ptr: *K) void {
|
2021-11-15 12:54:14 +00:00
|
|
|
// if @sizeOf(K) == 0 then there is at most one item in the hash
|
2023-07-19 18:17:03 +01:00
|
|
|
// map, which is assumed to exist as key_ptr must be valid. This
|
2021-11-15 12:54:14 +00:00
|
|
|
// item must be at index 0.
|
|
|
|
|
const idx = if (@sizeOf(K) > 0)
|
2025-09-11 00:14:01 +02:00
|
|
|
(key_ptr - self.keys())
|
2021-11-15 12:54:14 +00:00
|
|
|
else
|
|
|
|
|
0;
|
|
|
|
|
|
|
|
|
|
self.removeByIndex(idx);
|
|
|
|
|
}
|
|
|
|
|
|
2020-08-02 23:24:03 +02:00
|
|
|
fn initMetadatas(self: *Self) void {
|
2023-06-22 18:46:56 +01:00
|
|
|
@memset(@as([*]u8, @ptrCast(self.metadata.?))[0 .. @sizeOf(Metadata) * self.capacity()], 0);
|
2020-08-02 23:24:03 +02:00
|
|
|
}
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
|
2021-12-14 13:25:23 -08:00
|
|
|
// This counts the number of occupied slots (not counting tombstones), which is
|
2021-01-30 14:56:36 +02:00
|
|
|
// what has to stay under the max_load_percentage of capacity.
|
2024-05-16 18:56:35 -04:00
|
|
|
fn load(self: Self) Size {
|
2021-01-30 14:56:36 +02:00
|
|
|
const max_load = (self.capacity() * max_load_percentage) / 100;
|
2020-08-02 23:24:03 +02:00
|
|
|
assert(max_load >= self.available);
|
2023-06-22 18:46:56 +01:00
|
|
|
return @as(Size, @truncate(max_load - self.available));
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
}
|
2016-05-08 16:05:41 -07:00
|
|
|
|
2022-02-27 22:24:00 +02:00
|
|
|
fn growIfNeeded(self: *Self, allocator: Allocator, new_count: Size, ctx: Context) Allocator.Error!void {
|
2020-08-02 23:24:03 +02:00
|
|
|
if (new_count > self.available) {
|
2021-06-03 15:39:26 -05:00
|
|
|
try self.grow(allocator, capacityForSize(self.load() + new_count), ctx);
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
}
|
|
|
|
|
}
|
2016-05-08 16:05:41 -07:00
|
|
|
|
2022-02-27 22:24:00 +02:00
|
|
|
pub fn clone(self: Self, allocator: Allocator) Allocator.Error!Self {
|
2021-06-03 15:39:26 -05:00
|
|
|
if (@sizeOf(Context) != 0)
|
2021-06-10 20:13:43 -07:00
|
|
|
@compileError("Cannot infer context " ++ @typeName(Context) ++ ", call cloneContext instead.");
|
2021-06-03 15:39:26 -05:00
|
|
|
return self.cloneContext(allocator, @as(Context, undefined));
|
|
|
|
|
}
|
2022-02-27 22:24:00 +02:00
|
|
|
pub fn cloneContext(self: Self, allocator: Allocator, new_ctx: anytype) Allocator.Error!HashMapUnmanaged(K, V, @TypeOf(new_ctx), max_load_percentage) {
|
2024-09-02 22:32:21 +01:00
|
|
|
var other: HashMapUnmanaged(K, V, @TypeOf(new_ctx), max_load_percentage) = .empty;
|
2020-08-02 23:24:03 +02:00
|
|
|
if (self.size == 0)
|
|
|
|
|
return other;
|
|
|
|
|
|
|
|
|
|
const new_cap = capacityForSize(self.size);
|
|
|
|
|
try other.allocate(allocator, new_cap);
|
|
|
|
|
other.initMetadatas();
|
2023-07-24 05:34:16 -05:00
|
|
|
other.available = @truncate((new_cap * max_load_percentage) / 100);
|
2020-08-02 23:24:03 +02:00
|
|
|
|
|
|
|
|
var i: Size = 0;
|
|
|
|
|
var metadata = self.metadata.?;
|
2023-11-10 05:27:17 +00:00
|
|
|
const keys_ptr = self.keys();
|
|
|
|
|
const values_ptr = self.values();
|
2020-08-02 23:24:03 +02:00
|
|
|
while (i < self.capacity()) : (i += 1) {
|
|
|
|
|
if (metadata[i].isUsed()) {
|
2021-06-03 15:39:26 -05:00
|
|
|
other.putAssumeCapacityNoClobberContext(keys_ptr[i], values_ptr[i], new_ctx);
|
2020-08-02 23:24:03 +02:00
|
|
|
if (other.size == self.size)
|
|
|
|
|
break;
|
|
|
|
|
}
|
2016-12-18 19:40:26 -05:00
|
|
|
}
|
2020-08-02 23:24:03 +02:00
|
|
|
|
|
|
|
|
return other;
|
2016-05-08 16:05:41 -07:00
|
|
|
}
|
|
|
|
|
|
2022-12-02 23:05:12 -07:00
|
|
|
/// 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 {
|
2024-03-16 15:45:10 -07:00
|
|
|
self.pointer_stability.assertUnlocked();
|
2022-12-02 23:05:12 -07:00
|
|
|
const result = self.*;
|
2024-09-02 22:32:21 +01:00
|
|
|
self.* = .empty;
|
2022-12-02 23:05:12 -07:00
|
|
|
return result;
|
|
|
|
|
}
|
|
|
|
|
|
2024-08-08 11:59:22 -07:00
|
|
|
/// Rehash the map, in-place.
|
|
|
|
|
///
|
|
|
|
|
/// Over time, due to the current tombstone-based implementation, a
|
|
|
|
|
/// HashMap could become fragmented due to the buildup of tombstone
|
|
|
|
|
/// entries that causes a performance degradation due to excessive
|
|
|
|
|
/// probing. The kind of pattern that might cause this is a long-lived
|
|
|
|
|
/// HashMap with repeated inserts and deletes.
|
|
|
|
|
///
|
|
|
|
|
/// After this function is called, there will be no tombstones in
|
|
|
|
|
/// the HashMap, each of the entries is rehashed and any existing
|
|
|
|
|
/// key/value pointers into the HashMap are invalidated.
|
|
|
|
|
pub fn rehash(self: *Self, ctx: anytype) void {
|
|
|
|
|
const mask = self.capacity() - 1;
|
|
|
|
|
|
|
|
|
|
var metadata = self.metadata.?;
|
|
|
|
|
var keys_ptr = self.keys();
|
|
|
|
|
var values_ptr = self.values();
|
|
|
|
|
var curr: Size = 0;
|
|
|
|
|
|
|
|
|
|
// While we are re-hashing every slot, we will use the
|
|
|
|
|
// fingerprint to mark used buckets as being used and either free
|
|
|
|
|
// (needing to be rehashed) or tombstone (already rehashed).
|
|
|
|
|
|
|
|
|
|
while (curr < self.capacity()) : (curr += 1) {
|
|
|
|
|
metadata[curr].fingerprint = Metadata.free;
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
// Now iterate over all the buckets, rehashing them
|
|
|
|
|
|
|
|
|
|
curr = 0;
|
|
|
|
|
while (curr < self.capacity()) {
|
|
|
|
|
if (!metadata[curr].isUsed()) {
|
|
|
|
|
assert(metadata[curr].isFree());
|
|
|
|
|
curr += 1;
|
|
|
|
|
continue;
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
const hash = ctx.hash(keys_ptr[curr]);
|
|
|
|
|
const fingerprint = Metadata.takeFingerprint(hash);
|
|
|
|
|
var idx = @as(usize, @truncate(hash & mask));
|
|
|
|
|
|
|
|
|
|
// For each bucket, rehash to an index:
|
|
|
|
|
// 1) before the cursor, probed into a free slot, or
|
|
|
|
|
// 2) equal to the cursor, no need to move, or
|
|
|
|
|
// 3) ahead of the cursor, probing over already rehashed
|
|
|
|
|
|
|
|
|
|
while ((idx < curr and metadata[idx].isUsed()) or
|
|
|
|
|
(idx > curr and metadata[idx].fingerprint == Metadata.tombstone))
|
|
|
|
|
{
|
|
|
|
|
idx = (idx + 1) & mask;
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
if (idx < curr) {
|
|
|
|
|
assert(metadata[idx].isFree());
|
|
|
|
|
metadata[idx].fill(fingerprint);
|
|
|
|
|
keys_ptr[idx] = keys_ptr[curr];
|
|
|
|
|
values_ptr[idx] = values_ptr[curr];
|
|
|
|
|
|
|
|
|
|
metadata[curr].used = 0;
|
|
|
|
|
assert(metadata[curr].isFree());
|
|
|
|
|
keys_ptr[curr] = undefined;
|
|
|
|
|
values_ptr[curr] = undefined;
|
|
|
|
|
|
|
|
|
|
curr += 1;
|
|
|
|
|
} else if (idx == curr) {
|
|
|
|
|
metadata[idx].fingerprint = fingerprint;
|
|
|
|
|
curr += 1;
|
|
|
|
|
} else {
|
|
|
|
|
assert(metadata[idx].fingerprint != Metadata.tombstone);
|
|
|
|
|
metadata[idx].fingerprint = Metadata.tombstone;
|
|
|
|
|
if (metadata[idx].isUsed()) {
|
|
|
|
|
std.mem.swap(K, &keys_ptr[curr], &keys_ptr[idx]);
|
|
|
|
|
std.mem.swap(V, &values_ptr[curr], &values_ptr[idx]);
|
|
|
|
|
} else {
|
|
|
|
|
metadata[idx].used = 1;
|
|
|
|
|
keys_ptr[idx] = keys_ptr[curr];
|
|
|
|
|
values_ptr[idx] = values_ptr[curr];
|
|
|
|
|
|
|
|
|
|
metadata[curr].fingerprint = Metadata.free;
|
|
|
|
|
metadata[curr].used = 0;
|
|
|
|
|
keys_ptr[curr] = undefined;
|
|
|
|
|
values_ptr[curr] = undefined;
|
|
|
|
|
|
|
|
|
|
curr += 1;
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
2022-02-27 22:24:00 +02:00
|
|
|
fn grow(self: *Self, allocator: Allocator, new_capacity: Size, ctx: Context) Allocator.Error!void {
|
2024-08-24 16:16:53 +01:00
|
|
|
@branchHint(.cold);
|
2023-06-02 22:02:45 -04:00
|
|
|
const new_cap = @max(new_capacity, minimal_capacity);
|
2020-08-02 23:24:03 +02:00
|
|
|
assert(new_cap > self.capacity());
|
|
|
|
|
assert(std.math.isPowerOfTwo(new_cap));
|
|
|
|
|
|
2024-03-16 15:45:10 -07:00
|
|
|
var map: Self = .{};
|
2020-08-02 23:24:03 +02:00
|
|
|
try map.allocate(allocator, new_cap);
|
2024-03-20 11:13:50 -07:00
|
|
|
errdefer comptime unreachable;
|
|
|
|
|
map.pointer_stability.lock();
|
2020-08-02 23:24:03 +02:00
|
|
|
map.initMetadatas();
|
2023-07-24 05:34:16 -05:00
|
|
|
map.available = @truncate((new_cap * max_load_percentage) / 100);
|
2020-08-02 23:24:03 +02:00
|
|
|
|
|
|
|
|
if (self.size != 0) {
|
|
|
|
|
const old_capacity = self.capacity();
|
2024-03-16 15:45:10 -07:00
|
|
|
for (
|
|
|
|
|
self.metadata.?[0..old_capacity],
|
|
|
|
|
self.keys()[0..old_capacity],
|
|
|
|
|
self.values()[0..old_capacity],
|
|
|
|
|
) |m, k, v| {
|
|
|
|
|
if (!m.isUsed()) continue;
|
|
|
|
|
map.putAssumeCapacityNoClobberContext(k, v, ctx);
|
|
|
|
|
if (map.size == self.size) break;
|
2018-05-10 00:29:49 -04:00
|
|
|
}
|
|
|
|
|
}
|
2020-08-02 23:24:03 +02:00
|
|
|
|
|
|
|
|
self.size = 0;
|
2024-10-07 01:16:20 -07:00
|
|
|
self.pointer_stability = .{};
|
2020-08-02 23:24:03 +02:00
|
|
|
std.mem.swap(Self, self, &map);
|
2024-03-20 11:13:50 -07:00
|
|
|
map.deinit(allocator);
|
2020-08-02 23:24:03 +02:00
|
|
|
}
|
|
|
|
|
|
2022-02-27 22:24:00 +02:00
|
|
|
fn allocate(self: *Self, allocator: Allocator, new_capacity: Size) Allocator.Error!void {
|
2021-06-03 15:39:26 -05:00
|
|
|
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);
|
2025-04-11 17:55:25 -07:00
|
|
|
const max_align: Alignment = comptime .fromByteUnits(@max(header_align, key_align, val_align));
|
2021-06-03 15:39:26 -05:00
|
|
|
|
2024-02-24 00:56:00 -05:00
|
|
|
const new_cap: usize = new_capacity;
|
|
|
|
|
const meta_size = @sizeOf(Header) + new_cap * @sizeOf(Metadata);
|
2021-06-03 15:39:26 -05:00
|
|
|
comptime assert(@alignOf(Metadata) == 1);
|
|
|
|
|
|
2023-06-09 16:02:18 -07:00
|
|
|
const keys_start = std.mem.alignForward(usize, meta_size, key_align);
|
2024-02-24 00:56:00 -05:00
|
|
|
const keys_end = keys_start + new_cap * @sizeOf(K);
|
2020-08-02 23:24:03 +02:00
|
|
|
|
2023-06-09 16:02:18 -07:00
|
|
|
const vals_start = std.mem.alignForward(usize, keys_end, val_align);
|
2024-02-24 00:56:00 -05:00
|
|
|
const vals_end = vals_start + new_cap * @sizeOf(V);
|
2020-08-02 23:24:03 +02:00
|
|
|
|
2025-04-11 17:55:25 -07:00
|
|
|
const total_size = max_align.forward(vals_end);
|
2020-08-02 23:24:03 +02:00
|
|
|
|
2021-06-03 15:39:26 -05:00
|
|
|
const slice = try allocator.alignedAlloc(u8, max_align, total_size);
|
2024-05-16 18:56:35 -04:00
|
|
|
const ptr: [*]u8 = @ptrCast(slice.ptr);
|
2020-08-02 23:24:03 +02:00
|
|
|
|
|
|
|
|
const metadata = ptr + @sizeOf(Header);
|
|
|
|
|
|
2024-05-16 18:56:35 -04:00
|
|
|
const hdr = @as(*Header, @ptrCast(@alignCast(ptr)));
|
2021-06-03 15:39:26 -05:00
|
|
|
if (@sizeOf([*]V) != 0) {
|
2024-05-16 18:56:35 -04:00
|
|
|
hdr.values = @ptrCast(@alignCast((ptr + vals_start)));
|
2021-06-03 15:39:26 -05:00
|
|
|
}
|
|
|
|
|
if (@sizeOf([*]K) != 0) {
|
2024-05-16 18:56:35 -04:00
|
|
|
hdr.keys = @ptrCast(@alignCast((ptr + keys_start)));
|
2021-06-03 15:39:26 -05:00
|
|
|
}
|
2020-08-02 23:24:03 +02:00
|
|
|
hdr.capacity = new_capacity;
|
2024-05-16 18:56:35 -04:00
|
|
|
self.metadata = @ptrCast(@alignCast(metadata));
|
2016-12-18 19:40:26 -05:00
|
|
|
}
|
2021-06-03 15:39:26 -05:00
|
|
|
|
2021-10-29 00:37:25 +01:00
|
|
|
fn deallocate(self: *Self, allocator: Allocator) void {
|
2021-06-03 15:39:26 -05:00
|
|
|
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);
|
2023-06-02 22:02:45 -04:00
|
|
|
const max_align = comptime @max(header_align, key_align, val_align);
|
2021-06-03 15:39:26 -05:00
|
|
|
|
2024-02-24 00:56:00 -05:00
|
|
|
const cap: usize = self.capacity();
|
2021-06-03 15:39:26 -05:00
|
|
|
const meta_size = @sizeOf(Header) + cap * @sizeOf(Metadata);
|
|
|
|
|
comptime assert(@alignOf(Metadata) == 1);
|
|
|
|
|
|
2023-06-09 16:02:18 -07:00
|
|
|
const keys_start = std.mem.alignForward(usize, meta_size, key_align);
|
2021-06-03 15:39:26 -05:00
|
|
|
const keys_end = keys_start + cap * @sizeOf(K);
|
|
|
|
|
|
2023-06-09 16:02:18 -07:00
|
|
|
const vals_start = std.mem.alignForward(usize, keys_end, val_align);
|
2021-06-03 15:39:26 -05:00
|
|
|
const vals_end = vals_start + cap * @sizeOf(V);
|
|
|
|
|
|
2023-06-09 16:02:18 -07:00
|
|
|
const total_size = std.mem.alignForward(usize, vals_end, max_align);
|
2021-06-03 15:39:26 -05:00
|
|
|
|
2025-08-03 14:53:52 +02:00
|
|
|
const slice = @as([*]align(max_align) u8, @ptrCast(@alignCast(self.header())))[0..total_size];
|
2021-06-03 15:39:26 -05:00
|
|
|
allocator.free(slice);
|
|
|
|
|
|
|
|
|
|
self.metadata = null;
|
|
|
|
|
self.available = 0;
|
|
|
|
|
}
|
2022-03-16 15:38:30 +01:00
|
|
|
|
2023-02-26 22:11:41 -05:00
|
|
|
/// This function is used in the debugger pretty formatters in tools/ to fetch the
|
|
|
|
|
/// header type to facilitate fancy debug printing for this type.
|
|
|
|
|
fn dbHelper(self: *Self, hdr: *Header, entry: *Entry) void {
|
2022-03-16 15:38:30 +01:00
|
|
|
_ = self;
|
|
|
|
|
_ = hdr;
|
2023-02-26 22:11:41 -05:00
|
|
|
_ = entry;
|
2022-03-16 15:38:30 +01:00
|
|
|
}
|
|
|
|
|
|
|
|
|
|
comptime {
|
2024-09-10 12:15:51 -04:00
|
|
|
if (!builtin.strip_debug_info) _ = switch (builtin.zig_backend) {
|
|
|
|
|
.stage2_llvm => &dbHelper,
|
|
|
|
|
.stage2_x86_64 => KV,
|
|
|
|
|
else => {},
|
|
|
|
|
};
|
2022-03-16 15:38:30 +01:00
|
|
|
}
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
};
|
|
|
|
|
}
|
|
|
|
|
|
2020-08-02 23:24:03 +02:00
|
|
|
const testing = std.testing;
|
|
|
|
|
const expect = std.testing.expect;
|
|
|
|
|
const expectEqual = std.testing.expectEqual;
|
|
|
|
|
|
2024-02-25 23:31:53 -08:00
|
|
|
test "basic usage" {
|
2020-08-02 23:24:03 +02:00
|
|
|
var map = AutoHashMap(u32, u32).init(std.testing.allocator);
|
|
|
|
|
defer map.deinit();
|
|
|
|
|
|
|
|
|
|
const count = 5;
|
|
|
|
|
var i: u32 = 0;
|
|
|
|
|
var total: u32 = 0;
|
|
|
|
|
while (i < count) : (i += 1) {
|
|
|
|
|
try map.put(i, i);
|
|
|
|
|
total += i;
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
var sum: u32 = 0;
|
|
|
|
|
var it = map.iterator();
|
|
|
|
|
while (it.next()) |kv| {
|
2021-06-03 15:39:26 -05:00
|
|
|
sum += kv.key_ptr.*;
|
2020-08-02 23:24:03 +02:00
|
|
|
}
|
2021-06-03 15:39:26 -05:00
|
|
|
try expectEqual(total, sum);
|
2020-08-02 23:24:03 +02:00
|
|
|
|
|
|
|
|
i = 0;
|
|
|
|
|
sum = 0;
|
|
|
|
|
while (i < count) : (i += 1) {
|
2021-06-03 15:39:26 -05:00
|
|
|
try expectEqual(i, map.get(i).?);
|
2020-08-02 23:24:03 +02:00
|
|
|
sum += map.get(i).?;
|
|
|
|
|
}
|
2021-05-04 20:47:26 +03:00
|
|
|
try expectEqual(total, sum);
|
2020-08-02 23:24:03 +02:00
|
|
|
}
|
|
|
|
|
|
2024-02-25 23:31:53 -08:00
|
|
|
test "ensureTotalCapacity" {
|
2020-08-02 23:24:03 +02:00
|
|
|
var map = AutoHashMap(i32, i32).init(std.testing.allocator);
|
|
|
|
|
defer map.deinit();
|
2016-05-08 16:05:41 -07:00
|
|
|
|
2021-09-16 18:22:04 -07:00
|
|
|
try map.ensureTotalCapacity(20);
|
2020-08-02 23:24:03 +02:00
|
|
|
const initial_capacity = map.capacity();
|
2021-05-04 20:47:26 +03:00
|
|
|
try testing.expect(initial_capacity >= 20);
|
2020-08-02 23:24:03 +02:00
|
|
|
var i: i32 = 0;
|
|
|
|
|
while (i < 20) : (i += 1) {
|
2021-05-04 20:47:26 +03:00
|
|
|
try testing.expect(map.fetchPutAssumeCapacity(i, i + 10) == null);
|
2020-08-02 23:24:03 +02:00
|
|
|
}
|
|
|
|
|
// shouldn't resize from putAssumeCapacity
|
2021-05-04 20:47:26 +03:00
|
|
|
try testing.expect(initial_capacity == map.capacity());
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
}
|
|
|
|
|
|
2024-02-25 23:31:53 -08:00
|
|
|
test "ensureUnusedCapacity with tombstones" {
|
2020-08-02 23:24:03 +02:00
|
|
|
var map = AutoHashMap(i32, i32).init(std.testing.allocator);
|
|
|
|
|
defer map.deinit();
|
|
|
|
|
|
|
|
|
|
var i: i32 = 0;
|
|
|
|
|
while (i < 100) : (i += 1) {
|
2021-09-16 18:22:04 -07:00
|
|
|
try map.ensureUnusedCapacity(1);
|
2020-08-02 23:24:03 +02:00
|
|
|
map.putAssumeCapacity(i, i);
|
|
|
|
|
_ = map.remove(i);
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
2024-02-25 23:31:53 -08:00
|
|
|
test "clearRetainingCapacity" {
|
2020-08-02 23:24:03 +02:00
|
|
|
var map = AutoHashMap(u32, u32).init(std.testing.allocator);
|
|
|
|
|
defer map.deinit();
|
|
|
|
|
|
|
|
|
|
map.clearRetainingCapacity();
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
|
2020-08-02 23:24:03 +02:00
|
|
|
try map.put(1, 1);
|
2021-05-04 20:47:26 +03:00
|
|
|
try expectEqual(map.get(1).?, 1);
|
|
|
|
|
try expectEqual(map.count(), 1);
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
|
2020-11-11 14:05:43 +02:00
|
|
|
map.clearRetainingCapacity();
|
|
|
|
|
map.putAssumeCapacity(1, 1);
|
2021-05-04 20:47:26 +03:00
|
|
|
try expectEqual(map.get(1).?, 1);
|
|
|
|
|
try expectEqual(map.count(), 1);
|
2020-11-11 14:05:43 +02:00
|
|
|
|
2020-08-02 23:24:03 +02:00
|
|
|
const cap = map.capacity();
|
2021-05-04 20:47:26 +03:00
|
|
|
try expect(cap > 0);
|
2020-08-02 23:24:03 +02:00
|
|
|
|
|
|
|
|
map.clearRetainingCapacity();
|
|
|
|
|
map.clearRetainingCapacity();
|
2021-05-04 20:47:26 +03:00
|
|
|
try expectEqual(map.count(), 0);
|
|
|
|
|
try expectEqual(map.capacity(), cap);
|
|
|
|
|
try expect(!map.contains(1));
|
2020-08-02 23:24:03 +02:00
|
|
|
}
|
|
|
|
|
|
2024-02-25 23:31:53 -08:00
|
|
|
test "grow" {
|
2020-08-02 23:24:03 +02:00
|
|
|
var map = AutoHashMap(u32, u32).init(std.testing.allocator);
|
|
|
|
|
defer map.deinit();
|
2020-07-04 01:31:29 +00:00
|
|
|
|
2020-08-02 23:24:03 +02:00
|
|
|
const growTo = 12456;
|
|
|
|
|
|
|
|
|
|
var i: u32 = 0;
|
|
|
|
|
while (i < growTo) : (i += 1) {
|
|
|
|
|
try map.put(i, i);
|
|
|
|
|
}
|
2021-05-04 20:47:26 +03:00
|
|
|
try expectEqual(map.count(), growTo);
|
2020-08-02 23:24:03 +02:00
|
|
|
|
|
|
|
|
i = 0;
|
|
|
|
|
var it = map.iterator();
|
|
|
|
|
while (it.next()) |kv| {
|
2021-06-03 15:39:26 -05:00
|
|
|
try expectEqual(kv.key_ptr.*, kv.value_ptr.*);
|
2020-08-02 23:24:03 +02:00
|
|
|
i += 1;
|
|
|
|
|
}
|
2021-05-04 20:47:26 +03:00
|
|
|
try expectEqual(i, growTo);
|
2020-08-02 23:24:03 +02:00
|
|
|
|
|
|
|
|
i = 0;
|
|
|
|
|
while (i < growTo) : (i += 1) {
|
2021-05-04 20:47:26 +03:00
|
|
|
try expectEqual(map.get(i).?, i);
|
2020-08-02 23:24:03 +02:00
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
2024-02-25 23:31:53 -08:00
|
|
|
test "clone" {
|
2020-08-02 23:24:03 +02:00
|
|
|
var map = AutoHashMap(u32, u32).init(std.testing.allocator);
|
|
|
|
|
defer map.deinit();
|
|
|
|
|
|
|
|
|
|
var a = try map.clone();
|
|
|
|
|
defer a.deinit();
|
|
|
|
|
|
2021-05-04 20:47:26 +03:00
|
|
|
try expectEqual(a.count(), 0);
|
2020-08-02 23:24:03 +02:00
|
|
|
|
|
|
|
|
try a.put(1, 1);
|
|
|
|
|
try a.put(2, 2);
|
|
|
|
|
try a.put(3, 3);
|
|
|
|
|
|
|
|
|
|
var b = try a.clone();
|
|
|
|
|
defer b.deinit();
|
|
|
|
|
|
2021-05-04 20:47:26 +03:00
|
|
|
try expectEqual(b.count(), 3);
|
2021-06-03 15:39:26 -05:00
|
|
|
try expectEqual(b.get(1).?, 1);
|
|
|
|
|
try expectEqual(b.get(2).?, 2);
|
|
|
|
|
try expectEqual(b.get(3).?, 3);
|
2023-05-08 17:59:06 +10:00
|
|
|
|
|
|
|
|
var original = AutoHashMap(i32, i32).init(std.testing.allocator);
|
|
|
|
|
defer original.deinit();
|
|
|
|
|
|
|
|
|
|
var i: u8 = 0;
|
|
|
|
|
while (i < 10) : (i += 1) {
|
|
|
|
|
try original.putNoClobber(i, i * 10);
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
var copy = try original.clone();
|
|
|
|
|
defer copy.deinit();
|
|
|
|
|
|
|
|
|
|
i = 0;
|
|
|
|
|
while (i < 10) : (i += 1) {
|
|
|
|
|
try testing.expect(copy.get(i).? == i * 10);
|
|
|
|
|
}
|
2020-08-02 23:24:03 +02:00
|
|
|
}
|
|
|
|
|
|
2024-02-25 23:31:53 -08:00
|
|
|
test "ensureTotalCapacity with existing elements" {
|
2020-08-02 23:24:03 +02:00
|
|
|
var map = AutoHashMap(u32, u32).init(std.testing.allocator);
|
|
|
|
|
defer map.deinit();
|
|
|
|
|
|
|
|
|
|
try map.put(0, 0);
|
2021-05-04 20:47:26 +03:00
|
|
|
try expectEqual(map.count(), 1);
|
|
|
|
|
try expectEqual(map.capacity(), @TypeOf(map).Unmanaged.minimal_capacity);
|
2020-08-02 23:24:03 +02:00
|
|
|
|
2021-09-16 18:22:04 -07:00
|
|
|
try map.ensureTotalCapacity(65);
|
2021-05-04 20:47:26 +03:00
|
|
|
try expectEqual(map.count(), 1);
|
|
|
|
|
try expectEqual(map.capacity(), 128);
|
2020-08-02 23:24:03 +02:00
|
|
|
}
|
|
|
|
|
|
2024-02-25 23:31:53 -08:00
|
|
|
test "ensureTotalCapacity satisfies max load factor" {
|
2020-08-02 23:24:03 +02:00
|
|
|
var map = AutoHashMap(u32, u32).init(std.testing.allocator);
|
|
|
|
|
defer map.deinit();
|
|
|
|
|
|
2021-09-16 18:22:04 -07:00
|
|
|
try map.ensureTotalCapacity(127);
|
2021-05-04 20:47:26 +03:00
|
|
|
try expectEqual(map.capacity(), 256);
|
2020-08-02 23:24:03 +02:00
|
|
|
}
|
|
|
|
|
|
2024-02-25 23:31:53 -08:00
|
|
|
test "remove" {
|
2020-08-02 23:24:03 +02:00
|
|
|
var map = AutoHashMap(u32, u32).init(std.testing.allocator);
|
|
|
|
|
defer map.deinit();
|
|
|
|
|
|
|
|
|
|
var i: u32 = 0;
|
|
|
|
|
while (i < 16) : (i += 1) {
|
|
|
|
|
try map.put(i, i);
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
i = 0;
|
|
|
|
|
while (i < 16) : (i += 1) {
|
|
|
|
|
if (i % 3 == 0) {
|
|
|
|
|
_ = map.remove(i);
|
2019-06-05 23:26:48 -07:00
|
|
|
}
|
2020-08-02 23:24:03 +02:00
|
|
|
}
|
2021-05-04 20:47:26 +03:00
|
|
|
try expectEqual(map.count(), 10);
|
2020-08-02 23:24:03 +02:00
|
|
|
var it = map.iterator();
|
|
|
|
|
while (it.next()) |kv| {
|
2021-06-03 15:39:26 -05:00
|
|
|
try expectEqual(kv.key_ptr.*, kv.value_ptr.*);
|
|
|
|
|
try expect(kv.key_ptr.* % 3 != 0);
|
2020-08-02 23:24:03 +02:00
|
|
|
}
|
2019-06-05 23:26:48 -07:00
|
|
|
|
2020-08-02 23:24:03 +02:00
|
|
|
i = 0;
|
|
|
|
|
while (i < 16) : (i += 1) {
|
|
|
|
|
if (i % 3 == 0) {
|
2021-05-04 20:47:26 +03:00
|
|
|
try expect(!map.contains(i));
|
2020-08-02 23:24:03 +02:00
|
|
|
} else {
|
2021-05-04 20:47:26 +03:00
|
|
|
try expectEqual(map.get(i).?, i);
|
2016-12-18 19:40:26 -05:00
|
|
|
}
|
2020-08-02 23:24:03 +02:00
|
|
|
}
|
2016-05-08 16:05:41 -07:00
|
|
|
}
|
|
|
|
|
|
2024-02-25 23:31:53 -08:00
|
|
|
test "reverse removes" {
|
2020-08-02 23:24:03 +02:00
|
|
|
var map = AutoHashMap(u32, u32).init(std.testing.allocator);
|
|
|
|
|
defer map.deinit();
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
|
2020-08-02 23:24:03 +02:00
|
|
|
var i: u32 = 0;
|
|
|
|
|
while (i < 16) : (i += 1) {
|
|
|
|
|
try map.putNoClobber(i, i);
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
}
|
|
|
|
|
|
2020-08-02 23:24:03 +02:00
|
|
|
i = 16;
|
|
|
|
|
while (i > 0) : (i -= 1) {
|
|
|
|
|
_ = map.remove(i - 1);
|
2021-05-04 20:47:26 +03:00
|
|
|
try expect(!map.contains(i - 1));
|
2020-08-02 23:24:03 +02:00
|
|
|
var j: u32 = 0;
|
|
|
|
|
while (j < i - 1) : (j += 1) {
|
2021-05-04 20:47:26 +03:00
|
|
|
try expectEqual(map.get(j).?, j);
|
2020-08-02 23:24:03 +02:00
|
|
|
}
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
}
|
|
|
|
|
|
2021-05-04 20:47:26 +03:00
|
|
|
try expectEqual(map.count(), 0);
|
2020-08-02 23:24:03 +02:00
|
|
|
}
|
|
|
|
|
|
2024-02-25 23:31:53 -08:00
|
|
|
test "multiple removes on same metadata" {
|
2020-08-02 23:24:03 +02:00
|
|
|
var map = AutoHashMap(u32, u32).init(std.testing.allocator);
|
|
|
|
|
defer map.deinit();
|
|
|
|
|
|
|
|
|
|
var i: u32 = 0;
|
|
|
|
|
while (i < 16) : (i += 1) {
|
|
|
|
|
try map.put(i, i);
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
}
|
|
|
|
|
|
2020-08-02 23:24:03 +02:00
|
|
|
_ = map.remove(7);
|
|
|
|
|
_ = map.remove(15);
|
|
|
|
|
_ = map.remove(14);
|
|
|
|
|
_ = map.remove(13);
|
2021-05-04 20:47:26 +03:00
|
|
|
try expect(!map.contains(7));
|
|
|
|
|
try expect(!map.contains(15));
|
|
|
|
|
try expect(!map.contains(14));
|
|
|
|
|
try expect(!map.contains(13));
|
2020-08-02 23:24:03 +02:00
|
|
|
|
|
|
|
|
i = 0;
|
|
|
|
|
while (i < 13) : (i += 1) {
|
|
|
|
|
if (i == 7) {
|
2021-05-04 20:47:26 +03:00
|
|
|
try expect(!map.contains(i));
|
2020-08-02 23:24:03 +02:00
|
|
|
} else {
|
2021-05-04 20:47:26 +03:00
|
|
|
try expectEqual(map.get(i).?, i);
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
2020-08-02 23:24:03 +02:00
|
|
|
try map.put(15, 15);
|
|
|
|
|
try map.put(13, 13);
|
|
|
|
|
try map.put(14, 14);
|
|
|
|
|
try map.put(7, 7);
|
|
|
|
|
i = 0;
|
|
|
|
|
while (i < 16) : (i += 1) {
|
2021-05-04 20:47:26 +03:00
|
|
|
try expectEqual(map.get(i).?, i);
|
2020-08-02 23:24:03 +02:00
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
2024-02-25 23:31:53 -08:00
|
|
|
test "put and remove loop in random order" {
|
2020-08-02 23:24:03 +02:00
|
|
|
var map = AutoHashMap(u32, u32).init(std.testing.allocator);
|
|
|
|
|
defer map.deinit();
|
|
|
|
|
|
2025-07-31 21:54:07 -07:00
|
|
|
var keys = std.array_list.Managed(u32).init(std.testing.allocator);
|
2020-08-02 23:24:03 +02:00
|
|
|
defer keys.deinit();
|
|
|
|
|
|
|
|
|
|
const size = 32;
|
|
|
|
|
const iterations = 100;
|
|
|
|
|
|
|
|
|
|
var i: u32 = 0;
|
|
|
|
|
while (i < size) : (i += 1) {
|
|
|
|
|
try keys.append(i);
|
|
|
|
|
}
|
2024-07-22 16:03:11 -07:00
|
|
|
var prng = std.Random.DefaultPrng.init(std.testing.random_seed);
|
2021-10-27 15:53:29 +01:00
|
|
|
const random = prng.random();
|
2020-08-02 23:24:03 +02:00
|
|
|
|
|
|
|
|
while (i < iterations) : (i += 1) {
|
2021-10-27 15:53:29 +01:00
|
|
|
random.shuffle(u32, keys.items);
|
2020-08-02 23:24:03 +02:00
|
|
|
|
|
|
|
|
for (keys.items) |key| {
|
|
|
|
|
try map.put(key, key);
|
|
|
|
|
}
|
2021-05-04 20:47:26 +03:00
|
|
|
try expectEqual(map.count(), size);
|
2020-08-02 23:24:03 +02:00
|
|
|
|
|
|
|
|
for (keys.items) |key| {
|
|
|
|
|
_ = map.remove(key);
|
|
|
|
|
}
|
2021-05-04 20:47:26 +03:00
|
|
|
try expectEqual(map.count(), 0);
|
2020-08-02 23:24:03 +02:00
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
2025-10-28 18:32:55 -07:00
|
|
|
test "remove many elements in random order" {
|
2020-08-02 23:24:03 +02:00
|
|
|
const Map = AutoHashMap(u32, u32);
|
2025-10-28 18:32:55 -07:00
|
|
|
const n = 1000 * 100;
|
2020-08-02 23:24:03 +02:00
|
|
|
var map = Map.init(std.heap.page_allocator);
|
|
|
|
|
defer map.deinit();
|
|
|
|
|
|
2025-07-31 21:54:07 -07:00
|
|
|
var keys = std.array_list.Managed(u32).init(std.heap.page_allocator);
|
2020-08-02 23:24:03 +02:00
|
|
|
defer keys.deinit();
|
|
|
|
|
|
|
|
|
|
var i: u32 = 0;
|
|
|
|
|
while (i < n) : (i += 1) {
|
|
|
|
|
keys.append(i) catch unreachable;
|
|
|
|
|
}
|
|
|
|
|
|
2024-07-22 16:03:11 -07:00
|
|
|
var prng = std.Random.DefaultPrng.init(std.testing.random_seed);
|
2021-10-27 15:53:29 +01:00
|
|
|
const random = prng.random();
|
|
|
|
|
random.shuffle(u32, keys.items);
|
2020-08-02 23:24:03 +02:00
|
|
|
|
|
|
|
|
for (keys.items) |key| {
|
|
|
|
|
map.put(key, key) catch unreachable;
|
|
|
|
|
}
|
|
|
|
|
|
2021-10-27 15:53:29 +01:00
|
|
|
random.shuffle(u32, keys.items);
|
2020-08-02 23:24:03 +02:00
|
|
|
i = 0;
|
|
|
|
|
while (i < n) : (i += 1) {
|
|
|
|
|
const key = keys.items[i];
|
|
|
|
|
_ = map.remove(key);
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
2024-02-25 23:31:53 -08:00
|
|
|
test "put" {
|
2020-08-02 23:24:03 +02:00
|
|
|
var map = AutoHashMap(u32, u32).init(std.testing.allocator);
|
|
|
|
|
defer map.deinit();
|
|
|
|
|
|
|
|
|
|
var i: u32 = 0;
|
|
|
|
|
while (i < 16) : (i += 1) {
|
2021-02-27 13:49:02 +11:00
|
|
|
try map.put(i, i);
|
2020-08-02 23:24:03 +02:00
|
|
|
}
|
|
|
|
|
|
|
|
|
|
i = 0;
|
|
|
|
|
while (i < 16) : (i += 1) {
|
2021-05-04 20:47:26 +03:00
|
|
|
try expectEqual(map.get(i).?, i);
|
2020-08-02 23:24:03 +02:00
|
|
|
}
|
|
|
|
|
|
|
|
|
|
i = 0;
|
|
|
|
|
while (i < 16) : (i += 1) {
|
|
|
|
|
try map.put(i, i * 16 + 1);
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
i = 0;
|
|
|
|
|
while (i < 16) : (i += 1) {
|
2021-05-04 20:47:26 +03:00
|
|
|
try expectEqual(map.get(i).?, i * 16 + 1);
|
2020-08-02 23:24:03 +02:00
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
2024-02-25 23:31:53 -08:00
|
|
|
test "putAssumeCapacity" {
|
2020-11-11 00:01:40 +02:00
|
|
|
var map = AutoHashMap(u32, u32).init(std.testing.allocator);
|
|
|
|
|
defer map.deinit();
|
2020-12-09 13:54:26 +02:00
|
|
|
|
2021-09-16 18:22:04 -07:00
|
|
|
try map.ensureTotalCapacity(20);
|
2020-11-11 00:01:40 +02:00
|
|
|
var i: u32 = 0;
|
|
|
|
|
while (i < 20) : (i += 1) {
|
|
|
|
|
map.putAssumeCapacityNoClobber(i, i);
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
i = 0;
|
|
|
|
|
var sum = i;
|
|
|
|
|
while (i < 20) : (i += 1) {
|
2021-06-03 15:39:26 -05:00
|
|
|
sum += map.getPtr(i).?.*;
|
2020-11-11 00:01:40 +02:00
|
|
|
}
|
2021-05-04 20:47:26 +03:00
|
|
|
try expectEqual(sum, 190);
|
2020-11-11 00:01:40 +02:00
|
|
|
|
|
|
|
|
i = 0;
|
|
|
|
|
while (i < 20) : (i += 1) {
|
|
|
|
|
map.putAssumeCapacity(i, 1);
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
i = 0;
|
|
|
|
|
sum = i;
|
|
|
|
|
while (i < 20) : (i += 1) {
|
|
|
|
|
sum += map.get(i).?;
|
|
|
|
|
}
|
2021-05-04 20:47:26 +03:00
|
|
|
try expectEqual(sum, 20);
|
2020-11-11 00:01:40 +02:00
|
|
|
}
|
|
|
|
|
|
2024-02-25 23:31:53 -08:00
|
|
|
test "repeat putAssumeCapacity/remove" {
|
2021-12-14 13:25:23 -08:00
|
|
|
var map = AutoHashMap(u32, u32).init(std.testing.allocator);
|
|
|
|
|
defer map.deinit();
|
|
|
|
|
|
|
|
|
|
try map.ensureTotalCapacity(20);
|
|
|
|
|
const limit = map.unmanaged.available;
|
|
|
|
|
|
|
|
|
|
var i: u32 = 0;
|
|
|
|
|
while (i < limit) : (i += 1) {
|
|
|
|
|
map.putAssumeCapacityNoClobber(i, i);
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
// Repeatedly delete/insert an entry without resizing the map.
|
|
|
|
|
// Put to different keys so entries don't land in the just-freed slot.
|
|
|
|
|
i = 0;
|
2021-12-17 16:56:43 -07:00
|
|
|
while (i < 10 * limit) : (i += 1) {
|
2021-12-14 13:25:23 -08:00
|
|
|
try testing.expect(map.remove(i));
|
|
|
|
|
if (i % 2 == 0) {
|
|
|
|
|
map.putAssumeCapacityNoClobber(limit + i, i);
|
|
|
|
|
} else {
|
|
|
|
|
map.putAssumeCapacity(limit + i, i);
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
2021-12-17 16:56:43 -07:00
|
|
|
i = 9 * limit;
|
|
|
|
|
while (i < 10 * limit) : (i += 1) {
|
|
|
|
|
try expectEqual(map.get(limit + i), i);
|
2021-12-14 13:25:23 -08:00
|
|
|
}
|
|
|
|
|
try expectEqual(map.unmanaged.available, 0);
|
|
|
|
|
try expectEqual(map.unmanaged.count(), limit);
|
|
|
|
|
}
|
|
|
|
|
|
2024-02-25 23:31:53 -08:00
|
|
|
test "getOrPut" {
|
2020-08-02 23:24:03 +02:00
|
|
|
var map = AutoHashMap(u32, u32).init(std.testing.allocator);
|
|
|
|
|
defer map.deinit();
|
|
|
|
|
|
|
|
|
|
var i: u32 = 0;
|
|
|
|
|
while (i < 10) : (i += 1) {
|
|
|
|
|
try map.put(i * 2, 2);
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
}
|
|
|
|
|
|
2020-08-02 23:24:03 +02:00
|
|
|
i = 0;
|
|
|
|
|
while (i < 20) : (i += 1) {
|
2021-06-09 21:35:42 -04:00
|
|
|
_ = try map.getOrPutValue(i, 1);
|
reimplement std.HashMap
* breaking changes to the API. Some of the weird decisions from before
are changed to what would be more expected.
- `get` returns `?V`, use `getEntry` for the old API.
- `put` returns `!void`, use `fetchPut` for the old API.
* HashMap now has a comptime parameter of whether to store hashes with
entries. AutoHashMap has heuristics on whether to set this parameter.
For example, for integers, it is false, since equality checking is
cheap, but for strings, it is true, since equality checking is
probably expensive.
* The implementation has a separate array for entry_index /
distance_from_start_index. Entries no longer has holes; it is an
ArrayList, and iteration is simpler and more cache coherent.
This is inspired by Python's new dictionaries.
* HashMap is separated into an "unmanaged" and a "managed" API. The
unmanaged API is where the actual implementation is; the managed API
wraps it and provides a more convenient API, storing the allocator.
* Memory usage: When there are less than or equal to 8 entries, HashMap
now incurs only a single pointer-size integer as overhead, opposed to
using an ArrayList.
* Since the entries array is separate from the indexes array, the holes
in the indexes array take up less room than the holes in the entries
array otherwise would. However the entries array also allocates
additional capacity for appending into the array.
* HashMap now maintains insertion order. Deletion performs a "swap
remove". It's now possible to modify the HashMap while iterating.
2020-07-03 23:57:24 +00:00
|
|
|
}
|
|
|
|
|
|
2020-08-02 23:24:03 +02:00
|
|
|
i = 0;
|
|
|
|
|
var sum = i;
|
|
|
|
|
while (i < 20) : (i += 1) {
|
|
|
|
|
sum += map.get(i).?;
|
|
|
|
|
}
|
|
|
|
|
|
2021-05-04 20:47:26 +03:00
|
|
|
try expectEqual(sum, 30);
|
2020-08-02 23:24:03 +02:00
|
|
|
}
|
|
|
|
|
|
2024-02-25 23:31:53 -08:00
|
|
|
test "basic hash map usage" {
|
2020-01-29 22:06:26 -06:00
|
|
|
var map = AutoHashMap(i32, i32).init(std.testing.allocator);
|
2016-05-08 16:05:41 -07:00
|
|
|
defer map.deinit();
|
2016-05-09 15:07:38 -07:00
|
|
|
|
2021-05-04 20:47:26 +03:00
|
|
|
try testing.expect((try map.fetchPut(1, 11)) == null);
|
|
|
|
|
try testing.expect((try map.fetchPut(2, 22)) == null);
|
|
|
|
|
try testing.expect((try map.fetchPut(3, 33)) == null);
|
|
|
|
|
try testing.expect((try map.fetchPut(4, 44)) == null);
|
2018-01-09 00:07:01 -05:00
|
|
|
|
2019-06-12 23:48:46 -06:00
|
|
|
try map.putNoClobber(5, 55);
|
2021-05-04 20:47:26 +03:00
|
|
|
try testing.expect((try map.fetchPut(5, 66)).?.value == 55);
|
|
|
|
|
try testing.expect((try map.fetchPut(5, 55)).?.value == 66);
|
2018-08-03 17:22:17 -04:00
|
|
|
|
|
|
|
|
const gop1 = try map.getOrPut(5);
|
2021-05-04 20:47:26 +03:00
|
|
|
try testing.expect(gop1.found_existing == true);
|
2021-06-03 15:39:26 -05:00
|
|
|
try testing.expect(gop1.value_ptr.* == 55);
|
|
|
|
|
gop1.value_ptr.* = 77;
|
|
|
|
|
try testing.expect(map.getEntry(5).?.value_ptr.* == 77);
|
2018-08-03 17:22:17 -04:00
|
|
|
|
|
|
|
|
const gop2 = try map.getOrPut(99);
|
2021-05-04 20:47:26 +03:00
|
|
|
try testing.expect(gop2.found_existing == false);
|
2021-06-03 15:39:26 -05:00
|
|
|
gop2.value_ptr.* = 42;
|
|
|
|
|
try testing.expect(map.getEntry(99).?.value_ptr.* == 42);
|
2016-05-09 15:07:38 -07:00
|
|
|
|
2018-11-29 09:10:15 +01:00
|
|
|
const gop3 = try map.getOrPutValue(5, 5);
|
2021-06-03 15:39:26 -05:00
|
|
|
try testing.expect(gop3.value_ptr.* == 77);
|
2018-11-29 09:10:15 +01:00
|
|
|
|
|
|
|
|
const gop4 = try map.getOrPutValue(100, 41);
|
2021-06-03 15:39:26 -05:00
|
|
|
try testing.expect(gop4.value_ptr.* == 41);
|
2018-11-29 09:10:15 +01:00
|
|
|
|
2021-05-04 20:47:26 +03:00
|
|
|
try testing.expect(map.contains(2));
|
2021-06-03 15:39:26 -05:00
|
|
|
try testing.expect(map.getEntry(2).?.value_ptr.* == 22);
|
2021-05-04 20:47:26 +03:00
|
|
|
try testing.expect(map.get(2).? == 22);
|
2019-04-06 14:15:12 -07:00
|
|
|
|
2021-06-03 15:39:26 -05:00
|
|
|
const rmv1 = map.fetchRemove(2);
|
2021-05-04 20:47:26 +03:00
|
|
|
try testing.expect(rmv1.?.key == 2);
|
|
|
|
|
try testing.expect(rmv1.?.value == 22);
|
2021-06-03 15:39:26 -05:00
|
|
|
try testing.expect(map.fetchRemove(2) == null);
|
|
|
|
|
try testing.expect(map.remove(2) == false);
|
2021-05-04 20:47:26 +03:00
|
|
|
try testing.expect(map.getEntry(2) == null);
|
|
|
|
|
try testing.expect(map.get(2) == null);
|
2019-06-12 23:39:53 -04:00
|
|
|
|
2021-06-03 15:39:26 -05:00
|
|
|
try testing.expect(map.remove(3) == true);
|
2016-05-08 16:05:41 -07:00
|
|
|
}
|
|
|
|
|
|
2024-02-25 23:31:53 -08:00
|
|
|
test "getOrPutAdapted" {
|
2021-06-18 13:52:30 +08:00
|
|
|
const AdaptedContext = struct {
|
|
|
|
|
fn eql(self: @This(), adapted_key: []const u8, test_key: u64) bool {
|
2021-06-19 21:10:22 -04:00
|
|
|
_ = self;
|
2021-06-18 13:52:30 +08:00
|
|
|
return std.fmt.parseInt(u64, adapted_key, 10) catch unreachable == test_key;
|
|
|
|
|
}
|
|
|
|
|
fn hash(self: @This(), adapted_key: []const u8) u64 {
|
2021-06-19 21:10:22 -04:00
|
|
|
_ = self;
|
2021-06-18 13:52:30 +08:00
|
|
|
const key = std.fmt.parseInt(u64, adapted_key, 10) catch unreachable;
|
|
|
|
|
return (AutoContext(u64){}).hash(key);
|
|
|
|
|
}
|
|
|
|
|
};
|
|
|
|
|
var map = AutoHashMap(u64, u64).init(testing.allocator);
|
|
|
|
|
defer map.deinit();
|
|
|
|
|
|
|
|
|
|
const keys = [_][]const u8{
|
|
|
|
|
"1231",
|
|
|
|
|
"4564",
|
|
|
|
|
"7894",
|
|
|
|
|
"1132",
|
|
|
|
|
"65235",
|
|
|
|
|
"95462",
|
|
|
|
|
"0112305",
|
|
|
|
|
"00658",
|
|
|
|
|
"0",
|
|
|
|
|
"2",
|
|
|
|
|
};
|
|
|
|
|
|
|
|
|
|
var real_keys: [keys.len]u64 = undefined;
|
|
|
|
|
|
2023-02-18 09:02:57 -07:00
|
|
|
inline for (keys, 0..) |key_str, i| {
|
2021-06-18 13:52:30 +08:00
|
|
|
const result = try map.getOrPutAdapted(key_str, AdaptedContext{});
|
|
|
|
|
try testing.expect(!result.found_existing);
|
|
|
|
|
real_keys[i] = std.fmt.parseInt(u64, key_str, 10) catch unreachable;
|
|
|
|
|
result.key_ptr.* = real_keys[i];
|
|
|
|
|
result.value_ptr.* = i * 2;
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
try testing.expectEqual(map.count(), keys.len);
|
|
|
|
|
|
2023-02-18 09:02:57 -07:00
|
|
|
inline for (keys, 0..) |key_str, i| {
|
2023-01-02 03:35:56 -05:00
|
|
|
const result = map.getOrPutAssumeCapacityAdapted(key_str, AdaptedContext{});
|
2021-06-18 13:52:30 +08:00
|
|
|
try testing.expect(result.found_existing);
|
|
|
|
|
try testing.expectEqual(real_keys[i], result.key_ptr.*);
|
|
|
|
|
try testing.expectEqual(@as(u64, i) * 2, result.value_ptr.*);
|
2021-08-30 21:32:34 -07:00
|
|
|
try testing.expectEqual(real_keys[i], map.getKeyAdapted(key_str, AdaptedContext{}).?);
|
2021-06-18 13:52:30 +08:00
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
2024-02-25 23:31:53 -08:00
|
|
|
test "ensureUnusedCapacity" {
|
2021-07-12 18:32:02 +02:00
|
|
|
var map = AutoHashMap(u64, u64).init(testing.allocator);
|
|
|
|
|
defer map.deinit();
|
|
|
|
|
|
|
|
|
|
try map.ensureUnusedCapacity(32);
|
|
|
|
|
const capacity = map.capacity();
|
|
|
|
|
try map.ensureUnusedCapacity(32);
|
|
|
|
|
|
|
|
|
|
// Repeated ensureUnusedCapacity() calls with no insertions between
|
|
|
|
|
// should not change the capacity.
|
|
|
|
|
try testing.expectEqual(capacity, map.capacity());
|
|
|
|
|
}
|
2021-11-15 12:54:14 +00:00
|
|
|
|
2024-02-25 23:31:53 -08:00
|
|
|
test "removeByPtr" {
|
2021-11-15 12:54:14 +00:00
|
|
|
var map = AutoHashMap(i32, u64).init(testing.allocator);
|
|
|
|
|
defer map.deinit();
|
|
|
|
|
|
|
|
|
|
var i: i32 = undefined;
|
|
|
|
|
|
|
|
|
|
i = 0;
|
|
|
|
|
while (i < 10) : (i += 1) {
|
|
|
|
|
try map.put(i, 0);
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
try testing.expect(map.count() == 10);
|
|
|
|
|
|
|
|
|
|
i = 0;
|
|
|
|
|
while (i < 10) : (i += 1) {
|
2023-07-19 18:17:03 +01:00
|
|
|
const key_ptr = map.getKeyPtr(i);
|
|
|
|
|
try testing.expect(key_ptr != null);
|
2021-11-15 12:54:14 +00:00
|
|
|
|
2023-07-19 18:17:03 +01:00
|
|
|
if (key_ptr) |ptr| {
|
2021-11-15 12:54:14 +00:00
|
|
|
map.removeByPtr(ptr);
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
try testing.expect(map.count() == 0);
|
|
|
|
|
}
|
|
|
|
|
|
2024-02-25 23:31:53 -08:00
|
|
|
test "removeByPtr 0 sized key" {
|
2021-11-15 12:54:14 +00:00
|
|
|
var map = AutoHashMap(u0, u64).init(testing.allocator);
|
|
|
|
|
defer map.deinit();
|
|
|
|
|
|
|
|
|
|
try map.put(0, 0);
|
|
|
|
|
|
|
|
|
|
try testing.expect(map.count() == 1);
|
|
|
|
|
|
2023-07-19 18:17:03 +01:00
|
|
|
const key_ptr = map.getKeyPtr(0);
|
|
|
|
|
try testing.expect(key_ptr != null);
|
2021-11-15 12:54:14 +00:00
|
|
|
|
2023-07-19 18:17:03 +01:00
|
|
|
if (key_ptr) |ptr| {
|
2021-11-15 12:54:14 +00:00
|
|
|
map.removeByPtr(ptr);
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
try testing.expect(map.count() == 0);
|
|
|
|
|
}
|
2023-06-09 12:52:36 -07:00
|
|
|
|
2024-02-25 23:31:53 -08:00
|
|
|
test "repeat fetchRemove" {
|
2024-09-02 22:32:21 +01:00
|
|
|
var map: AutoHashMapUnmanaged(u64, void) = .empty;
|
2023-06-09 12:52:36 -07:00
|
|
|
defer map.deinit(testing.allocator);
|
|
|
|
|
|
|
|
|
|
try map.ensureTotalCapacity(testing.allocator, 4);
|
|
|
|
|
|
|
|
|
|
map.putAssumeCapacity(0, {});
|
|
|
|
|
map.putAssumeCapacity(1, {});
|
|
|
|
|
map.putAssumeCapacity(2, {});
|
|
|
|
|
map.putAssumeCapacity(3, {});
|
|
|
|
|
|
|
|
|
|
// fetchRemove() should make slots available.
|
|
|
|
|
var i: usize = 0;
|
|
|
|
|
while (i < 10) : (i += 1) {
|
|
|
|
|
try testing.expect(map.fetchRemove(3) != null);
|
|
|
|
|
map.putAssumeCapacity(3, {});
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
try testing.expect(map.get(0) != null);
|
|
|
|
|
try testing.expect(map.get(1) != null);
|
|
|
|
|
try testing.expect(map.get(2) != null);
|
|
|
|
|
try testing.expect(map.get(3) != null);
|
|
|
|
|
}
|
2024-03-20 11:13:50 -07:00
|
|
|
|
|
|
|
|
test "getOrPut allocation failure" {
|
2024-09-02 22:32:21 +01:00
|
|
|
var map: std.StringHashMapUnmanaged(void) = .empty;
|
2024-03-20 11:13:50 -07:00
|
|
|
try testing.expectError(error.OutOfMemory, map.getOrPut(std.testing.failing_allocator, "hello"));
|
|
|
|
|
}
|
2024-08-08 11:59:22 -07:00
|
|
|
|
2025-10-28 18:32:55 -07:00
|
|
|
test "rehash" {
|
2024-08-08 11:59:22 -07:00
|
|
|
var map = AutoHashMap(usize, usize).init(std.testing.allocator);
|
|
|
|
|
defer map.deinit();
|
|
|
|
|
|
|
|
|
|
var prng = std.Random.DefaultPrng.init(0);
|
|
|
|
|
const random = prng.random();
|
|
|
|
|
|
2025-10-28 18:32:55 -07:00
|
|
|
const count = 4 * random.intRangeLessThan(u32, 100_000, 500_000);
|
2024-08-08 11:59:22 -07:00
|
|
|
|
|
|
|
|
for (0..count) |i| {
|
|
|
|
|
try map.put(i, i);
|
|
|
|
|
if (i % 3 == 0) {
|
|
|
|
|
try expectEqual(map.remove(i), true);
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
map.rehash();
|
|
|
|
|
|
|
|
|
|
try expectEqual(map.count(), count * 2 / 3);
|
|
|
|
|
|
|
|
|
|
for (0..count) |i| {
|
|
|
|
|
if (i % 3 == 0) {
|
|
|
|
|
try expectEqual(map.get(i), null);
|
|
|
|
|
} else {
|
|
|
|
|
try expectEqual(map.get(i).?, i);
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
}
|
