Mercurial > hg4j

annotate src/org/tmatesoft/hg/repo/HgParentChildMap.java @ 675:a20121a2bba6

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Respect default range (0..tip)
author Artem Tikhomirov <tikhomirov.artem@gmail.com>
date Thu, 18 Jul 2013 18:02:36 +0200
parents d2552e6a5af6
children 19f5167c2155
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&lt;HgChangelog> pw = new ParentWalker&lt;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 }
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
350
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
351 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
352 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
353 }
432
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
354 }