A map keyed by an enum, backed by a bitfield and a dense array. If the enum is exhaustive but not dense, a mapping will be constructed from enum values to dense indices. This type does no dynamic allocation and can be copied by value.
pub fn EnumMap(comptime E: type, comptime V: type) typepub fn EnumMap(comptime E: type, comptime V: type) type {
return struct {
const Self = @This();
/// The index mapping for this map
pub const Indexer = EnumIndexer(E);
/// The key type used to index this map
pub const Key = Indexer.Key;
/// The value type stored in this map
pub const Value = V;
/// The number of possible keys in the map
pub const len = Indexer.count;
const BitSet = std.bit_set.Static(Indexer.count);
/// Bits determining whether items are in the map
bits: BitSet = .empty,
/// Values of items in the map. If the associated
/// bit is zero, the value is undefined.
values: [Indexer.count]Value = undefined,
/// Initializes the map using a sparse struct of optionals
pub fn init(init_values: EnumFieldStruct(E, ?Value, @as(?Value, null))) Self {
@setEvalBranchQuota(2 * @typeInfo(E).@"enum".field_names.len);
var result: Self = .{};
if (@typeInfo(E).@"enum".mode == .exhaustive) {
inline for (0..Self.len) |i| {
const key = comptime Indexer.keyForIndex(i);
const tag = @tagName(key);
if (@field(init_values, tag)) |*v| {
result.bits.set(i);
result.values[i] = v.*;
}
}
} else {
inline for (std.meta.fieldNames(E)) |field_name| {
const key = @field(E, field_name);
if (@field(init_values, field_name)) |*v| {
const i = comptime Indexer.indexOf(key);
result.bits.set(i);
result.values[i] = v.*;
}
}
}
return result;
}
/// Initializes a full mapping with all keys set to value.
/// Consider using EnumArray instead if the map will remain full.
pub fn initFull(value: Value) Self {
var result: Self = .{
.bits = .full,
.values = undefined,
};
@memset(&result.values, value);
return result;
}
/// Initializes a full mapping with supplied values.
/// Consider using EnumArray instead if the map will remain full.
pub fn initFullWith(init_values: EnumFieldStruct(E, Value, null)) Self {
return initFullWithDefault(null, init_values);
}
/// Initializes a full mapping with a provided default.
/// Consider using EnumArray instead if the map will remain full.
pub fn initFullWithDefault(comptime default: ?Value, init_values: EnumFieldStruct(E, Value, default)) Self {
@setEvalBranchQuota(2 * @typeInfo(E).@"enum".field_names.len);
var result: Self = .{
.bits = .full,
.values = undefined,
};
inline for (0..Self.len) |i| {
const key = comptime Indexer.keyForIndex(i);
const tag = @tagName(key);
result.values[i] = @field(init_values, tag);
}
return result;
}
/// The number of items in the map.
pub fn count(self: *const Self) usize {
return self.bits.count();
}
/// Checks if the map contains an item.
pub fn contains(self: *const Self, key: Key) bool {
return self.bits.isSet(Indexer.indexOf(key));
}
/// Gets the value associated with a key.
/// If the key is not in the map, returns null.
pub fn get(self: *const Self, key: Key) ?Value {
const index = Indexer.indexOf(key);
return if (self.bits.isSet(index)) self.values[index] else null;
}
/// Gets the value associated with a key, which must
/// exist in the map.
pub fn getAssertContains(self: *const Self, key: Key) Value {
const index = Indexer.indexOf(key);
assert(self.bits.isSet(index));
return self.values[index];
}
/// Gets the address of the value associated with a key.
/// If the key is not in the map, returns null.
pub fn getPtr(self: *Self, key: Key) ?*Value {
const index = Indexer.indexOf(key);
return if (self.bits.isSet(index)) &self.values[index] else null;
}
/// Gets the address of the const value associated with a key.
/// If the key is not in the map, returns null.
pub fn getPtrConst(self: *const Self, key: Key) ?*const Value {
const index = Indexer.indexOf(key);
return if (self.bits.isSet(index)) &self.values[index] else null;
}
/// Gets the address of the value associated with a key.
/// The key must be present in the map.
pub fn getPtrAssertContains(self: *Self, key: Key) *Value {
const index = Indexer.indexOf(key);
assert(self.bits.isSet(index));
return &self.values[index];
}
/// Gets the address of the const value associated with a key.
/// The key must be present in the map.
pub fn getPtrConstAssertContains(self: *const Self, key: Key) *const Value {
const index = Indexer.indexOf(key);
assert(self.bits.isSet(index));
return &self.values[index];
}
/// Adds the key to the map with the supplied value.
/// If the key is already in the map, overwrites the value.
pub fn put(self: *Self, key: Key, value: Value) void {
const index = Indexer.indexOf(key);
self.bits.set(index);
self.values[index] = value;
}
/// Adds the key to the map with an undefined value.
/// If the key is already in the map, the value becomes undefined.
/// A pointer to the value is returned, which should be
/// used to initialize the value.
pub fn putUninitialized(self: *Self, key: Key) *Value {
const index = Indexer.indexOf(key);
self.bits.set(index);
self.values[index] = undefined;
return &self.values[index];
}
/// Sets the value associated with the key in the map,
/// and returns the old value. If the key was not in
/// the map, returns null.
pub fn fetchPut(self: *Self, key: Key, value: Value) ?Value {
const index = Indexer.indexOf(key);
const result: ?Value = if (self.bits.isSet(index)) self.values[index] else null;
self.bits.set(index);
self.values[index] = value;
return result;
}
/// Removes a key from the map. If the key was not in the map,
/// does nothing.
pub fn remove(self: *Self, key: Key) void {
const index = Indexer.indexOf(key);
self.bits.unset(index);
self.values[index] = undefined;
}
/// Removes a key from the map, and returns the old value.
/// If the key was not in the map, returns null.
pub fn fetchRemove(self: *Self, key: Key) ?Value {
const index = Indexer.indexOf(key);
const result: ?Value = if (self.bits.isSet(index)) self.values[index] else null;
self.bits.unset(index);
self.values[index] = undefined;
return result;
}
/// Returns an iterator over the map, which visits items in index order.
/// Modifications to the underlying map may or may not be observed by
/// the iterator, but will not invalidate it.
pub fn iterator(self: *Self) Iterator {
return .{
.inner = self.bits.iterator(.{}),
.values = &self.values,
};
}
/// An entry in the map.
pub const Entry = struct {
/// The key associated with this entry.
/// Modifying this key will not change the map.
key: Key,
/// A pointer to the value in the map associated
/// with this key. Modifications through this
/// pointer will modify the underlying data.
value: *Value,
};
pub const Iterator = struct {
inner: BitSet.Iterator(.{}),
values: *[Indexer.count]Value,
pub fn next(self: *Iterator) ?Entry {
return if (self.inner.next()) |index|
Entry{
.key = Indexer.keyForIndex(index),
.value = &self.values[index],
}
else
null;
}
};
};
}