Mercurial > jhg

annotate src/org/tmatesoft/hg/internal/RevisionLookup.java @ 681:4f93bbc73b64

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Do not instantiate thousands of small arrays(numerous readInt/readLong calls)
author Artem Tikhomirov <tikhomirov.artem@gmail.com>
date Sun, 21 Jul 2013 17:48:05 +0200
parents 6526d8adbc0f
children
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;
628
6526d8adbc0f Explicit HgRuntimeException to facilitate easy switch from runtime to checked exceptions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 600
diff changeset
24 import org.tmatesoft.hg.repo.HgInvalidControlFileException;
6526d8adbc0f Explicit HgRuntimeException to facilitate easy switch from runtime to checked exceptions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 600
diff changeset
25 import org.tmatesoft.hg.repo.HgInvalidRevisionException;
600
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
26 import org.tmatesoft.hg.repo.HgRevisionMap;
628
6526d8adbc0f Explicit HgRuntimeException to facilitate easy switch from runtime to checked exceptions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 600
diff changeset
27 import org.tmatesoft.hg.repo.HgRuntimeException;
600
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
28
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
29 /**
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
30 * 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
31 * 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
32 * 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
33 * 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
34 *
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
35 * @author Artem Tikhomirov
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
36 * @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
37 */
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
38 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
39
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
40 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
41 private int[] nodeidHashes;
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
42
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
43 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
44 assert stream != null;
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
45 content = stream;
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
46 }
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
47
628
6526d8adbc0f Explicit HgRuntimeException to facilitate easy switch from runtime to checked exceptions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 600
diff changeset
48 public static RevisionLookup createFor(RevlogStream stream) throws HgRuntimeException {
600
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
49 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
50 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
51 rv.prepare(revCount);
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
52 if (revCount > 0) {
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
53 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
54 }
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
55 return rv;
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
56 }
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
57
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
58 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
59 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
60 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
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, byte[] 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(nodeid);
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 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
66 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
67 }
628
6526d8adbc0f Explicit HgRuntimeException to facilitate easy switch from runtime to checked exceptions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 600
diff changeset
68 public int findIndex(Nodeid nodeid) throws HgInvalidControlFileException, HgInvalidRevisionException {
600
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
69 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
70 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
71 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
72 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
73 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
74 return i;
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 }
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
77 // 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
78 }
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
79 return BAD_REVISION;
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
80 }
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 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
83 next(revisionIndex, nodeid);
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
84 }
46f29b73e51e Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
85 }