Mercurial > jhg

comparison src/org/tmatesoft/hg/repo/HgParentChildMap.java @ 679:19f5167c2155

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
HgParentChildMap: deduce common ancestor functionality
author Artem Tikhomirov <tikhomirov.artem@gmail.com>
date Sat, 20 Jul 2013 17:40:52 +0200
parents d2552e6a5af6
children
comparison
equal deleted inserted replaced
678:8625cba0a5a8 679:19f5167c2155
345 revisionIndexMap = new HgRevisionMap<T>(revlog); 345 revisionIndexMap = new HgRevisionMap<T>(revlog);
346 revisionIndexMap.init(seqWrapper); 346 revisionIndexMap.init(seqWrapper);
347 } 347 }
348 return revisionIndexMap; 348 return revisionIndexMap;
349 } 349 }
350
351 /**
352 * @return common ancestor of two revisions
353 */
354 public Nodeid ancestor(Nodeid r1, Nodeid r2) {
355 if (r1.equals(r2)) {
356 return r1;
357 }
358 BitSet a1 = buildAncestors(r1);
359 BitSet a2 = buildAncestors(r2);
360 // BitSet.and() trims to shorter bitset, it's ok as we are not
361 // interested in bits that are part of one bitset only
362 a1.and(a2);
363 final int cardinality = a1.cardinality();
364 if (cardinality == 1) {
365 return sequential[a1.nextSetBit(0)];
366 }
367 assert cardinality > 0; // every revision is child of at least rev0
368 final int length = sequential.length;
369 int index = length / 2;
370 int lastBitSet = -1;
371 do {
372 int nextSetBit = a1.nextSetBit(index);
373 int nextIndex;
374 if (nextSetBit == -1) {
375 assert lastBitSet == -1 || lastBitSet <= index;
376 nextIndex = index - (index - (lastBitSet == -1 ? 0 : lastBitSet)) / 2;
377 } else {
378 lastBitSet = nextSetBit;
379 nextIndex = lastBitSet + (length - lastBitSet) / 2;
380 }
381 if (nextIndex == index) {
382 break;
383 }
384 index = nextIndex;
385 } while (true);
386 if (lastBitSet == -1) {
387 assert false; // likely error in the algorithm above (e.g. can't reach index==0)
388 return sequential[0];
389 }
390 return sequential[lastBitSet];
391 }
350 392
351 private boolean hasChildren(int sequentialIndex) { 393 private boolean hasChildren(int sequentialIndex) {
352 return !heads.containsKey(sequentialIndex); 394 return !heads.containsKey(sequentialIndex);
353 } 395 }
396
397 private BitSet buildAncestors(Nodeid nid) {
398 int x = seqWrapper.binarySearchSorted(nid);
399 assertSortedIndex(x);
400 int i = seqWrapper.getReverseIndex(x);
401 BitSet rv = new BitSet(sequential.length);
402 HashSet<Nodeid> ancestors = new HashSet<Nodeid>();
403 ancestors.add(nid);
404 do {
405 if (ancestors.contains(sequential[i])) {
406 rv.set(i);
407 if(firstParent[i] != null) {
408 ancestors.add(firstParent[i]);
409 }
410 if (secondParent[i] != null) {
411 ancestors.add(secondParent[i]);
412 }
413 }
414 i--;
415 } while (i >= 0);
416 return rv;
417 }
354 } 418 }