Mercurial > jhg

comparison src/org/tmatesoft/hg/repo/Revlog.java @ 307:2f2ab5c27f41

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Collect sort reverse indexes along with array sorting
author Artem Tikhomirov <tikhomirov.artem@gmail.com>
date Sat, 24 Sep 2011 04:06:27 +0200
parents 74e7493a042a
children 3f40262153a4
comparison
equal deleted inserted replaced
306:971baa95fb07 307:2f2ab5c27f41
28 import java.util.List; 28 import java.util.List;
29 29
30 import org.tmatesoft.hg.core.HgBadStateException; 30 import org.tmatesoft.hg.core.HgBadStateException;
31 import org.tmatesoft.hg.core.HgException; 31 import org.tmatesoft.hg.core.HgException;
32 import org.tmatesoft.hg.core.Nodeid; 32 import org.tmatesoft.hg.core.Nodeid;
33 import org.tmatesoft.hg.internal.ArrayHelper;
33 import org.tmatesoft.hg.internal.DataAccess; 34 import org.tmatesoft.hg.internal.DataAccess;
34 import org.tmatesoft.hg.internal.RevlogStream; 35 import org.tmatesoft.hg.internal.RevlogStream;
35 import org.tmatesoft.hg.util.ByteChannel; 36 import org.tmatesoft.hg.util.ByteChannel;
36 import org.tmatesoft.hg.util.CancelSupport; 37 import org.tmatesoft.hg.util.CancelSupport;
37 import org.tmatesoft.hg.util.CancelledException; 38 import org.tmatesoft.hg.util.CancelledException;
414 public RevisionMap init(/*XXX Pool<Nodeid> to reuse nodeids, if possible. */) { 415 public RevisionMap init(/*XXX Pool<Nodeid> to reuse nodeids, if possible. */) {
415 // XXX HgRepository.register((RepoChangeListener) this); // listen to changes in repo, re-init if needed? 416 // XXX HgRepository.register((RepoChangeListener) this); // listen to changes in repo, re-init if needed?
416 final int revisionCount = Revlog.this.content.revisionCount(); 417 final int revisionCount = Revlog.this.content.revisionCount();
417 sequential = new Nodeid[revisionCount]; 418 sequential = new Nodeid[revisionCount];
418 sorted = new Nodeid[revisionCount]; 419 sorted = new Nodeid[revisionCount];
419 sorted2natural = new int[revisionCount];
420 RevlogStream.Inspector insp = new RevlogStream.Inspector() { 420 RevlogStream.Inspector insp = new RevlogStream.Inspector() {
421 421
422 public void next(int revisionNumber, int actualLen, int baseRevision, int linkRevision, int parent1Revision, int parent2Revision, byte[] nodeid, DataAccess data) { 422 public void next(int revisionNumber, int actualLen, int baseRevision, int linkRevision, int parent1Revision, int parent2Revision, byte[] nodeid, DataAccess data) {
423 final Nodeid nid = new Nodeid(nodeid, true); 423 final Nodeid nid = new Nodeid(nodeid, true);
424 sequential[revisionNumber] = sorted[revisionNumber] = nid; 424 sequential[revisionNumber] = sorted[revisionNumber] = nid;
425 } 425 }
426 }; 426 };
427 Revlog.this.content.iterate(0, TIP, false, insp); 427 Revlog.this.content.iterate(0, TIP, false, insp);
428 Arrays.sort(sorted); 428 // next is alternative to Arrays.sort(sorted), and build sorted2natural looking up each element of sequential in sorted.
429 for (int i = 0; i < revisionCount; i++) { 429 // the way sorted2natural was build is O(n*log n).
430 Nodeid n = sequential[i]; 430 final ArrayHelper ah = new ArrayHelper();
431 int x = Arrays.binarySearch(sorted, n); 431 ah.sort(sorted);
432 sorted2natural[x] = i; 432 // note, values in ArrayHelper#getReversed are 1-based indexes, not 0-based
433 } 433 sorted2natural = ah.getReverse();
434 return this; 434 return this;
435 } 435 }
436 436
437 public Nodeid revision(int localRevision) { 437 public Nodeid revision(int localRevision) {
438 return sequential[localRevision]; 438 return sequential[localRevision];
443 } 443 }
444 int x = Arrays.binarySearch(sorted, revision); 444 int x = Arrays.binarySearch(sorted, revision);
445 if (x < 0) { 445 if (x < 0) {
446 return BAD_REVISION; 446 return BAD_REVISION;
447 } 447 }
448 return sorted2natural[x]; 448 return sorted2natural[x]-1;
449 } 449 }
450 } 450 }
451 451
452 protected abstract static class ErrorHandlingInspector implements RevlogStream.Inspector, CancelSupport { 452 protected abstract static class ErrorHandlingInspector implements RevlogStream.Inspector, CancelSupport {
453 private Exception failure; 453 private Exception failure;