--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/jdk.jfr/share/classes/jdk/jfr/internal/util/PrimitiveHashMap.java Fri May 17 18:03:14 2019 +0200
@@ -0,0 +1,341 @@
+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