Mercurial > jhg

comparison src/org/tmatesoft/hg/repo/Revlog.java @ 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 32184ddcf46d
comparison
equal deleted inserted replaced
432:1fc0da631200 433:be697c3e951e
23 import java.util.ArrayList; 23 import java.util.ArrayList;
24 import java.util.Arrays; 24 import java.util.Arrays;
25 import java.util.List; 25 import java.util.List;
26 26
27 import org.tmatesoft.hg.core.Nodeid; 27 import org.tmatesoft.hg.core.Nodeid;
28 import org.tmatesoft.hg.internal.ArrayHelper;
29 import org.tmatesoft.hg.internal.DataAccess; 28 import org.tmatesoft.hg.internal.DataAccess;
30 import org.tmatesoft.hg.internal.Experimental; 29 import org.tmatesoft.hg.internal.Experimental;
31 import org.tmatesoft.hg.internal.Preview; 30 import org.tmatesoft.hg.internal.Preview;
32 import org.tmatesoft.hg.internal.RevlogStream; 31 import org.tmatesoft.hg.internal.RevlogStream;
33 import org.tmatesoft.hg.util.Adaptable; 32 import org.tmatesoft.hg.util.Adaptable;
132 /** 131 /**
133 * Get local index of the specified revision. 132 * Get local index of the specified revision.
134 * If unsure, use {@link #isKnown(Nodeid)} to find out whether nodeid belongs to this revlog. 133 * If unsure, use {@link #isKnown(Nodeid)} to find out whether nodeid belongs to this revlog.
135 * 134 *
136 * For occasional queries, this method works with decent performance, despite its O(n/2) approach. 135 * For occasional queries, this method works with decent performance, despite its O(n/2) approach.
137 * Alternatively, if you need to perform multiple queries (e.g. at least 15-20), {@link Revlog.RevisionMap} may come handy. 136 * Alternatively, if you need to perform multiple queries (e.g. at least 15-20), {@link HgRevisionMap} may come handy.
138 * 137 *
139 * @param nid revision to look up 138 * @param nid revision to look up
140 * @return revision local index in this revlog 139 * @return revision local index in this revlog
141 * @throws HgRuntimeException subclass thereof to indicate issues with the library. <em>Runtime exception</em> 140 * @throws HgRuntimeException subclass thereof to indicate issues with the library. <em>Runtime exception</em>
142 */ 141 */
338 HgParentChildMap<Revlog> pw = new HgParentChildMap<Revlog>(this); 337 HgParentChildMap<Revlog> pw = new HgParentChildMap<Revlog>(this);
339 pw.init(); 338 pw.init();
340 return pw; 339 return pw;
341 } 340 }
342 341
343 /** 342 /*
344 * Effective int to Nodeid and vice versa translation. It's advised to use this class instead of 343 * class with cancel and few other exceptions support. TODO consider general superclass to share with e.g. HgManifestCommand.Mediator
345 * multiple {@link Revlog#getRevisionIndex(Nodeid)} calls. 344 */
346 *
347 * {@link Revlog#getRevisionIndex(Nodeid)} with straightforward lookup approach performs O(n/2)
348 * {@link RevisionMap#revisionIndex(Nodeid)} is log(n), plus initialization is O(n) (just once).
349 */
350 public final class RevisionMap implements RevisionInspector {
351 /*
352 * in fact, initialization is much slower as it instantiates Nodeids, while #getRevisionIndex
353 * compares directly against byte buffer. Measuring cpython with 70k+ gives 3 times difference (47 vs 171)
354 * for complete changelog iteration.
355 */
356
357 /*
358 * XXX 3 * (x * 4) bytes. Can I do better?
359 * It seems, yes. Don't need to keep sorted, always can emulate it with indirect access to sequential through sorted2natural.
360 * i.e. instead sorted[mid].compareTo(toFind), do sequential[sorted2natural[mid]].compareTo(toFind)
361 */
362 private Nodeid[] sequential; // natural repository order, childrenOf rely on ordering
363 private Nodeid[] sorted; // for binary search
364 private int[] sorted2natural;
365
366 public RevisionMap() {
367 }
368
369 public HgRepository getRepo() {
370 return Revlog.this.getRepo();
371 }
372
373 public void next(int revisionIndex, Nodeid revision, int linkedRevision) {
374 sequential[revisionIndex] = sorted[revisionIndex] = revision;
375 }
376
377 /**
378 * @return <code>this</code> for convenience.
379 */
380 public RevisionMap init(/*XXX Pool<Nodeid> to reuse nodeids, if possible. */) throws HgInvalidControlFileException{
381 // XXX HgRepository.register((RepoChangeListener) this); // listen to changes in repo, re-init if needed?
382 final int revisionCount = Revlog.this.getRevisionCount();
383 sequential = new Nodeid[revisionCount];
384 sorted = new Nodeid[revisionCount];
385 Revlog.this.indexWalk(0, TIP, this);
386 // next is alternative to Arrays.sort(sorted), and build sorted2natural looking up each element of sequential in sorted.
387 // the way sorted2natural was build is O(n*log n).
388 final ArrayHelper ah = new ArrayHelper();
389 ah.sort(sorted);
390 // note, values in ArrayHelper#getReversed are 1-based indexes, not 0-based
391 sorted2natural = ah.getReverse();
392 return this;
393 }
394
395 public Nodeid revision(int revisionIndex) {
396 return sequential[revisionIndex];
397 }
398 public int revisionIndex(Nodeid revision) {
399 if (revision == null || revision.isNull()) {
400 return BAD_REVISION;
401 }
402 int x = Arrays.binarySearch(sorted, revision);
403 if (x < 0) {
404 return BAD_REVISION;
405 }
406 return sorted2natural[x]-1;
407 }
408 }
409
410 protected abstract static class ErrorHandlingInspector implements RevlogStream.Inspector, CancelSupport { 345 protected abstract static class ErrorHandlingInspector implements RevlogStream.Inspector, CancelSupport {
411 private Exception failure; 346 private Exception failure;
412 private CancelSupport cancelSupport; 347 private CancelSupport cancelSupport;
413 348
414 protected void setCancelSupport(CancelSupport cs) { 349 protected void setCancelSupport(CancelSupport cs) {