jhg: src/org/tmatesoft/hg/repo/HgParentChildMap.java annotate

annotate src/org/tmatesoft/hg/repo/HgParentChildMap.java @ 694:7efabe0cddcf

Speed up (a) file rename history to minimize file reads; (b) file.isCopy(int) to read metadata for few revisions at once (use pattern assumes earlier revisions are likely to be queried, too); (c) HgIgnore.isIgnored by caching matched initial fragments (to substitute more expensive Matcher.matches with cheaper HashMap.contains)

author	Artem Tikhomirov <tikhomirov.artem@gmail.com>
date	Mon, 05 Aug 2013 17:42:10 +0200
parents	19f5167c2155
children

rev	line source
432 1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	1 /*
628 6526d8adbc0f Explicit HgRuntimeException to facilitate easy switch from runtime to checked exceptions Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 433 diff changeset	2 * Copyright (c) 2011-2013 TMate Software Ltd
432 1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	3 *
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	4 * This program is free software; you can redistribute it and/or modify
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	5 * it under the terms of the GNU General Public License as published by
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	6 * the Free Software Foundation; version 2 of the License.
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	7 *
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	8 * This program is distributed in the hope that it will be useful,
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	11 * GNU General Public License for more details.
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	12 *
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	13 * For information on how to redistribute this software under
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	14 * the terms of a license other than GNU General Public License
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	15 * contact TMate Software at support@hg4j.com
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	16 */
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	17 package org.tmatesoft.hg.repo;
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	18
652 cd77bf51b562 Push: tests. Commit respects phases.new-commit setting. Fix outgoing when changes are not children of common (Issue 47) Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 650 diff changeset	19 import java.util.ArrayList;
432 1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	20 import java.util.Arrays;
652 cd77bf51b562 Push: tests. Commit respects phases.new-commit setting. Fix outgoing when changes are not children of common (Issue 47) Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 650 diff changeset	21 import java.util.BitSet;
432 1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	22 import java.util.Collection;
645 14dac192aa26 Push: phase2 - upload bundle with changes to remote server Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 628 diff changeset	23 import java.util.Collections;
432 1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	24 import java.util.HashSet;
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	25 import java.util.LinkedList;
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	26 import java.util.List;
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	27
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	28 import org.tmatesoft.hg.core.Nodeid;
657 6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 656 diff changeset	29 import org.tmatesoft.hg.internal.ArrayHelper;
656 a937e63b6e02 Performance: rebuild information about branches takes too long (my improvement: 3 times, 11-15 s to less than 4 sec) Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 653 diff changeset	30 import org.tmatesoft.hg.internal.IntMap;
432 1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	31 import org.tmatesoft.hg.repo.Revlog.ParentInspector;
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	32
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	33 /**
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	34 * Helper class to deal with parent-child relationship between revisions <i>en masse</i>.
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	35 * Works in terms of {@link Nodeid nodeids}, there's no need to deal with revision indexes.
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	36 * For a given revision, answers questions like "who's my parent and what are my immediate children".
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	37 *
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	38 * <p>Comes handy when multiple revisions are analyzed and distinct {@link Revlog#parents(int, int[], byte[], byte[])}
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	39 * queries are ineffective.
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	40 *
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	41 * <p>Next code snippet shows typical use:
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	42 * <pre>
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	43 * HgChangelog clog = repo.getChangelog();
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	44 * ParentWalker<HgChangelog> pw = new ParentWalker<HgChangelog>(clog);
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	45 * pw.init();
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	46 *
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	47 * Nodeid me = Nodeid.fromAscii("...");
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	48 * List<Nodei> immediateChildren = pw.directChildren(me);
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	49 * </pre>
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	50 *
668 d25f0324a27a Delete bundle with push/pull changes once command completes successfully. Test for bundle generator Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 663 diff changeset	51 * <p>Note, this map represents a snapshot of repository state at specific point, and is not automatically
d25f0324a27a Delete bundle with push/pull changes once command completes successfully. Test for bundle generator Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 663 diff changeset	52 * updated/refreshed along with repository changes. I.e. any revision committed after this map was initialized
d25f0324a27a Delete bundle with push/pull changes once command completes successfully. Test for bundle generator Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 663 diff changeset	53 * won't be recognized as known.
432 1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	54 *
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	55 * <p> Perhaps, later may add alternative way to access (and reuse) map instance, Revlog#getParentWalker(),
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	56 * that instantiates and initializes ParentWalker, and keep SoftReference to allow its reuse.
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	57 *
433 be697c3e951e Revlog.RevisionMap helper class got promoted as TLC, renamed to HgRevisionMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 432 diff changeset	58 * @see HgRevisionMap
432 1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	59 *
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	60 * @author Artem Tikhomirov
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	61 * @author TMate Software Ltd.
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	62 */
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	63 public final class HgParentChildMap<T extends Revlog> implements ParentInspector {
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	64
646 3b7d51ed4c65 Push: phase3 - update matching remote bookmarks Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 645 diff changeset	65 // IMPORTANT: Nodeid instances shall be shared between all arrays
3b7d51ed4c65 Push: phase3 - update matching remote bookmarks Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 645 diff changeset	66
657 6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 656 diff changeset	67 private final T revlog;
432 1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	68 private Nodeid[] sequential; // natural repository order, childrenOf rely on ordering
657 6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 656 diff changeset	69 private Nodeid[] sorted; // for binary search, just an origin of the actual value in use, the one inside seqWrapper
652 cd77bf51b562 Push: tests. Commit respects phases.new-commit setting. Fix outgoing when changes are not children of common (Issue 47) Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 650 diff changeset	70 private Nodeid[] firstParent; // parents by natural order (i.e. firstParent[A] is parent of revision with index A)
432 1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	71 private Nodeid[] secondParent;
656 a937e63b6e02 Performance: rebuild information about branches takes too long (my improvement: 3 times, 11-15 s to less than 4 sec) Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 653 diff changeset	72 private IntMap<Nodeid> heads;
a937e63b6e02 Performance: rebuild information about branches takes too long (my improvement: 3 times, 11-15 s to less than 4 sec) Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 653 diff changeset	73 private BitSet headsBitSet; // 1 indicates revision got children, != null only during init;
657 6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 656 diff changeset	74 private HgRevisionMap<T> revisionIndexMap;
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 656 diff changeset	75 private ArrayHelper<Nodeid> seqWrapper;
432 1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	76
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	77
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	78 public HgParentChildMap(T owner) {
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	79 revlog = owner;
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	80 }
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	81
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	82 public HgRepository getRepo() {
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	83 return revlog.getRepo();
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	84 }
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	85
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	86 public void next(int revisionNumber, Nodeid revision, int parent1Revision, int parent2Revision, Nodeid nidParent1, Nodeid nidParent2) {
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	87 if (parent1Revision >= revisionNumber \|\| parent2Revision >= revisionNumber) {
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	88 throw new IllegalStateException(); // sanity, revisions are sequential
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	89 }
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	90 int ix = revisionNumber;
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	91 sequential[ix] = sorted[ix] = revision;
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	92 if (parent1Revision != -1) {
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	93 firstParent[ix] = sequential[parent1Revision];
656 a937e63b6e02 Performance: rebuild information about branches takes too long (my improvement: 3 times, 11-15 s to less than 4 sec) Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 653 diff changeset	94 headsBitSet.set(parent1Revision);
432 1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	95 }
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	96 if (parent2Revision != -1) { // revlog of DataAccess.java has p2 set when p1 is -1
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	97 secondParent[ix] = sequential[parent2Revision];
656 a937e63b6e02 Performance: rebuild information about branches takes too long (my improvement: 3 times, 11-15 s to less than 4 sec) Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 653 diff changeset	98 headsBitSet.set(parent2Revision);
432 1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	99 }
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	100 }
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	101
628 6526d8adbc0f Explicit HgRuntimeException to facilitate easy switch from runtime to checked exceptions Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 433 diff changeset	102 /**
672 d2552e6a5af6 Effective update of HgParentChildMap when repository got few revisions added Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 668 diff changeset	103 * Prepare (initialize or update) the map. Once {@link HgParentChildMap} was initialized, it keeps snapshot
d2552e6a5af6 Effective update of HgParentChildMap when repository got few revisions added Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 668 diff changeset	104 * of repository state. New revisions committed to the repository are not visible. To update the map, call
d2552e6a5af6 Effective update of HgParentChildMap when repository got few revisions added Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 668 diff changeset	105 * {@link #init()} once again, it tries to refresh in effective way, and to bring in only relevant changes.
d2552e6a5af6 Effective update of HgParentChildMap when repository got few revisions added Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 668 diff changeset	106 *
628 6526d8adbc0f Explicit HgRuntimeException to facilitate easy switch from runtime to checked exceptions Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 433 diff changeset	107 * @throws HgInvalidControlFileException if failed to access revlog index/data entry. <em>Runtime exception</em>
6526d8adbc0f Explicit HgRuntimeException to facilitate easy switch from runtime to checked exceptions Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 433 diff changeset	108 * @throws HgRuntimeException subclass thereof to indicate other issues with the library. <em>Runtime exception</em>
6526d8adbc0f Explicit HgRuntimeException to facilitate easy switch from runtime to checked exceptions Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 433 diff changeset	109 */
6526d8adbc0f Explicit HgRuntimeException to facilitate easy switch from runtime to checked exceptions Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 433 diff changeset	110 public void init() throws HgRuntimeException {
432 1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	111 final int revisionCount = revlog.getRevisionCount();
672 d2552e6a5af6 Effective update of HgParentChildMap when repository got few revisions added Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 668 diff changeset	112 Nodeid[] oldSequential = null, oldFirstParent = null, oldSecondParent = null, oldSorted = null;
d2552e6a5af6 Effective update of HgParentChildMap when repository got few revisions added Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 668 diff changeset	113 if (sequential != null && sequential.length > 0 && sequential.length < revisionCount) {
d2552e6a5af6 Effective update of HgParentChildMap when repository got few revisions added Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 668 diff changeset	114 int lastRecordedRevIndex = sequential.length-1;
d2552e6a5af6 Effective update of HgParentChildMap when repository got few revisions added Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 668 diff changeset	115 if (sequential[lastRecordedRevIndex].equals(revlog.getRevision(lastRecordedRevIndex))) {
d2552e6a5af6 Effective update of HgParentChildMap when repository got few revisions added Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 668 diff changeset	116 oldSequential = sequential;
d2552e6a5af6 Effective update of HgParentChildMap when repository got few revisions added Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 668 diff changeset	117 oldFirstParent = firstParent;
d2552e6a5af6 Effective update of HgParentChildMap when repository got few revisions added Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 668 diff changeset	118 oldSecondParent = secondParent;
d2552e6a5af6 Effective update of HgParentChildMap when repository got few revisions added Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 668 diff changeset	119 oldSorted = sorted;
d2552e6a5af6 Effective update of HgParentChildMap when repository got few revisions added Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 668 diff changeset	120 // not sure if there's a benefit in keeping sorted. assume quite some of them
d2552e6a5af6 Effective update of HgParentChildMap when repository got few revisions added Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 668 diff changeset	121 // might end up on the same place and thus minimize rearrangements
d2552e6a5af6 Effective update of HgParentChildMap when repository got few revisions added Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 668 diff changeset	122 }
d2552e6a5af6 Effective update of HgParentChildMap when repository got few revisions added Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 668 diff changeset	123 }
432 1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	124 firstParent = new Nodeid[revisionCount];
652 cd77bf51b562 Push: tests. Commit respects phases.new-commit setting. Fix outgoing when changes are not children of common (Issue 47) Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 650 diff changeset	125 // TODO [post 1.1] Branches/merges are less frequent, and most of secondParent would be -1/null, hence
432 1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	126 // IntMap might be better alternative here, but need to carefully analyze (test) whether this brings
656 a937e63b6e02 Performance: rebuild information about branches takes too long (my improvement: 3 times, 11-15 s to less than 4 sec) Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 653 diff changeset	127 // real improvement (IntMap has 2n capacity, and element lookup is log(n) instead of array's constant).
a937e63b6e02 Performance: rebuild information about branches takes too long (my improvement: 3 times, 11-15 s to less than 4 sec) Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 653 diff changeset	128 // FWIW: in cpython's repo, with 70k+ revisions, there are 2618 values in secondParent
432 1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	129 secondParent = new Nodeid[revisionCount];
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	130 //
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	131 sequential = new Nodeid[revisionCount];
672 d2552e6a5af6 Effective update of HgParentChildMap when repository got few revisions added Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 668 diff changeset	132 sorted = new Nodeid[revisionCount];
656 a937e63b6e02 Performance: rebuild information about branches takes too long (my improvement: 3 times, 11-15 s to less than 4 sec) Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 653 diff changeset	133 headsBitSet = new BitSet(revisionCount);
672 d2552e6a5af6 Effective update of HgParentChildMap when repository got few revisions added Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 668 diff changeset	134 if (oldSequential != null) {
d2552e6a5af6 Effective update of HgParentChildMap when repository got few revisions added Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 668 diff changeset	135 assert oldFirstParent.length == oldSequential.length;
d2552e6a5af6 Effective update of HgParentChildMap when repository got few revisions added Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 668 diff changeset	136 assert oldSecondParent.length == oldSequential.length;
d2552e6a5af6 Effective update of HgParentChildMap when repository got few revisions added Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 668 diff changeset	137 assert oldSorted.length == oldSequential.length;
d2552e6a5af6 Effective update of HgParentChildMap when repository got few revisions added Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 668 diff changeset	138 System.arraycopy(oldSequential, 0, sequential, 0, oldSequential.length);
d2552e6a5af6 Effective update of HgParentChildMap when repository got few revisions added Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 668 diff changeset	139 System.arraycopy(oldFirstParent, 0, firstParent, 0, oldFirstParent.length);
d2552e6a5af6 Effective update of HgParentChildMap when repository got few revisions added Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 668 diff changeset	140 System.arraycopy(oldSecondParent, 0, secondParent, 0, oldSecondParent.length);
d2552e6a5af6 Effective update of HgParentChildMap when repository got few revisions added Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 668 diff changeset	141 System.arraycopy(oldSorted, 0, sorted, 0, oldSorted.length);
d2552e6a5af6 Effective update of HgParentChildMap when repository got few revisions added Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 668 diff changeset	142 // restore old heads so that new one are calculated correctly
d2552e6a5af6 Effective update of HgParentChildMap when repository got few revisions added Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 668 diff changeset	143 headsBitSet.set(0, oldSequential.length);
d2552e6a5af6 Effective update of HgParentChildMap when repository got few revisions added Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 668 diff changeset	144 for (int headIndex : heads.keys()) {
d2552e6a5af6 Effective update of HgParentChildMap when repository got few revisions added Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 668 diff changeset	145 headsBitSet.clear(headIndex);
d2552e6a5af6 Effective update of HgParentChildMap when repository got few revisions added Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 668 diff changeset	146 }
d2552e6a5af6 Effective update of HgParentChildMap when repository got few revisions added Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 668 diff changeset	147 }
d2552e6a5af6 Effective update of HgParentChildMap when repository got few revisions added Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 668 diff changeset	148 revlog.indexWalk(oldSequential == null ? 0 : oldSequential.length, revisionCount-1, this);
657 6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 656 diff changeset	149 seqWrapper = new ArrayHelper<Nodeid>(sequential);
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 656 diff changeset	150 // HgRevisionMap doesn't keep sorted, try alternative here.
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 656 diff changeset	151 // reference this.sorted (not only from ArrayHelper) helps to track ownership in hprof/mem dumps
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 656 diff changeset	152 seqWrapper.sort(sorted, false, true);
656 a937e63b6e02 Performance: rebuild information about branches takes too long (my improvement: 3 times, 11-15 s to less than 4 sec) Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 653 diff changeset	153 // no reason to keep BitSet, number of heads is usually small
672 d2552e6a5af6 Effective update of HgParentChildMap when repository got few revisions added Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 668 diff changeset	154 IntMap<Nodeid> _heads = new IntMap<Nodeid>(revisionCount - headsBitSet.cardinality());
656 a937e63b6e02 Performance: rebuild information about branches takes too long (my improvement: 3 times, 11-15 s to less than 4 sec) Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 653 diff changeset	155 int index = 0;
a937e63b6e02 Performance: rebuild information about branches takes too long (my improvement: 3 times, 11-15 s to less than 4 sec) Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 653 diff changeset	156 while (index < sequential.length) {
a937e63b6e02 Performance: rebuild information about branches takes too long (my improvement: 3 times, 11-15 s to less than 4 sec) Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 653 diff changeset	157 index = headsBitSet.nextClearBit(index);
a937e63b6e02 Performance: rebuild information about branches takes too long (my improvement: 3 times, 11-15 s to less than 4 sec) Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 653 diff changeset	158 // nextClearBit(length-1) gives length when bit is set,
a937e63b6e02 Performance: rebuild information about branches takes too long (my improvement: 3 times, 11-15 s to less than 4 sec) Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 653 diff changeset	159 // however, last revision can't be a parent of any other, and
a937e63b6e02 Performance: rebuild information about branches takes too long (my improvement: 3 times, 11-15 s to less than 4 sec) Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 653 diff changeset	160 // the last bit would be always 0, and no AIOOBE
a937e63b6e02 Performance: rebuild information about branches takes too long (my improvement: 3 times, 11-15 s to less than 4 sec) Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 653 diff changeset	161 _heads.put(index, sequential[index]);
a937e63b6e02 Performance: rebuild information about branches takes too long (my improvement: 3 times, 11-15 s to less than 4 sec) Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 653 diff changeset	162 index++;
a937e63b6e02 Performance: rebuild information about branches takes too long (my improvement: 3 times, 11-15 s to less than 4 sec) Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 653 diff changeset	163 }
a937e63b6e02 Performance: rebuild information about branches takes too long (my improvement: 3 times, 11-15 s to less than 4 sec) Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 653 diff changeset	164 headsBitSet = null;
a937e63b6e02 Performance: rebuild information about branches takes too long (my improvement: 3 times, 11-15 s to less than 4 sec) Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 653 diff changeset	165 heads = _heads;
432 1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	166 }
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	167
663 46b56864b483 Pull: phase2 - update phases from remote, fncache with added files. Tests Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 662 diff changeset	168 private static void assertSortedIndex(int x) {
432 1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	169 if (x < 0) {
663 46b56864b483 Pull: phase2 - update phases from remote, fncache with added files. Tests Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 662 diff changeset	170 throw new HgInvalidStateException(String.format("Bad index %d", x));
432 1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	171 }
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	172 }
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	173
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	174 /**
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	175 * Tells whether supplied revision is from the walker's associated revlog.
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	176 * Note, {@link Nodeid#NULL}, although implicitly present as parent of a first revision, is not recognized as known.
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	177 * @param nid revision to check, not <code>null</code>
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	178 * @return <code>true</code> if revision matches any revision in this revlog
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	179 */
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	180 public boolean knownNode(Nodeid nid) {
657 6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 656 diff changeset	181 return seqWrapper.binarySearchSorted(nid) >= 0;
432 1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	182 }
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	183
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	184 /**
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	185 * null if none. only known nodes (as per #knownNode) are accepted as arguments
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	186 */
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	187 public Nodeid firstParent(Nodeid nid) {
657 6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 656 diff changeset	188 int x = seqWrapper.binarySearchSorted(nid);
432 1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	189 assertSortedIndex(x);
657 6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 656 diff changeset	190 int i = seqWrapper.getReverseIndex(x);
432 1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	191 return firstParent[i];
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	192 }
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	193
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	194 // never null, Nodeid.NULL if none known
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	195 public Nodeid safeFirstParent(Nodeid nid) {
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	196 Nodeid rv = firstParent(nid);
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	197 return rv == null ? Nodeid.NULL : rv;
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	198 }
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	199
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	200 public Nodeid secondParent(Nodeid nid) {
657 6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 656 diff changeset	201 int x = seqWrapper.binarySearchSorted(nid);
432 1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	202 assertSortedIndex(x);
657 6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 656 diff changeset	203 int i = seqWrapper.getReverseIndex(x);
432 1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	204 return secondParent[i];
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	205 }
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	206
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	207 public Nodeid safeSecondParent(Nodeid nid) {
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	208 Nodeid rv = secondParent(nid);
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	209 return rv == null ? Nodeid.NULL : rv;
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	210 }
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	211
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	212 public boolean appendParentsOf(Nodeid nid, Collection<Nodeid> c) {
657 6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 656 diff changeset	213 int x = seqWrapper.binarySearchSorted(nid);
432 1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	214 assertSortedIndex(x);
657 6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 656 diff changeset	215 int i = seqWrapper.getReverseIndex(x);
432 1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	216 Nodeid p1 = firstParent[i];
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	217 boolean modified = false;
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	218 if (p1 != null) {
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	219 modified = c.add(p1);
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	220 }
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	221 Nodeid p2 = secondParent[i];
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	222 if (p2 != null) {
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	223 modified = c.add(p2) \|\| modified;
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	224 }
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	225 return modified;
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	226 }
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	227
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	228 // XXX alternative (and perhaps more reliable) approach would be to make a copy of allNodes and remove
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	229 // nodes, their parents and so on.
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	230
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	231 // @return ordered collection of all children rooted at supplied nodes. Nodes shall not be descendants of each other!
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	232 // Nodeids shall belong to this revlog
650 3b275cc2d2aa Push: phase4 - settle local and remote phases, push updated phases regardless of server publishing state, do not push secret changesets Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 646 diff changeset	233 public List<Nodeid> childrenOf(Collection<Nodeid> roots) {
645 14dac192aa26 Push: phase2 - upload bundle with changes to remote server Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 628 diff changeset	234 if (roots.isEmpty()) {
14dac192aa26 Push: phase2 - upload bundle with changes to remote server Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 628 diff changeset	235 return Collections.emptyList();
14dac192aa26 Push: phase2 - upload bundle with changes to remote server Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 628 diff changeset	236 }
432 1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	237 HashSet<Nodeid> parents = new HashSet<Nodeid>();
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	238 LinkedList<Nodeid> result = new LinkedList<Nodeid>();
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	239 int earliestRevision = Integer.MAX_VALUE;
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	240 assert sequential.length == firstParent.length && firstParent.length == secondParent.length;
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	241 // first, find earliest index of roots in question, as there's no sense
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	242 // to check children among nodes prior to branch's root node
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	243 for (Nodeid r : roots) {
657 6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 656 diff changeset	244 int x = seqWrapper.binarySearchSorted(r);
432 1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	245 assertSortedIndex(x);
657 6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 656 diff changeset	246 int i = seqWrapper.getReverseIndex(x);
432 1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	247 if (i < earliestRevision) {
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	248 earliestRevision = i;
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	249 }
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	250 parents.add(sequential[i]); // add canonical instance in hope equals() is bit faster when can do a ==
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	251 }
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	252 for (int i = earliestRevision + 1; i < sequential.length; i++) {
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	253 if (parents.contains(firstParent[i]) \|\| parents.contains(secondParent[i])) {
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	254 parents.add(sequential[i]); // to find next child
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	255 result.add(sequential[i]);
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	256 }
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	257 }
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	258 return result;
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	259 }
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	260
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	261 /**
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	262 * @return revisions that have supplied revision as their immediate parent
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	263 */
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	264 public List<Nodeid> directChildren(Nodeid nid) {
657 6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 656 diff changeset	265 int x = seqWrapper.binarySearchSorted(nid);
432 1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	266 assertSortedIndex(x);
657 6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 656 diff changeset	267 int start = seqWrapper.getReverseIndex(x);
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 656 diff changeset	268 nid = sequential[start]; // canonical instance
653 629a7370554c Tests for recent changes in HgParentChildMap and RepositoryComparator (outgoing to respect drafts and Issue 47) Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 652 diff changeset	269 if (!hasChildren(start)) {
629a7370554c Tests for recent changes in HgParentChildMap and RepositoryComparator (outgoing to respect drafts and Issue 47) Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 652 diff changeset	270 return Collections.emptyList();
629a7370554c Tests for recent changes in HgParentChildMap and RepositoryComparator (outgoing to respect drafts and Issue 47) Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 652 diff changeset	271 }
656 a937e63b6e02 Performance: rebuild information about branches takes too long (my improvement: 3 times, 11-15 s to less than 4 sec) Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 653 diff changeset	272 ArrayList<Nodeid> result = new ArrayList<Nodeid>(5);
432 1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	273 for (int i = start + 1; i < sequential.length; i++) {
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	274 if (nid == firstParent[i] \|\| nid == secondParent[i]) {
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	275 result.add(sequential[i]);
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	276 }
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	277 }
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	278 return result;
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	279 }
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	280
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	281 /**
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	282 * @param nid possibly parent node, shall be {@link #knownNode(Nodeid) known} in this revlog.
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	283 * @return <code>true</code> if there's any node in this revlog that has specified node as one of its parents.
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	284 */
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	285 public boolean hasChildren(Nodeid nid) {
657 6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 656 diff changeset	286 int x = seqWrapper.binarySearchSorted(nid);
432 1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	287 assertSortedIndex(x);
657 6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 656 diff changeset	288 int i = seqWrapper.getReverseIndex(x);
652 cd77bf51b562 Push: tests. Commit respects phases.new-commit setting. Fix outgoing when changes are not children of common (Issue 47) Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 650 diff changeset	289 return hasChildren(i);
432 1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	290 }
659 a5cf64f2e7e4 Poor performance when reading/collecting branch information. Respect new cache location for recent mercurial revisions. Use different algorithm to build branch cache Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 628 diff changeset	291
a5cf64f2e7e4 Poor performance when reading/collecting branch information. Respect new cache location for recent mercurial revisions. Use different algorithm to build branch cache Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 628 diff changeset	292 /**
645 14dac192aa26 Push: phase2 - upload bundle with changes to remote server Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 628 diff changeset	293 * @return all revisions this map knows about
14dac192aa26 Push: phase2 - upload bundle with changes to remote server Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 628 diff changeset	294 */
14dac192aa26 Push: phase2 - upload bundle with changes to remote server Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 628 diff changeset	295 public List<Nodeid> all() {
14dac192aa26 Push: phase2 - upload bundle with changes to remote server Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 628 diff changeset	296 return Arrays.asList(sequential);
14dac192aa26 Push: phase2 - upload bundle with changes to remote server Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 628 diff changeset	297 }
646 3b7d51ed4c65 Push: phase3 - update matching remote bookmarks Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 645 diff changeset	298
3b7d51ed4c65 Push: phase3 - update matching remote bookmarks Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 645 diff changeset	299 /**
3b7d51ed4c65 Push: phase3 - update matching remote bookmarks Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 645 diff changeset	300 * Find out whether a given node is among descendants of another.
3b7d51ed4c65 Push: phase3 - update matching remote bookmarks Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 645 diff changeset	301 *
3b7d51ed4c65 Push: phase3 - update matching remote bookmarks Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 645 diff changeset	302 * @param root revision to check for being (grand-)*parent of a child
3b7d51ed4c65 Push: phase3 - update matching remote bookmarks Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 645 diff changeset	303 * @param wannaBeChild candidate descendant revision
3b7d51ed4c65 Push: phase3 - update matching remote bookmarks Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 645 diff changeset	304 * @return <code>true</code> if <code>wannaBeChild</code> is among children of <code>root</code>
3b7d51ed4c65 Push: phase3 - update matching remote bookmarks Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 645 diff changeset	305 */
3b7d51ed4c65 Push: phase3 - update matching remote bookmarks Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 645 diff changeset	306 public boolean isChild(Nodeid root, Nodeid wannaBeChild) {
657 6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 656 diff changeset	307 int x = seqWrapper.binarySearchSorted(root);
646 3b7d51ed4c65 Push: phase3 - update matching remote bookmarks Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 645 diff changeset	308 assertSortedIndex(x);
657 6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 656 diff changeset	309 final int start = seqWrapper.getReverseIndex(x);
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 656 diff changeset	310 root = sequential[start]; // canonical instance
652 cd77bf51b562 Push: tests. Commit respects phases.new-commit setting. Fix outgoing when changes are not children of common (Issue 47) Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 650 diff changeset	311 if (!hasChildren(start)) {
cd77bf51b562 Push: tests. Commit respects phases.new-commit setting. Fix outgoing when changes are not children of common (Issue 47) Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 650 diff changeset	312 return false; // root got no children at all
cd77bf51b562 Push: tests. Commit respects phases.new-commit setting. Fix outgoing when changes are not children of common (Issue 47) Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 650 diff changeset	313 }
657 6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 656 diff changeset	314 int y = seqWrapper.binarySearchSorted(wannaBeChild);
652 cd77bf51b562 Push: tests. Commit respects phases.new-commit setting. Fix outgoing when changes are not children of common (Issue 47) Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 650 diff changeset	315 if (y < 0) {
cd77bf51b562 Push: tests. Commit respects phases.new-commit setting. Fix outgoing when changes are not children of common (Issue 47) Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 650 diff changeset	316 return false; // not found
646 3b7d51ed4c65 Push: phase3 - update matching remote bookmarks Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 645 diff changeset	317 }
657 6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 656 diff changeset	318 final int end = seqWrapper.getReverseIndex(y);
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 656 diff changeset	319 wannaBeChild = sequential[end]; // canonicalize
652 cd77bf51b562 Push: tests. Commit respects phases.new-commit setting. Fix outgoing when changes are not children of common (Issue 47) Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 650 diff changeset	320 if (end <= start) {
cd77bf51b562 Push: tests. Commit respects phases.new-commit setting. Fix outgoing when changes are not children of common (Issue 47) Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 650 diff changeset	321 return false; // potential child was in repository earlier than root
cd77bf51b562 Push: tests. Commit respects phases.new-commit setting. Fix outgoing when changes are not children of common (Issue 47) Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 650 diff changeset	322 }
646 3b7d51ed4c65 Push: phase3 - update matching remote bookmarks Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 645 diff changeset	323 HashSet<Nodeid> parents = new HashSet<Nodeid>();
3b7d51ed4c65 Push: phase3 - update matching remote bookmarks Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 645 diff changeset	324 parents.add(root);
3b7d51ed4c65 Push: phase3 - update matching remote bookmarks Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 645 diff changeset	325 for (int i = start + 1; i < end; i++) {
3b7d51ed4c65 Push: phase3 - update matching remote bookmarks Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 645 diff changeset	326 if (parents.contains(firstParent[i]) \|\| parents.contains(secondParent[i])) {
3b7d51ed4c65 Push: phase3 - update matching remote bookmarks Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 645 diff changeset	327 parents.add(sequential[i]); // collect ancestors line
3b7d51ed4c65 Push: phase3 - update matching remote bookmarks Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 645 diff changeset	328 }
3b7d51ed4c65 Push: phase3 - update matching remote bookmarks Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 645 diff changeset	329 }
3b7d51ed4c65 Push: phase3 - update matching remote bookmarks Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 645 diff changeset	330 return parents.contains(firstParent[end]) \|\| parents.contains(secondParent[end]);
3b7d51ed4c65 Push: phase3 - update matching remote bookmarks Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 645 diff changeset	331 }
652 cd77bf51b562 Push: tests. Commit respects phases.new-commit setting. Fix outgoing when changes are not children of common (Issue 47) Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 650 diff changeset	332
cd77bf51b562 Push: tests. Commit respects phases.new-commit setting. Fix outgoing when changes are not children of common (Issue 47) Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 650 diff changeset	333 /**
cd77bf51b562 Push: tests. Commit respects phases.new-commit setting. Fix outgoing when changes are not children of common (Issue 47) Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 650 diff changeset	334 * @return elements of this map that do not have a child recorded therein.
cd77bf51b562 Push: tests. Commit respects phases.new-commit setting. Fix outgoing when changes are not children of common (Issue 47) Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 650 diff changeset	335 */
cd77bf51b562 Push: tests. Commit respects phases.new-commit setting. Fix outgoing when changes are not children of common (Issue 47) Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 650 diff changeset	336 public Collection<Nodeid> heads() {
656 a937e63b6e02 Performance: rebuild information about branches takes too long (my improvement: 3 times, 11-15 s to less than 4 sec) Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 653 diff changeset	337 return heads.values();
652 cd77bf51b562 Push: tests. Commit respects phases.new-commit setting. Fix outgoing when changes are not children of common (Issue 47) Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 650 diff changeset	338 }
657 6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 656 diff changeset	339
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 656 diff changeset	340 /**
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 656 diff changeset	341 * @return map of revision to indexes
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 656 diff changeset	342 */
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 656 diff changeset	343 public HgRevisionMap<T> getRevisionMap() {
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 656 diff changeset	344 if (revisionIndexMap == null) {
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 656 diff changeset	345 revisionIndexMap = new HgRevisionMap<T>(revlog);
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 656 diff changeset	346 revisionIndexMap.init(seqWrapper);
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 656 diff changeset	347 }
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 656 diff changeset	348 return revisionIndexMap;
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 656 diff changeset	349 }
679 19f5167c2155 HgParentChildMap: deduce common ancestor functionality Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 672 diff changeset	350
19f5167c2155 HgParentChildMap: deduce common ancestor functionality Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 672 diff changeset	351 /**
19f5167c2155 HgParentChildMap: deduce common ancestor functionality Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 672 diff changeset	352 * @return common ancestor of two revisions
19f5167c2155 HgParentChildMap: deduce common ancestor functionality Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 672 diff changeset	353 */
19f5167c2155 HgParentChildMap: deduce common ancestor functionality Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 672 diff changeset	354 public Nodeid ancestor(Nodeid r1, Nodeid r2) {
19f5167c2155 HgParentChildMap: deduce common ancestor functionality Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 672 diff changeset	355 if (r1.equals(r2)) {
19f5167c2155 HgParentChildMap: deduce common ancestor functionality Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 672 diff changeset	356 return r1;
19f5167c2155 HgParentChildMap: deduce common ancestor functionality Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 672 diff changeset	357 }
19f5167c2155 HgParentChildMap: deduce common ancestor functionality Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 672 diff changeset	358 BitSet a1 = buildAncestors(r1);
19f5167c2155 HgParentChildMap: deduce common ancestor functionality Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 672 diff changeset	359 BitSet a2 = buildAncestors(r2);
19f5167c2155 HgParentChildMap: deduce common ancestor functionality Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 672 diff changeset	360 // BitSet.and() trims to shorter bitset, it's ok as we are not
19f5167c2155 HgParentChildMap: deduce common ancestor functionality Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 672 diff changeset	361 // interested in bits that are part of one bitset only
19f5167c2155 HgParentChildMap: deduce common ancestor functionality Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 672 diff changeset	362 a1.and(a2);
19f5167c2155 HgParentChildMap: deduce common ancestor functionality Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 672 diff changeset	363 final int cardinality = a1.cardinality();
19f5167c2155 HgParentChildMap: deduce common ancestor functionality Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 672 diff changeset	364 if (cardinality == 1) {
19f5167c2155 HgParentChildMap: deduce common ancestor functionality Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 672 diff changeset	365 return sequential[a1.nextSetBit(0)];
19f5167c2155 HgParentChildMap: deduce common ancestor functionality Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 672 diff changeset	366 }
19f5167c2155 HgParentChildMap: deduce common ancestor functionality Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 672 diff changeset	367 assert cardinality > 0; // every revision is child of at least rev0
19f5167c2155 HgParentChildMap: deduce common ancestor functionality Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 672 diff changeset	368 final int length = sequential.length;
19f5167c2155 HgParentChildMap: deduce common ancestor functionality Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 672 diff changeset	369 int index = length / 2;
19f5167c2155 HgParentChildMap: deduce common ancestor functionality Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 672 diff changeset	370 int lastBitSet = -1;
19f5167c2155 HgParentChildMap: deduce common ancestor functionality Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 672 diff changeset	371 do {
19f5167c2155 HgParentChildMap: deduce common ancestor functionality Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 672 diff changeset	372 int nextSetBit = a1.nextSetBit(index);
19f5167c2155 HgParentChildMap: deduce common ancestor functionality Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 672 diff changeset	373 int nextIndex;
19f5167c2155 HgParentChildMap: deduce common ancestor functionality Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 672 diff changeset	374 if (nextSetBit == -1) {
19f5167c2155 HgParentChildMap: deduce common ancestor functionality Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 672 diff changeset	375 assert lastBitSet == -1 \|\| lastBitSet <= index;
19f5167c2155 HgParentChildMap: deduce common ancestor functionality Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 672 diff changeset	376 nextIndex = index - (index - (lastBitSet == -1 ? 0 : lastBitSet)) / 2;
19f5167c2155 HgParentChildMap: deduce common ancestor functionality Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 672 diff changeset	377 } else {
19f5167c2155 HgParentChildMap: deduce common ancestor functionality Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 672 diff changeset	378 lastBitSet = nextSetBit;
19f5167c2155 HgParentChildMap: deduce common ancestor functionality Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 672 diff changeset	379 nextIndex = lastBitSet + (length - lastBitSet) / 2;
19f5167c2155 HgParentChildMap: deduce common ancestor functionality Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 672 diff changeset	380 }
19f5167c2155 HgParentChildMap: deduce common ancestor functionality Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 672 diff changeset	381 if (nextIndex == index) {
19f5167c2155 HgParentChildMap: deduce common ancestor functionality Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 672 diff changeset	382 break;
19f5167c2155 HgParentChildMap: deduce common ancestor functionality Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 672 diff changeset	383 }
19f5167c2155 HgParentChildMap: deduce common ancestor functionality Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 672 diff changeset	384 index = nextIndex;
19f5167c2155 HgParentChildMap: deduce common ancestor functionality Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 672 diff changeset	385 } while (true);
19f5167c2155 HgParentChildMap: deduce common ancestor functionality Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 672 diff changeset	386 if (lastBitSet == -1) {
19f5167c2155 HgParentChildMap: deduce common ancestor functionality Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 672 diff changeset	387 assert false; // likely error in the algorithm above (e.g. can't reach index==0)
19f5167c2155 HgParentChildMap: deduce common ancestor functionality Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 672 diff changeset	388 return sequential[0];
19f5167c2155 HgParentChildMap: deduce common ancestor functionality Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 672 diff changeset	389 }
19f5167c2155 HgParentChildMap: deduce common ancestor functionality Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 672 diff changeset	390 return sequential[lastBitSet];
19f5167c2155 HgParentChildMap: deduce common ancestor functionality Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 672 diff changeset	391 }
652 cd77bf51b562 Push: tests. Commit respects phases.new-commit setting. Fix outgoing when changes are not children of common (Issue 47) Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 650 diff changeset	392
cd77bf51b562 Push: tests. Commit respects phases.new-commit setting. Fix outgoing when changes are not children of common (Issue 47) Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 650 diff changeset	393 private boolean hasChildren(int sequentialIndex) {
656 a937e63b6e02 Performance: rebuild information about branches takes too long (my improvement: 3 times, 11-15 s to less than 4 sec) Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 653 diff changeset	394 return !heads.containsKey(sequentialIndex);
652 cd77bf51b562 Push: tests. Commit respects phases.new-commit setting. Fix outgoing when changes are not children of common (Issue 47) Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 650 diff changeset	395 }
679 19f5167c2155 HgParentChildMap: deduce common ancestor functionality Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 672 diff changeset	396
19f5167c2155 HgParentChildMap: deduce common ancestor functionality Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 672 diff changeset	397 private BitSet buildAncestors(Nodeid nid) {
19f5167c2155 HgParentChildMap: deduce common ancestor functionality Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 672 diff changeset	398 int x = seqWrapper.binarySearchSorted(nid);
19f5167c2155 HgParentChildMap: deduce common ancestor functionality Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 672 diff changeset	399 assertSortedIndex(x);
19f5167c2155 HgParentChildMap: deduce common ancestor functionality Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 672 diff changeset	400 int i = seqWrapper.getReverseIndex(x);
19f5167c2155 HgParentChildMap: deduce common ancestor functionality Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 672 diff changeset	401 BitSet rv = new BitSet(sequential.length);
19f5167c2155 HgParentChildMap: deduce common ancestor functionality Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 672 diff changeset	402 HashSet<Nodeid> ancestors = new HashSet<Nodeid>();
19f5167c2155 HgParentChildMap: deduce common ancestor functionality Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 672 diff changeset	403 ancestors.add(nid);
19f5167c2155 HgParentChildMap: deduce common ancestor functionality Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 672 diff changeset	404 do {
19f5167c2155 HgParentChildMap: deduce common ancestor functionality Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 672 diff changeset	405 if (ancestors.contains(sequential[i])) {
19f5167c2155 HgParentChildMap: deduce common ancestor functionality Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 672 diff changeset	406 rv.set(i);
19f5167c2155 HgParentChildMap: deduce common ancestor functionality Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 672 diff changeset	407 if(firstParent[i] != null) {
19f5167c2155 HgParentChildMap: deduce common ancestor functionality Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 672 diff changeset	408 ancestors.add(firstParent[i]);
19f5167c2155 HgParentChildMap: deduce common ancestor functionality Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 672 diff changeset	409 }
19f5167c2155 HgParentChildMap: deduce common ancestor functionality Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 672 diff changeset	410 if (secondParent[i] != null) {
19f5167c2155 HgParentChildMap: deduce common ancestor functionality Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 672 diff changeset	411 ancestors.add(secondParent[i]);
19f5167c2155 HgParentChildMap: deduce common ancestor functionality Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 672 diff changeset	412 }
19f5167c2155 HgParentChildMap: deduce common ancestor functionality Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 672 diff changeset	413 }
19f5167c2155 HgParentChildMap: deduce common ancestor functionality Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 672 diff changeset	414 i--;
19f5167c2155 HgParentChildMap: deduce common ancestor functionality Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 672 diff changeset	415 } while (i >= 0);
19f5167c2155 HgParentChildMap: deduce common ancestor functionality Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 672 diff changeset	416 return rv;
19f5167c2155 HgParentChildMap: deduce common ancestor functionality Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: 672 diff changeset	417 }
432 1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap Artem Tikhomirov <tikhomirov.artem@gmail.com> parents: diff changeset	418 }

Mercurial > jhg

annotate src/org/tmatesoft/hg/repo/HgParentChildMap.java @ 694:7efabe0cddcf