Mercurial > jhg

comparison src/org/tmatesoft/hg/internal/RevisionLookup.java @ 600:46f29b73e51e

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Utilize RevisionLookup to speed-up getRevisionIndex of both manifest and changelog
author Artem Tikhomirov <tikhomirov.artem@gmail.com>
date Fri, 03 May 2013 17:03:31 +0200
parents
children 6526d8adbc0f
comparison
equal deleted inserted replaced
599:55b7987c1796 600:46f29b73e51e
1 /*
2 * Copyright (c) 2013 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.internal;
18
19 import static org.tmatesoft.hg.repo.HgRepository.BAD_REVISION;
20
21 import java.util.Arrays;
22
23 import org.tmatesoft.hg.core.Nodeid;
24 import org.tmatesoft.hg.repo.HgRevisionMap;
25
26 /**
27 * Lite alternative to {@link HgRevisionMap}, to speed up nodeid to index conversion without consuming too much memory.
28 * E.g. for a 100k revisions, {@link HgRevisionMap} consumes 3 * (N * sizeof(int)) for indexes plus 48 bytes per
29 * Nodeid instance, total (12+48)*N = 6 mb of memory. {RevisionLookup} instead keeps only Nodeid hashes, (N * sizeof(int) = 400 kb),
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).
31 *
32 * @author Artem Tikhomirov
33 * @author TMate Software Ltd.
34 */
35 public class RevisionLookup implements RevlogStream.Inspector {
36
37 private final RevlogStream content;
38 private int[] nodeidHashes;
39
40 public RevisionLookup(RevlogStream stream) {
41 assert stream != null;
42 content = stream;
43 }
44
45 public static RevisionLookup createFor(RevlogStream stream) {
46 RevisionLookup rv = new RevisionLookup(stream);
47 int revCount = stream.revisionCount();
48 rv.prepare(revCount);
49 if (revCount > 0) {
50 stream.iterate(0, revCount - 1, false, rv);
51 }
52 return rv;
53 }
54
55 public void prepare(int count) {
56 nodeidHashes = new int[count];
57 Arrays.fill(nodeidHashes, BAD_REVISION);
58 }
59 public void next(int index, byte[] nodeid) {
60 nodeidHashes[index] = Nodeid.hashCode(nodeid);
61 }
62 public void next(int index, Nodeid nodeid) {
63 nodeidHashes[index] = nodeid.hashCode();
64 }
65 public int findIndex(Nodeid nodeid) {
66 final int hash = nodeid.hashCode();
67 for (int i = 0; i < nodeidHashes.length; i++) {
68 if (nodeidHashes[i] == hash) {
69 byte[] nodeidAtI = content.nodeid(i);
70 if (nodeid.equalsTo(nodeidAtI)) {
71 return i;
72 }
73 }
74 // else: false match (only 4 head bytes matched, continue loop
75 }
76 return BAD_REVISION;
77 }
78
79 public void next(int revisionIndex, int actualLen, int baseRevision, int linkRevision, int parent1Revision, int parent2Revision, byte[] nodeid, DataAccess data) {
80 next(revisionIndex, nodeid);
81 }
82 }