--- a/src/jdk.jfr/share/classes/jdk/jfr/internal/util/PerfectHashMap.java Fri May 24 20:45:11 2019 +0200
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,340 +0,0 @@
-package jdk.jfr.internal.util;
-
-import java.util.Arrays;
-import java.util.HashMap;
-import java.util.Map;
-import java.util.Objects;
-import java.util.function.BiConsumer;
-import java.util.function.Consumer;
-
-public class PerfectHashMap<V> {
- private static final long COLLISION_SHIFT = 63;
- private static final long COLLISION_BIT = 1L << COLLISION_SHIFT;
- private static final long COLLISION_MASK = COLLISION_BIT - 1;
- private static final int MAX_REMAP_ATTEMPTS = 100000;
- private static final int MAX_ATTEMPS_BEFORE_RESIZE = 100;
-
- static final long W = 64L;
- static class LinkedValue<V> {
- final V value;
- long next;
-
- LinkedValue(V value) {
- this.value = value;
- this.next = 0;
- }
- }
-
- private UniversalHashFamily hashFamily = new UniversalHashFamily();
- private PrimitiveHashMap<LinkedValue<V>> loadMap;
- private Object[] valueTable;
- private long[] routeTable;
- private long shift;
- private long shiftMask;
- private int tableLengthMask;
- private long primaryHashFunction = 0;
- private int collisions = 0;
- private int retries = 0;
- private int sizeFactor = 1;
- private boolean minimal;
-
- public V get(long key) {
- LinkedValue<V> v = loadMap.get(key);
- return v != null ? v.value : null;
- }
-
- public V put(long key, V value) {
- LinkedValue<V> existing = loadMap.put(key, new LinkedValue<V>(value));
- return existing != null ? existing.value : null;
- }
-
- public void forEach(BiConsumer<? super Long, ? super V> action) {
- //loadMap.forEach(PerfectHashMap<V>::callback);
- }
-
- public final void forEach(Consumer<? super V> action) {
- //loadMap.forEach(action);
- }
-
- public final long[] keys() {
- return loadMap.keys();
- }
-
- static class Log2 {
- private static final int MAX_SIZE_EXPONENT = 32;
-
- 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;
- }
- }
-
- static final int tableExponent(int cap) {
- return Log2.log2(cap);
- }
-
- PerfectHashMap() {
- this(false, 101);
- }
-
- PerfectHashMap(int size) {
- this(false, size);
- }
-
- PerfectHashMap(boolean minimal, int size) {
- this.minimal = minimal;
- this.loadMap = new PrimitiveHashMap<>(size);
- this.primaryHashFunction = hashFamily.getRandomHashFunction();
- }
-
- @SuppressWarnings("unchecked")
- public V getPerfect(long key) {
- int routeIdx = getIndex(key, primaryHashFunction);
- assert(routeIdx >= 0);
- assert(routeIdx < routeTable.length);
- long element = routeTable[routeIdx];
- int valueIdx = element < 0 ? getIndex(key, -element - 1) : (int)element;
- assert(valueIdx >= 0);
- assert(valueIdx < valueTable.length);
- return (V)valueTable[valueIdx];
- }
-
- private long getRandomHashFunction() {
- return hashFamily.getRandomHashFunction();
- }
- private int getIndex(long key, long hashFunction) {
- final int idx = UniversalHashFamily.getIndex(key, hashFunction, shift, shiftMask);
- assert(idx >= 0);
- assert(idx < routeTable.length);
- return idx;
- }
- private static boolean isColliding(long entry) {
- return entry < 0;
- }
- private boolean isNonColliding(long entry) {
- return entry > 0;
- }
- private static long setColliding(long entry) {
- return entry | COLLISION_BIT;
- }
- private static long read(long entry) {
- return entry & COLLISION_MASK;
- }
-
- private int nextValueTableSlot(int lastIdx) {
- assert(lastIdx < valueTable.length);
- int i = lastIdx;
- for (; i < valueTable.length; ++i) {
- if (valueTable[i] == null) {
- break;
- }
- }
- return i;
- }
-
- private int valueTableStore(V value, int lastIdx) {
- if (lastIdx > valueTable.length) {
- lastIdx = 0;
- }
- assert(lastIdx < valueTable.length);
- final int idx = nextValueTableSlot(lastIdx);
- assert(idx < valueTable.length);
- assert(valueTable[idx] == null);
- valueTable[idx] = value;
- return idx;
- }
-
-
- private void routeNonCollisions() {
- int lastIdx = 0;
- for (int i = 0; i < routeTable.length; ++i) {
- if (isNonColliding(routeTable[i])) {
- lastIdx = valueTableStore(loadMap.get(routeTable[i]).value, lastIdx);
- routeTable[i] = lastIdx++;
- }
- }
- }
-
- private void rollback(int idx, int length, long hashFunction) {
- assert(isColliding(routeTable[idx]));
- long key = read(routeTable[idx]);
- LinkedValue<V> v = loadMap.get(key); // boxing
- for (int i = 0; i < length; ++i) {
- final int valueIdx = getIndex(key, hashFunction);
- assert(valueIdx >= 0);
- assert(valueIdx < valueTable.length);
- assert(valueTable[valueIdx] != null);
- valueTable[valueIdx] = null;
- key = v.next;
- v = loadMap.get(v.next); // no boxing
- }
- }
-
- private boolean remap(int idx, long hashFunction) {
- assert(isColliding(routeTable[idx]));
- int completed = 0;
- long key = read(routeTable[idx]);
- LinkedValue<V> v = loadMap.get(key);
- while (key != 0) {
- final int valueIdx = getIndex(key, hashFunction);
- assert(valueIdx >= 0);
- assert(valueIdx < valueTable.length);
- if (valueTable[valueIdx] == null) {
- valueTable[valueIdx] = v.value;
- ++completed;
- key = v.next;
- v = loadMap.get(v.next);
- continue;
- }
- rollback(idx, completed, hashFunction);
- return false;
- }
- return true;
- }
-
- private boolean routeCollisions(int idx) {
- assert(isColliding(routeTable[idx]));
- boolean success = false;
- int attempts = 0;
- long randomHashFunction = 0;
- do {
- randomHashFunction = getRandomHashFunction();
- success = remap(idx, randomHashFunction);
- if (++attempts == MAX_REMAP_ATTEMPTS) {
- System.out.println("Failed number of attempts - restart: " + attempts);
- return false;
- }
- } while (!success);
- System.out.println("Number of remap attempts: " + attempts);
- routeTable[idx] = -1 - randomHashFunction;
- assert(-routeTable[idx] - 1 == randomHashFunction);
- return true;
- }
-
-
- private boolean routeCollisions() {
- for (int i = 0; i < routeTable.length; ++i) {
- if (isColliding(routeTable[i])) {
- if (!routeCollisions(i)) {
- return false;
- }
- }
- }
- return true;
- }
-
- private static void clearLongTable(long[] table) {
- Arrays.fill(table, 0);
- for (int i = 0; i < table.length; ++i) {
- assert(table[i] == 0);
- }
- }
-
- private static <T extends Object> void clearReferenceTable(T[] table) {
- Arrays.fill(table, null);
- for (int i = 0; i < table.length; ++i) {
- assert(table[i] == null);
- }
- }
-
- private void unlinkChains() {
- for (long key : loadMap.keys()) {
- loadMap.get(key).next = 0;
- }
- }
-
- private void routeTableStore(long key, LinkedValue<V> value, int idx) {
- assert(idx >= 0);
- assert(idx < routeTable.length);
- long existing = read(routeTable[idx]);
- if (existing == 0) {
- routeTable[idx] = key;
- return;
- }
- ++collisions;
- routeTable[idx] = setColliding(existing);
- LinkedValue<V> existingValue = loadMap.get(existing);
- value.next = existingValue.next;
- existingValue.next = key;
- }
-
- private void mapKeys() {
- for (long key : loadMap.keys()) {
- routeTableStore(key, loadMap.get(key), getIndex(key, primaryHashFunction));
- }
- }
-
- private void validate() {
- for (long key : loadMap.keys()) {
- long element = routeTable[getIndex(key, primaryHashFunction)];
- int valueIdx = element < 0 ? getIndex(key, -element - 1) : (int)element;
- assert(valueIdx >= 0);
- assert(loadMap.get(key) == valueTable[valueIdx]);
- }
- }
-
- private void reset() {
- collisions = 0;
- clearLongTable(routeTable);
- clearReferenceTable(valueTable);
- }
-
- private int dimensionTableSize() {
- int size = loadMap.size() * sizeFactor;
- return (int)Log2.log2base10(Log2.log2(size));
- }
-
- @SuppressWarnings({"rawtypes","unchecked"})
- private void allocateTables() {
- int size = dimensionTableSize();
- this.tableLengthMask = size - 1;
- this.shift = W - tableExponent(size);
- this.shiftMask = Log2.log2base10(shift) - 1;
- routeTable = new long[size];
- valueTable = (V[])new Object[size];
- collisions = 0;
- retries = 0;
- }
-
- public void build() {
- start:
- while (true) {
- allocateTables();
- System.out.println("Table size " + routeTable.length);
- mapKeys();
- if (collisions > 0) {
- if (!routeCollisions()) {
- unlinkChains();
- if (++retries <= MAX_ATTEMPS_BEFORE_RESIZE) {
- reset();
- } else {
- sizeFactor *= 2;
- }
- continue start;
- }
- }
- routeNonCollisions();
- return;
- }
- }
-
- public void rebuild() {
- sizeFactor = 1;
- build();
- }
- public int size() {
- return loadMap.size();
- }
-}
\ No newline at end of file
--- 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
--- a/src/jdk.jfr/share/classes/jdk/jfr/internal/util/UniversalHashFamily.java Fri May 24 20:45:11 2019 +0200
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,27 +0,0 @@
-package jdk.jfr.internal.util;
-
-import java.util.Random;
-
-public class UniversalHashFamily {
- final Random rand = new Random();
-
- private static long getA(long hashFunction) {
- return hashFunction | 1;
- }
-
- private static long getB(long hashFunction, long mask) {
- return hashFunction & mask;
- }
-
- private static long getHash(long key, long hashFunction, long mask) {
- return (getA(hashFunction) * key) + (hashFunction & mask);
- }
-
- public static int getIndex(long key, long hashFunction, long shift, long mask) {
- return (int)(getHash(key, hashFunction, mask) >>> shift);
- }
-
- public long getRandomHashFunction() {
- return rand.nextLong() & Long.MAX_VALUE;
- }
-}
\ No newline at end of file