While learning Zig as part of my game engine project I was looking for a way to store data in my entity system that is performant, cache friendly, compact, versatile and usable on the stack.
What I have come up with is a compile time evaluated function that returns a struct based on minimum key Size (if offset is useful to decrease memory), maximum key Size, type of the key to determine the function parameters of the struct, size of the data array and type of the data array. Based on this the function generates the smallest possible types that can fit the parameters to decrease memory significantly. Keys are used as index to the keys array and the actual values represent indices for the data array. This concept is nothing new for data and performance oriented design but usually this would have to be implemented for every data type individually, in Zig this can be implemented just once and then be created with all data types needed while still keeping memory usage low. Every operation is O(1) and on deletion the last element gets moved to the free slot, very simple conceptually.
I have personally added an extra “links” array as big as the data array to store keys in the same index as the data array so the whole “Map Array” is bidirectional and lets me check not only which data belongs to which key but also which key belongs to which data in case I added data without needing a key for it. Some form of this might even be useful as addition to the standard library but thats not up for me to decide because I made this for the domain that most needs it.
Just wanted to share this idea because I feel like dynamically generating types is a super underrated thing for less memory footprint and this data structure (at least to me) seems incredibly useful. Im sharing just a few bits of my code as proof of concept so my post stays small. This is also my first post here so sorry if Im not following traditional post conventions.
fn FindSmallestIntType(number: usize) type {
return std.math.IntFittingRange(0, number - 1);
}
pub fn CreateMapArray(comptime elementType: type, comptime size: u32, comptime keyType: type, comptime keyMax: u32, comptime keyMin: u32) type {
comptime {
if (keyMax < size) @compileError("MapArray: keyMax must be >= size");
if (keyMin > keyMax) @compileError("MapArray: keyMax must be > keyMin");
}
const elementLimit = size - 1;
const usedKeyCount = keyMax - keyMin + 1;
const sentinel = usedKeyCount + 1;
const smallKeyType = FindSmallestIntType(sentinel);
const indexType = FindSmallestIntType(size + 1); //
return struct {
const Self = @This();
count: indexType = 0,
keys: [usedKeyCount]smallKeyType = .{sentinel} ** usedKeyCount,
links: [size]smallKeyType = .{sentinel} ** size,
elements: [size]elementType = undefined,
pub fn set(self: *Self, key: keyType, element: elementType) void {
const castedKey: smallKeyType = @truncate(key - keyMin);
if (self.keys[castedKey] == sentinel) {
const index = self.count;
self.keys[castedKey] = index;
self.links[index] = castedKey;
self.elements[index] = element;
self.count += 1;
} else {
const index = self.keys[castedKey];
self.elements[index] = element;
}
}
pub fn setMany(self: *Self, keys: []const keyType, elements: []const elementType) void {
for (keys, elements) |key, element| self.set(key, element);
}
pub fn overwriteAtIndex(self: *Self, index: u32, element: elementType) void {
self.elements[index] = element;
}
pub fn append(self: *Self, element: elementType) void {
self.elements[self.count] = element;
self.links[self.count] = sentinel;
self.count += 1;
}
pub fn appendMany(self: *Self, elements: []const elementType) void {
for (elements) |element| self.append(element);
}
pub fn link(self: *Self, index: u32, key: keyType) void {
const castedKey: smallKeyType = @truncate(key - keyMin);
const oldKey = self.links[index];
if (oldKey != sentinel) self.keys[oldKey] = sentinel;
self.keys[castedKey] = @truncate(index);
self.links[index] = castedKey;
}
pub fn unlink(self: *Self, key: keyType) void {
const castedKey: smallKeyType = @truncate(key - keyMin);
self.unlinkAtIndex(self.keys[castedKey]);
}
pub fn unlinkAtIndex(self: *Self, index: u32) void {
const key = self.links[index];
if (key != sentinel) {
self.keys[key] = sentinel;
self.links[index] = sentinel;
}
}
pub fn removeLast(self: *Self) void {
const key = self.links[self.count - 1];
if (key != sentinel) self.keys[key] = sentinel;
self.links[self.count - 1] = sentinel;
self.count -= 1;
}
pub fn removeAtKey(self: *Self, key: keyType) void {
self.removeAtIndex(self.keys[key - keyMin]);
}
pub fn removeAtIndex(self: *Self, index: u32) void {
const keyIndex = self.links[index];
if (keyIndex != sentinel) self.keys[keyIndex] = sentinel;
const lastIndex = self.count - 1;
self.count -= 1;
if (index != lastIndex) {
const lastKey = self.links[lastIndex];
// Move last element to removed position
self.elements[index] = self.elements[lastIndex];
self.links[index] = lastKey;
// Update key mapping if last element has a key
if (lastKey != sentinel) self.keys[lastKey] = @truncate(index);
}
self.links[lastIndex] = sentinel;
}
pub fn swap(self: *Self, key1: keyType, key2: keyType) void {
self.swapAtIndex(self.keys[key1 - keyMin], self.keys[key2 - keyMin]);
}
pub fn isKeyUsed(self: *Self, key: keyType) bool {
const castedKey: smallKeyType = @truncate(key - keyMin);
return self.keys[castedKey] != sentinel;
}
pub inline fn isKeyValid(_: *Self, key: keyType) bool {
return key >= keyMin and (key - keyMin) < usedKeyCount;
}
pub inline fn isIndexUsed(self: *Self, index: u32) bool {
return index < self.count;
}
pub inline fn isIndexValid(_: *Self, index: u32) bool {
return index <= elementLimit;
}
pub inline fn isLinked(self: *Self, index: u32) bool {
return self.links[index] != sentinel;
}
pub inline fn getElements(self: *Self) []elementType {
return self.elements[0..self.count];
}
pub inline fn get(self: *Self, key: keyType) elementType {
return self.elements[self.keys[(key - keyMin)]];
}
pub inline fn getPtr(self: *Self, key: keyType) *elementType {
return &self.elements[self.keys[(key - keyMin)]];
}
pub inline fn getAtIndex(self: *Self, index: u32) elementType {
return self.elements[index];
}
pub inline fn getPtrAtIndex(self: *Self, index: u32) *elementType {
return &self.elements[index];
}
};
}