link DependencyData structs together

Cache generation needs a way of quickly iterating over the unique potion
of the dependencies to be able to share them. By linking them together
we can reduce the speed penality (~ 80%) with only a small reduction in
saved size (~ 20%).

Git-Dch: Ignore

diff --git a/apt-pkg/cacheiterators.h b/apt-pkg/cacheiterators.h
index 82c5d082bf433a6dfbb899fdd3bd9ca8d4036c4e..4173326ca43859d3dc5c67835e69b45f3a1a6d24 100644 (file)
--- a/apt-pkg/cacheiterators.h
+++ b/apt-pkg/cacheiterators.h
@@ -318,11 +318,12 @@ class pkgCache::DepIterator : public Iterator<Dependency, DepIterator> {
           map_pointer_t &DependencyData;
           map_pointer_t &NextRevDepends;
           map_pointer_t &NextDepends;
+          map_pointer_t &NextData;
           DependencyProxy const * operator->() const { return this; }
           DependencyProxy * operator->() { return this; }
        };
-       inline DependencyProxy operator->() const {return { S2->Version, S2->Package, S->ID, S2->Type, S2->CompareOp, S->ParentVer, S->DependencyData, S->NextRevDepends, S->NextDepends };}
-       inline DependencyProxy operator->() {return { S2->Version, S2->Package, S->ID, S2->Type, S2->CompareOp, S->ParentVer, S->DependencyData, S->NextRevDepends, S->NextDepends };}
+       inline DependencyProxy operator->() const {return { S2->Version, S2->Package, S->ID, S2->Type, S2->CompareOp, S->ParentVer, S->DependencyData, S->NextRevDepends, S->NextDepends, S2->NextData };}
+       inline DependencyProxy operator->() {return { S2->Version, S2->Package, S->ID, S2->Type, S2->CompareOp, S->ParentVer, S->DependencyData, S->NextRevDepends, S->NextDepends, S2->NextData };}
        void ReMap(void const * const oldMap, void const * const newMap)
        {
                Iterator<Dependency, DepIterator>::ReMap(oldMap, newMap);

diff --git a/apt-pkg/pkgcache.h b/apt-pkg/pkgcache.h
index 41709eae889861879bb97dc7b850af66e95cdfbe..b3a2e3184b14e421821f86a9ea34ad796f3cb51b 100644 (file)
--- a/apt-pkg/pkgcache.h
+++ b/apt-pkg/pkgcache.h
@@ -366,7 +366,7 @@ struct pkgCache::Header
        the same number of pools as there are structure types. The generator
        stores this information so future additions can make use of any unused pool
        blocks. */
-   DynamicMMap::Pool Pools[9];
+   DynamicMMap::Pool Pools[12];
 
    /** \brief hash tables providing rapid group/package name lookup
 
@@ -731,6 +731,8 @@ struct pkgCache::DependencyData
 
        If the high bit is set then it is a logical OR with the previous record. */
    unsigned char CompareOp;
+
+   map_pointer_t NextData;
 };
 struct pkgCache::Dependency
 {

diff --git a/apt-pkg/pkgcachegen.cc b/apt-pkg/pkgcachegen.cc
index d5b2820070d5d8439eba661ecfcb57dff8efe25c..a82483d15c84b5e0be7640587883c861fa0661e8 100644 (file)
--- a/apt-pkg/pkgcachegen.cc
+++ b/apt-pkg/pkgcachegen.cc
@@ -952,33 +952,30 @@ bool pkgCacheGenerator::NewDepends(pkgCache::PkgIterator &Pkg,
 
    bool isDuplicate = false;
    map_pointer_t DependencyData = 0;
-   map_pointer_t * PkgRevDepends = &Pkg->RevDepends;
-   map_pointer_t previous_id = 0;
-
-   while (*PkgRevDepends != 0)
+   map_pointer_t PreviousData = 0;
+   if (Pkg->RevDepends != 0)
    {
-      pkgCache::Dependency * const L = Cache.DepP + *PkgRevDepends;
-      PkgRevDepends = &L->NextRevDepends;
-      if (L->DependencyData == previous_id)
-        break;
-      previous_id = L->DependencyData;
-      pkgCache::DependencyData const * const D = Cache.DepDataP + previous_id;
-      if (D->Type == Type && D->CompareOp == Op && D->Version == Version)
-      {
-        DependencyData = previous_id;
-        isDuplicate = true;
-        break;
-      }
+      pkgCache::Dependency const * const L = Cache.DepP + Pkg->RevDepends;
+      DependencyData = L->DependencyData;
+      do {
+        pkgCache::DependencyData const * const D = Cache.DepDataP + DependencyData;
+        if (Version > D->Version)
+           break;
+        if (D->Version == Version && D->Type == Type && D->CompareOp == Op)
+        {
+           isDuplicate = true;
+           break;
+        }
+        PreviousData = DependencyData;
+        DependencyData = D->NextData;
+      } while (DependencyData != 0);
    }
 
    if (isDuplicate == false)
    {
-      void const * const oldMap2 = Map.Data();
       DependencyData = AllocateInMap(sizeof(pkgCache::DependencyData));
       if (unlikely(DependencyData == 0))
         return false;
-      if (oldMap2 != Map.Data())
-        PkgRevDepends += (map_pointer_t const * const) Map.Data() - (map_pointer_t const * const) oldMap2;
    }
 
    pkgCache::Dependency * Link = Cache.DepP + Dependency;
@@ -987,7 +984,6 @@ bool pkgCacheGenerator::NewDepends(pkgCache::PkgIterator &Pkg,
    Link->ID = Cache.HeaderP->DependsCount++;
 
    pkgCache::DepIterator Dep(Cache, Link);
-   Dynamic<pkgCache::DepIterator> DynDep(Dep);
    if (isDuplicate == false)
    {
       Dep->Type = Type;
@@ -995,31 +991,32 @@ bool pkgCacheGenerator::NewDepends(pkgCache::PkgIterator &Pkg,
       Dep->Version = Version;
       Dep->Package = Pkg.Index();
       ++Cache.HeaderP->DependsDataCount;
-      Link->NextRevDepends = Pkg->RevDepends;
-      Pkg->RevDepends = Dependency;
+      if (PreviousData != 0)
+      {
+        pkgCache::DependencyData * const D = Cache.DepDataP + PreviousData;
+        Dep->NextData = D->NextData;
+        D->NextData = DependencyData;
+      }
+      else if (Pkg->RevDepends != 0)
+      {
+        pkgCache::Dependency const * const D = Cache.DepP + Pkg->RevDepends;
+        Dep->NextData = D->DependencyData;
+      }
+   }
+
+   if (isDuplicate == true || PreviousData != 0)
+   {
+      pkgCache::Dependency * const L = Cache.DepP + Pkg->RevDepends;
+      Link->NextRevDepends = L->NextRevDepends;
+      L->NextRevDepends = Dependency;
    }
    else
    {
-      // dependency data is already fine, we just set the reverse link
-      // and in such a way that the loop above can finish fast, so we keep
-      // non-duplicates at the front and for the duplicates we:
-      // a) move to the end of the list, b) insert before another own duplicate
-      // or c) find two duplicates behind each other.
-      map_pointer_t const own_id = Link->DependencyData;
-      while (*PkgRevDepends != 0)
-      {
-        pkgCache::Dependency * const L = Cache.DepP + *PkgRevDepends;
-        PkgRevDepends = &L->NextRevDepends;
-        if (L->DependencyData == own_id || L->DependencyData == previous_id)
-        {
-           Link->NextRevDepends = L->NextRevDepends;
-           break;
-        }
-        previous_id = L->DependencyData;
-      }
-      *PkgRevDepends = Dependency;
+      Link->NextRevDepends = Pkg->RevDepends;
+      Pkg->RevDepends = Dependency;
    }
 
+
    // Do we know where to link the Dependency to?
    if (OldDepLast == NULL)
    {

diff --git a/test/integration/test-apt-cache b/test/integration/test-apt-cache
index 7da2ab71ffd56c9351383f29985d45a6d4712d8f..a22b08c2038bd474a62d4b170d599fadb38e2eae 100755 (executable)
--- a/test/integration/test-apt-cache
+++ b/test/integration/test-apt-cache
@@ -113,12 +113,12 @@ Reverse Depends:
   bar' aptcache rdepends foo
 testsuccessequal 'foo
 Reverse Depends:
-  Replaces: bar
-  Breaks: bar' aptcache rdepends foo -o APT::Cache::ShowDependencyType=1
+  Breaks: bar
+  Replaces: bar' aptcache rdepends foo -o APT::Cache::ShowDependencyType=1
 testsuccessequal 'foo
 Reverse Depends:
-  Replaces: bar (<< 1)
-  Breaks: bar (<< 1)' aptcache rdepends foo -o APT::Cache::ShowDependencyType=1 -o APT::Cache::ShowVersion=1
+  Breaks: bar (<< 1)
+  Replaces: bar (<< 1)' aptcache rdepends foo -o APT::Cache::ShowDependencyType=1 -o APT::Cache::ShowVersion=1
 testsuccessequal 'foo
 Reverse Depends:
   Breaks: bar (<< 1)' aptcache rdepends foo -o APT::Cache::ShowDependencyType=1 -o APT::Cache::ShowVersion=1 --important --breaks