Mercurial > jhg

comparison src/org/tmatesoft/hg/repo/HgRevisionMap.java @ 657:6334b0267103

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
author Artem Tikhomirov <tikhomirov.artem@gmail.com>
date Thu, 04 Jul 2013 20:27:45 +0200
parents 6526d8adbc0f
children
comparison
equal deleted inserted replaced
656:a937e63b6e02 657:6334b0267103
16 */ 16 */
17 package org.tmatesoft.hg.repo; 17 package org.tmatesoft.hg.repo;
18 18
19 import static org.tmatesoft.hg.repo.HgRepository.BAD_REVISION; 19 import static org.tmatesoft.hg.repo.HgRepository.BAD_REVISION;
20 import static org.tmatesoft.hg.repo.HgRepository.TIP; 20 import static org.tmatesoft.hg.repo.HgRepository.TIP;
21
22 import java.util.Arrays;
23 21
24 import org.tmatesoft.hg.core.Nodeid; 22 import org.tmatesoft.hg.core.Nodeid;
25 import org.tmatesoft.hg.internal.ArrayHelper; 23 import org.tmatesoft.hg.internal.ArrayHelper;
26 import org.tmatesoft.hg.repo.Revlog.RevisionInspector; 24 import org.tmatesoft.hg.repo.Revlog.RevisionInspector;
27 25
58 * in fact, initialization is much slower as it instantiates Nodeids, while #getRevisionIndex 56 * in fact, initialization is much slower as it instantiates Nodeids, while #getRevisionIndex
59 * compares directly against byte buffer. Measuring cpython with 70k+ gives 3 times difference (47 vs 171) 57 * compares directly against byte buffer. Measuring cpython with 70k+ gives 3 times difference (47 vs 171)
60 * for complete changelog iteration. 58 * for complete changelog iteration.
61 */ 59 */
62 60
61 private final T revlog;
63 /* 62 /*
64 * XXX 3 * (x * 4) bytes. Can I do better? 63 * XXX 3 * (x * 4) bytes. Can I do better?
65 * It seems, yes. Don't need to keep sorted, always can emulate it with indirect access to sequential through sorted2natural. 64 * It seems, yes. Don't need to keep sorted, always can emulate it with indirect access to sequential through sorted2natural.
66 * i.e. instead sorted[mid].compareTo(toFind), do sequential[sorted2natural[mid]].compareTo(toFind) 65 * i.e. instead sorted[mid].compareTo(toFind), do sequential[sorted2natural[mid]].compareTo(toFind)
67 */ 66 */
68 private Nodeid[] sequential; // natural repository order, childrenOf rely on ordering 67 private Nodeid[] sequential; // natural repository order
69 private Nodeid[] sorted; // for binary search 68 private ArrayHelper<Nodeid> seqWrapper;
70 private int[] sorted2natural;
71 private final T revlog;
72 69
73 public HgRevisionMap(T owner) { 70 public HgRevisionMap(T owner) {
74 revlog = owner; 71 revlog = owner;
75 } 72 }
76 73
77 public HgRepository getRepo() { 74 public HgRepository getRepo() {
78 return revlog.getRepo(); 75 return revlog.getRepo();
79 } 76 }
80 77
81 public void next(int revisionIndex, Nodeid revision, int linkedRevision) { 78 public void next(int revisionIndex, Nodeid revision, int linkedRevision) {
82 sequential[revisionIndex] = sorted[revisionIndex] = revision; 79 sequential[revisionIndex] = revision;
83 } 80 }
84 81
85 /** 82 /**
86 * @return <code>this</code> for convenience. 83 * @return <code>this</code> for convenience.
87 */ 84 */
88 public HgRevisionMap<T> init(/*XXX Pool<Nodeid> to reuse nodeids, if possible. */) throws HgRuntimeException { 85 public HgRevisionMap<T> init(/*XXX Pool<Nodeid> to reuse nodeids, if possible. */) throws HgRuntimeException {
89 // XXX HgRepository.register((RepoChangeListener) this); // listen to changes in repo, re-init if needed? 86 // XXX HgRepository.register((RepoChangeListener) this); // listen to changes in repo, re-init if needed?
90 final int revisionCount = revlog.getRevisionCount(); 87 final int revisionCount = revlog.getRevisionCount();
91 sequential = new Nodeid[revisionCount]; 88 sequential = new Nodeid[revisionCount];
92 sorted = new Nodeid[revisionCount];
93 revlog.indexWalk(0, TIP, this); 89 revlog.indexWalk(0, TIP, this);
94 // next is alternative to Arrays.sort(sorted), and build sorted2natural looking up each element of sequential in sorted. 90 // next is alternative to Arrays.sort(sorted), and build sorted2natural looking up each element of sequential in sorted.
95 // the way sorted2natural was build is O(n*log n). 91 // the way sorted2natural was build is O(n*log n).
96 final ArrayHelper ah = new ArrayHelper(); 92 seqWrapper = new ArrayHelper<Nodeid>(sequential);
97 ah.sort(sorted); 93 seqWrapper.sort(null, true, false);
98 // note, values in ArrayHelper#getReversed are 1-based indexes, not 0-based
99 sorted2natural = ah.getReverse();
100 return this; 94 return this;
95 }
96
97 /* friendly initializer to use from HgParentChildMap
98 /*package*/ void init(ArrayHelper<Nodeid> _seqWrapper) {
99 assert _seqWrapper.getData().length == revlog.getRevisionCount();
100 sequential = _seqWrapper.getData();
101 seqWrapper = _seqWrapper;
101 } 102 }
102 103
103 public Nodeid revision(int revisionIndex) { 104 public Nodeid revision(int revisionIndex) {
104 return sequential[revisionIndex]; 105 return sequential[revisionIndex];
105 } 106 }
107
106 public int revisionIndex(Nodeid revision) { 108 public int revisionIndex(Nodeid revision) {
107 if (revision == null || revision.isNull()) { 109 if (revision == null || revision.isNull()) {
108 return BAD_REVISION; 110 return BAD_REVISION;
109 } 111 }
110 int x = Arrays.binarySearch(sorted, revision); 112 return seqWrapper.binarySearch(revision, BAD_REVISION);
111 if (x < 0) {
112 return BAD_REVISION;
113 }
114 return sorted2natural[x]-1;
115 } 113 }
116 } 114 }