| 239 |
|
* |
| 240 |
|
* Indexing uses skip list parameters that maintain good search |
| 241 |
|
* performance while using sparser-than-usual indices: The |
| 242 |
< |
* hardwired parameters k=1, p=0.5 (see method randomLevel) mean |
| 242 |
> |
* hardwired parameters k=1, p=0.5 (see method addIndex) mean |
| 243 |
|
* that about one-quarter of the nodes have indices. Of those that |
| 244 |
|
* do, half have one level, a quarter have two, and so on (see |
| 245 |
|
* Pugh's Skip List Cookbook, sec 3.4). The expected total space |
| 277 |
|
* there is a fair amount of near-duplication of code to handle |
| 278 |
|
* variants. |
| 279 |
|
* |
| 280 |
+ |
* To produce random values without interference across threads, |
| 281 |
+ |
* we use within-JDK thread local random support (via the |
| 282 |
+ |
* "secondary seed", to avoid interference with user-level |
| 283 |
+ |
* ThreadLocalRandom.) |
| 284 |
+ |
* |
| 285 |
|
* A previous version of this class wrapped non-comparable keys |
| 286 |
|
* with their comparators to emulate Comparables when using |
| 287 |
|
* comparators vs Comparables. This saved the need to choose |
| 323 |
|
private static final long serialVersionUID = -8627078645895051609L; |
| 324 |
|
|
| 325 |
|
/** |
| 321 |
– |
* Generates the initial random seed for the cheaper per-instance |
| 322 |
– |
* random number generators used in randomLevel. |
| 323 |
– |
*/ |
| 324 |
– |
private static final Random seedGenerator = new Random(); |
| 325 |
– |
|
| 326 |
– |
/** |
| 326 |
|
* Special value used to identify base-level header |
| 327 |
|
*/ |
| 328 |
|
private static final Object BASE_HEADER = new Object(); |
| 847 |
|
Node<K,V> z = new Node<K,V>(kkey, value, n); |
| 848 |
|
if (!b.casNext(n, z)) |
| 849 |
|
break; // restart if lost race to append to b |
| 850 |
< |
int level = randomLevel(); |
| 852 |
< |
if (level > 0) |
| 853 |
< |
insertIndex(z, level); |
| 850 |
> |
addIndex(kkey, z); |
| 851 |
|
return null; |
| 852 |
|
} |
| 853 |
|
} |
| 854 |
|
} |
| 855 |
|
|
| 856 |
|
/** |
| 857 |
< |
* Returns a random level for inserting a new node. |
| 858 |
< |
* Hardwired to k=1, p=0.5, max 31 (see above and |
| 862 |
< |
* Pugh's "Skip List Cookbook", sec 3.4). |
| 857 |
> |
* Adds zero or more index nodes for the given key and node. |
| 858 |
> |
* Shared by plain and Cmp versions of put |
| 859 |
|
*/ |
| 860 |
< |
private int randomLevel() { |
| 861 |
< |
// int x = ThreadLocalRandom.nextSecondarySeed(); |
| 862 |
< |
int x = ThreadLocalRandom.current().nextInt(); |
| 863 |
< |
int level = 0; |
| 864 |
< |
if ((x & 0x80000001) == 0) { // test highest and lowest bits |
| 865 |
< |
do { ++level; } |
| 866 |
< |
while (((x >>>= 1) & 1) != 0); |
| 867 |
< |
} |
| 868 |
< |
return level; |
| 869 |
< |
} |
| 870 |
< |
|
| 871 |
< |
/** |
| 872 |
< |
* Creates and adds index nodes for the given node. |
| 873 |
< |
* @param z the node |
| 874 |
< |
* @param level the level of the index |
| 879 |
< |
*/ |
| 880 |
< |
private void insertIndex(Node<K,V> z, int level) { |
| 881 |
< |
HeadIndex<K,V> h = head; |
| 882 |
< |
int max = h.level; |
| 883 |
< |
|
| 884 |
< |
if (level <= max) { |
| 885 |
< |
Index<K,V> idx = null; |
| 886 |
< |
for (int i = 1; i <= level; ++i) |
| 887 |
< |
idx = new Index<K,V>(z, idx, null); |
| 888 |
< |
addIndex(idx, h, level); |
| 889 |
< |
|
| 890 |
< |
} else { // Add a new level |
| 891 |
< |
/* |
| 892 |
< |
* To reduce interference by other threads checking for |
| 893 |
< |
* empty levels in tryReduceLevel, new levels are added |
| 894 |
< |
* with initialized right pointers. Which in turn requires |
| 895 |
< |
* keeping levels in an array to access them while |
| 896 |
< |
* creating new head index nodes from the opposite |
| 897 |
< |
* direction. |
| 898 |
< |
*/ |
| 899 |
< |
level = max + 1; |
| 900 |
< |
Index<K,V>[] idxs = (Index<K,V>[])new Index<?,?>[level+1]; |
| 860 |
> |
private void addIndex(K key, Node<K,V> z) { |
| 861 |
> |
if (key == null || z == null) // don't postpone errors |
| 862 |
> |
throw new NullPointerException(); |
| 863 |
> |
int rnd; // generate a random level |
| 864 |
> |
Thread thread = Thread.currentThread(); |
| 865 |
> |
if ((rnd = UNSAFE.getInt(thread, SECONDARY)) == 0) // initialize |
| 866 |
> |
rnd = ThreadLocalRandom.current().nextInt(); |
| 867 |
> |
rnd ^= rnd << 13; // xorshift |
| 868 |
> |
rnd ^= rnd >>> 17; |
| 869 |
> |
rnd ^= rnd << 5; |
| 870 |
> |
UNSAFE.putInt(thread, SECONDARY, rnd); |
| 871 |
> |
if ((rnd & 0x80000001) == 0) { // test highest and lowest bits |
| 872 |
> |
int level = 1, max; |
| 873 |
> |
while (((rnd >>>= 1) & 1) != 0) |
| 874 |
> |
++level; |
| 875 |
|
Index<K,V> idx = null; |
| 876 |
< |
for (int i = 1; i <= level; ++i) |
| 877 |
< |
idxs[i] = idx = new Index<K,V>(z, idx, null); |
| 878 |
< |
|
| 879 |
< |
HeadIndex<K,V> oldh; |
| 906 |
< |
int k; |
| 907 |
< |
for (;;) { |
| 908 |
< |
oldh = head; |
| 909 |
< |
int oldLevel = oldh.level; |
| 910 |
< |
if (level <= oldLevel) { // lost race to add level |
| 911 |
< |
k = level; |
| 912 |
< |
break; |
| 913 |
< |
} |
| 914 |
< |
HeadIndex<K,V> newh = oldh; |
| 915 |
< |
Node<K,V> oldbase = oldh.node; |
| 916 |
< |
for (int j = oldLevel+1; j <= level; ++j) |
| 917 |
< |
newh = new HeadIndex<K,V>(oldbase, newh, idxs[j], j); |
| 918 |
< |
if (casHead(oldh, newh)) { |
| 919 |
< |
k = oldLevel; |
| 920 |
< |
break; |
| 921 |
< |
} |
| 876 |
> |
HeadIndex<K,V> h = head; |
| 877 |
> |
if (level <= (max = h.level)) { |
| 878 |
> |
for (int i = 1; i <= level; ++i) |
| 879 |
> |
idx = new Index<K,V>(z, idx, null); |
| 880 |
|
} |
| 881 |
< |
addIndex(idxs[k], oldh, k); |
| 882 |
< |
} |
| 883 |
< |
} |
| 884 |
< |
|
| 885 |
< |
/** |
| 886 |
< |
* Adds given index nodes from given level down to 1. |
| 887 |
< |
* @param idx the topmost index node being inserted |
| 888 |
< |
* @param h the value of head to use to insert. This must be |
| 889 |
< |
* snapshotted by callers to provide correct insertion level. |
| 890 |
< |
* @param indexLevel the level of the index |
| 891 |
< |
*/ |
| 892 |
< |
@SuppressWarnings("unchecked") |
| 893 |
< |
private void addIndex(Index<K,V> idx, HeadIndex<K,V> h, int indexLevel) { |
| 894 |
< |
// Track next level to insert in case of retries |
| 895 |
< |
int insertionLevel = indexLevel; |
| 896 |
< |
K key = idx.node.key; |
| 897 |
< |
if (key == null) throw new NullPointerException(); |
| 898 |
< |
Comparator<? super K> cmp = comparator; |
| 941 |
< |
// Similar to findPredecessor, but adding index nodes along |
| 942 |
< |
// path to key. |
| 943 |
< |
for (;;) { |
| 944 |
< |
int j = h.level; |
| 945 |
< |
Index<K,V> q = h; |
| 946 |
< |
Index<K,V> r = q.right; |
| 947 |
< |
Index<K,V> t = idx; |
| 948 |
< |
for (;;) { |
| 949 |
< |
if (r != null) { |
| 950 |
< |
Node<K,V> n = r.node; |
| 951 |
< |
// compare before deletion check avoids needing recheck |
| 952 |
< |
int c = (cmp == null) ? |
| 953 |
< |
((Comparable<? super K>)key).compareTo(n.key) : |
| 954 |
< |
cmp.compare(key, n.key); |
| 955 |
< |
if (n.value == null) { |
| 956 |
< |
if (!q.unlink(r)) |
| 957 |
< |
break; |
| 958 |
< |
r = q.right; |
| 959 |
< |
continue; |
| 960 |
< |
} |
| 961 |
< |
if (c > 0) { |
| 962 |
< |
q = r; |
| 963 |
< |
r = r.right; |
| 964 |
< |
continue; |
| 881 |
> |
else { // try to grow by one level |
| 882 |
> |
level = max + 1; // hold in array and later pick the one to use |
| 883 |
> |
Index<K,V>[] idxs = (Index<K,V>[])new Index<?,?>[level+1]; |
| 884 |
> |
for (int i = 1; i <= level; ++i) |
| 885 |
> |
idxs[i] = idx = new Index<K,V>(z, idx, null); |
| 886 |
> |
for (;;) { |
| 887 |
> |
h = head; |
| 888 |
> |
int oldLevel = h.level; |
| 889 |
> |
if (level <= oldLevel) // lost race to add level |
| 890 |
> |
break; |
| 891 |
> |
HeadIndex<K,V> newh = h; |
| 892 |
> |
Node<K,V> oldbase = h.node; |
| 893 |
> |
for (int j = oldLevel+1; j <= level; ++j) |
| 894 |
> |
newh = new HeadIndex<K,V>(oldbase, newh, idxs[j], j); |
| 895 |
> |
if (casHead(h, newh)) { |
| 896 |
> |
h = newh; |
| 897 |
> |
idx = idxs[level = oldLevel]; |
| 898 |
> |
break; |
| 899 |
|
} |
| 900 |
|
} |
| 901 |
< |
|
| 902 |
< |
if (j == insertionLevel) { |
| 903 |
< |
// Don't insert index if node already deleted |
| 904 |
< |
if (t.indexesDeletedNode()) { |
| 905 |
< |
if (cmp == null) |
| 906 |
< |
findNode((Comparable<? super K>)key); // cleans up |
| 907 |
< |
else |
| 908 |
< |
findNodeCmp(cmp, key); |
| 901 |
> |
} |
| 902 |
> |
Comparator<? super K> cmp = comparator; |
| 903 |
> |
for (int insertionLevel = level;;) { // find insertion points; splice |
| 904 |
> |
int j = h.level; |
| 905 |
> |
Index<K,V> q = h; |
| 906 |
> |
Index<K,V> r = q.right; |
| 907 |
> |
Index<K,V> t = idx; |
| 908 |
> |
for (;;) { |
| 909 |
> |
if (q == null || t == null) |
| 910 |
|
return; |
| 911 |
+ |
if (r != null) { |
| 912 |
+ |
Node<K,V> n = r.node; |
| 913 |
+ |
// compare before deletion check avoids needing recheck |
| 914 |
+ |
int c = (cmp == null) ? |
| 915 |
+ |
((Comparable<? super K>)key).compareTo(n.key) : |
| 916 |
+ |
cmp.compare(key, n.key); |
| 917 |
+ |
if (n.value == null) { |
| 918 |
+ |
if (!q.unlink(r)) |
| 919 |
+ |
break; |
| 920 |
+ |
r = q.right; |
| 921 |
+ |
continue; |
| 922 |
+ |
} |
| 923 |
+ |
if (c > 0) { |
| 924 |
+ |
q = r; |
| 925 |
+ |
r = r.right; |
| 926 |
+ |
continue; |
| 927 |
+ |
} |
| 928 |
|
} |
| 929 |
< |
if (!q.link(r, t)) |
| 930 |
< |
break; // restart |
| 931 |
< |
if (--insertionLevel == 0) { |
| 932 |
< |
// need final deletion check before return |
| 933 |
< |
if (t.indexesDeletedNode()) { |
| 934 |
< |
if (cmp == null) |
| 929 |
> |
|
| 930 |
> |
if (j == insertionLevel) { |
| 931 |
> |
if (!q.link(r, t)) |
| 932 |
> |
break; // restart |
| 933 |
> |
if (t.node.value == null) { |
| 934 |
> |
if (cmp == null) // node deleted; clean up |
| 935 |
|
findNode((Comparable<? super K>)key); |
| 936 |
|
else |
| 937 |
|
findNodeCmp(cmp, key); |
| 938 |
+ |
return; |
| 939 |
|
} |
| 940 |
< |
return; |
| 940 |
> |
if (--insertionLevel == 0) |
| 941 |
> |
return; |
| 942 |
|
} |
| 989 |
– |
} |
| 943 |
|
|
| 944 |
< |
if (--j >= insertionLevel && j < indexLevel) |
| 945 |
< |
t = t.down; |
| 946 |
< |
q = q.down; |
| 947 |
< |
r = q.right; |
| 944 |
> |
if (--j >= insertionLevel && j < level) |
| 945 |
> |
t = t.down; |
| 946 |
> |
q = q.down; |
| 947 |
> |
r = q.right; |
| 948 |
> |
} |
| 949 |
|
} |
| 950 |
|
} |
| 951 |
|
} |
| 1428 |
|
Node<K,V> z = new Node<K,V>(key, value, n); |
| 1429 |
|
if (!b.casNext(n, z)) |
| 1430 |
|
break; // restart if lost race to append to b |
| 1431 |
< |
int level = randomLevel(); |
| 1478 |
< |
if (level > 0) |
| 1479 |
< |
insertIndex(z, level); |
| 1431 |
> |
addIndex(key, z); |
| 1432 |
|
return null; |
| 1433 |
|
} |
| 1434 |
|
} |
| 1665 |
|
map.entrySet().iterator(); |
| 1666 |
|
while (it.hasNext()) { |
| 1667 |
|
Map.Entry<? extends K, ? extends V> e = it.next(); |
| 1668 |
< |
int j = randomLevel(); |
| 1669 |
< |
if (j > h.level) j = h.level + 1; |
| 1668 |
> |
int rnd = ThreadLocalRandom.current().nextInt(); |
| 1669 |
> |
int j = 0; |
| 1670 |
> |
if ((rnd & 0x80000001) == 0) { |
| 1671 |
> |
do { |
| 1672 |
> |
++j; |
| 1673 |
> |
} while (((rnd >>>= 1) & 1) != 0); |
| 1674 |
> |
if (j > h.level) j = h.level + 1; |
| 1675 |
> |
} |
| 1676 |
|
K k = e.getKey(); |
| 1677 |
|
V v = e.getValue(); |
| 1678 |
|
if (k == null || v == null) |
| 1763 |
|
throw new NullPointerException(); |
| 1764 |
|
K key = (K) k; |
| 1765 |
|
V val = (V) v; |
| 1766 |
< |
int j = randomLevel(); |
| 1767 |
< |
if (j > h.level) j = h.level + 1; |
| 1766 |
> |
int rnd = ThreadLocalRandom.current().nextInt(); |
| 1767 |
> |
int j = 0; |
| 1768 |
> |
if ((rnd & 0x80000001) == 0) { |
| 1769 |
> |
do { |
| 1770 |
> |
++j; |
| 1771 |
> |
} while (((rnd >>>= 1) & 1) != 0); |
| 1772 |
> |
if (j > h.level) j = h.level + 1; |
| 1773 |
> |
} |
| 1774 |
|
Node<K,V> z = new Node<K,V>(key, val, null); |
| 1775 |
|
basepred.next = z; |
| 1776 |
|
basepred = z; |
| 3580 |
|
Node<K,V> current; // current traversal node; initialize at origin |
| 3581 |
|
int est; // pseudo-size estimate |
| 3582 |
|
|
| 3583 |
+ |
CSLMSpliterator(ConcurrentSkipListMap<K,V> m) { |
| 3584 |
+ |
HeadIndex<K,V> h; Node<K,V> p; int d, n; Index<K,V> hd; |
| 3585 |
+ |
this.comparator = m.comparator; |
| 3586 |
+ |
this.fence = null; |
| 3587 |
+ |
for (;;) { // ensure h and n correspond to origin p |
| 3588 |
+ |
Node<K,V> b = (h = m.head).node; |
| 3589 |
+ |
if ((p = b.next) == null) { |
| 3590 |
+ |
n = 0; |
| 3591 |
+ |
break; |
| 3592 |
+ |
} |
| 3593 |
+ |
if (p.value != null) { |
| 3594 |
+ |
n = (d = h.level << 1) >= 31 ? Integer.MAX_VALUE : 1 << d; |
| 3595 |
+ |
break; |
| 3596 |
+ |
} |
| 3597 |
+ |
p.helpDelete(b, p.next); |
| 3598 |
+ |
} |
| 3599 |
+ |
this.est = n; |
| 3600 |
+ |
this.current = p; |
| 3601 |
+ |
this.row = (h.right == null && (hd = h.down) != null) ? hd : h; |
| 3602 |
+ |
} |
| 3603 |
+ |
|
| 3604 |
|
CSLMSpliterator(Comparator<? super K> comparator, Index<K,V> row, |
| 3605 |
|
Node<K,V> origin, K fence, int est) { |
| 3606 |
|
this.comparator = comparator; this.row = row; |
| 3619 |
|
} |
| 3620 |
|
|
| 3621 |
|
public final long estimateSize() { return (long)est; } |
| 3622 |
< |
public final boolean hasExactSize() { return est == 0; } |
| 3622 |
> |
public final boolean hasExactSize() { |
| 3623 |
> |
return est == 0 && current == null; // true only if empty |
| 3624 |
> |
} |
| 3625 |
|
public final boolean hasExactSplits() { return false; } |
| 3626 |
|
} |
| 3627 |
|
|
| 3628 |
|
// factory methods |
| 3629 |
|
final KeySpliterator<K,V> keySpliterator() { |
| 3630 |
< |
HeadIndex<K,V> h; Node<K,V> p; int d, n; |
| 3644 |
< |
for (;;) { // ensure h and n correspond to origin p |
| 3645 |
< |
Node<K,V> b = (h = head).node; |
| 3646 |
< |
if ((p = b.next) == null) { |
| 3647 |
< |
n = 0; |
| 3648 |
< |
break; |
| 3649 |
< |
} |
| 3650 |
< |
if (p.value != null) { |
| 3651 |
< |
n = (d = h.level << 1) >= 31 ? Integer.MAX_VALUE : 1 << d; |
| 3652 |
< |
break; |
| 3653 |
< |
} |
| 3654 |
< |
p.helpDelete(b, p.next); |
| 3655 |
< |
} |
| 3656 |
< |
return new KeySpliterator<K,V>(comparator, h, p, null, n); |
| 3630 |
> |
return new KeySpliterator<K,V>(this); |
| 3631 |
|
} |
| 3632 |
|
|
| 3633 |
|
final ValueSpliterator<K,V> valueSpliterator() { |
| 3634 |
< |
HeadIndex<K,V> h; Node<K,V> p; int d, n; |
| 3661 |
< |
for (;;) { // same as key version |
| 3662 |
< |
Node<K,V> b = (h = head).node; |
| 3663 |
< |
if ((p = b.next) == null) { |
| 3664 |
< |
n = 0; |
| 3665 |
< |
break; |
| 3666 |
< |
} |
| 3667 |
< |
if (p.value != null) { |
| 3668 |
< |
n = (d = h.level << 1) >= 31 ? Integer.MAX_VALUE : 1 << d; |
| 3669 |
< |
break; |
| 3670 |
< |
} |
| 3671 |
< |
p.helpDelete(b, p.next); |
| 3672 |
< |
} |
| 3673 |
< |
return new ValueSpliterator<K,V>(comparator, h, p, null, n); |
| 3634 |
> |
return new ValueSpliterator<K,V>(this); |
| 3635 |
|
} |
| 3636 |
|
|
| 3637 |
|
final EntrySpliterator<K,V> entrySpliterator() { |
| 3638 |
< |
HeadIndex<K,V> h; Node<K,V> p; int d, n; |
| 3678 |
< |
for (;;) { // same as key version |
| 3679 |
< |
Node<K,V> b = (h = head).node; |
| 3680 |
< |
if ((p = b.next) == null) { |
| 3681 |
< |
n = 0; |
| 3682 |
< |
break; |
| 3683 |
< |
} |
| 3684 |
< |
if (p.value != null) { |
| 3685 |
< |
n = (d = h.level << 1) >= 31 ? Integer.MAX_VALUE : 1 << d; |
| 3686 |
< |
break; |
| 3687 |
< |
} |
| 3688 |
< |
p.helpDelete(b, p.next); |
| 3689 |
< |
} |
| 3690 |
< |
return new EntrySpliterator<K,V>(comparator, head, p, null, n); |
| 3638 |
> |
return new EntrySpliterator<K,V>(this); |
| 3639 |
|
} |
| 3640 |
|
|
| 3641 |
|
static final class KeySpliterator<K,V> extends CSLMSpliterator<K,V> |
| 3642 |
|
implements Spliterator<K> { |
| 3643 |
+ |
KeySpliterator(ConcurrentSkipListMap<K,V> m) { super(m); } |
| 3644 |
|
KeySpliterator(Comparator<? super K> comparator, Index<K,V> row, |
| 3645 |
|
Node<K,V> origin, K fence, int est) { |
| 3646 |
|
super(comparator, row, origin, fence, est); |
| 3717 |
|
|
| 3718 |
|
static final class ValueSpliterator<K,V> extends CSLMSpliterator<K,V> |
| 3719 |
|
implements Spliterator<V> { |
| 3720 |
+ |
ValueSpliterator(ConcurrentSkipListMap<K,V> m) { super(m); } |
| 3721 |
|
ValueSpliterator(Comparator<? super K> comparator, Index<K,V> row, |
| 3722 |
|
Node<K,V> origin, K fence, int est) { |
| 3723 |
|
super(comparator, row, origin, fence, est); |
| 3795 |
|
|
| 3796 |
|
static final class EntrySpliterator<K,V> extends CSLMSpliterator<K,V> |
| 3797 |
|
implements Spliterator<Map.Entry<K,V>> { |
| 3798 |
+ |
EntrySpliterator(ConcurrentSkipListMap<K,V> m) { super(m); } |
| 3799 |
|
EntrySpliterator(Comparator<? super K> comparator, Index<K,V> row, |
| 3800 |
|
Node<K,V> origin, K fence, int est) { |
| 3801 |
|
super(comparator, row, origin, fence, est); |
| 3877 |
|
// Unsafe mechanics |
| 3878 |
|
private static final sun.misc.Unsafe UNSAFE; |
| 3879 |
|
private static final long headOffset; |
| 3880 |
+ |
private static final long SECONDARY; |
| 3881 |
|
static { |
| 3882 |
|
try { |
| 3883 |
|
UNSAFE = sun.misc.Unsafe.getUnsafe(); |
| 3884 |
|
Class<?> k = ConcurrentSkipListMap.class; |
| 3885 |
|
headOffset = UNSAFE.objectFieldOffset |
| 3886 |
|
(k.getDeclaredField("head")); |
| 3887 |
+ |
Class<?> tk = Thread.class; |
| 3888 |
+ |
SECONDARY = UNSAFE.objectFieldOffset |
| 3889 |
+ |
(tk.getDeclaredField("threadLocalRandomSecondarySeed")); |
| 3890 |
+ |
|
| 3891 |
|
} catch (Exception e) { |
| 3892 |
|
throw new Error(e); |
| 3893 |
|
} |
