basis/cuckoo-filters/cuckoo-filters.factor

   1 ! Copyright (C) 2016 John Benediktsson
   2 ! See http://factorcode.org/license.txt for BSD license
   3
   4 USING: accessors alien alien.c-types alien.data arrays checksums
   5 checksums.sha combinators.short-circuit kernel math math.bitwise
   6 random sequences ;
   7
   8 IN: cuckoo-filters
   9
  10 <PRIVATE
  11
  12 ! The maximum number of times we kick down items/displace from
  13 ! their buckets
  14 CONSTANT: max-cuckoo-count 500
  15
  16 ! The maximum load factor we allow before growing the capacity
  17 CONSTANT: max-load-factor 0.96
  18
  19 ! The number of fingerprint to store in each bucket
  20 CONSTANT: bucket-size 4
  21
  22 : #buckets ( capacity -- #buckets )
  23     [ bucket-size /i next-power-of-2 ] keep
  24     over / bucket-size / max-load-factor > [ 2 * ] when ;
  25
  26 : <cuckoo-buckets> ( capacity -- buckets )
  27     #buckets [ bucket-size f <array> ] replicate ;
  28
  29 : hash-index ( hash -- fingerprint index )
  30     4 over <displaced-alien> [ uint deref ] bi@ ;
  31
  32 : alt-index ( fingerprint index -- alt-index )
  33     [ 0x5bd1e995 w* ] [ bitxor ] bi* ;
  34
  35 : hash-indices ( bytes cuckoo-filter -- fingerprint index alt-index )
  36     checksum>> checksum-bytes hash-index 2dup alt-index ;
  37
  38 : bucket-lookup ( fingerprint bucket -- ? )
  39     member? ;
  40
  41 : bucket-insert ( fingerprint bucket -- ? )
  42     dup [ not ] find drop [ swap set-nth t ] [ 2drop f ] if* ;
  43
  44 : bucket-delete ( fingerprint bucket -- ? )
  45     [ f ] 2dip [ index ] keep over [ set-nth t ] [ 3drop f ] if ;
  46
  47 : bucket-swap ( fingerprint bucket -- fingerprint' )
  48     [ length random ] keep [ swap ] change-nth ;
  49
  50 PRIVATE>
  51
  52 TUPLE: cuckoo-filter buckets checksum size ;
  53
  54 : <cuckoo-filter> ( capacity -- cuckoo-filter )
  55     <cuckoo-buckets> sha1 0 cuckoo-filter boa ;
  56
  57 :: cuckoo-insert ( bytes cuckoo-filter -- ? )
  58     bytes cuckoo-filter hash-indices :> ( fp! i1 i2 )
  59     cuckoo-filter buckets>> :> buckets
  60     buckets length :> n
  61     {
  62         [ fp i1 n mod buckets nth bucket-insert ]
  63         [ fp i2 n mod buckets nth bucket-insert ]
  64     } 0|| [
  65         t
  66     ] [
  67         2 random zero? i1 i2 ? :> i!
  68         max-cuckoo-count [
  69             drop
  70             fp i n mod buckets nth bucket-swap fp!
  71             fp i alt-index i!
  72
  73             fp i n mod buckets nth bucket-insert
  74         ] find-integer >boolean
  75     ] if
  76     dup [ cuckoo-filter [ 1 + ] change-size drop ] when ;
  77
  78 :: cuckoo-lookup ( bytes cuckoo-filter -- ? )
  79     bytes cuckoo-filter hash-indices :> ( fp i1 i2 )
  80     cuckoo-filter buckets>> :> buckets
  81     buckets length :> n
  82     {
  83         [ fp i1 n mod buckets nth bucket-lookup ]
  84         [ fp i2 n mod buckets nth bucket-lookup ]
  85     } 0|| ;
  86
  87 :: cuckoo-delete ( bytes cuckoo-filter -- ? )
  88     bytes cuckoo-filter hash-indices :> ( fp i1 i2 )
  89     cuckoo-filter buckets>> :> buckets
  90     buckets length :> n
  91     {
  92         [ fp i1 n mod buckets nth bucket-delete ]
  93         [ fp i2 n mod buckets nth bucket-delete ]
  94     } 0||
  95     dup [ cuckoo-filter [ 1 - ] change-size drop ] when ;