| 1 |
|
| #ifndef SA_BLOOM_H |
| 2 |
|
| #define SA_BLOOM_H |
| 3 |
|
| |
| 4 |
|
| /* sa_bloom.h - a set that answers "no" exactly and "yes" probably. Perl-free. |
| 5 |
|
| * |
| 6 |
|
| * A bit array and k hash functions. Adding a key sets k bits; asking about a |
| 7 |
|
| * key tests them. If any is clear the key was definitely never added; if all |
| 8 |
|
| * are set it probably was, and the probability is a number you chose when you |
| 9 |
|
| * sized the filter. |
| 10 |
|
| * |
| 11 |
|
| * ---- why this fits an arena so well ---------------------------------------- |
| 12 |
|
| * |
| 13 |
|
| * There is nothing to allocate after the first moment, nothing to free ever, |
| 14 |
|
| * and no way for two processes to disagree about a write: setting a bit is one |
| 15 |
|
| * atomic OR, and two processes setting the same bit both simply set it. It is |
| 16 |
|
| * the only structure here that needs no lock at all, on either side. |
| 17 |
|
| * |
| 18 |
|
| * ---- what it cannot do ----------------------------------------------------- |
| 19 |
|
| * |
| 20 |
|
| * NO DELETION. Clearing a bit would clear it for every other key that happens |
| 21 |
|
| * to share it, turning a definite "no" into a wrong one. A filter only fills |
| 22 |
|
| * up; when it is too full, it is replaced. |
| 23 |
|
| * |
| 24 |
|
| * NO COUNT. `estimated_items` is arithmetic on how many bits are set, and it is |
| 25 |
|
| * an estimate that gets worse as the filter saturates. |
| 26 |
|
| * |
| 27 |
|
| * ---- sizing ---------------------------------------------------------------- |
| 28 |
|
| * |
| 29 |
|
| * From an expected item count n and an acceptable false-positive rate p, the |
| 30 |
|
| * standard result gives the bits m and the hash count k: |
| 31 |
|
| * |
| 32 |
|
| * m = -n ln p / (ln 2)^2 k = (m/n) ln 2 |
| 33 |
|
| * |
| 34 |
|
| * A filter sized for a million items at one percent needs about 1.2 MB and |
| 35 |
|
| * seven hash probes. Ask for what you expect, not for bits. |
| 36 |
|
| * |
| 37 |
|
| * The rate is what you get AT that item count. Past it the rate climbs, and it |
| 38 |
|
| * climbs quickly, which is why the fill is in the stats and why a caller that |
| 39 |
|
| * cares rotates rather than hoping. |
| 40 |
|
| * |
| 41 |
|
| * ---- two hashes, not k ----------------------------------------------------- |
| 42 |
|
| * |
| 43 |
|
| * Computing k independent hashes of every key would be k times the work for no |
| 44 |
|
| * benefit: Kirsch and Mitzenmacher showed that h1 + i*h2 gives the same false |
| 45 |
|
| * positive rate as k independent functions. So there are two, and the rest is |
| 46 |
|
| * arithmetic. h2 is forced odd so the probe sequence cannot get stuck on a |
| 47 |
|
| * subset of the array. |
| 48 |
|
| * |
| 49 |
|
| * Needs sa_arena.h. |
| 50 |
|
| */ |
| 51 |
|
| |
| 52 |
|
| #include "sa/sa_arena.h" |
| 53 |
|
| |
| 54 |
|
| #ifndef SA_NO_LIBM |
| 55 |
|
| # include <math.h> |
| 56 |
|
| #endif |
| 57 |
|
| |
| 58 |
|
| #define SA_BLOOM_MAGIC 0x4D4F4C42u /* 'B','L','O','M' little-endian */ |
| 59 |
|
| |
| 60 |
|
| #define SA_BLOOM_MAX_K 32 |
| 61 |
|
| |
| 62 |
|
| typedef struct { |
| 63 |
|
| volatile uint32_t magic; /* published LAST at init */ |
| 64 |
|
| uint32_t nhash; /* k */ |
| 65 |
|
| uint64_t nbits; /* m, a multiple of 64 */ |
| 66 |
|
| uint64_t bits_off; /* from the FILTER's base */ |
| 67 |
|
| uint64_t capacity; /* the n it was sized for */ |
| 68 |
|
| volatile uint64_t added; /* add() calls that set at least one bit */ |
| 69 |
|
| volatile uint64_t seen; /* add() calls that found every bit set */ |
| 70 |
|
| volatile unsigned char locks[SA_LOCK_STRIPES]; |
| 71 |
|
| } sa_bloom_hdr; |
| 72 |
|
| |
| 73 |
|
| #ifndef SA_BLOOM_FWD |
| 74 |
|
| #define SA_BLOOM_FWD |
| 75 |
|
| typedef struct sa_bloom sa_bloom; |
| 76 |
|
| #endif |
| 77 |
|
| struct sa_bloom { |
| 78 |
|
| sa_region *arena; |
| 79 |
|
| sa_bloom_hdr *hdr; |
| 80 |
|
| volatile uint64_t *words; |
| 81 |
|
| uint64_t nbits; |
| 82 |
|
| uint64_t nwords; |
| 83 |
|
| uint32_t nhash; |
| 84 |
|
| }; |
| 85 |
|
| |
| 86 |
|
| /* Round the bits up to a whole number of 64-bit words. */ |
| 87 |
70 |
| static uint64_t sa_bloom_words(uint64_t nbits) { |
| 88 |
70 |
| return (nbits + 63u) / 64u; |
| 89 |
|
| } |
| 90 |
|
| |
| 91 |
42 |
| static uint64_t sa_bloom_bytes(uint64_t nbits) { |
| 92 |
42 |
| return sa_align_up((uint64_t)sizeof(sa_bloom_hdr)) |
| 93 |
42 |
| + sa_bloom_words(nbits) * 8u; |
| 94 |
|
| } |
| 95 |
|
| |
| 96 |
|
| /* The bits and hash count for n items at a false-positive rate p. |
| 97 |
|
| * |
| 98 |
|
| * Falls back to eight bits per item and five hashes where there is no libm, |
| 99 |
|
| * which is roughly p = 0.02 - a working filter rather than none at all, and the |
| 100 |
|
| * build says so at configure time. */ |
| 101 |
13 |
| static void sa_bloom_size(uint64_t n, double p, uint64_t *nbits, uint32_t *k) { |
| 102 |
|
| uint64_t m; |
| 103 |
|
| uint32_t kk; |
| 104 |
|
| |
| 105 |
13 |
▶ | if (n < 1) n = 1; |
Branch: 1 branch
| Branch | True | False | Total |
| if (n < 1) n = 1; |
0 |
13 |
13 |
|
| 106 |
|
| #ifdef SA_NO_LIBM |
| 107 |
|
| (void)p; |
| 108 |
|
| m = n * 8u; |
| 109 |
|
| kk = 5; |
| 110 |
|
| #else |
| 111 |
13 |
▶ | if (!(p > 0.0) || p >= 1.0) p = 0.01; |
Branch: 2 branches
| Branch | True | False | Total |
| if (!(p > 0.0) || p >= 1.0) p = 0.01; |
13 |
0 |
13 |
| if (!(p > 0.0) || p >= 1.0) p = 0.01; |
0 |
13 |
13 |
|
| 112 |
|
| { |
| 113 |
13 |
| double ln2 = 0.6931471805599453; |
| 114 |
13 |
| double md = -((double)n) * log(p) / (ln2 * ln2); |
| 115 |
13 |
▶ | if (md < 64.0) md = 64.0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (md < 64.0) md = 64.0; |
0 |
13 |
13 |
|
| 116 |
13 |
| m = (uint64_t)(md + 0.5); |
| 117 |
13 |
| kk = (uint32_t)((md / (double)n) * ln2 + 0.5); |
| 118 |
|
| } |
| 119 |
|
| #endif |
| 120 |
13 |
▶ | if (kk < 1) kk = 1; |
Branch: 1 branch
| Branch | True | False | Total |
| if (kk < 1) kk = 1; |
0 |
13 |
13 |
|
| 121 |
13 |
▶ | if (kk > SA_BLOOM_MAX_K) kk = SA_BLOOM_MAX_K; |
Branch: 1 branch
| Branch | True | False | Total |
| if (kk > SA_BLOOM_MAX_K) kk = SA_BLOOM_MAX_K; |
0 |
13 |
13 |
|
| 122 |
13 |
| m = sa_bloom_words(m) * 64u; /* whole words */ |
| 123 |
13 |
▶ | if (nbits) *nbits = m; |
Branch: 1 branch
| Branch | True | False | Total |
| if (nbits) *nbits = m; |
13 |
0 |
13 |
|
| 124 |
13 |
▶ | if (k) *k = kk; |
Branch: 1 branch
| Branch | True | False | Total |
| if (k) *k = kk; |
13 |
0 |
13 |
|
| 125 |
13 |
| } |
| 126 |
|
| |
| 127 |
|
| /* The second hash. A finalising mix rather than a second pass over the key: the |
| 128 |
|
| * key has already been read once and reading it again to get an independent |
| 129 |
|
| * value is the cost this avoids. */ |
| 130 |
59038 |
| static uint64_t sa_bloom_mix(uint64_t h) { |
| 131 |
59038 |
| h ^= h >> 33; |
| 132 |
59038 |
| h *= 0xff51afd7ed558ccdULL; |
| 133 |
59038 |
| h ^= h >> 33; |
| 134 |
59038 |
| h *= 0xc4ceb9fe1a85ec53ULL; |
| 135 |
59038 |
| h ^= h >> 33; |
| 136 |
59038 |
| return h; |
| 137 |
|
| } |
| 138 |
|
| |
| 139 |
14 |
| static sa_bloom *sa_bloom_bind(sa_region *arena, sa_reg *e, |
| 140 |
|
| uint64_t nbits, uint32_t nhash, int *err) |
| 141 |
|
| { |
| 142 |
|
| #if !SA_HAVE_ATOMICS |
| 143 |
|
| (void)arena; (void)e; (void)nbits; (void)nhash; |
| 144 |
|
| if (err) *err = SA_E_NOATOMICS; |
| 145 |
|
| return NULL; |
| 146 |
|
| #else |
| 147 |
|
| sa_bloom *b; |
| 148 |
|
| sa_bloom_hdr *h; |
| 149 |
|
| uint64_t hash; |
| 150 |
|
| |
| 151 |
14 |
▶ | if (err) *err = SA_E_OK; |
Branch: 1 branch
| Branch | True | False | Total |
| if (err) *err = SA_E_OK; |
14 |
0 |
14 |
|
| 152 |
14 |
▶ | if (!arena || !e) { if (err) *err = SA_E_NOENT; return NULL; } |
Branch: 3 branches
| Branch | True | False | Total |
| if (!arena || !e) { if (err) *err = SA_E_NOENT; return NULL; } |
14 |
0 |
14 |
| if (!arena || !e) { if (err) *err = SA_E_NOENT; return NULL; } |
0 |
14 |
14 |
| if (!arena || !e) { if (err) *err = SA_E_NOENT; return NULL; } |
0 |
0 |
0 |
|
| 153 |
|
| |
| 154 |
14 |
| h = (sa_bloom_hdr *)sa_ptr_len(arena, e->off, sizeof(sa_bloom_hdr)); |
| 155 |
14 |
▶ | if (!h) { if (err) *err = SA_E_NOENT; return NULL; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (!h) { if (err) *err = SA_E_NOENT; return NULL; } |
0 |
14 |
14 |
| if (!h) { if (err) *err = SA_E_NOENT; return NULL; } |
0 |
0 |
0 |
|
| 156 |
|
| |
| 157 |
14 |
▶ | if (sa_at_load32_acq(&h->magic) != SA_BLOOM_MAGIC) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (sa_at_load32_acq(&h->magic) != SA_BLOOM_MAGIC) { |
14 |
0 |
14 |
|
| 158 |
14 |
| hash = sa_at_fnv(e->name, strlen(e->name)); |
| 159 |
14 |
▶ | if (sa_at_lock(h->locks, hash)) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (sa_at_lock(h->locks, hash)) { |
14 |
0 |
14 |
|
| 160 |
14 |
▶ | if (sa_at_load32_acq(&h->magic) != SA_BLOOM_MAGIC) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (sa_at_load32_acq(&h->magic) != SA_BLOOM_MAGIC) { |
14 |
0 |
14 |
|
| 161 |
14 |
▶ | if (!nbits || !nhash || sa_bloom_bytes(nbits) > e->len) { |
Branch: 3 branches
| Branch | True | False | Total |
| if (!nbits || !nhash || sa_bloom_bytes(nbits) > e->len) { |
14 |
0 |
14 |
| if (!nbits || !nhash || sa_bloom_bytes(nbits) > e->len) { |
14 |
0 |
14 |
| if (!nbits || !nhash || sa_bloom_bytes(nbits) > e->len) { |
0 |
14 |
14 |
|
| 162 |
0 |
| sa_at_unlock(h->locks, hash); |
| 163 |
0 |
▶ | if (err) *err = SA_E_FULL; |
Branch: 1 branch
| Branch | True | False | Total |
| if (err) *err = SA_E_FULL; |
0 |
0 |
0 |
|
| 164 |
0 |
| return NULL; |
| 165 |
|
| } |
| 166 |
14 |
| memset((void *)h, 0, (size_t)sa_bloom_bytes(nbits)); |
| 167 |
14 |
| h->nbits = nbits; |
| 168 |
14 |
| h->nhash = nhash; |
| 169 |
14 |
| h->bits_off = sa_align_up((uint64_t)sizeof(sa_bloom_hdr)); |
| 170 |
14 |
| sa_at_store32_rel(&h->magic, SA_BLOOM_MAGIC); |
| 171 |
|
| } |
| 172 |
14 |
| sa_at_unlock(h->locks, hash); |
| 173 |
|
| } |
| 174 |
14 |
▶ | if (!sa_wait_magic32(&h->magic, SA_BLOOM_MAGIC)) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (!sa_wait_magic32(&h->magic, SA_BLOOM_MAGIC)) { |
0 |
14 |
14 |
|
| 175 |
0 |
▶ | if (err) *err = SA_E_MAGIC; |
Branch: 1 branch
| Branch | True | False | Total |
| if (err) *err = SA_E_MAGIC; |
0 |
0 |
0 |
|
| 176 |
0 |
| return NULL; |
| 177 |
|
| } |
| 178 |
|
| } |
| 179 |
|
| |
| 180 |
|
| /* THE GEOMETRY IN THE HEADER IS ALSO SOMEBODY ELSE'S NUMBER. |
| 181 |
|
| * |
| 182 |
|
| * The branch above only checks a size when this process is the one doing |
| 183 |
|
| * the INITIALISING. A process that finds the magic already set reads the |
| 184 |
|
| * shape out of the shared header and believed it, so a header claiming |
| 185 |
|
| * four billion slots put every later read past the end of the mapping. |
| 186 |
|
| * sa_reg_ok makes `len` trustworthy; this makes the shape trustworthy. */ |
| 187 |
|
| |
| 188 |
14 |
▶ | if ((nbits && h->nbits != nbits) || (nhash && h->nhash != nhash)) { |
Branch: 4 branches
| Branch | True | False | Total |
| if ((nbits && h->nbits != nbits) || (nhash && h->nhash != nhash)) { |
14 |
0 |
14 |
| if ((nbits && h->nbits != nbits) || (nhash && h->nhash != nhash)) { |
14 |
0 |
14 |
| if ((nbits && h->nbits != nbits) || (nhash && h->nhash != nhash)) { |
14 |
0 |
14 |
| if ((nbits && h->nbits != nbits) || (nhash && h->nhash != nhash)) { |
0 |
14 |
14 |
|
| 189 |
0 |
▶ | if (err) *err = SA_E_NAME; |
Branch: 1 branch
| Branch | True | False | Total |
| if (err) *err = SA_E_NAME; |
0 |
0 |
0 |
|
| 190 |
0 |
| return NULL; |
| 191 |
|
| } |
| 192 |
|
| |
| 193 |
14 |
| b = (sa_bloom *)calloc(1, sizeof(sa_bloom)); |
| 194 |
14 |
▶ | if (!b) { if (err) *err = SA_E_NOMEM; return NULL; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (!b) { if (err) *err = SA_E_NOMEM; return NULL; } |
0 |
14 |
14 |
| if (!b) { if (err) *err = SA_E_NOMEM; return NULL; } |
0 |
0 |
0 |
|
| 195 |
14 |
| b->arena = arena; |
| 196 |
14 |
| b->hdr = h; |
| 197 |
14 |
| b->words = (volatile uint64_t *)((char *)h + (size_t)h->bits_off); |
| 198 |
14 |
| b->nbits = h->nbits; |
| 199 |
14 |
| b->nwords = sa_bloom_words(h->nbits); |
| 200 |
14 |
| b->nhash = h->nhash; |
| 201 |
14 |
| return b; |
| 202 |
|
| #endif |
| 203 |
|
| } |
| 204 |
|
| |
| 205 |
14 |
| static void sa_bloom_free(sa_bloom *b) { free(b); } |
| 206 |
|
| |
| 207 |
|
| /* Add a key. Returns 1 when every bit was ALREADY set - meaning the key had |
| 208 |
|
| * probably been added before - and 0 when this call set at least one. |
| 209 |
|
| * |
| 210 |
|
| * THAT ANSWER IS PER BIT, NOT PER KEY. Two processes adding the same key at the |
| 211 |
|
| * same instant can both be told it was new, because each set some of the bits |
| 212 |
|
| * the other was about to set. For a filter that is harmless; for a caller using |
| 213 |
|
| * this to do a job exactly once it is not, and that caller wants a lock or a |
| 214 |
|
| * compare-and-set, not a bloom filter. */ |
| 215 |
25820 |
| static int sa_bloom_add(sa_bloom *b, const char *key, uint32_t klen) { |
| 216 |
|
| #if !SA_HAVE_ATOMICS |
| 217 |
|
| (void)b; (void)key; (void)klen; |
| 218 |
|
| return 0; |
| 219 |
|
| #else |
| 220 |
25820 |
| uint64_t h1 = sa_at_fnv(key, klen); |
| 221 |
25820 |
| uint64_t h2 = sa_bloom_mix(h1) | 1u; /* odd, so the walk covers */ |
| 222 |
|
| uint32_t i; |
| 223 |
25820 |
| int all_set = 1; |
| 224 |
|
| |
| 225 |
206560 |
▶ | for (i = 0; i < b->nhash; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < b->nhash; i++) { |
180740 |
25820 |
206560 |
|
| 226 |
180740 |
| uint64_t bit = (h1 + (uint64_t)i * h2) % b->nbits; |
| 227 |
180740 |
| uint64_t mask = 1ULL << (bit & 63u); |
| 228 |
180740 |
| uint64_t was = sa_at_fetch_or64(&b->words[bit >> 6], mask); |
| 229 |
180740 |
▶ | if (!(was & mask)) all_set = 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!(was & mask)) all_set = 0; |
128901 |
51839 |
180740 |
|
| 230 |
|
| } |
| 231 |
|
| |
| 232 |
25820 |
▶ | if (all_set) sa_at_fetch_add64(&b->hdr->seen, 1); |
Branch: 1 branch
| Branch | True | False | Total |
| if (all_set) sa_at_fetch_add64(&b->hdr->seen, 1); |
50 |
25770 |
25820 |
|
| 233 |
25770 |
| else sa_at_fetch_add64(&b->hdr->added, 1); |
| 234 |
25820 |
| return all_set; |
| 235 |
|
| #endif |
| 236 |
|
| } |
| 237 |
|
| |
| 238 |
|
| /* Has this key probably been added? A 0 is exact; a 1 may be a coincidence. */ |
| 239 |
33218 |
| static int sa_bloom_check(sa_bloom *b, const char *key, uint32_t klen) { |
| 240 |
|
| #if !SA_HAVE_ATOMICS |
| 241 |
|
| (void)b; (void)key; (void)klen; |
| 242 |
|
| return 0; |
| 243 |
|
| #else |
| 244 |
33218 |
| uint64_t h1 = sa_at_fnv(key, klen); |
| 245 |
33218 |
| uint64_t h2 = sa_bloom_mix(h1) | 1u; |
| 246 |
|
| uint32_t i; |
| 247 |
|
| |
| 248 |
147039 |
▶ | for (i = 0; i < b->nhash; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < b->nhash; i++) { |
133638 |
13401 |
147039 |
|
| 249 |
133638 |
| uint64_t bit = (h1 + (uint64_t)i * h2) % b->nbits; |
| 250 |
133638 |
| uint64_t mask = 1ULL << (bit & 63u); |
| 251 |
|
| /* One clear bit is a definite no, and there is no point reading the |
| 252 |
|
| * rest. A miss is the common case in every use this has. */ |
| 253 |
133638 |
▶ | if (!(sa_at_load64_acq(&b->words[bit >> 6]) & mask)) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!(sa_at_load64_acq(&b->words[bit >> 6]) & mask)) return 0; |
19817 |
113821 |
133638 |
|
| 254 |
|
| } |
| 255 |
13401 |
| return 1; |
| 256 |
|
| #endif |
| 257 |
|
| } |
| 258 |
|
| |
| 259 |
|
| /* How many bits are set. O(m/64), so it is a question for a status page rather |
| 260 |
|
| * than for a request path. */ |
| 261 |
14 |
| static uint64_t sa_bloom_popcount(sa_bloom *b) { |
| 262 |
|
| #if !SA_HAVE_ATOMICS |
| 263 |
|
| (void)b; |
| 264 |
|
| return 0; |
| 265 |
|
| #else |
| 266 |
14 |
| uint64_t i, n = 0; |
| 267 |
13498 |
▶ | for (i = 0; i < b->nwords; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < b->nwords; i++) { |
13484 |
14 |
13498 |
|
| 268 |
13484 |
| uint64_t w = sa_at_load64_acq(&b->words[i]); |
| 269 |
|
| /* The SWAR popcount rather than a builtin: __builtin_popcountll is not |
| 270 |
|
| * everywhere, and this is a status query, not a hot path. */ |
| 271 |
13484 |
| w = w - ((w >> 1) & 0x5555555555555555ULL); |
| 272 |
13484 |
| w = (w & 0x3333333333333333ULL) + ((w >> 2) & 0x3333333333333333ULL); |
| 273 |
13484 |
| w = (w + (w >> 4)) & 0x0f0f0f0f0f0f0f0fULL; |
| 274 |
13484 |
| n += (w * 0x0101010101010101ULL) >> 56; |
| 275 |
|
| } |
| 276 |
14 |
| return n; |
| 277 |
|
| #endif |
| 278 |
|
| } |
| 279 |
|
| |
| 280 |
|
| /* Forget everything. |
| 281 |
|
| * |
| 282 |
|
| * Under the lock, but readers do not take it: a check running concurrently may |
| 283 |
|
| * see some words cleared and some not, and answer either way for a key that is |
| 284 |
|
| * being forgotten. That is exactly what it would have answered a moment either |
| 285 |
|
| * side, so there is nothing to protect it from - but it is the reason this is |
| 286 |
|
| * `reset` and not a transaction. */ |
| 287 |
2 |
| static void sa_bloom_reset(sa_bloom *b) { |
| 288 |
|
| #if SA_HAVE_ATOMICS |
| 289 |
2 |
| uint64_t hash = (uint64_t)(uintptr_t)b->hdr; |
| 290 |
|
| uint64_t i; |
| 291 |
2 |
▶ | if (!sa_at_lock(b->hdr->locks, hash)) return; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!sa_at_lock(b->hdr->locks, hash)) return; |
0 |
2 |
2 |
|
| 292 |
302 |
▶ | for (i = 0; i < b->nwords; i++) sa_at_store64_rel(&b->words[i], 0); |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < b->nwords; i++) sa_at_store64_rel(&b->words[i], 0); |
300 |
2 |
302 |
|
| 293 |
2 |
| sa_at_store64_rel(&b->hdr->added, 0); |
| 294 |
2 |
| sa_at_store64_rel(&b->hdr->seen, 0); |
| 295 |
2 |
| sa_at_unlock(b->hdr->locks, hash); |
| 296 |
|
| #else |
| 297 |
|
| (void)b; |
| 298 |
|
| #endif |
| 299 |
|
| } |
| 300 |
|
| |
| 301 |
|
| /* How many distinct keys the set bits suggest. An estimate, and one that gets |
| 302 |
|
| * worse as the filter fills: n* = -(m/k) ln(1 - X/m). */ |
| 303 |
6 |
| static uint64_t sa_bloom_estimate(sa_bloom *b) { |
| 304 |
|
| #if defined(SA_NO_LIBM) || !SA_HAVE_ATOMICS |
| 305 |
|
| return sa_bloom_popcount(b) / (b->nhash ? b->nhash : 1); |
| 306 |
|
| #else |
| 307 |
6 |
| uint64_t set = sa_bloom_popcount(b); |
| 308 |
6 |
| double m = (double)b->nbits, k = (double)b->nhash; |
| 309 |
6 |
▶ | if (set == 0) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (set == 0) return 0; |
2 |
4 |
6 |
|
| 310 |
4 |
▶ | if ((double)set >= m) return (uint64_t)-1; /* saturated */ |
Branch: 1 branch
| Branch | True | False | Total |
| if ((double)set >= m) return (uint64_t)-1; /* saturated */ |
0 |
4 |
4 |
|
| 311 |
4 |
| return (uint64_t)(-(m / k) * log(1.0 - (double)set / m) + 0.5); |
| 312 |
|
| #endif |
| 313 |
|
| } |
| 314 |
|
| |
| 315 |
|
| #endif /* SA_BLOOM_H */ |