From a93a32b5cda4f2a0572365a8b919329ea6af2c66 Mon Sep 17 00:00:00 2001
From: Michael Vogt <mvo@debian.org>
Date: Thu, 29 May 2014 10:22:09 +0200
Subject: [PATCH] add hashtable stats

---
 cmdline/apt-cache.cc | 58 +++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 57 insertions(+), 1 deletion(-)

diff --git a/cmdline/apt-cache.cc b/cmdline/apt-cache.cc
index 84b775390..a620740e1 100644
--- a/cmdline/apt-cache.cc
+++ b/cmdline/apt-cache.cc
@@ -373,7 +373,63 @@ static bool Stats(CommandLine &)
            Cache->Head().VerFileCount*Cache->Head().VerFileSz +
            Cache->Head().ProvidesCount*Cache->Head().ProvidesSz;
    cout << _("Total space accounted for: ") << SizeToStr(Total) << endl;
-   
+
+   // get the hash collisions average
+   long NumBuckets = sizeof(Cache->HeaderP->PkgHashTable)/sizeof(map_ptrloc);
+   long UsedBuckets = 0;
+   long UnusedBuckets = 0;
+   long LongestBucket = 0;
+   long ShortestBucket = NumBuckets;
+   for (unsigned int i=0; i < NumBuckets; ++i)
+   {
+      pkgCache::Package *Pkg = Cache->PkgP + Cache->HeaderP->PkgHashTable[i];
+      if(Pkg == 0 || Pkg == Cache->PkgP)
+      {
+         UnusedBuckets++;
+         continue;
+      }
+      long ThisBucketSize = 0;
+      for (; Pkg != Cache->PkgP; Pkg = Cache->PkgP + Pkg->NextPackage)
+         ThisBucketSize++;
+      LongestBucket = std::max(ThisBucketSize, LongestBucket);
+      ShortestBucket = std::min(ThisBucketSize, ShortestBucket);
+      UsedBuckets += ThisBucketSize;
+   }
+   cout << _("Pkg Hashtable stats:") << endl;
+   cout << _("Number of buckets: ") << SizeToStr(NumBuckets) << endl;
+   cout << _("Unused buckets: ") << SizeToStr(UnusedBuckets) << endl;
+   cout << _("Used buckets: ") << UsedBuckets << endl;
+   cout << _("Average num entries per bucket : ") << UsedBuckets/(double)NumBuckets << endl;
+   cout << _("Longest / Shortest bucket: ") << LongestBucket << " / " << ShortestBucket << endl;
+
+   // get the hash collisions average
+   NumBuckets = sizeof(Cache->HeaderP->GrpHashTable)/sizeof(map_ptrloc);
+   UsedBuckets = 0;
+   UnusedBuckets = 0;
+   LongestBucket = 0;
+   ShortestBucket = NumBuckets;
+   for (unsigned int i=0; i < NumBuckets; ++i)
+   {
+      pkgCache::Group *Grp = Cache->GrpP + Cache->HeaderP->GrpHashTable[i];
+      if(Grp == 0 || Grp == Cache->GrpP)
+      {
+         UnusedBuckets++;
+         continue;
+      }
+      long ThisBucketSize = 0;
+      for (; Grp != Cache->GrpP; Grp = Cache->GrpP + Grp->Next)
+         ThisBucketSize++;
+      LongestBucket = std::max(ThisBucketSize, LongestBucket);
+      ShortestBucket = std::min(ThisBucketSize, ShortestBucket);
+      UsedBuckets += ThisBucketSize;
+   }
+   cout << _("Grp Hashtable stats:") << endl;
+   cout << _("Number of buckets: ") << SizeToStr(NumBuckets) << endl;
+   cout << _("Unused buckets: ") << SizeToStr(UnusedBuckets) << endl;
+   cout << _("Used buckets: ") << UsedBuckets << endl;
+   cout << _("Average num entries per bucket : ") << UsedBuckets/(double)NumBuckets << endl;
+   cout << _("Longest / Shortest bucket: ") << LongestBucket << " / " << ShortestBucket << endl;
+
    return true;
 }
 									/*}}}*/
-- 
2.45.2