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 either of the constructors with arguments.
26 * MUST be a power of two <= 1<<29.
27 * <p>
28 * In fact, the map can hold no more than MAXIMUM_CAPACITY-1 items
29 * because it has to have at least one slot with the key == null
30 * in order to avoid infinite loops in get(), put(), remove()
31 */
32 private static final int MAXIMUM_CAPACITY = 1 << 29;
33
34 /**
35 * A special key that is used to overwrite a key when the entry is removed
36 */
37 private static class Tombstone {}
38
39 private static final Tombstone TOMBSTONE = new Tombstone();
40
41 /**
42 * All modifications are performed under a single lock
43 */
44 private final Object lock = new Object();
45
46 /**
47 * The table, resized as necessary. Length MUST always be a power of two.
48 */
49 private volatile Object[] table;
50
51 /**
52 * Counters of inserted and tombstoned entries (size == inserted - tombstoned).
53 */
54 private int inserted, tombstoned;
55
56 public LinearProbeHashtable(int expectedMaxSize) {
57 if (expectedMaxSize < 0)
58 throw new IllegalArgumentException("expectedMaxSize is negative: "
59 + expectedMaxSize);
60 table = new Object[2 * capacity(expectedMaxSize)];
61 }
62
63 @SuppressWarnings("unchecked")
64 public V get(Object key) {
65 Object[] tab = table;
66 int len = tab.length;
67 int i = firstIndex(key, len);
68 while (true) {
69 Object item = getVolatile(tab, i); // 1st read key...
70 if (key == item || (item != null && item != TOMBSTONE && key.equals(item))) {
71 // possible race with removing an entry can cause the value
72 // to be already cleared. If this happens, we know the key
73 // has been tombstoned just before that so null is returned
74 return (V) getVolatile(tab, i + 1); // ...then value
75 }
76 if (item == null) {
77 // key was not found
78 return null;
79 }
80 i = nextIndex(i, len);
81 }
82 }
83
84 @SuppressWarnings("unchecked")
85 public V putIfAbsent(K key, V value) {
86 Objects.requireNonNull(value, "value");
87 retry:
88 while (true) {
89 Object[] tab = table;
90 int len = tab.length;
91 int i = firstIndex(key, len);
92 // assert key != null;
93 while (true) {
94 Object item = getVolatile(tab, i); // 1st read key...
95 if (key == item || (item != null && item != TOMBSTONE && key.equals(item))) {
96 Object oldValue = getVolatile(tab, i + 1); // ...then value
97 // possible race with removing an entry can cause oldValue
98 // to be already cleared. If this happens, we know the key
99 // has been tombstoned just before that
100 if (oldValue != null) {
101 return (V) oldValue;
102 }
103 // assert getVolatile(tab, i) == TOMBSTONE;
104 // continue the search and find free slot or even the value
105 } else if (item == null) {
106 // the key was not found
107 synchronized (lock) {
108 // are we still there?
109 if (tab != table) {
110 continue retry;
111 }
112 // re-read key under lock
113 item = tab[i];
114 // if the table is still the same then the key slot is
115 // either still empty or not
116 if (item == null) {
117 if (rehash()) {
118 continue retry;
119 }
120 tab[i + 1] = value; // 1st write value...
121 inserted++;
122 putVolatile(tab, i, key); // ...then key
123 return null;
124 } else if (key == item || (item != TOMBSTONE && key.equals(item))) {
125 // if equal key was inserted by another thread then return
126 // the value
127 return (V) tab[i + 1];
128 }
129 // else the slot was filled with some other key so
130 // continue the search
131 }
132 }
133 i = nextIndex(i, len);
134 }
135 }
136 }
137
138 public V put(K key, V value) {
139 Objects.requireNonNull(value, "value");
140 synchronized (lock) {
141 retry:
142 while (true) {
143 Object[] tab = table;
144 int len = tab.length;
145 int i = firstIndex(key, len);
146 while (true) {
147 Object item = tab[i];
148 if (key == item || (item != null && key.equals(item))) {
149 // swap values and return the old one
150 @SuppressWarnings("unchecked")
151 V oldValue = (V) tab[i + 1];
152 putVolatile(tab, i + 1, value);
153 return oldValue;
154 }
155 if (item == null) {
156 if (rehash()) {
157 continue retry;
158 }
159 tab[i + 1] = value; // 1st write value...
160 inserted++;
161 putVolatile(tab, i, key); // ...then key
162 return null;
163 }
164 i = nextIndex(i, len);
165 }
166 }
167 }
168 }
169
170 @SuppressWarnings("unchecked")
171 public V remove(K key) {
172 retry:
173 while (true) {
174 Object[] tab = table;
175 int len = tab.length;
176 int i = firstIndex(key, len);
177 // assert key != null;
178 while (true) {
179 Object item = getVolatile(tab, i); // 1st read key...
180 if (key == item || (item != null && item != TOMBSTONE && key.equals(item))) {
181 Object oldValue = getVolatile(tab, i + 1); // ...then value
182 // possible race with another thread removing an entry can cause oldValue
183 // to be already cleared. If this happens, we know the key
184 // has been tombstoned just before that
185 if (oldValue == null) {
186 // assert getVolatile(tab, i) == TOMBSTONE;
187 return null;
188 }
189 synchronized (lock) {
190 // are we still there?
191 if (tab != table) {
192 continue retry;
193 }
194 // if the table is still the same then the key slot is
195 // either occupied by the same key or tombstoned
196 if (tab[i] == item) {
197 // re-read the value under lock
198 oldValue = tab[i + 1];
199 tab[i + 1] = null; // 1st clear the value...
200 tombstoned++;
201 putVolatile(tab, i, TOMBSTONE); // ...then tombstone the key
202 return (V) oldValue;
203 } else {
204 // assert tab[i] == TOMBSTONE;
205 return null;
206 }
207 }
208 } else if (item == null) {
209 // the key was not found
210 return null;
211 }
212 i = nextIndex(i, len);
213 }
214 }
215 }
216
217 public boolean replace(K key, V expectedValue, V newValue) {
218 Objects.requireNonNull(expectedValue, "expectedValue");
219 Objects.requireNonNull(newValue, "newValue");
220 retry:
221 while (true) {
222 Object[] tab = table;
223 int len = tab.length;
224 int i = firstIndex(key, len);
225 // assert key != null;
226 while (true) {
227 Object item = getVolatile(tab, i); // 1st read key...
228 if (key == item || (item != null && item != TOMBSTONE && key.equals(item))) {
229 Object oldValue = getVolatile(tab, i + 1); // ...then value
230 // possible race with another thread removing an entry can cause oldValue
231 // to be already cleared. If this happens, we know the key
232 // has been tombstoned just before that
233 if (oldValue == null) {
234 return false;
235 }
236 synchronized (lock) {
237 // are we still there?
238 if (tab != table) {
239 continue retry;
240 }
241 // if the table is still the same then the key slot is
242 // either occupied by the same key or tombstoned
243 if (tab[i] == item) {
244 // re-read the value under lock
245 oldValue = tab[i + 1];
246 if (expectedValue == oldValue ||
247 expectedValue.equals(oldValue)) {
248 putVolatile(tab, i + 1, newValue);
249 return true;
250 } else {
251 return false;
252 }
253 } else {
254 // assert tab[i] == TOMBSTONE;
255 return false;
256 }
257 }
258 } else if (item == null) {
259 // the key was not found
260 return false;
261 }
262 i = nextIndex(i, len);
263 }
264 }
265 }
266
267 /**
268 * Returns the appropriate capacity for the given expected maximum size.
269 *
270 * @throws OutOfMemoryError if {@code expectedMaxSize > MAXIMUM_CAPACITY * 2 / 3}
271 */
272 private static int capacity(int expectedMaxSize) {
273 // assert expectedMaxSize >= 0;
274 if (expectedMaxSize > MAXIMUM_CAPACITY * 2 / 3) {
275 throw new OutOfMemoryError("Maximum capacity exceeded");
276 }
277 return
278 (expectedMaxSize > MAXIMUM_CAPACITY / 3) ? MAXIMUM_CAPACITY :
279 (expectedMaxSize <= 2 * MINIMUM_CAPACITY / 3) ? MINIMUM_CAPACITY :
280 Integer.highestOneBit(expectedMaxSize + (expectedMaxSize << 1));
281 }
282
283 private static int firstIndex(Object key, int len) {
284 return (key.hashCode() << 1) & (len - 1);
285 }
286
287 private static int nextIndex(int i, int len) {
288 return (i + 2) & (len - 1);
289 }
290
291 /**
292 * Check whether current table is long enough to accommodate for
293 * new entry to be inserted and resize it by rehashing into new table if
294 * not.
295 *
296 * @return true if table was rehashed and replaced with new table
297 */
298 private boolean rehash() {
299 // assert Thread.holdsLock(lock);
300 Object[] curTab = table;
301 int curLen = curTab.length;
302 if (2 * capacity(inserted + 1) > curLen) {
303 // shrink table only half-way down to prevent excessive
304 // rehashing in situations with repeated put/remove usage
305 // patterns
306 int newLen = 2 * capacity(inserted - (tombstoned / 2) + 1);
307 Object[] newTab = new Object[newLen];
308 for (int j = 0; j < curLen; j += 2) {
309 Object key = curTab[j];
310 if (key != null && key != TOMBSTONE) {
311 Object value = curTab[j + 1];
312 curTab[j] = null;
313 curTab[j + 1] = null;
314 // insert it in the new table
315 int i = firstIndex(key, newLen);
316 while (newTab[i] != null) {
317 i = nextIndex(i, newLen);
318 }
319 newTab[i] = key;
320 newTab[i + 1] = value;
321 }
322 }
323 inserted -= tombstoned;
324 tombstoned = 0;
325 table = newTab;
326 return true;
327 } else {
328 return false;
329 }
330 }
331
332 private static Object getVolatile(Object[] a, int i) {
333 return U.getObjectVolatile(a, byteOffset(i));
334 }
335
336 private static void putVolatile(Object[] a, int i, Object x) {
337 U.putObjectVolatile(a, byteOffset(i), x);
338 }
339
340 private static long byteOffset(int i) {
341 return ((long) i << ASHIFT) + ABASE;
342 }
343
344 private static final Unsafe U;
345 private static final int ABASE;
346 private static final int ASHIFT;
347
348 static {
349 U = Unsafe.getUnsafe();
350 ABASE = U.arrayBaseOffset(Object[].class);
351 int scale = U.arrayIndexScale(Object[].class);
352 if ((scale & (scale - 1)) != 0)
353 throw new Error("array index scale not a power of two");
354 ASHIFT = 31 - Integer.numberOfLeadingZeros(scale);
355 }
356 }