Mercurial > jhg

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

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Revlog.ParentWalker helper class got promoted as TLC, renamed to HgParentChildMap
author Artem Tikhomirov <tikhomirov.artem@gmail.com>
date Fri, 30 Mar 2012 16:22:51 +0200
parents
children be697c3e951e
comparison
equal deleted inserted replaced
431:12f668401613 432:1fc0da631200
1 /*
2 * Copyright (c) 2011-2012 TMate Software Ltd
3 *
4 * This program is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation; version 2 of the License.
7 *
8 * This program is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 * GNU General Public License for more details.
12 *
13 * For information on how to redistribute this software under
14 * the terms of a license other than GNU General Public License
15 * contact TMate Software at support@hg4j.com
16 */
17 package org.tmatesoft.hg.repo;
18
19 import static org.tmatesoft.hg.repo.HgRepository.TIP;
20
21 import java.util.Arrays;
22 import java.util.Collection;
23 import java.util.HashSet;
24 import java.util.LinkedList;
25 import java.util.List;
26
27 import org.tmatesoft.hg.core.Nodeid;
28 import org.tmatesoft.hg.repo.Revlog.ParentInspector;
29
30 /**
31 * Helper class to deal with parent-child relationship between revisions <i>en masse</i>.
32 * Works in terms of {@link Nodeid nodeids}, there's no need to deal with revision indexes.
33 * For a given revision, answers questions like "who's my parent and what are my immediate children".
34 *
35 * <p>Comes handy when multiple revisions are analyzed and distinct {@link Revlog#parents(int, int[], byte[], byte[])}
36 * queries are ineffective.
37 *
38 * <p>Next code snippet shows typical use:
39 * <pre>
40 * HgChangelog clog = repo.getChangelog();
41 * ParentWalker&lt;HgChangelog> pw = new ParentWalker&lt;HgChangelog>(clog);
42 * pw.init();
43 *
44 * Nodeid me = Nodeid.fromAscii("...");
45 * List<Nodei> immediateChildren = pw.directChildren(me);
46 * </pre>
47 *
48 *
49 * <p> Perhaps, later may add alternative way to access (and reuse) map instance, Revlog#getParentWalker(),
50 * that instantiates and initializes ParentWalker, and keep SoftReference to allow its reuse.
51 *
52 * @see Revlog.RevisionMap
53 *
54 * @author Artem Tikhomirov
55 * @author TMate Software Ltd.
56 */
57 public final class HgParentChildMap<T extends Revlog> implements ParentInspector {
58
59
60 private Nodeid[] sequential; // natural repository order, childrenOf rely on ordering
61 private Nodeid[] sorted; // for binary search
62 private int[] sorted2natural;
63 private Nodeid[] firstParent;
64 private Nodeid[] secondParent;
65 private final T revlog;
66
67 // Nodeid instances shall be shared between all arrays
68
69 public HgParentChildMap(T owner) {
70 revlog = owner;
71 }
72
73 public HgRepository getRepo() {
74 return revlog.getRepo();
75 }
76
77 public void next(int revisionNumber, Nodeid revision, int parent1Revision, int parent2Revision, Nodeid nidParent1, Nodeid nidParent2) {
78 if (parent1Revision >= revisionNumber || parent2Revision >= revisionNumber) {
79 throw new IllegalStateException(); // sanity, revisions are sequential
80 }
81 int ix = revisionNumber;
82 sequential[ix] = sorted[ix] = revision;
83 if (parent1Revision != -1) {
84 firstParent[ix] = sequential[parent1Revision];
85 }
86 if (parent2Revision != -1) { // revlog of DataAccess.java has p2 set when p1 is -1
87 secondParent[ix] = sequential[parent2Revision];
88 }
89 }
90
91 public void init() throws HgInvalidControlFileException {
92 final int revisionCount = revlog.getRevisionCount();
93 firstParent = new Nodeid[revisionCount];
94 // TODO [post 1.0] Branches/merges are less frequent, and most of secondParent would be -1/null, hence
95 // IntMap might be better alternative here, but need to carefully analyze (test) whether this brings
96 // real improvement (IntMap has 2n capacity, and element lookup is log(n) instead of array's constant)
97 secondParent = new Nodeid[revisionCount];
98 //
99 sequential = new Nodeid[revisionCount];
100 sorted = new Nodeid[revisionCount];
101 revlog.indexWalk(0, TIP, this);
102 Arrays.sort(sorted);
103 sorted2natural = new int[revisionCount];
104 for (int i = 0; i < revisionCount; i++) {
105 Nodeid n = sequential[i];
106 int x = Arrays.binarySearch(sorted, n);
107 assertSortedIndex(x);
108 sorted2natural[x] = i;
109 }
110 }
111
112 private void assertSortedIndex(int x) {
113 if (x < 0) {
114 throw new HgInvalidStateException(String.format("Bad index", x));
115 }
116 }
117
118 /**
119 * Tells whether supplied revision is from the walker's associated revlog.
120 * Note, {@link Nodeid#NULL}, although implicitly present as parent of a first revision, is not recognized as known.
121 * @param nid revision to check, not <code>null</code>
122 * @return <code>true</code> if revision matches any revision in this revlog
123 */
124 public boolean knownNode(Nodeid nid) {
125 return Arrays.binarySearch(sorted, nid) >= 0;
126 }
127
128 /**
129 * null if none. only known nodes (as per #knownNode) are accepted as arguments
130 */
131 public Nodeid firstParent(Nodeid nid) {
132 int x = Arrays.binarySearch(sorted, nid);
133 assertSortedIndex(x);
134 int i = sorted2natural[x];
135 return firstParent[i];
136 }
137
138 // never null, Nodeid.NULL if none known
139 public Nodeid safeFirstParent(Nodeid nid) {
140 Nodeid rv = firstParent(nid);
141 return rv == null ? Nodeid.NULL : rv;
142 }
143
144 public Nodeid secondParent(Nodeid nid) {
145 int x = Arrays.binarySearch(sorted, nid);
146 assertSortedIndex(x);
147 int i = sorted2natural[x];
148 return secondParent[i];
149 }
150
151 public Nodeid safeSecondParent(Nodeid nid) {
152 Nodeid rv = secondParent(nid);
153 return rv == null ? Nodeid.NULL : rv;
154 }
155
156 public boolean appendParentsOf(Nodeid nid, Collection<Nodeid> c) {
157 int x = Arrays.binarySearch(sorted, nid);
158 assertSortedIndex(x);
159 int i = sorted2natural[x];
160 Nodeid p1 = firstParent[i];
161 boolean modified = false;
162 if (p1 != null) {
163 modified = c.add(p1);
164 }
165 Nodeid p2 = secondParent[i];
166 if (p2 != null) {
167 modified = c.add(p2) || modified;
168 }
169 return modified;
170 }
171
172 // XXX alternative (and perhaps more reliable) approach would be to make a copy of allNodes and remove
173 // nodes, their parents and so on.
174
175 // @return ordered collection of all children rooted at supplied nodes. Nodes shall not be descendants of each other!
176 // Nodeids shall belong to this revlog
177 public List<Nodeid> childrenOf(List<Nodeid> roots) {
178 HashSet<Nodeid> parents = new HashSet<Nodeid>();
179 LinkedList<Nodeid> result = new LinkedList<Nodeid>();
180 int earliestRevision = Integer.MAX_VALUE;
181 assert sequential.length == firstParent.length && firstParent.length == secondParent.length;
182 // first, find earliest index of roots in question, as there's no sense
183 // to check children among nodes prior to branch's root node
184 for (Nodeid r : roots) {
185 int x = Arrays.binarySearch(sorted, r);
186 assertSortedIndex(x);
187 int i = sorted2natural[x];
188 if (i < earliestRevision) {
189 earliestRevision = i;
190 }
191 parents.add(sequential[i]); // add canonical instance in hope equals() is bit faster when can do a ==
192 }
193 for (int i = earliestRevision + 1; i < sequential.length; i++) {
194 if (parents.contains(firstParent[i]) || parents.contains(secondParent[i])) {
195 parents.add(sequential[i]); // to find next child
196 result.add(sequential[i]);
197 }
198 }
199 return result;
200 }
201
202 /**
203 * @return revisions that have supplied revision as their immediate parent
204 */
205 public List<Nodeid> directChildren(Nodeid nid) {
206 LinkedList<Nodeid> result = new LinkedList<Nodeid>();
207 int x = Arrays.binarySearch(sorted, nid);
208 assertSortedIndex(x);
209 nid = sorted[x]; // canonical instance
210 int start = sorted2natural[x];
211 for (int i = start + 1; i < sequential.length; i++) {
212 if (nid == firstParent[i] || nid == secondParent[i]) {
213 result.add(sequential[i]);
214 }
215 }
216 return result;
217 }
218
219 /**
220 * @param nid possibly parent node, shall be {@link #knownNode(Nodeid) known} in this revlog.
221 * @return <code>true</code> if there's any node in this revlog that has specified node as one of its parents.
222 */
223 public boolean hasChildren(Nodeid nid) {
224 int x = Arrays.binarySearch(sorted, nid);
225 assertSortedIndex(x);
226 int i = sorted2natural[x];
227 assert firstParent.length == secondParent.length; // just in case later I implement sparse array for secondParent
228 assert firstParent.length == sequential.length;
229 // to use == instead of equals, take the same Nodeid instance we used to fill all the arrays.
230 final Nodeid canonicalNode = sequential[i];
231 i++; // no need to check node itself. child nodes may appear in sequential only after revision in question
232 for (; i < sequential.length; i++) {
233 // TODO [post 1.0] likely, not very effective.
234 // May want to optimize it with another (Tree|Hash)Set, created on demand on first use,
235 // however, need to be careful with memory usage
236 if (firstParent[i] == canonicalNode || secondParent[i] == canonicalNode) {
237 return true;
238 }
239 }
240 return false;
241 }
242 }