lib/ui/src/tree/map.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2
3 const abi = @import("../abi/root.zig");
4
5 const Node = abi.Node;
6
7 /// `absent` is 0, the value of an empty slot.
8 /// An occupied slot stores its node index plus 1.
9 pub const absent: u32 = 0;
10
11 /// `Map` finds a node index by node id through open addressing with linear probing.
12 /// It stores node indices, not ids. `lookup` and `insert` read the id through the node array
13 /// passed to them, so every call must pass the array the map was filled from.
14 pub const Map = struct {
15 /// `Map.slots` must have a power-of-two length, which `lookup` and `insert` assert.
16 slots: []u32 = &.{},
17 /// `Map.count` is the number of occupied slots.
18 count: u32 = 0,
19
20 /// `reset` empties every slot and sets `count` to 0.
21 pub fn reset(self: *Map) void {
22 @memset(self.slots, absent);
23 self.count = 0;
24 }
25
26 /// `lookup` returns the index of the node whose id equals `id`, or null.
27 /// A map with no slots answers null. Each call probes at most `slots.len` slots.
28 pub fn lookup(self: *const Map, nodes: []const Node, id: u64) ?u32 {
29 if (self.slots.len == 0) return null;
30 std.debug.assert(std.math.isPowerOfTwo(self.slots.len));
31 const mask = self.slots.len - 1;
32 var index = @as(usize, hash(id)) & mask;
33 var probe: usize = 0;
34 while (probe < self.slots.len) : (probe += 1) {
35 const slot = self.slots[index];
36 if (slot == absent) return null;
37 std.debug.assert(slot - 1 < nodes.len);
38 if (nodes[slot - 1].id == id) return slot - 1;
39 index = (index + 1) & mask;
40 }
41 return null;
42 }
43
44 /// `insert` adds node `index` under that node's id and returns true. When a node
45 /// with the same id is already present, it returns false and leaves the map unchanged.
46 /// It asserts that a free slot remains.
47 pub fn insert(self: *Map, nodes: []const Node, index: u32) bool {
48 std.debug.assert(self.slots.len > 0);
49 std.debug.assert(std.math.isPowerOfTwo(self.slots.len));
50 std.debug.assert(index < nodes.len);
51 const id = nodes[index].id;
52 if (self.lookup(nodes, id) != null) return false;
53 std.debug.assert(self.count < self.slots.len);
54 const mask = self.slots.len - 1;
55 var slot = @as(usize, hash(id)) & mask;
56 var probe: usize = 0;
57 while (probe < self.slots.len) : (probe += 1) {
58 if (self.slots[slot] == absent) {
59 self.slots[slot] = index + 1;
60 self.count += 1;
61 return true;
62 }
63 slot = (slot + 1) & mask;
64 }
65 unreachable;
66 }
67 };
68
69 /// `hash` gives the slot where probing for an id starts, before `lookup` and
70 /// `insert` mask it by `slots.len - 1`.
71 pub fn hash(id: u64) u32 {
72 var mixed = id;
73 mixed ^= mixed >> 33;
74 mixed *%= 0xff51afd7ed558ccd;
75 mixed ^= mixed >> 33;
76 mixed *%= 0xc4ceb9fe1a85ec53;
77 mixed ^= mixed >> 33;
78 return @truncate(mixed);
79 }
80
81 test "an empty map answers absent for every id" {
82 var slots: [8]u32 = @splat(0);
83 var map = Map{ .slots = &slots };
84 map.reset();
85 const nodes = [_]Node{.{ .id = 7 }};
86 try std.testing.expectEqual(@as(?u32, null), map.lookup(&nodes, 7));
87 try std.testing.expectEqual(@as(u32, 0), map.count);
88 }
89
90 test "an inserted id resolves to its own node index" {
91 var slots: [16]u32 = @splat(0);
92 var map = Map{ .slots = &slots };
93 map.reset();
94 const nodes = [_]Node{
95 .{ .id = 1000 },
96 .{ .id = 2000 },
97 .{ .id = 3000 },
98 };
99 for (0..nodes.len) |index| try std.testing.expect(map.insert(&nodes, @intCast(index)));
100 try std.testing.expectEqual(@as(u32, 3), map.count);
101 try std.testing.expectEqual(@as(?u32, 0), map.lookup(&nodes, 1000));
102 try std.testing.expectEqual(@as(?u32, 1), map.lookup(&nodes, 2000));
103 try std.testing.expectEqual(@as(?u32, 2), map.lookup(&nodes, 3000));
104 try std.testing.expectEqual(@as(?u32, null), map.lookup(&nodes, 4000));
105 }
106
107 test "a repeated id refuses its second insertion" {
108 var slots: [16]u32 = @splat(0);
109 var map = Map{ .slots = &slots };
110 map.reset();
111 const nodes = [_]Node{ .{ .id = 42 }, .{ .id = 42 } };
112 try std.testing.expect(map.insert(&nodes, 0));
113 try std.testing.expect(!map.insert(&nodes, 1));
114 try std.testing.expectEqual(@as(u32, 1), map.count);
115 }
116
117 test "a full map still resolves every id it holds" {
118 var slots: [32]u32 = @splat(0);
119 var map = Map{ .slots = &slots };
120 map.reset();
121 var nodes: [16]Node = undefined;
122 for (&nodes, 0..) |*node, index| node.* = .{ .id = @as(u64, index) * 0x1_0000_0001 };
123 for (0..nodes.len) |index| try std.testing.expect(map.insert(&nodes, @intCast(index)));
124 for (0..nodes.len) |index| {
125 const resolved = map.lookup(&nodes, nodes[index].id);
126 try std.testing.expectEqual(@as(?u32, @intCast(index)), resolved);
127 }
128 try std.testing.expectEqual(@as(u32, 16), map.count);
129 }
130
131 test "the mixer spreads consecutive ids across distinct slots" {
132 var seen: u32 = 0;
133 var index: u64 = 0;
134 while (index < 8) : (index += 1) {
135 const slot = @as(u32, 1) << @intCast(hash(index) & 31);
136 seen |= slot;
137 }
138 try std.testing.expect(@popCount(seen) >= 6);
139 try std.testing.expect(hash(0) != hash(1));
140 }