tiny.simd.Cuckoo2x2

1pub const Cuckoo2x2 = struct {2    hash1: hash_mod.WeakTwoMul,3    data: Cuckoo2x2Data,45    const Self = @This();67    pub fn init(data: Cuckoo2x2Data) Self {8        std.debug.assert(!data.isEmpty());9        std.debug.assert(data.numBuckets() >= minimum_bucket_count);10        return .{11            .hash1 = hash_mod.WeakTwoMul.initKey(data.config.hash_key),12            .data = data,13        };14    }1516    pub fn getData(self: Self) Cuckoo2x2Data {17        return self.data;18    }1920    pub fn contains(self: Self, key: u32) bool {21        const h1 = self.hash1.hash(key);22        const b1 = h1 & self.data.config.bucket_mask;23        const fingerprint = h1 >> 18;24        const b2 = b1 ^ (fingerprint + 1);25        const primary: u16 = @truncate(fingerprint | 0x4000);26        const secondary: u16 = @truncate(fingerprint | 0x8000);27        const e1 = self.data.entries[b1];28        const e2 = self.data.entries[b2];29        return primary == @as(u16, @truncate(e1)) or30            primary == @as(u16, @truncate(e1 >> 16)) or31            secondary == @as(u16, @truncate(e2)) or32            secondary == @as(u16, @truncate(e2 >> 16));33    }3435    pub fn query(self: Self, comptime D: type, keys: D.Vector) D.Mask {36        requireTag(D);37        const h1 = self.hash1.oneVec(D, keys);38        const b1 = h1 & @as(D.Vector, @splat(self.data.config.bucket_mask));39        const fingerprint = shift.shiftRight(D, 18, h1);40        const b2 = b1 ^ (fingerprint +% @as(D.Vector, @splat(1)));41        const primary = fingerprint | @as(D.Vector, @splat(0x4000));42        const secondary = fingerprint | @as(D.Vector, @splat(0x8000));43        const e1 = indexed.gatherIndex(D, self.data.entries, b1);44        const e2 = indexed.gatherIndex(D, self.data.entries, b2);45        const low_mask: D.Vector = @splat(0xffff);46        const found = (e1 & low_mask == primary) |47            (shift.shiftRight(D, 16, e1) == primary) |48            (e2 & low_mask == secondary) |49            (shift.shiftRight(D, 16, e2) == secondary);50        return !found;51    }5253    pub fn containsVec(self: Self, comptime D: type, keys: D.Vector) D.Mask {54        return !self.query(D, keys);55    }56};

1pub const Cuckoo2x2 = cuckoo2x2.Cuckoo2x2;