1 /*
2 * Copyright 2005 Ralf Joachim
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16 package org.castor.core.util;
17
18 import java.util.Collection;
19 import java.util.Map;
20 import java.util.Set;
21
22 /**
23 * An IdentityMap that uses reference-equality instead of object-equality. According
24 * to its special function it violates some design contracts of the <code>Map</code>
25 * interface.
26 *
27 * @author <a href="mailto:ralf DOT joachim AT syscon DOT eu">Ralf Joachim</a>
28 * @version $Revision: 7491 $ $Date: 2006-04-13 10:49:49 -0600 (Thu, 13 Apr 2006) $
29 * @since 0.9.9
30 */
31 public final class IdentityMap implements Map {
32 //--------------------------------------------------------------------------
33
34 /** Default number of buckets. */
35 private static final int DEFAULT_CAPACITY = 17;
36
37 /** Default load factor. */
38 private static final float DEFAULT_LOAD = 0.75f;
39
40 /** Default number of entries. */
41 private static final int DEFAULT_ENTRIES = (int) (DEFAULT_CAPACITY * DEFAULT_LOAD);
42
43 /** Default factor to increment capacity. */
44 private static final int DEFAULT_INCREMENT = 2;
45
46 /** First prime number to check is 3 as we prevent 2 by design. */
47 private static final int FIRST_PRIME_TO_CHECK = 3;
48
49 //--------------------------------------------------------------------------
50
51 /** Number of buckets. */
52 private int _capacity = DEFAULT_CAPACITY;
53
54 /** Maximum number of entries before rehashing. */
55 private int _maximum = DEFAULT_ENTRIES;
56
57 /** Buckets. */
58 private Entry[] _buckets = new Entry[DEFAULT_CAPACITY];
59
60 /** Number of map entries. */
61 private int _entries = 0;
62
63 //--------------------------------------------------------------------------
64
65 /**
66 * {@inheritDoc}
67 * @see java.util.Map#clear()
68 */
69 public void clear() {
70 _capacity = DEFAULT_CAPACITY;
71 _maximum = DEFAULT_ENTRIES;
72 _buckets = new Entry[DEFAULT_CAPACITY];
73 _entries = 0;
74 }
75
76 /**
77 * {@inheritDoc}
78 * @see java.util.Map#size()
79 */
80 public int size() { return _entries; }
81
82 /**
83 * {@inheritDoc}
84 * @see java.util.Map#isEmpty()
85 */
86 public boolean isEmpty() { return (_entries == 0); }
87
88 /**
89 * {@inheritDoc}
90 * @see java.util.Map#put(java.lang.Object, java.lang.Object)
91 */
92 public Object put(final Object key, final Object value) {
93 int hash = System.identityHashCode(key);
94 int index = hash % _capacity;
95 if (index < 0) { index = -index; }
96
97 Entry entry = _buckets[index];
98 Entry prev = null;
99 while (entry != null) {
100 if (entry.getKey() == key) {
101 // There is a mapping for this key so we have to replace the value.
102 Object ret = entry.getValue();
103 entry.setValue(value);
104 return ret;
105 }
106 prev = entry;
107 entry = entry.getNext();
108 }
109 if (prev == null) {
110 // There is no previous entry in this bucket.
111 _buckets[index] = new Entry(key, hash, value);
112 } else {
113 // Next entry is empty so we have no mapping for this key.
114 prev.setNext(new Entry(key, hash, value));
115 }
116 _entries++;
117 if (_entries > _maximum) { rehash(); }
118 return null;
119 }
120
121 /**
122 * Rehash the map into a new array with increased capacity.
123 */
124 private void rehash() {
125 long nextCapacity = _capacity * DEFAULT_INCREMENT;
126 if (nextCapacity > Integer.MAX_VALUE) { return; }
127 nextCapacity = nextPrime(nextCapacity);
128 if (nextCapacity > Integer.MAX_VALUE) { return; }
129
130 int newCapacity = (int) nextCapacity;
131 Entry[] newBuckets = new Entry[newCapacity];
132
133 Entry entry = null;
134 Entry temp = null;
135 Entry next = null;
136 int newIndex = 0;
137
138 for (int index = 0; index < _capacity; index++) {
139 entry = _buckets[index];
140 while (entry != null) {
141 next = entry.getNext();
142
143 newIndex = entry.getHash() % newCapacity;
144 if (newIndex < 0) { newIndex = -newIndex; }
145
146 temp = newBuckets[newIndex];
147 if (temp == null) {
148 // First entry of the bucket.
149 entry.setNext(null);
150 } else {
151 // Hook entry into beginning of the buckets chain.
152 entry.setNext(temp);
153 }
154 newBuckets[newIndex] = entry;
155
156 entry = next;
157 }
158 }
159
160 _capacity = newCapacity;
161 _maximum = (int) (newCapacity * DEFAULT_LOAD);
162 _buckets = newBuckets;
163 }
164
165 /**
166 * Find next prime number greater than minimum.
167 *
168 * @param minimum The minimum (exclusive) value of the next prime number.
169 * @return The next prime number greater than minimum.
170 */
171 private long nextPrime(final long minimum) {
172 long candidate = ((minimum + 1) / 2) * 2 + 1;
173 while (!isPrime(candidate)) { candidate += 2; }
174 return candidate;
175 }
176
177 /**
178 * Check for prime number.
179 *
180 * @param candidate Number to be checked for being a prime number.
181 * @return <code>true</code> if the given number is a prime number
182 * <code>false</code> otherwise.
183 */
184 private boolean isPrime(final long candidate) {
185 if ((candidate / 2) * 2 == candidate) { return false; }
186 long stop = candidate / 2;
187 for (long i = FIRST_PRIME_TO_CHECK; i < stop; i += 2) {
188 if ((candidate / i) * i == candidate) { return false; }
189 }
190 return true;
191 }
192
193 /**
194 * {@inheritDoc}
195 * @see java.util.Map#containsKey(java.lang.Object)
196 */
197 public boolean containsKey(final Object key) {
198 int hash = System.identityHashCode(key);
199 int index = hash % _capacity;
200 if (index < 0) { index = -index; }
201
202 Entry entry = _buckets[index];
203 while (entry != null) {
204 if (entry.getKey() == key) { return true; }
205 entry = entry.getNext();
206 }
207 return false;
208 }
209
210 /**
211 * {@inheritDoc}
212 * @see java.util.Map#get(java.lang.Object)
213 */
214 public Object get(final Object key) {
215 int hash = System.identityHashCode(key);
216 int index = hash % _capacity;
217 if (index < 0) { index = -index; }
218
219 Entry entry = _buckets[index];
220 while (entry != null) {
221 if (entry.getKey() == key) { return entry.getValue(); }
222 entry = entry.getNext();
223 }
224 return null;
225 }
226
227 /**
228 * {@inheritDoc}
229 * @see java.util.Map#remove(java.lang.Object)
230 */
231 public Object remove(final Object key) {
232 int hash = System.identityHashCode(key);
233 int index = hash % _capacity;
234 if (index < 0) { index = -index; }
235
236 Entry entry = _buckets[index];
237 Entry prev = null;
238 while (entry != null) {
239 if (entry.getKey() == key) {
240 // Found the entry.
241 if (prev == null) {
242 // First element in bucket matches.
243 _buckets[index] = entry.getNext();
244 } else {
245 // Remove the entry from the chain.
246 prev.setNext(entry.getNext());
247 }
248 _entries--;
249 return entry.getValue();
250 }
251 prev = entry;
252 entry = entry.getNext();
253 }
254 return null;
255 }
256
257 /**
258 * {@inheritDoc}
259 * @see java.util.Map#keySet()
260 */
261 public Set keySet() {
262 Set set = new IdentitySet(_capacity);
263
264 for (int i = 0; i < _capacity; i++) {
265 Entry entry = _buckets[i];
266 while (entry != null) {
267 set.add(entry.getKey());
268 entry = entry.getNext();
269 }
270 }
271
272 return set;
273 }
274
275 /**
276 * In contrast with the design contract of the <code>Map</code> interface this method
277 * has not been implemented and throws a <code>UnsupportedOperationException</code>.
278 *
279 * {@inheritDoc}
280 * @see java.util.Map#entrySet()
281 */
282 public Set entrySet() {
283 Set set = new IdentitySet(_capacity);
284
285 for (int i = 0; i < _capacity; i++) {
286 Entry entry = _buckets[i];
287 while (entry != null) {
288 set.add(entry);
289 entry = entry.getNext();
290 }
291 }
292
293 return set;
294 }
295
296 /**
297 * In contrast with the design contract of the <code>Map</code> interface this method
298 * has not been implemented and throws a <code>UnsupportedOperationException</code>.
299 *
300 * {@inheritDoc}
301 * @see java.util.Map#values()
302 */
303 public Collection values() {
304 throw new UnsupportedOperationException();
305 }
306
307 /**
308 * In contrast with the design contract of the <code>Map</code> interface this method
309 * has not been implemented and throws a <code>UnsupportedOperationException</code>.
310 *
311 * {@inheritDoc}
312 * @see java.util.Map#containsValue
313 */
314 public boolean containsValue(final Object value) {
315 throw new UnsupportedOperationException();
316 }
317
318 /**
319 * This optional method has not been implemented for <code>IdentityMap</code> instead
320 * it throws a <code>UnsupportedOperationException</code> as defined in the
321 * <code>Map</code> interface.
322 *
323 * {@inheritDoc}
324 * @see java.util.Map#putAll
325 */
326 public void putAll(final Map map) {
327 throw new UnsupportedOperationException();
328 }
329
330 //--------------------------------------------------------------------------
331
332 /**
333 * An entry of the <code>IdentityMap</code>.
334 */
335 public final class Entry implements Map.Entry {
336 /** Key of entry. */
337 private Object _key;
338
339 /** Identity hashcode of key. */
340 private int _hash;
341
342 /** Value of entry. */
343 private Object _value;
344
345 /** Reference to next entry. */
346 private Entry _next = null;
347
348 /**
349 * Construct an entry.
350 *
351 * @param key Key of entry.
352 * @param hash Identity hashcode of key.
353 * @param value Value of entry.
354 */
355 public Entry(final Object key, final int hash, final Object value) {
356 _key = key;
357 _hash = hash;
358 _value = value;
359 }
360
361 /**
362 * Get key of entry.
363 *
364 * @return Key of entry.
365 */
366 public Object getKey() { return _key; }
367
368 /**
369 * Get identity hashcode of key.
370 *
371 * @return Identity hashcode of key.
372 */
373 public int getHash() { return _hash; }
374
375 /**
376 * Set value of entry.
377 *
378 * @param value New value of entry.
379 * @return Previous entry in the map.
380 */
381 public Object setValue(final Object value) {
382 Object temp = _value;
383 _value = value;
384 return temp;
385 }
386
387 /**
388 * Get value of entry.
389 *
390 * @return Value of entry.
391 */
392 public Object getValue() { return _value; }
393
394 /**
395 * Set reference to next entry.
396 *
397 * @param next New reference to next entry.
398 */
399 public void setNext(final Entry next) { _next = next; }
400
401 /**
402 * Get reference to next entry.
403 *
404 * @return Reference to next entry.
405 */
406 public Entry getNext() { return _next; }
407 }
408
409 //--------------------------------------------------------------------------
410 }