summaryrefslogtreecommitdiff
path: root/apt-pkg
diff options
context:
space:
mode:
authorJulian Andres Klode <jak@debian.org>2016-09-27 15:24:24 +0200
committerJulian Andres Klode <jak@debian.org>2016-11-22 22:47:35 +0100
commit3e633069c9c187dc51c12e59a7ddba4b68a76c4f (patch)
tree21e5877767bc21df50f9adab765dd961e4326cd1 /apt-pkg
parent15e1ed52a741ff82deb0a4cd6150cf10e23b7368 (diff)
TagSection: Split AlphaIndexes into AlphaIndexes and BetaIndexes
Move the use of the AlphaHash to a new second hash table in preparation for the arrival of the new perfect hash function. With the new perfect hash function hashing most of the keys for us, having 128 slots for a fallback hash function seems enough and prevents us from wasting space.
Diffstat (limited to 'apt-pkg')
-rw-r--r--apt-pkg/tagfile.cc22
-rw-r--r--apt-pkg/tagfile.h3
2 files changed, 14 insertions, 11 deletions
diff --git a/apt-pkg/tagfile.cc b/apt-pkg/tagfile.cc
index 69148e08b..bf8320c31 100644
--- a/apt-pkg/tagfile.cc
+++ b/apt-pkg/tagfile.cc
@@ -98,7 +98,7 @@ public:
};
/*}}}*/
-static unsigned long AlphaHash(const char *Text, size_t Length) /*{{{*/
+static unsigned long BetaHash(const char *Text, size_t Length) /*{{{*/
{
/* This very simple hash function for the last 8 letters gives
very good performance on the debian package files */
@@ -110,7 +110,7 @@ static unsigned long AlphaHash(const char *Text, size_t Length) /*{{{*/
unsigned long Res = 0;
for (size_t i = 0; i < Length; ++i)
Res = ((unsigned long)(Text[i]) & 0xDF) ^ (Res << 1);
- return Res & 0xFF;
+ return Res & 0x7F;
}
/*}}}*/
@@ -474,6 +474,7 @@ pkgTagSection::pkgTagSection()
: Section(0), d(new pkgTagSectionPrivate()), Stop(0)
{
memset(&AlphaIndexes, 0, sizeof(AlphaIndexes));
+ memset(&BetaIndexes, 0, sizeof(BetaIndexes));
}
APT_IGNORE_DEPRECATED_POP
/*}}}*/
@@ -499,6 +500,7 @@ bool pkgTagSection::Scan(const char *Start,unsigned long MaxLength, bool const R
if (d->Tags.empty() == false)
{
memset(&AlphaIndexes, 0, sizeof(AlphaIndexes));
+ memset(&BetaIndexes, 0, sizeof(BetaIndexes));
d->Tags.clear();
}
d->Tags.reserve(0x100);
@@ -526,10 +528,10 @@ bool pkgTagSection::Scan(const char *Start,unsigned long MaxLength, bool const R
// store the last found tag
if (lastTagData.EndTag != 0)
{
- if (AlphaIndexes[lastTagHash] != 0)
- lastTagData.NextInBucket = AlphaIndexes[lastTagHash];
+ if (BetaIndexes[lastTagHash] != 0)
+ lastTagData.NextInBucket = BetaIndexes[lastTagHash];
APT_IGNORE_DEPRECATED_PUSH
- AlphaIndexes[lastTagHash] = TagCount;
+ BetaIndexes[lastTagHash] = TagCount;
APT_IGNORE_DEPRECATED_POP
d->Tags.push_back(lastTagData);
}
@@ -547,7 +549,7 @@ bool pkgTagSection::Scan(const char *Start,unsigned long MaxLength, bool const R
;
++EndTag;
lastTagData.EndTag = EndTag - Section;
- lastTagHash = AlphaHash(Stop, EndTag - Stop);
+ lastTagHash = BetaHash(Stop, EndTag - Stop);
// find the beginning of the value
Stop = Colon + 1;
for (; Stop < End && isspace_ascii(*Stop) != 0; ++Stop)
@@ -572,9 +574,9 @@ bool pkgTagSection::Scan(const char *Start,unsigned long MaxLength, bool const R
{
if (lastTagData.EndTag != 0)
{
- if (AlphaIndexes[lastTagHash] != 0)
- lastTagData.NextInBucket = AlphaIndexes[lastTagHash];
- APT_IGNORE_DEPRECATED(AlphaIndexes[lastTagHash] = TagCount;)
+ if (BetaIndexes[lastTagHash] != 0)
+ lastTagData.NextInBucket = BetaIndexes[lastTagHash];
+ APT_IGNORE_DEPRECATED(BetaIndexes[lastTagHash] = TagCount;)
d->Tags.push_back(lastTagData);
}
@@ -622,7 +624,7 @@ bool pkgTagSection::Find(StringView TagView,unsigned int &Pos) const
{
const char * const Tag = TagView.data();
size_t const Length = TagView.length();
- unsigned int Bucket = AlphaIndexes[AlphaHash(Tag, Length)];
+ unsigned int Bucket = BetaIndexes[BetaHash(Tag, Length)];
if (Bucket == 0)
return false;
diff --git a/apt-pkg/tagfile.h b/apt-pkg/tagfile.h
index 0f4c15436..f0f2f48c6 100644
--- a/apt-pkg/tagfile.h
+++ b/apt-pkg/tagfile.h
@@ -49,7 +49,8 @@ class pkgTagFilePrivate;
class pkgTagSection
{
const char *Section;
- unsigned int AlphaIndexes[0x100];
+ unsigned int AlphaIndexes[128];
+ unsigned int BetaIndexes[128];
pkgTagSectionPrivate * const d;