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 package org.graalvm.util.impl;

    24 

    25 import java.util.Iterator;

    26 import java.util.Objects;

    27 import java.util.function.BiFunction;

    28 

    29 import org.graalvm.util.Equivalence;

    30 import org.graalvm.util.EconomicMap;

    31 import org.graalvm.util.EconomicSet;

    32 import org.graalvm.util.UnmodifiableEconomicMap;

    33 import org.graalvm.util.UnmodifiableEconomicSet;

    34 import org.graalvm.util.MapCursor;

    35 

    36 /**

    37  * Implementation of a map with a memory-efficient structure that always preserves insertion order

    38  * when iterating over keys. Particularly efficient when number of entries is 0 or smaller equal

    39  * {@link #INITIAL_CAPACITY} or smaller 256.

    40  *

    41  * The key/value pairs are kept in an expanding flat object array with keys at even indices and

    42  * values at odd indices. If the map has smaller or equal to {@link #HASH_THRESHOLD} entries, there

    43  * is no additional hash data structure and comparisons are done via linear checking of the

    44  * key/value pairs. For the case where the equality check is particularly cheap (e.g., just an

    45  * object identity comparison), this limit below which the map is without an actual hash table is

    46  * higher and configured at {@link #HASH_THRESHOLD_IDENTITY_COMPARE}.

    47  *

    48  * When the hash table needs to be constructed, the field {@link #hashArray} becomes a new hash

    49  * array where an entry of 0 means no hit and otherwise denotes the entry number in the

    50  * {@link #entries} array. The hash array is interpreted as an actual byte array if the indices fit

    51  * within 8 bit, or as an array of short values if the indices fit within 16 bit, or as an array of

    52  * integer values in other cases.

    53  *

    54  * Hash collisions are handled by chaining a linked list of {@link CollisionLink} objects that take

    55  * the place of the values in the {@link #entries} array.

    56  *

    57  * Removing entries will put {@code null} into the {@link #entries} array. If the occupation of the

    58  * map falls below a specific threshold, the map will be compressed via the

    59  * {@link #maybeCompress(int)} method.

    60  */

    61 public final class EconomicMapImpl<K, V> implements EconomicMap<K, V>, EconomicSet<K> {

    62 

    63     /**

    64      * Initial number of key/value pair entries that is allocated in the first entries array.

    65      */

    66     private static final int INITIAL_CAPACITY = 4;

    67 

    68     /**

    69      * Maximum number of entries that are moved linearly forward if a key is removed.

    70      */

    71     private static final int COMPRESS_IMMEDIATE_CAPACITY = 8;

    72 

    73     /**

    74      * Minimum number of key/value pair entries added when the entries array is increased in size.

    75      */

    76     private static final int MIN_CAPACITY_INCREASE = 8;

    77 

    78     /**

    79      * Number of entries above which a hash table is created.

    80      */

    81     private static final int HASH_THRESHOLD = 4;

    82 

    83     /**

    84      * Number of entries above which a hash table is created when equality can be checked with

    85      * object identity.

    86      */

    87     private static final int HASH_THRESHOLD_IDENTITY_COMPARE = 8;

    88 

    89     /**

    90      * Maximum number of entries allowed in the map.

    91      */

    92     private static final int MAX_ELEMENT_COUNT = Integer.MAX_VALUE >> 1;

    93 

    94     /**

    95      * Number of entries above which more than 1 byte is necessary for the hash index.

    96      */

    97     private static final int LARGE_HASH_THRESHOLD = ((1 << Byte.SIZE) << 1);

    98 

    99     /**

   100      * Number of entries above which more than 2 bytes are are necessary for the hash index.

   101      */

   102     private static final int VERY_LARGE_HASH_THRESHOLD = (LARGE_HASH_THRESHOLD << Byte.SIZE);

   103 

   104     /**

   105      * Total number of entries (actual entries plus deleted entries).

   106      */

   107     private int totalEntries;

   108 

   109     /**

   110      * Number of deleted entries.

   111      */

   112     private int deletedEntries;

   113 

   114     /**

   115      * Entries array with even indices storing keys and odd indices storing values.

   116      */

   117     private Object[] entries;

   118 

   119     /**

   120      * Hash array that is interpreted either as byte or short or int array depending on number of

   121      * map entries.

   122      */

   123     private byte[] hashArray;

   124 

   125     /**

   126      * The strategy used for comparing keys or {@code null} for denoting special strategy

   127      * {@link Equivalence#IDENTITY}.

   128      */

   129     private final Equivalence strategy;

   130 

   131     /**

   132      * Intercept method for debugging purposes.

   133      */

   134     private static <K, V> EconomicMapImpl<K, V> intercept(EconomicMapImpl<K, V> map) {

   135         return map;

   136     }

   137 

   138     public static <K, V> EconomicMapImpl<K, V> create(Equivalence strategy) {

   139         return intercept(new EconomicMapImpl<>(strategy));

   140     }

   141 

   142     public static <K, V> EconomicMapImpl<K, V> create(Equivalence strategy, int initialCapacity) {

   143         return intercept(new EconomicMapImpl<>(strategy, initialCapacity));

   144     }

   145 

   146     public static <K, V> EconomicMapImpl<K, V> create(Equivalence strategy, UnmodifiableEconomicMap<K, V> other) {

   147         return intercept(new EconomicMapImpl<>(strategy, other));

   148     }

   149 

   150     public static <K, V> EconomicMapImpl<K, V> create(Equivalence strategy, UnmodifiableEconomicSet<K> other) {

   151         return intercept(new EconomicMapImpl<>(strategy, other));

   152     }

   153 

   154     private EconomicMapImpl(Equivalence strategy) {

   155         if (strategy == Equivalence.IDENTITY) {

   156             this.strategy = null;

   157         } else {

   158             this.strategy = strategy;

   159         }

   160     }

   161 

   162     private EconomicMapImpl(Equivalence strategy, int initialCapacity) {

   163         this(strategy);

   164         init(initialCapacity);

   165     }

   166 

   167     private EconomicMapImpl(Equivalence strategy, UnmodifiableEconomicMap<K, V> other) {

   168         this(strategy);

   169         if (!initFrom(other)) {

   170             init(other.size());

   171             putAll(other);

   172         }

   173     }

   174 

   175     private EconomicMapImpl(Equivalence strategy, UnmodifiableEconomicSet<K> other) {

   176         this(strategy);

   177         if (!initFrom(other)) {

   178             init(other.size());

   179             addAll(other);

   180         }

   181     }

   182 

   183     @SuppressWarnings("unchecked")

   184     private boolean initFrom(Object o) {

   185         if (o instanceof EconomicMapImpl) {

   186             EconomicMapImpl<K, V> otherMap = (EconomicMapImpl<K, V>) o;

   187             // We are only allowed to directly copy if the strategies of the two maps are the same.

   188             if (strategy == otherMap.strategy) {

   189                 totalEntries = otherMap.totalEntries;

   190                 deletedEntries = otherMap.deletedEntries;

   191                 if (otherMap.entries != null) {

   192                     entries = otherMap.entries.clone();

   193                 }

   194                 if (otherMap.hashArray != null) {

   195                     hashArray = otherMap.hashArray.clone();

   196                 }

   197                 return true;

   198             }

   199         }

   200         return false;

   201     }

   202 

   203     private void init(int size) {

   204         if (size > INITIAL_CAPACITY) {

   205             entries = new Object[size << 1];

   206         }

   207     }

   208 

   209     /**

   210      * Links the collisions. Needs to be immutable class for allowing efficient shallow copy from

   211      * other map on construction.

   212      */

   213     private static final class CollisionLink {

   214 

   215         CollisionLink(Object value, int next) {

   216             this.value = value;

   217             this.next = next;

   218         }

   219 

   220         final Object value;

   221 

   222         /**

   223          * Index plus one of the next entry in the collision link chain.

   224          */

   225         final int next;

   226     }

   227 

   228     @SuppressWarnings("unchecked")

   229     @Override

   230     public V get(K key) {

   231         Objects.requireNonNull(key);

   232 

   233         int index = find(key);

   234         if (index != -1) {

   235             return (V) getValue(index);

   236         }

   237         return null;

   238     }

   239 

   240     private int find(K key) {

   241         if (hasHashArray()) {

   242             return findHash(key);

   243         } else {

   244             return findLinear(key);

   245         }

   246     }

   247 

   248     private int findLinear(K key) {

   249         for (int i = 0; i < totalEntries; i++) {

   250             Object entryKey = entries[i << 1];

   251             if (entryKey != null && compareKeys(key, entryKey)) {

   252                 return i;

   253             }

   254         }

   255         return -1;

   256     }

   257 

   258     private boolean compareKeys(Object key, Object entryKey) {

   259         if (key == entryKey) {

   260             return true;

   261         }

   262         if (strategy != null && strategy != Equivalence.IDENTITY_WITH_SYSTEM_HASHCODE) {

   263             if (strategy == Equivalence.DEFAULT) {

   264                 return key.equals(entryKey);

   265             } else {

   266                 return strategy.equals(key, entryKey);

   267             }

   268         }

   269         return false;

   270     }

   271 

   272     private int findHash(K key) {

   273         int index = getHashArray(getHashIndex(key)) - 1;

   274         if (index != -1) {

   275             Object entryKey = getKey(index);

   276             if (compareKeys(key, entryKey)) {

   277                 return index;

   278             } else {

   279                 Object entryValue = getRawValue(index);

   280                 if (entryValue instanceof CollisionLink) {

   281                     return findWithCollision(key, (CollisionLink) entryValue);

   282                 }

   283             }

   284         }

   285 

   286         return -1;

   287     }

   288 

   289     private int findWithCollision(K key, CollisionLink initialEntryValue) {

   290         int index;

   291         Object entryKey;

   292         CollisionLink entryValue = initialEntryValue;

   293         while (true) {

   294             CollisionLink collisionLink = entryValue;

   295             index = collisionLink.next;

   296             entryKey = getKey(index);

   297             if (compareKeys(key, entryKey)) {

   298                 return index;

   299             } else {

   300                 Object value = getRawValue(index);

   301                 if (value instanceof CollisionLink) {

   302                     entryValue = (CollisionLink) getRawValue(index);

   303                 } else {

   304                     return -1;

   305                 }

   306             }

   307         }

   308     }

   309 

   310     private int getHashArray(int index) {

   311         if (entries.length < LARGE_HASH_THRESHOLD) {

   312             return (hashArray[index] & 0xFF);

   313         } else if (entries.length < VERY_LARGE_HASH_THRESHOLD) {

   314             int adjustedIndex = index << 1;

   315             return (hashArray[adjustedIndex] & 0xFF) | ((hashArray[adjustedIndex + 1] & 0xFF) << 8);

   316         } else {

   317             int adjustedIndex = index << 2;

   318             return (hashArray[adjustedIndex] & 0xFF) | ((hashArray[adjustedIndex + 1] & 0xFF) << 8) | ((hashArray[adjustedIndex + 2] & 0xFF) << 16) | ((hashArray[adjustedIndex + 3] & 0xFF) << 24);

   319         }

   320     }

   321 

   322     private void setHashArray(int index, int value) {

   323         if (entries.length < LARGE_HASH_THRESHOLD) {

   324             hashArray[index] = (byte) value;

   325         } else if (entries.length < VERY_LARGE_HASH_THRESHOLD) {

   326             int adjustedIndex = index << 1;

   327             hashArray[adjustedIndex] = (byte) value;

   328             hashArray[adjustedIndex + 1] = (byte) (value >> 8);

   329         } else {

   330             int adjustedIndex = index << 2;

   331             hashArray[adjustedIndex] = (byte) value;

   332             hashArray[adjustedIndex + 1] = (byte) (value >> 8);

   333             hashArray[adjustedIndex + 2] = (byte) (value >> 16);

   334             hashArray[adjustedIndex + 3] = (byte) (value >> 24);

   335         }

   336     }

   337 

   338     private int findAndRemoveHash(Object key) {

   339         int hashIndex = getHashIndex(key);

   340         int index = getHashArray(hashIndex) - 1;

   341         if (index != -1) {

   342             Object entryKey = getKey(index);

   343             if (compareKeys(key, entryKey)) {

   344                 Object value = getRawValue(index);

   345                 int nextIndex = -1;

   346                 if (value instanceof CollisionLink) {

   347                     CollisionLink collisionLink = (CollisionLink) value;

   348                     nextIndex = collisionLink.next;

   349                 }

   350                 setHashArray(hashIndex, nextIndex + 1);

   351                 return index;

   352             } else {

   353                 Object entryValue = getRawValue(index);

   354                 if (entryValue instanceof CollisionLink) {

   355                     return findAndRemoveWithCollision(key, (CollisionLink) entryValue, index);

   356                 }

   357             }

   358         }

   359 

   360         return -1;

   361     }

   362 

   363     private int findAndRemoveWithCollision(Object key, CollisionLink initialEntryValue, int initialIndexValue) {

   364         int index;

   365         Object entryKey;

   366         CollisionLink entryValue = initialEntryValue;

   367         int lastIndex = initialIndexValue;

   368         while (true) {

   369             CollisionLink collisionLink = entryValue;

   370             index = collisionLink.next;

   371             entryKey = getKey(index);

   372             if (compareKeys(key, entryKey)) {

   373                 Object value = getRawValue(index);

   374                 if (value instanceof CollisionLink) {

   375                     CollisionLink thisCollisionLink = (CollisionLink) value;

   376                     setRawValue(lastIndex, new CollisionLink(collisionLink.value, thisCollisionLink.next));

   377                 } else {

   378                     setRawValue(lastIndex, collisionLink.value);

   379                 }

   380                 return index;

   381             } else {

   382                 Object value = getRawValue(index);

   383                 if (value instanceof CollisionLink) {

   384                     entryValue = (CollisionLink) getRawValue(index);

   385                     lastIndex = index;

   386                 } else {

   387                     return -1;

   388                 }

   389             }

   390         }

   391     }

   392 

   393     private int getHashIndex(Object key) {

   394         int hash;

   395         if (strategy != null && strategy != Equivalence.DEFAULT) {

   396             if (strategy == Equivalence.IDENTITY_WITH_SYSTEM_HASHCODE) {

   397                 hash = System.identityHashCode(key);

   398             } else {

   399                 hash = strategy.hashCode(key);

   400             }

   401         } else {

   402             hash = key.hashCode();

   403         }

   404         hash = hash ^ (hash >>> 16);

   405         return hash & (getHashTableSize() - 1);

   406     }

   407 

   408     @SuppressWarnings("unchecked")

   409     @Override

   410     public V put(K key, V value) {

   411         if (key == null) {

   412             throw new UnsupportedOperationException("null not supported as key!");

   413         }

   414         int index = find(key);

   415         if (index != -1) {

   416             Object oldValue = getValue(index);

   417             setValue(index, value);

   418             return (V) oldValue;

   419         }

   420 

   421         int nextEntryIndex = totalEntries;

   422         if (entries == null) {

   423             entries = new Object[INITIAL_CAPACITY << 1];

   424         } else if (entries.length == nextEntryIndex << 1) {

   425             grow();

   426 

   427             assert entries.length > totalEntries << 1;

   428             // Can change if grow is actually compressing.

   429             nextEntryIndex = totalEntries;

   430         }

   431 

   432         setKey(nextEntryIndex, key);

   433         setValue(nextEntryIndex, value);

   434         totalEntries++;

   435 

   436         if (hasHashArray()) {

   437             // Rehash on collision if hash table is more than three quarters full.

   438             boolean rehashOnCollision = (getHashTableSize() < (size() + (size() >> 1)));

   439             putHashEntry(key, nextEntryIndex, rehashOnCollision);

   440         } else if (totalEntries > getHashThreshold()) {

   441             createHash();

   442         }

   443 

   444         return null;

   445     }

   446 

   447     /**

   448      * Number of entries above which a hash table should be constructed.

   449      */

   450     private int getHashThreshold() {

   451         if (strategy == null || strategy == Equivalence.IDENTITY_WITH_SYSTEM_HASHCODE) {

   452             return HASH_THRESHOLD_IDENTITY_COMPARE;

   453         } else {

   454             return HASH_THRESHOLD;

   455         }

   456     }

   457 

   458     private void grow() {

   459         int entriesLength = entries.length;

   460         int newSize = (entriesLength >> 1) + Math.max(MIN_CAPACITY_INCREASE, entriesLength >> 2);

   461         if (newSize > MAX_ELEMENT_COUNT) {

   462             throw new UnsupportedOperationException("map grown too large!");

   463         }

   464         Object[] newEntries = new Object[newSize << 1];

   465         System.arraycopy(entries, 0, newEntries, 0, entriesLength);

   466         entries = newEntries;

   467         if ((entriesLength < LARGE_HASH_THRESHOLD && newEntries.length >= LARGE_HASH_THRESHOLD) ||

   468                         (entriesLength < VERY_LARGE_HASH_THRESHOLD && newEntries.length > VERY_LARGE_HASH_THRESHOLD)) {

   469             // Rehash in order to change number of bits reserved for hash indices.

   470             createHash();

   471         }

   472     }

   473 

   474     /**

   475      * Compresses the graph if there is a large number of deleted entries and returns the translated

   476      * new next index.

   477      */

   478     private int maybeCompress(int nextIndex) {

   479         if (entries.length != INITIAL_CAPACITY << 1 && deletedEntries >= (totalEntries >> 1) + (totalEntries >> 2)) {

   480             return compressLarge(nextIndex);

   481         }

   482         return nextIndex;

   483     }

   484 

   485     /**

   486      * Compresses the graph and returns the translated new next index.

   487      */

   488     private int compressLarge(int nextIndex) {

   489         int size = INITIAL_CAPACITY;

   490         int remaining = totalEntries - deletedEntries;

   491 

   492         while (size <= remaining) {

   493             size += Math.max(MIN_CAPACITY_INCREASE, size >> 1);

   494         }

   495 

   496         Object[] newEntries = new Object[size << 1];

   497         int z = 0;

   498         int newNextIndex = remaining;

   499         for (int i = 0; i < totalEntries; ++i) {

   500             Object key = getKey(i);

   501             if (i == nextIndex) {

   502                 newNextIndex = z;

   503             }

   504             if (key != null) {

   505                 newEntries[z << 1] = key;

   506                 newEntries[(z << 1) + 1] = getValue(i);

   507                 z++;

   508             }

   509         }

   510 

   511         this.entries = newEntries;

   512         totalEntries = z;

   513         deletedEntries = 0;

   514         if (z <= getHashThreshold()) {

   515             this.hashArray = null;

   516         } else {

   517             createHash();

   518         }

   519         return newNextIndex;

   520     }

   521 

   522     private int getHashTableSize() {

   523         if (entries.length < LARGE_HASH_THRESHOLD) {

   524             return hashArray.length;

   525         } else if (entries.length < VERY_LARGE_HASH_THRESHOLD) {

   526             return hashArray.length >> 1;

   527         } else {

   528             return hashArray.length >> 2;

   529         }

   530     }

   531 

   532     private void createHash() {

   533         int entryCount = size();

   534 

   535         // Calculate smallest 2^n that is greater number of entries.

   536         int size = getHashThreshold();

   537         while (size <= entryCount) {

   538             size <<= 1;

   539         }

   540 

   541         // Give extra size to avoid collisions.

   542         size <<= 1;

   543 

   544         if (this.entries.length >= VERY_LARGE_HASH_THRESHOLD) {

   545             // Every entry has 4 bytes.

   546             size <<= 2;

   547         } else if (this.entries.length >= LARGE_HASH_THRESHOLD) {

   548             // Every entry has 2 bytes.

   549             size <<= 1;

   550         } else {

   551             // Entries are very small => give extra size to further reduce collisions.

   552             size <<= 1;

   553         }

   554 

   555         hashArray = new byte[size];

   556         for (int i = 0; i < totalEntries; i++) {

   557             Object entryKey = getKey(i);

   558             if (entryKey != null) {

   559                 putHashEntry(entryKey, i, false);

   560             }

   561         }

   562     }

   563 

   564     private void putHashEntry(Object key, int entryIndex, boolean rehashOnCollision) {

   565         int hashIndex = getHashIndex(key);

   566         int oldIndex = getHashArray(hashIndex) - 1;

   567         if (oldIndex != -1 && rehashOnCollision) {

   568             this.createHash();

   569             return;

   570         }

   571         setHashArray(hashIndex, entryIndex + 1);

   572         Object value = getRawValue(entryIndex);

   573         if (oldIndex != -1) {

   574             assert entryIndex != oldIndex : "this cannot happend and would create an endless collision link cycle";

   575             if (value instanceof CollisionLink) {

   576                 CollisionLink collisionLink = (CollisionLink) value;

   577                 setRawValue(entryIndex, new CollisionLink(collisionLink.value, oldIndex));

   578             } else {

   579                 setRawValue(entryIndex, new CollisionLink(getRawValue(entryIndex), oldIndex));

   580             }

   581         } else {

   582             if (value instanceof CollisionLink) {

   583                 CollisionLink collisionLink = (CollisionLink) value;

   584                 setRawValue(entryIndex, collisionLink.value);

   585             }

   586         }

   587     }

   588 

   589     @Override

   590     public int size() {

   591         return totalEntries - deletedEntries;

   592     }

   593 

   594     @Override

   595     public boolean containsKey(K key) {

   596         return find(key) != -1;

   597     }

   598 

   599     @Override

   600     public void clear() {

   601         entries = null;

   602         hashArray = null;

   603         totalEntries = deletedEntries = 0;

   604     }

   605 

   606     private boolean hasHashArray() {

   607         return hashArray != null;

   608     }

   609 

   610     @SuppressWarnings("unchecked")

   611     @Override

   612     public V removeKey(K key) {

   613         if (key == null) {

   614             throw new UnsupportedOperationException("null not supported as key!");

   615         }

   616         int index;

   617         if (hasHashArray()) {

   618             index = this.findAndRemoveHash(key);

   619         } else {

   620             index = this.findLinear(key);

   621         }

   622 

   623         if (index != -1) {

   624             Object value = getValue(index);

   625             remove(index);

   626             return (V) value;

   627         }

   628         return null;

   629     }

   630 

   631     /**

   632      * Removes the element at the specific index and returns the index of the next element. This can

   633      * be a different value if graph compression was triggered.

   634      */

   635     private int remove(int indexToRemove) {

   636         int index = indexToRemove;

   637         int entriesAfterIndex = totalEntries - index - 1;

   638         int result = index + 1;

   639 

   640         // Without hash array, compress immediately.

   641         if (entriesAfterIndex <= COMPRESS_IMMEDIATE_CAPACITY && !hasHashArray()) {

   642             while (index < totalEntries - 1) {

   643                 setKey(index, getKey(index + 1));

   644                 setRawValue(index, getRawValue(index + 1));

   645                 index++;

   646             }

   647             result--;

   648         }

   649 

   650         setKey(index, null);

   651         setRawValue(index, null);

   652         if (index == totalEntries - 1) {

   653             // Make sure last element is always non-null.

   654             totalEntries--;

   655             while (index > 0 && getKey(index - 1) == null) {

   656                 totalEntries--;

   657                 deletedEntries--;

   658                 index--;

   659             }

   660         } else {

   661             deletedEntries++;

   662             result = maybeCompress(result);

   663         }

   664 

   665         return result;

   666     }

   667 

   668     private abstract class SparseMapIterator<E> implements Iterator<E> {

   669 

   670         protected int current;

   671 

   672         @Override

   673         public boolean hasNext() {

   674             return current < totalEntries;

   675         }

   676 

   677         @Override

   678         public void remove() {

   679             if (hasHashArray()) {

   680                 EconomicMapImpl.this.findAndRemoveHash(getKey(current - 1));

   681             }

   682             current = EconomicMapImpl.this.remove(current - 1);

   683         }

   684     }

   685 

   686     @Override

   687     public Iterable<V> getValues() {

   688         return new Iterable<V>() {

   689             @Override

   690             public Iterator<V> iterator() {

   691                 return new SparseMapIterator<V>() {

   692                     @SuppressWarnings("unchecked")

   693                     @Override

   694                     public V next() {

   695                         Object result;

   696                         while (true) {

   697                             result = getValue(current);

   698                             if (result == null && getKey(current) == null) {

   699                                 // values can be null, double-check if key is also null

   700                                 current++;

   701                             } else {

   702                                 current++;

   703                                 break;

   704                             }

   705                         }

   706                         return (V) result;

   707                     }

   708                 };

   709             }

   710         };

   711     }

   712 

   713     @Override

   714     public Iterable<K> getKeys() {

   715         return this;

   716     }

   717 

   718     @Override

   719     public boolean isEmpty() {

   720         return this.size() == 0;

   721     }

   722 

   723     @Override

   724     public MapCursor<K, V> getEntries() {

   725         return new MapCursor<K, V>() {

   726             int current = -1;

   727 

   728             @Override

   729             public boolean advance() {

   730                 current++;

   731                 if (current >= totalEntries) {

   732                     return false;

   733                 } else {

   734                     while (EconomicMapImpl.this.getKey(current) == null) {

   735                         // Skip over null entries

   736                         current++;

   737                     }

   738                     return true;

   739                 }

   740             }

   741 

   742             @SuppressWarnings("unchecked")

   743             @Override

   744             public K getKey() {

   745                 return (K) EconomicMapImpl.this.getKey(current);

   746             }

   747 

   748             @SuppressWarnings("unchecked")

   749             @Override

   750             public V getValue() {

   751                 return (V) EconomicMapImpl.this.getValue(current);

   752             }

   753 

   754             @Override

   755             public void remove() {

   756                 if (hasHashArray()) {

   757                     EconomicMapImpl.this.findAndRemoveHash(EconomicMapImpl.this.getKey(current));

   758                 }

   759                 current = EconomicMapImpl.this.remove(current) - 1;

   760             }

   761         };

   762     }

   763 

   764     @SuppressWarnings("unchecked")

   765     @Override

   766     public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {

   767         for (int i = 0; i < totalEntries; i++) {

   768             Object entryKey = getKey(i);

   769             if (entryKey != null) {

   770                 Object newValue = function.apply((K) entryKey, (V) getValue(i));

   771                 setValue(i, newValue);

   772             }

   773         }

   774     }

   775 

   776     private Object getKey(int index) {

   777         return entries[index << 1];

   778     }

   779 

   780     private void setKey(int index, Object newValue) {

   781         entries[index << 1] = newValue;

   782     }

   783 

   784     private void setValue(int index, Object newValue) {

   785         Object oldValue = getRawValue(index);

   786         if (oldValue instanceof CollisionLink) {

   787             CollisionLink collisionLink = (CollisionLink) oldValue;

   788             setRawValue(index, new CollisionLink(newValue, collisionLink.next));

   789         } else {

   790             setRawValue(index, newValue);

   791         }

   792     }

   793 

   794     private void setRawValue(int index, Object newValue) {

   795         entries[(index << 1) + 1] = newValue;

   796     }

   797 

   798     private Object getRawValue(int index) {

   799         return entries[(index << 1) + 1];

   800     }

   801 

   802     private Object getValue(int index) {

   803         Object object = getRawValue(index);

   804         if (object instanceof CollisionLink) {

   805             return ((CollisionLink) object).value;

   806         }

   807         return object;

   808     }

   809 

   810     @Override

   811     public String toString() {

   812         StringBuilder builder = new StringBuilder();

   813         builder.append("map(size=").append(size()).append(", {");

   814         MapCursor<K, V> cursor = getEntries();

   815         while (cursor.advance()) {

   816             builder.append("(").append(cursor.getKey()).append(",").append(cursor.getValue()).append("),");

   817         }

   818         builder.append("})");

   819         return builder.toString();

   820     }

   821 

   822     @Override

   823     public Iterator<K> iterator() {

   824         return new SparseMapIterator<K>() {

   825             @SuppressWarnings("unchecked")

   826             @Override

   827             public K next() {

   828                 Object result;

   829                 while ((result = getKey(current++)) == null) {

   830                     // skip null entries

   831                 }

   832                 return (K) result;

   833             }

   834         };

   835     }

   836 

   837     @Override

   838     public boolean contains(K element) {

   839         return containsKey(element);

   840     }

   841 

   842     @SuppressWarnings("unchecked")

   843     @Override

   844     public boolean add(K element) {

   845         return put(element, (V) element) == null;

   846     }

   847 

   848     @Override

   849     public void remove(K element) {

   850         removeKey(element);

   851     }

   852 }