1const std = @import("std");
2const expect = std.testing.expect;
3const expectEqual = std.testing.expectEqual;
4const builtin = @import("builtin");
5
6fn ShardedTable(comptime Key: type, comptime mask_bit_count: comptime_int, comptime V: type) type {
7 const key_bits = @typeInfo(Key).int.bits;
8 std.debug.assert(Key == @Int(.unsigned, key_bits));
9 std.debug.assert(key_bits >= mask_bit_count);
10 const shard_key_bits = mask_bit_count;
11 const ShardKey = @Int(.unsigned, mask_bit_count);
12 const shift_amount = key_bits - shard_key_bits;
13 return struct {
14 const Self = @This();
15 shards: [1 << shard_key_bits]?*Node,
16
17 pub fn create() Self {
18 return .{ .shards = @splat(null) };
19 }
20
21 fn getShardKey(key: Key) ShardKey {
22 // https://github.com/ziglang/zig/issues/1544
23 // this special case is needed because you can't u32 >> 32.
24 if (ShardKey == u0) return 0;
25
26 // this can be u1 >> u0
27 const shard_key = key >> shift_amount;
28
29 // TODO: https://github.com/ziglang/zig/issues/1544
30 // This cast could be implicit if we teach the compiler that
31 // u32 >> 30 -> u2
32 return @as(ShardKey, @intCast(shard_key));
33 }
34
35 pub fn put(self: *Self, node: *Node) void {
36 const shard_key = Self.getShardKey(node.key);
37 node.next = self.shards[shard_key];
38 self.shards[shard_key] = node;
39 }
40
41 pub fn get(self: *Self, key: Key) ?*Node {
42 const shard_key = Self.getShardKey(key);
43 var maybe_node = self.shards[shard_key];
44 while (maybe_node) |node| : (maybe_node = node.next) {
45 if (node.key == key) return node;
46 }
47 return null;
48 }
49
50 pub const Node = struct {
51 key: Key,
52 value: V,
53 next: ?*Node,
54
55 pub fn init(self: *Node, key: Key, value: V) void {
56 self.key = key;
57 self.value = value;
58 self.next = null;
59 }
60 };
61 };
62}
63
64test "sharded table" {
65 if (builtin.zig_backend == .stage2_aarch64) return error.SkipZigTest;
66 if (builtin.zig_backend == .stage2_arm) return error.SkipZigTest;
67 if (builtin.zig_backend == .stage2_sparc64) return error.SkipZigTest; // TODO
68 if (builtin.zig_backend == .stage2_spirv) return error.SkipZigTest;
69
70 // realistic 16-way sharding
71 try testShardedTable(u32, 4, 8);
72
73 try testShardedTable(u5, 0, 32); // ShardKey == u0
74 try testShardedTable(u5, 2, 32);
75 try testShardedTable(u5, 5, 32);
76
77 try testShardedTable(u1, 0, 2);
78 try testShardedTable(u1, 1, 2); // this does u1 >> u0
79
80 try testShardedTable(u0, 0, 1);
81}
82
83fn testShardedTable(comptime Key: type, comptime mask_bit_count: comptime_int, comptime node_count: comptime_int) !void {
84 const Table = ShardedTable(Key, mask_bit_count, void);
85
86 var table = Table.create();
87 var node_buffer: [node_count]Table.Node = undefined;
88 for (&node_buffer, 0..) |*node, i| {
89 const key = @as(Key, @intCast(i));
90 try expect(table.get(key) == null);
91 node.init(key, {});
92 table.put(node);
93 }
94
95 for (&node_buffer, 0..) |*node, i| {
96 try expect(table.get(@as(Key, @intCast(i))) == node);
97 }
98}
99
100// #2225
101test "comptime shr of BigInt" {
102 comptime {
103 const n0 = 0xdeadbeef0000000000000000;
104 try expect(n0 >> 64 == 0xdeadbeef);
105 const n1 = 17908056155735594659;
106 try expect(n1 >> 64 == 0);
107 }
108}
109
110test "comptime shift safety check" {
111 _ = @as(usize, 42) << @sizeOf(usize);
112}
113
114test "Saturating Shift Left where lhs is of a computed type" {
115 if (builtin.zig_backend == .stage2_aarch64) return error.SkipZigTest;
116 if (builtin.zig_backend == .stage2_arm) return error.SkipZigTest; // TODO
117 if (builtin.zig_backend == .stage2_sparc64) return error.SkipZigTest; // TODO
118 if (builtin.zig_backend == .stage2_spirv) return error.SkipZigTest;
119 if (builtin.zig_backend == .stage2_riscv64) return error.SkipZigTest;
120
121 const S = struct {
122 pub fn FixedPoint(comptime ValueType: type) type {
123 return struct {
124 value: ValueType,
125 exponent: ShiftType,
126
127 const ShiftType = @Int(.signed, @typeInfo(std.math.Log2Int(ValueType)).int.bits);
128
129 pub fn shiftExponent(self: @This(), shift: ShiftType) @This() {
130 const shiftAbs = @abs(shift);
131 return .{ .value = if (shift >= 0) self.value >> shiftAbs else self.value <<| shiftAbs, .exponent = self.exponent + shift };
132 }
133 };
134 }
135 };
136
137 const FP = S.FixedPoint(i32);
138
139 const value = (FP{
140 .value = 1,
141 .exponent = 1,
142 }).shiftExponent(-1);
143
144 try expect(value.value == 2);
145 try expect(value.exponent == 0);
146}
147
148test "Saturating Shift Left" {
149 if (builtin.zig_backend == .stage2_aarch64) return error.SkipZigTest;
150 if (builtin.zig_backend == .stage2_sparc64) return error.SkipZigTest;
151 if (builtin.zig_backend == .stage2_spirv) return error.SkipZigTest;
152 if (builtin.zig_backend == .stage2_riscv64) return error.SkipZigTest;
153
154 const S = struct {
155 fn shlSat(x: anytype, y: std.math.Log2Int(@TypeOf(x))) @TypeOf(x) {
156 return x <<| y;
157 }
158
159 fn testType(comptime T: type) !void {
160 comptime var rhs: std.math.Log2Int(T) = 0;
161 inline while (true) : (rhs += 1) {
162 comptime var lhs: T = std.math.minInt(T);
163 inline while (true) : (lhs += 1) {
164 try expectEqual(lhs <<| rhs, shlSat(lhs, rhs));
165 if (lhs == std.math.maxInt(T)) break;
166 }
167 if (rhs == @bitSizeOf(T) - 1) break;
168 }
169 }
170 };
171
172 try S.testType(u2);
173 try S.testType(i2);
174 try S.testType(u3);
175 try S.testType(i3);
176 try S.testType(u4);
177 try S.testType(i4);
178
179 try expectEqual(0xfffffffffffffff0fffffffffffffff0, S.shlSat(@as(u128, 0x0fffffffffffffff0fffffffffffffff), 4));
180 try expectEqual(0xffffffffffffffffffffffffffffffff, S.shlSat(@as(u128, 0x0fffffffffffffff0fffffffffffffff), 5));
181 try expectEqual(-0x80000000000000000000000000000000, S.shlSat(@as(i128, -0x0fffffffffffffff0fffffffffffffff), 5));
182
183 try expectEqual(51146728248377216718956089012931236753385031969422887335676427626502090568823039920051095192592252455482604439493126109519019633529459266458258243583, S.shlSat(@as(i495, 0x2fe6bc5448c55ce18252e2c9d44777505dfe63ff249a8027a6626c7d8dd9893fd5731e51474727be556f757facb586a4e04bbc0148c6c7ad692302f46fbd), 0x31));
184 try expectEqual(-57896044618658097711785492504343953926634992332820282019728792003956564819968, S.shlSat(@as(i256, -0x53d4148cee74ea43477a65b3daa7b8fdadcbf4508e793f4af113b8d8da5a7eb6), 0x91));
185 try expectEqual(170141183460469231731687303715884105727, S.shlSat(@as(i128, 0x2fe6bc5448c55ce18252e2c9d4477750), 0x31));
186 try expectEqual(0, S.shlSat(@as(i128, 0), 127));
187}