12 #define _RPMBF_INTERNAL
18 #define _JLU3_jlu32lpair 1
31 bf->bits = PBM_FREE(bf->bits);
44 if (_rpmbfPool == NULL) {
54 static size_t nestimate = 1024;
58 if (m == 0) m = (3 * nestimate * k) / 2;
63 bf->bits = (
unsigned char *) PBM_ALLOC(bf->m-1);
70 const char * s = (
const char *) _s;
74 if (bf == NULL)
return -1;
76 if (ns == 0) ns = strlen(s);
77 jlu32lpair(s, ns, &h0, &h1);
79 for (ns = 0; ns < bf->k; ns++) {
86 fprintf(stderr,
"<-- %s(%p,\"%s\") bf{%u,%u}[%u]\n", __FUNCTION__, bf, s, (
unsigned)bf->m, (
unsigned)bf->k, (
unsigned)bf->n);
92 const char * s = (
const char *) _s;
97 if (bf == NULL)
return -1;
99 if (ns == 0) ns = strlen(s);
100 jlu32lpair(s, ns, &h0, &h1);
102 for (ns = 0; ns < bf->k; ns++) {
105 if (PBM_ISSET(ix, bf))
111 fprintf(stderr,
"<-- %s(%p,\"%s\") bf{%u,%u}[%u] rc %d\n", __FUNCTION__, bf, s, (
unsigned)bf->m, (
unsigned)bf->k, (
unsigned)bf->n, rc);
117 static size_t nbw = (__PBM_NBITS/8);
121 if (bf == NULL)
return -1;
123 bits = __PBM_BITS(bf);
124 nw = (__PBM_IX(bf->m-1) + 1);
125 memset(bits, 0, nw * nbw);
128 fprintf(stderr,
"<-- %s(%p) bf{%u,%u}[%u]\n", __FUNCTION__, bf, (
unsigned)bf->m, (
unsigned)bf->k, (
unsigned)bf->n);
134 const char * s = (
const char *) _s;
138 if (bf == NULL)
return -1;
140 if (ns == 0) ns = strlen(s);
142 jlu32lpair(s, ns, &h0, &h1);
144 for (ns = 0; ns < bf->k; ns++) {
152 fprintf(stderr,
"<-- %s(%p,\"%s\") bf{%u,%u}[%u]\n", __FUNCTION__, bf, s, (
unsigned)bf->m, (
unsigned)bf->k, (
unsigned)bf->n);
163 if (a == NULL || b == NULL)
return -1;
165 abits = __PBM_BITS(a);
166 bbits = __PBM_BITS(b);
167 nw = (__PBM_IX(a->m-1) + 1);
169 if (!(a->m == b->m && a->k == b->k))
171 for (i = 0; i < nw; i++)
172 abits[i] &= bbits[i];
175 fprintf(stderr,
"<-- %s(%p,%p) bf{%u,%u}[%u]\n", __FUNCTION__, a, b, (
unsigned)a->m, (
unsigned)a->k, (
unsigned)a->n);
186 if (a == NULL || b == NULL)
return -1;
188 abits = __PBM_BITS(a);
189 bbits = __PBM_BITS(b);
190 nw = (__PBM_IX(a->m-1) + 1);
192 if (!(a->m == b->m && a->k == b->k))
194 for (i = 0; i < nw; i++)
195 abits[i] |= bbits[i];
198 fprintf(stderr,
"<-- %s(%p,%p) bf{%u,%u}[%u]\n", __FUNCTION__, a, b, (
unsigned)a->m, (
unsigned)a->k, (
unsigned)a->n);
204 static size_t _nmin = 10;
205 static size_t _n = 10000;
206 static size_t _nmax = 1 * 1000 * 1000 * 1000;
207 static double _emin = 1.0e-10;
208 static double _e = 1.0e-4;
209 static double _emax = 1.0e-2;
214 if (!(n >= _nmin && _n <= _nmax))
216 if (!(e >= _emin && _e <= _emax))
219 m = (size_t)((n * log(e)) / (log(1.0 / pow(2.0, log(2.0)))) + 0.5);
220 k = (size_t) ((m * log(2.0)) / n);
224 fprintf(stderr,
"<-- %s(%u, %g) m %u k %u\n", __FUNCTION__, (
unsigned)n, e, (
unsigned)m, (
unsigned)k);
rpmbf rpmbfNew(size_t m, size_t k, unsigned flags)
Create a Bloom filter.
void rpmbfParams(size_t n, double e, size_t *mp, size_t *kp)
Return optimal {m, k} for given n and e.
Yet Another syslog(3) API clone.
rpmioItem rpmioGetPool(rpmioPool pool, size_t size)
Get unused item from pool, or alloc a new item.
int rpmbfDel(rpmbf bf, const void *_s, size_t ns)
Delete item from a Bloom filter.
int rpmbfUnion(rpmbf a, const rpmbf b)
Return union of two Bloom filters.
const char const bson int mongo_write_concern int flags
static rpmbf rpmbfGetPool(rpmioPool pool)
int rpmbfIntersect(rpmbf a, const rpmbf b)
Return intersection of two Bloom filters.
rpmioPool rpmioNewPool(const char *name, size_t size, int limit, int flags, char *(*dbg)(void *item), void(*init)(void *item), void(*fini)(void *item))
Create a memory pool.
int rpmbfClr(rpmbf bf)
Clear a Bloom filter, discarding all set memberships.
int rpmbfAdd(rpmbf bf, const void *_s, size_t ns)
Add item to a Bloom filter.
static void rpmbfFini(void *_bf)
rpmbf rpmbfLink(rpmbf bf)
Reference a Bloom filter instance.
int rpmbfChk(rpmbf bf, const void *_s, size_t ns)
Check for item in a Bloom filter.