1 /*
2 * Copyright (c) 2017, 2017, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23
24
25 package jdk.internal.vm.compiler.collections;
26
27 import java.util.Iterator;
28 import java.util.Objects;
29 import java.util.function.BiFunction;
30
31 /**
32 * Implementation of a map with a memory-efficient structure that always preserves insertion order
33 * when iterating over keys. Particularly efficient when number of entries is 0 or smaller equal
34 * {@link #INITIAL_CAPACITY} or smaller 256.
35 *
36 * The key/value pairs are kept in an expanding flat object array with keys at even indices and
37 * values at odd indices. If the map has smaller or equal to {@link #HASH_THRESHOLD} entries, there
38 * is no additional hash data structure and comparisons are done via linear checking of the
39 * key/value pairs. For the case where the equality check is particularly cheap (e.g., just an
40 * object identity comparison), this limit below which the map is without an actual hash table is
41 * higher and configured at {@link #HASH_THRESHOLD_IDENTITY_COMPARE}.
42 *
43 * When the hash table needs to be constructed, the field {@link #hashArray} becomes a new hash
44 * array where an entry of 0 means no hit and otherwise denotes the entry number in the
45 * {@link #entries} array. The hash array is interpreted as an actual byte array if the indices fit
46 * within 8 bit, or as an array of short values if the indices fit within 16 bit, or as an array of
47 * integer values in other cases.
48 *
49 * Hash collisions are handled by chaining a linked list of {@link CollisionLink} objects that take
50 * the place of the values in the {@link #entries} array.
51 *
52 * Removing entries will put {@code null} into the {@link #entries} array. If the occupation of the
53 * map falls below a specific threshold, the map will be compressed via the
54 * {@link #maybeCompress(int)} method.
55 */
56 final class EconomicMapImpl<K, V> implements EconomicMap<K, V>, EconomicSet<K> {
57
58 /**
59 * Initial number of key/value pair entries that is allocated in the first entries array.
60 */
61 private static final int INITIAL_CAPACITY = 4;
62
63 /**
64 * Maximum number of entries that are moved linearly forward if a key is removed.
65 */
66 private static final int COMPRESS_IMMEDIATE_CAPACITY = 8;
67
68 /**
69 * Minimum number of key/value pair entries added when the entries array is increased in size.
70 */
71 private static final int MIN_CAPACITY_INCREASE = 8;
72
73 /**
74 * Number of entries above which a hash table is created.
75 */
76 private static final int HASH_THRESHOLD = 4;
77
78 /**
79 * Number of entries above which a hash table is created when equality can be checked with
80 * object identity.
81 */
82 private static final int HASH_THRESHOLD_IDENTITY_COMPARE = 8;
83
84 /**
85 * Maximum number of entries allowed in the map.
86 */
87 private static final int MAX_ELEMENT_COUNT = Integer.MAX_VALUE >> 1;
88
89 /**
90 * Number of entries above which more than 1 byte is necessary for the hash index.
91 */
92 private static final int LARGE_HASH_THRESHOLD = ((1 << Byte.SIZE) << 1);
93
94 /**
95 * Number of entries above which more than 2 bytes are are necessary for the hash index.
96 */
97 private static final int VERY_LARGE_HASH_THRESHOLD = (LARGE_HASH_THRESHOLD << Byte.SIZE);
98
99 /**
100 * Total number of entries (actual entries plus deleted entries).
101 */
102 private int totalEntries;
103
104 /**
105 * Number of deleted entries.
106 */
107 private int deletedEntries;
108
109 /**
110 * Entries array with even indices storing keys and odd indices storing values.
111 */
112 private Object[] entries;
113
114 /**
115 * Hash array that is interpreted either as byte or short or int array depending on number of
116 * map entries.
117 */
118 private byte[] hashArray;
119
120 /**
121 * The strategy used for comparing keys or {@code null} for denoting special strategy
122 * {@link Equivalence#IDENTITY}.
123 */
124 private final Equivalence strategy;
125
126 /**
127 * Intercept method for debugging purposes.
128 */
129 private static <K, V> EconomicMapImpl<K, V> intercept(EconomicMapImpl<K, V> map) {
130 return map;
131 }
132
133 public static <K, V> EconomicMapImpl<K, V> create(Equivalence strategy, boolean isSet) {
134 return intercept(new EconomicMapImpl<>(strategy, isSet));
135 }
136
137 public static <K, V> EconomicMapImpl<K, V> create(Equivalence strategy, int initialCapacity, boolean isSet) {
138 return intercept(new EconomicMapImpl<>(strategy, initialCapacity, isSet));
139 }
140
141 public static <K, V> EconomicMapImpl<K, V> create(Equivalence strategy, UnmodifiableEconomicMap<K, V> other, boolean isSet) {
142 return intercept(new EconomicMapImpl<>(strategy, other, isSet));
143 }
144
145 public static <K, V> EconomicMapImpl<K, V> create(Equivalence strategy, UnmodifiableEconomicSet<K> other, boolean isSet) {
146 return intercept(new EconomicMapImpl<>(strategy, other, isSet));
147 }
148
149 private EconomicMapImpl(Equivalence strategy, boolean isSet) {
150 if (strategy == Equivalence.IDENTITY) {
151 this.strategy = null;
152 } else {
153 this.strategy = strategy;
154 }
155 this.isSet = isSet;
156 }
157
158 private EconomicMapImpl(Equivalence strategy, int initialCapacity, boolean isSet) {
159 this(strategy, isSet);
160 init(initialCapacity);
161 }
162
163 private EconomicMapImpl(Equivalence strategy, UnmodifiableEconomicMap<K, V> other, boolean isSet) {
164 this(strategy, isSet);
165 if (!initFrom(other)) {
166 init(other.size());
167 putAll(other);
168 }
169 }
170
171 private EconomicMapImpl(Equivalence strategy, UnmodifiableEconomicSet<K> other, boolean isSet) {
172 this(strategy, isSet);
173 if (!initFrom(other)) {
174 init(other.size());
175 addAll(other);
176 }
177 }
178
179 @SuppressWarnings("unchecked")
180 private boolean initFrom(Object o) {
181 if (o instanceof EconomicMapImpl) {
182 EconomicMapImpl<K, V> otherMap = (EconomicMapImpl<K, V>) o;
183 // We are only allowed to directly copy if the strategies of the two maps are the same.
184 if (strategy == otherMap.strategy) {
185 totalEntries = otherMap.totalEntries;
186 deletedEntries = otherMap.deletedEntries;
187 if (otherMap.entries != null) {
188 entries = otherMap.entries.clone();
189 }
190 if (otherMap.hashArray != null) {
191 hashArray = otherMap.hashArray.clone();
192 }
193 return true;
194 }
195 }
196 return false;
197 }
198
199 private void init(int size) {
200 if (size > INITIAL_CAPACITY) {
201 entries = new Object[size << 1];
202 }
203 }
204
205 /**
206 * Links the collisions. Needs to be immutable class for allowing efficient shallow copy from
207 * other map on construction.
208 */
209 private static final class CollisionLink {
210
211 CollisionLink(Object value, int next) {
212 this.value = value;
213 this.next = next;
214 }
215
216 final Object value;
217
218 /**
219 * Index plus one of the next entry in the collision link chain.
220 */
221 final int next;
222 }
223
224 @SuppressWarnings("unchecked")
225 @Override
226 public V get(K key) {
227 Objects.requireNonNull(key);
228
229 int index = find(key);
230 if (index != -1) {
231 return (V) getValue(index);
232 }
233 return null;
234 }
235
236 private int find(K key) {
237 if (hasHashArray()) {
238 return findHash(key);
239 } else {
240 return findLinear(key);
241 }
242 }
243
244 private int findLinear(K key) {
245 for (int i = 0; i < totalEntries; i++) {
246 Object entryKey = entries[i << 1];
247 if (entryKey != null && compareKeys(key, entryKey)) {
248 return i;
249 }
250 }
251 return -1;
252 }
253
254 private boolean compareKeys(Object key, Object entryKey) {
255 if (key == entryKey) {
256 return true;
257 }
258 if (strategy != null && strategy != Equivalence.IDENTITY_WITH_SYSTEM_HASHCODE) {
259 if (strategy == Equivalence.DEFAULT) {
260 return key.equals(entryKey);
261 } else {
262 return strategy.equals(key, entryKey);
263 }
264 }
265 return false;
266 }
267
268 private int findHash(K key) {
269 int index = getHashArray(getHashIndex(key)) - 1;
270 if (index != -1) {
271 Object entryKey = getKey(index);
272 if (compareKeys(key, entryKey)) {
273 return index;
274 } else {
275 Object entryValue = getRawValue(index);
276 if (entryValue instanceof CollisionLink) {
277 return findWithCollision(key, (CollisionLink) entryValue);
278 }
279 }
280 }
281
282 return -1;
283 }
284
285 private int findWithCollision(K key, CollisionLink initialEntryValue) {
286 int index;
287 Object entryKey;
288 CollisionLink entryValue = initialEntryValue;
289 while (true) {
290 CollisionLink collisionLink = entryValue;
291 index = collisionLink.next;
292 entryKey = getKey(index);
293 if (compareKeys(key, entryKey)) {
294 return index;
295 } else {
296 Object value = getRawValue(index);
297 if (value instanceof CollisionLink) {
298 entryValue = (CollisionLink) getRawValue(index);
299 } else {
300 return -1;
301 }
302 }
303 }
304 }
305
306 private int getHashArray(int index) {
307 if (entries.length < LARGE_HASH_THRESHOLD) {
308 return (hashArray[index] & 0xFF);
309 } else if (entries.length < VERY_LARGE_HASH_THRESHOLD) {
310 int adjustedIndex = index << 1;
311 return (hashArray[adjustedIndex] & 0xFF) | ((hashArray[adjustedIndex + 1] & 0xFF) << 8);
312 } else {
313 int adjustedIndex = index << 2;
314 return (hashArray[adjustedIndex] & 0xFF) | ((hashArray[adjustedIndex + 1] & 0xFF) << 8) | ((hashArray[adjustedIndex + 2] & 0xFF) << 16) | ((hashArray[adjustedIndex + 3] & 0xFF) << 24);
315 }
316 }
317
318 private void setHashArray(int index, int value) {
319 if (entries.length < LARGE_HASH_THRESHOLD) {
320 hashArray[index] = (byte) value;
321 } else if (entries.length < VERY_LARGE_HASH_THRESHOLD) {
322 int adjustedIndex = index << 1;
323 hashArray[adjustedIndex] = (byte) value;
324 hashArray[adjustedIndex + 1] = (byte) (value >> 8);
325 } else {
326 int adjustedIndex = index << 2;
327 hashArray[adjustedIndex] = (byte) value;
328 hashArray[adjustedIndex + 1] = (byte) (value >> 8);
329 hashArray[adjustedIndex + 2] = (byte) (value >> 16);
330 hashArray[adjustedIndex + 3] = (byte) (value >> 24);
331 }
332 }
333
334 private int findAndRemoveHash(Object key) {
335 int hashIndex = getHashIndex(key);
336 int index = getHashArray(hashIndex) - 1;
337 if (index != -1) {
338 Object entryKey = getKey(index);
339 if (compareKeys(key, entryKey)) {
340 Object value = getRawValue(index);
341 int nextIndex = -1;
342 if (value instanceof CollisionLink) {
343 CollisionLink collisionLink = (CollisionLink) value;
344 nextIndex = collisionLink.next;
345 }
346 setHashArray(hashIndex, nextIndex + 1);
347 return index;
348 } else {
349 Object entryValue = getRawValue(index);
350 if (entryValue instanceof CollisionLink) {
351 return findAndRemoveWithCollision(key, (CollisionLink) entryValue, index);
352 }
353 }
354 }
355
356 return -1;
357 }
358
359 private int findAndRemoveWithCollision(Object key, CollisionLink initialEntryValue, int initialIndexValue) {
360 int index;
361 Object entryKey;
362 CollisionLink entryValue = initialEntryValue;
363 int lastIndex = initialIndexValue;
364 while (true) {
365 CollisionLink collisionLink = entryValue;
366 index = collisionLink.next;
367 entryKey = getKey(index);
368 if (compareKeys(key, entryKey)) {
369 Object value = getRawValue(index);
370 if (value instanceof CollisionLink) {
371 CollisionLink thisCollisionLink = (CollisionLink) value;
372 setRawValue(lastIndex, new CollisionLink(collisionLink.value, thisCollisionLink.next));
373 } else {
374 setRawValue(lastIndex, collisionLink.value);
375 }
376 return index;
377 } else {
378 Object value = getRawValue(index);
379 if (value instanceof CollisionLink) {
380 entryValue = (CollisionLink) getRawValue(index);
381 lastIndex = index;
382 } else {
383 return -1;
384 }
385 }
386 }
387 }
388
389 private int getHashIndex(Object key) {
390 int hash;
391 if (strategy != null && strategy != Equivalence.DEFAULT) {
392 if (strategy == Equivalence.IDENTITY_WITH_SYSTEM_HASHCODE) {
393 hash = System.identityHashCode(key);
394 } else {
395 hash = strategy.hashCode(key);
396 }
397 } else {
398 hash = key.hashCode();
399 }
400 hash = hash ^ (hash >>> 16);
401 return hash & (getHashTableSize() - 1);
402 }
403
404 @SuppressWarnings("unchecked")
405 @Override
406 public V put(K key, V value) {
407 if (key == null) {
408 throw new UnsupportedOperationException("null not supported as key!");
409 }
410 int index = find(key);
411 if (index != -1) {
412 Object oldValue = getValue(index);
413 setValue(index, value);
414 return (V) oldValue;
415 }
416
417 int nextEntryIndex = totalEntries;
418 if (entries == null) {
419 entries = new Object[INITIAL_CAPACITY << 1];
420 } else if (entries.length == nextEntryIndex << 1) {
421 grow();
422
423 assert entries.length > totalEntries << 1;
424 // Can change if grow is actually compressing.
425 nextEntryIndex = totalEntries;
426 }
427
428 setKey(nextEntryIndex, key);
429 setValue(nextEntryIndex, value);
430 totalEntries++;
431
432 if (hasHashArray()) {
433 // Rehash on collision if hash table is more than three quarters full.
434 boolean rehashOnCollision = (getHashTableSize() < (size() + (size() >> 1)));
435 putHashEntry(key, nextEntryIndex, rehashOnCollision);
436 } else if (totalEntries > getHashThreshold()) {
437 createHash();
438 }
439
440 return null;
441 }
442
443 /**
444 * Number of entries above which a hash table should be constructed.
445 */
446 private int getHashThreshold() {
447 if (strategy == null || strategy == Equivalence.IDENTITY_WITH_SYSTEM_HASHCODE) {
448 return HASH_THRESHOLD_IDENTITY_COMPARE;
449 } else {
450 return HASH_THRESHOLD;
451 }
452 }
453
454 private void grow() {
455 int entriesLength = entries.length;
456 int newSize = (entriesLength >> 1) + Math.max(MIN_CAPACITY_INCREASE, entriesLength >> 2);
457 if (newSize > MAX_ELEMENT_COUNT) {
458 throw new UnsupportedOperationException("map grown too large!");
459 }
460 Object[] newEntries = new Object[newSize << 1];
461 System.arraycopy(entries, 0, newEntries, 0, entriesLength);
462 entries = newEntries;
463 if ((entriesLength < LARGE_HASH_THRESHOLD && newEntries.length >= LARGE_HASH_THRESHOLD) ||
464 (entriesLength < VERY_LARGE_HASH_THRESHOLD && newEntries.length > VERY_LARGE_HASH_THRESHOLD)) {
465 // Rehash in order to change number of bits reserved for hash indices.
466 createHash();
467 }
468 }
469
470 /**
471 * Compresses the graph if there is a large number of deleted entries and returns the translated
472 * new next index.
473 */
474 private int maybeCompress(int nextIndex) {
475 if (entries.length != INITIAL_CAPACITY << 1 && deletedEntries >= (totalEntries >> 1) + (totalEntries >> 2)) {
476 return compressLarge(nextIndex);
477 }
478 return nextIndex;
479 }
480
481 /**
482 * Compresses the graph and returns the translated new next index.
483 */
484 private int compressLarge(int nextIndex) {
485 int size = INITIAL_CAPACITY;
486 int remaining = totalEntries - deletedEntries;
487
488 while (size <= remaining) {
489 size += Math.max(MIN_CAPACITY_INCREASE, size >> 1);
490 }
491
492 Object[] newEntries = new Object[size << 1];
493 int z = 0;
494 int newNextIndex = remaining;
495 for (int i = 0; i < totalEntries; ++i) {
496 Object key = getKey(i);
497 if (i == nextIndex) {
498 newNextIndex = z;
499 }
500 if (key != null) {
501 newEntries[z << 1] = key;
502 newEntries[(z << 1) + 1] = getValue(i);
503 z++;
504 }
505 }
506
507 this.entries = newEntries;
508 totalEntries = z;
509 deletedEntries = 0;
510 if (z <= getHashThreshold()) {
511 this.hashArray = null;
512 } else {
513 createHash();
514 }
515 return newNextIndex;
516 }
517
518 private int getHashTableSize() {
519 if (entries.length < LARGE_HASH_THRESHOLD) {
520 return hashArray.length;
521 } else if (entries.length < VERY_LARGE_HASH_THRESHOLD) {
522 return hashArray.length >> 1;
523 } else {
524 return hashArray.length >> 2;
525 }
526 }
527
528 private void createHash() {
529 int entryCount = size();
530
531 // Calculate smallest 2^n that is greater number of entries.
532 int size = getHashThreshold();
533 while (size <= entryCount) {
534 size <<= 1;
535 }
536
537 // Give extra size to avoid collisions.
538 size <<= 1;
539
540 if (this.entries.length >= VERY_LARGE_HASH_THRESHOLD) {
541 // Every entry has 4 bytes.
542 size <<= 2;
543 } else if (this.entries.length >= LARGE_HASH_THRESHOLD) {
544 // Every entry has 2 bytes.
545 size <<= 1;
546 } else {
547 // Entries are very small => give extra size to further reduce collisions.
548 size <<= 1;
549 }
550
551 hashArray = new byte[size];
552 for (int i = 0; i < totalEntries; i++) {
553 Object entryKey = getKey(i);
554 if (entryKey != null) {
555 putHashEntry(entryKey, i, false);
556 }
557 }
558 }
559
560 private void putHashEntry(Object key, int entryIndex, boolean rehashOnCollision) {
561 int hashIndex = getHashIndex(key);
562 int oldIndex = getHashArray(hashIndex) - 1;
563 if (oldIndex != -1 && rehashOnCollision) {
564 this.createHash();
565 return;
566 }
567 setHashArray(hashIndex, entryIndex + 1);
568 Object value = getRawValue(entryIndex);
569 if (oldIndex != -1) {
570 assert entryIndex != oldIndex : "this cannot happend and would create an endless collision link cycle";
571 if (value instanceof CollisionLink) {
572 CollisionLink collisionLink = (CollisionLink) value;
573 setRawValue(entryIndex, new CollisionLink(collisionLink.value, oldIndex));
574 } else {
575 setRawValue(entryIndex, new CollisionLink(getRawValue(entryIndex), oldIndex));
576 }
577 } else {
578 if (value instanceof CollisionLink) {
579 CollisionLink collisionLink = (CollisionLink) value;
580 setRawValue(entryIndex, collisionLink.value);
581 }
582 }
583 }
584
585 @Override
586 public int size() {
587 return totalEntries - deletedEntries;
588 }
589
590 @Override
591 public boolean containsKey(K key) {
592 return find(key) != -1;
593 }
594
595 @Override
596 public void clear() {
597 entries = null;
598 hashArray = null;
599 totalEntries = deletedEntries = 0;
600 }
601
602 private boolean hasHashArray() {
603 return hashArray != null;
604 }
605
606 @SuppressWarnings("unchecked")
607 @Override
608 public V removeKey(K key) {
609 if (key == null) {
610 throw new UnsupportedOperationException("null not supported as key!");
611 }
612 int index;
613 if (hasHashArray()) {
614 index = this.findAndRemoveHash(key);
615 } else {
616 index = this.findLinear(key);
617 }
618
619 if (index != -1) {
620 Object value = getValue(index);
621 remove(index);
622 return (V) value;
623 }
624 return null;
625 }
626
627 /**
628 * Removes the element at the specific index and returns the index of the next element. This can
629 * be a different value if graph compression was triggered.
630 */
631 private int remove(int indexToRemove) {
632 int index = indexToRemove;
633 int entriesAfterIndex = totalEntries - index - 1;
634 int result = index + 1;
635
636 // Without hash array, compress immediately.
637 if (entriesAfterIndex <= COMPRESS_IMMEDIATE_CAPACITY && !hasHashArray()) {
638 while (index < totalEntries - 1) {
639 setKey(index, getKey(index + 1));
640 setRawValue(index, getRawValue(index + 1));
641 index++;
642 }
643 result--;
644 }
645
646 setKey(index, null);
647 setRawValue(index, null);
648 if (index == totalEntries - 1) {
649 // Make sure last element is always non-null.
650 totalEntries--;
651 while (index > 0 && getKey(index - 1) == null) {
652 totalEntries--;
653 deletedEntries--;
654 index--;
655 }
656 } else {
657 deletedEntries++;
658 result = maybeCompress(result);
659 }
660
661 return result;
662 }
663
664 private abstract class SparseMapIterator<E> implements Iterator<E> {
665
666 protected int current;
667
668 @Override
669 public boolean hasNext() {
670 return current < totalEntries;
671 }
672
673 @Override
674 public void remove() {
675 if (hasHashArray()) {
676 EconomicMapImpl.this.findAndRemoveHash(getKey(current - 1));
677 }
678 current = EconomicMapImpl.this.remove(current - 1);
679 }
680 }
681
682 @Override
683 public Iterable<V> getValues() {
684 return new Iterable<V>() {
685 @Override
686 public Iterator<V> iterator() {
687 return new SparseMapIterator<V>() {
688 @SuppressWarnings("unchecked")
689 @Override
690 public V next() {
691 Object result;
692 while (true) {
693 result = getValue(current);
694 if (result == null && getKey(current) == null) {
695 // values can be null, double-check if key is also null
696 current++;
697 } else {
698 current++;
699 break;
700 }
701 }
702 return (V) result;
703 }
704 };
705 }
706 };
707 }
708
709 @Override
710 public Iterable<K> getKeys() {
711 return this;
712 }
713
714 @Override
715 public boolean isEmpty() {
716 return this.size() == 0;
717 }
718
719 @Override
720 public MapCursor<K, V> getEntries() {
721 return new MapCursor<K, V>() {
722 int current = -1;
723
724 @Override
725 public boolean advance() {
726 current++;
727 if (current >= totalEntries) {
728 return false;
729 } else {
730 while (EconomicMapImpl.this.getKey(current) == null) {
731 // Skip over null entries
732 current++;
733 }
734 return true;
735 }
736 }
737
738 @SuppressWarnings("unchecked")
739 @Override
740 public K getKey() {
741 return (K) EconomicMapImpl.this.getKey(current);
742 }
743
744 @SuppressWarnings("unchecked")
745 @Override
746 public V getValue() {
747 return (V) EconomicMapImpl.this.getValue(current);
748 }
749
750 @Override
751 public void remove() {
752 if (hasHashArray()) {
753 EconomicMapImpl.this.findAndRemoveHash(EconomicMapImpl.this.getKey(current));
754 }
755 current = EconomicMapImpl.this.remove(current) - 1;
756 }
757 };
758 }
759
760 @SuppressWarnings("unchecked")
761 @Override
762 public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
763 for (int i = 0; i < totalEntries; i++) {
764 Object entryKey = getKey(i);
765 if (entryKey != null) {
766 Object newValue = function.apply((K) entryKey, (V) getValue(i));
767 setValue(i, newValue);
768 }
769 }
770 }
771
772 private Object getKey(int index) {
773 return entries[index << 1];
774 }
775
776 private void setKey(int index, Object newValue) {
777 entries[index << 1] = newValue;
778 }
779
780 private void setValue(int index, Object newValue) {
781 Object oldValue = getRawValue(index);
782 if (oldValue instanceof CollisionLink) {
783 CollisionLink collisionLink = (CollisionLink) oldValue;
784 setRawValue(index, new CollisionLink(newValue, collisionLink.next));
785 } else {
786 setRawValue(index, newValue);
787 }
788 }
789
790 private void setRawValue(int index, Object newValue) {
791 entries[(index << 1) + 1] = newValue;
792 }
793
794 private Object getRawValue(int index) {
795 return entries[(index << 1) + 1];
796 }
797
798 private Object getValue(int index) {
799 Object object = getRawValue(index);
800 if (object instanceof CollisionLink) {
801 return ((CollisionLink) object).value;
802 }
803 return object;
804 }
805
806 private final boolean isSet;
807
808 @Override
809 public String toString() {
810 StringBuilder builder = new StringBuilder();
811 builder.append(isSet ? "set(size=" : "map(size=").append(size()).append(", {");
812 String sep = "";
813 MapCursor<K, V> cursor = getEntries();
814 while (cursor.advance()) {
815 builder.append(sep);
816 if (isSet) {
817 builder.append(cursor.getKey());
818 } else {
819 builder.append("(").append(cursor.getKey()).append(",").append(cursor.getValue()).append(")");
820 }
821 sep = ",";
822 }
823 builder.append("})");
824 return builder.toString();
825 }
826
827 @Override
828 public Iterator<K> iterator() {
829 return new SparseMapIterator<K>() {
830 @SuppressWarnings("unchecked")
831 @Override
832 public K next() {
833 Object result;
834 while ((result = getKey(current++)) == null) {
835 // skip null entries
836 }
837 return (K) result;
838 }
839 };
840 }
841
842 @Override
843 public boolean contains(K element) {
844 return containsKey(element);
845 }
846
847 @SuppressWarnings("unchecked")
848 @Override
849 public boolean add(K element) {
850 return put(element, (V) element) == null;
851 }
852
853 @Override
854 public void remove(K element) {
855 removeKey(element);
856 }
857 }