Line data Source code
1 : #include "fd_bloom.h"
2 :
3 : #include "../../util/log/fd_log.h"
4 :
5 : #include <math.h>
6 :
7 : static const double FD_BLOOM_LN_2 = 0.69314718055994530941723212145818;
8 : static ulong
9 : fnv_hasher( uchar const * ele,
10 : ulong ele_sz,
11 60 : ulong key ) {
12 846 : for( ulong i=0UL; i<ele_sz; i++ ) {
13 786 : key ^= (ulong)ele[i];
14 786 : key *= 1099511628211UL; /* FNV prime */
15 786 : }
16 60 : return key;
17 60 : }
18 :
19 : FD_FN_CONST ulong
20 3630 : fd_bloom_align( void ) {
21 3630 : return FD_BLOOM_ALIGN;
22 3630 : }
23 :
24 : FD_FN_CONST ulong
25 : fd_bloom_footprint( double false_positive_rate,
26 1842 : ulong max_bits ) {
27 1842 : if( FD_UNLIKELY( false_positive_rate<=0.0 ) ) return 0UL;
28 1842 : if( FD_UNLIKELY( false_positive_rate>=1.0 ) ) return 0UL;
29 :
30 1842 : if( FD_UNLIKELY( max_bits<1UL || max_bits>32768UL ) ) return 0UL;
31 :
32 1842 : ulong num_keys = (ulong)( round( (double)max_bits*FD_BLOOM_LN_2 ) );
33 :
34 1842 : ulong l;
35 1842 : l = FD_LAYOUT_INIT;
36 1842 : l = FD_LAYOUT_APPEND( l, FD_BLOOM_ALIGN, sizeof(fd_bloom_t) );
37 1842 : l = FD_LAYOUT_APPEND( l, 8UL, num_keys*sizeof(ulong) );
38 1842 : l = FD_LAYOUT_APPEND( l, 8UL, (max_bits+7UL)/8UL );
39 1842 : return FD_LAYOUT_FINI( l, FD_BLOOM_ALIGN );
40 1842 : }
41 :
42 : void *
43 : fd_bloom_new( void * shmem,
44 : fd_rng_t * rng,
45 : double false_positive_rate,
46 1809 : ulong max_bits ) {
47 :
48 1809 : if( FD_UNLIKELY( !shmem ) ) {
49 0 : FD_LOG_WARNING(( "NULL shmem" ));
50 0 : return NULL;
51 0 : }
52 :
53 1809 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmem, fd_bloom_align() ) ) ) {
54 0 : FD_LOG_WARNING(( "misaligned shmem" ));
55 0 : return NULL;
56 0 : }
57 :
58 1809 : if( FD_UNLIKELY( false_positive_rate<=0.0 ) ) return NULL;
59 1809 : if( FD_UNLIKELY( false_positive_rate>=1.0 ) ) return NULL;
60 :
61 1809 : if( FD_UNLIKELY( max_bits<1UL || max_bits>32768UL ) ) return NULL;
62 :
63 1809 : if( FD_UNLIKELY( !rng ) ) return NULL;
64 :
65 1809 : ulong num_keys = (ulong)( round( (double)max_bits*FD_BLOOM_LN_2 ) );
66 :
67 1809 : FD_SCRATCH_ALLOC_INIT( l, shmem );
68 1809 : fd_bloom_t * bloom = FD_SCRATCH_ALLOC_APPEND( l, FD_BLOOM_ALIGN, sizeof(fd_bloom_t) );
69 1809 : void * _keys = FD_SCRATCH_ALLOC_APPEND( l, 8UL, num_keys*sizeof(ulong) );
70 1809 : void * _bits = FD_SCRATCH_ALLOC_APPEND( l, 8UL, (max_bits+7UL)/8UL );
71 1809 : FD_TEST( FD_SCRATCH_ALLOC_FINI( l, FD_BLOOM_ALIGN ) == (ulong)shmem + fd_bloom_footprint( false_positive_rate, max_bits ) );
72 :
73 1809 : bloom->keys = (ulong *)_keys;
74 1809 : bloom->keys_len = 0UL;
75 1809 : bloom->bits = (ulong *)_bits;
76 1809 : bloom->bits_len = 0UL;
77 :
78 1809 : bloom->hash_seed = 0UL;
79 1809 : bloom->rng = rng;
80 :
81 1809 : bloom->false_positive_rate = false_positive_rate;
82 1809 : bloom->max_bits = max_bits;
83 :
84 1809 : FD_COMPILER_MFENCE();
85 1809 : FD_VOLATILE( bloom->magic ) = FD_BLOOM_MAGIC;
86 1809 : FD_COMPILER_MFENCE();
87 :
88 1809 : return (void *)bloom;
89 1809 : }
90 :
91 : fd_bloom_t *
92 1809 : fd_bloom_join( void * shbloom ) {
93 1809 : if( FD_UNLIKELY( !shbloom ) ) {
94 0 : FD_LOG_WARNING(( "NULL shbloom" ));
95 0 : return NULL;
96 0 : }
97 :
98 1809 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shbloom, fd_bloom_align() ) ) ) {
99 0 : FD_LOG_WARNING(( "misaligned shbloom" ));
100 0 : return NULL;
101 0 : }
102 :
103 1809 : fd_bloom_t * bloom = (fd_bloom_t *)shbloom;
104 :
105 1809 : if( FD_UNLIKELY( bloom->magic!=FD_BLOOM_MAGIC ) ) {
106 0 : FD_LOG_WARNING(( "bad magic" ));
107 0 : return NULL;
108 0 : }
109 :
110 1809 : return bloom;
111 1809 : }
112 :
113 : void
114 : fd_bloom_initialize( fd_bloom_t * bloom,
115 18 : ulong num_items ) {
116 18 : double num_bits = ceil( ((double)num_items * log( bloom->false_positive_rate )) / log( 1.0 / pow( 2.0, log( 2.0 ) ) ) );
117 18 : num_bits = fmax( 1.0, fmin( (double)bloom->max_bits, num_bits ) );
118 :
119 18 : ulong num_keys;
120 18 : if( FD_UNLIKELY( num_items == 0UL ) ) {
121 3 : num_keys = 0UL;
122 15 : } else {
123 15 : num_keys = fd_ulong_max( 1UL, (ulong)( round( ((double)num_bits/(double)num_items) * FD_BLOOM_LN_2 ) ) );
124 15 : }
125 66 : for( ulong i=0UL; i<num_keys; i++ ) bloom->keys[ i ] = fd_rng_ulong( bloom->rng );
126 :
127 18 : bloom->keys_len = num_keys;
128 18 : bloom->bits_len = (ulong)num_bits;
129 18 : fd_memset( bloom->bits, 0, (ulong)((num_bits+7UL)/8UL) );
130 18 : }
131 :
132 : void
133 : fd_bloom_insert( fd_bloom_t * bloom,
134 : uchar const * key,
135 9 : ulong key_sz ) {
136 36 : for( ulong i=0UL; i<bloom->keys_len; i++ ) {
137 27 : ulong bit = fnv_hasher( key, key_sz, bloom->keys[ i ] ) % bloom->bits_len;
138 27 : bloom->bits[ bit / 64UL ] |= (1UL << (bit % 64UL));
139 27 : }
140 9 : }
141 :
142 : int
143 : fd_bloom_contains( fd_bloom_t * bloom,
144 : uchar const * key,
145 15 : ulong key_sz ) {
146 42 : for( ulong i=0UL; i<bloom->keys_len; i++ ) {
147 33 : ulong bit = fnv_hasher( key, key_sz, bloom->keys[ i ]) % bloom->bits_len;
148 33 : if( !(bloom->bits[ bit / 64UL ] & (1UL << (bit % 64UL))) ) {
149 6 : return 0;
150 6 : }
151 33 : }
152 9 : return 1;
153 15 : }
154 :
155 : int
156 : fd_bloom_init_inplace( ulong * keys,
157 : ulong * bits,
158 : ulong keys_len,
159 : ulong bits_len,
160 : ulong hash_seed,
161 : fd_rng_t * rng,
162 : double false_positive_rate,
163 0 : fd_bloom_t * out_bloom ) {
164 0 : if( FD_UNLIKELY( !keys || !bits || !out_bloom ) ) {
165 0 : FD_LOG_ERR(( "NULL keys, bits or out_bloom" ));
166 0 : return -1;
167 0 : }
168 0 : out_bloom->keys = keys;
169 0 : for( ulong i=0UL; i<keys_len; i++ ) out_bloom->keys[ i ] = fd_rng_ulong( rng );
170 :
171 0 : out_bloom->keys_len = keys_len;
172 0 : out_bloom->bits = bits;
173 0 : out_bloom->bits_len = bits_len;
174 0 : out_bloom->hash_seed = hash_seed;
175 0 : out_bloom->rng = rng;
176 0 : out_bloom->false_positive_rate = false_positive_rate;
177 0 : out_bloom->max_bits = bits_len;
178 :
179 0 : return 0;
180 0 : }
|
