4 |
|
* http://creativecommons.org/licenses/publicdomain |
5 |
|
*/ |
6 |
|
|
7 |
< |
package jsr166x; |
7 |
> |
package jsr166x; |
8 |
|
|
9 |
|
import java.util.*; |
10 |
|
import java.util.concurrent.*; |
56 |
|
* |
57 |
|
* @author Doug Lea |
58 |
|
* @param <K> the type of keys maintained by this map |
59 |
< |
* @param <V> the type of mapped values |
59 |
> |
* @param <V> the type of mapped values |
60 |
|
*/ |
61 |
< |
public class ConcurrentSkipListMap<K,V> extends AbstractMap<K,V> |
61 |
> |
public class ConcurrentSkipListMap<K,V> extends AbstractMap<K,V> |
62 |
|
implements ConcurrentNavigableMap<K,V>, |
63 |
< |
Cloneable, |
63 |
> |
Cloneable, |
64 |
|
java.io.Serializable { |
65 |
|
/* |
66 |
|
* This class implements a tree-like two-dimensionally linked skip |
74 |
|
* possible list with 2 levels of index: |
75 |
|
* |
76 |
|
* Head nodes Index nodes |
77 |
< |
* +-+ right +-+ +-+ |
77 |
> |
* +-+ right +-+ +-+ |
78 |
|
* |2|---------------->| |--------------------->| |->null |
79 |
< |
* +-+ +-+ +-+ |
79 |
> |
* +-+ +-+ +-+ |
80 |
|
* | down | | |
81 |
|
* v v v |
82 |
< |
* +-+ +-+ +-+ +-+ +-+ +-+ |
82 |
> |
* +-+ +-+ +-+ +-+ +-+ +-+ |
83 |
|
* |1|----------->| |->| |------>| |----------->| |------>| |->null |
84 |
< |
* +-+ +-+ +-+ +-+ +-+ +-+ |
84 |
> |
* +-+ +-+ +-+ +-+ +-+ +-+ |
85 |
|
* v | | | | | |
86 |
|
* Nodes next v v v v v |
87 |
< |
* +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ |
87 |
> |
* +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ |
88 |
|
* | |->|A|->|B|->|C|->|D|->|E|->|F|->|G|->|H|->|I|->|J|->|K|->null |
89 |
< |
* +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ |
89 |
> |
* +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ |
90 |
|
* |
91 |
|
* The base lists use a variant of the HM linked ordered set |
92 |
|
* algorithm. See Tim Harris, "A pragmatic implementation of |
145 |
|
* Here's the sequence of events for a deletion of node n with |
146 |
|
* predecessor b and successor f, initially: |
147 |
|
* |
148 |
< |
* +------+ +------+ +------+ |
148 |
> |
* +------+ +------+ +------+ |
149 |
|
* ... | b |------>| n |----->| f | ... |
150 |
< |
* +------+ +------+ +------+ |
150 |
> |
* +------+ +------+ +------+ |
151 |
|
* |
152 |
|
* 1. CAS n's value field from non-null to null. |
153 |
|
* From this point on, no public operations encountering |
161 |
|
* |
162 |
|
* +------+ +------+ +------+ +------+ |
163 |
|
* ... | b |------>| n |----->|marker|------>| f | ... |
164 |
< |
* +------+ +------+ +------+ +------+ |
164 |
> |
* +------+ +------+ +------+ +------+ |
165 |
|
* |
166 |
|
* 3. CAS b's next pointer over both n and its marker. |
167 |
|
* From this point on, no new traversals will encounter n, |
168 |
|
* and it can eventually be GCed. |
169 |
|
* +------+ +------+ |
170 |
|
* ... | b |----------------------------------->| f | ... |
171 |
< |
* +------+ +------+ |
172 |
< |
* |
171 |
> |
* +------+ +------+ |
172 |
> |
* |
173 |
|
* A failure at step 1 leads to simple retry due to a lost race |
174 |
|
* with another operation. Steps 2-3 can fail because some other |
175 |
|
* thread noticed during a traversal a node with null value and |
188 |
|
* nodes. This doesn't change the basic algorithm except for the |
189 |
|
* need to make sure base traversals start at predecessors (here, |
190 |
|
* b) that are not (structurally) deleted, otherwise retrying |
191 |
< |
* after processing the deletion. |
191 |
> |
* after processing the deletion. |
192 |
|
* |
193 |
|
* Index levels are maintained as lists with volatile next fields, |
194 |
|
* using CAS to link and unlink. Races are allowed in index-list |
266 |
|
* For explanation of algorithms sharing at least a couple of |
267 |
|
* features with this one, see Mikhail Fomitchev's thesis |
268 |
|
* (http://www.cs.yorku.ca/~mikhail/), Keir Fraser's thesis |
269 |
< |
* (http://www.cl.cam.ac.uk/users/kaf24/), and Håkan Sundell's |
269 |
> |
* (http://www.cl.cam.ac.uk/users/kaf24/), and Hakan Sundell's |
270 |
|
* thesis (http://www.cs.chalmers.se/~phs/). |
271 |
|
* |
272 |
|
* Given the use of tree-like index nodes, you might wonder why |
292 |
|
|
293 |
|
/** |
294 |
|
* Special value used to identify base-level header |
295 |
< |
*/ |
295 |
> |
*/ |
296 |
|
private static final Object BASE_HEADER = new Object(); |
297 |
|
|
298 |
|
/** |
299 |
< |
* The topmost head index of the skiplist. |
299 |
> |
* The topmost head index of the skiplist. |
300 |
|
*/ |
301 |
|
private transient volatile HeadIndex<K,V> head; |
302 |
|
|
331 |
|
*/ |
332 |
|
final void initialize() { |
333 |
|
keySet = null; |
334 |
< |
entrySet = null; |
334 |
> |
entrySet = null; |
335 |
|
values = null; |
336 |
|
descendingEntrySet = null; |
337 |
|
descendingKeySet = null; |
341 |
|
} |
342 |
|
|
343 |
|
/** Updater for casHead */ |
344 |
< |
private static final |
345 |
< |
AtomicReferenceFieldUpdater<ConcurrentSkipListMap, HeadIndex> |
344 |
> |
private static final |
345 |
> |
AtomicReferenceFieldUpdater<ConcurrentSkipListMap, HeadIndex> |
346 |
|
headUpdater = AtomicReferenceFieldUpdater.newUpdater |
347 |
|
(ConcurrentSkipListMap.class, HeadIndex.class, "head"); |
348 |
|
|
390 |
|
} |
391 |
|
|
392 |
|
/** Updater for casNext */ |
393 |
< |
static final AtomicReferenceFieldUpdater<Node, Node> |
393 |
> |
static final AtomicReferenceFieldUpdater<Node, Node> |
394 |
|
nextUpdater = AtomicReferenceFieldUpdater.newUpdater |
395 |
|
(Node.class, Node.class, "next"); |
396 |
|
|
397 |
|
/** Updater for casValue */ |
398 |
< |
static final AtomicReferenceFieldUpdater<Node, Object> |
398 |
> |
static final AtomicReferenceFieldUpdater<Node, Object> |
399 |
|
valueUpdater = AtomicReferenceFieldUpdater.newUpdater |
400 |
|
(Node.class, Object.class, "value"); |
401 |
|
|
466 |
|
|
467 |
|
/** |
468 |
|
* Return value if this node contains a valid key-value pair, |
469 |
< |
* else null. |
469 |
> |
* else null. |
470 |
|
* @return this node's value if it isn't a marker or header or |
471 |
|
* is deleted, else null. |
472 |
|
*/ |
508 |
|
|
509 |
|
/** |
510 |
|
* Creates index node with given values |
511 |
< |
*/ |
511 |
> |
*/ |
512 |
|
Index(Node<K,V> node, Index<K,V> down, Index<K,V> right) { |
513 |
|
this.node = node; |
514 |
|
this.key = node.key; |
517 |
|
} |
518 |
|
|
519 |
|
/** Updater for casRight */ |
520 |
< |
static final AtomicReferenceFieldUpdater<Index, Index> |
520 |
> |
static final AtomicReferenceFieldUpdater<Index, Index> |
521 |
|
rightUpdater = AtomicReferenceFieldUpdater.newUpdater |
522 |
|
(Index.class, Index.class, "right"); |
523 |
|
|
546 |
|
*/ |
547 |
|
final boolean link(Index<K,V> succ, Index<K,V> newSucc) { |
548 |
|
Node<K,V> n = node; |
549 |
< |
newSucc.right = succ; |
549 |
> |
newSucc.right = succ; |
550 |
|
return n.value != null && casRight(succ, newSucc); |
551 |
|
} |
552 |
|
|
573 |
|
super(node, down, right); |
574 |
|
this.level = level; |
575 |
|
} |
576 |
< |
} |
576 |
> |
} |
577 |
|
|
578 |
|
/* ---------------- Map.Entry support -------------- */ |
579 |
|
|
581 |
|
* An immutable representation of a key-value mapping as it |
582 |
|
* existed at some point in time. This class does <em>not</em> |
583 |
|
* support the <tt>Map.Entry.setValue</tt> method. |
584 |
< |
*/ |
584 |
> |
*/ |
585 |
|
static class SnapshotEntry<K,V> implements Map.Entry<K,V> { |
586 |
< |
private final K key; |
587 |
< |
private final V value; |
586 |
> |
private final K key; |
587 |
> |
private final V value; |
588 |
|
|
589 |
|
/** |
590 |
|
* Creates a new entry representing the given key and value. |
592 |
|
* @param value the value |
593 |
|
*/ |
594 |
|
SnapshotEntry(K key, V value) { |
595 |
< |
this.key = key; |
596 |
< |
this.value = value; |
597 |
< |
} |
598 |
< |
|
599 |
< |
/** |
600 |
< |
* Returns the key corresponding to this entry. |
601 |
< |
* |
602 |
< |
* @return the key corresponding to this entry. |
603 |
< |
*/ |
595 |
> |
this.key = key; |
596 |
> |
this.value = value; |
597 |
> |
} |
598 |
> |
|
599 |
> |
/** |
600 |
> |
* Returns the key corresponding to this entry. |
601 |
> |
* |
602 |
> |
* @return the key corresponding to this entry. |
603 |
> |
*/ |
604 |
|
public K getKey() { |
605 |
|
return key; |
606 |
|
} |
607 |
|
|
608 |
< |
/** |
609 |
< |
* Returns the value corresponding to this entry. |
610 |
< |
* |
611 |
< |
* @return the value corresponding to this entry. |
612 |
< |
*/ |
608 |
> |
/** |
609 |
> |
* Returns the value corresponding to this entry. |
610 |
> |
* |
611 |
> |
* @return the value corresponding to this entry. |
612 |
> |
*/ |
613 |
|
public V getValue() { |
614 |
< |
return value; |
614 |
> |
return value; |
615 |
|
} |
616 |
|
|
617 |
< |
/** |
618 |
< |
* Always fails, throwing <tt>UnsupportedOperationException</tt>. |
619 |
< |
* @throws UnsupportedOperationException always. |
617 |
> |
/** |
618 |
> |
* Always fails, throwing <tt>UnsupportedOperationException</tt>. |
619 |
> |
* @throws UnsupportedOperationException always. |
620 |
|
*/ |
621 |
|
public V setValue(V value) { |
622 |
|
throw new UnsupportedOperationException(); |
649 |
|
* @return a String representation of this entry. |
650 |
|
*/ |
651 |
|
public String toString() { |
652 |
< |
return getKey() + "=" + getValue(); |
652 |
> |
return getKey() + "=" + getValue(); |
653 |
|
} |
654 |
|
} |
655 |
|
|
688 |
|
* which is propagated back to caller. |
689 |
|
*/ |
690 |
|
private Comparable<K> comparable(Object key) throws ClassCastException { |
691 |
< |
if (key == null) |
691 |
> |
if (key == null) |
692 |
|
throw new NullPointerException(); |
693 |
< |
return (comparator != null) |
694 |
< |
? new ComparableUsingComparator(key, comparator) |
693 |
> |
return (comparator != null) |
694 |
> |
? new ComparableUsingComparator(key, comparator) |
695 |
|
: (Comparable<K>)key; |
696 |
|
} |
697 |
|
|
713 |
|
* fence oare null. Needed mainly in submap operations. |
714 |
|
*/ |
715 |
|
boolean inHalfOpenRange(K key, K least, K fence) { |
716 |
< |
if (key == null) |
716 |
> |
if (key == null) |
717 |
|
throw new NullPointerException(); |
718 |
|
return ((least == null || compare(key, least) >= 0) && |
719 |
|
(fence == null || compare(key, fence) < 0)); |
724 |
|
* or equal to fence. Needed mainly in submap operations. |
725 |
|
*/ |
726 |
|
boolean inOpenRange(K key, K least, K fence) { |
727 |
< |
if (key == null) |
727 |
> |
if (key == null) |
728 |
|
throw new NullPointerException(); |
729 |
|
return ((least == null || compare(key, least) >= 0) && |
730 |
|
(fence == null || compare(key, fence) <= 0)); |
738 |
|
* unlinks indexes to deleted nodes found along the way. Callers |
739 |
|
* rely on this side-effect of clearing indices to deleted nodes. |
740 |
|
* @param key the key |
741 |
< |
* @return a predecessor of key |
741 |
> |
* @return a predecessor of key |
742 |
|
*/ |
743 |
|
private Node<K,V> findPredecessor(Comparable<K> key) { |
744 |
|
for (;;) { |
757 |
|
continue; |
758 |
|
} |
759 |
|
} |
760 |
< |
if ((d = q.down) != null) |
760 |
> |
if ((d = q.down) != null) |
761 |
|
q = d; |
762 |
|
else |
763 |
|
return q.node; |
787 |
|
* here because doing so would not usually outweigh cost of |
788 |
|
* restarting. |
789 |
|
* |
790 |
< |
* (3) n is a marker or n's predecessor's value field is null, |
790 |
> |
* (3) n is a marker or n's predecessor's value field is null, |
791 |
|
* indicating (among other possibilities) that |
792 |
|
* findPredecessor returned a deleted node. We can't unlink |
793 |
|
* the node because we don't know its predecessor, so rely |
805 |
|
* findLast. They can't easily share code because each uses the |
806 |
|
* reads of fields held in locals occurring in the orders they |
807 |
|
* were performed. |
808 |
< |
* |
808 |
> |
* |
809 |
|
* @param key the key |
810 |
|
* @return node holding key, or null if no such. |
811 |
|
*/ |
814 |
|
Node<K,V> b = findPredecessor(key); |
815 |
|
Node<K,V> n = b.next; |
816 |
|
for (;;) { |
817 |
< |
if (n == null) |
817 |
> |
if (n == null) |
818 |
|
return null; |
819 |
|
Node<K,V> f = n.next; |
820 |
|
if (n != b.next) // inconsistent read |
829 |
|
int c = key.compareTo(n.key); |
830 |
|
if (c < 0) |
831 |
|
return null; |
832 |
< |
if (c == 0) |
832 |
> |
if (c == 0) |
833 |
|
return n; |
834 |
|
b = n; |
835 |
|
n = f; |
837 |
|
} |
838 |
|
} |
839 |
|
|
840 |
< |
/** |
840 |
> |
/** |
841 |
|
* Specialized variant of findNode to perform Map.get. Does a weak |
842 |
|
* traversal, not bothering to fix any deleted index nodes, |
843 |
|
* returning early if it happens to see key in index, and passing |
856 |
|
for (;;) { |
857 |
|
K rk; |
858 |
|
Index<K,V> d, r; |
859 |
< |
if ((r = q.right) != null && |
859 |
> |
if ((r = q.right) != null && |
860 |
|
(rk = r.key) != null && rk != bound) { |
861 |
|
int c = key.compareTo(rk); |
862 |
|
if (c > 0) { |
869 |
|
} |
870 |
|
bound = rk; |
871 |
|
} |
872 |
< |
if ((d = q.down) != null) |
872 |
> |
if ((d = q.down) != null) |
873 |
|
q = d; |
874 |
|
else { |
875 |
|
for (Node<K,V> n = q.node.next; n != null; n = n.next) { |
916 |
|
/** |
917 |
|
* Main insertion method. Adds element if not present, or |
918 |
|
* replaces value if present and onlyIfAbsent is false. |
919 |
< |
* @param kkey the key |
919 |
> |
* @param kkey the key |
920 |
|
* @param value the value that must be associated with key |
921 |
|
* @param onlyIfAbsent if should not insert if already present |
922 |
|
* @return the old value, or null if newly inserted |
930 |
|
if (n != null) { |
931 |
|
Node<K,V> f = n.next; |
932 |
|
if (n != b.next) // inconsistent read |
933 |
< |
break;; |
933 |
> |
break; |
934 |
|
Object v = n.value; |
935 |
|
if (v == null) { // n is deleted |
936 |
|
n.helpDelete(b, f); |
952 |
|
} |
953 |
|
// else c < 0; fall through |
954 |
|
} |
955 |
< |
|
955 |
> |
|
956 |
|
Node<K,V> z = new Node<K,V>(kkey, value, n); |
957 |
< |
if (!b.casNext(n, z)) |
957 |
> |
if (!b.casNext(n, z)) |
958 |
|
break; // restart if lost race to append to b |
959 |
< |
int level = randomLevel(); |
960 |
< |
if (level > 0) |
959 |
> |
int level = randomLevel(); |
960 |
> |
if (level > 0) |
961 |
|
insertIndex(z, level); |
962 |
|
return null; |
963 |
|
} |
979 |
|
int level = 0; |
980 |
|
int r = randomSeed; |
981 |
|
randomSeed = r * 134775813 + 1; |
982 |
< |
if (r < 0) { |
983 |
< |
while ((r <<= 1) > 0) |
982 |
> |
if (r < 0) { |
983 |
> |
while ((r <<= 1) > 0) |
984 |
|
++level; |
985 |
|
} |
986 |
|
return level; |
1013 |
|
level = max + 1; |
1014 |
|
Index<K,V>[] idxs = (Index<K,V>[])new Index[level+1]; |
1015 |
|
Index<K,V> idx = null; |
1016 |
< |
for (int i = 1; i <= level; ++i) |
1016 |
> |
for (int i = 1; i <= level; ++i) |
1017 |
|
idxs[i] = idx = new Index<K,V>(z, idx, null); |
1018 |
|
|
1019 |
|
HeadIndex<K,V> oldh; |
1027 |
|
} |
1028 |
|
HeadIndex<K,V> newh = oldh; |
1029 |
|
Node<K,V> oldbase = oldh.node; |
1030 |
< |
for (int j = oldLevel+1; j <= level; ++j) |
1030 |
> |
for (int j = oldLevel+1; j <= level; ++j) |
1031 |
|
newh = new HeadIndex<K,V>(oldbase, newh, idxs[j], j); |
1032 |
|
if (casHead(oldh, newh)) { |
1033 |
|
k = oldLevel; |
1065 |
|
if (q.unlink(r)) |
1066 |
|
continue; |
1067 |
|
else |
1068 |
< |
break; |
1068 |
> |
break; |
1069 |
|
} |
1070 |
|
if (c > 0) { |
1071 |
|
q = r; |
1079 |
|
findNode(key); // cleans up |
1080 |
|
return; |
1081 |
|
} |
1082 |
< |
if (!q.link(r, t)) |
1082 |
> |
if (!q.link(r, t)) |
1083 |
|
break; // restart |
1084 |
|
if (--insertionLevel == 0) { |
1085 |
|
// need final deletion check before return |
1086 |
< |
if (t.indexesDeletedNode()) |
1087 |
< |
findNode(key); |
1086 |
> |
if (t.indexesDeletedNode()) |
1087 |
> |
findNode(key); |
1088 |
|
return; |
1089 |
|
} |
1090 |
|
} |
1091 |
|
|
1092 |
< |
if (j > insertionLevel && j <= indexLevel) |
1092 |
> |
if (j > insertionLevel && j <= indexLevel) |
1093 |
|
t = t.down; |
1094 |
|
q = q.down; |
1095 |
|
--j; |
1111 |
|
* index nodes because it might be the case that some or all |
1112 |
|
* indexes hadn't been inserted yet for this node during initial |
1113 |
|
* search for it, and we'd like to ensure lack of garbage |
1114 |
< |
* retention, so must call to be sure. |
1114 |
> |
* retention, so must call to be sure. |
1115 |
|
* |
1116 |
|
* @param okey the key |
1117 |
|
* @param value if non-null, the value that must be |
1120 |
|
*/ |
1121 |
|
private V doRemove(Object okey, Object value) { |
1122 |
|
Comparable<K> key = comparable(okey); |
1123 |
< |
for (;;) { |
1123 |
> |
for (;;) { |
1124 |
|
Node<K,V> b = findPredecessor(key); |
1125 |
|
Node<K,V> n = b.next; |
1126 |
|
for (;;) { |
1127 |
< |
if (n == null) |
1127 |
> |
if (n == null) |
1128 |
|
return null; |
1129 |
|
Node<K,V> f = n.next; |
1130 |
|
if (n != b.next) // inconsistent read |
1144 |
|
n = f; |
1145 |
|
continue; |
1146 |
|
} |
1147 |
< |
if (value != null && !value.equals(v)) |
1148 |
< |
return null; |
1149 |
< |
if (!n.casValue(v, null)) |
1147 |
> |
if (value != null && !value.equals(v)) |
1148 |
> |
return null; |
1149 |
> |
if (!n.casValue(v, null)) |
1150 |
|
break; |
1151 |
< |
if (!n.appendMarker(f) || !b.casNext(n, f)) |
1151 |
> |
if (!n.appendMarker(f) || !b.casNext(n, f)) |
1152 |
|
findNode(key); // Retry via findNode |
1153 |
|
else { |
1154 |
|
findPredecessor(key); // Clean index |
1155 |
< |
if (head.right == null) |
1155 |
> |
if (head.right == null) |
1156 |
|
tryReduceLevel(); |
1157 |
|
} |
1158 |
|
return (V)v; |
1185 |
|
HeadIndex<K,V> d; |
1186 |
|
HeadIndex<K,V> e; |
1187 |
|
if (h.level > 3 && |
1188 |
< |
(d = (HeadIndex<K,V>)h.down) != null && |
1189 |
< |
(e = (HeadIndex<K,V>)d.down) != null && |
1190 |
< |
e.right == null && |
1191 |
< |
d.right == null && |
1188 |
> |
(d = (HeadIndex<K,V>)h.down) != null && |
1189 |
> |
(e = (HeadIndex<K,V>)d.down) != null && |
1190 |
> |
e.right == null && |
1191 |
> |
d.right == null && |
1192 |
|
h.right == null && |
1193 |
|
casHead(h, d) && // try to set |
1194 |
|
h.right != null) // recheck |
1214 |
|
Node<K,V> n = b.next; |
1215 |
|
if (n == null) |
1216 |
|
return null; |
1217 |
< |
if (n.value != null) |
1217 |
> |
if (n.value != null) |
1218 |
|
return n; |
1219 |
|
n.helpDelete(b, n.next); |
1220 |
|
} |
1221 |
|
} |
1222 |
|
|
1223 |
|
/** |
1224 |
< |
* Remove first entry; return either its key or a snapshot. |
1224 |
> |
* Remove first entry; return either its key or a snapshot. |
1225 |
|
* @param keyOnly if true return key, else return SnapshotEntry |
1226 |
|
* (This is a little ugly, but avoids code duplication.) |
1227 |
|
* @return null if empty, first key if keyOnly true, else key,value entry |
1228 |
|
*/ |
1229 |
|
Object doRemoveFirst(boolean keyOnly) { |
1230 |
< |
for (;;) { |
1230 |
> |
for (;;) { |
1231 |
|
Node<K,V> b = head.node; |
1232 |
|
Node<K,V> n = b.next; |
1233 |
< |
if (n == null) |
1233 |
> |
if (n == null) |
1234 |
|
return null; |
1235 |
|
Node<K,V> f = n.next; |
1236 |
|
if (n != b.next) |
1260 |
|
for (;;) { |
1261 |
|
Index<K,V> r = q.right; |
1262 |
|
if (r != null && r.indexesDeletedNode() && !q.unlink(r)) |
1263 |
< |
break; |
1263 |
> |
break; |
1264 |
|
if ((q = q.down) == null) { |
1265 |
< |
if (head.right == null) |
1265 |
> |
if (head.right == null) |
1266 |
|
tryReduceLevel(); |
1267 |
|
return; |
1268 |
|
} |
1271 |
|
} |
1272 |
|
|
1273 |
|
/** |
1274 |
< |
* Remove first entry; return key or null if empty. |
1274 |
> |
* Remove first entry; return key or null if empty. |
1275 |
|
*/ |
1276 |
|
K pollFirstKey() { |
1277 |
|
return (K)doRemoveFirst(true); |
1296 |
|
if (r.indexesDeletedNode()) { |
1297 |
|
q.unlink(r); |
1298 |
|
q = head; // restart |
1299 |
< |
} |
1299 |
> |
} |
1300 |
|
else |
1301 |
|
q = r; |
1302 |
|
} else if ((d = q.down) != null) { |
1305 |
|
Node<K,V> b = q.node; |
1306 |
|
Node<K,V> n = b.next; |
1307 |
|
for (;;) { |
1308 |
< |
if (n == null) |
1308 |
> |
if (n == null) |
1309 |
|
return (b.isBaseHeader())? null : b; |
1310 |
|
Node<K,V> f = n.next; // inconsistent read |
1311 |
|
if (n != b.next) |
1332 |
|
* @return null if empty, last key if keyOnly true, else key,value entry |
1333 |
|
*/ |
1334 |
|
Object doRemoveLast(boolean keyOnly) { |
1335 |
< |
for (;;) { |
1335 |
> |
for (;;) { |
1336 |
|
Node<K,V> b = findPredecessorOfLast(); |
1337 |
|
Node<K,V> n = b.next; |
1338 |
|
if (n == null) { |
1339 |
|
if (b.isBaseHeader()) // empty |
1340 |
|
return null; |
1341 |
< |
else |
1341 |
> |
else |
1342 |
|
continue; // all b's successors are deleted; retry |
1343 |
|
} |
1344 |
|
for (;;) { |
1357 |
|
n = f; |
1358 |
|
continue; |
1359 |
|
} |
1360 |
< |
if (!n.casValue(v, null)) |
1360 |
> |
if (!n.casValue(v, null)) |
1361 |
|
break; |
1362 |
|
K key = n.key; |
1363 |
|
Comparable<K> ck = comparable(key); |
1364 |
< |
if (!n.appendMarker(f) || !b.casNext(n, f)) |
1364 |
> |
if (!n.appendMarker(f) || !b.casNext(n, f)) |
1365 |
|
findNode(ck); // Retry via findNode |
1366 |
|
else { |
1367 |
|
findPredecessor(ck); // Clean index |
1368 |
< |
if (head.right == null) |
1368 |
> |
if (head.right == null) |
1369 |
|
tryReduceLevel(); |
1370 |
|
} |
1371 |
|
return (keyOnly)? key : new SnapshotEntry<K,V>(key, (V)v); |
1378 |
|
* last valid node. Needed by doRemoveLast. It is possible that |
1379 |
|
* all successors of returned node will have been deleted upon |
1380 |
|
* return, in which case this method can be retried. |
1381 |
< |
* @return likely predecessor of last node. |
1381 |
> |
* @return likely predecessor of last node. |
1382 |
|
*/ |
1383 |
|
private Node<K,V> findPredecessorOfLast() { |
1384 |
|
for (;;) { |
1396 |
|
continue; |
1397 |
|
} |
1398 |
|
} |
1399 |
< |
if ((d = q.down) != null) |
1399 |
> |
if ((d = q.down) != null) |
1400 |
|
q = d; |
1401 |
< |
else |
1401 |
> |
else |
1402 |
|
return q.node; |
1403 |
|
} |
1404 |
|
} |
1405 |
|
} |
1406 |
|
|
1407 |
|
/** |
1408 |
< |
* Remove last entry; return key or null if empty. |
1408 |
> |
* Remove last entry; return key or null if empty. |
1409 |
|
*/ |
1410 |
|
K pollLastKey() { |
1411 |
|
return (K)doRemoveLast(true); |
1431 |
|
Node<K,V> b = findPredecessor(key); |
1432 |
|
Node<K,V> n = b.next; |
1433 |
|
for (;;) { |
1434 |
< |
if (n == null) |
1434 |
> |
if (n == null) |
1435 |
|
return ((rel & LT) == 0 || b.isBaseHeader())? null : b; |
1436 |
|
Node<K,V> f = n.next; |
1437 |
|
if (n != b.next) // inconsistent read |
1512 |
|
return null; |
1513 |
|
K k = n.key; |
1514 |
|
V v = n.getValidValue(); |
1515 |
< |
if (v != null) |
1515 |
> |
if (v != null) |
1516 |
|
return keyOnly? k : new SnapshotEntry<K,V>(k, v); |
1517 |
|
} |
1518 |
|
} |
1563 |
|
|
1564 |
|
/** |
1565 |
|
* Constructs a new empty map, sorted according to the keys' natural |
1566 |
< |
* order. |
1566 |
> |
* order. |
1567 |
|
*/ |
1568 |
|
public ConcurrentSkipListMap() { |
1569 |
|
this.comparator = null; |
1584 |
|
|
1585 |
|
/** |
1586 |
|
* Constructs a new map containing the same mappings as the given map, |
1587 |
< |
* sorted according to the keys' <i>natural order</i>. |
1587 |
> |
* sorted according to the keys' <i>natural order</i>. |
1588 |
|
* |
1589 |
|
* @param m the map whose mappings are to be placed in this map. |
1590 |
|
* @throws ClassCastException if the keys in m are not Comparable, or |
1599 |
|
|
1600 |
|
/** |
1601 |
|
* Constructs a new map containing the same mappings as the given |
1602 |
< |
* <tt>SortedMap</tt>, sorted according to the same ordering. |
1602 |
> |
* <tt>SortedMap</tt>, sorted according to the same ordering. |
1603 |
|
* @param m the sorted map whose mappings are to be placed in this |
1604 |
|
* map, and whose comparator is to be used to sort this map. |
1605 |
|
* @throws NullPointerException if the specified sorted map is |
1647 |
|
ArrayList<Index<K,V>> preds = new ArrayList<Index<K,V>>(); |
1648 |
|
|
1649 |
|
// initialize |
1650 |
< |
for (int i = 0; i <= h.level; ++i) |
1650 |
> |
for (int i = 0; i <= h.level; ++i) |
1651 |
|
preds.add(null); |
1652 |
|
Index<K,V> q = h; |
1653 |
|
for (int i = h.level; i > 0; --i) { |
1655 |
|
q = q.down; |
1656 |
|
} |
1657 |
|
|
1658 |
< |
Iterator<? extends Map.Entry<? extends K, ? extends V>> it = |
1658 |
> |
Iterator<? extends Map.Entry<? extends K, ? extends V>> it = |
1659 |
|
map.entrySet().iterator(); |
1660 |
|
while (it.hasNext()) { |
1661 |
|
Map.Entry<? extends K, ? extends V> e = it.next(); |
1672 |
|
Index<K,V> idx = null; |
1673 |
|
for (int i = 1; i <= j; ++i) { |
1674 |
|
idx = new Index<K,V>(z, idx, null); |
1675 |
< |
if (i > h.level) |
1675 |
> |
if (i > h.level) |
1676 |
|
h = new HeadIndex<K,V>(h.node, h, idx, i); |
1677 |
|
|
1678 |
|
if (i < preds.size()) { |
1692 |
|
* Save the state of the <tt>Map</tt> instance to a stream. |
1693 |
|
* |
1694 |
|
* @serialData The key (Object) and value (Object) for each |
1695 |
< |
* key-value mapping represented by the Map, followed by |
1695 |
> |
* key-value mapping represented by the Map, followed by |
1696 |
|
* <tt>null</tt>. The key-value mappings are emitted in key-order |
1697 |
|
* (as determined by the Comparator, or by the keys' natural |
1698 |
|
* ordering if no Comparator). |
1723 |
|
// Reset transients |
1724 |
|
initialize(); |
1725 |
|
|
1726 |
< |
/* |
1726 |
> |
/* |
1727 |
|
* This is nearly identical to buildFromSorted, but is |
1728 |
|
* distinct because readObject calls can't be nicely adapted |
1729 |
|
* as the kind of iterator needed by buildFromSorted. (They |
1734 |
|
HeadIndex<K,V> h = head; |
1735 |
|
Node<K,V> basepred = h.node; |
1736 |
|
ArrayList<Index<K,V>> preds = new ArrayList<Index<K,V>>(); |
1737 |
< |
for (int i = 0; i <= h.level; ++i) |
1737 |
> |
for (int i = 0; i <= h.level; ++i) |
1738 |
|
preds.add(null); |
1739 |
|
Index<K,V> q = h; |
1740 |
|
for (int i = h.level; i > 0; --i) { |
1747 |
|
if (k == null) |
1748 |
|
break; |
1749 |
|
Object v = s.readObject(); |
1750 |
< |
if (v == null) |
1750 |
> |
if (v == null) |
1751 |
|
throw new NullPointerException(); |
1752 |
|
K key = (K) k; |
1753 |
|
V val = (V) v; |
1760 |
|
Index<K,V> idx = null; |
1761 |
|
for (int i = 1; i <= j; ++i) { |
1762 |
|
idx = new Index<K,V>(z, idx, null); |
1763 |
< |
if (i > h.level) |
1763 |
> |
if (i > h.level) |
1764 |
|
h = new HeadIndex<K,V>(h.node, h, idx, i); |
1765 |
|
|
1766 |
|
if (i < preds.size()) { |
1792 |
|
|
1793 |
|
/** |
1794 |
|
* Returns the value to which this map maps the specified key. Returns |
1795 |
< |
* <tt>null</tt> if the map contains no mapping for this key. |
1795 |
> |
* <tt>null</tt> if the map contains no mapping for this key. |
1796 |
|
* |
1797 |
|
* @param key key whose associated value is to be returned. |
1798 |
|
* @return the value to which this map maps the specified key, or |
1814 |
|
* @param value value to be associated with the specified key. |
1815 |
|
* |
1816 |
|
* @return previous value associated with specified key, or <tt>null</tt> |
1817 |
< |
* if there was no mapping for key. |
1817 |
> |
* if there was no mapping for key. |
1818 |
|
* @throws ClassCastException if the key cannot be compared with the keys |
1819 |
|
* currently in the map. |
1820 |
|
* @throws NullPointerException if the key or value are <tt>null</tt>. |
1821 |
|
*/ |
1822 |
|
public V put(K key, V value) { |
1823 |
< |
if (value == null) |
1823 |
> |
if (value == null) |
1824 |
|
throw new NullPointerException(); |
1825 |
|
return doPut(key, value, false); |
1826 |
|
} |
1830 |
|
* |
1831 |
|
* @param key key for which mapping should be removed |
1832 |
|
* @return previous value associated with specified key, or <tt>null</tt> |
1833 |
< |
* if there was no mapping for key. |
1833 |
> |
* if there was no mapping for key. |
1834 |
|
* |
1835 |
|
* @throws ClassCastException if the key cannot be compared with the keys |
1836 |
|
* currently in the map. |
1847 |
|
* |
1848 |
|
* @param value value whose presence in this Map is to be tested. |
1849 |
|
* @return <tt>true</tt> if a mapping to <tt>value</tt> exists; |
1850 |
< |
* <tt>false</tt> otherwise. |
1850 |
> |
* <tt>false</tt> otherwise. |
1851 |
|
* @throws NullPointerException if the value is <tt>null</tt>. |
1852 |
< |
*/ |
1852 |
> |
*/ |
1853 |
|
public boolean containsValue(Object value) { |
1854 |
< |
if (value == null) |
1854 |
> |
if (value == null) |
1855 |
|
throw new NullPointerException(); |
1856 |
|
for (Node<K,V> n = findFirst(); n != null; n = n.next) { |
1857 |
|
V v = n.getValidValue(); |
2056 |
|
* @return <tt>true</tt> if the specified object is equal to this map. |
2057 |
|
*/ |
2058 |
|
public boolean equals(Object o) { |
2059 |
< |
if (o == this) |
2060 |
< |
return true; |
2061 |
< |
if (!(o instanceof Map)) |
2062 |
< |
return false; |
2063 |
< |
Map<K,V> t = (Map<K,V>) o; |
2059 |
> |
if (o == this) |
2060 |
> |
return true; |
2061 |
> |
if (!(o instanceof Map)) |
2062 |
> |
return false; |
2063 |
> |
Map<K,V> t = (Map<K,V>) o; |
2064 |
|
try { |
2065 |
< |
return (containsAllMappings(this, t) && |
2065 |
> |
return (containsAllMappings(this, t) && |
2066 |
|
containsAllMappings(t, this)); |
2067 |
< |
} catch(ClassCastException unused) { |
2067 |
> |
} catch (ClassCastException unused) { |
2068 |
|
return false; |
2069 |
< |
} catch(NullPointerException unused) { |
2069 |
> |
} catch (NullPointerException unused) { |
2070 |
|
return false; |
2071 |
|
} |
2072 |
|
} |
2080 |
|
Entry<K,V> e = it.next(); |
2081 |
|
Object k = e.getKey(); |
2082 |
|
Object v = e.getValue(); |
2083 |
< |
if (k == null || v == null || !v.equals(a.get(k))) |
2083 |
> |
if (k == null || v == null || !v.equals(a.get(k))) |
2084 |
|
return false; |
2085 |
|
} |
2086 |
|
return true; |
2093 |
|
* with a value, associate it with the given value. |
2094 |
|
* This is equivalent to |
2095 |
|
* <pre> |
2096 |
< |
* if (!map.containsKey(key)) |
2096 |
> |
* if (!map.containsKey(key)) |
2097 |
|
* return map.put(key, value); |
2098 |
|
* else |
2099 |
|
* return map.get(key); |
2102 |
|
* @param key key with which the specified value is to be associated. |
2103 |
|
* @param value value to be associated with the specified key. |
2104 |
|
* @return previous value associated with specified key, or <tt>null</tt> |
2105 |
< |
* if there was no mapping for key. |
2105 |
> |
* if there was no mapping for key. |
2106 |
|
* |
2107 |
|
* @throws ClassCastException if the key cannot be compared with the keys |
2108 |
|
* currently in the map. |
2109 |
|
* @throws NullPointerException if the key or value are <tt>null</tt>. |
2110 |
|
*/ |
2111 |
|
public V putIfAbsent(K key, V value) { |
2112 |
< |
if (value == null) |
2112 |
> |
if (value == null) |
2113 |
|
throw new NullPointerException(); |
2114 |
|
return doPut(key, value, true); |
2115 |
|
} |
2117 |
|
/** |
2118 |
|
* Remove entry for key only if currently mapped to given value. |
2119 |
|
* Acts as |
2120 |
< |
* <pre> |
2120 |
> |
* <pre> |
2121 |
|
* if ((map.containsKey(key) && map.get(key).equals(value)) { |
2122 |
|
* map.remove(key); |
2123 |
|
* return true; |
2132 |
|
* @throws NullPointerException if the key or value are <tt>null</tt>. |
2133 |
|
*/ |
2134 |
|
public boolean remove(Object key, Object value) { |
2135 |
< |
if (value == null) |
2135 |
> |
if (value == null) |
2136 |
|
throw new NullPointerException(); |
2137 |
|
return doRemove(key, value) != null; |
2138 |
|
} |
2140 |
|
/** |
2141 |
|
* Replace entry for key only if currently mapped to given value. |
2142 |
|
* Acts as |
2143 |
< |
* <pre> |
2143 |
> |
* <pre> |
2144 |
|
* if ((map.containsKey(key) && map.get(key).equals(oldValue)) { |
2145 |
|
* map.put(key, newValue); |
2146 |
|
* return true; |
2157 |
|
* <tt>null</tt>. |
2158 |
|
*/ |
2159 |
|
public boolean replace(K key, V oldValue, V newValue) { |
2160 |
< |
if (oldValue == null || newValue == null) |
2160 |
> |
if (oldValue == null || newValue == null) |
2161 |
|
throw new NullPointerException(); |
2162 |
|
Comparable<K> k = comparable(key); |
2163 |
|
for (;;) { |
2177 |
|
/** |
2178 |
|
* Replace entry for key only if currently mapped to some value. |
2179 |
|
* Acts as |
2180 |
< |
* <pre> |
2180 |
> |
* <pre> |
2181 |
|
* if ((map.containsKey(key)) { |
2182 |
|
* return map.put(key, value); |
2183 |
|
* } else return null; |
2186 |
|
* @param key key with which the specified value is associated. |
2187 |
|
* @param value value to be associated with the specified key. |
2188 |
|
* @return previous value associated with specified key, or <tt>null</tt> |
2189 |
< |
* if there was no mapping for key. |
2189 |
> |
* if there was no mapping for key. |
2190 |
|
* @throws ClassCastException if the key cannot be compared with the keys |
2191 |
|
* currently in the map. |
2192 |
|
* @throws NullPointerException if the key or value are <tt>null</tt>. |
2193 |
|
*/ |
2194 |
|
public V replace(K key, V value) { |
2195 |
< |
if (value == null) |
2195 |
> |
if (value == null) |
2196 |
|
throw new NullPointerException(); |
2197 |
|
Comparable<K> k = comparable(key); |
2198 |
|
for (;;) { |
2224 |
|
* @return the first (lowest) key currently in this map. |
2225 |
|
* @throws NoSuchElementException Map is empty. |
2226 |
|
*/ |
2227 |
< |
public K firstKey() { |
2227 |
> |
public K firstKey() { |
2228 |
|
Node<K,V> n = findFirst(); |
2229 |
|
if (n == null) |
2230 |
|
throw new NoSuchElementException(); |
2318 |
|
* greater than or equal to the given key, or <tt>null</tt> if |
2319 |
|
* there is no such entry. The returned entry does <em>not</em> |
2320 |
|
* support the <tt>Entry.setValue</tt> method. |
2321 |
< |
* |
2321 |
> |
* |
2322 |
|
* @param key the key. |
2323 |
|
* @return an Entry associated with ceiling of given key, or |
2324 |
|
* <tt>null</tt> if there is no such Entry. |
2333 |
|
/** |
2334 |
|
* Returns least key greater than or equal to the given key, or |
2335 |
|
* <tt>null</tt> if there is no such key. |
2336 |
< |
* |
2336 |
> |
* |
2337 |
|
* @param key the key. |
2338 |
|
* @return the ceiling key, or <tt>null</tt> |
2339 |
|
* if there is no such key. |
2351 |
|
* key strictly less than the given key, or <tt>null</tt> if there is no |
2352 |
|
* such entry. The returned entry does <em>not</em> support |
2353 |
|
* the <tt>Entry.setValue</tt> method. |
2354 |
< |
* |
2354 |
> |
* |
2355 |
|
* @param key the key. |
2356 |
|
* @return an Entry with greatest key less than the given |
2357 |
|
* key, or <tt>null</tt> if there is no such Entry. |
2366 |
|
/** |
2367 |
|
* Returns the greatest key strictly less than the given key, or |
2368 |
|
* <tt>null</tt> if there is no such key. |
2369 |
< |
* |
2369 |
> |
* |
2370 |
|
* @param key the key. |
2371 |
|
* @return the greatest key less than the given |
2372 |
|
* key, or <tt>null</tt> if there is no such key. |
2384 |
|
* less than or equal to the given key, or <tt>null</tt> if there |
2385 |
|
* is no such entry. The returned entry does <em>not</em> support |
2386 |
|
* the <tt>Entry.setValue</tt> method. |
2387 |
< |
* |
2387 |
> |
* |
2388 |
|
* @param key the key. |
2389 |
|
* @return an Entry associated with floor of given key, or <tt>null</tt> |
2390 |
|
* if there is no such Entry. |
2400 |
|
* Returns the greatest key |
2401 |
|
* less than or equal to the given key, or <tt>null</tt> if there |
2402 |
|
* is no such key. |
2403 |
< |
* |
2403 |
> |
* |
2404 |
|
* @param key the key. |
2405 |
|
* @return the floor of given key, or <tt>null</tt> if there is no |
2406 |
|
* such key. |
2418 |
|
* strictly greater than the given key, or <tt>null</tt> if there |
2419 |
|
* is no such entry. The returned entry does <em>not</em> support |
2420 |
|
* the <tt>Entry.setValue</tt> method. |
2421 |
< |
* |
2421 |
> |
* |
2422 |
|
* @param key the key. |
2423 |
|
* @return an Entry with least key greater than the given key, or |
2424 |
|
* <tt>null</tt> if there is no such Entry. |
2433 |
|
/** |
2434 |
|
* Returns the least key strictly greater than the given key, or |
2435 |
|
* <tt>null</tt> if there is no such key. |
2436 |
< |
* |
2436 |
> |
* |
2437 |
|
* @param key the key. |
2438 |
|
* @return the least key greater than the given key, or |
2439 |
|
* <tt>null</tt> if there is no such key. |
2451 |
|
* key in this map, or <tt>null</tt> if the map is empty. |
2452 |
|
* The returned entry does <em>not</em> support |
2453 |
|
* the <tt>Entry.setValue</tt> method. |
2454 |
< |
* |
2455 |
< |
* @return an Entry with least key, or <tt>null</tt> |
2454 |
> |
* |
2455 |
> |
* @return an Entry with least key, or <tt>null</tt> |
2456 |
|
* if the map is empty. |
2457 |
|
*/ |
2458 |
|
public Map.Entry<K,V> firstEntry() { |
2459 |
|
for (;;) { |
2460 |
|
Node<K,V> n = findFirst(); |
2461 |
< |
if (n == null) |
2461 |
> |
if (n == null) |
2462 |
|
return null; |
2463 |
|
SnapshotEntry<K,V> e = n.createSnapshot(); |
2464 |
|
if (e != null) |
2471 |
|
* key in this map, or <tt>null</tt> if the map is empty. |
2472 |
|
* The returned entry does <em>not</em> support |
2473 |
|
* the <tt>Entry.setValue</tt> method. |
2474 |
< |
* |
2474 |
> |
* |
2475 |
|
* @return an Entry with greatest key, or <tt>null</tt> |
2476 |
|
* if the map is empty. |
2477 |
|
*/ |
2478 |
|
public Map.Entry<K,V> lastEntry() { |
2479 |
|
for (;;) { |
2480 |
|
Node<K,V> n = findLast(); |
2481 |
< |
if (n == null) |
2481 |
> |
if (n == null) |
2482 |
|
return null; |
2483 |
|
SnapshotEntry<K,V> e = n.createSnapshot(); |
2484 |
|
if (e != null) |
2491 |
|
* the least key in this map, or <tt>null</tt> if the map is empty. |
2492 |
|
* The returned entry does <em>not</em> support |
2493 |
|
* the <tt>Entry.setValue</tt> method. |
2494 |
< |
* |
2494 |
> |
* |
2495 |
|
* @return the removed first entry of this map, or <tt>null</tt> |
2496 |
|
* if the map is empty. |
2497 |
|
*/ |
2504 |
|
* the greatest key in this map, or <tt>null</tt> if the map is empty. |
2505 |
|
* The returned entry does <em>not</em> support |
2506 |
|
* the <tt>Entry.setValue</tt> method. |
2507 |
< |
* |
2507 |
> |
* |
2508 |
|
* @return the removed last entry of this map, or <tt>null</tt> |
2509 |
|
* if the map is empty. |
2510 |
|
*/ |
2517 |
|
|
2518 |
|
/** |
2519 |
|
* Base of ten kinds of iterator classes: |
2520 |
< |
* ascending: {map, submap} X {key, value, entry} |
2521 |
< |
* descending: {map, submap} X {key, entry} |
2520 |
> |
* ascending: {map, submap} X {key, value, entry} |
2521 |
> |
* descending: {map, submap} X {key, entry} |
2522 |
|
*/ |
2523 |
|
abstract class Iter { |
2524 |
|
/** the last node returned by next() */ |
2525 |
|
Node<K,V> last; |
2526 |
|
/** the next node to return from next(); */ |
2527 |
|
Node<K,V> next; |
2528 |
< |
/** Cache of next value field to maintain weak consistency */ |
2529 |
< |
Object nextValue; |
2528 |
> |
/** Cache of next value field to maintain weak consistency */ |
2529 |
> |
Object nextValue; |
2530 |
|
|
2531 |
|
Iter() {} |
2532 |
|
|
2533 |
< |
public final boolean hasNext() { |
2534 |
< |
return next != null; |
2533 |
> |
public final boolean hasNext() { |
2534 |
> |
return next != null; |
2535 |
|
} |
2536 |
|
|
2537 |
|
/** initialize ascending iterator for entire range */ |
2538 |
|
final void initAscending() { |
2539 |
|
for (;;) { |
2540 |
< |
next = findFirst(); |
2540 |
> |
next = findFirst(); |
2541 |
|
if (next == null) |
2542 |
|
break; |
2543 |
|
nextValue = next.value; |
2546 |
|
} |
2547 |
|
} |
2548 |
|
|
2549 |
< |
/** |
2549 |
> |
/** |
2550 |
|
* initialize ascending iterator starting at given least key, |
2551 |
|
* or first node if least is <tt>null</tt>, but not greater or |
2552 |
|
* equal to fence, or end if fence is <tt>null</tt>. |
2553 |
|
*/ |
2554 |
< |
final void initAscending(K least, K fence) { |
2554 |
> |
final void initAscending(K least, K fence) { |
2555 |
|
for (;;) { |
2556 |
< |
next = findCeiling(least); |
2556 |
> |
next = findCeiling(least); |
2557 |
|
if (next == null) |
2558 |
|
break; |
2559 |
|
nextValue = next.value; |
2571 |
|
if ((last = next) == null) |
2572 |
|
throw new NoSuchElementException(); |
2573 |
|
for (;;) { |
2574 |
< |
next = next.next; |
2574 |
> |
next = next.next; |
2575 |
|
if (next == null) |
2576 |
|
break; |
2577 |
|
nextValue = next.value; |
2587 |
|
if ((last = next) == null) |
2588 |
|
throw new NoSuchElementException(); |
2589 |
|
for (;;) { |
2590 |
< |
next = next.next; |
2590 |
> |
next = next.next; |
2591 |
|
if (next == null) |
2592 |
|
break; |
2593 |
|
nextValue = next.value; |
2604 |
|
/** initialize descending iterator for entire range */ |
2605 |
|
final void initDescending() { |
2606 |
|
for (;;) { |
2607 |
< |
next = findLast(); |
2607 |
> |
next = findLast(); |
2608 |
|
if (next == null) |
2609 |
|
break; |
2610 |
|
nextValue = next.value; |
2613 |
|
} |
2614 |
|
} |
2615 |
|
|
2616 |
< |
/** |
2616 |
> |
/** |
2617 |
|
* initialize descending iterator starting at key less |
2618 |
|
* than or equal to given fence key, or |
2619 |
|
* last node if fence is <tt>null</tt>, but not less than |
2620 |
|
* least, or beginning if lest is <tt>null</tt>. |
2621 |
|
*/ |
2622 |
< |
final void initDescending(K least, K fence) { |
2622 |
> |
final void initDescending(K least, K fence) { |
2623 |
|
for (;;) { |
2624 |
< |
next = findLower(fence); |
2624 |
> |
next = findLower(fence); |
2625 |
|
if (next == null) |
2626 |
|
break; |
2627 |
|
nextValue = next.value; |
2641 |
|
throw new NoSuchElementException(); |
2642 |
|
K k = last.key; |
2643 |
|
for (;;) { |
2644 |
< |
next = findNear(k, LT); |
2644 |
> |
next = findNear(k, LT); |
2645 |
|
if (next == null) |
2646 |
|
break; |
2647 |
|
nextValue = next.value; |
2658 |
|
throw new NoSuchElementException(); |
2659 |
|
K k = last.key; |
2660 |
|
for (;;) { |
2661 |
< |
next = findNear(k, LT); |
2661 |
> |
next = findNear(k, LT); |
2662 |
|
if (next == null) |
2663 |
|
break; |
2664 |
|
nextValue = next.value; |
2687 |
|
ValueIterator() { |
2688 |
|
initAscending(); |
2689 |
|
} |
2690 |
< |
public V next() { |
2690 |
> |
public V next() { |
2691 |
|
Object v = nextValue; |
2692 |
|
ascend(); |
2693 |
|
return (V)v; |
2698 |
|
KeyIterator() { |
2699 |
|
initAscending(); |
2700 |
|
} |
2701 |
< |
public K next() { |
2701 |
> |
public K next() { |
2702 |
|
Node<K,V> n = next; |
2703 |
|
ascend(); |
2704 |
|
return n.key; |
2712 |
|
this.fence = fence; |
2713 |
|
} |
2714 |
|
|
2715 |
< |
public V next() { |
2715 |
> |
public V next() { |
2716 |
|
Object v = nextValue; |
2717 |
|
ascend(fence); |
2718 |
|
return (V)v; |
2726 |
|
this.fence = fence; |
2727 |
|
} |
2728 |
|
|
2729 |
< |
public K next() { |
2729 |
> |
public K next() { |
2730 |
|
Node<K,V> n = next; |
2731 |
|
ascend(fence); |
2732 |
|
return n.key; |
2737 |
|
DescendingKeyIterator() { |
2738 |
|
initDescending(); |
2739 |
|
} |
2740 |
< |
public K next() { |
2740 |
> |
public K next() { |
2741 |
|
Node<K,V> n = next; |
2742 |
|
descend(); |
2743 |
|
return n.key; |
2751 |
|
this.least = least; |
2752 |
|
} |
2753 |
|
|
2754 |
< |
public K next() { |
2754 |
> |
public K next() { |
2755 |
|
Node<K,V> n = next; |
2756 |
|
descend(least); |
2757 |
|
return n.key; |
2767 |
|
/** Cache of last value returned */ |
2768 |
|
Object lastValue; |
2769 |
|
|
2770 |
< |
EntryIter() { |
2770 |
> |
EntryIter() { |
2771 |
|
} |
2772 |
|
|
2773 |
|
public K getKey() { |
2781 |
|
Object v = lastValue; |
2782 |
|
if (last == null || v == null) |
2783 |
|
throw new IllegalStateException(); |
2784 |
< |
return (V)v; |
2784 |
> |
return (V)v; |
2785 |
|
} |
2786 |
|
|
2787 |
|
public V setValue(V value) { |
2810 |
|
// If not acting as entry, just use default. |
2811 |
|
if (last == null) |
2812 |
|
return super.toString(); |
2813 |
< |
return getKey() + "=" + getValue(); |
2813 |
> |
return getKey() + "=" + getValue(); |
2814 |
|
} |
2815 |
|
} |
2816 |
|
|
2817 |
< |
final class EntryIterator extends EntryIter |
2817 |
> |
final class EntryIterator extends EntryIter |
2818 |
|
implements Iterator<Map.Entry<K,V>> { |
2819 |
< |
EntryIterator() { |
2820 |
< |
initAscending(); |
2819 |
> |
EntryIterator() { |
2820 |
> |
initAscending(); |
2821 |
|
} |
2822 |
< |
public Map.Entry<K,V> next() { |
2822 |
> |
public Map.Entry<K,V> next() { |
2823 |
|
lastValue = nextValue; |
2824 |
|
ascend(); |
2825 |
|
return this; |
2826 |
|
} |
2827 |
|
} |
2828 |
|
|
2829 |
< |
final class SubMapEntryIterator extends EntryIter |
2829 |
> |
final class SubMapEntryIterator extends EntryIter |
2830 |
|
implements Iterator<Map.Entry<K,V>> { |
2831 |
|
final K fence; |
2832 |
|
SubMapEntryIterator(K least, K fence) { |
2834 |
|
this.fence = fence; |
2835 |
|
} |
2836 |
|
|
2837 |
< |
public Map.Entry<K,V> next() { |
2837 |
> |
public Map.Entry<K,V> next() { |
2838 |
|
lastValue = nextValue; |
2839 |
|
ascend(fence); |
2840 |
|
return this; |
2841 |
|
} |
2842 |
|
} |
2843 |
|
|
2844 |
< |
final class DescendingEntryIterator extends EntryIter |
2844 |
> |
final class DescendingEntryIterator extends EntryIter |
2845 |
|
implements Iterator<Map.Entry<K,V>> { |
2846 |
< |
DescendingEntryIterator() { |
2847 |
< |
initDescending(); |
2846 |
> |
DescendingEntryIterator() { |
2847 |
> |
initDescending(); |
2848 |
|
} |
2849 |
< |
public Map.Entry<K,V> next() { |
2849 |
> |
public Map.Entry<K,V> next() { |
2850 |
|
lastValue = nextValue; |
2851 |
|
descend(); |
2852 |
|
return this; |
2853 |
|
} |
2854 |
|
} |
2855 |
|
|
2856 |
< |
final class DescendingSubMapEntryIterator extends EntryIter |
2856 |
> |
final class DescendingSubMapEntryIterator extends EntryIter |
2857 |
|
implements Iterator<Map.Entry<K,V>> { |
2858 |
|
final K least; |
2859 |
|
DescendingSubMapEntryIterator(K least, K fence) { |
2861 |
|
this.least = least; |
2862 |
|
} |
2863 |
|
|
2864 |
< |
public Map.Entry<K,V> next() { |
2864 |
> |
public Map.Entry<K,V> next() { |
2865 |
|
lastValue = nextValue; |
2866 |
|
descend(least); |
2867 |
|
return this; |
2985 |
|
if (!(o instanceof Map.Entry)) |
2986 |
|
return false; |
2987 |
|
Map.Entry<K,V> e = (Map.Entry<K,V>)o; |
2988 |
< |
return ConcurrentSkipListMap.this.remove(e.getKey(), |
2988 |
> |
return ConcurrentSkipListMap.this.remove(e.getKey(), |
2989 |
|
e.getValue()); |
2990 |
|
} |
2991 |
|
public boolean isEmpty() { |
3000 |
|
|
3001 |
|
public Object[] toArray() { |
3002 |
|
Collection<Map.Entry<K,V>> c = new ArrayList<Map.Entry<K,V>>(); |
3003 |
< |
for (Map.Entry e : this) |
3003 |
> |
for (Map.Entry e : this) |
3004 |
|
c.add(new SnapshotEntry(e.getKey(), e.getValue())); |
3005 |
|
return c.toArray(); |
3006 |
|
} |
3007 |
|
public <T> T[] toArray(T[] a) { |
3008 |
|
Collection<Map.Entry<K,V>> c = new ArrayList<Map.Entry<K,V>>(); |
3009 |
< |
for (Map.Entry e : this) |
3009 |
> |
for (Map.Entry e : this) |
3010 |
|
c.add(new SnapshotEntry(e.getKey(), e.getValue())); |
3011 |
|
return c.toArray(a); |
3012 |
|
} |
3036 |
|
/** Underlying map */ |
3037 |
|
private final ConcurrentSkipListMap<K,V> m; |
3038 |
|
/** lower bound key, or null if from start */ |
3039 |
< |
private final K least; |
3039 |
> |
private final K least; |
3040 |
|
/** upper fence key, or null if to end */ |
3041 |
< |
private final K fence; |
3041 |
> |
private final K fence; |
3042 |
|
// Lazily initialized view holders |
3043 |
|
private transient Set<K> keySetView; |
3044 |
|
private transient Set<Map.Entry<K,V>> entrySetView; |
3047 |
|
private transient Set<Map.Entry<K,V>> descendingEntrySetView; |
3048 |
|
|
3049 |
|
/** |
3050 |
< |
* Creates a new submap. |
3050 |
> |
* Creates a new submap. |
3051 |
|
* @param least inclusive least value, or <tt>null</tt> if from start |
3052 |
|
* @param fence exclusive upper bound or <tt>null</tt> if to end |
3053 |
|
* @throws IllegalArgumentException if least and fence nonnull |
3054 |
|
* and least greater than fence |
3055 |
|
*/ |
3056 |
< |
ConcurrentSkipListSubMap(ConcurrentSkipListMap<K,V> map, |
3056 |
> |
ConcurrentSkipListSubMap(ConcurrentSkipListMap<K,V> map, |
3057 |
|
K least, K fence) { |
3058 |
< |
if (least != null && |
3059 |
< |
fence != null && |
3058 |
> |
if (least != null && |
3059 |
> |
fence != null && |
3060 |
|
map.compare(least, fence) > 0) |
3061 |
|
throw new IllegalArgumentException("inconsistent range"); |
3062 |
|
this.m = map; |
3083 |
|
} |
3084 |
|
|
3085 |
|
boolean isBeforeEnd(ConcurrentSkipListMap.Node<K,V> n) { |
3086 |
< |
return (n != null && |
3087 |
< |
(fence == null || |
3086 |
> |
return (n != null && |
3087 |
> |
(fence == null || |
3088 |
|
n.key == null || // pass by markers and headers |
3089 |
|
m.compare(fence, n.key) > 0)); |
3090 |
|
} |
3143 |
|
|
3144 |
|
public int size() { |
3145 |
|
long count = 0; |
3146 |
< |
for (ConcurrentSkipListMap.Node<K,V> n = firstNode(); |
3147 |
< |
isBeforeEnd(n); |
3146 |
> |
for (ConcurrentSkipListMap.Node<K,V> n = firstNode(); |
3147 |
> |
isBeforeEnd(n); |
3148 |
|
n = n.next) { |
3149 |
|
if (n.getValidValue() != null) |
3150 |
|
++count; |
3157 |
|
} |
3158 |
|
|
3159 |
|
public boolean containsValue(Object value) { |
3160 |
< |
if (value == null) |
3160 |
> |
if (value == null) |
3161 |
|
throw new NullPointerException(); |
3162 |
< |
for (ConcurrentSkipListMap.Node<K,V> n = firstNode(); |
3163 |
< |
isBeforeEnd(n); |
3162 |
> |
for (ConcurrentSkipListMap.Node<K,V> n = firstNode(); |
3163 |
> |
isBeforeEnd(n); |
3164 |
|
n = n.next) { |
3165 |
|
V v = n.getValidValue(); |
3166 |
|
if (v != null && value.equals(v)) |
3170 |
|
} |
3171 |
|
|
3172 |
|
public void clear() { |
3173 |
< |
for (ConcurrentSkipListMap.Node<K,V> n = firstNode(); |
3174 |
< |
isBeforeEnd(n); |
3173 |
> |
for (ConcurrentSkipListMap.Node<K,V> n = firstNode(); |
3174 |
> |
isBeforeEnd(n); |
3175 |
|
n = n.next) { |
3176 |
|
if (n.getValidValue() != null) |
3177 |
|
m.remove(n.key); |
3280 |
|
m.getNear(key, m.LT|m.EQ, least, fence, true); |
3281 |
|
} |
3282 |
|
|
3283 |
< |
|
3283 |
> |
|
3284 |
|
public Map.Entry<K,V> higherEntry(K key) { |
3285 |
|
return (SnapshotEntry<K,V>) |
3286 |
|
m.getNear(key, m.GT, least, fence, false); |
3294 |
|
public Map.Entry<K,V> firstEntry() { |
3295 |
|
for (;;) { |
3296 |
|
ConcurrentSkipListMap.Node<K,V> n = firstNode(); |
3297 |
< |
if (!isBeforeEnd(n)) |
3297 |
> |
if (!isBeforeEnd(n)) |
3298 |
|
return null; |
3299 |
|
Map.Entry<K,V> e = n.createSnapshot(); |
3300 |
|
if (e != null) |
3436 |
|
} |
3437 |
|
public Object[] toArray() { |
3438 |
|
Collection<Map.Entry<K,V>> c = new ArrayList<Map.Entry<K,V>>(); |
3439 |
< |
for (Map.Entry e : this) |
3439 |
> |
for (Map.Entry e : this) |
3440 |
|
c.add(new SnapshotEntry(e.getKey(), e.getValue())); |
3441 |
|
return c.toArray(); |
3442 |
|
} |
3443 |
|
public <T> T[] toArray(T[] a) { |
3444 |
|
Collection<Map.Entry<K,V>> c = new ArrayList<Map.Entry<K,V>>(); |
3445 |
< |
for (Map.Entry e : this) |
3445 |
> |
for (Map.Entry e : this) |
3446 |
|
c.add(new SnapshotEntry(e.getKey(), e.getValue())); |
3447 |
|
return c.toArray(a); |
3448 |
|
} |