1 package jdk.jfr.internal.util;

     2 

     3 import java.util.AbstractCollection;

     4 import java.util.Collection;

     5 import java.util.Objects;

     6 import java.util.Set;

     7 import java.util.Map;

     8 import java.util.Iterator;

     9 import java.util.function.BiConsumer;

    10 import java.util.function.Consumer;

    11 import java.util.ConcurrentModificationException;

    12 import java.util.Random;

    13 

    14 public class PrimitiveHashMap<V> {

    15 

    16     static final long W = 64L;

    17     static final long A = 4633630788178346939L;

    18     final Random rand = new Random();

    19 

    20     private static int getIndex(long key, long hashFunction, long shift, long mask) {

    21         return (int)(((A * key) + (hashFunction & mask)) >>> shift);

    22     }

    23     private long getRandomHashFunction() {

    24         return rand.nextLong();

    25     }

    26     /**

    27      * The maximum capacity, used if a higher value is implicitly specified

    28      * by either of the constructors with arguments.

    29      */

    30     static final int MAX_SIZE_EXPONENT = 30;

    31     static final int MAXIMUM_CAPACITY = 1 << MAX_SIZE_EXPONENT;

    32 

    33     static final int DEFAULT_SIZE_EXPONENT = 4;

    34     static final int DEFAULT_INITIAL_CAPACITY = 1 << DEFAULT_SIZE_EXPONENT; // aka 16

    35     /**

    36      * The load factor used when none specified in constructor.

    37      */

    38     static final float DEFAULT_LOAD_FACTOR = 0.75f;

    39     static class Log2 {

    40 

    41         static long log2base10(long exponent) {

    42             return 1L << exponent;

    43         }

    44         static int log2(int value) {

    45             int i = 0;

    46             int lastMultiple = 0;

    47             while (i < MAX_SIZE_EXPONENT) {

    48                 int multiple = (int)log2base10(i);

    49                 if ((value & multiple) != 0) {

    50                     lastMultiple = i;

    51                 }

    52                 ++i;

    53             }

    54             return ((int)log2base10(lastMultiple) ^ value) != 0 ? lastMultiple + 1 : lastMultiple;

    55         }

    56     }

    57         /**

    58      * Returns a power of two size for the given target capacity.

    59      */

    60     static final int tableSizeFor(int cap) {

    61         int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);

    62         return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;

    63     }

    64     static final int tableExponent(int cap) {

    65         return Log2.log2(cap);

    66     }

    67 

    68     static class Node<V> {

    69         final long key;

    70         V value;

    71 

    72         Node(long key, V value) {

    73             this.key = key;

    74             this.value = value;

    75         }

    76 

    77         public final long getKey()     { return key; }

    78         public final V getValue()      { return value; }

    79         public final String toString() { return key + "=" + value; }

    80     }

    81 

    82     private Node<V>[] table;

    83     private int size;

    84     private int threshold;

    85     private long shift;

    86     private long shiftMask;

    87     private int tableLengthMask;

    88     int modCount;

    89     private final float loadFactor;

    90     long h1 = 0;

    91     long h2 = 0;

    92 

    93     public PrimitiveHashMap(int initialCapacity, float loadFactor) {

    94         if (initialCapacity < 0) {

    95             throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);

    96         }

    97         if (initialCapacity > MAXIMUM_CAPACITY) {

    98             initialCapacity = MAXIMUM_CAPACITY;

    99         }

   100         if (loadFactor <= 0 || Float.isNaN(loadFactor)) {

   101             throw new IllegalArgumentException("Illegal load factor: " + loadFactor);

   102         }

   103         this.loadFactor = loadFactor;

   104         this.threshold = tableSizeFor(initialCapacity);

   105         h1 = getRandomHashFunction();

   106         h2 = getRandomHashFunction();

   107         resize();

   108     }

   109 

   110     public PrimitiveHashMap(int initialCapacity) {

   111         this(initialCapacity, DEFAULT_LOAD_FACTOR);

   112     }

   113 

   114     public PrimitiveHashMap() {

   115         this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);

   116     }

   117 

   118     public final void forEach(BiConsumer<? super Long, ? super V> action) {

   119         Node<V>[] tab;

   120         if (action == null)

   121             throw new NullPointerException();

   122         if (size > 0 && (tab = table) != null) {

   123             int mc = modCount;

   124             for (int i = 0; i < table.length; ++i) {

   125                 if (table[i] == null) continue;

   126                 action.accept(table[i].getKey(), table[i].getValue());

   127             }

   128             if (modCount != mc)

   129                 throw new ConcurrentModificationException();

   130         }

   131     }

   132 

   133     public final void forEach(Consumer<? super V> action) {

   134         Node<V>[] tab;

   135         if (action == null)

   136             throw new NullPointerException();

   137         if (size > 0 && (tab = table) != null) {

   138             int mc = modCount;

   139             for (int i = 0; i < table.length; ++i) {

   140                 if (table[i] == null) continue;

   141                 action.accept(table[i].getValue());

   142             }

   143             if (modCount != mc)

   144                 throw new ConcurrentModificationException();

   145         }

   146     }

   147 

   148     public final long[] keys() {

   149         long[] keys = new long[size];

   150         int j = 0;

   151         for (int i = 0; i < table.length; ++i) {

   152             if (table[i] == null) continue;

   153             keys[j++] = table[i].getKey();

   154         }

   155         assert(j == size);

   156         assert(keys.length == size);

   157         return keys;

   158     }

   159 

   160     public Collection<V> values () {

   161         final PrimitiveHashMap<V> thisMap = this;

   162         return new AbstractCollection<V>() {

   163             private PrimitiveHashMap<V> map = thisMap;

   164             public Iterator<V> iterator() {

   165                 return new Iterator<V>() {

   166                     private int i = 0;

   167                     private long [] k = keys();

   168                     public boolean hasNext() {

   169                         return i < k.length;

   170                     }

   171                     public V next() {

   172                         assert(i < k.length);

   173                         return map.get(k[i++]);

   174                     }

   175                 };

   176             }

   177             public int size() {

   178                 return map.size();

   179             }

   180             public boolean isEmpty() {

   181                 return size() != 0;

   182             }

   183             public void clear() {

   184                 throw new UnsupportedOperationException();

   185             }

   186             public boolean contains(Object v) {

   187                 for (V value : map.values()) {

   188                     if (v == value) {

   189                         return true;

   190                     }

   191                 }

   192                 return false;

   193             }

   194         };

   195     }

   196     private int doubleHash(long key, int i) {

   197         int h1_idx = getIndex(key, h1, shift, shiftMask);

   198         assert(h1_idx < table.length);

   199         int h2_idx = 0;

   200         if (i != 0) {

   201             h2_idx = getIndex(key, h2, shift, shiftMask);

   202             h2_idx |= 1;

   203             assert((h2_idx & 1) == 1);

   204         }

   205         assert(h2_idx < table.length);

   206         final int idx = (h1_idx + (i * h2_idx)) & tableLengthMask;

   207         assert(idx >= 0);

   208         assert(idx < table.length);

   209         return idx;

   210     }

   211 

   212      /**

   213      * Initializes or doubles table size.  If null, allocates in

   214      * accord with initial capacity target held in field threshold.

   215      * Otherwise, because we are using power-of-two expansion, the

   216      * elements from each bin must either stay at same index, or move

   217      * with a power of two offset in the new table.

   218      *

   219      * @return the table

   220      */

   221     final Node<V>[] resize() {

   222         Node<V>[] oldTab = table;

   223         int oldCap = (oldTab == null) ? 0 : oldTab.length;

   224         int oldThr = threshold;

   225         int newCap, newThr = 0;

   226         if (oldCap > 0) {

   227             if (oldCap >= MAXIMUM_CAPACITY) {

   228                 threshold = Integer.MAX_VALUE;

   229                 return oldTab;

   230             }

   231             else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&

   232                      oldCap >= DEFAULT_INITIAL_CAPACITY)

   233                 newThr = oldThr << 1; // double threshold

   234         }

   235         else if (oldThr > 0) // initial capacity was placed in threshold

   236             newCap = oldThr;

   237         else {               // zero initial threshold signifies using defaults

   238             newCap = DEFAULT_INITIAL_CAPACITY;

   239             newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);

   240         }

   241         if (newThr == 0) {

   242             float ft = (float)newCap * loadFactor;

   243             newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?

   244                       (int)ft : Integer.MAX_VALUE);

   245         }

   246         threshold = newThr;

   247         @SuppressWarnings({"rawtypes","unchecked"})

   248         Node<V>[] newTab = (Node<V>[])new Node[newCap];

   249         table = newTab;

   250         tableLengthMask = newCap - 1;

   251         this.shift = W - tableExponent(newCap);

   252         this.shiftMask = Log2.log2base10(shift) - 1;

   253         if (oldTab != null) {

   254             for (int j = 0; j < oldCap; ++j) {

   255                 Node<V> e;

   256                 if ((e = oldTab[j]) != null) {

   257                     oldTab[j] = null;

   258                     reinsert(e);

   259                 }

   260             }

   261         }

   262         return newTab;

   263     }

   264 

   265     // used by table resize

   266     private void reinsert(Node<V> e) {

   267         assert(size < table.length);

   268         for (int i = 0; i < table.length; ++i) {

   269             int idx = doubleHash(e.getKey(), i);

   270             assert(idx >= 0);

   271             assert(idx < table.length);

   272             if (table[idx] == null) {

   273                 table[idx] = e;

   274                 return;

   275             }

   276             assert(table[idx].key != e.getKey());

   277         }

   278     }

   279 

   280     public V put(long key, V value) {

   281         Node<V> existing = insert(key, value);

   282         return existing != null ? existing.value : null;

   283     }

   284 

   285     private Node<V> insert(long key, V value) {

   286         return insert(new Node<V>(key, value), key);

   287     }

   288 

   289     private Node<V> insert(Node<V> e, final long key) {

   290         assert(size < table.length);

   291         assert(e.getKey() == key);

   292         Node<V> existing = null;

   293         for (int i = 0; i < table.length; ++i) {

   294             int idx = doubleHash(key, i);

   295             assert(idx >= 0);

   296             assert(idx < table.length);

   297             if (table[idx] == null) {

   298                 table[idx] = e;

   299                 ++size;

   300                 break;

   301             } else {

   302                if (table[idx].key == key) {

   303                    existing = table[idx];

   304                    table[idx] = e;

   305                    break;

   306                }

   307             }

   308         }

   309         if (size > threshold) {

   310             resize();

   311         }

   312         return existing;

   313     }

   314 

   315     private Node<V> find(long key) {

   316         Node<V> result = null;

   317         for (int i = 0; i < table.length; ++i) {

   318             int idx = doubleHash(key, i);

   319             assert(idx >= 0);

   320             assert(idx < table.length);

   321             result = table[idx];

   322             if (result == null || result.key == key) {

   323                 break;

   324             }

   325         }

   326         return result;

   327     }

   328 

   329 

   330     public V get(long key) {

   331         Node<V> existing = find(key);

   332         return existing != null ? existing.value : null;

   333     }

   334 

   335     public boolean containsKey(long key) {

   336         return find(key) != null;

   337     }

   338     public int size() {

   339         return this.size;

   340     }

   341 }