Line data    Source code

       1             : #ifndef HEADER_fd_src_flamenco_gossip_fd_bloom_h
       2             : #define HEADER_fd_src_flamenco_gossip_fd_bloom_h
       3             : 
       4             : #include "../../util/rng/fd_rng.h"
       5             : 
       6             : #include <math.h>
       7             : 
       8        1830 : #define FD_BLOOM_ALIGN     (64UL)
       9             : #define FD_BLOOM_FOOTPRINT (128UL)
      10             : 
      11         909 : #define FD_BLOOM_MAGIC (0xF17EDA2CE8100800) /* FIREDANCE BLOOM V0 */
      12             : 
      13             : struct __attribute__((aligned(FD_BLOOM_ALIGN))) fd_bloom_private {
      14             :   ulong * keys;
      15             :   ulong   keys_len;
      16             : 
      17             :   ulong * bits;
      18             :   ulong   bits_len;
      19             : 
      20             :   ulong   hash_seed;
      21             :   fd_rng_t * rng;
      22             : 
      23             :   ulong   max_bits;
      24             :   double  false_positive_rate;
      25             : 
      26             :   ulong magic; /* ==FD_BLOOM_MAGIC */
      27             : };
      28             : 
      29             : typedef struct fd_bloom_private fd_bloom_t;
      30             : 
      31             : FD_PROTOTYPES_BEGIN
      32             : 
      33             : FD_FN_CONST ulong
      34             : fd_bloom_align( void );
      35             : 
      36             : FD_FN_CONST ulong
      37             : fd_bloom_footprint( double false_positive_rate,
      38             :                     ulong  max_bits );
      39             : 
      40             : void *
      41             : fd_bloom_new( void *     shmem,
      42             :               fd_rng_t * rng,
      43             :               double     false_positive_rate,
      44             :               ulong      max_bits );
      45             : 
      46             : fd_bloom_t *
      47             : fd_bloom_join( void * shbloom );
      48             : 
      49             : void
      50             : fd_bloom_initialize( fd_bloom_t * bloom,
      51             :                      ulong        num_items );
      52             : 
      53             : void
      54             : fd_bloom_insert( fd_bloom_t *  bloom,
      55             :                  uchar const * key,
      56             :                  ulong         key_sz );
      57             : 
      58             : int
      59             : fd_bloom_contains( fd_bloom_t *  bloom,
      60             :                    uchar const * key,
      61             :                    ulong         key_sz );
      62             : 
      63             : int
      64             : fd_bloom_init_inplace( ulong *      keys,
      65             :                        ulong *      bits,
      66             :                        ulong        keys_len,
      67             :                        ulong        bits_len,
      68             :                        ulong        hash_seed,
      69             :                        fd_rng_t *   rng,
      70             :                        double       false_positive_rate,
      71             :                        fd_bloom_t * out_bloom );
      72             : 
      73             : static inline double
      74             : fd_bloom_max_items( double max_bits,
      75             :                     double num_keys,
      76           0 :                     double false_positive_rate ) {
      77           0 :   return ceil( max_bits / ( -num_keys / log( 1.0 - exp( log( false_positive_rate ) / num_keys ) )));
      78           0 : }
      79             : 
      80             : static inline ulong
      81             : fd_bloom_num_bits( double num_items,
      82             :                    double false_positive_rate,
      83           0 :                    double max_bits ) {
      84           0 :   double num_bits = ceil( ((double)num_items * log( false_positive_rate )) / log( 1.0 / pow( 2.0, log( 2.0 ) )));
      85           0 :   return (ulong)fmax( 1.0, fmin( max_bits, num_bits ) );
      86           0 : }
      87             : 
      88             : FD_PROTOTYPES_END
      89             : 
      90             : #endif /* HEADER_fd_src_flamenco_gossip_fd_bloom_h */