rpm  5.4.15
Macros | Functions | Variables
rpmbf.c File Reference
#include "system.h"
#include <math.h>
#include <rpmiotypes.h>
#include <rpmio.h>
#include <rpmlog.h>
#include <rpmbf.h>
#include "debug.h"
#include "lookup3.c"
Include dependency graph for rpmbf.c:

Go to the source code of this file.

Macros

#define _RPMBF_INTERNAL
 
#define _JLU3_jlu32lpair   1
 

Functions

static void rpmbfFini (void *_bf)
 
static rpmbf rpmbfGetPool (rpmioPool pool)
 
rpmbf rpmbfNew (size_t m, size_t k, unsigned flags)
 Create a Bloom filter. More...
 
int rpmbfAdd (rpmbf bf, const void *_s, size_t ns)
 Add item to a Bloom filter. More...
 
int rpmbfChk (rpmbf bf, const void *_s, size_t ns)
 Check for item in a Bloom filter. More...
 
int rpmbfClr (rpmbf bf)
 Clear a Bloom filter, discarding all set memberships. More...
 
int rpmbfDel (rpmbf bf, const void *_s, size_t ns)
 Delete item from a Bloom filter. More...
 
int rpmbfIntersect (rpmbf a, const rpmbf b)
 Return intersection of two Bloom filters. More...
 
int rpmbfUnion (rpmbf a, const rpmbf b)
 Return union of two Bloom filters. More...
 
void rpmbfParams (size_t n, double e, size_t *mp, size_t *kp)
 Return optimal {m, k} for given n and e. More...
 

Variables

int _rpmbf_debug = 0
 
rpmioPool _rpmbfPool = NULL
 

Macro Definition Documentation

#define _JLU3_jlu32lpair   1

Definition at line 18 of file rpmbf.c.

#define _RPMBF_INTERNAL

Definition at line 12 of file rpmbf.c.

Function Documentation

int rpmbfAdd ( rpmbf  bf,
const void *  _s,
size_t  ns 
)

Add item to a Bloom filter.

Parameters
bfBloom filter
*_sbytes
nsno. bytes (0 uses strlen)
Returns
0 on success, -1 on NULL pointer

Definition at line 68 of file rpmbf.c.

References _rpmbf_debug.

Referenced by db3Acallback(), removePackage(), rpmfiFNBF(), rpmhkpFindKey(), rpmhkpValidate(), rpmmiPrune(), rpmtsFindBaseNamesInDB(), and rpmtsFindPubkey().

int rpmbfChk ( rpmbf  bf,
const void *  _s,
size_t  ns 
)

Check for item in a Bloom filter.

Parameters
bfBloom filter
*_sbytes
nsno. bytes (0 uses strlen)
Returns
1 if string is present, 0 if not, -1 on NULL pointer

Definition at line 90 of file rpmbf.c.

References _rpmbf_debug.

Referenced by addRelation(), db3Acallback(), orgrpmAddRelation(), packagedDir(), rpmalAllFileSatisfiesDepend(), rpmhkpFindKey(), rpmhkpVerify(), rpmmiNext(), rpmtsFindBaseNamesInDB(), and rpmtsFindPubkey().

int rpmbfClr ( rpmbf  bf)

Clear a Bloom filter, discarding all set memberships.

Parameters
bfBloom filter
Returns
0 on success, -1 on NULL pointer

Definition at line 115 of file rpmbf.c.

References _rpmbf_debug.

int rpmbfDel ( rpmbf  bf,
const void *  _s,
size_t  ns 
)

Delete item from a Bloom filter.

Todo:
Counting bloom filter needed?
Parameters
bfBloom filter
*_sbytes
nsno. bytes (0 will do strlen)
Returns
0 on success, -1 on NULL pointer

Definition at line 132 of file rpmbf.c.

References _rpmbf_debug.

static void rpmbfFini ( void *  _bf)
static

Definition at line 25 of file rpmbf.c.

Referenced by rpmbfGetPool().

static rpmbf rpmbfGetPool ( rpmioPool  pool)
static

Definition at line 38 of file rpmbf.c.

References _rpmbf_debug, _rpmbfPool, rpmbfFini(), rpmioGetPool(), and rpmioNewPool().

Referenced by rpmbfNew().

int rpmbfIntersect ( rpmbf  a,
const rpmbf  b 
)

Return intersection of two Bloom filters.

Return values
aBloom filter
Parameters
bBloom filter
Returns
0 on success, -1 if {m,k} disagree or NULL pointers.

Definition at line 156 of file rpmbf.c.

References _rpmbf_debug, and i.

rpmbf rpmbfNew ( size_t  m,
size_t  k,
unsigned  flags 
)

Create a Bloom filter.

Parameters
mno. of bits
kno. of hashes
flagsflags
Returns
new Bloom filter

Definition at line 52 of file rpmbf.c.

References rpmbfGetPool(), and rpmbfLink().

Referenced by db3Acallback(), removePackage(), rpmfiFNBF(), rpmhkpNew(), rpmmiPrune(), and rpmtsFindBaseNamesInDB().

void rpmbfParams ( size_t  n,
double  e,
size_t *  mp,
size_t *  kp 
)

Return optimal {m, k} for given n and e.

Parameters
npopulation estimate
eprobability of error
Return values
*mpno. of bits
*kpno. of hashes

Definition at line 202 of file rpmbf.c.

References _rpmbf_debug.

Referenced by db3Acallback(), removePackage(), rpmfiFNBF(), rpmhkpNew(), rpmmiPrune(), and rpmtsFindBaseNamesInDB().

int rpmbfUnion ( rpmbf  a,
const rpmbf  b 
)

Return union of two Bloom filters.

Return values
aBloom filter
Parameters
bBloom filter
Returns
0 on success, -1 if {m,k} disagree or NULL pointers.

Definition at line 179 of file rpmbf.c.

References _rpmbf_debug, and i.

Variable Documentation

int _rpmbf_debug = 0
rpmioPool _rpmbfPool = NULL

Definition at line 36 of file rpmbf.c.

Referenced by rpmbfGetPool(), and rpmioClean().