Mercurial > jhg

annotate src/org/tmatesoft/hg/internal/RevisionLookup.java @ 604:c3505001a42a

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Use nodeid reverse lookup speedup cache for #isKnown, if available
author Artem Tikhomirov <tikhomirov.artem@gmail.com>
date Mon, 06 May 2013 18:53:04 +0200
parents 46f29b73e51e
children 6526d8adbc0f
rev   line source
600
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
1 /*
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
2 * Copyright (c) 2013 TMate Software Ltd
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
3 *
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
4 * This program is free software; you can redistribute it and/or modify
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
5 * it under the terms of the GNU General Public License as published by
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
6 * the Free Software Foundation; version 2 of the License.
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
7 *
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
8 * This program is distributed in the hope that it will be useful,
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
11 * GNU General Public License for more details.
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
12 *
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
13 * For information on how to redistribute this software under
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
14 * the terms of a license other than GNU General Public License
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
15 * contact TMate Software at support@hg4j.com
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
16 */
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
17 package org.tmatesoft.hg.internal;
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
18
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
19 import static org.tmatesoft.hg.repo.HgRepository.BAD_REVISION;
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
20
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
21 import java.util.Arrays;
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
22
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
23 import org.tmatesoft.hg.core.Nodeid;
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
24 import org.tmatesoft.hg.repo.HgRevisionMap;
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
25
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
26 /**
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
27 * Lite alternative to {@link HgRevisionMap}, to speed up nodeid to index conversion without consuming too much memory.
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
28 * E.g. for a 100k revisions, {@link HgRevisionMap} consumes 3 * (N * sizeof(int)) for indexes plus 48 bytes per
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
29 * Nodeid instance, total (12+48)*N = 6 mb of memory. {RevisionLookup} instead keeps only Nodeid hashes, (N * sizeof(int) = 400 kb),
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
30 * but is slower in lookup, O(N/2) to find potential match plus disk read operatin (or few, in an unlikely case of hash collisions).
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
31 *
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
32 * @author Artem Tikhomirov
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
33 * @author TMate Software Ltd.
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
34 */
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
35 public class RevisionLookup implements RevlogStream.Inspector {
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
36
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
37 private final RevlogStream content;
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
38 private int[] nodeidHashes;
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
39
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
40 public RevisionLookup(RevlogStream stream) {
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
41 assert stream != null;
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
42 content = stream;
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
43 }
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
44
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
45 public static RevisionLookup createFor(RevlogStream stream) {
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
46 RevisionLookup rv = new RevisionLookup(stream);
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
47 int revCount = stream.revisionCount();
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
48 rv.prepare(revCount);
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
49 if (revCount > 0) {
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
50 stream.iterate(0, revCount - 1, false, rv);
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
51 }
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
52 return rv;
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
53 }
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
54
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
55 public void prepare(int count) {
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
56 nodeidHashes = new int[count];
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
57 Arrays.fill(nodeidHashes, BAD_REVISION);
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
58 }
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
59 public void next(int index, byte[] nodeid) {
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
60 nodeidHashes[index] = Nodeid.hashCode(nodeid);
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
61 }
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
62 public void next(int index, Nodeid nodeid) {
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
63 nodeidHashes[index] = nodeid.hashCode();
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
64 }
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
65 public int findIndex(Nodeid nodeid) {
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
66 final int hash = nodeid.hashCode();
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
67 for (int i = 0; i < nodeidHashes.length; i++) {
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
68 if (nodeidHashes[i] == hash) {
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
69 byte[] nodeidAtI = content.nodeid(i);
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
70 if (nodeid.equalsTo(nodeidAtI)) {
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
71 return i;
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
72 }
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
73 }
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
74 // else: false match (only 4 head bytes matched, continue loop
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
75 }
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
76 return BAD_REVISION;
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
77 }
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
78
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
79 public void next(int revisionIndex, int actualLen, int baseRevision, int linkRevision, int parent1Revision, int parent2Revision, byte[] nodeid, DataAccess data) {
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
80 next(revisionIndex, nodeid);
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
81 }
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
82 }