split-up Dependency struct

Having dependency data separated from the link between version/package
and the dependency allows use to work on sharing the depdency data a bit
as it turns out that many dependencies are in fact duplicates. How many
are duplicates various heavily with the sources configured, but for a
single Debian release the ballpark is 2 duplicates for each dependency
already (e.g. libc6 counts 18410 dependencies, but only 45 unique). Add
more releases and the duplicates count only rises to get ~6 for 3
releases. For each architecture a user has configured which given the
shear number of dependencies amounts to MBs of duplication.

We can cut down on this number, but pay a heavy price for it: In my
many releases(3) + architectures(3) test we have a 10% (~ 0.5 sec)
increase in cache creationtime, but also 10% less cachesize (~ 10 MB).

Further work is needed to rip the whole benefits from this through, so
this is just the start.

Git-Dch: Ignore

5 files changed, 162 insertions, 58 deletions

diff --git a/apt-pkg/cacheiterators.h b/apt-pkg/cacheiterators.h
index 06deef950..82c5d082b 100644
--- a/apt-pkg/cacheiterators.h
+++ b/apt-pkg/cacheiterators.h
@@ -275,6 +275,7 @@ class pkgCache::DescIterator : public Iterator<Description, DescIterator> {
 // Dependency iterator							/*{{{*/
 class pkgCache::DepIterator : public Iterator<Dependency, DepIterator> {
 	enum {DepVer, DepRev} Type;
+	DependencyData * S2;
 
 	public:
 	inline Dependency* OwnerPointer() const {
@@ -282,13 +283,12 @@ class pkgCache::DepIterator : public Iterator<Dependency, DepIterator> {
 	}
 
 	// Iteration
-	inline DepIterator& operator++() {if (S != Owner->DepP) S = Owner->DepP +
-		(Type == DepVer ? S->NextDepends : S->NextRevDepends); return *this;}
+	DepIterator& operator++();
 	inline DepIterator operator++(int) { DepIterator const tmp(*this); operator++(); return tmp; }
 
 	// Accessors
-	inline const char *TargetVer() const {return S->Version == 0?0:Owner->StrP + S->Version;}
-	inline PkgIterator TargetPkg() const {return PkgIterator(*Owner,Owner->PkgP + S->Package);}
+	inline const char *TargetVer() const {return S2->Version == 0?0:Owner->StrP + S2->Version;}
+	inline PkgIterator TargetPkg() const {return PkgIterator(*Owner,Owner->PkgP + S2->Package);}
 	inline PkgIterator SmartTargetPkg() const {PkgIterator R(*Owner,0);SmartTargetPkg(R);return R;}
 	inline VerIterator ParentVer() const {return VerIterator(*Owner,Owner->VerP + S->ParentVer);}
 	inline PkgIterator ParentPkg() const {return PkgIterator(*Owner,Owner->PkgP + Owner->VerP[S->ParentVer].ParentPkg);}
@@ -303,23 +303,48 @@ class pkgCache::DepIterator : public Iterator<Dependency, DepIterator> {
 	void GlobOr(DepIterator &Start,DepIterator &End);
 	Version **AllTargets() const;
 	bool SmartTargetPkg(PkgIterator &Result) const;
-	inline const char *CompType() const {return Owner->CompType(S->CompareOp);}
-	inline const char *DepType() const {return Owner->DepType(S->Type);}
+	inline const char *CompType() const {return Owner->CompType(S2->CompareOp);}
+	inline const char *DepType() const {return Owner->DepType(S2->Type);}
+
+	// overrides because we are special
+	struct DependencyProxy
+	{
+	   map_stringitem_t &Version;
+	   map_pointer_t &Package;
+	   should_be_map_id_t &ID;
+	   unsigned char &Type;
+	   unsigned char &CompareOp;
+	   map_pointer_t &ParentVer;
+	   map_pointer_t &DependencyData;
+	   map_pointer_t &NextRevDepends;
+	   map_pointer_t &NextDepends;
+	   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 };}
+	void ReMap(void const * const oldMap, void const * const newMap)
+	{
+		Iterator<Dependency, DepIterator>::ReMap(oldMap, newMap);
+		if (Owner == 0 || S == 0 || S2 == 0)
+			return;
+		S2 += (DependencyData const * const)(newMap) - (DependencyData const * const)(oldMap);
+	}
 
 	//Nice printable representation
 	friend std::ostream& operator <<(std::ostream& out, DepIterator D);
 
 	inline DepIterator(pkgCache &Owner, Dependency *Trg, Version* = 0) :
-		Iterator<Dependency, DepIterator>(Owner, Trg), Type(DepVer) {
+		Iterator<Dependency, DepIterator>(Owner, Trg), Type(DepVer), S2(Trg == 0 ? Owner.DepDataP : (Owner.DepDataP + Trg->DependencyData)) {
 		if (S == 0)
 			S = Owner.DepP;
 	}
 	inline DepIterator(pkgCache &Owner, Dependency *Trg, Package*) :
-		Iterator<Dependency, DepIterator>(Owner, Trg), Type(DepRev) {
+		Iterator<Dependency, DepIterator>(Owner, Trg), Type(DepRev), S2(Trg == 0 ? Owner.DepDataP : (Owner.DepDataP + Trg->DependencyData)) {
 		if (S == 0)
 			S = Owner.DepP;
 	}
-	inline DepIterator() : Iterator<Dependency, DepIterator>(), Type(DepVer) {}
+	inline DepIterator() : Iterator<Dependency, DepIterator>(), Type(DepVer), S2(0) {}
 };
 									/*}}}*/
 // Provides iterator							/*{{{*/
diff --git a/apt-pkg/depcache.cc b/apt-pkg/depcache.cc
index 6271a024a..7b1448c73 100644
--- a/apt-pkg/depcache.cc
+++ b/apt-pkg/depcache.cc
@@ -348,22 +348,21 @@ bool pkgDepCache::CheckDep(DepIterator const &Dep,int const Type,PkgIterator &Re
       bug. Conflicts may never self match */
    if (Dep.IsIgnorable(Res) == false)
    {
-      PkgIterator Pkg = Dep.TargetPkg();
       // Check the base package
       if (Type == NowVersion)
       {
-	 if (Pkg->CurrentVer != 0 && Dep.IsSatisfied(Pkg.CurrentVer()) == true)
+	 if (Res->CurrentVer != 0 && Dep.IsSatisfied(Res.CurrentVer()) == true)
 	    return true;
       }
       else if (Type == InstallVersion)
       {
-	 if (PkgState[Pkg->ID].InstallVer != 0 &&
-	       Dep.IsSatisfied(PkgState[Pkg->ID].InstVerIter(*this)) == true)
+	 if (PkgState[Res->ID].InstallVer != 0 &&
+	       Dep.IsSatisfied(PkgState[Res->ID].InstVerIter(*this)) == true)
 	    return true;
       }
       else if (Type == CandidateVersion)
-	 if (PkgState[Pkg->ID].CandidateVer != 0 &&
-	       Dep.IsSatisfied(PkgState[Pkg->ID].CandidateVerIter(*this)) == true)
+	 if (PkgState[Res->ID].CandidateVer != 0 &&
+	       Dep.IsSatisfied(PkgState[Res->ID].CandidateVerIter(*this)) == true)
 	    return true;
    }
 
diff --git a/apt-pkg/pkgcache.cc b/apt-pkg/pkgcache.cc
index 897f1ee2a..8cd716c6e 100644
--- a/apt-pkg/pkgcache.cc
+++ b/apt-pkg/pkgcache.cc
@@ -66,6 +66,7 @@ pkgCache::Header::Header()
    VersionSz = sizeof(pkgCache::Version);
    DescriptionSz = sizeof(pkgCache::Description);
    DependencySz = sizeof(pkgCache::Dependency);
+   DependencyDataSz = sizeof(pkgCache::DependencyData);
    ProvidesSz = sizeof(pkgCache::Provides);
    VerFileSz = sizeof(pkgCache::VerFile);
    DescFileSz = sizeof(pkgCache::DescFile);
@@ -75,6 +76,7 @@ pkgCache::Header::Header()
    VersionCount = 0;
    DescriptionCount = 0;
    DependsCount = 0;
+   DependsDataCount = 0;
    ReleaseFileCount = 0;
    PackageFileCount = 0;
    VerFileCount = 0;
@@ -110,6 +112,7 @@ bool pkgCache::Header::CheckSizes(Header &Against) const
        VersionSz == Against.VersionSz &&
        DescriptionSz == Against.DescriptionSz &&
        DependencySz == Against.DependencySz &&
+       DependencyDataSz == Against.DependencyDataSz &&
        VerFileSz == Against.VerFileSz &&
        DescFileSz == Against.DescFileSz &&
        ProvidesSz == Against.ProvidesSz)
@@ -150,6 +153,7 @@ bool pkgCache::ReMap(bool const &Errorchecks)
    DescP = (Description *)Map.Data();
    ProvideP = (Provides *)Map.Data();
    DepP = (Dependency *)Map.Data();
+   DepDataP = (DependencyData *)Map.Data();
    StrP = (char *)Map.Data();
 
    if (Errorchecks == false)
@@ -408,7 +412,7 @@ pkgCache::PkgIterator pkgCache::GrpIterator::NextPkg(pkgCache::PkgIterator const
 	return PkgIterator(*Owner, Owner->PkgP + LastPkg->NextPackage);
 }
 									/*}}}*/
-// GrpIterator::operator ++ - Postfix incr				/*{{{*/
+// GrpIterator::operator++ - Prefix incr				/*{{{*/
 // ---------------------------------------------------------------------
 /* This will advance to the next logical group in the hash table. */
 pkgCache::GrpIterator& pkgCache::GrpIterator::operator++()
@@ -420,16 +424,16 @@ pkgCache::GrpIterator& pkgCache::GrpIterator::operator++()
    // Follow the hash table
    while (S == Owner->GrpP && (HashIndex+1) < (signed)Owner->HeaderP->GetHashTableSize())
    {
-      HashIndex++;
+      ++HashIndex;
       S = Owner->GrpP + Owner->HeaderP->GrpHashTableP()[HashIndex];
    }
    return *this;
 }
 									/*}}}*/
-// PkgIterator::operator ++ - Postfix incr				/*{{{*/
+// PkgIterator::operator++ - Prefix incr				/*{{{*/
 // ---------------------------------------------------------------------
 /* This will advance to the next logical package in the hash table. */
-pkgCache::PkgIterator& pkgCache::PkgIterator::operator ++()
+pkgCache::PkgIterator& pkgCache::PkgIterator::operator++()
 {
    // Follow the current links
    if (S != Owner->PkgP)
@@ -438,12 +442,24 @@ pkgCache::PkgIterator& pkgCache::PkgIterator::operator ++()
    // Follow the hash table
    while (S == Owner->PkgP && (HashIndex+1) < (signed)Owner->HeaderP->GetHashTableSize())
    {
-      HashIndex++;
+      ++HashIndex;
       S = Owner->PkgP + Owner->HeaderP->PkgHashTableP()[HashIndex];
    }
    return *this;
 }
 									/*}}}*/
+pkgCache::DepIterator& pkgCache::DepIterator::operator++()		/*{{{*/
+{
+   if (S == Owner->DepP)
+      return *this;
+   S = Owner->DepP + (Type == DepVer ? S->NextDepends : S->NextRevDepends);
+   if (S == Owner->DepP)
+      S2 = Owner->DepDataP;
+   else
+      S2 = Owner->DepDataP + S->DependencyData;
+   return *this;
+}
+									/*}}}*/
 // PkgIterator::State - Check the State of the package			/*{{{*/
 // ---------------------------------------------------------------------
 /* By this we mean if it is either cleanly installed or cleanly removed. */
@@ -543,8 +559,8 @@ std::string pkgCache::PkgIterator::FullName(bool const &Pretty) const
 bool pkgCache::DepIterator::IsCritical() const
 {
    if (IsNegative() == true ||
-       S->Type == pkgCache::Dep::Depends ||
-       S->Type == pkgCache::Dep::PreDepends)
+       S2->Type == pkgCache::Dep::Depends ||
+       S2->Type == pkgCache::Dep::PreDepends)
       return true;
    return false;
 }
@@ -555,9 +571,9 @@ bool pkgCache::DepIterator::IsCritical() const
    are negative like Conflicts which can and should be handled differently */
 bool pkgCache::DepIterator::IsNegative() const
 {
-   return S->Type == Dep::DpkgBreaks ||
-	  S->Type == Dep::Conflicts ||
-	  S->Type == Dep::Obsoletes;
+   return S2->Type == Dep::DpkgBreaks ||
+	  S2->Type == Dep::Conflicts ||
+	  S2->Type == Dep::Obsoletes;
 }
 									/*}}}*/
 // DepIterator::SmartTargetPkg - Resolve dep target pointers w/provides	/*{{{*/
@@ -686,7 +702,7 @@ void pkgCache::DepIterator::GlobOr(DepIterator &Start,DepIterator &End)
    End = *this;
    for (bool LastOR = true; end() == false && LastOR == true;)
    {
-      LastOR = (S->CompareOp & pkgCache::Dep::Or) == pkgCache::Dep::Or;
+      LastOR = (S2->CompareOp & pkgCache::Dep::Or) == pkgCache::Dep::Or;
       ++(*this);
       if (LastOR == true)
 	 End = (*this);
@@ -714,15 +730,15 @@ bool pkgCache::DepIterator::IsIgnorable(PkgIterator const &PT) const
    if ((PV->MultiArch & pkgCache::Version::Same) == pkgCache::Version::Same)
    {
       // Replaces: ${self}:other ( << ${binary:Version})
-      if (S->Type == pkgCache::Dep::Replaces)
+      if (S2->Type == pkgCache::Dep::Replaces)
       {
-	 if (S->CompareOp == pkgCache::Dep::Less && strcmp(PV.VerStr(), TargetVer()) == 0)
+	 if (S2->CompareOp == pkgCache::Dep::Less && strcmp(PV.VerStr(), TargetVer()) == 0)
 	    return false;
       }
       // Breaks: ${self}:other (!= ${binary:Version})
-      else if (S->Type == pkgCache::Dep::DpkgBreaks)
+      else if (S2->Type == pkgCache::Dep::DpkgBreaks)
       {
-	 if (S->CompareOp == pkgCache::Dep::NotEquals && strcmp(PV.VerStr(), TargetVer()) == 0)
+	 if (S2->CompareOp == pkgCache::Dep::NotEquals && strcmp(PV.VerStr(), TargetVer()) == 0)
 	    return false;
       }
       return true;
@@ -755,9 +771,9 @@ bool pkgCache::DepIterator::IsIgnorable(PrvIterator const &Prv) const
 bool pkgCache::DepIterator::IsMultiArchImplicit() const
 {
    if (ParentPkg()->Arch != TargetPkg()->Arch &&
-       (S->Type == pkgCache::Dep::Replaces ||
-	S->Type == pkgCache::Dep::DpkgBreaks ||
-	S->Type == pkgCache::Dep::Conflicts))
+       (S2->Type == pkgCache::Dep::Replaces ||
+	S2->Type == pkgCache::Dep::DpkgBreaks ||
+	S2->Type == pkgCache::Dep::Conflicts))
       return true;
    return false;
 }
@@ -765,11 +781,11 @@ bool pkgCache::DepIterator::IsMultiArchImplicit() const
 // DepIterator::IsSatisfied - check if a version satisfied the dependency /*{{{*/
 bool pkgCache::DepIterator::IsSatisfied(VerIterator const &Ver) const
 {
-   return Owner->VS->CheckDep(Ver.VerStr(),S->CompareOp,TargetVer());
+   return Owner->VS->CheckDep(Ver.VerStr(),S2->CompareOp,TargetVer());
 }
 bool pkgCache::DepIterator::IsSatisfied(PrvIterator const &Prv) const
 {
-   return Owner->VS->CheckDep(Prv.ProvideVersion(),S->CompareOp,TargetVer());
+   return Owner->VS->CheckDep(Prv.ProvideVersion(),S2->CompareOp,TargetVer());
 }
 									/*}}}*/
 // ostream operator to handle string representation of a dependecy	/*{{{*/
diff --git a/apt-pkg/pkgcache.h b/apt-pkg/pkgcache.h
index 0042eac96..41709eae8 100644
--- a/apt-pkg/pkgcache.h
+++ b/apt-pkg/pkgcache.h
@@ -139,6 +139,7 @@ class pkgCache								/*{{{*/
    struct Description;
    struct Provides;
    struct Dependency;
+   struct DependencyData;
    struct StringItem;
    struct VerFile;
    struct DescFile;
@@ -226,6 +227,7 @@ class pkgCache								/*{{{*/
    Description *DescP;
    Provides *ProvideP;
    Dependency *DepP;
+   DependencyData *DepDataP;
    APT_DEPRECATED StringItem *StringItemP;
    char *StrP;
 
@@ -310,6 +312,7 @@ struct pkgCache::Header
    unsigned short VersionSz;
    unsigned short DescriptionSz;
    unsigned short DependencySz;
+   unsigned short DependencyDataSz;
    unsigned short ProvidesSz;
    unsigned short VerFileSz;
    unsigned short DescFileSz;
@@ -324,6 +327,7 @@ struct pkgCache::Header
    map_id_t VersionCount;
    map_id_t DescriptionCount;
    map_id_t DependsCount;
+   map_id_t DependsDataCount;
    map_fileid_t ReleaseFileCount;
    map_fileid_t PackageFileCount;
    map_fileid_t VerFileCount;
@@ -711,7 +715,7 @@ struct pkgCache::Description
     The base of the linked list is pkgCache::Version::DependsList.
     All forms of dependencies are recorded here including Depends,
     Recommends, Suggests, Enhances, Conflicts, Replaces and Breaks. */
-struct pkgCache::Dependency
+struct pkgCache::DependencyData
 {
    /** \brief string of the version the dependency is applied against */
    map_stringitem_t Version;
@@ -720,15 +724,7 @@ struct pkgCache::Dependency
        The generator will - if the package does not already exist -
        create a blank (no version records) package. */
    map_pointer_t Package;         // Package
-   /** \brief next dependency of this version */
-   map_pointer_t NextDepends;     // Dependency
-   /** \brief next reverse dependency of this package */
-   map_pointer_t NextRevDepends;  // Dependency
-   /** \brief version of the package which has the reverse depends */
-   map_pointer_t ParentVer;       // Version
 
-   /** \brief unique sequel ID */
-   should_be_map_id_t ID;
    /** \brief Dependency type - Depends, Recommends, Conflicts, etc */
    unsigned char Type;
    /** \brief comparison operator specified on the depends line
@@ -736,6 +732,19 @@ struct pkgCache::Dependency
        If the high bit is set then it is a logical OR with the previous record. */
    unsigned char CompareOp;
 };
+struct pkgCache::Dependency
+{
+   map_pointer_t DependencyData;  // DependencyData
+   /** \brief version of the package which has the depends */
+   map_pointer_t ParentVer;       // Version
+   /** \brief next reverse dependency of this package */
+   map_pointer_t NextRevDepends;  // Dependency
+   /** \brief next dependency of this version */
+   map_pointer_t NextDepends;     // Dependency
+
+   /** \brief unique sequel ID */
+   should_be_map_id_t ID;
+};
 									/*}}}*/
 // Provides structure							/*{{{*/
 /** \brief handles virtual packages
diff --git a/apt-pkg/pkgcachegen.cc b/apt-pkg/pkgcachegen.cc
index 0eba5795f..d5b282007 100644
--- a/apt-pkg/pkgcachegen.cc
+++ b/apt-pkg/pkgcachegen.cc
@@ -950,19 +950,75 @@ bool pkgCacheGenerator::NewDepends(pkgCache::PkgIterator &Pkg,
    if (unlikely(Dependency == 0))
       return false;
 
-   // Fill it in
-   pkgCache::DepIterator Dep(Cache,Cache.DepP + Dependency);
-   Dynamic<pkgCache::DepIterator> DynDep(Dep);
-   Dep->ParentVer = Ver.Index();
-   Dep->Type = Type;
-   Dep->CompareOp = Op;
-   Dep->Version = Version;
-   Dep->ID = Cache.HeaderP->DependsCount++;
+   bool isDuplicate = false;
+   map_pointer_t DependencyData = 0;
+   map_pointer_t * PkgRevDepends = &Pkg->RevDepends;
+   map_pointer_t previous_id = 0;
 
-   // Link it to the package
-   Dep->Package = Pkg.Index();
-   Dep->NextRevDepends = Pkg->RevDepends;
-   Pkg->RevDepends = Dep.Index();
+   while (*PkgRevDepends != 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;
+      }
+   }
+
+   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;
+   Link->ParentVer = Ver.Index();
+   Link->DependencyData = DependencyData;
+   Link->ID = Cache.HeaderP->DependsCount++;
+
+   pkgCache::DepIterator Dep(Cache, Link);
+   Dynamic<pkgCache::DepIterator> DynDep(Dep);
+   if (isDuplicate == false)
+   {
+      Dep->Type = Type;
+      Dep->CompareOp = Op;
+      Dep->Version = Version;
+      Dep->Package = Pkg.Index();
+      ++Cache.HeaderP->DependsDataCount;
+      Link->NextRevDepends = Pkg->RevDepends;
+      Pkg->RevDepends = 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;
+   }
 
    // Do we know where to link the Dependency to?
    if (OldDepLast == NULL)
@@ -974,9 +1030,8 @@ bool pkgCacheGenerator::NewDepends(pkgCache::PkgIterator &Pkg,
       OldDepLast += (map_pointer_t const * const) Map.Data() - (map_pointer_t const * const) oldMap;
 
    Dep->NextDepends = *OldDepLast;
-   *OldDepLast = Dep.Index();
+   *OldDepLast = Dependency;
    OldDepLast = &Dep->NextDepends;
-
    return true;
 }
 									/*}}}*/