Mercurial > jhg

annotate src/org/tmatesoft/hg/internal/IntMap.java @ 686:f1f095e42555

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Annotated file is not always changed in the latest changeset, need to find out last changest it was changed at (iow, diffed to with BlameHelper)
author Artem Tikhomirov <tikhomirov.artem@gmail.com>
date Thu, 25 Jul 2013 22:12:14 +0200
parents d2552e6a5af6
children
rev   line source
276
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
1 /*
551
4ea0351ca878 Better (precise) name for diff facility, tests
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 471
diff changeset
2 * Copyright (c) 2011-2013 TMate Software Ltd
276
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
3 *
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
4 * This program is free software; you can redistribute it and/or modify
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
5 * it under the terms of the GNU General Public License as published by
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
6 * the Free Software Foundation; version 2 of the License.
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
7 *
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
8 * This program is distributed in the hope that it will be useful,
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
11 * GNU General Public License for more details.
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
12 *
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
13 * For information on how to redistribute this software under
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
14 * the terms of a license other than GNU General Public License
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
15 * contact TMate Software at support@hg4j.com
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
16 */
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
17 package org.tmatesoft.hg.internal;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
18
551
4ea0351ca878 Better (precise) name for diff facility, tests
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 471
diff changeset
19 import java.util.Arrays;
656
a937e63b6e02 Performance: rebuild information about branches takes too long (my improvement: 3 times, 11-15 s to less than 4 sec)
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 613
diff changeset
20 import java.util.Collection;
415
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
21 import java.util.Iterator;
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
22 import java.util.Map;
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
23 import java.util.Map.Entry;
276
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
24 import java.util.NoSuchElementException;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
25
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
26
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
27 /**
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
28 * Map implementation that uses plain int keys and performs with log n effectiveness.
448
2e402c12ebc6 Issue 31: Revlog#walk() fails with AIOOBE when start > 0
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
29 * May contain null values
276
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
30 *
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
31 * @author Artem Tikhomirov
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
32 * @author TMate Software Ltd.
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
33 */
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
34 public class IntMap<V> {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
35
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
36 private int[] keys;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
37 private Object[] values;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
38 private int size;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
39
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
40 public IntMap(int size) {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
41 keys = new int[size <= 0 ? 16 : size];
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
42 values = new Object[keys.length];
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
43 }
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
44
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
45 public int size() {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
46 return size;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
47 }
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
48
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
49 public int firstKey() {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
50 if (size == 0) {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
51 throw new NoSuchElementException();
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
52 }
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
53 return keys[0];
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
54 }
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
55
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
56 public int lastKey() {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
57 if (size == 0) {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
58 throw new NoSuchElementException();
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
59 }
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
60 return keys[size-1];
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
61 }
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
62
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
63 public void trimToSize() {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
64 if (size < keys.length) {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
65 int[] newKeys = new int[size];
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
66 Object[] newValues = new Object[size];
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
67 System.arraycopy(keys, 0, newKeys, 0, size);
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
68 System.arraycopy(values, 0, newValues, 0, size);
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
69 keys = newKeys;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
70 values = newValues;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
71 }
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
72 }
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
73
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
74 public void put(int key, V value) {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
75 int ix = binarySearch(keys, size, key);
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
76 if (ix < 0) {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
77 final int insertPoint = -ix - 1;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
78 assert insertPoint <= size; // can't be greater, provided binarySearch didn't malfunction.
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
79 if (size == keys.length) {
278
55fad5e0e98b Ensure capacity grows regardless of initial map size. Separate unit test
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 276
diff changeset
80 int capInc = size >>> 2; // +25%
55fad5e0e98b Ensure capacity grows regardless of initial map size. Separate unit test
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 276
diff changeset
81 int newCapacity = size + (capInc < 2 ? 2 : capInc) ;
276
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
82 int[] newKeys = new int[newCapacity];
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
83 Object[] newValues = new Object[newCapacity];
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
84 System.arraycopy(keys, 0, newKeys, 0, insertPoint);
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
85 System.arraycopy(keys, insertPoint, newKeys, insertPoint+1, keys.length - insertPoint);
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
86 System.arraycopy(values, 0, newValues, 0, insertPoint);
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
87 System.arraycopy(values, insertPoint, newValues, insertPoint+1, values.length - insertPoint);
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
88 keys = newKeys;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
89 values = newValues;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
90 } else {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
91 // arrays got enough capacity
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
92 if (insertPoint != size) {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
93 System.arraycopy(keys, insertPoint, keys, insertPoint+1, keys.length - insertPoint - 1);
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
94 System.arraycopy(values, insertPoint, values, insertPoint+1, values.length - insertPoint - 1);
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
95 }
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
96 // else insertPoint is past known elements, no need to copy arrays
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
97 }
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
98 keys[insertPoint] = key;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
99 values[insertPoint] = value;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
100 size++;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
101 } else {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
102 values[ix] = value;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
103 }
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
104 }
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
105
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
106 public boolean containsKey(int key) {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
107 return binarySearch(keys, size, key) >= 0;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
108 }
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
109
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
110 @SuppressWarnings("unchecked")
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
111 public V get(int key) {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
112 int ix = binarySearch(keys, size, key);
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
113 if (ix >= 0) {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
114 return (V) values[ix];
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
115 }
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
116 return null;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
117 }
281
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
118
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
119 public void remove(int key) {
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
120 int ix = binarySearch(keys, size, key);
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
121 if (ix >= 0) {
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
122 if (ix <= size - 1) {
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
123 System.arraycopy(keys, ix+1, keys, ix, size - ix - 1);
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
124 System.arraycopy(values, ix+1, values, ix, size - ix - 1);
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
125 } // if ix points to last element, no reason to attempt a copy
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
126 size--;
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
127 keys[size] = 0;
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
128 values[size] = null;
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
129 }
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
130 }
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
131
551
4ea0351ca878 Better (precise) name for diff facility, tests
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 471
diff changeset
132 public void clear() {
4ea0351ca878 Better (precise) name for diff facility, tests
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 471
diff changeset
133 Arrays.fill(values, 0, size, null); // do not keep the references
4ea0351ca878 Better (precise) name for diff facility, tests
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 471
diff changeset
134 size = 0;
4ea0351ca878 Better (precise) name for diff facility, tests
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 471
diff changeset
135 }
4ea0351ca878 Better (precise) name for diff facility, tests
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 471
diff changeset
136
281
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
137 /**
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
138 * Forget first N entries (in natural order) in the map.
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
139 */
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
140 public void removeFromStart(int count) {
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
141 if (count > 0 && count <= size) {
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
142 if (count < size) {
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
143 System.arraycopy(keys, count, keys, 0, size - count);
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
144 System.arraycopy(values, count, values, 0, size - count);
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
145 }
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
146 for (int i = size - count; i < size; i++) {
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
147 keys[i] = 0;
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
148 values[i] = null;
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
149 }
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
150 size -= count;
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
151 }
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
152 }
415
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
153
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
154 // document iterator is non-modifying (neither remove() nor setValue() works)
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
155 // perhaps, may also implement Iterable<Map.Entry> to use nice for()
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
156 public Iterator<Map.Entry<Integer, V>> entryIterator() {
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
157 class E implements Map.Entry<Integer, V> {
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
158 private Integer key;
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
159 private V value;
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
160
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
161 public Integer getKey() {
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
162 return key;
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
163 }
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
164
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
165 public V getValue() {
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
166 return value;
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
167 }
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
168
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
169 public V setValue(V value) {
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
170 throw new UnsupportedOperationException();
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
171 }
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
172
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
173 void init(Integer k, V v) {
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
174 key = k;
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
175 value = v;
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
176 }
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
177 }
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
178
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
179 return new Iterator<Map.Entry<Integer, V>>() {
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
180 private int i = 0;
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
181 private final E entry = new E();
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
182 private final int _size;
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
183 private final int[] _keys;
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
184 private final Object[] _values;
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
185
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
186 {
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
187 _size = IntMap.this.size;
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
188 _keys = IntMap.this.keys;
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
189 _values = IntMap.this.values;
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
190 }
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
191
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
192 public boolean hasNext() {
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
193 return i < _size;
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
194 }
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
195
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
196 public Entry<Integer, V> next() {
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
197 if (i >= _size) {
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
198 throw new NoSuchElementException();
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
199 }
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
200 @SuppressWarnings("unchecked")
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
201 V val = (V) _values[i];
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
202 entry.init(_keys[i], val);
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
203 i++;
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
204 return entry;
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
205 }
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
206
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
207 public void remove() {
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
208 throw new UnsupportedOperationException();
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
209 }
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
210 };
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
211 }
281
81e9a3c9bafe Utilize IntMap when caching manifest revisions
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 278
diff changeset
212
415
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
213 public Map<Integer, ? super V> fill(Map<Integer, ? super V> map) {
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
214 for (Iterator<Map.Entry<Integer, V>> it = entryIterator(); it.hasNext(); ) {
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
215 Map.Entry<Integer, V> next = it.next();
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
216 map.put(next.getKey(), next.getValue());
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
217 }
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
218 return map;
ee8264d80747 Explicit constant for regular file flags, access to flags for a given file revision
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 281
diff changeset
219 }
656
a937e63b6e02 Performance: rebuild information about branches takes too long (my improvement: 3 times, 11-15 s to less than 4 sec)
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 613
diff changeset
220
672
d2552e6a5af6 Effective update of HgParentChildMap when repository got few revisions added
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 656
diff changeset
221 public int[] keys() {
d2552e6a5af6 Effective update of HgParentChildMap when repository got few revisions added
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 656
diff changeset
222 int[] rv = new int[size];
d2552e6a5af6 Effective update of HgParentChildMap when repository got few revisions added
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 656
diff changeset
223 System.arraycopy(keys, 0, rv, 0, size);
d2552e6a5af6 Effective update of HgParentChildMap when repository got few revisions added
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 656
diff changeset
224 return rv;
d2552e6a5af6 Effective update of HgParentChildMap when repository got few revisions added
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 656
diff changeset
225 }
d2552e6a5af6 Effective update of HgParentChildMap when repository got few revisions added
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 656
diff changeset
226
656
a937e63b6e02 Performance: rebuild information about branches takes too long (my improvement: 3 times, 11-15 s to less than 4 sec)
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 613
diff changeset
227 public Collection<V> values() {
a937e63b6e02 Performance: rebuild information about branches takes too long (my improvement: 3 times, 11-15 s to less than 4 sec)
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 613
diff changeset
228 @SuppressWarnings("unchecked")
a937e63b6e02 Performance: rebuild information about branches takes too long (my improvement: 3 times, 11-15 s to less than 4 sec)
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 613
diff changeset
229 V[] rv = (V[]) new Object[size];
a937e63b6e02 Performance: rebuild information about branches takes too long (my improvement: 3 times, 11-15 s to less than 4 sec)
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 613
diff changeset
230 System.arraycopy(values, 0, rv, 0, size);
a937e63b6e02 Performance: rebuild information about branches takes too long (my improvement: 3 times, 11-15 s to less than 4 sec)
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 613
diff changeset
231 return Arrays.<V>asList(rv);
a937e63b6e02 Performance: rebuild information about branches takes too long (my improvement: 3 times, 11-15 s to less than 4 sec)
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 613
diff changeset
232 }
276
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
233
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
234 // copy of Arrays.binarySearch, with upper search limit as argument
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
235 private static int binarySearch(int[] a, int high, int key) {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
236 int low = 0;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
237 high--;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
238
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
239 while (low <= high) {
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
240 int mid = (low + high) >> 1;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
241 int midVal = a[mid];
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
242
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
243 if (midVal < key)
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
244 low = mid + 1;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
245 else if (midVal > key)
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
246 high = mid - 1;
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
247 else
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
248 return mid; // key found
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
249 }
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
250 return -(low + 1); // key not found.
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
251 }
6355ecda1f08 Tailored Map implementation with int keys
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
252 }