cuckoo-insert ( bytes cuckoo-filter -- ? )

Vocabulary

cuckoo-filters

Inputs

bytes	a byte-array
cuckoo-filter	a cuckoo-filter

Outputs

?

a boolean

Word description

Insert the data into the cuckoo-filter, returning t if the data was inserted. If insertion fails, returns f and leaves existing entries unchanged.

Notes

Attempting to insert data twice will result in the hashed fingerprint of the data appearing twice and the cuckoo-filter size being incremented twice.

Definition

USING: accessors assocs combinators.short-circuit
cuckoo-filters.private kernel math random sequences ;

IN: cuckoo-filters

:: cuckoo-insert ( bytes cuckoo-filter -- ? )
    bytes cuckoo-filter hash-indices :> ( fp! i1 i2 )
    cuckoo-filter buckets>> :> buckets buckets length :> n {
        [ fp i1 n mod buckets nth bucket-insert ]
        [ fp i2 n mod buckets nth bucket-insert ]
    } 0||
    [ t ] [
        H{ } clone :> originals 2 random zero? i1 i2 ?
        :> i! max-cuckoo-count [
            drop i n mod :> index index originals
            [ buckets nth clone ] cache drop
            fp index buckets nth bucket-swap fp! fp i alt-index
            i! fp i n mod buckets nth bucket-insert
        ] find-integer >boolean dup
        [ originals [ swap buckets set-nth ] assoc-each ] unless
    ] if dup [ cuckoo-filter [ 1 + ] change-size drop ] when ;