Mercurial > jhg

comparison src/org/tmatesoft/hg/repo/Revlog.java @ 432:1fc0da631200

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
author Artem Tikhomirov <tikhomirov.artem@gmail.com>
date Fri, 30 Mar 2012 16:22:51 +0200
parents 12f668401613
children be697c3e951e
comparison
equal deleted inserted replaced
431:12f668401613 432:1fc0da631200
20 20
21 import java.io.IOException; 21 import java.io.IOException;
22 import java.nio.ByteBuffer; 22 import java.nio.ByteBuffer;
23 import java.util.ArrayList; 23 import java.util.ArrayList;
24 import java.util.Arrays; 24 import java.util.Arrays;
25 import java.util.Collection;
26 import java.util.HashSet;
27 import java.util.LinkedList;
28 import java.util.List; 25 import java.util.List;
29 26
30 import org.tmatesoft.hg.core.Nodeid; 27 import org.tmatesoft.hg.core.Nodeid;
31 import org.tmatesoft.hg.internal.ArrayHelper; 28 import org.tmatesoft.hg.internal.ArrayHelper;
32 import org.tmatesoft.hg.internal.DataAccess; 29 import org.tmatesoft.hg.internal.DataAccess;
335 public interface ParentInspector extends Inspector { 332 public interface ParentInspector extends Inspector {
336 // XXX document whether parentX is -1 or a constant (BAD_REVISION? or dedicated?) 333 // XXX document whether parentX is -1 or a constant (BAD_REVISION? or dedicated?)
337 void next(int revisionIndex, Nodeid revision, int parent1, int parent2, Nodeid nidParent1, Nodeid nidParent2); 334 void next(int revisionIndex, Nodeid revision, int parent1, int parent2, Nodeid nidParent1, Nodeid nidParent2);
338 } 335 }
339 336
340 /* 337 protected HgParentChildMap<? extends Revlog> getParentWalker() {
341 * FIXME think over if it's better to do either: 338 HgParentChildMap<Revlog> pw = new HgParentChildMap<Revlog>(this);
342 * pw = getChangelog().new ParentWalker(); pw.init() and pass pw instance around as needed 339 pw.init();
343 * or 340 return pw;
344 * add Revlog#getParentWalker(), static class, make cons() and #init package-local, and keep SoftReference to allow walker reuse.
345 *
346 * and yes, walker is not a proper name
347 */
348 public final class ParentWalker implements ParentInspector {
349
350
351 private Nodeid[] sequential; // natural repository order, childrenOf rely on ordering
352 private Nodeid[] sorted; // for binary search
353 private int[] sorted2natural;
354 private Nodeid[] firstParent;
355 private Nodeid[] secondParent;
356
357 // Nodeid instances shall be shared between all arrays
358
359 public ParentWalker() {
360 }
361
362 public HgRepository getRepo() {
363 return Revlog.this.getRepo();
364 }
365
366 public void next(int revisionNumber, Nodeid revision, int parent1Revision, int parent2Revision, Nodeid nidParent1, Nodeid nidParent2) {
367 if (parent1Revision >= revisionNumber || parent2Revision >= revisionNumber) {
368 throw new IllegalStateException(); // sanity, revisions are sequential
369 }
370 int ix = revisionNumber;
371 sequential[ix] = sorted[ix] = revision;
372 if (parent1Revision != -1) {
373 firstParent[ix] = sequential[parent1Revision];
374 }
375 if (parent2Revision != -1) { // revlog of DataAccess.java has p2 set when p1 is -1
376 secondParent[ix] = sequential[parent2Revision];
377 }
378 }
379
380 public void init() throws HgInvalidControlFileException {
381 final int revisionCount = Revlog.this.getRevisionCount();
382 firstParent = new Nodeid[revisionCount];
383 // TODO [post 1.0] Branches/merges are less frequent, and most of secondParent would be -1/null, hence
384 // IntMap might be better alternative here, but need to carefully analyze (test) whether this brings
385 // real improvement (IntMap has 2n capacity, and element lookup is log(n) instead of array's constant)
386 secondParent = new Nodeid[revisionCount];
387 //
388 sequential = new Nodeid[revisionCount];
389 sorted = new Nodeid[revisionCount];
390 Revlog.this.indexWalk(0, TIP, this);
391 Arrays.sort(sorted);
392 sorted2natural = new int[revisionCount];
393 for (int i = 0; i < revisionCount; i++) {
394 Nodeid n = sequential[i];
395 int x = Arrays.binarySearch(sorted, n);
396 assertSortedIndex(x);
397 sorted2natural[x] = i;
398 }
399 }
400
401 private void assertSortedIndex(int x) {
402 if (x < 0) {
403 throw new HgInvalidStateException(String.format("Bad index", x));
404 }
405 }
406
407 /**
408 * Tells whether supplied revision is from the walker's associated revlog.
409 * Note, {@link Nodeid#NULL}, although implicitly present as parent of a first revision, is not recognized as known.
410 * @param nid revision to check, not <code>null</code>
411 * @return <code>true</code> if revision matches any revision in this revlog
412 */
413 public boolean knownNode(Nodeid nid) {
414 return Arrays.binarySearch(sorted, nid) >= 0;
415 }
416
417 /**
418 * null if none. only known nodes (as per #knownNode) are accepted as arguments
419 */
420 public Nodeid firstParent(Nodeid nid) {
421 int x = Arrays.binarySearch(sorted, nid);
422 assertSortedIndex(x);
423 int i = sorted2natural[x];
424 return firstParent[i];
425 }
426
427 // never null, Nodeid.NULL if none known
428 public Nodeid safeFirstParent(Nodeid nid) {
429 Nodeid rv = firstParent(nid);
430 return rv == null ? Nodeid.NULL : rv;
431 }
432
433 public Nodeid secondParent(Nodeid nid) {
434 int x = Arrays.binarySearch(sorted, nid);
435 assertSortedIndex(x);
436 int i = sorted2natural[x];
437 return secondParent[i];
438 }
439
440 public Nodeid safeSecondParent(Nodeid nid) {
441 Nodeid rv = secondParent(nid);
442 return rv == null ? Nodeid.NULL : rv;
443 }
444
445 public boolean appendParentsOf(Nodeid nid, Collection<Nodeid> c) {
446 int x = Arrays.binarySearch(sorted, nid);
447 assertSortedIndex(x);
448 int i = sorted2natural[x];
449 Nodeid p1 = firstParent[i];
450 boolean modified = false;
451 if (p1 != null) {
452 modified = c.add(p1);
453 }
454 Nodeid p2 = secondParent[i];
455 if (p2 != null) {
456 modified = c.add(p2) || modified;
457 }
458 return modified;
459 }
460
461 // XXX alternative (and perhaps more reliable) approach would be to make a copy of allNodes and remove
462 // nodes, their parents and so on.
463
464 // @return ordered collection of all children rooted at supplied nodes. Nodes shall not be descendants of each other!
465 // Nodeids shall belong to this revlog
466 public List<Nodeid> childrenOf(List<Nodeid> roots) {
467 HashSet<Nodeid> parents = new HashSet<Nodeid>();
468 LinkedList<Nodeid> result = new LinkedList<Nodeid>();
469 int earliestRevision = Integer.MAX_VALUE;
470 assert sequential.length == firstParent.length && firstParent.length == secondParent.length;
471 // first, find earliest index of roots in question, as there's no sense
472 // to check children among nodes prior to branch's root node
473 for (Nodeid r : roots) {
474 int x = Arrays.binarySearch(sorted, r);
475 assertSortedIndex(x);
476 int i = sorted2natural[x];
477 if (i < earliestRevision) {
478 earliestRevision = i;
479 }
480 parents.add(sequential[i]); // add canonical instance in hope equals() is bit faster when can do a ==
481 }
482 for (int i = earliestRevision + 1; i < sequential.length; i++) {
483 if (parents.contains(firstParent[i]) || parents.contains(secondParent[i])) {
484 parents.add(sequential[i]); // to find next child
485 result.add(sequential[i]);
486 }
487 }
488 return result;
489 }
490
491 /**
492 * @return revisions that have supplied revision as their immediate parent
493 */
494 public List<Nodeid> directChildren(Nodeid nid) {
495 LinkedList<Nodeid> result = new LinkedList<Nodeid>();
496 int x = Arrays.binarySearch(sorted, nid);
497 assertSortedIndex(x);
498 nid = sorted[x]; // canonical instance
499 int start = sorted2natural[x];
500 for (int i = start + 1; i < sequential.length; i++) {
501 if (nid == firstParent[i] || nid == secondParent[i]) {
502 result.add(sequential[i]);
503 }
504 }
505 return result;
506 }
507
508 /**
509 * @param nid possibly parent node, shall be {@link #knownNode(Nodeid) known} in this revlog.
510 * @return <code>true</code> if there's any node in this revlog that has specified node as one of its parents.
511 */
512 public boolean hasChildren(Nodeid nid) {
513 int x = Arrays.binarySearch(sorted, nid);
514 assertSortedIndex(x);
515 int i = sorted2natural[x];
516 assert firstParent.length == secondParent.length; // just in case later I implement sparse array for secondParent
517 assert firstParent.length == sequential.length;
518 // to use == instead of equals, take the same Nodeid instance we used to fill all the arrays.
519 final Nodeid canonicalNode = sequential[i];
520 i++; // no need to check node itself. child nodes may appear in sequential only after revision in question
521 for (; i < sequential.length; i++) {
522 // TODO [post 1.0] likely, not very effective.
523 // May want to optimize it with another (Tree|Hash)Set, created on demand on first use,
524 // however, need to be careful with memory usage
525 if (firstParent[i] == canonicalNode || secondParent[i] == canonicalNode) {
526 return true;
527 }
528 }
529 return false;
530 }
531 } 341 }
532 342
533 /** 343 /**
534 * Effective int to Nodeid and vice versa translation. It's advised to use this class instead of 344 * Effective int to Nodeid and vice versa translation. It's advised to use this class instead of
535 * multiple {@link Revlog#getRevisionIndex(Nodeid)} calls. 345 * multiple {@link Revlog#getRevisionIndex(Nodeid)} calls.