summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--apt-pkg/pkgcache.cc23
-rw-r--r--apt-pkg/pkgcache.h12
-rw-r--r--apt-pkg/pkgcachegen.cc13
3 files changed, 26 insertions, 22 deletions
diff --git a/apt-pkg/pkgcache.cc b/apt-pkg/pkgcache.cc
index 4fbdc93d5..7b092f07e 100644
--- a/apt-pkg/pkgcache.cc
+++ b/apt-pkg/pkgcache.cc
@@ -54,8 +54,8 @@ pkgCache::Header::Header()
/* Whenever the structures change the major version should be bumped,
whenever the generator changes the minor version should be bumped. */
- MajorVersion = 9;
- MinorVersion = 2;
+ MajorVersion = 10;
+ MinorVersion = 0;
Dirty = false;
HeaderSz = sizeof(pkgCache::Header);
@@ -85,8 +85,7 @@ pkgCache::Header::Header()
StringList = 0;
VerSysName = 0;
Architecture = 0;
- memset(PkgHashTable,0,sizeof(PkgHashTable));
- memset(GrpHashTable,0,sizeof(GrpHashTable));
+ HashTableSize = _config->FindI("APT::Cache-HashTableSize", 10 * 1048);
memset(Pools,0,sizeof(Pools));
CacheFileSize = 0;
@@ -194,7 +193,7 @@ unsigned long pkgCache::sHash(const string &Str) const
unsigned long Hash = 0;
for (string::const_iterator I = Str.begin(); I != Str.end(); ++I)
Hash = 41 * Hash + tolower_ascii(*I);
- return Hash % _count(HeaderP->PkgHashTable);
+ return Hash % HeaderP->HashTableSize;
}
unsigned long pkgCache::sHash(const char *Str) const
@@ -202,7 +201,7 @@ unsigned long pkgCache::sHash(const char *Str) const
unsigned long Hash = tolower_ascii(*Str);
for (const char *I = Str + 1; *I != 0; ++I)
Hash = 41 * Hash + tolower_ascii(*I);
- return Hash % _count(HeaderP->PkgHashTable);
+ return Hash % HeaderP->HashTableSize;
}
/*}}}*/
// Cache::SingleArchFindPkg - Locate a package by name /*{{{*/
@@ -213,7 +212,7 @@ unsigned long pkgCache::sHash(const char *Str) const
pkgCache::PkgIterator pkgCache::SingleArchFindPkg(const string &Name)
{
// Look at the hash bucket
- Package *Pkg = PkgP + HeaderP->PkgHashTable[Hash(Name)];
+ Package *Pkg = PkgP + HeaderP->PkgHashTable()[Hash(Name)];
for (; Pkg != PkgP; Pkg = PkgP + Pkg->Next)
{
if (unlikely(Pkg->Name == 0))
@@ -278,7 +277,7 @@ pkgCache::GrpIterator pkgCache::FindGrp(const string &Name) {
return GrpIterator(*this,0);
// Look at the hash bucket for the group
- Group *Grp = GrpP + HeaderP->GrpHashTable[sHash(Name)];
+ Group *Grp = GrpP + HeaderP->GrpHashTable()[sHash(Name)];
for (; Grp != GrpP; Grp = GrpP + Grp->Next) {
if (unlikely(Grp->Name == 0))
continue;
@@ -432,10 +431,10 @@ void pkgCache::GrpIterator::operator ++(int)
S = Owner->GrpP + S->Next;
// Follow the hash table
- while (S == Owner->GrpP && (HashIndex+1) < (signed)_count(Owner->HeaderP->GrpHashTable))
+ while (S == Owner->GrpP && (HashIndex+1) < (signed)Owner->HeaderP->HashTableSize)
{
HashIndex++;
- S = Owner->GrpP + Owner->HeaderP->GrpHashTable[HashIndex];
+ S = Owner->GrpP + Owner->HeaderP->GrpHashTable()[HashIndex];
}
}
/*}}}*/
@@ -449,10 +448,10 @@ void pkgCache::PkgIterator::operator ++(int)
S = Owner->PkgP + S->Next;
// Follow the hash table
- while (S == Owner->PkgP && (HashIndex+1) < (signed)_count(Owner->HeaderP->PkgHashTable))
+ while (S == Owner->PkgP && (HashIndex+1) < (signed)Owner->HeaderP->HashTableSize)
{
HashIndex++;
- S = Owner->PkgP + Owner->HeaderP->PkgHashTable[HashIndex];
+ S = Owner->PkgP + Owner->HeaderP->PkgHashTable()[HashIndex];
}
}
/*}}}*/
diff --git a/apt-pkg/pkgcache.h b/apt-pkg/pkgcache.h
index 55f0187f9..b6b2894cf 100644
--- a/apt-pkg/pkgcache.h
+++ b/apt-pkg/pkgcache.h
@@ -304,20 +304,20 @@ struct pkgCache::Header
stores this information so future additions can make use of any unused pool
blocks. */
DynamicMMap::Pool Pools[9];
-
+
/** \brief hash tables providing rapid group/package name lookup
- Each group/package name is inserted into the hash table using pkgCache::Hash(const &string)
+ Each group/package name is inserted into a hash table using pkgCache::Hash(const &string)
By iterating over each entry in the hash table it is possible to iterate over
the entire list of packages. Hash Collisions are handled with a singly linked
list of packages based at the hash item. The linked list contains only
packages that match the hashing function.
In the PkgHashTable is it possible that multiple packages have the same name -
these packages are stored as a sequence in the list.
-
- Beware: The Hashmethod assumes that the hash table sizes are equal */
- map_ptrloc PkgHashTable[64*1048];
- map_ptrloc GrpHashTable[64*1048];
+ The size of both tables is the same. */
+ unsigned int HashTableSize;
+ map_ptrloc * PkgHashTable() const { return (map_ptrloc*) (this + 1); }
+ map_ptrloc * GrpHashTable() const { return PkgHashTable() + HashTableSize; }
/** \brief Size of the complete cache file */
unsigned long CacheFileSize;
diff --git a/apt-pkg/pkgcachegen.cc b/apt-pkg/pkgcachegen.cc
index 9615b4c22..360f19736 100644
--- a/apt-pkg/pkgcachegen.cc
+++ b/apt-pkg/pkgcachegen.cc
@@ -73,6 +73,11 @@ pkgCacheGenerator::pkgCacheGenerator(DynamicMMap *pMap,OpProgress *Prog) :
// Starting header
*Cache.HeaderP = pkgCache::Header();
+
+ // make room for the hashtables for packages and groups
+ if (Map.RawAllocate(2 * (Cache.HeaderP->HashTableSize * sizeof(map_ptrloc))) == 0)
+ return;
+
map_ptrloc const idxVerSysName = WriteStringInMap(_system->VS->Label);
if (unlikely(idxVerSysName == 0))
return;
@@ -110,9 +115,9 @@ pkgCacheGenerator::pkgCacheGenerator(DynamicMMap *pMap,OpProgress *Prog) :
{
_error->Error(_("Cache has an incompatible versioning system"));
return;
- }
+ }
}
-
+
Cache.HeaderP->Dirty = true;
Map.Sync(0,sizeof(pkgCache::Header));
}
@@ -618,7 +623,7 @@ bool pkgCacheGenerator::NewGroup(pkgCache::GrpIterator &Grp, const string &Name)
// Insert it into the hash table
unsigned long const Hash = Cache.Hash(Name);
- map_ptrloc *insertAt = &Cache.HeaderP->GrpHashTable[Hash];
+ map_ptrloc *insertAt = &Cache.HeaderP->GrpHashTable()[Hash];
while (*insertAt != 0 && strcasecmp(Name.c_str(), Cache.StrP + (Cache.GrpP + *insertAt)->Name) > 0)
insertAt = &(Cache.GrpP + *insertAt)->Next;
Grp->Next = *insertAt;
@@ -654,7 +659,7 @@ bool pkgCacheGenerator::NewPackage(pkgCache::PkgIterator &Pkg,const string &Name
Grp->FirstPackage = Package;
// Insert it into the hash table
unsigned long const Hash = Cache.Hash(Name);
- map_ptrloc *insertAt = &Cache.HeaderP->PkgHashTable[Hash];
+ map_ptrloc *insertAt = &Cache.HeaderP->PkgHashTable()[Hash];
while (*insertAt != 0 && strcasecmp(Name.c_str(), Cache.StrP + (Cache.PkgP + *insertAt)->Name) > 0)
insertAt = &(Cache.PkgP + *insertAt)->Next;
Pkg->Next = *insertAt;