Mercurial > jhg

comparison src/org/tmatesoft/hg/repo/HgRevisionMap.java @ 433:be697c3e951e

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Revlog.RevisionMap helper class got promoted as TLC, renamed to HgRevisionMap
author Artem Tikhomirov <tikhomirov.artem@gmail.com>
date Fri, 30 Mar 2012 16:43:09 +0200
parents
children 6526d8adbc0f
comparison
equal deleted inserted replaced
432:1fc0da631200 433:be697c3e951e
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.BAD_REVISION;
20 import static org.tmatesoft.hg.repo.HgRepository.TIP;
21
22 import java.util.Arrays;
23
24 import org.tmatesoft.hg.core.Nodeid;
25 import org.tmatesoft.hg.internal.ArrayHelper;
26 import org.tmatesoft.hg.repo.Revlog.RevisionInspector;
27
28 /**
29 * Effective int to Nodeid and vice versa translation. It's advised to use this class instead of
30 * multiple {@link Revlog#getRevisionIndex(Nodeid)} calls. Rule of thumb is 20+ calls (given
31 * initialization costs). It's also important to take into account memory consumption, for huge
32 * repositories use of this class may pay off only when accessing greatest fraction of all revisions.
33 *
34 * <p>Next code snippet shows instantiation and sample use:
35 * <pre>
36 * RevisionMap<HgChangelog> clogMap = new RevisionMap<HgChangelog>(clog).init();
37 * RevisionMap<HgDataFile> fileMap = new RevisionMap<HgDataFile>(fileNode).init();
38 *
39 * int fileRevIndex = 0;
40 * Nodeid fileRev = fileMap.revision(fileRevIndex);
41 * int csetRevIndex = fileNode.getChangesetRevisionIndex(fileRevIndex);
42 * Nodeid csetRev = clogMap.revision(localCset);
43 * changesetToNodeidMap.put(csetRev, fileRev);
44 * </pre>
45 *
46 * <p>
47 * {@link Revlog#getRevisionIndex(Nodeid)} with straightforward lookup approach performs O(n/2)
48 * <p>
49 * {@link HgRevisionMap#revisionIndex(Nodeid)} is log(n), plus initialization is O(n) (just once).
50 *
51 * @see HgParentChildMap
52 *
53 * @author Artem Tikhomirov
54 * @author TMate Software Ltd.
55 */
56 public final class HgRevisionMap<T extends Revlog> implements RevisionInspector {
57 /*
58 * in fact, initialization is much slower as it instantiates Nodeids, while #getRevisionIndex
59 * compares directly against byte buffer. Measuring cpython with 70k+ gives 3 times difference (47 vs 171)
60 * for complete changelog iteration.
61 */
62
63 /*
64 * XXX 3 * (x * 4) bytes. Can I do better?
65 * It seems, yes. Don't need to keep sorted, always can emulate it with indirect access to sequential through sorted2natural.
66 * i.e. instead sorted[mid].compareTo(toFind), do sequential[sorted2natural[mid]].compareTo(toFind)
67 */
68 private Nodeid[] sequential; // natural repository order, childrenOf rely on ordering
69 private Nodeid[] sorted; // for binary search
70 private int[] sorted2natural;
71 private final T revlog;
72
73 public HgRevisionMap(T owner) {
74 revlog = owner;
75 }
76
77 public HgRepository getRepo() {
78 return revlog.getRepo();
79 }
80
81 public void next(int revisionIndex, Nodeid revision, int linkedRevision) {
82 sequential[revisionIndex] = sorted[revisionIndex] = revision;
83 }
84
85 /**
86 * @return <code>this</code> for convenience.
87 */
88 public HgRevisionMap<T> init(/*XXX Pool<Nodeid> to reuse nodeids, if possible. */) throws HgInvalidControlFileException{
89 // XXX HgRepository.register((RepoChangeListener) this); // listen to changes in repo, re-init if needed?
90 final int revisionCount = revlog.getRevisionCount();
91 sequential = new Nodeid[revisionCount];
92 sorted = new Nodeid[revisionCount];
93 revlog.indexWalk(0, TIP, this);
94 // next is alternative to Arrays.sort(sorted), and build sorted2natural looking up each element of sequential in sorted.
95 // the way sorted2natural was build is O(n*log n).
96 final ArrayHelper ah = new ArrayHelper();
97 ah.sort(sorted);
98 // note, values in ArrayHelper#getReversed are 1-based indexes, not 0-based
99 sorted2natural = ah.getReverse();
100 return this;
101 }
102
103 public Nodeid revision(int revisionIndex) {
104 return sequential[revisionIndex];
105 }
106 public int revisionIndex(Nodeid revision) {
107 if (revision == null || revision.isNull()) {
108 return BAD_REVISION;
109 }
110 int x = Arrays.binarySearch(sorted, revision);
111 if (x < 0) {
112 return BAD_REVISION;
113 }
114 return sorted2natural[x]-1;
115 }
116 }