# HG changeset patch
# User mpm@selenic.com
# Date 1117559026 28800
# Node ID 8450c18f2a45796d97f0857ce7549a661923bf2f
# Parent  2424676edd8cac7bb85454da79324d5643257105
annotate: memory efficiency

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

annotate: memory efficiency

Keep track of how many times a given ancestor is referenced and delete
the annotation information after it's no longer relevant. This tends
to reduce the number of cached revisions to just a couple.

manifest hash: 281e48b67ce310e355bed1615e0f16a643850f56
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.0 (GNU/Linux)

iD8DBQFCnJjyywK+sNU5EO8RAkZ1AKCugPjkRgwVB+71amZf8H5dLCbNvgCfePIB
4FHI1c9IOEzHUNkYPDGqt+0=
=OnFo
-----END PGP SIGNATURE-----


diff -r 2424676edd8c -r 8450c18f2a45 mercurial/hg.py
--- a/mercurial/hg.py	Tue May 31 08:56:05 2005 -0800
+++ b/mercurial/hg.py	Tue May 31 09:03:46 2005 -0800
@@ -41,6 +41,7 @@
                     new += child[s:t]
             return new
 
+        # find all ancestors
         needed = {}
         visit = [node]
         while visit:
@@ -49,7 +50,11 @@
                 if p not in needed:
                     needed[p] = 1
                     visit.append(p)
+                else:
+                    # count how many times we'll use this
+                    needed[p] += 1
 
+        # sort by revision which is a topological order
         visit = needed.keys()
         visit = [ (self.rev(n), n) for n in visit ]
         visit.sort()
@@ -61,6 +66,10 @@
             for p in self.parents(n):
                 if p != nullid:
                     curr = pair(hist[p], curr)
+                    # trim the history of unneeded revs
+                    needed[p] -= 1
+                    if not needed[p]:
+                        del hist[p]
             hist[n] = curr
 
         return hist[n]