GET /xrpc/app.bsky.actor.searchActorsTypeahead
typeahead.waow.tech
1//! Fixed-size bloom filter for DID dedup
2//! Avoids re-sending already-known bare DIDs to the worker
3
4const std = @import("std");
5const Allocator = std.mem.Allocator;
6
7const BLOOM_HASHES: usize = 7;
8
9pub const BloomFilter = struct {
10 bits: std.DynamicBitSetUnmanaged,
11 num_bits: usize,
12 num_hashes: usize,
13 count: usize = 0,
14
15 pub fn init(allocator: Allocator, num_bits: usize, num_hashes: usize) !BloomFilter {
16 const bits = try std.DynamicBitSetUnmanaged.initEmpty(allocator, num_bits);
17 return .{
18 .bits = bits,
19 .num_bits = num_bits,
20 .num_hashes = num_hashes,
21 };
22 }
23
24 pub fn deinit(self: *BloomFilter, allocator: Allocator) void {
25 self.bits.deinit(allocator);
26 }
27
28 fn hashIndices(self: *const BloomFilter, key: []const u8) [BLOOM_HASHES]usize {
29 const h1 = std.hash.Wyhash.hash(0, key);
30 const h2 = std.hash.Wyhash.hash(1, key);
31 var indices: [BLOOM_HASHES]usize = undefined;
32 for (0..self.num_hashes) |i| {
33 indices[i] = @intCast((h1 +% i *% h2) % self.num_bits);
34 }
35 return indices;
36 }
37
38 pub fn insert(self: *BloomFilter, key: []const u8) void {
39 const indices = self.hashIndices(key);
40 for (indices) |idx| {
41 self.bits.set(idx);
42 }
43 self.count += 1;
44 }
45
46 pub fn contains(self: *const BloomFilter, key: []const u8) bool {
47 const indices = self.hashIndices(key);
48 for (indices) |idx| {
49 if (!self.bits.isSet(idx)) return false;
50 }
51 return true;
52 }
53
54 pub fn reset(self: *BloomFilter) void {
55 self.bits.unsetAll();
56 self.count = 0;
57 }
58};