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