annotate src/org/tmatesoft/hg/internal/IntVector.java @ 304:85b8efde5586

Use memory-friendly set implementation to canonicalize filenames and nodeids
author Artem Tikhomirov <tikhomirov.artem@gmail.com>
date Wed, 21 Sep 2011 18:26:16 +0200
parents b11f6a08f748
children a674b8590362
rev   line source
288
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
1 /*
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
2 * Copyright (c) 2011 TMate Software Ltd
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
3 *
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
4 * This program is free software; you can redistribute it and/or modify
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
5 * it under the terms of the GNU General Public License as published by
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
6 * the Free Software Foundation; version 2 of the License.
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
7 *
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
8 * This program is distributed in the hope that it will be useful,
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
11 * GNU General Public License for more details.
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
12 *
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
13 * For information on how to redistribute this software under
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
14 * the terms of a license other than GNU General Public License
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
15 * contact TMate Software at support@hg4j.com
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
16 */
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
17 package org.tmatesoft.hg.internal;
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
18
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
19 /**
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
20 *
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
21 * @author Artem Tikhomirov
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
22 * @author TMate Software Ltd.
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
23 */
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
24 class IntVector {
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
25
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
26 private int[] data;
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
27 private final int increment;
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
28 private int count;
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
29
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
30
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
31 public IntVector() {
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
32 this(16, -1);
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
33 }
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
34
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
35 // increment == -1: grow by power of two.
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
36 // increment == 0: no resize (Exception will be thrown on attempt to add past capacity)
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
37 public IntVector(int initialCapacity, int increment) {
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
38 data = new int[initialCapacity];
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
39 this.increment = increment;
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
40 }
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
41
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
42 public void add(int v) {
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
43 if (count == data.length) {
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
44 grow();
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
45 }
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
46 data[count++] = v;
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
47 }
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
48
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
49 public int get(int i) {
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
50 if (i < 0 || i >= count) {
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
51 throw new IndexOutOfBoundsException(String.format("Index: %d, size: %d", i, count));
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
52 }
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
53 return data[i];
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
54 }
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
55
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
56 public int size() {
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
57 return count;
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
58 }
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
59
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
60 public int[] toArray() {
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
61 int[] rv = new int[count];
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
62 System.arraycopy(data, 0, rv, 0, count);
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
63 return rv;
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
64 }
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
65
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
66 /**
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
67 * Use only when this instance won't be used any longer
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
68 */
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
69 @Experimental
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
70 int[] toArray(boolean internalIfSizeMatchCapacity) {
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
71 if (count == data.length) {
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
72 return data;
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
73 }
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
74 return toArray();
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
75 }
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
76
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
77 private void grow() {
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
78 if (increment == 0) {
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
79 // throw specific exception right away
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
80 return;
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
81 }
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
82 int newCapacity = increment < 0 ? data.length << 1 : data.length + increment;
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
83 assert newCapacity > 0 && newCapacity != data.length : newCapacity;
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
84 int[] newData = new int[newCapacity];
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
85 System.arraycopy(data, 0, newData, 0, count);
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
86 data = newData;
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
87 }
b11f6a08f748 Avoid boxing int values and list resizes on revlog read
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
88 }