RPM Package Manager, CVS Repository http://rpm5.org/cvs/ ____________________________________________________________________________
Server: rpm5.org Name: Jeff Johnson Root: /v/rpm/cvs Email: [email protected] Module: rpm Date: 27-Jun-2009 06:10:51 Branch: HEAD Handle: 2009062704105100 Modified files: rpm CHANGES rpm/rpmio rpmbf.c Log: - rpmbf: use lookup3.c hash pairs with k linear combinations. Summary: Revision Changes Path 1.3034 +1 -0 rpm/CHANGES 2.3 +54 -21 rpm/rpmio/rpmbf.c ____________________________________________________________________________ patch -p0 <<'@@ .' Index: rpm/CHANGES ============================================================================ $ cvs diff -u -r1.3033 -r1.3034 CHANGES --- rpm/CHANGES 26 Jun 2009 05:17:08 -0000 1.3033 +++ rpm/CHANGES 27 Jun 2009 04:10:51 -0000 1.3034 @@ -1,5 +1,6 @@ 5.2b1 -> 5.3a1 + - jbj: rpmbf: use lookup3.c hash pairs with k linear combinations. - jbj: rpmbf: stub-in a Bloom filter. - jbj: selinux: fix: disabler bit toggle sense was inverted. - jbj: js: add getters/setters to handle defvar() variables. @@ . patch -p0 <<'@@ .' Index: rpm/rpmio/rpmbf.c ============================================================================ $ cvs diff -u -r2.2 -r2.3 rpmbf.c --- rpm/rpmio/rpmbf.c 26 Jun 2009 18:10:33 -0000 2.2 +++ rpm/rpmio/rpmbf.c 27 Jun 2009 04:10:51 -0000 2.3 @@ -11,11 +11,12 @@ #define _RPMBF_INTERNAL #include <rpmbf.h> -#include <rpmhash.h> -#include <crc.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; @@ -51,43 +52,75 @@ { rpmbf bf = rpmbfGetPool(_rpmbfPool); - bf->n = (n > 0 ? n : 1024); - bf->m = (m > 0 ? m : 8192); - bf->k = (k > 0 ? k : 2); - bf->bits = PBM_ALLOC(bf->m); + if (n == 0) n = 1024; + if (k == 0) k = 16; + if (m == 0) m = (3 * n * k) / 2; + + bf->n = n; + bf->k = k; + bf->m = m; + bf->bits = PBM_ALLOC(bf->m-1); return rpmbfLink(bf); } int rpmbfAdd(rpmbf bf, const char * s) { - rpmuint32_t ix = hashFunctionString(0, s, 0) % bf->m; - rpmuint32_t jx = __crc32(0, (const rpmuint8_t *)s, 0) % bf->m; - PBM_SET(ix, bf); - PBM_SET(jx, bf); + size_t ns = (s ? strlen(s) : 0); + rpmuint32_t h0 = 0; + rpmuint32_t h1 = 0; + +assert(ns > 0); + jlu32lpair(s, ns, &h0, &h1); + + for (ns = 0; ns < bf->k; ns++) { + rpmuint32_t h = h0 + ns * h1; + rpmuint32_t ix = (h % bf->m); + PBM_SET(ix, bf); + } return 0; } int rpmbfChk(rpmbf bf, const char * s) { - rpmuint32_t ix; - - ix = hashFunctionString(0, s, 0) % bf->m; - if (!PBM_ISSET(ix, bf)) - return 0; - ix = __crc32(0, (const rpmuint8_t *)s, 0) % bf->m; - if (!PBM_ISSET(ix, bf)) - return 0; - return 1; + size_t ns = (s ? strlen(s) : 0); + rpmuint32_t h0 = 0; + rpmuint32_t h1 = 0; + int rc = 1; + +assert(ns > 0); + jlu32lpair(s, ns, &h0, &h1); + + for (ns = 0; ns < bf->k; ns++) { + rpmuint32_t h = h0 + ns * h1; + rpmuint32_t ix = (h % bf->m); + if (PBM_ISSET(ix, bf)) + continue; + rc = 0; + break; + } + return rc; } int rpmbfClr(rpmbf bf) { - memset(__PBM_BITS(bf), 0, (__PBM_IX(bf->m) + 1) * (__PBM_NBITS/8)); + memset(__PBM_BITS(bf), 0, (__PBM_IX(bf->m-1) + 1) * (__PBM_NBITS/8)); return 0; } int rpmbfDel(rpmbf bf, const char * s) { + size_t ns = (s ? strlen(s) : 0); + rpmuint32_t h0 = 0; + rpmuint32_t h1 = 0; + +assert(ns > 0); + jlu32lpair(s, ns, &h0, &h1); + + for (ns = 0; ns < bf->k; ns++) { + rpmuint32_t h = h0 + ns * h1; + rpmuint32_t ix = (h % bf->m); + PBM_CLR(ix, bf); + } return 0; } @@ . ______________________________________________________________________ RPM Package Manager http://rpm5.org CVS Sources Repository [email protected]
