Mercurial > jhg

changeset 433:be697c3e951e

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Revlog.RevisionMap helper class got promoted as TLC, renamed to HgRevisionMap
author Artem Tikhomirov <tikhomirov.artem@gmail.com>
date Fri, 30 Mar 2012 16:43:09 +0200
parents 1fc0da631200
children 7e1912b4ce99
files cmdline/org/tmatesoft/hg/console/Main.java src/org/tmatesoft/hg/repo/HgBranches.java src/org/tmatesoft/hg/repo/HgParentChildMap.java src/org/tmatesoft/hg/repo/HgRevisionMap.java src/org/tmatesoft/hg/repo/Revlog.java test/org/tmatesoft/hg/test/MapTagsToFileRevisions.java
diffstat 6 files changed, 135 insertions(+), 82 deletions(-) [+]
line wrap: on
line diff
--- a/cmdline/org/tmatesoft/hg/console/Main.java	Fri Mar 30 16:22:51 2012 +0200
+++ b/cmdline/org/tmatesoft/hg/console/Main.java	Fri Mar 30 16:43:09 2012 +0200
@@ -65,6 +65,7 @@
 import org.tmatesoft.hg.repo.HgSubrepoLocation;
 import org.tmatesoft.hg.repo.HgSubrepoLocation.Kind;
 import org.tmatesoft.hg.repo.HgWorkingCopyStatusCollector;
+import org.tmatesoft.hg.repo.HgRevisionMap;
 import org.tmatesoft.hg.util.FileWalker;
 import org.tmatesoft.hg.util.LogFacility;
 import org.tmatesoft.hg.util.Pair;
@@ -288,7 +289,7 @@
 	 */
 	private void testRevisionMap() throws Exception {
 		HgChangelog changelog = hgRepo.getChangelog();
-		HgChangelog.RevisionMap rmap = changelog.new RevisionMap().init(); // warm-up, ensure complete file read
+		HgRevisionMap<HgChangelog> rmap = new HgRevisionMap<HgChangelog>(changelog).init(); // warm-up, ensure complete file read
 		int tip = changelog.getLastRevision();
 		// take 5 arbitrary revisions at 0, 1/4, 2/4, 3/4 and 4/4 
 		final Nodeid[] revs = new Nodeid[5];
@@ -306,7 +307,7 @@
 		System.out.println();
 		//
 		start = System.currentTimeMillis();
-		rmap = changelog.new RevisionMap().init();
+		rmap = new HgRevisionMap<HgChangelog>(changelog).init();
 		long s2 = System.currentTimeMillis();
 		for (int i = 0; i < revs.length; i++) {
 			final int localRev = rmap.revisionIndex(revs[i]);
--- a/src/org/tmatesoft/hg/repo/HgBranches.java	Fri Mar 30 16:22:51 2012 +0200
+++ b/src/org/tmatesoft/hg/repo/HgBranches.java	Fri Mar 30 16:43:09 2012 +0200
@@ -217,7 +217,7 @@
 			}
 		}
 		final HgChangelog clog = repo.getChangelog();
-		final HgChangelog.RevisionMap rmap = clog.new RevisionMap().init();
+		final HgRevisionMap<HgChangelog> rmap = new HgRevisionMap<HgChangelog>(clog).init();
 		for (BranchInfo bi : branches.values()) {
 			bi.validate(clog, rmap);
 		}
@@ -296,7 +296,7 @@
 			this(branchName, Nodeid.NULL, branchHeads);
 		}
 		
