--- a/src/jdk.jfr/share/classes/jdk/jfr/internal/util/PrimitiveHashMap.java Fri May 24 20:45:11 2019 +0200
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,341 +0,0 @@
-package jdk.jfr.internal.util;
-
-import java.util.AbstractCollection;
-import java.util.Collection;
-import java.util.Objects;
-import java.util.Set;
-import java.util.Map;
-import java.util.Iterator;
-import java.util.function.BiConsumer;
-import java.util.function.Consumer;
-import java.util.ConcurrentModificationException;
-import java.util.Random;
-
-public class PrimitiveHashMap<V> {
-
- static final long W = 64L;
- static final long A = 4633630788178346939L;
- final Random rand = new Random();
-
- private static int getIndex(long key, long hashFunction, long shift, long mask) {
- return (int)(((A * key) + (hashFunction & mask)) >>> shift);
- }
- private long getRandomHashFunction() {
- return rand.nextLong();
- }
- /**
- * The maximum capacity, used if a higher value is implicitly specified
- * by either of the constructors with arguments.
- */
- static final int MAX_SIZE_EXPONENT = 30;
- static final int MAXIMUM_CAPACITY = 1 << MAX_SIZE_EXPONENT;
-
- static final int DEFAULT_SIZE_EXPONENT = 4;
- static final int DEFAULT_INITIAL_CAPACITY = 1 << DEFAULT_SIZE_EXPONENT; // aka 16
- /**
- * The load factor used when none specified in constructor.
- */
- static final float DEFAULT_LOAD_FACTOR = 0.75f;
- static class Log2 {
-
- static long log2base10(long exponent) {
- return 1L << exponent;
- }
- static int log2(int value) {
- int i = 0;
- int lastMultiple = 0;
- while (i < MAX_SIZE_EXPONENT) {
- int multiple = (int)log2base10(i);
- if ((value & multiple) != 0) {
- lastMultiple = i;
- }
- ++i;
- }
- return ((int)log2base10(lastMultiple) ^ value) != 0 ? lastMultiple + 1 : lastMultiple;
- }
- }
- /**
- * Returns a power of two size for the given target capacity.
- */
- static final int tableSizeFor(int cap) {
- int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
- return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
- }
- static final int tableExponent(int cap) {
- return Log2.log2(cap);
- }
-
- static class Node<V> {
- final long key;
- V value;
-
- Node(long key, V value) {
- this.key = key;
- this.value = value;
- }
-
- public final long getKey() { return key; }
- public final V getValue() { return value; }
- public final String toString() { return key + "=" + value; }
- }
-
- private Node<V>[] table;
- private int size;
- private int threshold;
- private long shift;
- private long shiftMask;
- private int tableLengthMask;
- int modCount;
- private final float loadFactor;
- long h1 = 0;
- long h2 = 0;
-
- public PrimitiveHashMap(int initialCapacity, float loadFactor) {
- if (initialCapacity < 0) {
- throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
- }
- if (initialCapacity > MAXIMUM_CAPACITY) {
- initialCapacity = MAXIMUM_CAPACITY;
- }
- if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
- throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
- }
- this.loadFactor = loadFactor;
- this.threshold = tableSizeFor(initialCapacity);
- h1 = getRandomHashFunction();
- h2 = getRandomHashFunction();
- resize();
- }
-
- public PrimitiveHashMap(int initialCapacity) {
- this(initialCapacity, DEFAULT_LOAD_FACTOR);
- }
-
- public PrimitiveHashMap() {
- this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
- }
-
- public final void forEach(BiConsumer<? super Long, ? super V> action) {
- Node<V>[] tab;
- if (action == null)
- throw new NullPointerException();
- if (size > 0 && (tab = table) != null) {
- int mc = modCount;
- for (int i = 0; i < table.length; ++i) {
- if (table[i] == null) continue;
- action.accept(table[i].getKey(), table[i].getValue());
- }
- if (modCount != mc)
- throw new ConcurrentModificationException();
- }
- }
-
- public final void forEach(Consumer<? super V> action) {
- Node<V>[] tab;
- if (action == null)
- throw new NullPointerException();
- if (size > 0 && (tab = table) != null) {
- int mc = modCount;
- for (int i = 0; i < table.length; ++i) {
- if (table[i] == null) continue;
- action.accept(table[i].getValue());
- }
- if (modCount != mc)
- throw new ConcurrentModificationException();
- }
- }
-
- public final long[] keys() {
- long[] keys = new long[size];
- int j = 0;
- for (int i = 0; i < table.length; ++i) {
- if (table[i] == null) continue;
- keys[j++] = table[i].getKey();
- }
- assert(j == size);
- assert(keys.length == size);
- return keys;
- }
-
- public Collection<V> values () {
- final PrimitiveHashMap<V> thisMap = this;
- return new AbstractCollection<V>() {
- private PrimitiveHashMap<V> map = thisMap;
- public Iterator<V> iterator() {
- return new Iterator<V>() {
- private int i = 0;
- private long [] k = keys();
- public boolean hasNext() {
- return i < k.length;
- }
- public V next() {
- assert(i < k.length);
- return map.get(k[i++]);
- }
- };
- }
- public int size() {
- return map.size();
- }
- public boolean isEmpty() {
- return size() != 0;
- }
- public void clear() {
- throw new UnsupportedOperationException();
- }
- public boolean contains(Object v) {
- for (V value : map.values()) {
- if (v == value) {
- return true;
- }
- }
- return false;
- }
- };
- }
- private int doubleHash(long key, int i) {
- int h1_idx = getIndex(key, h1, shift, shiftMask);
- assert(h1_idx < table.length);
- int h2_idx = 0;
- if (i != 0) {
- h2_idx = getIndex(key, h2, shift, shiftMask);
- h2_idx |= 1;
- assert((h2_idx & 1) == 1);
- }
- assert(h2_idx < table.length);
- final int idx = (h1_idx + (i * h2_idx)) & tableLengthMask;
- assert(idx >= 0);
- assert(idx < table.length);
- return idx;
- }
-
- /**
- * Initializes or doubles table size. If null, allocates in
- * accord with initial capacity target held in field threshold.
- * Otherwise, because we are using power-of-two expansion, the
- * elements from each bin must either stay at same index, or move
- * with a power of two offset in the new table.
- *
- * @return the table
- */
- final Node<V>[] resize() {
- Node<V>[] oldTab = table;
- int oldCap = (oldTab == null) ? 0 : oldTab.length;
- int oldThr = threshold;
- int newCap, newThr = 0;
- if (oldCap > 0) {
- if (oldCap >= MAXIMUM_CAPACITY) {
- threshold = Integer.MAX_VALUE;
- return oldTab;
- }
- else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
- oldCap >= DEFAULT_INITIAL_CAPACITY)
- newThr = oldThr << 1; // double threshold
- }
- else if (oldThr > 0) // initial capacity was placed in threshold
- newCap = oldThr;
- else { // zero initial threshold signifies using defaults
- newCap = DEFAULT_INITIAL_CAPACITY;
- newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
- }
- if (newThr == 0) {
- float ft = (float)newCap * loadFactor;
- newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
- (int)ft : Integer.MAX_VALUE);
- }
- threshold = newThr;
- @SuppressWarnings({"rawtypes","unchecked"})
- Node<V>[] newTab = (Node<V>[])new Node[newCap];
- table = newTab;
- tableLengthMask = newCap - 1;
- this.shift = W - tableExponent(newCap);
- this.shiftMask = Log2.log2base10(shift) - 1;
- if (oldTab != null) {
- for (int j = 0; j < oldCap; ++j) {
- Node<V> e;
- if ((e = oldTab[j]) != null) {
- oldTab[j] = null;
- reinsert(e);
- }
- }
- }
- return newTab;
- }
-
- // used by table resize
- private void reinsert(Node<V> e) {
- assert(size < table.length);
- for (int i = 0; i < table.length; ++i) {
- int idx = doubleHash(e.getKey(), i);
- assert(idx >= 0);
- assert(idx < table.length);
- if (table[idx] == null) {
- table[idx] = e;
- return;
- }
- assert(table[idx].key != e.getKey());
- }
- }
-
- public V put(long key, V value) {
- Node<V> existing = insert(key, value);
- return existing != null ? existing.value : null;
- }
-
- private Node<V> insert(long key, V value) {
- return insert(new Node<V>(key, value), key);
- }
-
- private Node<V> insert(Node<V> e, final long key) {
- assert(size < table.length);
- assert(e.getKey() == key);
- Node<V> existing = null;
- for (int i = 0; i < table.length; ++i) {
- int idx = doubleHash(key, i);
- assert(idx >= 0);
- assert(idx < table.length);
- if (table[idx] == null) {
- table[idx] = e;
- ++size;
- break;
- } else {
- if (table[idx].key == key) {
- existing = table[idx];
- table[idx] = e;
- break;
- }
- }
- }
- if (size > threshold) {
- resize();
- }
- return existing;
- }
-
- private Node<V> find(long key) {
- Node<V> result = null;
- for (int i = 0; i < table.length; ++i) {
- int idx = doubleHash(key, i);
- assert(idx >= 0);
- assert(idx < table.length);
- result = table[idx];
- if (result == null || result.key == key) {
- break;
- }
- }
- return result;
- }
-
-
- public V get(long key) {
- Node<V> existing = find(key);
- return existing != null ? existing.value : null;
- }
-
- public boolean containsKey(long key) {
- return find(key) != null;
- }
- public int size() {
- return this.size;
- }
-}
\ No newline at end of file