1 package java.lang;
   2 
   3 import jdk.internal.misc.Unsafe;
   4 
   5 import java.util.Objects;
   6 
   7 /**
   8  * A linear-probe hash table that is lock-free for lookups and uses a single
   9  * lock for modifications.
  10  *
  11  * @author peter.levart@gmail.com
  12  */
  13 class LinearProbeHashtable<K, V> {
  14 
  15     /**
  16      * The minimum capacity, used if a lower value is implicitly specified
  17      * by either of the constructors with arguments.  The value 2 corresponds
  18      * to an expected maximum size of 1 with load factor 2/3.
  19      * MUST be a power of two.
  20      */
  21     private static final int MINIMUM_CAPACITY = 2;
  22 
  23     /**
  24      * The maximum capacity, used if a higher value is implicitly specified
  25      * by constructor. MUST be a power of two <= 1<<29.
  26      * <p>
  27      * The table can not hold more than MAXIMUM_CAPACITY * 2 / 3 = 357913941
  28      * entries. Attempts to insert more than that are rejected with
  29      * OutOfMemoryError.
  30      */
  31     private static final int MAXIMUM_CAPACITY = 1 << 29;
  32 
  33     /**
  34      * A special key that is used to overwrite a key when the entry is removed.
  35      */
  36     private static final class Tombstone {
  37         // Indicates at least (considering data races) how many tombstones are
  38         // following this tombstone in a consecutive run (including this tombstone)
  39         // before reaching another non-tombstone key or null (used to quickly skip
  40         // over consecutive runs of tombstones that pile-up when an entry is
  41         // repeatedly inserted and removed for the same key).
  42         //
  43         // Consider the following situation:
  44         //
  45         // hashtable.put(keyX, value1); hashtable.remove(keyX);
  46         // hashtable.put(keyX, value2); hashtable.remove(keyX);
  47         // hashtable.put(keyX, value3); hashtable.remove(keyX);
  48         // hashtable.put(keyX, value4);
  49         //
  50         // After above modifications and in case they didn't trigger rehashing,
  51         // hashtable.get(keyX) encounters the following state:
  52         //
  53         // i = firstIndex(keyX, table.length);
  54         // table[i+0] == Tombstone(skip=3)
  55         // table[i+1] == null
  56         // table[i+2] == Tombstone(skip=2)
  57         // table[i+3] == null
  58         // table[i+4] == Tombstone(skip=1)
  59         // table[i+5] == null
  60         // table[i+6] == keyX
  61         // table[i+7] == value4
  62         //
  63         // Without tombstone skip value(s), keyX lookup would require probing
  64         // all tombstones in a consecutive run before reaching the entry.
  65         //
  66         // A consecutive run of tombstones expands when a tombstone is prepended
  67         // or appended to the run. Two runs merge when a slot between them
  68         // is filled with a tombstone. Skip values are updated accordingly with
  69         // ever increasing sequence (see remove()). The correctness is not lost
  70         // if they are observed by lookup threads using data races, because the
  71         // initial skip value of any tombstone is correctly published with the
  72         // tombstone.
  73         int skip;
  74 
  75         Tombstone(int skip) { this.skip = skip; }
  76 
  77         int getSkipVolatile() {
  78             return U.getIntVolatile(this, SKIP_OFFSET);
  79         }
  80 
  81         @Override
  82         public String toString() {
  83             return "Tombstone(skip=" + skip + ")";
  84         }
  85 
  86         private static final Unsafe U;
  87         private static final long SKIP_OFFSET;
  88 
  89         static {
  90             U = Unsafe.getUnsafe();
  91             try {
  92                 SKIP_OFFSET = U.objectFieldOffset(
  93                     Tombstone.class.getDeclaredField("skip"));
  94             } catch (NoSuchFieldException e) {
  95                 throw new Error(e);
  96             }
  97         }
  98     }
  99 
 100     /**
 101      * All modifications are performed under a single lock
 102      */
 103     private final Object lock = new Object();
 104 
 105     /**
 106      * The table, resized as necessary. Length MUST always be a power of two.
 107      */
 108     private volatile Object[] table;
 109 
 110     /**
 111      * Number of inserted / tombstoned entries (size == inserted - tombstoned).
 112      */
 113     private int inserted, tombstoned;
 114 
 115     public LinearProbeHashtable(int expectedMaxSize) {
 116         if (expectedMaxSize < 0)
 117             throw new IllegalArgumentException("expectedMaxSize is negative: "
 118                                                + expectedMaxSize);
 119         table = new Object[2 * capacity(expectedMaxSize)];
 120     }
 121 
 122     @SuppressWarnings("unchecked")
 123     public V get(Object key) {
 124         Object[] tab = table;
 125         int len = tab.length;
 126         int i = firstIndex(key, len);
 127         while (true) {
 128             Object item = getVolatile(tab, i); // 1st read key...
 129             if (key == item || (item != null && key.equals(item))) {
 130                 // possible race with removing an entry can cause the value
 131                 // to be observed cleared. If this happens, we know the key
 132                 // has/will be tombstoned just after that so null is returned
 133                 return (V) getVolatile(tab, i + 1);  // ...then value
 134             } else if (item == null) {
 135                 // key was not found
 136                 return null;
 137             } else if (item instanceof Tombstone) {
 138                 // quickly skip over a run of tombstones
 139                 i = skipIndex(i, ((Tombstone) item).getSkipVolatile(), len);
 140             } else {
 141                 // skip over a non-tombstone non-null key
 142                 i = nextIndex(i, len);
 143             }
 144         }
 145     }
 146 
 147     @SuppressWarnings("unchecked")
 148     public V putIfAbsent(K key, V value) {
 149         Objects.requireNonNull(value, "value");
 150         retry:
 151         while (true) {
 152             Object[] tab = table;
 153             int len = tab.length;
 154             int i = firstIndex(key, len);
 155             // assert key != null;
 156             while (true) {
 157                 Object item = getVolatile(tab, i); // 1st read key...
 158                 if (key == item || (item != null && key.equals(item))) {
 159                     Object oldValue = getVolatile(tab, i + 1); // ...then value
 160                     // possible race with removing an entry can cause oldValue
 161                     // to be observed cleared. If this happens, we know the key
 162                     // has/will be tombstoned just after that so we re-read it
 163                     if (oldValue == null) {
 164                         continue;
 165                     }
 166                     return (V) oldValue;
 167                 } else if (item == null) {
 168                     // the key was not found
 169                     synchronized (lock) {
 170                         // validate everything under lock...
 171                         // the table might have changed so retry with new table
 172                         if (tab != table) {
 173                             continue retry;
 174                         }
 175                         // the table is still the same, but key slot might have
 176                         // been filled so retry
 177                         if (tab[i] != null) {
 178                             continue;
 179                         }
 180                         // the key slot is still empty, but the table might need
 181                         // to be rehashed so retry with new table
 182                         if (rehash()) {
 183                             continue retry;
 184                         }
 185                         tab[i + 1] = value; // 1st write value...
 186                         inserted++;
 187                         putVolatile(tab, i, key); // ...then publish the key
 188                         return null;
 189                     }
 190                 } else if (item instanceof Tombstone) {
 191                     // quickly skip over a run of tombstones
 192                     i = skipIndex(i, ((Tombstone) item).getSkipVolatile(), len);
 193                 } else {
 194                     // skip over a non-tombstone non-null key
 195                     i = nextIndex(i, len);
 196                 }
 197             }
 198         }
 199     }
 200 
 201     public V put(K key, V value) {
 202         Objects.requireNonNull(value, "value");
 203         synchronized (lock) {
 204             retry:
 205             while (true) {
 206                 Object[] tab = table; // no need for getTableAcquire under lock
 207                 int len = tab.length;
 208                 int i = firstIndex(key, len);
 209                 while (true) {
 210                     Object item = tab[i];
 211                     if (key == item || (item != null && key.equals(item))) {
 212                         // swap values and return the old one
 213                         @SuppressWarnings("unchecked")
 214                         V oldValue = (V) tab[i + 1];
 215                         putVolatile(tab, i + 1, value); // publish new value
 216                         return oldValue;
 217                     } else if (item == null) {
 218                         // the key was not found
 219                         // if the table needs rehashing, retry with new table
 220                         if (rehash()) {
 221                             continue retry;
 222                         }
 223                         tab[i + 1] = value; // 1st write value...
 224                         inserted++;
 225                         putVolatile(tab, i, key); // ...then publish the key
 226                         return null;
 227                     } else if (item instanceof Tombstone) {
 228                         // quickly skip over a run of tombstones
 229                         // (no need for getSkipVolatile as we have a lock)
 230                         i = skipIndex(i, ((Tombstone) item).skip, len);
 231                     } else {
 232                         // skip over a non-tombstone non-null key
 233                         i = nextIndex(i, len);
 234                     }
 235                 }
 236             }
 237         }
 238     }
 239 
 240     @SuppressWarnings("unchecked")
 241     public V remove(K key) {
 242         retry:
 243         while (true) {
 244             Object[] tab = table;
 245             int len = tab.length;
 246             int i = firstIndex(key, len);
 247             // assert key != null;
 248             while (true) {
 249                 Object item = getVolatile(tab, i); // 1st read key...
 250                 if (key == item || (item != null && key.equals(item))) {
 251                     Object oldValue = getVolatile(tab, i + 1); // ...then value
 252                     // possible race with another thread removing an entry can cause oldValue
 253                     // to be observed cleared. If this happens, we know the key
 254                     // has/will be tombstoned just after that so we return null
 255                     if (oldValue == null) {
 256                         return null;
 257                     }
 258                     synchronized (lock) {
 259                         // validate everything under lock...
 260                         // the table might have changed so retry with new table
 261                         if (tab != table) {
 262                             continue retry;
 263                         }
 264                         // the table is still the same, but key might have
 265                         // been tombstoned so retry
 266                         if (tab[i] != item) {
 267                             continue;
 268                         }
 269                         // re-read current value under lock
 270                         oldValue = tab[i + 1];
 271                         // get next key following our key slot
 272                         Object nextKey = tab[nextIndex(i, len)];
 273                         // obtain appropriate skip value
 274                         int skip = nextKey instanceof Tombstone
 275                                    ? ((Tombstone) nextKey).skip + 1 : 1;
 276                         // create tombstone with the skip value
 277                         Tombstone tombstone = new Tombstone(skip);
 278                         // update skip values of tombstones preceding our key slot
 279                         Object prevKey;
 280                         for (int j = prevIndex(i, len);
 281                              (prevKey = tab[j]) instanceof Tombstone;
 282                              j = prevIndex(j, len)) {
 283                             ((Tombstone) prevKey).skip = ++skip;
 284                         }
 285                         tab[i + 1] = null; // clear the value...
 286                         tombstoned++;
 287                         putVolatile(tab, i, tombstone); // ...publish
 288                         return (V) oldValue;
 289                     }
 290                 } else if (item == null) {
 291                     // the key was not found
 292                     return null;
 293                 } else if (item instanceof Tombstone) {
 294                     // quickly skip over a run of tombstones
 295                     i = skipIndex(i, ((Tombstone) item).getSkipVolatile(), len);
 296                 } else {
 297                     // skip over a non-tombstone non-null key
 298                     i = nextIndex(i, len);
 299                 }
 300             }
 301         }
 302     }
 303 
 304     public boolean replace(K key, V expectedValue, V newValue) {
 305         Objects.requireNonNull(expectedValue, "expectedValue");
 306         Objects.requireNonNull(newValue, "newValue");
 307         retry:
 308         while (true) {
 309             Object[] tab = table;
 310             int len = tab.length;
 311             int i = firstIndex(key, len);
 312             // assert key != null;
 313             while (true) {
 314                 Object item = getVolatile(tab, i); // 1st read key...
 315                 if (key == item || (item != null && key.equals(item))) {
 316                     Object oldValue = getVolatile(tab, i + 1); // ...then value
 317                     // possible race with another thread removing an entry can cause oldValue
 318                     // to be observed cleared. If this happens, we know the key
 319                     // has/will be tombstoned just after that and return false
 320                     if (oldValue == null ||
 321                         (expectedValue != oldValue && !expectedValue.equals(oldValue))) {
 322                         return false;
 323                     }
 324                     synchronized (lock) {
 325                         // validate everything under lock...
 326                         // the table might have changed so retry with new table
 327                         if (tab != table) {
 328                             continue retry;
 329                         }
 330                         // the table is still the same, but key might have
 331                         // been tombstoned so retry
 332                         if (tab[i] != item) {
 333                             continue;
 334                         }
 335                         // re-read the value under lock
 336                         oldValue = tab[i + 1];
 337                         if (expectedValue == oldValue ||
 338                             expectedValue.equals(oldValue)) {
 339                             putVolatile(tab, i + 1, newValue); // publish new value
 340                             return true;
 341                         } else {
 342                             return false;
 343                         }
 344                     }
 345                 } else if (item == null) {
 346                     // the key was not found
 347                     return false;
 348                 } else if (item instanceof Tombstone) {
 349                     // quickly skip over a run of tombstones
 350                     i = skipIndex(i, ((Tombstone) item).getSkipVolatile(), len);
 351                 } else {
 352                     // skip over a non-tombstone non-null key
 353                     i = nextIndex(i, len);
 354                 }
 355             }
 356         }
 357     }
 358 
 359     public int size() {
 360         synchronized (lock) {
 361             return inserted - tombstoned;
 362         }
 363     }
 364 
 365     /**
 366      * @throws OutOfMemoryError if given {@code size > MAXIMUM_CAPACITY * 2 / 3}
 367      */
 368     private static void checkSize(int size) {
 369         if (size > MAXIMUM_CAPACITY * 2 / 3) {
 370             throw new OutOfMemoryError("Maximum capacity exceeded");
 371         }
 372     }
 373 
 374     /**
 375      * Returns the appropriate capacity for the given expected maximum size.
 376      * Returns the smallest power of two between MINIMUM_CAPACITY and
 377      * MAXIMUM_CAPACITY, inclusive, that is greater than (3 *
 378      * expectedMaxSize)/2, if such a number exists.  Otherwise returns
 379      * MAXIMUM_CAPACITY.
 380      */
 381     private static int capacity(int expectedMaxSize) {
 382         // assert expectedMaxSize >= 0;
 383         return
 384             (expectedMaxSize > MAXIMUM_CAPACITY / 3) ? MAXIMUM_CAPACITY :
 385             (expectedMaxSize <= 2 * MINIMUM_CAPACITY / 3) ? MINIMUM_CAPACITY :
 386             Integer.highestOneBit(expectedMaxSize + (expectedMaxSize << 1));
 387     }
 388 
 389     private static int firstIndex(Object key, int len) {
 390         return (key.hashCode() << 1) & (len - 1);
 391     }
 392 
 393     private static int nextIndex(int i, int len) {
 394         return (i + 2) & (len - 1);
 395     }
 396 
 397     private static int prevIndex(int i, int len) {
 398         return (i - 2) & (len - 1);
 399     }
 400 
 401     private static int skipIndex(int i, int skip, int len) {
 402         return (i + (skip << 1)) & (len - 1);
 403     }
 404 
 405     /**
 406      * Check whether current table is long enough to accommodate for
 407      * new entry to be inserted and resize it by rehashing into new table if
 408      * needed.
 409      *
 410      * @return true if table was rehashed and replaced with new table
 411      * @throws OutOfMemoryError if current {@link #size()} increased by 1 would
 412      *                          result in a table that exceeds 2/3 load factor
 413      *                          for table length of 2*MAXIMUM_CAPACITY
 414      */
 415     private boolean rehash() {
 416         // assert Thread.holdsLock(lock);
 417         checkSize(inserted - tombstoned + 1);
 418         Object[] curTab = table;
 419         int curLen = curTab.length;
 420         if (2 * capacity(inserted + 1) > curLen) {
 421             // be conservative with shrinking to prevent excessive rehashing.
 422             // guarantee that after rehashing at least size()/2 + 1 entries can
 423             // be inserted without further rehashing.
 424             // Note: factor 3/2 is chosen as a compromise between conserving
 425             // space and minimizing needed rehashes. It can be chosen between
 426             // 1 <= factor < 2 without affecting resizing policy when entries
 427             // are only inserted and never removed.
 428             int newLen = 2 * capacity((inserted - tombstoned) * 3 / 2 + 1);
 429             Object[] newTab = new Object[newLen];
 430             for (int j = 0; j < curLen; j += 2) {
 431                 Object key = curTab[j];
 432                 if (key != null && !(key instanceof Tombstone)) {
 433                     Object value = curTab[j + 1];
 434                     curTab[j] = null;
 435                     curTab[j + 1] = null;
 436                     // insert it in the new table
 437                     int i = firstIndex(key, newLen);
 438                     while (newTab[i] != null) {
 439                         i = nextIndex(i, newLen);
 440                     }
 441                     newTab[i] = key;
 442                     newTab[i + 1] = value;
 443                 }
 444             }
 445             inserted -= tombstoned;
 446             tombstoned = 0;
 447             table = newTab;
 448             return true;
 449         } else {
 450             return false;
 451         }
 452     }
 453 
 454     // -- volatile access to arrays slots  --
 455 
 456     private static Object getVolatile(Object[] a, int i) {
 457         return U.getObjectVolatile(a, byteOffset(i));
 458     }
 459 
 460     private static void putVolatile(Object[] a, int i, Object x) {
 461         U.putObjectVolatile(a, byteOffset(i), x);
 462     }
 463 
 464     private static long byteOffset(int i) {
 465         return ((long) i << ASHIFT) + ABASE;
 466     }
 467 
 468     private static final Unsafe U;
 469     private static final int ABASE;
 470     private static final int ASHIFT;
 471 
 472     static {
 473         U = Unsafe.getUnsafe();
 474         ABASE = U.arrayBaseOffset(Object[].class);
 475         int scale = U.arrayIndexScale(Object[].class);
 476         if ((scale & (scale - 1)) != 0)
 477             throw new Error("array index scale not a power of two");
 478         ASHIFT = 31 - Integer.numberOfLeadingZeros(scale);
 479     }
 480 }