lib/simd/src/cuckoo/family.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const builder = @import("builder.zig");
3 const local = @import("local.zig");
4 const optimizer = @import("optimizer.zig");
5 const simd = @import("../root.zig");
6 const hash_mod = simd.hash;
7 const random = simd.random;
8 const tag = simd.tag;
9
10 pub const CuckooConfigError = error{
11 CapacityExceeded,
12 InvalidEpsilon,
13 };
14
15 pub const CuckooTableError = error{
16 FingerprintSlotsTooSmall,
17 FingerprintsRequireMinimumBuckets,
18 FingerprintsRequireU32,
19 FingerprintSlotsUnavailable,
20 FullSlotsUnavailable,
21 SlotsTooSmall,
22 };
23
24 pub const CuckooBuildAlgo = enum {
25 hopcroft_karp,
26 min_cost,
27 local_search,
28 };
29
30 pub fn CuckooFamily(
31 comptime HashType: type,
32 comptime bucket_size_value: usize,
33 comptime minimum_bucket_count_value: usize,
34 ) type {
35 if (bucket_size_value == 0 or !std.math.isPowerOfTwo(bucket_size_value)) {
36 @compileError("Cuckoo bucket size must be a nonzero power of two");
37 }
38 if (minimum_bucket_count_value == 0 or
39 !std.math.isPowerOfTwo(minimum_bucket_count_value))
40 {
41 @compileError("Cuckoo minimum bucket count must be a nonzero power of two");
42 }
43 const KeyType = HashType.Lane;
44 const key_info = @typeInfo(KeyType);
45 if (key_info != .int or key_info.int.signedness != .unsigned) {
46 @compileError("Cuckoo hash lanes must be unsigned integers");
47 }
48 if (bucket_size_value > std.math.maxInt(KeyType) or
49 bucket_size_value > std.math.maxInt(usize) / 2)
50 {
51 @compileError("Cuckoo bucket size exceeds the supported index range");
52 }
53 return struct {
54 const Family = @This();
55
56 pub const Hash = HashType;
57 pub const Key = KeyType;
58 pub const bucket_size = bucket_size_value;
59 pub const log_bucket_size = std.math.log2_int(usize, bucket_size);
60 pub const minimum_bucket_count = minimum_bucket_count_value;
61 pub const empty_key = std.math.maxInt(Key);
62 pub const empty_fingerprint: u16 = 0;
63 pub const primary_tag: u16 = 0x4000;
64 pub const secondary_tag: u16 = 0x8000;
65 pub const minimum_fingerprint_bucket_count: usize = 262_144;
66 pub const BuildPlan = builder.Plan(Family);
67 pub const Builder = builder.Builder(Family);
68 pub const OptimizedBuildPlan = optimizer.Plan(Family);
69 pub const Optimizer = optimizer.Optimizer(Family);
70 pub const LocalBuildPlan = local.Plan(Family);
71 pub const LocalSearch = local.Search(Family);
72 pub const BuildStats = builder.CuckooBuildStats;
73
74 pub const Config = struct {
75 num_keys: usize = 0,
76 num_slots: usize = 0,
77 num_buckets: usize = 0,
78 bucket_bits: usize = 0,
79 epsilon: f64 = 0,
80 bucket_mask: Key = 0,
81
82 const Self = @This();
83
84 pub fn init(num_keys: usize, epsilon: f64) CuckooConfigError!Self {
85 if (!std.math.isFinite(epsilon) or epsilon < 0) return error.InvalidEpsilon;
86 if (num_keys > std.math.maxInt(u32)) return error.CapacityExceeded;
87 const scaled = @as(f64, @floatFromInt(num_keys)) * (1 + epsilon);
88 const maximum_exclusive: f64 = @floatFromInt(std.math.maxInt(usize));
89 if (!std.math.isFinite(scaled) or scaled >= maximum_exclusive) {
90 return error.CapacityExceeded;
91 }
92 const raw_slots = @as(usize, @intFromFloat(scaled)) + 1;
93 const required_buckets = std.math.divCeil(
94 usize,
95 raw_slots,
96 bucket_size,
97 ) catch unreachable;
98 const at_least = @max(minimum_bucket_count, required_buckets);
99 const num_buckets = std.math.ceilPowerOfTwo(usize, at_least) catch
100 return error.CapacityExceeded;
101 if (num_buckets - 1 > std.math.maxInt(Key)) return error.CapacityExceeded;
102 const num_slots = std.math.mul(usize, num_buckets, bucket_size) catch
103 return error.CapacityExceeded;
104 if (num_slots > std.math.maxInt(u32)) return error.CapacityExceeded;
105 return .{
106 .num_keys = num_keys,
107 .num_slots = num_slots,
108 .num_buckets = num_buckets,
109 .bucket_bits = std.math.log2_int(usize, num_buckets),
110 .epsilon = epsilon,
111 .bucket_mask = @intCast(num_buckets - 1),
112 };
113 }
114 };
115
116 pub const LookupOne = struct {
117 primary_hash: Key,
118 secondary_hash: Key,
119 primary_slot: usize,
120 secondary_slot: usize,
121 };
122
123 pub fn LookupVectors(comptime D: type) type {
124 requireTag(D);
125 return struct {
126 primary_slots: D.Vector,
127 secondary_slots: D.Vector,
128 primary_hashes: D.Vector,
129 };
130 }
131
132 pub const Table = struct {
133 config: Config,
134 hash_primary: Hash,
135 hash_secondary: Hash,
136 full_slots: []Key,
137 fingerprint_slots: []u16,
138 num_primary: u32,
139
140 const Self = @This();
141
142 pub fn init(
143 config: Config,
144 hash_primary: Hash,
145 hash_secondary: Hash,
146 full_storage: []Key,
147 num_primary: u32,
148 ) CuckooTableError!Self {
149 if (full_storage.len < config.num_slots) return error.SlotsTooSmall;
150 std.debug.assert(num_primary <= config.num_keys);
151 return .{
152 .config = config,
153 .hash_primary = hash_primary,
154 .hash_secondary = hash_secondary,
155 .full_slots = full_storage[0..config.num_slots],
156 .fingerprint_slots = emptySlice(u16),
157 .num_primary = num_primary,
158 };
159 }
160
161 pub fn isEmpty(self: Self) bool {
162 return self.config.num_keys == 0;
163 }
164
165 pub fn allocatedBytes(self: Self) usize {
166 return self.full_slots.len * @sizeOf(Key) +
167 self.fingerprint_slots.len * @sizeOf(u16);
168 }
169
170 pub fn slots(self: Self) []const Key {
171 return self.full_slots;
172 }
173
174 pub fn mutableSlots(self: *Self) []Key {
175 return self.full_slots;
176 }
177
178 pub fn fingerprints(self: Self) []const u16 {
179 return self.fingerprint_slots;
180 }
181
182 pub fn hasU16Slots(self: Self) bool {
183 return self.fingerprint_slots.len != 0;
184 }
185
186 pub fn primaryBucketOffset(self: Self, key: Key) usize {
187 return self.bucketOffset(self.hash_primary.hash(key));
188 }
189
190 pub fn secondaryBucketOffset(self: Self, key: Key) usize {
191 return self.bucketOffset(self.hash_secondary.hash(key));
192 }
193
194 pub fn queryOne(self: Self, key: Key) bool {
195 if (self.queryBucket(key, self.primaryBucketOffset(key))) return true;
196 return self.queryBucket(key, self.secondaryBucketOffset(key));
197 }
198
199 pub fn queryBucket(self: Self, key: Key, offset: usize) bool {
200 std.debug.assert(self.full_slots.len == self.config.num_slots);
201 std.debug.assert(offset + bucket_size <= self.full_slots.len);
202 const D = tag.CappedTag(Key, bucket_size);
203 const needle: D.Vector = @splat(key);
204 var index: usize = 0;
205 while (index < bucket_size) : (index += D.lane_count) {
206 const values: D.Vector = self.full_slots[offset + index ..][0..D.lane_count].*;
207 if (@reduce(.Or, values == needle)) return true;
208 }
209 return false;
210 }
211
212 pub fn lookupOneSlot(self: Self, key: Key) LookupOne {
213 const primary_hash = self.hash_primary.hash(key);
214 const secondary_hash = self.hash_secondary.hash(key);
215 return .{
216 .primary_hash = primary_hash,
217 .secondary_hash = secondary_hash,
218 .primary_slot = self.bucketOffset(primary_hash),
219 .secondary_slot = self.bucketOffset(secondary_hash),
220 };
221 }
222
223 pub fn lookupSlotsAndHash(
224 self: Self,
225 comptime D: type,
226 keys: D.Vector,
227 ) LookupVectors(D) {
228 requireTag(D);
229 const mask: D.Vector = @splat(self.config.bucket_mask);
230 const scale: D.Vector = @splat(@as(Key, @intCast(bucket_size)));
231 const primary_hashes = self.hash_primary.oneVec(D, keys);
232 const secondary_hashes = self.hash_secondary.oneVec(D, keys);
233 return .{
234 .primary_slots = (primary_hashes & mask) *% scale,
235 .secondary_slots = (secondary_hashes & mask) *% scale,
236 .primary_hashes = primary_hashes,
237 };
238 }
239
240 pub fn queryBatch(
241 self: Self,
242 comptime precompute_secondary: bool,
243 comptime D: type,
244 keys: D.Vector,
245 ) D.Mask {
246 if (comptime Key != u32) @compileError("Cuckoo batch queries require u32 keys");
247 requireTag(D);
248 const mask: D.Vector = @splat(self.config.bucket_mask);
249 const scale: D.Vector = @splat(@as(u32, @intCast(bucket_size)));
250 const primary_hashes = self.hash_primary.oneVec(D, keys);
251 const primary_offsets = (primary_hashes & mask) *% scale;
252 const secondary_offsets = if (precompute_secondary)
253 (self.hash_secondary.oneVec(D, keys) & mask) *% scale
254 else
255 @as(D.Vector, @splat(0));
256 var found: D.Mask = @splat(false);
257 inline for (0..D.lane_count) |lane| {
258 found[lane] = self.queryBucket(keys[lane], primary_offsets[lane]);
259 }
260 inline for (0..D.lane_count) |lane| {
261 if (!found[lane]) {
262 const offset = if (precompute_secondary)
263 secondary_offsets[lane]
264 else
265 self.secondaryBucketOffset(keys[lane]);
266 found[lane] = self.queryBucket(keys[lane], offset);
267 }
268 }
269 return !found;
270 }
271
272 pub fn buildU16Slots(
273 self: Self,
274 output: []u16,
275 ) CuckooTableError!Self {
276 if (comptime Key != u32) return error.FingerprintsRequireU32;
277 if (self.config.num_buckets < minimum_fingerprint_bucket_count) {
278 return error.FingerprintsRequireMinimumBuckets;
279 }
280 if (self.full_slots.len != self.config.num_slots) {
281 return error.FullSlotsUnavailable;
282 }
283 if (output.len < self.config.num_slots) {
284 return error.FingerprintSlotsTooSmall;
285 }
286 const fingerprint_storage = output[0..self.config.num_slots];
287 @memset(fingerprint_storage, empty_fingerprint);
288 for (self.full_slots, 0..) |key, slot| {
289 if (key == empty_key) continue;
290 const bucket = slot / bucket_size;
291 const primary_hash = self.hash_primary.hash(key);
292 if ((primary_hash & self.config.bucket_mask) == bucket) {
293 fingerprint_storage[slot] = fingerprintU16(primary_hash, primary_tag);
294 } else {
295 const secondary_hash = self.hash_secondary.hash(key);
296 std.debug.assert(
297 (secondary_hash & self.config.bucket_mask) == bucket,
298 );
299 fingerprint_storage[slot] = fingerprintU16(
300 secondary_hash,
301 secondary_tag,
302 );
303 }
304 }
305 return .{
306 .config = self.config,
307 .hash_primary = self.hash_primary,
308 .hash_secondary = self.hash_secondary,
309 .full_slots = emptySlice(Key),
310 .fingerprint_slots = fingerprint_storage,
311 .num_primary = self.num_primary,
312 };
313 }
314
315 pub fn queryBucketU16(self: Self, fingerprint: u16, offset: usize) bool {
316 if (self.fingerprint_slots.len != self.config.num_slots) return false;
317 std.debug.assert(offset + bucket_size <= self.fingerprint_slots.len);
318 const D = tag.CappedTag(u16, bucket_size);
319 const needle: D.Vector = @splat(fingerprint);
320 var index: usize = 0;
321 while (index < bucket_size) : (index += D.lane_count) {
322 const remaining = self.fingerprint_slots[offset + index ..];
323 const values: D.Vector = remaining[0..D.lane_count].*;
324 if (@reduce(.Or, values == needle)) return true;
325 }
326 return false;
327 }
328
329 pub fn queryOneU16(self: Self, key: u32) CuckooTableError!bool {
330 if (comptime Key != u32) return error.FingerprintsRequireU32;
331 if (!self.hasU16Slots()) return error.FingerprintSlotsUnavailable;
332 const primary_hash = self.hash_primary.hash(key);
333 const primary = fingerprintU16(primary_hash, primary_tag);
334 const primary_offset = self.bucketOffset(primary_hash);
335 if (self.queryBucketU16(primary, primary_offset)) return true;
336 const secondary_hash = self.hash_secondary.hash(key);
337 const secondary = fingerprintU16(secondary_hash, secondary_tag);
338 const secondary_offset = self.bucketOffset(secondary_hash);
339 return self.queryBucketU16(secondary, secondary_offset);
340 }
341
342 pub fn queryBatchU16(
343 self: Self,
344 comptime precompute_secondary: bool,
345 comptime D: type,
346 keys: D.Vector,
347 ) CuckooTableError!D.Mask {
348 if (comptime Key != u32) return error.FingerprintsRequireU32;
349 if (!self.hasU16Slots()) return error.FingerprintSlotsUnavailable;
350 requireTag(D);
351 const mask: D.Vector = @splat(self.config.bucket_mask);
352 const scale: D.Vector = @splat(@as(u32, @intCast(bucket_size)));
353 const primary_hashes = self.hash_primary.oneVec(D, keys);
354 const primary_offsets = (primary_hashes & mask) *% scale;
355 const secondary_hashes = if (precompute_secondary)
356 self.hash_secondary.oneVec(D, keys)
357 else
358 @as(D.Vector, @splat(0));
359 const secondary_offsets = (secondary_hashes & mask) *% scale;
360 var found: D.Mask = @splat(false);
361 inline for (0..D.lane_count) |lane| {
362 const fingerprint = fingerprintU16(primary_hashes[lane], primary_tag);
363 found[lane] = self.queryBucketU16(
364 fingerprint,
365 primary_offsets[lane],
366 );
367 }
368 inline for (0..D.lane_count) |lane| {
369 if (!found[lane]) {
370 const secondary_hash = if (precompute_secondary)
371 secondary_hashes[lane]
372 else
373 self.hash_secondary.hash(keys[lane]);
374 const offset = if (precompute_secondary)
375 secondary_offsets[lane]
376 else
377 self.bucketOffset(secondary_hash);
378 found[lane] = self.queryBucketU16(
379 fingerprintU16(secondary_hash, secondary_tag),
380 offset,
381 );
382 }
383 }
384 return !found;
385 }
386
387 fn bucketOffset(self: Self, hash: Key) usize {
388 const bucket: usize = @intCast(hash & self.config.bucket_mask);
389 return bucket * bucket_size;
390 }
391 };
392
393 pub fn fingerprintU16(hash: u32, tag_value: u16) u16 {
394 return @truncate((hash >> 18) | tag_value);
395 }
396
397 fn requireTag(comptime D: type) void {
398 if (comptime D.Lane != Key) @compileError("Cuckoo tag lane type mismatch");
399 }
400 };
401 }
402
403 pub const DefaultCuckoo = CuckooFamily(hash_mod.WeakTwoMul, 16, 1);
404 pub const CuckooConfig = DefaultCuckoo.Config;
405 pub const CuckooTable = DefaultCuckoo.Table;
406 pub const CuckooBuildPlan = DefaultCuckoo.BuildPlan;
407 pub const CuckooBuilder = DefaultCuckoo.Builder;
408 pub const CuckooOptimizedBuildPlan = DefaultCuckoo.OptimizedBuildPlan;
409 pub const CuckooOptimizer = DefaultCuckoo.Optimizer;
410 pub const CuckooLocalBuildPlan = DefaultCuckoo.LocalBuildPlan;
411 pub const CuckooLocalSearch = DefaultCuckoo.LocalSearch;
412
413 pub fn cuckooScratchLen(
414 num_keys: usize,
415 epsilon: f64,
416 algorithm: CuckooBuildAlgo,
417 ) builder.CuckooBuildError!usize {
418 return switch (algorithm) {
419 .hopcroft_karp => (try CuckooBuildPlan.inspect(num_keys, epsilon)).scratch_len,
420 .min_cost => (try CuckooOptimizedBuildPlan.inspect(num_keys, epsilon)).scratch_len,
421 .local_search => (try CuckooLocalBuildPlan.inspect(num_keys, epsilon)).scratch_len,
422 };
423 }
424
425 pub fn cuckooSlotsLen(num_keys: usize, epsilon: f64) builder.CuckooBuildError!usize {
426 return (try CuckooBuildPlan.inspect(num_keys, epsilon)).slots_len;
427 }
428
429 pub fn cuckooOptimizedScratchLen(
430 num_keys: usize,
431 epsilon: f64,
432 ) builder.CuckooBuildError!usize {
433 return (try CuckooOptimizedBuildPlan.inspect(num_keys, epsilon)).scratch_len;
434 }
435
436 pub fn cuckooLocalScratchLen(
437 num_keys: usize,
438 epsilon: f64,
439 ) builder.CuckooBuildError!usize {
440 return (try CuckooLocalBuildPlan.inspect(num_keys, epsilon)).scratch_len;
441 }
442
443 pub fn buildCuckoo(
444 scratch: []u32,
445 slots: []u32,
446 keys: []const u32,
447 epsilon: f64,
448 max_attempts: u32,
449 algorithm: CuckooBuildAlgo,
450 stats: ?*builder.CuckooBuildStats,
451 ) builder.CuckooBuildError!CuckooTable {
452 return switch (algorithm) {
453 .hopcroft_karp => blk: {
454 const plan = try CuckooBuildPlan.inspect(keys.len, epsilon);
455 break :blk plan.build(scratch, slots, keys, max_attempts, stats);
456 },
457 .min_cost => blk: {
458 const plan = try CuckooOptimizedBuildPlan.inspect(keys.len, epsilon);
459 break :blk plan.build(scratch, slots, keys, max_attempts, stats);
460 },
461 .local_search => blk: {
462 const plan = try CuckooLocalBuildPlan.inspect(keys.len, epsilon);
463 break :blk plan.build(scratch, slots, keys, max_attempts, stats);
464 },
465 };
466 }
467
468 fn emptySlice(comptime T: type) []T {
469 return @constCast((&[_]T{})[0..]);
470 }
471
472 fn fixtureTable(
473 comptime Family: type,
474 keys: []const Family.Key,
475 epsilon: f64,
476 slots: []Family.Key,
477 ) !Family.Table {
478 const config = try Family.Config.init(keys.len, epsilon);
479 if (slots.len < config.num_slots) return error.FixtureSlotsTooSmall;
480 const used = slots[0..config.num_slots];
481 @memset(used, Family.empty_key);
482 const engine = random.AesCtrEngine.initDeterministic();
483 const primary = Family.Hash.initSeed(&engine, 0);
484 const secondary = Family.Hash.initSeed(&engine, 1);
485 var num_primary: u32 = 0;
486 for (keys) |key| {
487 const primary_bucket: usize = @intCast(primary.hash(key) & config.bucket_mask);
488 const primary_offset = primary_bucket * Family.bucket_size;
489 if (firstEmpty(Family, used, primary_offset)) |slot| {
490 used[slot] = key;
491 num_primary += 1;
492 continue;
493 }
494 const secondary_bucket: usize = @intCast(secondary.hash(key) & config.bucket_mask);
495 const secondary_offset = secondary_bucket * Family.bucket_size;
496 if (firstEmpty(Family, used, secondary_offset)) |slot| {
497 used[slot] = key;
498 continue;
499 }
500 return error.FixtureBuildFailed;
501 }
502 return Family.Table.init(config, primary, secondary, used, num_primary);
503 }
504
505 fn firstEmpty(comptime Family: type, slots: []const Family.Key, offset: usize) ?usize {
506 for (slots[offset .. offset + Family.bucket_size], 0..) |slot, index| {
507 if (slot == Family.empty_key) return offset + index;
508 }
509 return null;
510 }
511
512 test "Highway generic Cuckoo configuration rounds slots and buckets" {
513 const empty = try CuckooConfig.init(0, 0.25);
514 try std.testing.expectEqual(@as(usize, 1), empty.num_buckets);
515 try std.testing.expectEqual(@as(usize, 16), empty.num_slots);
516 const small = try CuckooConfig.init(100, 0.25);
517 try std.testing.expectEqual(@as(usize, 8), small.num_buckets);
518 try std.testing.expectEqual(@as(usize, 128), small.num_slots);
519 try std.testing.expectEqual(@as(usize, 3), small.bucket_bits);
520 const medium = try CuckooConfig.init(10_000, 0.25);
521 try std.testing.expectEqual(@as(usize, 1024), medium.num_buckets);
522 try std.testing.expectEqual(@as(usize, 16_384), medium.num_slots);
523 const Min = CuckooFamily(hash_mod.WeakTwoMul, 16, 262_144);
524 const constrained = try Min.Config.init(100, 0.25);
525 try std.testing.expectEqual(@as(usize, 262_144), constrained.num_buckets);
526 try std.testing.expectError(error.InvalidEpsilon, CuckooConfig.init(1, -0.1));
527 }
528
529 test "Highway generic Cuckoo u64 scalar lookup preserves bounded offsets" {
530 const Family = CuckooFamily(hash_mod.Moremur, 16, 1);
531 const config = try Family.Config.init(32, 0.25);
532 var slots: [64]u64 = @splat(Family.empty_key);
533 const table = try Family.Table.init(
534 config,
535 Family.Hash.initKey(0x0123_4567_89ab_cdef),
536 Family.Hash.initKey(0xfedc_ba98_7654_3210),
537 &slots,
538 0,
539 );
540 const key: u64 = 0xf00d_cafe_dead_beef;
541 const lookup = table.lookupOneSlot(key);
542 try std.testing.expectEqual(table.primaryBucketOffset(key), lookup.primary_slot);
543 try std.testing.expectEqual(table.secondaryBucketOffset(key), lookup.secondary_slot);
544 try std.testing.expect(lookup.primary_slot < config.num_slots);
545 try std.testing.expect(lookup.secondary_slot < config.num_slots);
546 }
547
548 test "Highway generic Cuckoo query table oracle matches exactly" {
549 const key_count = 1024;
550 var keys: [key_count]u32 = undefined;
551 const engine = random.AesCtrEngine.initDeterministic();
552 const permutation = hash_mod.Triple32.initSeed(&engine, 42);
553 for (&keys, 0..) |*key, index| key.* = permutation.hash(@intCast(index));
554 const config = try CuckooConfig.init(key_count, 0.25);
555 const allocator = std.testing.allocator;
556 const slots = try allocator.alloc(u32, config.num_slots);
557 defer allocator.free(slots);
558 const table = try fixtureTable(DefaultCuckoo, &keys, 0.25, slots);
559 try std.testing.expectEqual(@as(usize, 2048), table.config.num_slots);
560 try std.testing.expectEqual(@as(usize, 128), table.config.num_buckets);
561 try std.testing.expectEqual(@as(usize, 7), table.config.bucket_bits);
562 try std.testing.expectEqual(@as(u32, 1023), table.num_primary);
563 const expected_keys = [8]u32{
564 0xf123_3796,
565 0x27e2_607d,
566 0x4f2d_bc23,
567 0xef67_db61,
568 0x96ee_e43d,
569 0x2711_aea8,
570 0x962a_7e49,
571 0x1c5e_91ed,
572 };
573 const primary_offsets = [8]usize{ 1776, 1440, 240, 96, 1072, 1184, 1936, 1920 };
574 const secondary_offsets = [8]usize{ 1120, 832, 1808, 1840, 304, 528, 48, 2032 };
575 for (expected_keys, primary_offsets, secondary_offsets) |key, primary, secondary| {
576 try std.testing.expect(table.queryOne(key));
577 try std.testing.expectEqual(primary, table.primaryBucketOffset(key));
578 try std.testing.expectEqual(secondary, table.secondaryBucketOffset(key));
579 }
580 var digest: u64 = 1_469_598_103_934_665_603;
581 for (table.slots()) |slot| digest = (digest ^ slot) *% 1_099_511_628_211;
582 try std.testing.expectEqual(@as(u64, 0x590c_18fa_4183_b4ab), digest);
583 try std.testing.expectEqual(@as(usize, 8192), table.allocatedBytes());
584 }
585
586 test "Highway generic Cuckoo scalar batch and lookup queries agree" {
587 const key_count = 2000;
588 var keys: [key_count]u32 = undefined;
589 hash_mod.fillRandomDistinct(u32, 0, &keys);
590 const config = try CuckooConfig.init(key_count, 0.25);
591 const allocator = std.testing.allocator;
592 const slots = try allocator.alloc(u32, config.num_slots);
593 defer allocator.free(slots);
594 const table = try fixtureTable(DefaultCuckoo, &keys, 0.25, slots);
595 try std.testing.expect(!table.isEmpty());
596 for (keys) |key| try std.testing.expect(table.queryOne(key));
597 const D = tag.FixedTag(u32, 8);
598 var index: usize = 0;
599 while (index + D.lane_count <= keys.len) : (index += D.lane_count) {
600 const input: D.Vector = keys[index..][0..D.lane_count].*;
601 try std.testing.expect(!@reduce(.Or, table.queryBatch(false, D, input)));
602 try std.testing.expect(!@reduce(.Or, table.queryBatch(true, D, input)));
603 const lookup = table.lookupSlotsAndHash(D, input);
604 inline for (0..D.lane_count) |lane| {
605 const scalar = table.lookupOneSlot(input[lane]);
606 try std.testing.expectEqual(scalar.primary_hash, lookup.primary_hashes[lane]);
607 try std.testing.expectEqual(scalar.primary_slot, lookup.primary_slots[lane]);
608 try std.testing.expectEqual(scalar.secondary_slot, lookup.secondary_slots[lane]);
609 }
610 }
611 const permutation = hash_mod.Triple32.initKey(0);
612 var absent: [D.lane_count]u32 = undefined;
613 for (&absent, 0..) |*key, lane| {
614 key.* = permutation.hash(@intCast(key_count + 1000 + lane));
615 }
616 for (absent) |key| try std.testing.expect(!table.queryOne(key));
617 try std.testing.expect(@reduce(.And, table.queryBatch(true, D, absent)));
618 }
619
620 test "Highway generic Cuckoo u16 fingerprints retain all members" {
621 const Family = CuckooFamily(hash_mod.WeakTwoMul, 16, 262_144);
622 const key_count = 1000;
623 var keys: [key_count]u32 = undefined;
624 hash_mod.fillRandomDistinct(u32, 7, &keys);
625 const config = try Family.Config.init(key_count, 0.25);
626 const allocator = std.testing.allocator;
627 const slots = try allocator.alloc(u32, config.num_slots);
628 defer allocator.free(slots);
629 const fingerprints = try allocator.alloc(u16, config.num_slots);
630 defer allocator.free(fingerprints);
631 const full = try fixtureTable(Family, &keys, 0.25, slots);
632 const table = try full.buildU16Slots(fingerprints);
633 try std.testing.expect(table.hasU16Slots());
634 try std.testing.expectEqual(@as(usize, 0), table.slots().len);
635 try std.testing.expectEqual(config.num_slots * @sizeOf(u16), table.allocatedBytes());
636 for (keys) |key| try std.testing.expect(try table.queryOneU16(key));
637 const D = tag.FixedTag(u32, 8);
638 var index: usize = 0;
639 while (index + D.lane_count <= keys.len) : (index += D.lane_count) {
640 const input: D.Vector = keys[index..][0..D.lane_count].*;
641 try std.testing.expect(!@reduce(.Or, try table.queryBatchU16(false, D, input)));
642 try std.testing.expect(!@reduce(.Or, try table.queryBatchU16(true, D, input)));
643 }
644 }