| 1 |
|
| #ifndef SA_CMS_H |
| 2 |
|
| #define SA_CMS_H |
| 3 |
|
| |
| 4 |
|
| /* sa_cms.h - a count-min sketch: how often, in fixed space. Perl-free. |
| 5 |
|
| * |
| 6 |
|
| * ---- the question the other tenants do not answer --------------------------- |
| 7 |
|
| * |
| 8 |
|
| * The bloom filter answers "have I seen this key". The histogram answers "what |
| 9 |
|
| * does the distribution of these numbers look like". Neither answers B<how many |
| 10 |
|
| * times have I seen THIS key>, and that is the question behind every piece of |
| 11 |
|
| * abuse detection: which client is hammering the gateway, which query is being |
| 12 |
|
| * repeated, which key deserves a limit that the others do not. |
| 13 |
|
| * |
| 14 |
|
| * A map would answer it exactly and needs a slot per key. Key cardinality is |
| 15 |
|
| * the one thing an abuse detector cannot bound - the whole problem is that |
| 16 |
|
| * somebody is generating keys - so the exact structure is the one that falls |
| 17 |
|
| * over first. |
| 18 |
|
| * |
| 19 |
|
| * A sketch does not store keys at all. d rows of w counters, each key hashed to |
| 20 |
|
| * one counter per row, every add incrementing all d. The estimate is the |
| 21 |
|
| * SMALLEST of them, because collisions can only ever have added. |
| 22 |
|
| * |
| 23 |
|
| * ---- it overestimates, and it never underestimates --------------------------- |
| 24 |
|
| * |
| 25 |
|
| * That asymmetry is the whole contract, and it is the right way round. A count |
| 26 |
|
| * that can only be too high never MISSES a heavy hitter; it can only accuse a |
| 27 |
|
| * light key of being heavier than it is, and how often it does that is the |
| 28 |
|
| * number you chose when you sized it. |
| 29 |
|
| * |
| 30 |
|
| * With w = e/epsilon and d = ln(1/delta), the estimate exceeds the truth by |
| 31 |
|
| * more than epsilon * N with probability at most delta, where N is the total |
| 32 |
|
| * of everything added. Note what the error is relative to: not the key's own |
| 33 |
|
| * count, but the WHOLE. A sketch sized for one percent on a stream of a million |
| 34 |
|
| * is accurate to ten thousand, which is useless for a key seen twice and |
| 35 |
|
| * exactly right for finding the one seen half a million times. |
| 36 |
|
| * |
| 37 |
|
| * So `total` is in the header and in the stats. An estimate quoted without it |
| 38 |
|
| * is a number with no error bar. |
| 39 |
|
| * |
| 40 |
|
| * ---- why NOT conservative update -------------------------------------------- |
| 41 |
|
| * |
| 42 |
|
| * The well-known improvement is to increment only those counters that are at |
| 43 |
|
| * the current minimum, which cuts overestimation substantially. It is refused |
| 44 |
|
| * here, and the reason is this dist rather than the algorithm. |
| 45 |
|
| * |
| 46 |
|
| * Conservative update is read-then-write: read all d, work out the minimum, |
| 47 |
|
| * write back some of them. Two processes doing that at once can each decide a |
| 48 |
|
| * counter needs no increment because the other's is not visible yet, and the |
| 49 |
|
| * counter then ends up short. A sketch that can UNDERESTIMATE has lost the only |
| 50 |
|
| * guarantee it offers - a heavy hitter can hide - and it fails silently, |
| 51 |
|
| * because a low answer looks exactly like a quiet key. |
| 52 |
|
| * |
| 53 |
|
| * A plain increment is one fetch-add per row, needs no lock, cannot be lost, |
| 54 |
|
| * and cannot be corrupted by a process dying between two of them: the worst a |
| 55 |
|
| * crash leaves behind is a key counted in some rows and not others, which reads |
| 56 |
|
| * as a slightly LOWER estimate on a structure that was going to be high anyway. |
| 57 |
|
| * |
| 58 |
|
| * ---- what it cannot do ------------------------------------------------------- |
| 59 |
|
| * |
| 60 |
|
| * IT CANNOT LIST ANYTHING. A sketch holds no keys, so it can answer about a key |
| 61 |
|
| * you name and can never tell you which keys exist. "The top ten" is a |
| 62 |
|
| * different structure: a candidate set beside the sketch, which is a Map of the |
| 63 |
|
| * keys currently believed to be heavy, consulted and updated when a key's |
| 64 |
|
| * estimate crosses the smallest of them. |
| 65 |
|
| * |
| 66 |
|
| * IT CANNOT DECREMENT. Subtracting breaks the min estimate the same way |
| 67 |
|
| * conservative update does, and for the same reason. A sketch is reset, or |
| 68 |
|
| * rotated, not decremented. |
| 69 |
|
| * |
| 70 |
|
| * Needs sa_arena.h. |
| 71 |
|
| */ |
| 72 |
|
| |
| 73 |
|
| #include "sa/sa_arena.h" |
| 74 |
|
| |
| 75 |
|
| #ifndef SA_NO_LIBM |
| 76 |
|
| # include <math.h> |
| 77 |
|
| #endif |
| 78 |
|
| |
| 79 |
|
| #define SA_CMS_MAGIC 0x534D4353u /* 'S','C','M','S' little-endian */ |
| 80 |
|
| |
| 81 |
|
| #define SA_CMS_MAX_ROWS 32 |
| 82 |
|
| |
| 83 |
|
| typedef struct { |
| 84 |
|
| volatile uint32_t magic; /* published LAST at init */ |
| 85 |
|
| uint32_t rows; /* d */ |
| 86 |
|
| uint64_t width; /* w, a power of two */ |
| 87 |
|
| uint64_t cells_off; /* from the SKETCH's base */ |
| 88 |
|
| volatile uint64_t total; /* everything ever added, for the error bar */ |
| 89 |
|
| volatile uint64_t adds; /* add() calls */ |
| 90 |
|
| volatile unsigned char locks[SA_LOCK_STRIPES]; |
| 91 |
|
| } sa_cms_hdr; |
| 92 |
|
| |
| 93 |
|
| #ifndef SA_CMS_FWD |
| 94 |
|
| #define SA_CMS_FWD |
| 95 |
|
| typedef struct sa_cms sa_cms; |
| 96 |
|
| #endif |
| 97 |
|
| |
| 98 |
|
| struct sa_cms { |
| 99 |
|
| sa_region *arena; |
| 100 |
|
| sa_cms_hdr *hdr; |
| 101 |
|
| volatile uint64_t *cells; |
| 102 |
|
| uint32_t rows; |
| 103 |
|
| uint64_t width; |
| 104 |
|
| uint64_t mask; |
| 105 |
|
| }; |
| 106 |
|
| |
| 107 |
|
| /* Sixty-four bit counters, not thirty-two. |
| 108 |
|
| * |
| 109 |
|
| * A sketch counts a stream, and a stream on a busy gateway passes four billion |
| 110 |
|
| * in a day. A 32-bit counter would need saturating arithmetic to avoid wrapping |
| 111 |
|
| * to nearly zero - which is an underestimate, the one thing this structure |
| 112 |
|
| * promises never to produce - and saturating means a compare-and-swap loop |
| 113 |
|
| * rather than a fetch-add. Eight bytes a cell buys a plain atomic increment and |
| 114 |
|
| * a counter nobody has to think about. */ |
| 115 |
111 |
| static uint64_t sa_cms_bytes(uint32_t rows, uint64_t width) { |
| 116 |
111 |
| return sa_align_up((uint64_t)sizeof(sa_cms_hdr)) |
| 117 |
111 |
| + (uint64_t)rows * width * 8u; |
| 118 |
|
| } |
| 119 |
|
| |
| 120 |
32 |
| static uint64_t sa_cms_pow2(uint64_t n) { |
| 121 |
32 |
| uint64_t p = 64; |
| 122 |
32 |
▶ | if (n < 64) return 64; |
Branch: 1 branch
| Branch | True | False | Total |
| if (n < 64) return 64; |
0 |
32 |
32 |
|
| 123 |
192 |
▶ | while (p < n && p < (uint64_t)1 << 40) p <<= 1; |
Branch: 2 branches
| Branch | True | False | Total |
| while (p < n && p < (uint64_t)1 << 40) p <<= 1; |
160 |
32 |
192 |
| while (p < n && p < (uint64_t)1 << 40) p <<= 1; |
160 |
0 |
160 |
|
| 124 |
32 |
| return p; |
| 125 |
|
| } |
| 126 |
|
| |
| 127 |
|
| /* Rows and width from the two numbers a caller actually has: how much error it |
| 128 |
|
| * will accept as a fraction of the total, and how sure it wants to be. |
| 129 |
|
| * |
| 130 |
|
| * w = e / epsilon d = ln(1 / delta) |
| 131 |
|
| * |
| 132 |
|
| * The width is rounded UP to a power of two, so the row index is a mask rather |
| 133 |
|
| * than a division on a path that runs per row per add. Rounding up only reduces |
| 134 |
|
| * epsilon, so the caller gets at least the accuracy it asked for. */ |
| 135 |
24 |
| static void sa_cms_size(double epsilon, double confidence, |
| 136 |
|
| uint32_t *rows, uint64_t *width) |
| 137 |
|
| { |
| 138 |
|
| uint64_t w; |
| 139 |
|
| uint32_t d; |
| 140 |
|
| |
| 141 |
|
| #ifdef SA_NO_LIBM |
| 142 |
|
| (void)confidence; |
| 143 |
|
| if (!(epsilon > 0.0) || epsilon >= 1.0) epsilon = 0.01; |
| 144 |
|
| w = (uint64_t)(2.718281828459045 / epsilon + 0.5); |
| 145 |
|
| d = 5; /* delta about 0.007 */ |
| 146 |
|
| #else |
| 147 |
|
| double delta; |
| 148 |
24 |
▶ | if (!(epsilon > 0.0) || epsilon >= 1.0) epsilon = 0.01; |
Branch: 2 branches
| Branch | True | False | Total |
| if (!(epsilon > 0.0) || epsilon >= 1.0) epsilon = 0.01; |
24 |
0 |
24 |
| if (!(epsilon > 0.0) || epsilon >= 1.0) epsilon = 0.01; |
0 |
24 |
24 |
|
| 149 |
24 |
▶ | if (!(confidence > 0.0) || confidence >= 1.0) confidence = 0.99; |
Branch: 2 branches
| Branch | True | False | Total |
| if (!(confidence > 0.0) || confidence >= 1.0) confidence = 0.99; |
24 |
0 |
24 |
| if (!(confidence > 0.0) || confidence >= 1.0) confidence = 0.99; |
0 |
24 |
24 |
|
| 150 |
24 |
| delta = 1.0 - confidence; |
| 151 |
24 |
| w = (uint64_t)(2.718281828459045 / epsilon + 0.5); |
| 152 |
|
| { |
| 153 |
24 |
| double dd = -log(delta); |
| 154 |
24 |
▶ | if (dd < 1.0) dd = 1.0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (dd < 1.0) dd = 1.0; |
0 |
24 |
24 |
|
| 155 |
24 |
| d = (uint32_t)(dd + 0.999); |
| 156 |
|
| } |
| 157 |
|
| #endif |
| 158 |
24 |
▶ | if (d < 1) d = 1; |
Branch: 1 branch
| Branch | True | False | Total |
| if (d < 1) d = 1; |
0 |
24 |
24 |
|
| 159 |
24 |
▶ | if (d > SA_CMS_MAX_ROWS) d = SA_CMS_MAX_ROWS; |
Branch: 1 branch
| Branch | True | False | Total |
| if (d > SA_CMS_MAX_ROWS) d = SA_CMS_MAX_ROWS; |
0 |
24 |
24 |
|
| 160 |
24 |
| w = sa_cms_pow2(w); |
| 161 |
24 |
▶ | if (rows) *rows = d; |
Branch: 1 branch
| Branch | True | False | Total |
| if (rows) *rows = d; |
24 |
0 |
24 |
|
| 162 |
24 |
▶ | if (width) *width = w; |
Branch: 1 branch
| Branch | True | False | Total |
| if (width) *width = w; |
24 |
0 |
24 |
|
| 163 |
24 |
| } |
| 164 |
|
| |
| 165 |
|
| /* The second hash. A finalising mix rather than a second pass over the key: the |
| 166 |
|
| * key has been read once already, and reading it again to get an independent |
| 167 |
|
| * value is the cost this avoids. Kirsch and Mitzenmacher: h1 + i*h2 has the |
| 168 |
|
| * same behaviour as d independent functions. */ |
| 169 |
152948 |
| static uint64_t sa_cms_mix(uint64_t h) { |
| 170 |
152948 |
| h ^= h >> 33; |
| 171 |
152948 |
| h *= 0xff51afd7ed558ccdULL; |
| 172 |
152948 |
| h ^= h >> 33; |
| 173 |
152948 |
| h *= 0xc4ceb9fe1a85ec53ULL; |
| 174 |
152948 |
| h ^= h >> 33; |
| 175 |
152948 |
| return h; |
| 176 |
|
| } |
| 177 |
|
| |
| 178 |
31 |
| static sa_cms *sa_cms_bind(sa_region *arena, sa_reg *e, uint32_t rows, |
| 179 |
|
| uint64_t width, int *err) |
| 180 |
|
| { |
| 181 |
|
| #if !SA_HAVE_ATOMICS |
| 182 |
|
| (void)arena; (void)e; (void)rows; (void)width; |
| 183 |
|
| if (err) *err = SA_E_NOATOMICS; |
| 184 |
|
| return NULL; |
| 185 |
|
| #else |
| 186 |
|
| sa_cms *s; |
| 187 |
|
| sa_cms_hdr *h; |
| 188 |
|
| uint64_t hash; |
| 189 |
|
| |
| 190 |
31 |
▶ | if (err) *err = SA_E_OK; |
Branch: 1 branch
| Branch | True | False | Total |
| if (err) *err = SA_E_OK; |
31 |
0 |
31 |
|
| 191 |
31 |
▶ | 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; } |
31 |
0 |
31 |
| if (!arena || !e) { if (err) *err = SA_E_NOENT; return NULL; } |
0 |
31 |
31 |
| if (!arena || !e) { if (err) *err = SA_E_NOENT; return NULL; } |
0 |
0 |
0 |
|
| 192 |
|
| |
| 193 |
31 |
| h = (sa_cms_hdr *)sa_ptr_len(arena, e->off, sizeof(sa_cms_hdr)); |
| 194 |
31 |
▶ | 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 |
31 |
31 |
| if (!h) { if (err) *err = SA_E_NOENT; return NULL; } |
0 |
0 |
0 |
|
| 195 |
|
| |
| 196 |
31 |
▶ | if (sa_at_load32_acq(&h->magic) != SA_CMS_MAGIC) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (sa_at_load32_acq(&h->magic) != SA_CMS_MAGIC) { |
31 |
0 |
31 |
|
| 197 |
31 |
| hash = sa_at_fnv(e->name, strlen(e->name)); |
| 198 |
31 |
▶ | if (sa_at_lock(h->locks, hash)) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (sa_at_lock(h->locks, hash)) { |
31 |
0 |
31 |
|
| 199 |
31 |
▶ | if (sa_at_load32_acq(&h->magic) != SA_CMS_MAGIC) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (sa_at_load32_acq(&h->magic) != SA_CMS_MAGIC) { |
31 |
0 |
31 |
|
| 200 |
31 |
▶ | if (!rows || !width || sa_cms_bytes(rows, width) > e->len) { |
Branch: 3 branches
| Branch | True | False | Total |
| if (!rows || !width || sa_cms_bytes(rows, width) > e->len) { |
31 |
0 |
31 |
| if (!rows || !width || sa_cms_bytes(rows, width) > e->len) { |
31 |
0 |
31 |
| if (!rows || !width || sa_cms_bytes(rows, width) > e->len) { |
0 |
31 |
31 |
|
| 201 |
0 |
| sa_at_unlock(h->locks, hash); |
| 202 |
0 |
▶ | if (err) *err = SA_E_FULL; |
Branch: 1 branch
| Branch | True | False | Total |
| if (err) *err = SA_E_FULL; |
0 |
0 |
0 |
|
| 203 |
0 |
| return NULL; |
| 204 |
|
| } |
| 205 |
31 |
| memset((void *)h, 0, (size_t)sa_cms_bytes(rows, width)); |
| 206 |
31 |
| h->rows = rows; |
| 207 |
31 |
| h->width = width; |
| 208 |
31 |
| h->cells_off = sa_align_up((uint64_t)sizeof(sa_cms_hdr)); |
| 209 |
31 |
| sa_at_store32_rel(&h->magic, SA_CMS_MAGIC); |
| 210 |
|
| } |
| 211 |
31 |
| sa_at_unlock(h->locks, hash); |
| 212 |
|
| } |
| 213 |
31 |
▶ | if (!sa_wait_magic32(&h->magic, SA_CMS_MAGIC)) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (!sa_wait_magic32(&h->magic, SA_CMS_MAGIC)) { |
0 |
31 |
31 |
|
| 214 |
0 |
▶ | if (err) *err = SA_E_MAGIC; |
Branch: 1 branch
| Branch | True | False | Total |
| if (err) *err = SA_E_MAGIC; |
0 |
0 |
0 |
|
| 215 |
0 |
| return NULL; |
| 216 |
|
| } |
| 217 |
|
| } |
| 218 |
|
| |
| 219 |
|
| /* THE GEOMETRY IN THE HEADER IS ALSO SOMEBODY ELSE'S NUMBER. |
| 220 |
|
| * |
| 221 |
|
| * The branch above only checks a size when this process is the one doing |
| 222 |
|
| * the INITIALISING. A process that finds the magic already set reads the |
| 223 |
|
| * shape out of the shared header and believed it, so a header claiming |
| 224 |
|
| * four billion slots put every later read past the end of the mapping. |
| 225 |
|
| * sa_reg_ok makes `len` trustworthy; this makes the shape trustworthy. */ |
| 226 |
|
| |
| 227 |
31 |
▶ | if ((rows && h->rows != rows) || (width && h->width != width)) { |
Branch: 4 branches
| Branch | True | False | Total |
| if ((rows && h->rows != rows) || (width && h->width != width)) { |
31 |
0 |
31 |
| if ((rows && h->rows != rows) || (width && h->width != width)) { |
31 |
0 |
31 |
| if ((rows && h->rows != rows) || (width && h->width != width)) { |
31 |
0 |
31 |
| if ((rows && h->rows != rows) || (width && h->width != width)) { |
0 |
31 |
31 |
|
| 228 |
0 |
▶ | if (err) *err = SA_E_SHAPE; |
Branch: 1 branch
| Branch | True | False | Total |
| if (err) *err = SA_E_SHAPE; |
0 |
0 |
0 |
|
| 229 |
0 |
| return NULL; |
| 230 |
|
| } |
| 231 |
|
| |
| 232 |
31 |
| s = (sa_cms *)calloc(1, sizeof(sa_cms)); |
| 233 |
31 |
▶ | if (!s) { if (err) *err = SA_E_NOMEM; return NULL; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (!s) { if (err) *err = SA_E_NOMEM; return NULL; } |
0 |
31 |
31 |
| if (!s) { if (err) *err = SA_E_NOMEM; return NULL; } |
0 |
0 |
0 |
|
| 234 |
31 |
| s->arena = arena; |
| 235 |
31 |
| s->hdr = h; |
| 236 |
31 |
| s->cells = (volatile uint64_t *)((char *)h + (size_t)h->cells_off); |
| 237 |
31 |
| s->rows = h->rows; |
| 238 |
31 |
| s->width = h->width; |
| 239 |
31 |
| s->mask = h->width - 1; |
| 240 |
31 |
| return s; |
| 241 |
|
| #endif |
| 242 |
|
| } |
| 243 |
|
| |
| 244 |
31 |
| static void sa_cms_free(sa_cms *s) { free(s); } |
| 245 |
|
| |
| 246 |
|
| #if SA_HAVE_ATOMICS |
| 247 |
|
| |
| 248 |
|
| /* Add `n` to a key, and return what the sketch now believes its count to be. |
| 249 |
|
| * |
| 250 |
|
| * The answer is the minimum ACROSS THE ROWS AFTER THIS ADD, which is what a |
| 251 |
|
| * caller asking "has this key just crossed my threshold" wants, and it costs |
| 252 |
|
| * nothing extra: the values are already in hand. |
| 253 |
|
| * |
| 254 |
|
| * One fetch-add per row, no lock, and nothing to undo. A process that dies part |
| 255 |
|
| * way through has counted its key in some rows and not others, which reads back |
| 256 |
|
| * as a slightly lower estimate - never a corrupt one. */ |
| 257 |
148925 |
| static uint64_t sa_cms_add(sa_cms *s, const char *key, uint32_t klen, |
| 258 |
|
| uint64_t n) |
| 259 |
|
| { |
| 260 |
148925 |
| uint64_t h1, h2, min = 0; |
| 261 |
|
| uint32_t i; |
| 262 |
|
| |
| 263 |
148925 |
▶ | if (!s || !n) return 0; |
Branch: 2 branches
| Branch | True | False | Total |
| if (!s || !n) return 0; |
148925 |
0 |
148925 |
| if (!s || !n) return 0; |
0 |
148925 |
148925 |
|
| 264 |
148925 |
| h1 = sa_at_fnv(key, (size_t)klen); |
| 265 |
148925 |
| h2 = sa_cms_mix(h1) | 1u; /* odd, so the rows cannot coincide */ |
| 266 |
|
| |
| 267 |
842548 |
▶ | for (i = 0; i < s->rows; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < s->rows; i++) { |
693623 |
148925 |
842548 |
|
| 268 |
693623 |
| uint64_t idx = (h1 + (uint64_t)i * h2) & s->mask; |
| 269 |
693623 |
| volatile uint64_t *c = &s->cells[(uint64_t)i * s->width + idx]; |
| 270 |
693623 |
| uint64_t was = sa_at_fetch_add64(c, n); |
| 271 |
693623 |
▶ | if (i == 0 || was + n < min) min = was + n; |
Branch: 2 branches
| Branch | True | False | Total |
| if (i == 0 || was + n < min) min = was + n; |
544698 |
148925 |
693623 |
| if (i == 0 || was + n < min) min = was + n; |
101237 |
443461 |
544698 |
|
| 272 |
|
| } |
| 273 |
|
| |
| 274 |
148925 |
| sa_at_fetch_add64(&s->hdr->total, n); |
| 275 |
148925 |
| sa_at_fetch_add64(&s->hdr->adds, 1); |
| 276 |
148925 |
| return min; |
| 277 |
|
| } |
| 278 |
|
| |
| 279 |
|
| /* What the sketch believes, without adding to it. At most epsilon * total too |
| 280 |
|
| * high, with the confidence it was sized for, and never too low. */ |
| 281 |
4023 |
| static uint64_t sa_cms_estimate(sa_cms *s, const char *key, uint32_t klen) { |
| 282 |
4023 |
| uint64_t h1, h2, min = 0; |
| 283 |
|
| uint32_t i; |
| 284 |
|
| |
| 285 |
4023 |
▶ | if (!s) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!s) return 0; |
0 |
4023 |
4023 |
|
| 286 |
4023 |
| h1 = sa_at_fnv(key, (size_t)klen); |
| 287 |
4023 |
| h2 = sa_cms_mix(h1) | 1u; |
| 288 |
|
| |
| 289 |
21134 |
▶ | for (i = 0; i < s->rows; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < s->rows; i++) { |
17111 |
4023 |
21134 |
|
| 290 |
17111 |
| uint64_t idx = (h1 + (uint64_t)i * h2) & s->mask; |
| 291 |
17111 |
| uint64_t v = sa_at_load64_acq(&s->cells[(uint64_t)i * s->width + idx]); |
| 292 |
17111 |
▶ | if (i == 0 || v < min) min = v; |
Branch: 2 branches
| Branch | True | False | Total |
| if (i == 0 || v < min) min = v; |
13088 |
4023 |
17111 |
| if (i == 0 || v < min) min = v; |
1519 |
11569 |
13088 |
|
| 293 |
|
| } |
| 294 |
4023 |
| return min; |
| 295 |
|
| } |
| 296 |
|
| |
| 297 |
|
| /* Forget everything. |
| 298 |
|
| * |
| 299 |
|
| * Readers are not locked out, so a count running at the same moment may see the |
| 300 |
|
| * sketch half cleared and answer low for a key being forgotten - which is the |
| 301 |
|
| * one direction this structure otherwise never goes. It is the price of a reset |
| 302 |
|
| * that does not stop the world, and a caller rotating two sketches rather than |
| 303 |
|
| * clearing one never pays it. */ |
| 304 |
2 |
| static void sa_cms_reset(sa_cms *s) { |
| 305 |
|
| uint64_t i, n; |
| 306 |
2 |
▶ | if (!s) return; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!s) return; |
0 |
2 |
2 |
|
| 307 |
2 |
| n = (uint64_t)s->rows * s->width; |
| 308 |
2754 |
▶ | for (i = 0; i < n; i++) sa_at_store64_rel(&s->cells[i], 0); |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < n; i++) sa_at_store64_rel(&s->cells[i], 0); |
2752 |
2 |
2754 |
|
| 309 |
2 |
| sa_at_store64_rel(&s->hdr->total, 0); |
| 310 |
2 |
| sa_at_store64_rel(&s->hdr->adds, 0); |
| 311 |
|
| } |
| 312 |
|
| |
| 313 |
|
| /* The absolute error bound at the current total: an estimate may be this much |
| 314 |
|
| * too high, and no more, with the confidence the sketch was sized for. |
| 315 |
|
| * |
| 316 |
|
| * epsilon is e/w, so this is arithmetic on the shape rather than a number |
| 317 |
|
| * anybody has to remember. */ |
| 318 |
18 |
| static uint64_t sa_cms_error(sa_cms *s) { |
| 319 |
18 |
▶ | if (!s || !s->width) return 0; |
Branch: 2 branches
| Branch | True | False | Total |
| if (!s || !s->width) return 0; |
18 |
0 |
18 |
| if (!s || !s->width) return 0; |
0 |
18 |
18 |
|
| 320 |
36 |
| return (uint64_t)((2.718281828459045 / (double)s->width) |
| 321 |
18 |
| * (double)sa_at_load64_acq(&s->hdr->total)); |
| 322 |
|
| } |
| 323 |
|
| |
| 324 |
|
| #else /* !SA_HAVE_ATOMICS */ |
| 325 |
|
| |
| 326 |
|
| /* No atomics, so no sketch: sa_cms_bind refuses. These answer the way the XSUBs |
| 327 |
|
| * do in that build, nothing counted and nothing estimated, so that the op doors |
| 328 |
|
| * and the ABI table have something to point at. */ |
| 329 |
|
| static uint64_t sa_cms_add(sa_cms *s, const char *key, uint32_t klen, |
| 330 |
|
| uint64_t n) |
| 331 |
|
| { |
| 332 |
|
| (void)s; (void)key; (void)klen; (void)n; |
| 333 |
|
| return 0; |
| 334 |
|
| } |
| 335 |
|
| |
| 336 |
|
| static uint64_t sa_cms_estimate(sa_cms *s, const char *key, uint32_t klen) { |
| 337 |
|
| (void)s; (void)key; (void)klen; |
| 338 |
|
| return 0; |
| 339 |
|
| } |
| 340 |
|
| |
| 341 |
|
| static void sa_cms_reset(sa_cms *s) { (void)s; } |
| 342 |
|
| |
| 343 |
|
| static uint64_t sa_cms_error(sa_cms *s) { (void)s; return 0; } |
| 344 |
|
| |
| 345 |
|
| #endif /* SA_HAVE_ATOMICS */ |
| 346 |
|
| |
| 347 |
|
| #endif /* SA_CMS_H */ |