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 ObjectId} subclasses.
53 * <p>
54 * This map provides an efficient translation from any ObjectId instance to a
55 * cached subclass of ObjectId that has the same value.
56 * <p>
57 * If object instances are stored in only one map, {@link ObjectIdOwnerMap} is a
58 * more efficient implementation.
59 *
60 * @param <V>
61 * type of subclass of ObjectId that will be stored in the map.
62 */
63 public class ObjectIdSubclassMap<V extends ObjectId>
64 implements Iterable<V>, ObjectIdSet {
65 private static final int INITIAL_TABLE_SIZE = 2048;
66
67 int size;
68
69 private int grow;
70
71 private int mask;
72
73 V[] table;
74
75 /** Create an empty map. */
76 public ObjectIdSubclassMap() {
77 initTable(INITIAL_TABLE_SIZE);
78 }
79
80 /** Remove all entries from this map. */
81 public void clear() {
82 size = 0;
83 initTable(INITIAL_TABLE_SIZE);
84 }
85
86 /**
87 * Lookup an existing mapping.
88 *
89 * @param toFind
90 * the object identifier to find.
91 * @return the instance mapped to toFind, or null if no mapping exists.
92 */
93 public V get(final AnyObjectId toFind) {
94 final int msk = mask;
95 int i = toFind.w1 & msk;
96 final V[] tbl = table;
97 V obj;
98
99 while ((obj = tbl[i]) != null) {
100 if (AnyObjectId.equals(obj, toFind))
101 return obj;
102 i = (i + 1) & msk;
103 }
104 return null;
105 }
106
107 /**
108 * Returns true if this map contains the specified object.
109 *
110 * @param toFind
111 * object to find.
112 * @return true if the mapping exists for this object; false otherwise.
113 */
114 @Override
115 public boolean contains(final AnyObjectId toFind) {
116 return get(toFind) != null;
117 }
118
119 /**
120 * Store an object for future lookup.
121 * <p>
122 * An existing mapping for <b>must not</b> be in this map. Callers must
123 * first call {@link #get(AnyObjectId)} to verify there is no current
124 * mapping prior to adding a new mapping, or use
125 * {@link #addIfAbsent(ObjectId)}.
126 *
127 * @param newValue
128 * the object to store.
129 * @param <Q>
130 * type of instance to store.
131 */
132 public <Q extends V> void add(final Q newValue) {
133 if (++size == grow)
134 grow();
135 insert(newValue);
136 }
137
138 /**
139 * Store an object for future lookup.
140 * <p>
141 * Stores {@code newValue}, but only if there is not already an object for
142 * the same object name. Callers can tell if the value is new by checking
143 * the return value with reference equality:
144 *
145 * <pre>
146 * V obj = ...;
147 * boolean wasNew = map.addIfAbsent(obj) == obj;
148 * </pre>
149 *
150 * @param newValue
151 * the object to store.
152 * @return {@code newValue} if stored, or the prior value already stored and
153 * that would have been returned had the caller used
154 * {@code get(newValue)} first.
155 * @param <Q>
156 * type of instance to store.
157 */
158 public <Q extends V> V addIfAbsent(final 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 * @return number of objects in map
181 */
182 public int size() {
183 return size;
184 }
185
186 /** @return true if {@link #size()} is 0. */
187 public boolean isEmpty() {
188 return size == 0;
189 }
190
191 @Override
192 public Iterator<V> iterator() {
193 return new Iterator<V>() {
194 private int found;
195
196 private int i;
197
198 @Override
199 public boolean hasNext() {
200 return found < size;
201 }
202
203 @Override
204 public V next() {
205 while (i < table.length) {
206 final V v = table[i++];
207 if (v != null) {
208 found++;
209 return v;
210 }
211 }
212 throw new NoSuchElementException();
213 }
214
215 @Override
216 public void remove() {
217 throw new UnsupportedOperationException();
218 }
219 };
220 }
221
222 private void insert(final V newValue) {
223 final int msk = mask;
224 int j = newValue.w1 & msk;
225 final V[] tbl = table;
226 while (tbl[j] != null)
227 j = (j + 1) & msk;
228 tbl[j] = newValue;
229 }
230
231 private void grow() {
232 final V[] oldTable = table;
233 final int oldSize = table.length;
234
235 initTable(oldSize << 1);
236 for (int i = 0; i < oldSize; i++) {
237 final V obj = oldTable[i];
238 if (obj != null)
239 insert(obj);
240 }
241 }
242
243 private void initTable(int sz) {
244 grow = sz >> 1;
245 mask = sz - 1;
246 table = createArray(sz);
247 }
248
249 @SuppressWarnings("unchecked")
250 private final V[] createArray(final int sz) {
251 return (V[]) new ObjectId[sz];
252 }
253 }