From 805f7fd5af6fb4527f8487049565437a4ab11ecd Mon Sep 17 00:00:00 2001 From: Panu Matilainen Date: Thu, 10 Mar 2011 09:00:07 +0200 Subject: Move string hash function to librpmio and rename for namespacing - There are places in rpmio and build that would benefit from hashing, but hashFunctionString() being internal to librpm has prevented that. Rename to rstrhash() to resemble the other foo in rpmstring.h for minimal namespacing as its now public function and update callers. - Also mark the function as "pure" - it only looks at its arguments. This is one of the busiest functions in entire rpm so any optimization no matter how minor is well worth it. - Hereby awarding hashFunctionString() with the grand prize for the Most Moved Around Function in rpm ;) --- lib/Makefile.am | 2 +- lib/depends.c | 2 +- lib/fprint.c | 6 +++--- lib/misc.c | 24 ------------------------ lib/misc.h | 3 --- lib/rpmal.c | 4 ++-- lib/rpmug.c | 2 +- lib/transaction.c | 2 +- rpmio/rpmstring.c | 17 +++++++++++++++++ rpmio/rpmstring.h | 8 ++++++++ 10 files changed, 34 insertions(+), 36 deletions(-) delete mode 100644 lib/misc.c diff --git a/lib/Makefile.am b/lib/Makefile.am index 356c258bd..5ae5e955a 100644 --- a/lib/Makefile.am +++ b/lib/Makefile.am @@ -26,7 +26,7 @@ librpm_la_SOURCES = \ rpmdb.c rpmdb_internal.h \ fprint.c fprint.h tagname.c rpmtd.c \ cpio.c cpio.h depends.c order.c formats.c tagexts.c fsm.c fsm.h \ - manifest.c manifest.h misc.c package.c \ + manifest.c manifest.h package.c \ poptALL.c poptI.c poptQV.c psm.c query.c \ rpmal.c rpmal.h rpmchecksig.c rpmds.c rpmfi.c rpmfi_internal.h \ rpmgi.h rpmgi.c rpminstall.c rpmts_internal.h \ diff --git a/lib/depends.c b/lib/depends.c index 69aecbbdc..d59ae89c0 100644 --- a/lib/depends.c +++ b/lib/depends.c @@ -530,7 +530,7 @@ int rpmtsCheck(rpmts ts) } /* XXX FIXME: figure some kind of heuristic for the cache size */ - dcache = depCacheCreate(5001, hashFunctionString, strcmp, + dcache = depCacheCreate(5001, rstrhash, strcmp, (depCacheFreeKey)rfree, NULL); /* diff --git a/lib/fprint.c b/lib/fprint.c index 228922450..c894513ec 100644 --- a/lib/fprint.c +++ b/lib/fprint.c @@ -29,7 +29,7 @@ fingerPrintCache fpCacheCreate(int sizeHint) fingerPrintCache fpc; fpc = xmalloc(sizeof(*fpc)); - fpc->ht = rpmFpEntryHashCreate(sizeHint, hashFunctionString, strcmp, + fpc->ht = rpmFpEntryHashCreate(sizeHint, rstrhash, strcmp, (rpmFpEntryHashFreeKey)free, (rpmFpEntryHashFreeData)free); return fpc; @@ -195,8 +195,8 @@ unsigned int fpHashFunction(const fingerPrint * fp) unsigned int hash = 0; int j; - hash = hashFunctionString(fp->baseName); - if (fp->subDir) hash ^= hashFunctionString(fp->subDir); + hash = rstrhash(fp->baseName); + if (fp->subDir) hash ^= rstrhash(fp->subDir); hash ^= ((unsigned)fp->entry->dev); for (j=0; j<4; j++) hash ^= ((fp->entry->ino >> (8*j)) & 0xFF) << ((3-j)*8); diff --git a/lib/misc.c b/lib/misc.c deleted file mode 100644 index 3ea41a581..000000000 --- a/lib/misc.c +++ /dev/null @@ -1,24 +0,0 @@ -/** - * \file lib/misc.c - */ - -#include "system.h" -#include "lib/misc.h" -#include "debug.h" - -unsigned int hashFunctionString(const char * string) -{ - /* Jenkins One-at-a-time hash */ - unsigned int hash = 0xe4721b68; - - while (*string != '\0') { - hash += *string; - hash += (hash << 10); - hash ^= (hash >> 6); - string++; - } - hash += (hash << 3); - hash ^= (hash >> 11); - hash += (hash << 15); - return hash; -} diff --git a/lib/misc.h b/lib/misc.h index 958561c60..50c6944e2 100644 --- a/lib/misc.h +++ b/lib/misc.h @@ -24,9 +24,6 @@ char * rpmVerifyString(uint32_t verifyResult, const char *pad); RPM_GNUC_INTERNAL char * rpmFFlagsString(uint32_t fflags, const char *pad); -RPM_GNUC_INTERNAL -unsigned int hashFunctionString(const char * string); - typedef char * (*headerTagFormatFunction) (rpmtd td, char * formatPrefix); typedef int (*headerTagTagFunction) (Header h, rpmtd td, headerGetFlags hgflags); diff --git a/lib/rpmal.c b/lib/rpmal.c index 2f934c7d5..6753ca7db 100644 --- a/lib/rpmal.c +++ b/lib/rpmal.c @@ -121,7 +121,7 @@ rpmal rpmalFree(rpmal al) } static unsigned int fileHash(struct fileNameEntry_s file){ - return hashFunctionString(file.dirName) ^ hashFunctionString(file.baseName); + return rstrhash(file.dirName) ^ rstrhash(file.baseName); } static int fileCompare(struct fileNameEntry_s one, struct fileNameEntry_s two) { @@ -240,7 +240,7 @@ static void rpmalMakeIndex(rpmal al) fileCnt += rpmfiFC(alp->fi); } - al->providesHash = rpmalProvidesHashCreate(providesCnt/4+128, hashFunctionString, + al->providesHash = rpmalProvidesHashCreate(providesCnt/4+128, rstrhash, strcmp, NULL, NULL); al->fileHash = rpmalFileHashCreate(fileCnt/4+128, fileHash, fileCompare, NULL, NULL); diff --git a/lib/rpmug.c b/lib/rpmug.c index b365e4a21..53a5a6e4d 100644 --- a/lib/rpmug.c +++ b/lib/rpmug.c @@ -23,7 +23,7 @@ const char * rpmugStashStr(const char *str) const char *ret = NULL; if (str) { if (strStash == NULL) { - strStash = strCacheCreate(64, hashFunctionString, strcmp, + strStash = strCacheCreate(64, rstrhash, strcmp, (strCacheFreeKey)rfree); } diff --git a/lib/transaction.c b/lib/transaction.c index d16a7bd31..5abfab780 100644 --- a/lib/transaction.c +++ b/lib/transaction.c @@ -862,7 +862,7 @@ rpmdbMatchIterator rpmFindBaseNamesInDB(rpmts ts, uint64_t fileCount) const char * baseName; rpmStringSet baseNames = rpmStringSetCreate(fileCount, - hashFunctionString, strcmp, NULL); + rstrhash, strcmp, NULL); mi = rpmdbNewIterator(rpmtsGetRdb(ts), RPMDBI_BASENAMES); diff --git a/rpmio/rpmstring.c b/rpmio/rpmstring.c index 8961cb3e6..d82b9d5a0 100644 --- a/rpmio/rpmstring.c +++ b/rpmio/rpmstring.c @@ -189,3 +189,20 @@ size_t rstrlcpy(char *dest, const char *src, size_t n) return s - src - 1; /* count does not include NUL */ } + +unsigned int rstrhash(const char * string) +{ + /* Jenkins One-at-a-time hash */ + unsigned int hash = 0xe4721b68; + + while (*string != '\0') { + hash += *string; + hash += (hash << 10); + hash ^= (hash >> 6); + string++; + } + hash += (hash << 3); + hash ^= (hash >> 11); + hash += (hash << 15); + return hash; +} diff --git a/rpmio/rpmstring.h b/rpmio/rpmstring.h index 4e8a5dbf7..a1d90d8ee 100644 --- a/rpmio/rpmstring.h +++ b/rpmio/rpmstring.h @@ -172,6 +172,14 @@ char *rstrscat(char **dest, const char *arg, ...) RPM_GNUC_NULL_TERMINATED; */ size_t rstrlcpy(char *dest, const char *src, size_t n); +/** \ingroup rpmstring + * String hashing function + * @param string string to hash + * @return hash id + */ +RPM_GNUC_PURE +unsigned int rstrhash(const char * string); + #ifdef __cplusplus } #endif -- cgit v1.2.3