Expands the table if possible.
()
| 2867 | |
| 2868 | /** Expands the table if possible. */ |
| 2869 | @GuardedBy("this") |
| 2870 | void expand() { |
| 2871 | AtomicReferenceArray<ReferenceEntry<K, V>> oldTable = table; |
| 2872 | int oldCapacity = oldTable.length(); |
| 2873 | if (oldCapacity >= MAXIMUM_CAPACITY) { |
| 2874 | return; |
| 2875 | } |
| 2876 | |
| 2877 | /* |
| 2878 | * Reclassify nodes in each list to new Map. Because we are using power-of-two expansion, the |
| 2879 | * elements from each bin must either stay at same index, or move with a power of two offset. |
| 2880 | * We eliminate unnecessary node creation by catching cases where old nodes can be reused |
| 2881 | * because their next fields won't change. Statistically, at the default threshold, only about |
| 2882 | * one-sixth of them need cloning when a table doubles. The nodes they replace will be garbage |
| 2883 | * collectable as soon as they are no longer referenced by any reader thread that may be in |
| 2884 | * the midst of traversing table right now. |
| 2885 | */ |
| 2886 | |
| 2887 | int newCount = count; |
| 2888 | AtomicReferenceArray<ReferenceEntry<K, V>> newTable = newEntryArray(oldCapacity << 1); |
| 2889 | threshold = newTable.length() * 3 / 4; |
| 2890 | int newMask = newTable.length() - 1; |
| 2891 | for (int oldIndex = 0; oldIndex < oldCapacity; ++oldIndex) { |
| 2892 | // We need to guarantee that any existing reads of old Map can |
| 2893 | // proceed. So we cannot yet null out each bin. |
| 2894 | ReferenceEntry<K, V> head = oldTable.get(oldIndex); |
| 2895 | |
| 2896 | if (head != null) { |
| 2897 | ReferenceEntry<K, V> next = head.getNext(); |
| 2898 | int headIndex = head.getHash() & newMask; |
| 2899 | |
| 2900 | // Single node on list |
| 2901 | if (next == null) { |
| 2902 | newTable.set(headIndex, head); |
| 2903 | } else { |
| 2904 | // Reuse the consecutive sequence of nodes with the same target |
| 2905 | // index from the end of the list. tail points to the first |
| 2906 | // entry in the reusable list. |
| 2907 | ReferenceEntry<K, V> tail = head; |
| 2908 | int tailIndex = headIndex; |
| 2909 | for (ReferenceEntry<K, V> e = next; e != null; e = e.getNext()) { |
| 2910 | int newIndex = e.getHash() & newMask; |
| 2911 | if (newIndex != tailIndex) { |
| 2912 | // The index changed. We'll need to copy the previous entry. |
| 2913 | tailIndex = newIndex; |
| 2914 | tail = e; |
| 2915 | } |
| 2916 | } |
| 2917 | newTable.set(tailIndex, tail); |
| 2918 | |
| 2919 | // Clone nodes leading up to the tail. |
| 2920 | for (ReferenceEntry<K, V> e = head; e != tail; e = e.getNext()) { |
| 2921 | int newIndex = e.getHash() & newMask; |
| 2922 | ReferenceEntry<K, V> newNext = newTable.get(newIndex); |
| 2923 | ReferenceEntry<K, V> newFirst = copyEntry(e, newNext); |
| 2924 | if (newFirst != null) { |
| 2925 | newTable.set(newIndex, newFirst); |
| 2926 | } else { |