-		void validate(HgChangelog clog, HgChangelog.RevisionMap rmap) throws HgInvalidControlFileException {
+		void validate(HgChangelog clog, HgRevisionMap<HgChangelog> rmap) throws HgInvalidControlFileException {
 			int[] localCset = new int[heads.size()];
 			int i = 0;
 			for (Nodeid h : heads) {
--- a/src/org/tmatesoft/hg/repo/HgParentChildMap.java	Fri Mar 30 16:22:51 2012 +0200
+++ b/src/org/tmatesoft/hg/repo/HgParentChildMap.java	Fri Mar 30 16:43:09 2012 +0200
@@ -49,7 +49,7 @@
  * <p> Perhaps, later may add alternative way to access (and reuse) map instance, Revlog#getParentWalker(), 
  * that instantiates and initializes ParentWalker, and keep SoftReference to allow its reuse.
  * 
- * @see Revlog.RevisionMap
+ * @see HgRevisionMap
  * 
  * @author Artem Tikhomirov
  * @author TMate Software Ltd.
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/org/tmatesoft/hg/repo/HgRevisionMap.java	Fri Mar 30 16:43:09 2012 +0200
@@ -0,0 +1,116 @@
+/*
+ * Copyright (c) 2011-2012 TMate Software Ltd
+ *  
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; version 2 of the License.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * For information on how to redistribute this software under
+ * the terms of a license other than GNU General Public License
+ * contact TMate Software at support@hg4j.com
+ */
+package org.tmatesoft.hg.repo;
+
+import static org.tmatesoft.hg.repo.HgRepository.BAD_REVISION;
+import static org.tmatesoft.hg.repo.HgRepository.TIP;
+
+import java.util.Arrays;
+
+import org.tmatesoft.hg.core.Nodeid;
+import org.tmatesoft.hg.internal.ArrayHelper;
+import org.tmatesoft.hg.repo.Revlog.RevisionInspector;
+
+/**
+ * Effective int to Nodeid and vice versa translation. It's advised to use this class instead of 
+ * multiple {@link Revlog#getRevisionIndex(Nodeid)} calls. Rule of thumb is 20+ calls (given 
+ * initialization costs). It's also important to take into account memory consumption, for huge
+ * repositories use of this class may pay off only when accessing greatest fraction of all revisions.  
+ * 
+ * <p>Next code snippet shows instantiation and sample use: 
+ * <pre>
+ *   RevisionMap<HgChangelog> clogMap = new RevisionMap<HgChangelog>(clog).init();
+ *   RevisionMap<HgDataFile> fileMap = new RevisionMap<HgDataFile>(fileNode).init();
+ *   
+ *   int fileRevIndex = 0;
+ *   Nodeid fileRev = fileMap.revision(fileRevIndex);
+ *   int csetRevIndex = fileNode.getChangesetRevisionIndex(fileRevIndex);
+ *   Nodeid csetRev = clogMap.revision(localCset);
+ *   changesetToNodeidMap.put(csetRev, fileRev);
+ * </pre>
+ * 
+ * <p>
+ * {@link Revlog#getRevisionIndex(Nodeid)} with straightforward lookup approach performs O(n/2)
+ * <p>
+ * {@link HgRevisionMap#revisionIndex(Nodeid)} is log(n), plus initialization is O(n) (just once).
+ * 
+ * @see HgParentChildMap
+ * 
+ * @author Artem Tikhomirov
+ * @author TMate Software Ltd.
+ */
+public final class HgRevisionMap<T extends Revlog> implements RevisionInspector {
+	/*
+	 * in fact, initialization is much slower as it instantiates Nodeids, while #getRevisionIndex
+	 * compares directly against byte buffer. Measuring cpython with 70k+ gives 3 times difference (47 vs 171)
+	 * for complete changelog iteration. 
+	 */
+	
+	/*
+	 * XXX 3 * (x * 4) bytes. Can I do better?
+	 * It seems, yes. Don't need to keep sorted, always can emulate it with indirect access to sequential through sorted2natural.
+	 * i.e. instead sorted[mid].compareTo(toFind), do sequential[sorted2natural[mid]].compareTo(toFind) 
+	 */
+	private Nodeid[] sequential; // natural repository order, childrenOf rely on ordering
+	private Nodeid[] sorted; // for binary search
+	private int[] sorted2natural;
+	private final T revlog;
+
+	public HgRevisionMap(T owner) {
+		revlog = owner;
+	}
+	
+	public HgRepository getRepo() {
+		return revlog.getRepo();
+	}
+	
+	public void next(int revisionIndex, Nodeid revision, int linkedRevision) {
+		sequential[revisionIndex] = sorted[revisionIndex] = revision;
+	}
+
+	/**
+	 * @return <code>this</code> for convenience.
+	 */
+	public HgRevisionMap<T> init(/*XXX Pool<Nodeid> to reuse nodeids, if possible. */) throws HgInvalidControlFileException{
+		// XXX HgRepository.register((RepoChangeListener) this); // listen to changes in repo, re-init if needed?
+		final int revisionCount = revlog.getRevisionCount();
+		sequential = new Nodeid[revisionCount];
+		sorted = new Nodeid[revisionCount];
+		revlog.indexWalk(0, TIP, this);
+		// next is alternative to Arrays.sort(sorted), and build sorted2natural looking up each element of sequential in sorted.
+		// the way sorted2natural was build is O(n*log n).  
+		final ArrayHelper ah = new ArrayHelper();
+		ah.sort(sorted);
+		// note, values in ArrayHelper#getReversed are 1-based indexes, not 0-based 
+		sorted2natural = ah.getReverse();
+		return this;
+	}
+	
+	public Nodeid revision(int revisionIndex) {
+		return sequential[revisionIndex];
+	}
+	public int revisionIndex(Nodeid revision) {
+		if (revision == null || revision.isNull()) {
+			return BAD_REVISION;
+		}
+		int x = Arrays.binarySearch(sorted, revision);
+		if (x < 0) {
+			return BAD_REVISION;
+		}
+		return sorted2natural[x]-1;
+	}
+}
\ No newline at end of file
--- a/src/org/tmatesoft/hg/repo/Revlog.java	Fri Mar 30 16:22:51 2012 +0200
+++ b/src/org/tmatesoft/hg/repo/Revlog.java	Fri Mar 30 16:43:09 2012 +0200
@@ -25,7 +25,6 @@
 import java.util.List;
 
 import org.tmatesoft.hg.core.Nodeid;
-import org.tmatesoft.hg.internal.ArrayHelper;
 import org.tmatesoft.hg.internal.DataAccess;
 import org.tmatesoft.hg.internal.Experimental;
 import org.tmatesoft.hg.internal.Preview;
@@ -134,7 +133,7 @@
 	 * If unsure, use {@link #isKnown(Nodeid)} to find out whether nodeid belongs to this revlog.
 	 * 
 	 * For occasional queries, this method works with decent performance, despite its O(n/2) approach.
-	 * Alternatively, if you need to perform multiple queries (e.g. at least 15-20), {@link Revlog.RevisionMap} may come handy.
+	 * Alternatively, if you need to perform multiple queries (e.g. at least 15-20), {@link HgRevisionMap} may come handy.
 	 * 
 	 * @param nid revision to look up 
 	 * @return revision local index in this revlog
@@ -340,73 +339,9 @@
 		return pw;
 	}
 
-	/**
-	 * Effective int to Nodeid and vice versa translation. It's advised to use this class instead of 
-	 * multiple {@link Revlog#getRevisionIndex(Nodeid)} calls.
-	 * 
-	 * {@link Revlog#getRevisionIndex(Nodeid)} with straightforward lookup approach performs O(n/2)
-	 * {@link RevisionMap#revisionIndex(Nodeid)} is log(n), plus initialization is O(n) (just once).
+	/*
+	 * class with cancel and few other exceptions support. TODO consider general superclass to share with e.g. HgManifestCommand.Mediator
 	 */
-	public final class RevisionMap implements RevisionInspector {
-		/*
-		 * in fact, initialization is much slower as it instantiates Nodeids, while #getRevisionIndex
-		 * compares directly against byte buffer. Measuring cpython with 70k+ gives 3 times difference (47 vs 171)
-		 * for complete changelog iteration. 
-		 */
-		
-		/*
-		 * XXX 3 * (x * 4) bytes. Can I do better?
-		 * It seems, yes. Don't need to keep sorted, always can emulate it with indirect access to sequential through sorted2natural.
-		 * i.e. instead sorted[mid].compareTo(toFind), do sequential[sorted2natural[mid]].compareTo(toFind) 
-		 */
-		private Nodeid[] sequential; // natural repository order, childrenOf rely on ordering
-		private Nodeid[] sorted; // for binary search
-		private int[] sorted2natural;
-
-		public RevisionMap() {
-		}
-		
-		public HgRepository getRepo() {
-			return Revlog.this.getRepo();
-		}
-		
-		public void next(int revisionIndex, Nodeid revision, int linkedRevision) {
-			sequential[revisionIndex] = sorted[revisionIndex] = revision;
-		}
-
-		/**
-		 * @return <code>this</code> for convenience.
-		 */
-		public RevisionMap init(/*XXX Pool<Nodeid> to reuse nodeids, if possible. */) throws HgInvalidControlFileException{
-			// XXX HgRepository.register((RepoChangeListener) this); // listen to changes in repo, re-init if needed?
-			final int revisionCount = Revlog.this.getRevisionCount();
-			sequential = new Nodeid[revisionCount];
-			sorted = new Nodeid[revisionCount];
-			Revlog.this.indexWalk(0, TIP, this);
-			// next is alternative to Arrays.sort(sorted), and build sorted2natural looking up each element of sequential in sorted.
-			// the way sorted2natural was build is O(n*log n).  
-			final ArrayHelper ah = new ArrayHelper();
-			ah.sort(sorted);
-			// note, values in ArrayHelper#getReversed are 1-based indexes, not 0-based 
-			sorted2natural = ah.getReverse();
-			return this;
-		}
-		
-		public Nodeid revision(int revisionIndex) {
-			return sequential[revisionIndex];
-		}
-		public int revisionIndex(Nodeid revision) {
-			if (revision == null || revision.isNull()) {
-				return BAD_REVISION;
-			}
-			int x = Arrays.binarySearch(sorted, revision);
-			if (x < 0) {
-				return BAD_REVISION;
-			}
-			return sorted2natural[x]-1;
-		}
-	}
-
 	protected abstract static class ErrorHandlingInspector implements RevlogStream.Inspector, CancelSupport {
 		private Exception failure;
 		private CancelSupport cancelSupport;
--- a/test/org/tmatesoft/hg/test/MapTagsToFileRevisions.java	Fri Mar 30 16:22:51 2012 +0200
+++ b/test/org/tmatesoft/hg/test/MapTagsToFileRevisions.java	Fri Mar 30 16:43:09 2012 +0200
@@ -27,6 +27,7 @@
 import org.tmatesoft.hg.repo.HgRepository;
 import org.tmatesoft.hg.repo.HgTags;
 import org.tmatesoft.hg.repo.HgTags.TagInfo;
+import org.tmatesoft.hg.repo.HgRevisionMap;
 import org.tmatesoft.hg.util.CancelledException;
 import org.tmatesoft.hg.util.Path;
 
@@ -85,13 +86,13 @@
 		final HgChangelog clog = repository.getChangelog();
 		final HgDataFile fileNode = repository.getFileNode("configure.in");
 		// warm-up
-		HgChangelog.RevisionMap clogMap = clog.new RevisionMap().init();
-		HgDataFile.RevisionMap fileMap = fileNode.new RevisionMap().init();
+		HgRevisionMap<HgChangelog> clogMap = new HgRevisionMap<HgChangelog>(clog).init();
+		HgRevisionMap<HgDataFile> fileMap = new HgRevisionMap<HgDataFile>(fileNode).init();
 		//
 		final int latestRevision = fileNode.getLastRevision();
 		//
 		final long start_1 = System.nanoTime();
-		fileMap = fileNode.new RevisionMap().init();
+		fileMap = new HgRevisionMap<HgDataFile>(fileNode).init();
 		final long start_1a = System.nanoTime();
 		final Map<Nodeid, Nodeid> changesetToNodeid_1 = new HashMap<Nodeid, Nodeid>();
 		for (int revision = 0; revision <= latestRevision; revision++) {
@@ -104,8 +105,8 @@
 		final long end_1 = System.nanoTime();
 		//
 		final long start_2 = System.nanoTime();
-		clogMap = clog.new RevisionMap().init();
-		fileMap = fileNode.new RevisionMap().init();
+		clogMap = new HgRevisionMap<HgChangelog>(clog).init();
+		fileMap = new HgRevisionMap<HgDataFile>(fileNode).init();
 		final Map<Nodeid, Nodeid> changesetToNodeid_2 = new HashMap<Nodeid, Nodeid>();
 		final long start_2a = System.nanoTime();
 		for (int revision = 0; revision <= latestRevision; revision++) {
@@ -156,7 +157,7 @@
 			}
 		}
 		System.out.printf("Direct lookup of %d revisions took %,d ns\n", revisions.size(), System.nanoTime() - s1);
-		HgChangelog.RevisionMap rmap = clog.new RevisionMap();
+		HgRevisionMap<HgChangelog> rmap = new HgRevisionMap<HgChangelog>(clog);
 		final long s2 = System.nanoTime();
 		rmap.init();
 		final long s3 = System.nanoTime();
@@ -207,7 +208,7 @@
 		System.out.printf("Free mem: %,d\n", Runtime.getRuntime().freeMemory());
 	}
 	
-	private int[] collectLocalTagRevisions(HgChangelog.RevisionMap clogrmap, TagInfo[] allTags, IntMap<List<TagInfo>> tagLocalRev2TagInfo) {
+	private int[] collectLocalTagRevisions(HgRevisionMap<HgChangelog> clogrmap, TagInfo[] allTags, IntMap<List<TagInfo>> tagLocalRev2TagInfo) {
 		int[] tagLocalRevs = new int[allTags.length];
 		int x = 0;
 		for (int i = 0; i < allTags.length; i++) {
@@ -241,7 +242,7 @@
 		final TagInfo[] allTags = new TagInfo[tags.getAllTags().size()];
 		tags.getAllTags().values().toArray(allTags);
 		// effective translation of changeset revisions to their local indexes
-		final HgChangelog.RevisionMap clogrmap = repository.getChangelog().new RevisionMap().init();
+		final HgRevisionMap<HgChangelog> clogrmap = new HgRevisionMap<HgChangelog>(repository.getChangelog()).init();
 		// map to look up tag by changeset local number
 		final IntMap<List<TagInfo>> tagLocalRev2TagInfo = new IntMap<List<TagInfo>>(allTags.length);
 		System.out.printf("Collecting manifests for %d tags\n", allTags.length);
@@ -259,7 +260,7 @@
 		
 	// Approach 1. Build map with all files, their revisions and corresponding tags
 	//
-	private void collectTagsPerFile_Approach_1(final HgChangelog.RevisionMap clogrmap, final int[] tagLocalRevs, final TagInfo[] allTags, Path targetPath) throws HgException {
+	private void collectTagsPerFile_Approach_1(final HgRevisionMap clogrmap, final int[] tagLocalRevs, final TagInfo[] allTags, Path targetPath) throws HgException {
 		HgRepository repository = clogrmap.getRepo();
 		final long start = System.currentTimeMillis();
 		// file2rev2tag value is array of revisions, always of allTags.length. Revision index in the array