1 /*

     2  * Copyright (c) 2019, Oracle and/or its affiliates. All rights reserved.

     3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

     4  *

     5  * This code is free software; you can redistribute it and/or modify it

     6  * under the terms of the GNU General Public License version 2 only, as

     7  * published by the Free Software Foundation.  Oracle designates this

     8  * particular file as subject to the "Classpath" exception as provided

     9  * by Oracle in the LICENSE file that accompanied this code.

    10  *

    11  * This code is distributed in the hope that it will be useful, but WITHOUT

    12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

    13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

    14  * version 2 for more details (a copy is included in the LICENSE file that

    15  * accompanied this code).

    16  *

    17  * You should have received a copy of the GNU General Public License version

    18  * 2 along with this work; if not, write to the Free Software Foundation,

    19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

    20  *

    21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

    22  * or visit www.oracle.com if you need additional information or have any

    23  * questions.

    24  */

    25 

    26 package jdk.jfr.internal;

    27 

    28 import java.util.BitSet;

    29 import java.util.function.Consumer;

    30 import java.util.function.LongConsumer;

    31 

    32 @SuppressWarnings("unchecked")

    33 public final class LongMap<T> {

    34     private static final int MAXIMUM_CAPACITY = 1 << 30;

    35     private static final long[] EMPTY_KEYS = new long[0];

    36     private static final Object[] EMPTY_OBJECTS = new Object[0];

    37     private static final int DEFAULT_SIZE = 32;

    38     private static final Object NULL_OBJECT = new Object();

    39 

    40     private final int bitCount;

    41     private BitSet bitSet;

    42     private long[] keys = EMPTY_KEYS;

    43     private T[] objects = (T[]) EMPTY_OBJECTS;

    44     private int count;

    45     private int shift;

    46 

    47     public LongMap() {

    48         this.bitCount = 0;

    49     }

    50 

    51     public LongMap(int markBits) {

    52         this.bitCount = markBits;

    53         this.bitSet = new BitSet();

    54     }

    55 

    56     // Should be 2^n

    57     private void initialize(int capacity) {

    58         keys = new long[capacity];

    59         objects = (T[]) new Object[capacity];

    60         shift = 64 - (31 - Integer.numberOfLeadingZeros(capacity));

    61     }

    62 

    63     public void claimBits() {

    64         // flip last bit back and forth to make bitset expand to max size

    65         int lastBit = bitSetIndex(objects.length - 1, bitCount -1);

    66         bitSet.flip(lastBit);

    67         bitSet.flip(lastBit);

    68     }

    69 

    70     public void setId(long id, int bitIndex) {

    71         int bitSetIndex = bitSetIndex(tableIndexOf(id), bitIndex);

    72         bitSet.set(bitSetIndex, true);

    73     }

    74 

    75     public void clearId(long id, int bitIndex) {

    76         int bitSetIndex = bitSetIndex(tableIndexOf(id), bitIndex);

    77         bitSet.set(bitSetIndex, false);

    78     }

    79 

    80     public boolean isSetId(long id, int bitIndex) {

    81         int bitSetIndex = bitSetIndex(tableIndexOf(id), bitIndex);

    82         return bitSet.get(bitSetIndex);

    83     }

    84 

    85     private int bitSetIndex(int tableIndex, int bitIndex) {

    86         return bitCount * tableIndex + bitIndex;

    87     }

    88 

    89     private int tableIndexOf(long id) {

    90         int index = index(id);

    91         while (true) {

    92             if (objects[index] == null) {

    93                 throw new InternalError("Unknown id");

    94             }

    95             if (keys[index] == id) {

    96                 return index;

    97             }

    98             index++;

    99             if (index == keys.length) {

   100                 index = 0;

   101             }

   102         }

   103     }

   104 

   105     public boolean hasKey(long id) {

   106         int index = index(id);

   107         while (true) {

   108             if (objects[index] == null) {

   109                return false;

   110             }

   111             if (keys[index] == id) {

   112                 return true;

   113             }

   114             index++;

   115             if (index == keys.length) {

   116                 index = 0;

   117             }

   118         }

   119     }

   120 

   121     public void expand(int size) {

   122         int l = 4 * size / 3;

   123         if (l <= keys.length) {

   124             return;

   125         }

   126         int n = tableSizeFor(l);

   127         LongMap<T> temp = new LongMap<>(bitCount);

   128         temp.initialize(n);

   129         // Optimization, avoid growing while copying bits

   130         if (bitCount > 0 && !bitSet.isEmpty()) {

   131            temp.claimBits();

   132            claimBits();

   133         }

   134         for (int tIndex = 0; tIndex < keys.length; tIndex++) {

   135             T o = objects[tIndex];

   136             if (o != null) {

   137                 long key = keys[tIndex];

   138                 temp.put(key, o);

   139                 if (bitCount != 0) {

   140                     for (int bIndex = 0; bIndex < bitCount; bIndex++) {

   141                         boolean bitValue = isSetId(key, bIndex);

   142                         if (bitValue) {

   143                             temp.setId(key, bIndex);

   144                         }

   145                     }

   146                 }

   147             }

   148         }

   149         keys = temp.keys;

   150         objects = temp.objects;

   151         shift = temp.shift;

   152         bitSet = temp.bitSet;

   153     }

   154 

   155     public void put(long id, T object) {

   156         if (keys == EMPTY_KEYS) {

   157             // Lazy initialization

   158             initialize(DEFAULT_SIZE);

   159         }

   160         if (object == null) {

   161             object = (T) NULL_OBJECT;

   162         }

   163 

   164         int index = index(id);

   165         // probe for empty slot

   166         while (true) {

   167             if (objects[index] == null) {

   168                 keys[index] = id;

   169                 objects[index] = object;

   170                 count++;

   171                 // Don't expand lazy since it

   172                 // can cause resize when replacing

   173                 // an object.

   174                 if (count > 3 * keys.length / 4) {

   175                     expand(2 * keys.length);

   176                 }

   177                 return;

   178             }

   179             // if it already exists, replace

   180             if (keys[index] == id) {

   181                 objects[index] = object;

   182                 return;

   183             }

   184             index++;

   185             if (index == keys.length) {

   186                 index = 0;

   187             }

   188         }

   189     }

   190     public T getAt(int tableIndex) {

   191         T o =  objects[tableIndex];

   192         return o == NULL_OBJECT ? null : o;

   193     }

   194 

   195     public T get(long id) {

   196         if (keys == EMPTY_KEYS) {

   197             return null;

   198         }

   199         int index = index(id);

   200         while (true) {

   201             if (objects[index] == null) {

   202                 return null;

   203             }

   204             if (keys[index] == id) {

   205                 return getAt(index);

   206             }

   207             index++;

   208             if (index == keys.length) {

   209                 index = 0;

   210             }

   211         }

   212     }

   213 

   214     private int index(long id) {

   215         return (int) ((id * -7046029254386353131L) >>> shift);

   216     }

   217 

   218     // Copied from HashMap::tableSizeFor

   219     private static final int tableSizeFor(int cap) {

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

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

   222     }

   223 

   224     public void forEachKey(LongConsumer keyTraverser) {

   225         for (int i = 0; i < keys.length; i++) {

   226             if (objects[i] != null) {

   227                 keyTraverser.accept(keys[i]);

   228             }

   229         }

   230     }

   231 

   232     public void forEach(Consumer<T> consumer) {

   233         for (int i = 0; i < keys.length; i++) {

   234             T o = objects[i];

   235             if (o != null) {

   236                 consumer.accept(o);

   237             }

   238         }

   239     }

   240 

   241     public int size() {

   242         return count;

   243     }

   244 

   245     public String toString() {

   246         StringBuilder sb = new StringBuilder();

   247         for (int i = 0; i < objects.length; i++) {

   248             sb.append(i);

   249             sb.append(": id=");

   250             sb.append(keys[i]);

   251             sb.append(" ");

   252             sb.append(objects[i]);

   253             sb.append("\n");

   254         }

   255         return sb.toString();

   256     }

   257 }