tiny.simd.Cuckoo2x2Plan

1pub const Cuckoo2x2Plan = struct {2    key_count: usize,3    bucket_counts: [configuration_count]usize,4    max_bucket_count: usize,5    entries_len: usize,6    scratch_len: usize,78    const Self = @This();910    pub fn inspect(key_count: usize) Cuckoo2x2BuildError!Self {11        if (key_count > std.math.maxInt(u32)) return error.CapacityExceeded;12        const quarter = key_count / 4;13        const base = if (quarter <= 1)14            @as(usize, 1)15        else16            std.math.ceilPowerOfTwo(usize, quarter) catch return error.CapacityExceeded;17        var bucket_counts: [configuration_count]usize = undefined;18        inline for (0..configuration_count) |index| {19            const multiplier = @as(usize, 1) << index;20            const candidate = std.math.mul(usize, base, multiplier) catch21                return error.CapacityExceeded;22            const num_buckets = @max(candidate, minimum_bucket_count);23            if (num_buckets > std.math.maxInt(u32)) return error.CapacityExceeded;24            bucket_counts[index] = num_buckets;25        }26        const max_bucket_count = bucket_counts[configuration_count - 1];27        const bucket_key_count = std.math.mul(usize, max_bucket_count, 2) catch28            return error.CapacityExceeded;29        const byte_count = std.math.add(usize, key_count, max_bucket_count) catch30            return error.CapacityExceeded;31        const byte_words = std.math.divCeil(usize, byte_count, @sizeOf(u32)) catch32            unreachable;33        const hash_and_keys = std.math.add(usize, key_count, bucket_key_count) catch34            return error.CapacityExceeded;35        const scratch_len = std.math.add(usize, hash_and_keys, byte_words) catch36            return error.CapacityExceeded;37        return .{38            .key_count = key_count,39            .bucket_counts = bucket_counts,40            .max_bucket_count = max_bucket_count,41            .entries_len = max_bucket_count,42            .scratch_len = scratch_len,43        };44    }4546    pub fn build(47        self: Self,48        scratch: []u32,49        entries: []u32,50        keys: []const u32,51    ) Cuckoo2x2BuildError!Cuckoo2x2Data {52        if (keys.len != self.key_count) return error.PlanMismatch;53        if (scratch.len < self.scratch_len) return error.ScratchTooSmall;54        if (entries.len < self.entries_len) return error.EntriesTooSmall;55        const parts = self.sections(scratch);56        const engine = random.AesCtrEngine.initDeterministic();57        const distinct_hash = hash_mod.WeakTwoMul.initSeed(&engine, 0);58        hash_mod.hashArray(tag.ScalableTag(u32), distinct_hash, keys, parts.hashes);59        std.mem.sort(u32, parts.hashes, {}, std.sort.asc(u32));60        const sorted_hashes = parts.hashes;61        if (sorted_hashes.len > 1) {62            const previous_hashes = sorted_hashes[0 .. sorted_hashes.len - 1];63            for (sorted_hashes[1..], previous_hashes) |current, previous| {64                if (current == previous) return error.DuplicateKey;65            }66        }6768        for (self.bucket_counts, 0..) |num_buckets, config_idx| {69            for (0..max_attempts) |attempt_idx| {70                const hash_key: u32 = @truncate(engine.generate(attempt_idx, 0));71                const config = Cuckoo2x2Config.init(num_buckets, hash_key);72                const hash1 = hash_mod.WeakTwoMul.initKey(hash_key);73                @memset(parts.counts[0..num_buckets], 0);74                @memset(entries[0..num_buckets], 0);75                hash_mod.hashArray(tag.ScalableTag(u32), hash1, keys, parts.hashes);76                if (!cuckooAssign(77                    config,78                    parts.hashes,79                    parts.choices,80                    parts.counts[0..num_buckets],81                    parts.bucket_keys[0 .. num_buckets * 2],82                )) continue;83                populateEntries(84                    config,85                    parts.hashes,86                    parts.choices,87                    parts.counts[0..num_buckets],88                    entries[0..num_buckets],89                );90                var num_primary: u32 = 0;91                for (parts.choices) |choice| num_primary += @intFromBool(choice == 0);92                return .{93                    .config = config,94                    .entries = entries[0..num_buckets],95                    .config_idx = config_idx,96                    .attempt_idx = attempt_idx,97                    .num_primary = num_primary,98                    .num_secondary = @as(u32, @intCast(keys.len)) - num_primary,99                };100            }101        }102        return error.BuildFailed;103    }104105    fn sections(self: Self, scratch: []u32) ScratchSections {106        const hashes = scratch[0..self.key_count];107        const bucket_keys_begin = self.key_count;108        const bucket_keys_end = bucket_keys_begin + self.max_bucket_count * 2;109        const bucket_keys = scratch[bucket_keys_begin..bucket_keys_end];110        const bytes = std.mem.sliceAsBytes(scratch[bucket_keys_end..self.scratch_len]);111        const choices = bytes[0..self.key_count];112        const counts = bytes[self.key_count .. self.key_count + self.max_bucket_count];113        return .{114            .hashes = hashes,115            .bucket_keys = bucket_keys,116            .choices = choices,117            .counts = counts,118        };119    }120};

1pub const Cuckoo2x2Plan = cuckoo2x2.Cuckoo2x2Plan;