1 package org.codehaus.plexus.util;
2
3 /*
4 * J.A.D.E. Java(TM) Addition to Default Environment.
5 * Latest release available at http://jade.dautelle.com/
6 * This class is public domain (not copyrighted).
7 */
8
9 import java.io.IOException;
10 import java.io.ObjectInputStream;
11 import java.io.ObjectOutputStream;
12 import java.io.Serializable;
13 import java.util.AbstractCollection;
14 import java.util.AbstractSet;
15 import java.util.Collection;
16 import java.util.Iterator;
17 import java.util.Map;
18 import java.util.Set;
19
20 /**
21 * <p>
22 * This class represents a <code>Map</code> collection with real-time behavior. Unless the map's size exceeds its
23 * current capacity, no dynamic memory allocation is ever performed and response time is <b>extremely fast</b> and
24 * <b>consistent</b>.
25 * </p>
26 * <p>
27 * Our <a href="http://jade.dautelle.com/doc/benchmark.txt">benchmark</a> indicates that {@link FastMap#put
28 * FastMap.put(key, value)} is up to <b>5x faster</b> than <code>java.util.HashMap.put(key, value)</code>. This
29 * difference is mostly due to the cost of the <code>Map.Entry</code> allocations that {@link FastMap} avoids by
30 * recycling its entries (see note below).
31 * </p>
32 * <p>
33 * {@link FastMap} has a predictable iteration order, which is the order in which keys were inserted into the map
34 * (similar to <code>java.util.LinkedHashMap</code> collection class).
35 * </p>
36 * <p>
37 * Applications may change the resizing policy of {@link FastMap} by overriding the {@link #sizeChanged} method. For
38 * example, to improve predictability, automatic resizing can be disabled.
39 * </p>
40 * <p>
41 * This implementation is not synchronized. Multiple threads accessing or modifying the collection must be synchronized
42 * externally.
43 * </p>
44 * <p>
45 * <b>Note:</b> To avoid dynamic memory allocations, {@link FastMap} maintains an internal pool of
46 * <code>Map.Entry</code> objects. The size of the pool is determined by the map's capacity. When an entry is removed
47 * from the map, it is automatically restored to the pool.
48 * </p>
49 * <p>
50 * <i> This class is <b>public domain</b> (not copyrighted).</i>
51 * </p>
52 *
53 * @author <a href="mailto:jean-marie@dautelle.com">Jean-Marie Dautelle</a>
54 * @version 5.3, October 31 2003
55 */
56 public class FastMap<K, V> implements Map<K, V>, Cloneable, Serializable {
57
58 /**
59 * Holds the map's hash table.
60 */
61 private transient EntryImpl[] _entries;
62
63 /**
64 * Holds the map's current capacity.
65 */
66 private transient int _capacity;
67
68 /**
69 * Holds the hash code mask.
70 */
71 private transient int _mask;
72
73 /**
74 * Holds the first pool entry (linked list).
75 */
76 private transient EntryImpl _poolFirst;
77
78 /**
79 * Holds the first map entry (linked list).
80 */
81 private transient EntryImpl _mapFirst;
82
83 /**
84 * Holds the last map entry (linked list).
85 */
86 private transient EntryImpl _mapLast;
87
88 /**
89 * Holds the current size.
90 */
91 private transient int _size;
92
93 /**
94 * Creates a {@link FastMap} with a capacity of <code>256</code> entries.
95 */
96 public FastMap() {
97 initialize(256);
98 }
99
100 /**
101 * Creates a {@link FastMap}, copy of the specified <code>Map</code>. If the specified map is not an instance of
102 * {@link FastMap}, the newly created map has a capacity set to the specified map's size. The copy has the same
103 * order as the original, regardless of the original map's implementation:
104 *
105 * <pre>
106 * TreeMap dictionary = ...;
107 * FastMap dictionaryLookup = new FastMap(dictionary);
108 * </pre>
109 *
110 * @param map the map whose mappings are to be placed in this map.
111 */
112 public FastMap(Map map) {
113 int capacity = (map instanceof FastMap) ? ((FastMap) map).capacity() : map.size();
114 initialize(capacity);
115 putAll(map);
116 }
117
118 /**
119 * Creates a {@link FastMap} with the specified capacity. Unless the capacity is exceeded, operations on this map do
120 * not allocate entries. For optimum performance, the capacity should be of the same order of magnitude or larger
121 * than the expected map's size.
122 *
123 * @param capacity the number of buckets in the hash table; it also defines the number of pre-allocated entries.
124 */
125 public FastMap(int capacity) {
126 initialize(capacity);
127 }
128
129 /**
130 * Returns the number of key-value mappings in this {@link FastMap}.
131 *
132 * @return this map's size.
133 */
134 @Override
135 public int size() {
136 return _size;
137 }
138
139 /**
140 * Returns the capacity of this {@link FastMap}. The capacity defines the number of buckets in the hash table, as
141 * well as the maximum number of entries the map may contain without allocating memory.
142 *
143 * @return this map's capacity.
144 */
145 public int capacity() {
146 return _capacity;
147 }
148
149 /**
150 * Indicates if this {@link FastMap} contains no key-value mappings.
151 *
152 * @return <code>true</code> if this map contains no key-value mappings; <code>false</code> otherwise.
153 */
154 @Override
155 public boolean isEmpty() {
156 return _size == 0;
157 }
158
159 /**
160 * Indicates if this {@link FastMap} contains a mapping for the specified key.
161 *
162 * @param key the key whose presence in this map is to be tested.
163 * @return <code>true</code> if this map contains a mapping for the specified key; <code>false</code> otherwise.
164 * @throws NullPointerException if the key is <code>null</code>.
165 */
166 @Override
167 public boolean containsKey(Object key) {
168 EntryImpl entry = _entries[keyHash(key) & _mask];
169 while (entry != null) {
170 if (key.equals(entry._key)) {
171 return true;
172 }
173 entry = entry._next;
174 }
175 return false;
176 }
177
178 /**
179 * Indicates if this {@link FastMap} maps one or more keys to the specified value.
180 *
181 * @param value the value whose presence in this map is to be tested.
182 * @return <code>true</code> if this map maps one or more keys to the specified value.
183 * @throws NullPointerException if the key is <code>null</code>.
184 */
185 @Override
186 public boolean containsValue(Object value) {
187 EntryImpl entry = _mapFirst;
188 while (entry != null) {
189 if (value.equals(entry._value)) {
190 return true;
191 }
192 entry = entry._after;
193 }
194 return false;
195 }
196
197 /**
198 * Returns the value to which this {@link FastMap} maps the specified key.
199 *
200 * @param key the key whose associated value is to be returned.
201 * @return the value to which this map maps the specified key, or <code>null</code> if there is no mapping for the
202 * key.
203 * @throws NullPointerException if key is <code>null</code>.
204 */
205 @Override
206 public V get(Object key) {
207 EntryImpl<K, V> entry = _entries[keyHash(key) & _mask];
208 while (entry != null) {
209 if (key.equals(entry._key)) {
210 return entry._value;
211 }
212 entry = entry._next;
213 }
214 return null;
215 }
216
217 /**
218 * Returns the entry with the specified key.
219 *
220 * @param key the key whose associated entry is to be returned.
221 * @return the entry for the specified key or <code>null</code> if none.
222 */
223 public Map.Entry getEntry(Object key) {
224 EntryImpl entry = _entries[keyHash(key) & _mask];
225 while (entry != null) {
226 if (key.equals(entry._key)) {
227 return entry;
228 }
229 entry = entry._next;
230 }
231 return null;
232 }
233
234 /**
235 * Associates the specified value with the specified key in this {@link FastMap}. If the {@link FastMap} previously
236 * contained a mapping for this key, the old value is replaced.
237 *
238 * @param key the key with which the specified value is to be associated.
239 * @param value the value to be associated with the specified key.
240 * @return the previous value associated with specified key, or <code>null</code> if there was no mapping for key. A
241 * <code>null</code> return can also indicate that the map previously associated <code>null</code> with the
242 * specified key.
243 * @throws NullPointerException if the key is <code>null</code>.
244 */
245 @Override
246 public Object put(Object key, Object value) {
247 EntryImpl entry = _entries[keyHash(key) & _mask];
248 while (entry != null) {
249 if (key.equals(entry._key)) {
250 Object prevValue = entry._value;
251 entry._value = value;
252 return prevValue;
253 }
254 entry = entry._next;
255 }
256 // No previous mapping.
257 addEntry(key, value);
258 return null;
259 }
260
261 /**
262 * Copies all of the mappings from the specified map to this {@link FastMap}.
263 *
264 * @param map the mappings to be stored in this map.
265 * @throws NullPointerException the specified map is <code>null</code>, or the specified map contains
266 * <code>null</code> keys.
267 */
268 @Override
269 public void putAll(Map<? extends K, ? extends V> map) {
270 for (Entry<? extends K, ? extends V> entry : map.entrySet()) {
271 addEntry(entry.getKey(), entry.getValue());
272 }
273 }
274
275 /**
276 * Removes the mapping for this key from this {@link FastMap} if present.
277 *
278 * @param key the key whose mapping is to be removed from the map.
279 * @return previous value associated with specified key, or <code>null</code> if there was no mapping for key. A
280 * <code>null</code> return can also indicate that the map previously associated <code>null</code> with the
281 * specified key.
282 * @throws NullPointerException if the key is <code>null</code>.
283 */
284 @Override
285 public V remove(Object key) {
286 EntryImpl<K, V> entry = _entries[keyHash(key) & _mask];
287 while (entry != null) {
288 if (key.equals(entry._key)) {
289 V prevValue = entry._value;
290 removeEntry(entry);
291 return prevValue;
292 }
293 entry = entry._next;
294 }
295 return null;
296 }
297
298 /**
299 * Removes all mappings from this {@link FastMap}.
300 */
301 @Override
302 public void clear() {
303 // Clears all keys, values and buckets linked lists.
304 for (EntryImpl entry = _mapFirst; entry != null; entry = entry._after) {
305 entry._key = null;
306 entry._value = null;
307 entry._before = null;
308 entry._next = null;
309 if (entry._previous == null) { // First in bucket.
310 _entries[entry._index] = null;
311 } else {
312 entry._previous = null;
313 }
314 }
315
316 // Recycles all entries.
317 if (_mapLast != null) {
318 _mapLast._after = _poolFirst; // Connects to pool.
319 _poolFirst = _mapFirst;
320 _mapFirst = null;
321 _mapLast = null;
322 _size = 0;
323 sizeChanged();
324 }
325 }
326
327 /**
328 * Changes the current capacity of this {@link FastMap}. If the capacity is increased, new entries are allocated and
329 * added to the pool. If the capacity is decreased, entries from the pool are deallocated (and are eventually
330 * garbage collected). The capacity also determined the number of buckets for the hash table.
331 *
332 * @param newCapacity the new capacity of this map.
333 */
334 public void setCapacity(int newCapacity) {
335 if (newCapacity > _capacity) { // Capacity increases.
336 for (int i = _capacity; i < newCapacity; i++) {
337 EntryImpl entry = new EntryImpl();
338 entry._after = _poolFirst;
339 _poolFirst = entry;
340 }
341 } else if (newCapacity < _capacity) { // Capacity decreases.
342 for (int i = newCapacity; (i < _capacity) && (_poolFirst != null); i++) {
343 // Disconnects the entry for gc to do its work.
344 EntryImpl entry = _poolFirst;
345 _poolFirst = entry._after;
346 entry._after = null; // All pointers are now null!
347 }
348 }
349 // Find a power of 2 >= capacity
350 int tableLength = 16;
351 while (tableLength < newCapacity) {
352 tableLength <<= 1;
353 }
354 // Checks if the hash table has to be re-sized.
355 if (_entries.length != tableLength) {
356 _entries = new EntryImpl[tableLength];
357 _mask = tableLength - 1;
358
359 // Repopulates the hash table.
360 EntryImpl entry = _mapFirst;
361 while (entry != null) {
362 int index = keyHash(entry._key) & _mask;
363 entry._index = index;
364
365 // Connects to bucket.
366 entry._previous = null; // Resets previous.
367 EntryImpl next = _entries[index];
368 entry._next = next;
369 if (next != null) {
370 next._previous = entry;
371 }
372 _entries[index] = entry;
373
374 entry = entry._after;
375 }
376 }
377 _capacity = newCapacity;
378 }
379
380 /**
381 * Returns a shallow copy of this {@link FastMap}. The keys and the values themselves are not cloned.
382 *
383 * @return a shallow copy of this map.
384 */
385 @Override
386 public Object clone() {
387 try {
388 FastMap clone = (FastMap) super.clone();
389 clone.initialize(_capacity);
390 clone.putAll(this);
391 return clone;
392 } catch (CloneNotSupportedException e) {
393 // Should not happen, since we are Cloneable.
394 throw new InternalError();
395 }
396 }
397
398 /**
399 * Compares the specified object with this {@link FastMap} for equality. Returns <code>true</code> if the given
400 * object is also a map and the two maps represent the same mappings (regardless of collection iteration order).
401 *
402 * @param obj the object to be compared for equality with this map.
403 * @return <code>true</code> if the specified object is equal to this map; <code>false</code> otherwise.
404 */
405 @Override
406 public boolean equals(Object obj) {
407 if (obj == this) {
408 return true;
409 } else if (obj instanceof Map) {
410 Map that = (Map) obj;
411 if (this.size() == that.size()) {
412 EntryImpl entry = _mapFirst;
413 while (entry != null) {
414 if (!that.entrySet().contains(entry)) {
415 return false;
416 }
417 entry = entry._after;
418 }
419 return true;
420 } else {
421 return false;
422 }
423 } else {
424 return false;
425 }
426 }
427
428 /**
429 * Returns the hash code value for this {@link FastMap}.
430 *
431 * @return the hash code value for this map.
432 */
433 @Override
434 public int hashCode() {
435 int code = 0;
436 EntryImpl entry = _mapFirst;
437 while (entry != null) {
438 code += entry.hashCode();
439 entry = entry._after;
440 }
441 return code;
442 }
443
444 /**
445 * Returns a <code>String</code> representation of this {@link FastMap}.
446 *
447 * @return <code>this.entrySet().toString();</code>
448 */
449 @Override
450 public String toString() {
451 return entrySet().toString();
452 }
453
454 /**
455 * Returns a collection view of the values contained in this {@link FastMap}. The collection is backed by the map,
456 * so changes to the map are reflected in the collection, and vice-versa. The collection supports element removal,
457 * which removes the corresponding mapping from this map, via the <code>Iterator.remove</code>,
458 * <code>Collection.remove</code>, <code>removeAll</code>, <code>retainAll</code>, and <code>clear</code>
459 * operations. It does not support the <code>add</code> or <code>addAll</code> operations.
460 *
461 * @return a collection view of the values contained in this map.
462 */
463 @Override
464 public Collection values() {
465 return _values;
466 }
467
468 private transient Values _values;
469
470 private class Values extends AbstractCollection {
471 @Override
472 public Iterator iterator() {
473 return new Iterator() {
474 EntryImpl after = _mapFirst;
475
476 EntryImpl before;
477
478 @Override
479 public void remove() {
480 removeEntry(before);
481 }
482
483 @Override
484 public boolean hasNext() {
485 return after != null;
486 }
487
488 @Override
489 public Object next() {
490 before = after;
491 after = after._after;
492 return before._value;
493 }
494 };
495 }
496
497 @Override
498 public int size() {
499 return _size;
500 }
501
502 @Override
503 public boolean contains(Object o) {
504 return containsValue(o);
505 }
506
507 @Override
508 public void clear() {
509 FastMap.this.clear();
510 }
511 }
512
513 /**
514 * Returns a collection view of the mappings contained in this {@link FastMap}. Each element in the returned
515 * collection is a <code>Map.Entry</code>. The collection is backed by the map, so changes to the map are reflected
516 * in the collection, and vice-versa. The collection supports element removal, which removes the corresponding
517 * mapping from this map, via the <code>Iterator.remove</code>, <code>Collection.remove</code>,
518 * <code>removeAll</code>, <code>retainAll</code>, and <code>clear</code> operations. It does not support the
519 * <code>add</code> or <code>addAll</code> operations.
520 *
521 * @return a collection view of the mappings contained in this map.
522 */
523 @Override
524 public Set entrySet() {
525 return _entrySet;
526 }
527
528 private transient EntrySet _entrySet;
529
530 private class EntrySet extends AbstractSet {
531 @Override
532 public Iterator iterator() {
533 return new Iterator() {
534 EntryImpl after = _mapFirst;
535
536 EntryImpl before;
537
538 @Override
539 public void remove() {
540 removeEntry(before);
541 }
542
543 @Override
544 public boolean hasNext() {
545 return after != null;
546 }
547
548 @Override
549 public Object next() {
550 before = after;
551 after = after._after;
552 return before;
553 }
554 };
555 }
556
557 @Override
558 public int size() {
559 return _size;
560 }
561
562 @Override
563 public boolean contains(Object obj) { // Optimization.
564 if (obj instanceof Map.Entry) {
565 Map.Entry entry = (Map.Entry) obj;
566 Map.Entry mapEntry = getEntry(entry.getKey());
567 return entry.equals(mapEntry);
568 } else {
569 return false;
570 }
571 }
572
573 @Override
574 public boolean remove(Object obj) { // Optimization.
575 if (obj instanceof Map.Entry) {
576 Map.Entry entry = (Map.Entry) obj;
577 EntryImpl mapEntry = (EntryImpl) getEntry(entry.getKey());
578 if ((mapEntry != null) && (entry.getValue()).equals(mapEntry._value)) {
579 removeEntry(mapEntry);
580 return true;
581 }
582 }
583 return false;
584 }
585 }
586
587 /**
588 * Returns a set view of the keys contained in this {@link FastMap}. The set is backed by the map, so changes to the
589 * map are reflected in the set, and vice-versa. The set supports element removal, which removes the corresponding
590 * mapping from this map, via the <code>Iterator.remove</code>, <code>Collection.remove</code>,
591 * <code>removeAll</code>, <code>retainAll</code>, and <code>clear</code> operations. It does not support the
592 * <code>add</code> or <code>addAll</code> operations.
593 *
594 * @return a set view of the keys contained in this map.
595 */
596 @Override
597 public Set keySet() {
598 return _keySet;
599 }
600
601 private transient KeySet _keySet;
602
603 private class KeySet extends AbstractSet {
604 @Override
605 public Iterator iterator() {
606 return new Iterator() {
607 EntryImpl after = _mapFirst;
608
609 EntryImpl before;
610
611 @Override
612 public void remove() {
613 removeEntry(before);
614 }
615
616 @Override
617 public boolean hasNext() {
618 return after != null;
619 }
620
621 @Override
622 public Object next() {
623 before = after;
624 after = after._after;
625 return before._key;
626 }
627 };
628 }
629
630 @Override
631 public int size() {
632 return _size;
633 }
634
635 @Override
636 public boolean contains(Object obj) { // Optimization.
637 return FastMap.this.containsKey(obj);
638 }
639
640 @Override
641 public boolean remove(Object obj) { // Optimization.
642 return FastMap.this.remove(obj) != null;
643 }
644
645 @Override
646 public void clear() { // Optimization.
647 FastMap.this.clear();
648 }
649 }
650
651 /**
652 * This methods is being called when the size of this {@link FastMap} has changed. The default behavior is to double
653 * the map's capacity when the map's size reaches the current map's capacity. Sub-class may override this method to
654 * implement custom resizing policies or to disable automatic resizing. For example:
655 *
656 * <pre>
657 * Map fixedCapacityMap = new FastMap( 256 )
658 * {
659 * protected sizeChanged()
660 * {
661 * // Do nothing, automatic resizing disabled.
662 * }
663 * };
664 * </pre>
665 *
666 * @see #setCapacity
667 */
668 protected void sizeChanged() {
669 if (size() > capacity()) {
670 setCapacity(capacity() * 2);
671 }
672 }
673
674 /**
675 * Returns the hash code for the specified key. The formula being used is identical to the formula used by
676 * <code>java.util.HashMap</code> (ensures similar behavior for ill-conditioned hashcode keys).
677 *
678 * @param key the key to calculate the hashcode for.
679 * @return the hash code for the specified key.
680 */
681 private static int keyHash(Object key) {
682 // From HashMap.hash(Object) function.
683 int hashCode = key.hashCode();
684 hashCode += ~(hashCode << 9);
685 hashCode ^= (hashCode >>> 14);
686 hashCode += (hashCode << 4);
687 hashCode ^= (hashCode >>> 10);
688 return hashCode;
689 }
690
691 /**
692 * Adds a new entry for the specified key and value.
693 *
694 * @param key the entry's key.
695 * @param value the entry's value.
696 */
697 private void addEntry(Object key, Object value) {
698 EntryImpl entry = _poolFirst;
699 if (entry != null) {
700 _poolFirst = entry._after;
701 entry._after = null;
702 } else { // Pool empty.
703 entry = new EntryImpl();
704 }
705
706 // Setup entry parameters.
707 entry._key = key;
708 entry._value = value;
709 int index = keyHash(key) & _mask;
710 entry._index = index;
711
712 // Connects to bucket.
713 EntryImpl next = _entries[index];
714 entry._next = next;
715 if (next != null) {
716 next._previous = entry;
717 }
718 _entries[index] = entry;
719
720 // Connects to collection.
721 if (_mapLast != null) {
722 entry._before = _mapLast;
723 _mapLast._after = entry;
724 } else {
725 _mapFirst = entry;
726 }
727 _mapLast = entry;
728
729 // Updates size.
730 _size++;
731 sizeChanged();
732 }
733
734 /**
735 * Removes the specified entry from the map.
736 *
737 * @param entry the entry to be removed.
738 */
739 private void removeEntry(EntryImpl entry) {
740
741 // Removes from bucket.
742 EntryImpl previous = entry._previous;
743 EntryImpl next = entry._next;
744 if (previous != null) {
745 previous._next = next;
746 entry._previous = null;
747 } else { // First in bucket.
748 _entries[entry._index] = next;
749 }
750 if (next != null) {
751 next._previous = previous;
752 entry._next = null;
753 } // Else do nothing, no last pointer.
754
755 // Removes from collection.
756 EntryImpl before = entry._before;
757 EntryImpl after = entry._after;
758 if (before != null) {
759 before._after = after;
760 entry._before = null;
761 } else { // First in collection.
762 _mapFirst = after;
763 }
764 if (after != null) {
765 after._before = before;
766 } else { // Last in collection.
767 _mapLast = before;
768 }
769
770 // Clears value and key.
771 entry._key = null;
772 entry._value = null;
773
774 // Recycles.
775 entry._after = _poolFirst;
776 _poolFirst = entry;
777
778 // Updates size.
779 _size--;
780 sizeChanged();
781 }
782
783 /**
784 * Initializes this instance for the specified capacity. Once initialized, operations on this map should not create
785 * new objects (unless the map's size exceeds the specified capacity).
786 *
787 * @param capacity the initial capacity.
788 */
789 private void initialize(int capacity) {
790 // Find a power of 2 >= capacity
791 int tableLength = 16;
792 while (tableLength < capacity) {
793 tableLength <<= 1;
794 }
795 // Allocates hash table.
796 _entries = new EntryImpl[tableLength];
797 _mask = tableLength - 1;
798 _capacity = capacity;
799 _size = 0;
800 // Allocates views.
801 _values = new Values();
802 _entrySet = new EntrySet();
803 _keySet = new KeySet();
804 // Resets pointers.
805 _poolFirst = null;
806 _mapFirst = null;
807 _mapLast = null;
808 // Allocates entries.
809 for (int i = 0; i < capacity; i++) {
810 EntryImpl entry = new EntryImpl();
811 entry._after = _poolFirst;
812 _poolFirst = entry;
813 }
814 }
815
816 /**
817 * Requires special handling during de-serialization process.
818 *
819 * @param stream the object input stream.
820 * @throws IOException if an I/O error occurs.
821 * @throws ClassNotFoundException if the class for the object de-serialized is not found.
822 */
823 private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException {
824 int capacity = stream.readInt();
825 initialize(capacity);
826 int size = stream.readInt();
827 for (int i = 0; i < size; i++) {
828 Object key = stream.readObject();
829 Object value = stream.readObject();
830 addEntry(key, value);
831 }
832 }
833
834 /**
835 * Requires special handling during serialization process.
836 *
837 * @param stream the object output stream.
838 * @throws IOException if an I/O error occurs.
839 */
840 private void writeObject(ObjectOutputStream stream) throws IOException {
841 stream.writeInt(_capacity);
842 stream.writeInt(_size);
843 int count = 0;
844 EntryImpl entry = _mapFirst;
845 while (entry != null) {
846 stream.writeObject(entry._key);
847 stream.writeObject(entry._value);
848 count++;
849 entry = entry._after;
850 }
851 if (count != _size) {
852 throw new IOException("FastMap Corrupted");
853 }
854 }
855
856 /**
857 * This class represents a {@link FastMap} entry.
858 */
859 private static final class EntryImpl<K, V> implements Map.Entry<K, V> {
860
861 /**
862 * Holds the entry key (null when in pool).
863 */
864 private K _key;
865
866 /**
867 * Holds the entry value (null when in pool).
868 */
869 private V _value;
870
871 /**
872 * Holds the bucket index (undefined when in pool).
873 */
874 private int _index;
875
876 /**
877 * Holds the previous entry in the same bucket (null when in pool).
878 */
879 private EntryImpl _previous;
880
881 /**
882 * Holds the next entry in the same bucket (null when in pool).
883 */
884 private EntryImpl _next;
885
886 /**
887 * Holds the entry added before this entry (null when in pool).
888 */
889 private EntryImpl _before;
890
891 /**
892 * Holds the entry added after this entry or the next available entry when in pool.
893 */
894 private EntryImpl _after;
895
896 /**
897 * Returns the key for this entry.
898 *
899 * @return the entry's key.
900 */
901 @Override
902 public K getKey() {
903 return _key;
904 }
905
906 /**
907 * Returns the value for this entry.
908 *
909 * @return the entry's value.
910 */
911 @Override
912 public V getValue() {
913 return _value;
914 }
915
916 /**
917 * Sets the value for this entry.
918 *
919 * @param value the new value.
920 * @return the previous value.
921 */
922 @Override
923 public V setValue(V value) {
924 V old = _value;
925 _value = value;
926 return old;
927 }
928
929 /**
930 * Indicates if this entry is considered equals to the specified entry.
931 *
932 * @param that the object to test for equality.
933 * @return <code>true<code> if both entry are considered equal; <code>false<code> otherwise.
934 */
935 @Override
936 public boolean equals(Object that) {
937 if (that instanceof Map.Entry) {
938 Map.Entry entry = (Map.Entry) that;
939 return (_key.equals(entry.getKey()))
940 && ((_value != null) ? _value.equals(entry.getValue()) : (entry.getValue() == null));
941 } else {
942 return false;
943 }
944 }
945
946 /**
947 * Returns the hash code for this entry.
948 *
949 * @return this entry's hash code.
950 */
951 @Override
952 public int hashCode() {
953 return _key.hashCode() ^ ((_value != null) ? _value.hashCode() : 0);
954 }
955
956 /**
957 * Returns the text representation of this entry.
958 *
959 * @return this entry's textual representation.
960 */
961 @Override
962 public String toString() {
963 return _key + "=" + _value;
964 }
965 }
966 }