From aa0fe657e46b87cc692895a36df12e8b74bb27bb Mon Sep 17 00:00:00 2001 From: David Kalnischkies Date: Wed, 3 Apr 2013 12:44:36 +0200 Subject: - sort group and package names in the hashtable on insert * apt-pkg/pkgcache.cc: - assume sorted hashtable entries for groups/packages --- apt-pkg/pkgcachegen.cc | 16 +++++++++++----- 1 file changed, 11 insertions(+), 5 deletions(-) (limited to 'apt-pkg/pkgcachegen.cc') diff --git a/apt-pkg/pkgcachegen.cc b/apt-pkg/pkgcachegen.cc index b11ddcf9e..8437dc68f 100644 --- a/apt-pkg/pkgcachegen.cc +++ b/apt-pkg/pkgcachegen.cc @@ -595,8 +595,11 @@ bool pkgCacheGenerator::NewGroup(pkgCache::GrpIterator &Grp, const string &Name) // Insert it into the hash table unsigned long const Hash = Cache.Hash(Name); - Grp->Next = Cache.HeaderP->GrpHashTable[Hash]; - Cache.HeaderP->GrpHashTable[Hash] = Group; + 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; + *insertAt = Group; Grp->ID = Cache.HeaderP->GroupCount++; return true; @@ -625,11 +628,14 @@ bool pkgCacheGenerator::NewPackage(pkgCache::PkgIterator &Pkg,const string &Name // Insert the package into our package list if (Grp->FirstPackage == 0) // the group is new { + Grp->FirstPackage = Package; // Insert it into the hash table unsigned long const Hash = Cache.Hash(Name); - Pkg->NextPackage = Cache.HeaderP->PkgHashTable[Hash]; - Cache.HeaderP->PkgHashTable[Hash] = Package; - Grp->FirstPackage = Package; + 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)->NextPackage; + Pkg->NextPackage = *insertAt; + *insertAt = Package; } else // Group the Packages together { -- cgit v1.2.3