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