xtc_prob(3)

---

xtc_prob(3)

Bloom filter and HyperLogLog cardinality estimator

XTC_PROB(3) Library Functions Manual XTC_PROB(3)

xtc_bloom_init, xtc_bloom_add, xtc_bloom_maybe_contains, xtc_bloom_fini, xtc_hll_init, xtc_hll_add, xtc_hll_count, xtc_hll_merge, xtc_hll_fini — Bloom filter and HyperLogLog cardinality estimator

#include <xtc.h>
#include <xtc_prob.h>

int
xtc_bloom_init(xtc_bloom_t **out, size_t n_expected, double fp_rate);

void
xtc_bloom_add(xtc_bloom_t *b, const void *key, size_t len);

int
xtc_bloom_maybe_contains(const xtc_bloom_t *b, const void *key, size_t len);

void
xtc_bloom_fini(xtc_bloom_t *b);

int
xtc_hll_init(xtc_hll_t **out, int precision);

void
xtc_hll_add(xtc_hll_t *h, const void *key, size_t len);

uint64_t
xtc_hll_count(const xtc_hll_t *h);

int
xtc_hll_merge(xtc_hll_t *dst, const xtc_hll_t *src);

void
xtc_hll_fini(xtc_hll_t *h);

xtc_prob provides two probabilistic sketches that trade a small, bounded, tunable error for memory that stays flat no matter how many distinct keys pass through: a Bloom filter for approximate set membership and a HyperLogLog for approximate distinct-count estimation. Keys are opaque byte spans (key, len), hashed internally, so any key type works with no caller-supplied hash or comparator; nothing is copied or retained, so a key buffer may be freed the moment the call returns.

Both structures are in this version: unlike xtc_chash(3) and xtc_cskip(3) there is no internal locking and no RCU. Concurrent () or () on one instance is a data race. Serialize externally, or give each thread its own instance and (for HLL) combine them with (), which is an exact register-wise maximum.

A bit array of m bits probed by k hash functions. () derives the optimal m and k from the expected element count n_expected and the target false-positive rate fp_rate (strictly between 0 and 1): m = ceil(-n*ln(p) / (ln2)^2) and k = round((m/n)*ln2). xtc_bloom_add() sets the k bits for a key (adding the same key twice is idempotent). () returns 1 if the key MAY be present and 0 if it is DEFINITELY absent: there are NO false negatives (every added key returns 1), and a 1 result carries the configured false-positive probability once the filter holds about n_expected elements. The filter does not resize; loading it well past n_expected raises the false-positive rate, so size it for the true expected load. () frees it.

() allocates 2^ Ns Fa precision registers; precision must be in the range 4 to 18 (16 to 262144 registers). Each register holds the maximum leading-zero run seen for the hashes that fall in its bucket. xtc_hll_add() folds a key in. () returns the estimated number of DISTINCT keys added, using the bias-corrected harmonic-mean estimator with the standard small-range (linear-counting) and large-range corrections; the relative standard error is about 1.04/sqrt(2^ Ns Fa precision Ns ) -- roughly 1.6% at precision 12 and well under 1% at precision 16 -- in a few kilobytes regardless of the true cardinality. xtc_hll_merge() takes the register-wise max of src into dst, so dst afterward estimates the cardinality of the UNION of the two key sets with no error added by the merge; both sketches must have the same precision. () frees it.

xtc_bloom_init(), xtc_hll_init(), and xtc_hll_merge() return XTC_OK on success, XTC_E_INVAL for a NULL out-pointer, an fp_rate not in the open interval (0,1), an out-of-range precision, or mismatched precisions at merge, and XTC_E_NOMEM on allocation failure. xtc_bloom_maybe_contains() returns 1 (maybe present) or 0 (definitely absent; also 0 for a NULL filter). xtc_hll_count() returns the estimated distinct-key count (0 for a NULL sketch). xtc_bloom_add(), xtc_hll_add(), xtc_bloom_fini(), and xtc_hll_fini() have no return value and treat a NULL instance as a no-op.

xtc_bloom_t *b;
xtc_bloom_init(&b, 100000, 0.01);      /* 1% false positives */
xtc_bloom_add(b, "answer", 6);
if (xtc_bloom_maybe_contains(b, "answer", 6))
	printf("maybe present\n");     /* always true for an added key */
if (!xtc_bloom_maybe_contains(b, "nope", 4))
	printf("definitely absent\n"); /* usually true */
xtc_bloom_fini(b);

xtc_hll_t *h;
xtc_hll_init(&h, 14);                    /* 2^14 registers */
for (int i = 0; i < 1000000; i++)
	xtc_hll_add(h, &i, sizeof i);
printf("~%llu distinct\n",
    (unsigned long long)xtc_hll_count(h));
xtc_hll_fini(h);

xtc_chash(3), xtc_cskip(3), xtc(7)

Appeared in xtc 0.1, M14.

July 23, 2026 Debian

View the mdoc source