1 /*
2 * Copyright (C) 2009, Google Inc.
3 * Copyright (C) 2008, Marek Zawirski <marek.zawirski@gmail.com>
4 * Copyright (C) 2008, Shawn O. Pearce <spearce@spearce.org>
5 * and other copyright owners as documented in the project's IP log.
6 *
7 * This program and the accompanying materials are made available
8 * under the terms of the Eclipse Distribution License v1.0 which
9 * accompanies this distribution, is reproduced below, and is
10 * available at http://www.eclipse.org/org/documents/edl-v10.php
11 *
12 * All rights reserved.
13 *
14 * Redistribution and use in source and binary forms, with or
15 * without modification, are permitted provided that the following
16 * conditions are met:
17 *
18 * - Redistributions of source code must retain the above copyright
19 * notice, this list of conditions and the following disclaimer.
20 *
21 * - Redistributions in binary form must reproduce the above
22 * copyright notice, this list of conditions and the following
23 * disclaimer in the documentation and/or other materials provided
24 * with the distribution.
25 *
26 * - Neither the name of the Eclipse Foundation, Inc. nor the
27 * names of its contributors may be used to endorse or promote
28 * products derived from this software without specific prior
29 * written permission.
30 *
31 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
32 * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
33 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
34 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
35 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
36 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
37 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
38 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
39 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
40 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
41 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
42 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
43 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
44 */
45
46 package org.eclipse.jgit.lib;
47
48 import java.util.Iterator;
49 import java.util.NoSuchElementException;
50
51 /**
52 * Fast, efficient map specifically for {@link org.eclipse.jgit.lib.ObjectId}
53 * subclasses.
54 * <p>
55 * This map provides an efficient translation from any ObjectId instance to a
56 * cached subclass of ObjectId that has the same value.
57 * <p>
58 * If object instances are stored in only one map,
59 * {@link org.eclipse.jgit.lib.ObjectIdOwnerMap} is a more efficient
60 * implementation.
61 *
62 * @param <V>
63 * type of subclass of ObjectId that will be stored in the map.
64 */
65 public class ObjectIdSubclassMap<V extends ObjectId>
66 implements Iterable<V>, ObjectIdSet {
67 private static final int INITIAL_TABLE_SIZE = 2048;
68
69 int size;
70
71 private int grow;
72
73 private int mask;
74
75 V[] table;
76
77 /**
78 * Create an empty map.
79 */
80 public ObjectIdSubclassMap() {
81 initTable(INITIAL_TABLE_SIZE);
82 }
83
84 /**
85 * Remove all entries from this map.
86 */
87 public void clear() {
88 size = 0;
89 initTable(INITIAL_TABLE_SIZE);
90 }
91
92 /**
93 * Lookup an existing mapping.
94 *
95 * @param toFind
96 * the object identifier to find.
97 * @return the instance mapped to toFind, or null if no mapping exists.
98 */
99 public V get(AnyObjectId toFind) {
100 final int msk = mask;
101 int i = toFind.w1 & msk;
102 final V[] tbl = table;
103 V obj;
104
105 while ((obj = tbl[i]) != null) {
106 if (AnyObjectId.isEqual(obj, toFind)) {
107 return obj;
108 }
109 i = (i + 1) & msk;
110 }
111 return null;
112 }
113
114 /**
115 * {@inheritDoc}
116 * <p>
117 * Returns true if this map contains the specified object.
118 */
119 @Override
120 public boolean contains(AnyObjectId toFind) {
121 return get(toFind) != null;
122 }
123
124 /**
125 * Store an object for future lookup.
126 * <p>
127 * An existing mapping for <b>must not</b> be in this map. Callers must
128 * first call {@link #get(AnyObjectId)} to verify there is no current
129 * mapping prior to adding a new mapping, or use
130 * {@link #addIfAbsent(ObjectId)}.
131 *
132 * @param newValue
133 * the object to store.
134 */
135 public <Q extends V> void add(Q newValue) {
136 if (++size == grow)
137 grow();
138 insert(newValue);
139 }
140
141 /**
142 * Store an object for future lookup.
143 * <p>
144 * Stores {@code newValue}, but only if there is not already an object for
145 * the same object name. Callers can tell if the value is new by checking
146 * the return value with reference equality:
147 *
148 * <pre>
149 * V obj = ...;
150 * boolean wasNew = map.addIfAbsent(obj) == obj;
151 * </pre>
152 *
153 * @param newValue
154 * the object to store.
155 * @return {@code newValue} if stored, or the prior value already stored and
156 * that would have been returned had the caller used
157 * {@code get(newValue)} first.
158 */
159 public <Q extends V> V addIfAbsent(Q newValue) {
160 final int msk = mask;
161 int i = newValue.w1 & msk;
162 final V[] tbl = table;
163 V obj;
164
165 while ((obj = tbl[i]) != null) {
166 if (AnyObjectId.isEqual(obj, newValue))
167 return obj;
168 i = (i + 1) & msk;
169 }
170
171 if (++size == grow) {
172 grow();
173 insert(newValue);
174 } else {
175 tbl[i] = newValue;
176 }
177 return newValue;
178 }
179
180 /**
181 * Get number of objects in map
182 *
183 * @return number of objects in map
184 */
185 public int size() {
186 return size;
187 }
188
189 /**
190 * Whether {@link #size()} is 0.
191 *
192 * @return true if {@link #size()} is 0.
193 */
194 public boolean isEmpty() {
195 return size == 0;
196 }
197
198 /** {@inheritDoc} */
199 @Override
200 public Iterator<V> iterator() {
201 return new Iterator<V>() {
202 private int found;
203
204 private int i;
205
206 @Override
207 public boolean hasNext() {
208 return found < size;
209 }
210
211 @Override
212 public V next() {
213 while (i < table.length) {
214 final V v = table[i++];
215 if (v != null) {
216 found++;
217 return v;
218 }
219 }
220 throw new NoSuchElementException();
221 }
222
223 @Override
224 public void remove() {
225 throw new UnsupportedOperationException();
226 }
227 };
228 }
229
230 private void insert(V newValue) {
231 final int msk = mask;
232 int j = newValue.w1 & msk;
233 final V[] tbl = table;
234 while (tbl[j] != null)
235 j = (j + 1) & msk;
236 tbl[j] = newValue;
237 }
238
239 private void grow() {
240 final V[] oldTable = table;
241 final int oldSize = table.length;
242
243 initTable(oldSize << 1);
244 for (int i = 0; i < oldSize; i++) {
245 final V obj = oldTable[i];
246 if (obj != null)
247 insert(obj);
248 }
249 }
250
251 private void initTable(int sz) {
252 grow = sz >> 1;
253 mask = sz - 1;
254 table = createArray(sz);
255 }
256
257 @SuppressWarnings("unchecked")
258 private final V[] createArray(int sz) {
259 return (V[]) new ObjectId[sz];
260 }
261 }