Mercurial > hg4j

comparison src/org/tmatesoft/hg/repo/HgParentChildMap.java @ 656:a937e63b6e02

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Performance: rebuild information about branches takes too long (my improvement: 3 times, 11-15 s to less than 4 sec)
author Artem Tikhomirov <tikhomirov.artem@gmail.com>
date Thu, 04 Jul 2013 18:40:03 +0200
parents 629a7370554c
children 6334b0267103
comparison
equal deleted inserted replaced
655:bcbcc318f250 656:a937e63b6e02
26 import java.util.HashSet; 26 import java.util.HashSet;
27 import java.util.LinkedList; 27 import java.util.LinkedList;
28 import java.util.List; 28 import java.util.List;
29 29
30 import org.tmatesoft.hg.core.Nodeid; 30 import org.tmatesoft.hg.core.Nodeid;
31 import org.tmatesoft.hg.internal.IntMap;
31 import org.tmatesoft.hg.repo.Revlog.ParentInspector; 32 import org.tmatesoft.hg.repo.Revlog.ParentInspector;
32 33
33 /** 34 /**
34 * Helper class to deal with parent-child relationship between revisions <i>en masse</i>. 35 * Helper class to deal with parent-child relationship between revisions <i>en masse</i>.
35 * Works in terms of {@link Nodeid nodeids}, there's no need to deal with revision indexes. 36 * Works in terms of {@link Nodeid nodeids}, there's no need to deal with revision indexes.
65 private Nodeid[] sorted; // for binary search 66 private Nodeid[] sorted; // for binary search
66 private int[] sorted2natural; // indexes in sorted to indexes in sequential 67 private int[] sorted2natural; // indexes in sorted to indexes in sequential
67 private Nodeid[] firstParent; // parents by natural order (i.e. firstParent[A] is parent of revision with index A) 68 private Nodeid[] firstParent; // parents by natural order (i.e. firstParent[A] is parent of revision with index A)
68 private Nodeid[] secondParent; 69 private Nodeid[] secondParent;
69 private final T revlog; 70 private final T revlog;
70 private BitSet heads; // 1 indicates revision got children 71 private IntMap<Nodeid> heads;
72 private BitSet headsBitSet; // 1 indicates revision got children, != null only during init;
71 73
72 74
73 public HgParentChildMap(T owner) { 75 public HgParentChildMap(T owner) {
74 revlog = owner; 76 revlog = owner;
75 } 77 }
84 } 86 }
85 int ix = revisionNumber; 87 int ix = revisionNumber;
86 sequential[ix] = sorted[ix] = revision; 88 sequential[ix] = sorted[ix] = revision;
87 if (parent1Revision != -1) { 89 if (parent1Revision != -1) {
88 firstParent[ix] = sequential[parent1Revision]; 90 firstParent[ix] = sequential[parent1Revision];
89 heads.set(parent1Revision); 91 headsBitSet.set(parent1Revision);
90 } 92 }
91 if (parent2Revision != -1) { // revlog of DataAccess.java has p2 set when p1 is -1 93 if (parent2Revision != -1) { // revlog of DataAccess.java has p2 set when p1 is -1
92 secondParent[ix] = sequential[parent2Revision]; 94 secondParent[ix] = sequential[parent2Revision];
93 heads.set(parent2Revision); 95 headsBitSet.set(parent2Revision);
94 } 96 }
95 } 97 }
96 98
97 /** 99 /**
98 * Prepare the map 100 * Prepare the map
102 public void init() throws HgRuntimeException { 104 public void init() throws HgRuntimeException {
103 final int revisionCount = revlog.getRevisionCount(); 105 final int revisionCount = revlog.getRevisionCount();
104 firstParent = new Nodeid[revisionCount]; 106 firstParent = new Nodeid[revisionCount];
105 // TODO [post 1.1] Branches/merges are less frequent, and most of secondParent would be -1/null, hence 107 // TODO [post 1.1] Branches/merges are less frequent, and most of secondParent would be -1/null, hence
106 // IntMap might be better alternative here, but need to carefully analyze (test) whether this brings 108 // IntMap might be better alternative here, but need to carefully analyze (test) whether this brings
107 // real improvement (IntMap has 2n capacity, and element lookup is log(n) instead of array's constant) 109 // real improvement (IntMap has 2n capacity, and element lookup is log(n) instead of array's constant).
110 // FWIW: in cpython's repo, with 70k+ revisions, there are 2618 values in secondParent
108 secondParent = new Nodeid[revisionCount]; 111 secondParent = new Nodeid[revisionCount];
109 // 112 //
110 sequential = new Nodeid[revisionCount]; 113 sequential = new Nodeid[revisionCount];
111 sorted = new Nodeid[revisionCount]; 114 sorted = new Nodeid[revisionCount];
112 heads = new BitSet(revisionCount); 115 headsBitSet = new BitSet(revisionCount);
113 revlog.indexWalk(0, TIP, this); 116 revlog.indexWalk(0, TIP, this);
114 Arrays.sort(sorted); 117 Arrays.sort(sorted);
115 // FIXME use ArrayHelper instead 118 // FIXME use ArrayHelper instead
116 sorted2natural = new int[revisionCount]; 119 sorted2natural = new int[revisionCount];
117 for (int i = 0; i < revisionCount; i++) { 120 for (int i = 0; i < revisionCount; i++) {
118 Nodeid n = sequential[i]; 121 Nodeid n = sequential[i];
119 int x = Arrays.binarySearch(sorted, n); 122 int x = Arrays.binarySearch(sorted, n);
120 assertSortedIndex(x); 123 assertSortedIndex(x);
121 sorted2natural[x] = i; 124 sorted2natural[x] = i;
122 } 125 }
126 // no reason to keep BitSet, number of heads is usually small
127 IntMap<Nodeid> _heads = new IntMap<Nodeid>(headsBitSet.size() - headsBitSet.cardinality());
128 int index = 0;
129 while (index < sequential.length) {
130 index = headsBitSet.nextClearBit(index);
131 // nextClearBit(length-1) gives length when bit is set,
132 // however, last revision can't be a parent of any other, and
133 // the last bit would be always 0, and no AIOOBE
134 _heads.put(index, sequential[index]);
135 index++;
136 }
137 headsBitSet = null;
138 heads = _heads;
123 } 139 }
124 140
125 private void assertSortedIndex(int x) { 141 private void assertSortedIndex(int x) {
126 if (x < 0) { 142 if (x < 0) {
127 throw new HgInvalidStateException(String.format("Bad index", x)); 143 throw new HgInvalidStateException(String.format("Bad index", x));
213 } 229 }
214 } 230 }
215 return result; 231 return result;
216 } 232 }
217 233
234 public long AAA = 0;
235
218 /** 236 /**
219 * @return revisions that have supplied revision as their immediate parent 237 * @return revisions that have supplied revision as their immediate parent
220 */ 238 */
221 public List<Nodeid> directChildren(Nodeid nid) { 239 public List<Nodeid> directChildren(Nodeid nid) {
222 int x = Arrays.binarySearch(sorted, nid); 240 int x = Arrays.binarySearch(sorted, nid);
224 nid = sorted[x]; // canonical instance 242 nid = sorted[x]; // canonical instance
225 int start = sorted2natural[x]; 243 int start = sorted2natural[x];
226 if (!hasChildren(start)) { 244 if (!hasChildren(start)) {
227 return Collections.emptyList(); 245 return Collections.emptyList();
228 } 246 }
229 LinkedList<Nodeid> result = new LinkedList<Nodeid>(); 247 ArrayList<Nodeid> result = new ArrayList<Nodeid>(5);
230 for (int i = start + 1; i < sequential.length; i++) { 248 for (int i = start + 1; i < sequential.length; i++) {
249 AAA++;
231 if (nid == firstParent[i] || nid == secondParent[i]) { 250 if (nid == firstParent[i] || nid == secondParent[i]) {
232 result.add(sequential[i]); 251 result.add(sequential[i]);
233 } 252 }
234 } 253 }
235 return result; 254 return result;
289 308
290 /** 309 /**
291 * @return elements of this map that do not have a child recorded therein. 310 * @return elements of this map that do not have a child recorded therein.
292 */ 311 */
293 public Collection<Nodeid> heads() { 312 public Collection<Nodeid> heads() {
294 ArrayList<Nodeid> result = new ArrayList<Nodeid>(); 313 return heads.values();
295 int index = 0;
296 do {
297 index = heads.nextClearBit(index);
298 // nextClearBit(length-1) gives length when bit is set,
299 // however, last revision can't be a parent of any other, and
300 // the last bit would be always 0, and no AIOOBE
301 result.add(sequential[index]);
302 index++;
303 } while (index < sequential.length);
304 return result;
305 } 314 }
306 315
307 private boolean hasChildren(int sequentialIndex) { 316 private boolean hasChildren(int sequentialIndex) {
308 return heads.get(sequentialIndex); 317 return !heads.containsKey(sequentialIndex);
309 } 318 }
310 } 319 }