RPM Package Manager, CVS Repository
/cvs/
____________________________________________________________________________
Server: rpm5.org Name: Jeff Johnson
Root: /v/rpm/cvs Email: jbj@rpm5.org
Module: rpm Date: 19-Aug-2010 18:27:02
Branch: rpm-5_1 Handle: 2010081916270001
Added files: (Branch: rpm-5_1)
rpm/rpmio rpmbf.c rpmbf.h
Modified files: (Branch: rpm-5_1)
rpm CHANGES
rpm/rpmio Makefile.am librpmio.vers poptIO.c rpmio.c
Log:
- rpmbf: backport from HEAD.
Summary:
Revision Changes Path
1.2288.2.318+1 -0 rpm/CHANGES
1.162.2.28 +3 -3 rpm/rpmio/Makefile.am
2.63.2.23 +10 -0 rpm/rpmio/librpmio.vers
1.24.2.11 +3 -0 rpm/rpmio/poptIO.c
2.10.2.2 +225 -0 rpm/rpmio/rpmbf.c
2.8.2.2 +203 -0 rpm/rpmio/rpmbf.h
1.127.2.28 +2 -0 rpm/rpmio/rpmio.c
____________________________________________________________________________
patch -p0 <<'@@ .'
Index: rpm/CHANGES
============================================================================
$ cvs diff -u -r1.2288.2.317 -r1.2288.2.318 CHANGES
--- rpm/CHANGES 19 Aug 2010 01:10:23 -0000 1.2288.2.317
+++ rpm/CHANGES 19 Aug 2010 16:27:00 -0000 1.2288.2.318
@@ -1,4 +1,5 @@
5.1.9 -> 5.1.10:
+ - jbj: rpmbf: backport from HEAD.
- jbj: solve: commit to a test framework based on EDOS and Poky.
- jbj: solve: use RPMTAG_PACKAGEORIGIN paths when available.
- jbj: solve: loop over solve db's in a bag.
@@ .
patch -p0 <<'@@ .'
Index: rpm/rpmio/Makefile.am
============================================================================
$ cvs diff -u -r1.162.2.27 -r1.162.2.28 Makefile.am
--- rpm/rpmio/Makefile.am 13 Aug 2010 22:40:49 -0000 1.162.2.27
+++ rpm/rpmio/Makefile.am 19 Aug 2010 16:27:01 -0000 1.162.2.28
@@ -64,7 +64,7 @@
ar.h cpio.h crc.h fnmatch.h glob.h iosm.h \
md2.h md4.h poptIO.h rmd128.h rmd160.h rmd256.h rmd320.h sha224.h \
salsa10.h salsa20.h tar.h tiger.h \
- rpmbag.h rpmbz.h rpmhook.h rpmio_internal.h rpmlua.h
+ rpmbag.h rpmbf.h rpmbz.h rpmhook.h rpmio_internal.h rpmlua.h
usrlibdir = $(libdir)
usrlib_LTLIBRARIES = librpmio.la
@@ -74,8 +74,8 @@
macro.c mire.c mount.c poptIO.c \
md2.c md4.c rmd128.c rmd160.c rmd256.c rmd320.c sha224.c \
salsa10.c salsa20.c tiger.c \
- rpmbag.c rpmbc.c rpmdav.c rpmgc.c rpmhash.c rpmhook.c rpmio.c rpmiob.c \
- rpmio-stub.c rpmku.c rpmlog.c rpmlua.c rpmmalloc.c rpmmg.c \
+ rpmbag.c rpmbc.c rpmbf.c rpmdav.c rpmgc.c rpmhash.c rpmhook.c rpmio.c \
+ rpmiob.c rpmio-stub.c rpmku.c rpmlog.c rpmlua.c rpmmalloc.c rpmmg.c \
rpmnss.c rpmpgp.c rpmrpc.c rpmsq.c rpmssl.c rpmsw.c rpmuuid.c \
rpmxar.c rpmzlog.c strcasecmp.c strtolocale.c \
tar.c url.c ugid.c xzdio.c yarn.c
@@ .
patch -p0 <<'@@ .'
Index: rpm/rpmio/librpmio.vers
============================================================================
$ cvs diff -u -r2.63.2.22 -r2.63.2.23 librpmio.vers
--- rpm/rpmio/librpmio.vers 13 Aug 2010 22:40:49 -0000 2.63.2.22
+++ rpm/rpmio/librpmio.vers 19 Aug 2010 16:27:01 -0000 2.63.2.23
@@ -256,6 +256,16 @@
rpmbagDel;
rpmbagNew;
rpmbcImplVecs;
+ _rpmbf_debug;
+ rpmbfFree;
+ rpmbfNew;
+ rpmbfAdd;
+ rpmbfChk;
+ rpmbfClr;
+ rpmbfDel;
+ rpmbfIntersect;
+ rpmbfParams;
+ rpmbfUnion;
rpmCleanPath;
rpmCLIMacroContext;
rpmDefineMacro;
@@ .
patch -p0 <<'@@ .'
Index: rpm/rpmio/poptIO.c
============================================================================
$ cvs diff -u -r1.24.2.10 -r1.24.2.11 poptIO.c
--- rpm/rpmio/poptIO.c 13 Aug 2010 22:40:49 -0000 1.24.2.10
+++ rpm/rpmio/poptIO.c 19 Aug 2010 16:27:01 -0000 1.24.2.11
@@ -26,6 +26,7 @@
#endif
#include <rpmbag.h>
+#include <rpmbf.h>
#include "debug.h"
@@ -407,6 +408,8 @@
{ "rpmbagdebug", '\0', POPT_ARG_VAL|POPT_ARGFLAG_DOC_HIDDEN, &_rpmbag_debug, -1,
N_("Debug depsolver wrappers "), NULL},
+ { "rpmbfdebug", '\0', POPT_ARG_VAL|POPT_ARGFLAG_DOC_HIDDEN, &_rpmbf_debug, -1,
+ N_("Debug Bloom filters"), NULL},
#ifdef WITH_LUA
{ "rpmluadebug", '\0', POPT_ARG_VAL|POPT_ARGFLAG_DOC_HIDDEN, &_rpmlua_debug, -1,
@@ .
patch -p0 <<'@@ .'
Index: rpm/rpmio/rpmbf.c
============================================================================
$ cvs diff -u -r0 -r2.10.2.2 rpmbf.c
--- /dev/null 2010-08-19 18:22:01.000000000 +0200
+++ rpmbf.c 2010-08-19 18:27:02.264989522 +0200
@@ -0,0 +1,225 @@
+/** \ingroup rpmio
+ * \file rpmio/rpmbf.c
+ */
+
+#include "system.h"
+#include <math.h>
+
+#include <rpmiotypes.h>
+#include <rpmio.h> /* for *Pool methods */
+#include <rpmlog.h>
+
+#define _RPMBF_INTERNAL
+#include <rpmbf.h>
+
+#include "debug.h"
+
+/* Any pair of 32 bit hashes can be used. lookup3.c generates pairs, will do. */
+#define _JLU3_jlu32lpair 1
+#include "lookup3.c"
+
+/*@unchecked@*/
+int _rpmbf_debug = 0;
+
+/*@-mustmod@*/ /* XXX splint on crack */
+static void rpmbfFini(void * _bf)
+ /*@globals fileSystem @*/
+ /*@modifies *_bf, fileSystem @*/
+{
+ rpmbf bf = _bf;
+
+ bf->bits = PBM_FREE(bf->bits);
+}
+/*@=mustmod@*/
+
+/*@unchecked@*/ /*@only@*/ /*@null@*/
+rpmioPool _rpmbfPool = NULL;
+
+static rpmbf rpmbfGetPool(/*@null@*/ rpmioPool pool)
+ /*@globals _rpmbfPool, fileSystem @*/
+ /*@modifies pool, _rpmbfPool, fileSystem @*/
+{
+ rpmbf bf;
+
+ if (_rpmbfPool == NULL) {
+ _rpmbfPool = rpmioNewPool("bf", sizeof(*bf), -1, _rpmbf_debug,
+ NULL, NULL, rpmbfFini);
+ pool = _rpmbfPool;
+ }
+ return (rpmbf) rpmioGetPool(pool, sizeof(*bf));
+}
+
+rpmbf rpmbfNew(size_t m, size_t k, unsigned flags)
+{
+ static size_t nestimate = 1024; /* XXX default estimated population. */
+ rpmbf bf = rpmbfGetPool(_rpmbfPool);
+
+ if (k == 0) k = 16;
+ if (m == 0) m = (3 * nestimate * k) / 2;
+
+ bf->k = k;
+ bf->m = m;
+ bf->n = 0;
+ bf->bits = PBM_ALLOC(bf->m-1);
+
+ return rpmbfLink(bf);
+}
+
+int rpmbfAdd(rpmbf bf, const void * _s, size_t ns)
+{
+ const char * s = _s;
+ uint32_t h0 = 0;
+ uint32_t h1 = 0;
+
+ if (bf == NULL) return -1;
+
+ if (ns == 0) ns = strlen(s);
+ jlu32lpair(s, ns, &h0, &h1);
+
+ for (ns = 0; ns < bf->k; ns++) {
+ uint32_t h = h0 + ns * h1;
+ uint32_t ix = (h % bf->m);
+ PBM_SET(ix, bf);
+ }
+ bf->n++;
+if (_rpmbf_debug)
+fprintf(stderr, "<-- %s(%p,\"%s\") bf{%u,%u}[%u]\n", __FUNCTION__, bf, s, (unsigned)bf->m, (unsigned)bf->k, (unsigned)bf->n);
+ return 0;
+}
+
+int rpmbfChk(rpmbf bf, const void * _s, size_t ns)
+{
+ const char * s = _s;
+ uint32_t h0 = 0;
+ uint32_t h1 = 0;
+ int rc = 1;
+
+ if (bf == NULL) return -1;
+
+ if (ns == 0) ns = strlen(s);
+ jlu32lpair(s, ns, &h0, &h1);
+
+ for (ns = 0; ns < bf->k; ns++) {
+ uint32_t h = h0 + ns * h1;
+ uint32_t ix = (h % bf->m);
+ if (PBM_ISSET(ix, bf))
+ continue;
+ rc = 0;
+ break;
+ }
+if (_rpmbf_debug)
+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);
+ return rc;
+}
+
+int rpmbfClr(rpmbf bf)
+{
+ static size_t nbw = (__PBM_NBITS/8);
+ __pbm_bits * bits;
+ size_t nw;
+
+ if (bf == NULL) return -1;
+
+ bits = __PBM_BITS(bf);
+ nw = (__PBM_IX(bf->m-1) + 1);
+ memset(bits, 0, nw * nbw);
+ bf->n = 0;
+if (_rpmbf_debug)
+fprintf(stderr, "<-- %s(%p) bf{%u,%u}[%u]\n", __FUNCTION__, bf, (unsigned)bf->m, (unsigned)bf->k, (unsigned)bf->n);
+ return 0;
+}
+
+int rpmbfDel(rpmbf bf, const void * _s, size_t ns)
+{
+ const char * s = _s;
+ uint32_t h0 = 0;
+ uint32_t h1 = 0;
+
+ if (bf == NULL) return -1;
+
+ if (ns == 0) ns = strlen(s);
+assert(ns > 0);
+ jlu32lpair(s, ns, &h0, &h1);
+
+ for (ns = 0; ns < bf->k; ns++) {
+ uint32_t h = h0 + ns * h1;
+ uint32_t ix = (h % bf->m);
+ PBM_CLR(ix, bf);
+ }
+ if (bf->n != 0)
+ bf->n--;
+if (_rpmbf_debug)
+fprintf(stderr, "<-- %s(%p,\"%s\") bf{%u,%u}[%u]\n", __FUNCTION__, bf, s, (unsigned)bf->m, (unsigned)bf->k, (unsigned)bf->n);
+ return 0;
+}
+
+int rpmbfIntersect(rpmbf a, const rpmbf b)
+{
+ __pbm_bits * abits;
+ __pbm_bits * bbits;
+ size_t nw;
+ size_t i;
+
+ if (a == NULL || b == NULL) return -1;
+
+ abits = __PBM_BITS(a);
+ bbits = __PBM_BITS(b);
+ nw = (__PBM_IX(a->m-1) + 1);
+
+ if (!(a->m == b->m && a->k == b->k))
+ return -1;
+ for (i = 0; i < nw; i++)
+ abits[i] &= bbits[i];
+ a->n = 1; /* XXX what is population estimate? */
+if (_rpmbf_debug)
+fprintf(stderr, "<-- %s(%p,%p) bf{%u,%u}[%u]\n", __FUNCTION__, a, b, (unsigned)a->m, (unsigned)a->k, (unsigned)a->n);
+ return 0;
+}
+
+int rpmbfUnion(rpmbf a, const rpmbf b)
+{
+ __pbm_bits * abits;
+ __pbm_bits * bbits;
+ size_t nw;
+ size_t i;
+
+ if (a == NULL || b == NULL) return -1;
+
+ abits = __PBM_BITS(a);
+ bbits = __PBM_BITS(b);
+ nw = (__PBM_IX(a->m-1) + 1);
+
+ if (!(a->m == b->m && a->k == b->k))
+ return -1;
+ for (i = 0; i < nw; i++)
+ abits[i] |= bbits[i];
+ a->n += b->n;
+if (_rpmbf_debug)
+fprintf(stderr, "<-- %s(%p,%p) bf{%u,%u}[%u]\n", __FUNCTION__, a, b, (unsigned)a->m, (unsigned)a->k, (unsigned)a->n);
+ return 0;
+}
+
+void rpmbfParams(size_t n, double e, size_t * mp, size_t * kp)
+{
+ static size_t _nmin = 10;
+ static size_t _n = 10000;
+ static size_t _nmax = 1 * 1000 * 1000 * 1000;
+ static double _emin = 1.0e-10;
+ static double _e = 1.0e-4;
+ static double _emax = 1.0e-2;
+ size_t m;
+ size_t k;
+
+ /* XXX sanity checks on (n,e) args. */
+ if (!(n >= _nmin && _n <= _nmax))
+ n = _n;
+ if (!(e >= _emin && _e <= _emax))
+ e = _e;
+
+ m = (size_t)((n * log(e)) / (log(1.0 / pow(2.0, log(2.0)))) + 0.5);
+ k = (size_t) ((m * log(2.0)) / n);
+ if (mp) *mp = m;
+ if (kp) *kp = k;
+if (_rpmbf_debug)
+fprintf(stderr, "<-- %s(%u, %g) m %u k %u\n", __FUNCTION__, (unsigned)n, e, (unsigned)m, (unsigned)k);
+}
@@ .
patch -p0 <<'@@ .'
Index: rpm/rpmio/rpmbf.h
============================================================================
$ cvs diff -u -r0 -r2.8.2.2 rpmbf.h
--- /dev/null 2010-08-19 18:22:01.000000000 +0200
+++ rpmbf.h 2010-08-19 18:27:02.294991960 +0200
@@ -0,0 +1,203 @@
+#ifndef H_RPMBF
+#define H_RPMBF
+
+/** \ingroup rpmio
+ * \file rpmio/rpmbf.h
+ */
+
+/** \ingroup rpmio
+ */
+/*@unchecked@*/
+extern int _rpmbf_debug;
+
+/** \ingroup rpmio
+ */
+typedef /*@refcounted@*/ struct rpmbf_s * rpmbf;
+
+typedef unsigned int __pbm_bits;
+
+typedef struct {
+ __pbm_bits bits[1];
+} pbm_set;
+
+#if defined(_RPMBF_INTERNAL)
+/** \ingroup rpmio
+ */
+struct rpmbf_s {
+ struct rpmioItem_s _item; /*!< usage mutex and pool identifier. */
+ size_t m;
+ size_t n;
+ size_t k;
+/*@relnull@*/
+ unsigned char * bits;
+#if defined(__LCLINT__)
+/*@refs@*/
+ int nrefs; /*!< (unused) keep splint happy */
+#endif
+};
+#endif /* _RPMBF_INTERNAL */
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#if defined(_RPMBF_INTERNAL)
+
+/* Bit mask macros. */
+#define __PBM_NBITS /*@-sizeoftype@*/(8 * sizeof(__pbm_bits))/*@=sizeoftype@*/
+#define __PBM_IX(d) ((d) / __PBM_NBITS)
+#define __PBM_MASK(d) ((__pbm_bits) 1 << (((unsigned)(d)) % __PBM_NBITS))
+#define __PBM_BITS(set) ((__pbm_bits *)(set)->bits)
+
+#define PBM_FREE(s) _free(s);
+#define PBM_SET(d, s) (__PBM_BITS (s)[__PBM_IX (d)] |= __PBM_MASK (d))
+#define PBM_CLR(d, s) (__PBM_BITS (s)[__PBM_IX (d)] &= ~__PBM_MASK (d))
+#define PBM_ISSET(d, s) ((__PBM_BITS (s)[__PBM_IX (d)] & __PBM_MASK (d)) != 0)
+
+#define PBM_ALLOC(d) xcalloc(__PBM_IX (d) + 1, __PBM_NBITS/8)
+
+/**
+ * Reallocate a bit map.
+ * @retval sp address of bit map pointer
+ * @retval odp no. of bits in map
+ * @param nd desired no. of bits
+ */
+/*@unused@*/
+static inline pbm_set * PBM_REALLOC(pbm_set ** sp, int * odp, int nd)
+ /*@modifies *sp, *odp @*/
+{
+ int i, nb;
+
+ if (nd > (*odp)) {
+ nd *= 2;
+ nb = __PBM_IX(nd) + 1;
+/*@-unqualifiedtrans@*/
+ *sp = xrealloc(*sp, nb * (__PBM_NBITS/8));
+/*@=unqualifiedtrans@*/
+ for (i = __PBM_IX(*odp) + 1; i < nb; i++)
+ __PBM_BITS(*sp)[i] = 0;
+ *odp = nd;
+ }
+/*@-compdef -retalias -usereleased@*/
+ return *sp;
+/*@=compdef =retalias =usereleased@*/
+}
+
+#endif /* _RPMBF_INTERNAL */
+
+/**
+ * Unreference a Bloom filter instance.
+ * @param bf Bloom filter
+ * @return NULL on last dereference
+ */
+/*@unused@*/ /*@null@*/
+rpmbf rpmbfUnlink (/*@killref@*/ /*@only@*/ /*@null@*/ rpmbf bf)
+ /*@modifies bf @*/;
+#define rpmbfUnlink(_bf) \
+ ((rpmbf)rpmioUnlinkPoolItem((rpmioItem)(_bf), __FUNCTION__, __FILE__, __LINE__))
+
+/**
+ * Reference a Bloom filter instance.
+ * @param bf Bloom filter
+ * @return new Bloom filter reference
+ */
+/*@unused@*/ /*@newref@*/ /*@null@*/
+rpmbf rpmbfLink (/*@null@*/ rpmbf bf)
+ /*@modifies bf @*/;
+#define rpmbfLink(_bf) \
+ ((rpmbf)rpmioLinkPoolItem((rpmioItem)(_bf), __FUNCTION__, __FILE__, __LINE__))
+
+/**
+ * Destroy a Bloom filter.
+ * @param bf Bloom filter
+ * @return NULL on last dereference
+ */
+/*@null@*/
+rpmbf rpmbfFree(/*@killref@*/ /*@null@*/rpmbf bf)
+ /*@modifies bf @*/;
+#define rpmbfFree(_bf) \
+ ((rpmbf)rpmioFreePoolItem((rpmioItem)(_bf), __FUNCTION__, __FILE__, __LINE__))
+
+/**
+ * Create a Bloom filter.
+ * @param m no. of bits
+ * @param k no. of hashes
+ * @param flags flags
+ * @return new Bloom filter
+ */
+/*@newref@*/ /*@null@*/
+rpmbf rpmbfNew(size_t m, size_t k, unsigned flags)
+ /*@*/;
+
+/**
+ * Add item to a Bloom filter.
+ * @param bf Bloom filter
+ * @param *_s bytes
+ * @param ns no. bytes (0 uses strlen)
+ * @return 0 on success, -1 on NULL pointer
+ */
+int rpmbfAdd(rpmbf bf, const void * _s, size_t ns)
+ /*@modifies bf @*/;
+
+/**
+ * Clear a Bloom filter, discarding all set memberships.
+ * @param bf Bloom filter
+ * @return 0 on success, -1 on NULL pointer
+ */
+int rpmbfClr(rpmbf bf)
+ /*@modifies bf @*/;
+
+/**
+ * Check for item in a Bloom filter.
+ * @param bf Bloom filter
+ * @param *_s bytes
+ * @param ns no. bytes (0 uses strlen)
+ * @return 1 if string is present, 0 if not, -1 on NULL pointer
+ */
+int rpmbfChk(rpmbf bf, const void * _s, size_t ns)
+ /*@modifies bf @*/;
+
+/**
+ * Delete item from a Bloom filter.
+ * @todo Counting bloom filter needed?
+ * @param bf Bloom filter
+ * @param *_s bytes
+ * @param ns no. bytes (0 will do strlen)
+ * @return 0 on success, -1 on NULL pointer
+ */
+int rpmbfDel(rpmbf bf, const void * _s, size_t ns)
+ /*@modifies bf @*/;
+
+/**
+ * Return intersection of two Bloom filters.
+ * @retval a Bloom filter
+ * @param b Bloom filter
+ * @return 0 on success, -1 if {m,k} disagree or NULL pointers.
+ */
+int rpmbfIntersect(rpmbf a, const rpmbf b)
+ /*@modifies a @*/;
+
+/**
+ * Return union of two Bloom filters.
+ * @retval a Bloom filter
+ * @param b Bloom filter
+ * @return 0 on success, -1 if {m,k} disagree or NULL pointers.
+ */
+int rpmbfUnion(rpmbf a, const rpmbf b)
+ /*@modifies a @*/;
+
+/**
+ * Return optimal {m, k} for given n and e.
+ * @param population estimate
+ * @param e probability of error
+ * @retval *mp no. of bits
+ * @retval *kp no. of hashes
+ */
+void rpmbfParams(size_t n, double e, size_t * mp, size_t * kp)
+ /*@modifies *mp, *kp @*/;
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* H_RPMBF */
@@ .
patch -p0 <<'@@ .'
Index: rpm/rpmio/rpmio.c
============================================================================
$ cvs diff -u -r1.127.2.27 -r1.127.2.28 rpmio.c
--- rpm/rpmio/rpmio.c 13 Aug 2010 22:40:49 -0000 1.127.2.27
+++ rpm/rpmio/rpmio.c 19 Aug 2010 16:27:01 -0000 1.127.2.28
@@ -3143,6 +3143,7 @@
extern rpmioPool _rpmiobPool;
/*@-shadow@*/
extern rpmioPool _mirePool;
+ extern rpmioPool _rpmbfPool;
extern rpmioPool _htPool;
/*@=shadow@*/
extern rpmioPool _rpmbagPool;
@@ -3175,6 +3176,7 @@
#endif
_mirePool = rpmioFreePool(_mirePool);
_rpmmgPool = rpmioFreePool(_rpmmgPool);
+ _rpmbfPool = rpmioFreePool(_rpmbfPool);
_htPool = rpmioFreePool(_htPool);
_rpmiobPool = rpmioFreePool(_rpmiobPool);
_digPool = rpmioFreePool(_digPool);
@@ .
Received on Thu Aug 19 18:27:02 2010