prob/cuckoo
Cuckoo
(defstruct Cuckoo [buckets : (Vec int) num-buckets : int bucket-size : int])
a Cuckoo filter with num-buckets buckets of bucket-size slots.
Since: probabilistic-spice-plan C2
cuckoo-num-buckets
(cuckoo-num-buckets [^borrow cf : Cuckoo] :)
the bucket count.
Since: probabilistic-spice-plan C2
cuckoo-bucket-size
(cuckoo-bucket-size [^borrow cf : Cuckoo] :)
the slots per bucket.
Since: probabilistic-spice-plan C2
cuckoo-new
(cuckoo-new [num-buckets : int] :)
create a Cuckoo filter with num-buckets buckets.
| num-buckets | number of buckets (should be a power of two) |
A new Cuckoo filter with all slots empty. Each bucket has 4 slots.
(let [cf (cuckoo-new 1024)] ...)
Since: probabilistic-spice-plan C2
cuckoo-free
(cuckoo-free [cf : Cuckoo] :)
release the bucket array.
Since: probabilistic-spice-plan C2
cuckoo-insert!
(cuckoo-insert! [^borrow cf : Cuckoo key : int] :)
add an element to the filter.
| cf | the filter (mutated in place) | |
| key | the integer key to insert |
true if the element was inserted (or was already present). false if the filter is full (max kicks exceeded).
Since: probabilistic-spice-plan C2
cuckoo-maybe?
(cuckoo-maybe? [^borrow cf : Cuckoo key : int] :)
is the element possibly in the filter?
| cf | the filter | |
| key | the integer key to check |
true if the fingerprint is found in either candidate bucket. false if not found (element is definitely not present).
Since: probabilistic-spice-plan C2
cuckoo-delete!
(cuckoo-delete! [^borrow cf : Cuckoo key : int] :)
remove an element from the filter.
| cf | the filter (mutated in place) | |
| key | the integer key to remove |
true if the fingerprint was found and removed. false if the fingerprint was not found (element not present).
Since: probabilistic-spice-plan C2
cuckoo-count
(cuckoo-count [^borrow cf : Cuckoo] :)
the number of occupied slots.
Since: probabilistic-spice-plan C2
cuckoo-merge
(cuckoo-merge [^borrow a : Cuckoo ^borrow b : Cuckoo] :)
"insert all of B into A" into a new filter.
| a | first filter | |
| b | second filter (must have the same num-buckets and bucket-size) |
A new Cuckoo filter containing all fingerprints from both a and b. Both inputs remain valid. Note: this merge is NOT idempotent and NOT commutative under shared items. It is "insert all of B into A", not a lattice join. No JoinSemilattice instance is declared for Cuckoo (probabilistic-spice-plan 2.6). If the result filter is full, some fingerprints from B may be dropped; the caller should size num-buckets to accommodate the union.
Since: probabilistic-spice-plan C2
Internal definitions
__cuckoo-bucket-size-- constant: 4 slots per bucket.__cuckoo-max-kicks-- constant: 500 kicks before declaring full.__cuckoo-init-- internal: push n zeros into the bucket Vec.__cuckoo-fingerprint-- compute a non-zero 8-bit fingerprint.__cuckoo-alt-index-- compute the alternate bucket index.__cuckoo-bucket-base-- compute the base slot index for bucket idx.__cuckoo-try-insert-- internal: try to place fp in one slot of bucket.__cuckoo-find-fp-- internal: find the slot index of fp in a bucket.__cuckoo-relocate-- internal: cuckoo relocation loop.__cuckoo-remove-from-- internal: remove fp from a bucket if found.__cuckoo-count-loop-- internal: count non-zero slots.__cuckoo-merge-scan-- internal: scan B's buckets, re-insert each fp.