766 return (Node<K,V>)U.getObjectAcquire(tab, ((long)i << ASHIFT) + ABASE); |
766 return (Node<K,V>)U.getObjectAcquire(tab, ((long)i << ASHIFT) + ABASE); |
767 } |
767 } |
768 |
768 |
769 static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i, |
769 static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i, |
770 Node<K,V> c, Node<K,V> v) { |
770 Node<K,V> c, Node<K,V> v) { |
771 return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v); |
771 return U.compareAndSetObject(tab, ((long)i << ASHIFT) + ABASE, c, v); |
772 } |
772 } |
773 |
773 |
774 static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) { |
774 static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) { |
775 U.putObjectRelease(tab, ((long)i << ASHIFT) + ABASE, v); |
775 U.putObjectRelease(tab, ((long)i << ASHIFT) + ABASE, v); |
776 } |
776 } |
2297 private final Node<K,V>[] initTable() { |
2297 private final Node<K,V>[] initTable() { |
2298 Node<K,V>[] tab; int sc; |
2298 Node<K,V>[] tab; int sc; |
2299 while ((tab = table) == null || tab.length == 0) { |
2299 while ((tab = table) == null || tab.length == 0) { |
2300 if ((sc = sizeCtl) < 0) |
2300 if ((sc = sizeCtl) < 0) |
2301 Thread.yield(); // lost initialization race; just spin |
2301 Thread.yield(); // lost initialization race; just spin |
2302 else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) { |
2302 else if (U.compareAndSetInt(this, SIZECTL, sc, -1)) { |
2303 try { |
2303 try { |
2304 if ((tab = table) == null || tab.length == 0) { |
2304 if ((tab = table) == null || tab.length == 0) { |
2305 int n = (sc > 0) ? sc : DEFAULT_CAPACITY; |
2305 int n = (sc > 0) ? sc : DEFAULT_CAPACITY; |
2306 @SuppressWarnings("unchecked") |
2306 @SuppressWarnings("unchecked") |
2307 Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n]; |
2307 Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n]; |
2328 * @param check if <0, don't check resize, if <= 1 only check if uncontended |
2328 * @param check if <0, don't check resize, if <= 1 only check if uncontended |
2329 */ |
2329 */ |
2330 private final void addCount(long x, int check) { |
2330 private final void addCount(long x, int check) { |
2331 CounterCell[] as; long b, s; |
2331 CounterCell[] as; long b, s; |
2332 if ((as = counterCells) != null || |
2332 if ((as = counterCells) != null || |
2333 !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) { |
2333 !U.compareAndSetLong(this, BASECOUNT, b = baseCount, s = b + x)) { |
2334 CounterCell a; long v; int m; |
2334 CounterCell a; long v; int m; |
2335 boolean uncontended = true; |
2335 boolean uncontended = true; |
2336 if (as == null || (m = as.length - 1) < 0 || |
2336 if (as == null || (m = as.length - 1) < 0 || |
2337 (a = as[ThreadLocalRandom.getProbe() & m]) == null || |
2337 (a = as[ThreadLocalRandom.getProbe() & m]) == null || |
2338 !(uncontended = |
2338 !(uncontended = |
2339 U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) { |
2339 U.compareAndSetLong(a, CELLVALUE, v = a.value, v + x))) { |
2340 fullAddCount(x, uncontended); |
2340 fullAddCount(x, uncontended); |
2341 return; |
2341 return; |
2342 } |
2342 } |
2343 if (check <= 1) |
2343 if (check <= 1) |
2344 return; |
2344 return; |
2352 if (sc < 0) { |
2352 if (sc < 0) { |
2353 if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 || |
2353 if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 || |
2354 sc == rs + MAX_RESIZERS || (nt = nextTable) == null || |
2354 sc == rs + MAX_RESIZERS || (nt = nextTable) == null || |
2355 transferIndex <= 0) |
2355 transferIndex <= 0) |
2356 break; |
2356 break; |
2357 if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) |
2357 if (U.compareAndSetInt(this, SIZECTL, sc, sc + 1)) |
2358 transfer(tab, nt); |
2358 transfer(tab, nt); |
2359 } |
2359 } |
2360 else if (U.compareAndSwapInt(this, SIZECTL, sc, |
2360 else if (U.compareAndSetInt(this, SIZECTL, sc, |
2361 (rs << RESIZE_STAMP_SHIFT) + 2)) |
2361 (rs << RESIZE_STAMP_SHIFT) + 2)) |
2362 transfer(tab, null); |
2362 transfer(tab, null); |
2363 s = sumCount(); |
2363 s = sumCount(); |
2364 } |
2364 } |
2365 } |
2365 } |
2376 while (nextTab == nextTable && table == tab && |
2376 while (nextTab == nextTable && table == tab && |
2377 (sc = sizeCtl) < 0) { |
2377 (sc = sizeCtl) < 0) { |
2378 if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 || |
2378 if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 || |
2379 sc == rs + MAX_RESIZERS || transferIndex <= 0) |
2379 sc == rs + MAX_RESIZERS || transferIndex <= 0) |
2380 break; |
2380 break; |
2381 if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) { |
2381 if (U.compareAndSetInt(this, SIZECTL, sc, sc + 1)) { |
2382 transfer(tab, nextTab); |
2382 transfer(tab, nextTab); |
2383 break; |
2383 break; |
2384 } |
2384 } |
2385 } |
2385 } |
2386 return nextTab; |
2386 return nextTab; |
2399 int sc; |
2399 int sc; |
2400 while ((sc = sizeCtl) >= 0) { |
2400 while ((sc = sizeCtl) >= 0) { |
2401 Node<K,V>[] tab = table; int n; |
2401 Node<K,V>[] tab = table; int n; |
2402 if (tab == null || (n = tab.length) == 0) { |
2402 if (tab == null || (n = tab.length) == 0) { |
2403 n = (sc > c) ? sc : c; |
2403 n = (sc > c) ? sc : c; |
2404 if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) { |
2404 if (U.compareAndSetInt(this, SIZECTL, sc, -1)) { |
2405 try { |
2405 try { |
2406 if (table == tab) { |
2406 if (table == tab) { |
2407 @SuppressWarnings("unchecked") |
2407 @SuppressWarnings("unchecked") |
2408 Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n]; |
2408 Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n]; |
2409 table = nt; |
2409 table = nt; |
2416 } |
2416 } |
2417 else if (c <= sc || n >= MAXIMUM_CAPACITY) |
2417 else if (c <= sc || n >= MAXIMUM_CAPACITY) |
2418 break; |
2418 break; |
2419 else if (tab == table) { |
2419 else if (tab == table) { |
2420 int rs = resizeStamp(n); |
2420 int rs = resizeStamp(n); |
2421 if (U.compareAndSwapInt(this, SIZECTL, sc, |
2421 if (U.compareAndSetInt(this, SIZECTL, sc, |
2422 (rs << RESIZE_STAMP_SHIFT) + 2)) |
2422 (rs << RESIZE_STAMP_SHIFT) + 2)) |
2423 transfer(tab, null); |
2423 transfer(tab, null); |
2424 } |
2424 } |
2425 } |
2425 } |
2426 } |
2426 } |
2457 advance = false; |
2457 advance = false; |
2458 else if ((nextIndex = transferIndex) <= 0) { |
2458 else if ((nextIndex = transferIndex) <= 0) { |
2459 i = -1; |
2459 i = -1; |
2460 advance = false; |
2460 advance = false; |
2461 } |
2461 } |
2462 else if (U.compareAndSwapInt |
2462 else if (U.compareAndSetInt |
2463 (this, TRANSFERINDEX, nextIndex, |
2463 (this, TRANSFERINDEX, nextIndex, |
2464 nextBound = (nextIndex > stride ? |
2464 nextBound = (nextIndex > stride ? |
2465 nextIndex - stride : 0))) { |
2465 nextIndex - stride : 0))) { |
2466 bound = nextBound; |
2466 bound = nextBound; |
2467 i = nextIndex - 1; |
2467 i = nextIndex - 1; |
2474 nextTable = null; |
2474 nextTable = null; |
2475 table = nextTab; |
2475 table = nextTab; |
2476 sizeCtl = (n << 1) - (n >>> 1); |
2476 sizeCtl = (n << 1) - (n >>> 1); |
2477 return; |
2477 return; |
2478 } |
2478 } |
2479 if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) { |
2479 if (U.compareAndSetInt(this, SIZECTL, sc = sizeCtl, sc - 1)) { |
2480 if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT) |
2480 if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT) |
2481 return; |
2481 return; |
2482 finishing = advance = true; |
2482 finishing = advance = true; |
2483 i = n; // recheck before commit |
2483 i = n; // recheck before commit |
2484 } |
2484 } |
2599 if ((as = counterCells) != null && (n = as.length) > 0) { |
2599 if ((as = counterCells) != null && (n = as.length) > 0) { |
2600 if ((a = as[(n - 1) & h]) == null) { |
2600 if ((a = as[(n - 1) & h]) == null) { |
2601 if (cellsBusy == 0) { // Try to attach new Cell |
2601 if (cellsBusy == 0) { // Try to attach new Cell |
2602 CounterCell r = new CounterCell(x); // Optimistic create |
2602 CounterCell r = new CounterCell(x); // Optimistic create |
2603 if (cellsBusy == 0 && |
2603 if (cellsBusy == 0 && |
2604 U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) { |
2604 U.compareAndSetInt(this, CELLSBUSY, 0, 1)) { |
2605 boolean created = false; |
2605 boolean created = false; |
2606 try { // Recheck under lock |
2606 try { // Recheck under lock |
2607 CounterCell[] rs; int m, j; |
2607 CounterCell[] rs; int m, j; |
2608 if ((rs = counterCells) != null && |
2608 if ((rs = counterCells) != null && |
2609 (m = rs.length) > 0 && |
2609 (m = rs.length) > 0 && |
2621 } |
2621 } |
2622 collide = false; |
2622 collide = false; |
2623 } |
2623 } |
2624 else if (!wasUncontended) // CAS already known to fail |
2624 else if (!wasUncontended) // CAS already known to fail |
2625 wasUncontended = true; // Continue after rehash |
2625 wasUncontended = true; // Continue after rehash |
2626 else if (U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x)) |
2626 else if (U.compareAndSetLong(a, CELLVALUE, v = a.value, v + x)) |
2627 break; |
2627 break; |
2628 else if (counterCells != as || n >= NCPU) |
2628 else if (counterCells != as || n >= NCPU) |
2629 collide = false; // At max size or stale |
2629 collide = false; // At max size or stale |
2630 else if (!collide) |
2630 else if (!collide) |
2631 collide = true; |
2631 collide = true; |
2632 else if (cellsBusy == 0 && |
2632 else if (cellsBusy == 0 && |
2633 U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) { |
2633 U.compareAndSetInt(this, CELLSBUSY, 0, 1)) { |
2634 try { |
2634 try { |
2635 if (counterCells == as) {// Expand table unless stale |
2635 if (counterCells == as) {// Expand table unless stale |
2636 CounterCell[] rs = new CounterCell[n << 1]; |
2636 CounterCell[] rs = new CounterCell[n << 1]; |
2637 for (int i = 0; i < n; ++i) |
2637 for (int i = 0; i < n; ++i) |
2638 rs[i] = as[i]; |
2638 rs[i] = as[i]; |
2645 continue; // Retry with expanded table |
2645 continue; // Retry with expanded table |
2646 } |
2646 } |
2647 h = ThreadLocalRandom.advanceProbe(h); |
2647 h = ThreadLocalRandom.advanceProbe(h); |
2648 } |
2648 } |
2649 else if (cellsBusy == 0 && counterCells == as && |
2649 else if (cellsBusy == 0 && counterCells == as && |
2650 U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) { |
2650 U.compareAndSetInt(this, CELLSBUSY, 0, 1)) { |
2651 boolean init = false; |
2651 boolean init = false; |
2652 try { // Initialize table |
2652 try { // Initialize table |
2653 if (counterCells == as) { |
2653 if (counterCells == as) { |
2654 CounterCell[] rs = new CounterCell[2]; |
2654 CounterCell[] rs = new CounterCell[2]; |
2655 rs[h & 1] = new CounterCell(x); |
2655 rs[h & 1] = new CounterCell(x); |
2856 |
2856 |
2857 /** |
2857 /** |
2858 * Acquires write lock for tree restructuring. |
2858 * Acquires write lock for tree restructuring. |
2859 */ |
2859 */ |
2860 private final void lockRoot() { |
2860 private final void lockRoot() { |
2861 if (!U.compareAndSwapInt(this, LOCKSTATE, 0, WRITER)) |
2861 if (!U.compareAndSetInt(this, LOCKSTATE, 0, WRITER)) |
2862 contendedLock(); // offload to separate method |
2862 contendedLock(); // offload to separate method |
2863 } |
2863 } |
2864 |
2864 |
2865 /** |
2865 /** |
2866 * Releases write lock for tree restructuring. |
2866 * Releases write lock for tree restructuring. |
2874 */ |
2874 */ |
2875 private final void contendedLock() { |
2875 private final void contendedLock() { |
2876 boolean waiting = false; |
2876 boolean waiting = false; |
2877 for (int s;;) { |
2877 for (int s;;) { |
2878 if (((s = lockState) & ~WAITER) == 0) { |
2878 if (((s = lockState) & ~WAITER) == 0) { |
2879 if (U.compareAndSwapInt(this, LOCKSTATE, s, WRITER)) { |
2879 if (U.compareAndSetInt(this, LOCKSTATE, s, WRITER)) { |
2880 if (waiting) |
2880 if (waiting) |
2881 waiter = null; |
2881 waiter = null; |
2882 return; |
2882 return; |
2883 } |
2883 } |
2884 } |
2884 } |
2885 else if ((s & WAITER) == 0) { |
2885 else if ((s & WAITER) == 0) { |
2886 if (U.compareAndSwapInt(this, LOCKSTATE, s, s | WAITER)) { |
2886 if (U.compareAndSetInt(this, LOCKSTATE, s, s | WAITER)) { |
2887 waiting = true; |
2887 waiting = true; |
2888 waiter = Thread.currentThread(); |
2888 waiter = Thread.currentThread(); |
2889 } |
2889 } |
2890 } |
2890 } |
2891 else if (waiting) |
2891 else if (waiting) |
2906 if (e.hash == h && |
2906 if (e.hash == h && |
2907 ((ek = e.key) == k || (ek != null && k.equals(ek)))) |
2907 ((ek = e.key) == k || (ek != null && k.equals(ek)))) |
2908 return e; |
2908 return e; |
2909 e = e.next; |
2909 e = e.next; |
2910 } |
2910 } |
2911 else if (U.compareAndSwapInt(this, LOCKSTATE, s, |
2911 else if (U.compareAndSetInt(this, LOCKSTATE, s, |
2912 s + READER)) { |
2912 s + READER)) { |
2913 TreeNode<K,V> r, p; |
2913 TreeNode<K,V> r, p; |
2914 try { |
2914 try { |
2915 p = ((r = root) == null ? null : |
2915 p = ((r = root) == null ? null : |
2916 r.findTreeNode(h, k, null)); |
2916 r.findTreeNode(h, k, null)); |