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.equals(obj, toFind))
107 return obj;
108 i = (i + 1) & msk;
109 }
110 return null;
111 }
112
113 /**
114 * {@inheritDoc}
115 * <p>
116 * Returns true if this map contains the specified object.
117 */
118 @Override
119 public boolean contains(AnyObjectId toFind) {
120 return get(toFind) != null;
121 }
122
123 /**
124 * Store an object for future lookup.
125 * <p>
126 * An existing mapping for <b>must not</b> be in this map. Callers must
127 * first call {@link #get(AnyObjectId)} to verify there is no current
128 * mapping prior to adding a new mapping, or use
129 * {@link #addIfAbsent(ObjectId)}.
130 *
131 * @param newValue
132 * the object to store.
133 */
134 public <Q extends V> void add(Q newValue) {
135 if (++size == grow)
136 grow();
137 insert(newValue);
138 }
139
140 /**
141 * Store an object for future lookup.
142 * <p>
143 * Stores {@code newValue}, but only if there is not already an object for
144 * the same object name. Callers can tell if the value is new by checking
145 * the return value with reference equality:
146 *
147 * <pre>
148 * V obj = ...;
149 * boolean wasNew = map.addIfAbsent(obj) == obj;
150 * </pre>
151 *
152 * @param newValue
153 * the object to store.
154 * @return {@code newValue} if stored, or the prior value already stored and
155 * that would have been returned had the caller used
156 * {@code get(newValue)} first.
157 */
158 public <Q extends V> V addIfAbsent(Q newValue) {
159 final int msk = mask;
160 int i = newValue.w1 & msk;
161 final V[] tbl = table;
162 V obj;
163
164 while ((obj = tbl[i]) != null) {
165 if (AnyObjectId.equals(obj, newValue))
166 return obj;
167 i = (i + 1) & msk;
168 }
169
170 if (++size == grow) {
171 grow();
172 insert(newValue);
173 } else {
174 tbl[i] = newValue;
175 }
176 return newValue;
177 }
178
179 /**
180 * Get number of objects in map
181 *
182 * @return number of objects in map
183 */
184 public int size() {
185 return size;
186 }
187
188 /**
189 * Whether {@link #size()} is 0.
190 *
191 * @return true if {@link #size()} is 0.
192 */
193 public boolean isEmpty() {
194 return size == 0;
195 }
196
197 /** {@inheritDoc} */
198 @Override
199 public Iterator<V> iterator() {
200 return new Iterator<V>() {
201 private int found;
202
203 private int i;
204
205 @Override
206 public boolean hasNext() {
207 return found < size;
208 }
209
210 @Override
211 public V next() {
212 while (i < table.length) {
213 final V v = table[i++];
214 if (v != null) {
215 found++;
216 return v;
217 }
218 }
219 throw new NoSuchElementException();
220 }
221
222 @Override
223 public void remove() {
224 throw new UnsupportedOperationException();
225 }
226 };
227 }
228
229 private void insert(V newValue) {
230 final int msk = mask;
231 int j = newValue.w1 & msk;
232 final V[] tbl = table;
233 while (tbl[j] != null)
234 j = (j + 1) & msk;
235 tbl[j] = newValue;
236 }
237
238 private void grow() {
239 final V[] oldTable = table;
240 final int oldSize = table.length;
241
242 initTable(oldSize << 1);
243 for (int i = 0; i < oldSize; i++) {
244 final V obj = oldTable[i];
245 if (obj != null)
246 insert(obj);
247 }
248 }
249
250 private void initTable(int sz) {
251 grow = sz >> 1;
252 mask = sz - 1;
253 table = createArray(sz);
254 }
255
256 @SuppressWarnings("unchecked")
257 private final V[] createArray(int sz) {
258 return (V[]) new ObjectId[sz];
259 }
260 }