LibCuckooFilter

Cuckoo Filter for WoW Lua 5.1 environment - Probabilistic set membership testing with minimal memory footprint.

Features

Efficiently tests whether an element is a member of a set.
Low memory usage, suitable for constrained environments.
Simple API for adding and checking elements.
Compatible with World of Warcraft Lua 5.1 environment.

Installation

To install LibCuckooFilter, simply download the LibCuckooFilter.lua file and include it in your WoW addon folder. Then, you can load it using LibStub in your addon code.

local LibCuckooFilter = LibStub("LibCuckooFilter")

Usage

-- Create a new Cuckoo Filter with expected 1000 values
local filter = LibCuckooFilter.New(1000)

-- Add values to the filter
for i = 1, 1000 do
    filter:Insert("value" .. i)
end

-- Check for membership
for i = 1, 1200 do
    local value = "value" .. i
    if filter:Contains(value) then
        print(value .. " is possibly in the set.")
    else
        print(value .. " is definitely not in the set.")
    end
end

-- Export the filter state, so you can serialize it
local state = filter:Export()

-- Import the filter state into a new filter
local newFilter = LibCuckooFilter.Import(state)

API

LibCuckooFilter.New(capacity, seed, bucketSize, fingerprintBits, maxKicks)

Create a new Cuckoo Filter instance.

capacity: Capacity of the filter (expected number of values).
seed: (Optional) Seed for hash functions (default: 0).
bucketSize: (Optional) Number of entries per bucket (default: 4).
fingerprintBits: (Optional) Number of bits per fingerprint (default: 12).
maxKicks: (Optional) Maximum number of kicks during insertion (default: 512).
Returns: The new Cuckoo Filter instance.

filter:Insert(value)

Insert a value into the filter.

value: Value to insert.
Returns: True if insertion succeeded, false if the filter is full.

filter:Contains(value)

Determine if a value is possibly in the filter.

value: Value to check.
Returns: True if value might be in the set, false if definitely not.

filter:Delete(value)

Delete a value from the filter.

Note: May cause false negatives if the same fingerprint was inserted multiple times.

value: Value to delete.
Returns: True if deletion succeeded, false if value not found.

filter:Export()

Export the current state of the filter.

Returns: Compact representation of the filter.

LibCuckooFilter.Import(state)

Import a new Cuckoo Filter from a compact representation.

state: Compact representation of the filter.
Returns: The imported Cuckoo Filter instance.

filter:Clear()

Clear all values from the Cuckoo Filter.

filter:EstimateFalsePositiveRate()

Estimate the current false positive rate (FPR) of the filter based on current load factor.

Returns: Estimated false positive rate.

License

This library is released under the MIT License. See the LICENSE file for details.