Mercurial > jhg

comparison src/org/tmatesoft/hg/repo/HgParentChildMap.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 a937e63b6e02
children af5223b86dd3
comparison
equal deleted inserted replaced
656:a937e63b6e02 657:6334b0267103
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.ArrayHelper;
31 import org.tmatesoft.hg.internal.IntMap; 32 import org.tmatesoft.hg.internal.IntMap;
32 import org.tmatesoft.hg.repo.Revlog.ParentInspector; 33 import org.tmatesoft.hg.repo.Revlog.ParentInspector;
33 34
34 /** 35 /**
35 * Helper class to deal with parent-child relationship between revisions <i>en masse</i>. 36 * Helper class to deal with parent-child relationship between revisions <i>en masse</i>.
60 */ 61 */
61 public final class HgParentChildMap<T extends Revlog> implements ParentInspector { 62 public final class HgParentChildMap<T extends Revlog> implements ParentInspector {
62 63
63 // IMPORTANT: Nodeid instances shall be shared between all arrays 64 // IMPORTANT: Nodeid instances shall be shared between all arrays
64 65
66 private final T revlog;
65 private Nodeid[] sequential; // natural repository order, childrenOf rely on ordering 67 private Nodeid[] sequential; // natural repository order, childrenOf rely on ordering
66 private Nodeid[] sorted; // for binary search 68 private Nodeid[] sorted; // for binary search, just an origin of the actual value in use, the one inside seqWrapper
67 private int[] sorted2natural; // indexes in sorted to indexes in sequential
68 private Nodeid[] firstParent; // parents by natural order (i.e. firstParent[A] is parent of revision with index A) 69 private Nodeid[] firstParent; // parents by natural order (i.e. firstParent[A] is parent of revision with index A)
69 private Nodeid[] secondParent; 70 private Nodeid[] secondParent;
70 private final T revlog;
71 private IntMap<Nodeid> heads; 71 private IntMap<Nodeid> heads;
72 private BitSet headsBitSet; // 1 indicates revision got children, != null only during init; 72 private BitSet headsBitSet; // 1 indicates revision got children, != null only during init;
73 private HgRevisionMap<T> revisionIndexMap;
74 private ArrayHelper<Nodeid> seqWrapper;
73 75
74 76
75 public HgParentChildMap(T owner) { 77 public HgParentChildMap(T owner) {
76 revlog = owner; 78 revlog = owner;
77 } 79 }
109 // real improvement (IntMap has 2n capacity, and element lookup is log(n) instead of array's constant). 111 // 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 112 // FWIW: in cpython's repo, with 70k+ revisions, there are 2618 values in secondParent
111 secondParent = new Nodeid[revisionCount]; 113 secondParent = new Nodeid[revisionCount];
112 // 114 //
113 sequential = new Nodeid[revisionCount]; 115 sequential = new Nodeid[revisionCount];
114 sorted = new Nodeid[revisionCount]; 116 sorted = new Nodeid[revisionCount];
115 headsBitSet = new BitSet(revisionCount); 117 headsBitSet = new BitSet(revisionCount);
116 revlog.indexWalk(0, TIP, this); 118 revlog.indexWalk(0, TIP, this);
117 Arrays.sort(sorted); 119 seqWrapper = new ArrayHelper<Nodeid>(sequential);
118 // FIXME use ArrayHelper instead 120 // HgRevisionMap doesn't keep sorted, try alternative here.
119 sorted2natural = new int[revisionCount]; 121 // reference this.sorted (not only from ArrayHelper) helps to track ownership in hprof/mem dumps
120 for (int i = 0; i < revisionCount; i++) { 122 seqWrapper.sort(sorted, false, true);
121 Nodeid n = sequential[i];
122 int x = Arrays.binarySearch(sorted, n);
123 assertSortedIndex(x);
124 sorted2natural[x] = i;
125 }
126 // no reason to keep BitSet, number of heads is usually small 123 // no reason to keep BitSet, number of heads is usually small
127 IntMap<Nodeid> _heads = new IntMap<Nodeid>(headsBitSet.size() - headsBitSet.cardinality()); 124 IntMap<Nodeid> _heads = new IntMap<Nodeid>(headsBitSet.size() - headsBitSet.cardinality());
128 int index = 0; 125 int index = 0;
129 while (index < sequential.length) { 126 while (index < sequential.length) {
130 index = headsBitSet.nextClearBit(index); 127 index = headsBitSet.nextClearBit(index);
149 * Note, {@link Nodeid#NULL}, although implicitly present as parent of a first revision, is not recognized as known. 146 * Note, {@link Nodeid#NULL}, although implicitly present as parent of a first revision, is not recognized as known.
150 * @param nid revision to check, not <code>null</code> 147 * @param nid revision to check, not <code>null</code>
151 * @return <code>true</code> if revision matches any revision in this revlog 148 * @return <code>true</code> if revision matches any revision in this revlog
152 */ 149 */
153 public boolean knownNode(Nodeid nid) { 150 public boolean knownNode(Nodeid nid) {
154 return Arrays.binarySearch(sorted, nid) >= 0; 151 return seqWrapper.binarySearchSorted(nid) >= 0;
155 } 152 }
156 153
157 /** 154 /**
158 * null if none. only known nodes (as per #knownNode) are accepted as arguments 155 * null if none. only known nodes (as per #knownNode) are accepted as arguments
159 */ 156 */
160 public Nodeid firstParent(Nodeid nid) { 157 public Nodeid firstParent(Nodeid nid) {
161 int x = Arrays.binarySearch(sorted, nid); 158 int x = seqWrapper.binarySearchSorted(nid);
162 assertSortedIndex(x); 159 assertSortedIndex(x);
163 int i = sorted2natural[x]; 160 int i = seqWrapper.getReverseIndex(x);
164 return firstParent[i]; 161 return firstParent[i];
165 } 162 }
166 163
167 // never null, Nodeid.NULL if none known 164 // never null, Nodeid.NULL if none known
168 public Nodeid safeFirstParent(Nodeid nid) { 165 public Nodeid safeFirstParent(Nodeid nid) {
169 Nodeid rv = firstParent(nid); 166 Nodeid rv = firstParent(nid);
170 return rv == null ? Nodeid.NULL : rv; 167 return rv == null ? Nodeid.NULL : rv;
171 } 168 }
172 169
173 public Nodeid secondParent(Nodeid nid) { 170 public Nodeid secondParent(Nodeid nid) {
174 int x = Arrays.binarySearch(sorted, nid); 171 int x = seqWrapper.binarySearchSorted(nid);
175 assertSortedIndex(x); 172 assertSortedIndex(x);
176 int i = sorted2natural[x]; 173 int i = seqWrapper.getReverseIndex(x);
177 return secondParent[i]; 174 return secondParent[i];
178 } 175 }
179 176
180 public Nodeid safeSecondParent(Nodeid nid) { 177 public Nodeid safeSecondParent(Nodeid nid) {
181 Nodeid rv = secondParent(nid); 178 Nodeid rv = secondParent(nid);
182 return rv == null ? Nodeid.NULL : rv; 179 return rv == null ? Nodeid.NULL : rv;
183 } 180 }
184 181
185 public boolean appendParentsOf(Nodeid nid, Collection<Nodeid> c) { 182 public boolean appendParentsOf(Nodeid nid, Collection<Nodeid> c) {
186 int x = Arrays.binarySearch(sorted, nid); 183 int x = seqWrapper.binarySearchSorted(nid);
187 assertSortedIndex(x); 184 assertSortedIndex(x);
188 int i = sorted2natural[x]; 185 int i = seqWrapper.getReverseIndex(x);
189 Nodeid p1 = firstParent[i]; 186 Nodeid p1 = firstParent[i];
190 boolean modified = false; 187 boolean modified = false;
191 if (p1 != null) { 188 if (p1 != null) {
192 modified = c.add(p1); 189 modified = c.add(p1);
193 } 190 }
212 int earliestRevision = Integer.MAX_VALUE; 209 int earliestRevision = Integer.MAX_VALUE;
213 assert sequential.length == firstParent.length && firstParent.length == secondParent.length; 210 assert sequential.length == firstParent.length && firstParent.length == secondParent.length;
214 // first, find earliest index of roots in question, as there's no sense 211 // first, find earliest index of roots in question, as there's no sense
215 // to check children among nodes prior to branch's root node 212 // to check children among nodes prior to branch's root node
216 for (Nodeid r : roots) { 213 for (Nodeid r : roots) {
217 int x = Arrays.binarySearch(sorted, r); 214 int x = seqWrapper.binarySearchSorted(r);
218 assertSortedIndex(x); 215 assertSortedIndex(x);
219 int i = sorted2natural[x]; 216 int i = seqWrapper.getReverseIndex(x);
220 if (i < earliestRevision) { 217 if (i < earliestRevision) {
221 earliestRevision = i; 218 earliestRevision = i;
222 } 219 }
223 parents.add(sequential[i]); // add canonical instance in hope equals() is bit faster when can do a == 220 parents.add(sequential[i]); // add canonical instance in hope equals() is bit faster when can do a ==
224 } 221 }
229 } 226 }
230 } 227 }
231 return result; 228 return result;
232 } 229 }
233 230
234 public long AAA = 0;
235
236 /** 231 /**
237 * @return revisions that have supplied revision as their immediate parent 232 * @return revisions that have supplied revision as their immediate parent
238 */ 233 */
239 public List<Nodeid> directChildren(Nodeid nid) { 234 public List<Nodeid> directChildren(Nodeid nid) {
240 int x = Arrays.binarySearch(sorted, nid); 235 int x = seqWrapper.binarySearchSorted(nid);
241 assertSortedIndex(x); 236 assertSortedIndex(x);
242 nid = sorted[x]; // canonical instance 237 int start = seqWrapper.getReverseIndex(x);
243 int start = sorted2natural[x]; 238 nid = sequential[start]; // canonical instance
244 if (!hasChildren(start)) { 239 if (!hasChildren(start)) {
245 return Collections.emptyList(); 240 return Collections.emptyList();
246 } 241 }
247 ArrayList<Nodeid> result = new ArrayList<Nodeid>(5); 242 ArrayList<Nodeid> result = new ArrayList<Nodeid>(5);
248 for (int i = start + 1; i < sequential.length; i++) { 243 for (int i = start + 1; i < sequential.length; i++) {
249 AAA++;
250 if (nid == firstParent[i] || nid == secondParent[i]) { 244 if (nid == firstParent[i] || nid == secondParent[i]) {
251 result.add(sequential[i]); 245 result.add(sequential[i]);
252 } 246 }
253 } 247 }
254 return result; 248 return result;
257 /** 251 /**
258 * @param nid possibly parent node, shall be {@link #knownNode(Nodeid) known} in this revlog. 252 * @param nid possibly parent node, shall be {@link #knownNode(Nodeid) known} in this revlog.
259 * @return <code>true</code> if there's any node in this revlog that has specified node as one of its parents. 253 * @return <code>true</code> if there's any node in this revlog that has specified node as one of its parents.
260 */ 254 */
261 public boolean hasChildren(Nodeid nid) { 255 public boolean hasChildren(Nodeid nid) {
262 int x = Arrays.binarySearch(sorted, nid); 256 int x = seqWrapper.binarySearchSorted(nid);
263 assertSortedIndex(x); 257 assertSortedIndex(x);
264 int i = sorted2natural[x]; 258 int i = seqWrapper.getReverseIndex(x);
265 return hasChildren(i); 259 return hasChildren(i);
266 } 260 }
267 261
268 /** 262 /**
269 * @return all revisions this map knows about 263 * @return all revisions this map knows about
278 * @param root revision to check for being (grand-)*parent of a child 272 * @param root revision to check for being (grand-)*parent of a child
279 * @param wannaBeChild candidate descendant revision 273 * @param wannaBeChild candidate descendant revision
280 * @return <code>true</code> if <code>wannaBeChild</code> is among children of <code>root</code> 274 * @return <code>true</code> if <code>wannaBeChild</code> is among children of <code>root</code>
281 */ 275 */
282 public boolean isChild(Nodeid root, Nodeid wannaBeChild) { 276 public boolean isChild(Nodeid root, Nodeid wannaBeChild) {
283 int x = Arrays.binarySearch(sorted, root); 277 int x = seqWrapper.binarySearchSorted(root);
284 assertSortedIndex(x); 278 assertSortedIndex(x);
285 root = sorted[x]; // canonical instance 279 final int start = seqWrapper.getReverseIndex(x);
286 final int start = sorted2natural[x]; 280 root = sequential[start]; // canonical instance
287 if (!hasChildren(start)) { 281 if (!hasChildren(start)) {
288 return false; // root got no children at all 282 return false; // root got no children at all
289 } 283 }
290 int y = Arrays.binarySearch(sorted, wannaBeChild); 284 int y = seqWrapper.binarySearchSorted(wannaBeChild);
291 if (y < 0) { 285 if (y < 0) {
292 return false; // not found 286 return false; // not found
293 } 287 }
294 wannaBeChild = sorted[y]; // canonicalize 288 final int end = seqWrapper.getReverseIndex(y);
295 final int end = sorted2natural[y]; 289 wannaBeChild = sequential[end]; // canonicalize
296 if (end <= start) { 290 if (end <= start) {
297 return false; // potential child was in repository earlier than root 291 return false; // potential child was in repository earlier than root
298 } 292 }
299 HashSet<Nodeid> parents = new HashSet<Nodeid>(); 293 HashSet<Nodeid> parents = new HashSet<Nodeid>();
300 parents.add(root); 294 parents.add(root);
310 * @return elements of this map that do not have a child recorded therein. 304 * @return elements of this map that do not have a child recorded therein.
311 */ 305 */
312 public Collection<Nodeid> heads() { 306 public Collection<Nodeid> heads() {
313 return heads.values(); 307 return heads.values();
314 } 308 }
309
310 /**
311 * @return map of revision to indexes
312 */
313 public HgRevisionMap<T> getRevisionMap() {
314 if (revisionIndexMap == null) {
315 revisionIndexMap = new HgRevisionMap<T>(revlog);
316 revisionIndexMap.init(seqWrapper);
317 }
318 return revisionIndexMap;
319 }
315 320
316 private boolean hasChildren(int sequentialIndex) { 321 private boolean hasChildren(int sequentialIndex) {
317 return !heads.containsKey(sequentialIndex); 322 return !heads.containsKey(sequentialIndex);
318 } 323 }
319 } 324 }