Mercurial > jhg

annotate src/org/tmatesoft/hg/repo/HgParentChildMap.java @ 621:99ad1e3a4e4d

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
RevlogStream: be aware of existence (not HgDataFile), facilitate use of an added HgDataFile over a commit; Rollback: be more sensitive about file changes (file size is not enough: write/rollback leaves it intact); tests
author Artem Tikhomirov <tikhomirov.artem@gmail.com>
date Sat, 18 May 2013 22:23:57 +0200
parents be697c3e951e
children 6526d8adbc0f
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 /*
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
2 * Copyright (c) 2011-2012 TMate Software Ltd
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
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
19 import static org.tmatesoft.hg.repo.HgRepository.TIP;
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
20
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
21 import java.util.Arrays;
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;
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
23 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
24 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
25 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
26
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
27 import org.tmatesoft.hg.core.Nodeid;
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.repo.Revlog.ParentInspector;
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
29
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
30 /**
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
31 * 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
32 * 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
33 * 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
34 *
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
35 * <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
36 * queries are ineffective.
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>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
39 * <pre>
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
40 * 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
41 * 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
42 * pw.init();
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
43 *
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
44 * 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
45 * 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
46 * </pre>
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
47 *
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
48 *
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
49 * <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
50 * 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
51 *
433
be697c3e951e Revlog.RevisionMap helper class got promoted as TLC, renamed to HgRevisionMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 432
diff changeset
52 * @see HgRevisionMap
432
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
53 *
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
54 * @author Artem Tikhomirov
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
55 * @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
56 */
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
57 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
58
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 private Nodeid[] sequential; // natural repository order, childrenOf rely on ordering
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
61 private Nodeid[] sorted; // for binary search
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
62 private int[] sorted2natural;
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
63 private Nodeid[] firstParent;
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
64 private Nodeid[] secondParent;
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
65 private final T revlog;
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
66
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
67 // Nodeid instances shall be shared between all arrays
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
68
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
69 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
70 revlog = owner;
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
71 }
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
72
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
73 public HgRepository getRepo() {
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
74 return revlog.getRepo();
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
75 }
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 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
78 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
79 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
80 }
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
81 int ix = revisionNumber;
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
82 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
83 if (parent1Revision != -1) {
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
84 firstParent[ix] = sequential[parent1Revision];
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 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
87 secondParent[ix] = sequential[parent2Revision];
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
88 }
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
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
91 public void init() throws HgInvalidControlFileException {
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
92 final int revisionCount = revlog.getRevisionCount();
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
93 firstParent = new Nodeid[revisionCount];
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
94 // TODO [post 1.0] Branches/merges are less frequent, and most of secondParent would be -1/null, hence
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
95 // IntMap might be better alternative here, but need to carefully analyze (test) whether this brings
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
96 // real improvement (IntMap has 2n capacity, and element lookup is log(n) instead of array's constant)
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
97 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
98 //
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
99 sequential = new Nodeid[revisionCount];
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
100 sorted = new Nodeid[revisionCount];
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
101 revlog.indexWalk(0, TIP, this);
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
102 Arrays.sort(sorted);
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
103 sorted2natural = new int[revisionCount];
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
104 for (int i = 0; i < revisionCount; i++) {
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
105 Nodeid n = sequential[i];
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
106 int x = Arrays.binarySearch(sorted, n);
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
107 assertSortedIndex(x);
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
108 sorted2natural[x] = i;
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
109 }
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
110 }
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
111
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
112 private void assertSortedIndex(int x) {
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
113 if (x < 0) {
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
114 throw new HgInvalidStateException(String.format("Bad index", x));
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
115 }
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
116 }
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
117
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
118 /**
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
119 * 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
120 * 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
121 * @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
122 * @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
123 */
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
124 public boolean knownNode(Nodeid nid) {
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
125 return Arrays.binarySearch(sorted, nid) >= 0;
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
126 }
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
127
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
128 /**
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
129 * 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
130 */
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
131 public Nodeid firstParent(Nodeid nid) {
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
132 int x = Arrays.binarySearch(sorted, nid);
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
133 assertSortedIndex(x);
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
134 int i = sorted2natural[x];
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
135 return firstParent[i];
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
136 }
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
137
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
138 // 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
139 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
140 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
141 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
142 }
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
143
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
144 public Nodeid secondParent(Nodeid nid) {
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
145 int x = Arrays.binarySearch(sorted, nid);
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
146 assertSortedIndex(x);
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
147 int i = sorted2natural[x];
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
148 return secondParent[i];
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
149 }
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
150
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
151 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
152 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
153 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
154 }
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
155
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
156 public boolean appendParentsOf(Nodeid nid, Collection<Nodeid> c) {
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
157 int x = Arrays.binarySearch(sorted, nid);
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
158 assertSortedIndex(x);
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
159 int i = sorted2natural[x];
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
160 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
161 boolean modified = false;
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
162 if (p1 != null) {
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
163 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
164 }
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
165 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
166 if (p2 != null) {
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
167 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
168 }
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
169 return modified;
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
170 }
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 // 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
173 // 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
174
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
175 // @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
176 // Nodeids shall belong to this revlog
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
177 public List<Nodeid> childrenOf(List<Nodeid> roots) {
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
178 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
179 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
180 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
181 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
182 // 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
183 // 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
184 for (Nodeid r : roots) {
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
185 int x = Arrays.binarySearch(sorted, r);
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
186 assertSortedIndex(x);
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
187 int i = sorted2natural[x];
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
188 if (i < earliestRevision) {
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
189 earliestRevision = i;
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
190 }
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
191 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
192 }
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
193 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
194 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
195 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
196 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
197 }
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 return result;
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
200 }
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
201
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
202 /**
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
203 * @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
204 */
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
205 public List<Nodeid> directChildren(Nodeid nid) {
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
206 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
207 int x = Arrays.binarySearch(sorted, nid);
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
208 assertSortedIndex(x);
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
209 nid = sorted[x]; // canonical instance
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
210 int start = sorted2natural[x];
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
211 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
212 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
213 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
214 }
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
215 }
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
216 return result;
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
217 }
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
218
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
219 /**
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
220 * @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
221 * @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
222 */
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
223 public boolean hasChildren(Nodeid nid) {
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
224 int x = Arrays.binarySearch(sorted, nid);
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
225 assertSortedIndex(x);
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
226 int i = sorted2natural[x];
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
227 assert firstParent.length == secondParent.length; // just in case later I implement sparse array for secondParent
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
228 assert firstParent.length == sequential.length;
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
229 // to use == instead of equals, take the same Nodeid instance we used to fill all the arrays.
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
230 final Nodeid canonicalNode = sequential[i];
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
231 i++; // no need to check node itself. child nodes may appear in sequential only after revision in question
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
232 for (; 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
233 // TODO [post 1.0] likely, not very effective.
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
234 // May want to optimize it with another (Tree|Hash)Set, created on demand on first use,
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
235 // however, need to be careful with memory usage
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
236 if (firstParent[i] == canonicalNode || secondParent[i] == canonicalNode) {
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
237 return true;
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
238 }
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
239 }
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
240 return false;
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
241 }
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
242 }