Mercurial > jhg

annotate src/org/tmatesoft/hg/repo/HgParentChildMap.java @ 659:a5cf64f2e7e4 smartgit-4.6

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Poor performance when reading/collecting branch information. Respect new cache location for recent mercurial revisions. Use different algorithm to build branch cache
author Artem Tikhomirov <tikhomirov.artem@gmail.com>
date Fri, 05 Jul 2013 20:42:45 +0200
parents 6526d8adbc0f
children af5223b86dd3
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
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
628
6526d8adbc0f Explicit HgRuntimeException to facilitate easy switch from runtime to checked exceptions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 433
diff changeset
91 /**
6526d8adbc0f Explicit HgRuntimeException to facilitate easy switch from runtime to checked exceptions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 433
diff changeset
92 * Prepare the map
6526d8adbc0f Explicit HgRuntimeException to facilitate easy switch from runtime to checked exceptions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 433
diff changeset
93 * @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
94 * @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
95 */
6526d8adbc0f Explicit HgRuntimeException to facilitate easy switch from runtime to checked exceptions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 433
diff changeset
96 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
97 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
98 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
99 // 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
100 // 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
101 // 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
102 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
103 //
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
104 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
105 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
106 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
107 Arrays.sort(sorted);
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
108 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
109 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
110 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
111 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
112 assertSortedIndex(x);
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
113 sorted2natural[x] = i;
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
114 }
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 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
118 if (x < 0) {
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
119 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
120 }
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
121 }
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
122
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 * 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
125 * 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
126 * @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
127 * @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
128 */
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
129 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
130 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
131 }
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
132
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
133 /**
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
134 * 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
135 */
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
136 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
137 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
138 assertSortedIndex(x);
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
139 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
140 return firstParent[i];
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
141 }
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 // 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
144 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
145 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
146 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
147 }
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
148
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
149 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
150 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
151 assertSortedIndex(x);
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
152 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
153 return secondParent[i];
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 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
157 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
158 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
159 }
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
160
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
161 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
162 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
163 assertSortedIndex(x);
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
164 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
165 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
166 boolean modified = false;
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
167 if (p1 != null) {
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
168 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
169 }
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
170 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
171 if (p2 != null) {
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
172 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
173 }
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
174 return modified;
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
175 }
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
176
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
177 // 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
178 // 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
179
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
180 // @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
181 // 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
182 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
183 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
184 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
185 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
186 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
187 // 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
188 // 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
189 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
190 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
191 assertSortedIndex(x);
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
192 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
193 if (i < earliestRevision) {
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
194 earliestRevision = i;
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
195 }
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
196 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
197 }
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
198 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
199 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
200 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
201 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
202 }
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
203 }
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
204 return result;
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 /**
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
208 * @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
209 */
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
210 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
211 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
212 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
213 assertSortedIndex(x);
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
214 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
215 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
216 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
217 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
218 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
219 }
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 return result;
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
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 * @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
226 * @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
227 */
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
228 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
229 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
230 assertSortedIndex(x);
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
231 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
232 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
233 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
234 // 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
235 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
236 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
237 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
238 // 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
239 // 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
240 // 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
241 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
242 return true;
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
243 }
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
244 }
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
245 return false;
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
246 }
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
247
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
248 /**
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
249 * Find out whether a given node is among descendants of another.
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
250 *
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
251 * @param root revision to check for being (grand-)*parent of a child
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
252 * @param wannaBeChild candidate descendant revision
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
253 * @return <code>true</code> if <code>wannaBeChild</code> is among children of <code>root</code>
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
254 */
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
255 public boolean isChild(Nodeid root, Nodeid wannaBeChild) {
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
256 int x = Arrays.binarySearch(sorted, root);
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
257 assertSortedIndex(x);
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
258 root = sorted[x]; // canonical instance
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
259 final int start = sorted2natural[x];
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
260 int y = Arrays.binarySearch(sorted, wannaBeChild);
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
261 if (y < 0) {
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
262 return false; // not found
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
263 }
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
264 wannaBeChild = sorted[y]; // canonicalize
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
265 final int end = sorted2natural[y];
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
266 if (end <= start) {
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
267 return false; // potential child was in repository earlier than root
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
268 }
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
269 HashSet<Nodeid> parents = new HashSet<Nodeid>();
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
270 parents.add(root);
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
271 for (int i = start + 1; i < end; i++) {
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
272 if (parents.contains(firstParent[i]) || parents.contains(secondParent[i])) {
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
273 parents.add(sequential[i]); // collect ancestors line
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
274 }
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
275 }
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
276 return parents.contains(firstParent[end]) || parents.contains(secondParent[end]);
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
277 }
432
1fc0da631200 Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
278 }