29 |
|
* ConcurrentModificationException}, and may proceed concurrently with |
30 |
|
* other operations. |
31 |
|
* |
32 |
< |
* <p> All <tt>Map.Entry</tt> pairs returned by methods in this class |
32 |
> |
* <p>All <tt>Map.Entry</tt> pairs returned by methods in this class |
33 |
|
* and its views represent snapshots of mappings at the time they were |
34 |
|
* produced. They do <em>not</em> support the <tt>Entry.setValue</tt> |
35 |
|
* method. (Note however that it is possible to change mappings in the |
39 |
|
* <p>Beware that, unlike in most collections, the <tt>size</tt> |
40 |
|
* method is <em>not</em> a constant-time operation. Because of the |
41 |
|
* asynchronous nature of these maps, determining the current number |
42 |
< |
* of elements requires a traversal of the elements. |
42 |
> |
* of elements requires a traversal of the elements. Additionally, |
43 |
> |
* the bulk operations <tt>putAll</tt>, <tt>equals</tt>, and |
44 |
> |
* <tt>clear</tt> are <em>not</em> guaranteed to be performed |
45 |
> |
* atomically. For example, an iterator operating concurrently with a |
46 |
> |
* <tt>putAll</tt> operation might view only some of the added |
47 |
> |
* elements. |
48 |
|
* |
49 |
|
* <p>This class and its views and iterators implement all of the |
50 |
|
* <em>optional</em> methods of the {@link Map} and {@link Iterator} |
73 |
|
* possible list with 2 levels of index: |
74 |
|
* |
75 |
|
* Head nodes Index nodes |
76 |
< |
* +-+ right +-+ +-+ |
76 |
> |
* +-+ right +-+ +-+ |
77 |
|
* |2|---------------->| |--------------------->| |->null |
78 |
|
* +-+ +-+ +-+ |
79 |
|
* | down | | |
81 |
|
* +-+ +-+ +-+ +-+ +-+ +-+ |
82 |
|
* |1|----------->| |->| |------>| |----------->| |------>| |->null |
83 |
|
* +-+ +-+ +-+ +-+ +-+ +-+ |
84 |
< |
* | | | | | | |
85 |
< |
* v Nodes v v v v v |
84 |
> |
* v | | | | | |
85 |
> |
* Nodes next v v v v v |
86 |
|
* +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ |
87 |
|
* | |->|A|->|B|->|C|->|D|->|E|->|F|->|G|->|H|->|I|->|J|->|K|->null |
88 |
|
* +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ |
89 |
|
* |
90 |
|
* The base lists use a variant of the HM linked ordered set |
91 |
< |
* algorithm (See Tim Harris, "A pragmatic implementation of |
91 |
> |
* algorithm. See Tim Harris, "A pragmatic implementation of |
92 |
|
* non-blocking linked lists" |
93 |
|
* http://www.cl.cam.ac.uk/~tlh20/publications.html and Maged |
94 |
|
* Michael "High Performance Dynamic Lock-Free Hash Tables and |
95 |
|
* List-Based Sets" |
96 |
< |
* http://www.research.ibm.com/people/m/michael/pubs.htm). The |
97 |
< |
* basic idea in these lists is to mark pointers of deleted nodes |
98 |
< |
* when deleting, and when traversing to keep track of triples |
96 |
> |
* http://www.research.ibm.com/people/m/michael/pubs.htm. The |
97 |
> |
* basic idea in these lists is to mark the "next" pointers of |
98 |
> |
* deleted nodes when deleting to avoid conflicts with concurrent |
99 |
> |
* insertions, and when traversing to keep track of triples |
100 |
|
* (predecessor, node, successor) in order to detect when and how |
101 |
|
* to unlink these deleted nodes. |
102 |
|
* |
501 |
|
volatile Index<K,V> right; |
502 |
|
|
503 |
|
/** |
504 |
< |
* Creates index node with unknown right pointer |
499 |
< |
*/ |
500 |
< |
Index(Node<K,V> node, Index<K,V> down) { |
501 |
< |
this.node = node; |
502 |
< |
this.key = node.key; |
503 |
< |
this.down = down; |
504 |
< |
} |
505 |
< |
|
506 |
< |
/** |
507 |
< |
* Creates index node with known right pointer |
504 |
> |
* Creates index node with given values |
505 |
|
*/ |
506 |
|
Index(Node<K,V> node, Index<K,V> down, Index<K,V> right) { |
507 |
|
this.node = node; |
563 |
|
*/ |
564 |
|
static final class HeadIndex<K,V> extends Index<K,V> { |
565 |
|
final int level; |
566 |
< |
HeadIndex(Node<K,V> node, Index<K,V> down, Index<K,V> right, |
570 |
< |
int level) { |
566 |
> |
HeadIndex(Node<K,V> node, Index<K,V> down, Index<K,V> right, int level) { |
567 |
|
super(node, down, right); |
568 |
|
this.level = level; |
569 |
|
} |
703 |
|
|
704 |
|
/** |
705 |
|
* Return true if given key greater than or equal to least and |
706 |
< |
* strictly less than fence. Needed mainly in submap operations. |
706 |
> |
* strictly less than fence, bypassing either test if least or |
707 |
> |
* fence oare null. Needed mainly in submap operations. |
708 |
|
*/ |
709 |
|
boolean inHalfOpenRange(K key, K least, K fence) { |
710 |
|
if (key == null) |
794 |
|
* links, and so will retry anyway. |
795 |
|
* |
796 |
|
* The traversal loops in doPut, doRemove, and findNear all |
797 |
< |
* include with the same three kinds of checks. And specialized |
798 |
< |
* versions appear in doRemoveFirstEntry, findFirst, and |
797 |
> |
* include the same three kinds of checks. And specialized |
798 |
> |
* versions appear in doRemoveFirst, doRemoveLast, findFirst, and |
799 |
|
* findLast. They can't easily share code because each uses the |
800 |
|
* reads of fields held in locals occurring in the orders they |
801 |
|
* were performed. |
890 |
|
* @return the value, or null if absent |
891 |
|
*/ |
892 |
|
private V getUsingFindNode(Comparable<K> key) { |
893 |
< |
// Loop needed here and elsewhere to protect against value |
894 |
< |
// field going null just as it is about to be returned. |
893 |
> |
/* |
894 |
> |
* Loop needed here and elsewhere in case value field goes |
895 |
> |
* null just as it is about to be returned, in which case we |
896 |
> |
* lost a race with a deletion, so must retry. |
897 |
> |
*/ |
898 |
|
for (;;) { |
899 |
|
Node<K,V> n = findNode(key); |
900 |
|
if (n == null) |
992 |
|
if (level <= max) { |
993 |
|
Index<K,V> idx = null; |
994 |
|
for (int i = 1; i <= level; ++i) |
995 |
< |
idx = new Index<K,V>(z, idx); |
995 |
> |
idx = new Index<K,V>(z, idx, null); |
996 |
|
addIndex(idx, h, level); |
997 |
|
|
998 |
|
} else { // Add a new level |
1008 |
|
Index<K,V>[] idxs = (Index<K,V>[])new Index[level+1]; |
1009 |
|
Index<K,V> idx = null; |
1010 |
|
for (int i = 1; i <= level; ++i) |
1011 |
< |
idxs[i] = idx = new Index<K,V>(z, idx); |
1011 |
> |
idxs[i] = idx = new Index<K,V>(z, idx, null); |
1012 |
|
|
1013 |
|
HeadIndex<K,V> oldh; |
1014 |
|
int k; |
1158 |
|
* Possibly reduce head level if it has no nodes. This method can |
1159 |
|
* (rarely) make mistakes, in which case levels can disappear even |
1160 |
|
* though they are about to contain index nodes. This impacts |
1161 |
< |
* performance, not correctness. To minimize mistakes and also to |
1162 |
< |
* reduce hysteresis, the level is reduced by one only if the |
1161 |
> |
* performance, not correctness. To minimize mistakes as well as |
1162 |
> |
* to reduce hysteresis, the level is reduced by one only if the |
1163 |
|
* topmost three levels look empty. Also, if the removed level |
1164 |
|
* looks non-empty after CAS, we try to change it back quick |
1165 |
|
* before anyone notices our mistake! (This trick works pretty |
1190 |
|
} |
1191 |
|
|
1192 |
|
|
1193 |
< |
/* ---------------- Positional operations -------------- */ |
1193 |
> |
/* ---------------- Finding and removing first element -------------- */ |
1194 |
|
|
1195 |
|
/** |
1196 |
< |
* Specialized version of find to get first valid node |
1196 |
> |
* Specialized variant of findNode to get first valid node |
1197 |
|
* @return first node or null if empty |
1198 |
|
*/ |
1199 |
|
Node<K,V> findFirst() { |
1200 |
|
for (;;) { |
1201 |
– |
// cheaper checks because we know head is never deleted |
1201 |
|
Node<K,V> b = head.node; |
1202 |
|
Node<K,V> n = b.next; |
1203 |
|
if (n == null) |
1209 |
|
} |
1210 |
|
|
1211 |
|
/** |
1212 |
< |
* Remove first entry; return its key or null if empty. |
1213 |
< |
* Used by ConcurrentSkipListSet |
1214 |
< |
*/ |
1215 |
< |
K removeFirstKey() { |
1217 |
< |
for (;;) { |
1218 |
< |
Node<K,V> b = head.node; |
1219 |
< |
Node<K,V> n = b.next; |
1220 |
< |
if (n == null) |
1221 |
< |
return null; |
1222 |
< |
Node<K,V> f = n.next; |
1223 |
< |
if (n != b.next) |
1224 |
< |
continue; |
1225 |
< |
Object v = n.value; |
1226 |
< |
if (v == null) { |
1227 |
< |
n.helpDelete(b, f); |
1228 |
< |
continue; |
1229 |
< |
} |
1230 |
< |
if (!n.casValue(v, null)) |
1231 |
< |
continue; |
1232 |
< |
if (!n.appendMarker(f) || !b.casNext(n, f)) |
1233 |
< |
findFirst(); // retry |
1234 |
< |
clearIndexToFirst(); |
1235 |
< |
return n.key; |
1236 |
< |
} |
1237 |
< |
} |
1238 |
< |
|
1239 |
< |
/** |
1240 |
< |
* Remove first entry; return SnapshotEntry or null if empty. |
1212 |
> |
* Remove first entry; return either its key or a snapshot. |
1213 |
> |
* @param keyOnly if true return key, else return SnapshotEntry |
1214 |
> |
* (This is a little ugly, but avoids code duplication.) |
1215 |
> |
* @return null if empty, first key if keyOnly true, else key,value entry |
1216 |
|
*/ |
1217 |
< |
private SnapshotEntry<K,V> doRemoveFirstEntry() { |
1243 |
< |
/* |
1244 |
< |
* This must be mostly duplicated from removeFirstKey because we |
1245 |
< |
* need to save the last value read before it is nulled out |
1246 |
< |
*/ |
1217 |
> |
Object doRemoveFirst(boolean keyOnly) { |
1218 |
|
for (;;) { |
1219 |
|
Node<K,V> b = head.node; |
1220 |
|
Node<K,V> n = b.next; |
1233 |
|
if (!n.appendMarker(f) || !b.casNext(n, f)) |
1234 |
|
findFirst(); // retry |
1235 |
|
clearIndexToFirst(); |
1236 |
< |
return new SnapshotEntry<K,V>(n.key, (V)v); |
1236 |
> |
K key = n.key; |
1237 |
> |
return (keyOnly)? key : new SnapshotEntry<K,V>(key, (V)v); |
1238 |
|
} |
1239 |
|
} |
1240 |
|
|
1241 |
|
/** |
1242 |
|
* Clear out index nodes associated with deleted first entry. |
1243 |
< |
* Needed by removeFirstKey and removeFirstEntry |
1243 |
> |
* Needed by doRemoveFirst |
1244 |
|
*/ |
1245 |
|
private void clearIndexToFirst() { |
1246 |
|
for (;;) { |
1258 |
|
} |
1259 |
|
} |
1260 |
|
|
1261 |
+ |
/* ---------------- Finding and removing last element -------------- */ |
1262 |
+ |
|
1263 |
|
/** |
1264 |
|
* Specialized version of find to get last valid node |
1265 |
|
* @return last node or null if empty |
1306 |
|
} |
1307 |
|
} |
1308 |
|
|
1309 |
+ |
|
1310 |
|
/** |
1311 |
< |
* Temporary helper method for two-pass implementation of |
1312 |
< |
* removeLastEntry, mostly pasted from doRemove. |
1313 |
< |
* TODO: replace with one-pass implementation |
1311 |
> |
* Specialized version of doRemove for last entry. |
1312 |
> |
* @param keyOnly if true return key, else return SnapshotEntry |
1313 |
> |
* @return null if empty, last key if keyOnly true, else key,value entry |
1314 |
|
*/ |
1315 |
< |
private Object removeIfLast(K kkey) { |
1341 |
< |
Comparable<K> key = comparable(kkey); |
1315 |
> |
Object doRemoveLast(boolean keyOnly) { |
1316 |
|
for (;;) { |
1317 |
< |
Node<K,V> b = findPredecessor(key); |
1317 |
> |
Node<K,V> b = findPredecessorOfLast(); |
1318 |
|
Node<K,V> n = b.next; |
1319 |
< |
for (;;) { |
1320 |
< |
if (n == null) |
1319 |
> |
if (n == null) { |
1320 |
> |
if (b.isBaseHeader()) // empty |
1321 |
|
return null; |
1322 |
+ |
else |
1323 |
+ |
continue; // all b's successors are deleted; retry |
1324 |
+ |
} |
1325 |
+ |
for (;;) { |
1326 |
|
Node<K,V> f = n.next; |
1327 |
|
if (n != b.next) // inconsistent read |
1328 |
|
break; |
1333 |
|
} |
1334 |
|
if (v == n || b.value == null) // b is deleted |
1335 |
|
break; |
1336 |
< |
int c = key.compareTo(n.key); |
1359 |
< |
if (c < 0) |
1360 |
< |
return null; |
1361 |
< |
if (c > 0) { |
1336 |
> |
if (f != null) { |
1337 |
|
b = n; |
1338 |
|
n = f; |
1339 |
|
continue; |
1340 |
|
} |
1366 |
– |
if (f != null) // fail if n not last |
1367 |
– |
return null; |
1341 |
|
if (!n.casValue(v, null)) |
1342 |
< |
return null; |
1342 |
> |
break; |
1343 |
> |
K key = n.key; |
1344 |
> |
Comparable<K> ck = comparable(key); |
1345 |
|
if (!n.appendMarker(f) || !b.casNext(n, f)) |
1346 |
< |
findNode(key); // Retry via findNode |
1346 |
> |
findNode(ck); // Retry via findNode |
1347 |
|
else { |
1348 |
< |
findPredecessor(key); // Clean index |
1348 |
> |
findPredecessor(ck); // Clean index |
1349 |
|
if (head.right == null) |
1350 |
|
tryReduceLevel(); |
1351 |
|
} |
1352 |
< |
return v; |
1352 |
> |
return (keyOnly)? key : new SnapshotEntry<K,V>(key, (V)v); |
1353 |
|
} |
1354 |
|
} |
1355 |
|
} |
1356 |
|
|
1357 |
|
/** |
1358 |
< |
* Remove last entry; return SnapshotEntry or null if empty. |
1358 |
> |
* Specialized variant of findPredecessor to get predecessor of |
1359 |
> |
* last valid node. Needed by doRemoveLast. It is possible that |
1360 |
> |
* all successors of returned node will have been deleted upon |
1361 |
> |
* return, in which case this method can be retried. |
1362 |
> |
* @return likely predecessor of last node. |
1363 |
|
*/ |
1364 |
< |
private SnapshotEntry<K,V> doRemoveLastEntry() { |
1364 |
> |
private Node<K,V> findPredecessorOfLast() { |
1365 |
|
for (;;) { |
1366 |
< |
Node<K,V> l = findLast(); |
1367 |
< |
if (l == null) |
1368 |
< |
return null; |
1369 |
< |
K k = l.key; |
1370 |
< |
Object v = removeIfLast(k); |
1371 |
< |
if (v != null) |
1372 |
< |
return new SnapshotEntry<K, V>(k, (V)v); |
1366 |
> |
Index<K,V> q = head; |
1367 |
> |
for (;;) { |
1368 |
> |
Index<K,V> d, r; |
1369 |
> |
if ((r = q.right) != null) { |
1370 |
> |
if (r.indexesDeletedNode()) { |
1371 |
> |
q.unlink(r); |
1372 |
> |
break; // must restart |
1373 |
> |
} |
1374 |
> |
// proceed as far across as possible without overshooting |
1375 |
> |
if (r.node.next != null) { |
1376 |
> |
q = r; |
1377 |
> |
continue; |
1378 |
> |
} |
1379 |
> |
} |
1380 |
> |
if ((d = q.down) != null) |
1381 |
> |
q = d; |
1382 |
> |
else |
1383 |
> |
return q.node; |
1384 |
> |
} |
1385 |
|
} |
1386 |
|
} |
1387 |
|
|
1397 |
– |
/** |
1398 |
– |
* Remove last entry; return key or null if empty. |
1399 |
– |
*/ |
1400 |
– |
K removeLastKey() { |
1401 |
– |
for (;;) { |
1402 |
– |
Node<K,V> l = findLast(); |
1403 |
– |
if (l == null) |
1404 |
– |
return null; |
1405 |
– |
K k = l.key; |
1406 |
– |
if (removeIfLast(k) != null) |
1407 |
– |
return k; |
1408 |
– |
} |
1409 |
– |
} |
1410 |
– |
|
1388 |
|
/* ---------------- Relational operations -------------- */ |
1389 |
|
|
1390 |
|
// Control values OR'ed as arguments to findNear |
1476 |
|
* @param m the map whose mappings are to be placed in this map. |
1477 |
|
* @throws ClassCastException if the keys in m are not Comparable, or |
1478 |
|
* are not mutually comparable. |
1479 |
< |
* @throws NullPointerException if the specified map is null. |
1479 |
> |
* @throws NullPointerException if the specified map is <tt>null</tt>. |
1480 |
|
*/ |
1481 |
|
public ConcurrentSkipListMap(Map<? extends K, ? extends V> m) { |
1482 |
|
this.comparator = null; |
1487 |
|
/** |
1488 |
|
* Constructs a new map containing the same mappings as the given |
1489 |
|
* <tt>SortedMap</tt>, sorted according to the same ordering. |
1490 |
< |
* @param m the sorted map whose mappings are to be placed in this map, |
1491 |
< |
* and whose comparator is to be used to sort this map. |
1492 |
< |
* @throws NullPointerException if the specified sorted map is null. |
1490 |
> |
* @param m the sorted map whose mappings are to be placed in this |
1491 |
> |
* map, and whose comparator is to be used to sort this map. |
1492 |
> |
* @throws NullPointerException if the specified sorted map is |
1493 |
> |
* <tt>null</tt>. |
1494 |
|
*/ |
1495 |
|
public ConcurrentSkipListMap(SortedMap<K, ? extends V> m) { |
1496 |
|
this.comparator = m.comparator(); |
1558 |
|
if (j > 0) { |
1559 |
|
Index<K,V> idx = null; |
1560 |
|
for (int i = 1; i <= j; ++i) { |
1561 |
< |
idx = new Index<K,V>(z, idx); |
1561 |
> |
idx = new Index<K,V>(z, idx, null); |
1562 |
|
if (i > h.level) |
1563 |
|
h = new HeadIndex<K,V>(h.node, h, idx, i); |
1564 |
|
|
1611 |
|
initialize(); |
1612 |
|
|
1613 |
|
/* |
1614 |
< |
* This is basically identical to buildFromSorted, but is |
1614 |
> |
* This is nearly identical to buildFromSorted, but is |
1615 |
|
* distinct because readObject calls can't be nicely adapted |
1616 |
|
* as the kind of iterator needed by buildFromSorted. (They |
1617 |
|
* can be, but doing so requires type cheats and/or creation |
1646 |
|
if (j > 0) { |
1647 |
|
Index<K,V> idx = null; |
1648 |
|
for (int i = 1; i <= j; ++i) { |
1649 |
< |
idx = new Index<K,V>(z, idx); |
1649 |
> |
idx = new Index<K,V>(z, idx, null); |
1650 |
|
if (i > h.level) |
1651 |
|
h = new HeadIndex<K,V>(h.node, h, idx, i); |
1652 |
|
|
1868 |
|
return (es != null) ? es : (entrySet = new EntrySet()); |
1869 |
|
} |
1870 |
|
|
1871 |
+ |
/* ---------------- AbstractMap Overrides -------------- */ |
1872 |
+ |
|
1873 |
+ |
/** |
1874 |
+ |
* Compares the specified object with this map for equality. |
1875 |
+ |
* Returns <tt>true</tt> if the given object is also a map and the |
1876 |
+ |
* two maps represent the same mappings. More formally, two maps |
1877 |
+ |
* <tt>t1</tt> and <tt>t2</tt> represent the same mappings if |
1878 |
+ |
* <tt>t1.keySet().equals(t2.keySet())</tt> and for every key |
1879 |
+ |
* <tt>k</tt> in <tt>t1.keySet()</tt>, <tt> (t1.get(k)==null ? |
1880 |
+ |
* t2.get(k)==null : t1.get(k).equals(t2.get(k))) </tt>. This |
1881 |
+ |
* operation may return misleading results if either map is |
1882 |
+ |
* concurrently modified during execution of this method. |
1883 |
+ |
* |
1884 |
+ |
* @param o object to be compared for equality with this map. |
1885 |
+ |
* @return <tt>true</tt> if the specified object is equal to this map. |
1886 |
+ |
*/ |
1887 |
+ |
public boolean equals(Object o) { |
1888 |
+ |
if (o == this) |
1889 |
+ |
return true; |
1890 |
+ |
if (!(o instanceof Map)) |
1891 |
+ |
return false; |
1892 |
+ |
Map<K,V> t = (Map<K,V>) o; |
1893 |
+ |
try { |
1894 |
+ |
return (containsAllMappings(this, t) && |
1895 |
+ |
containsAllMappings(t, this)); |
1896 |
+ |
} catch(ClassCastException unused) { |
1897 |
+ |
return false; |
1898 |
+ |
} catch(NullPointerException unused) { |
1899 |
+ |
return false; |
1900 |
+ |
} |
1901 |
+ |
} |
1902 |
+ |
|
1903 |
+ |
/** |
1904 |
+ |
* Helper for equals -- check for containment, avoiding nulls. |
1905 |
+ |
*/ |
1906 |
+ |
static <K,V> boolean containsAllMappings(Map<K,V> a, Map<K,V> b) { |
1907 |
+ |
Iterator<Entry<K,V>> it = b.entrySet().iterator(); |
1908 |
+ |
while (it.hasNext()) { |
1909 |
+ |
Entry<K,V> e = it.next(); |
1910 |
+ |
Object k = e.getKey(); |
1911 |
+ |
Object v = e.getValue(); |
1912 |
+ |
if (k == null || v == null || !v.equals(a.get(k))) |
1913 |
+ |
return false; |
1914 |
+ |
} |
1915 |
+ |
return true; |
1916 |
+ |
} |
1917 |
+ |
|
1918 |
|
/* ------ ConcurrentMap API methods ------ */ |
1919 |
|
|
1920 |
|
/** |
1927 |
|
* else |
1928 |
|
* return map.get(key); |
1929 |
|
* </pre> |
1930 |
< |
* Except that the action is performed atomically. |
1930 |
> |
* except that the action is performed atomically. |
1931 |
|
* @param key key with which the specified value is to be associated. |
1932 |
|
* @param value value to be associated with the specified key. |
1933 |
|
* @return previous value associated with specified key, or <tt>null</tt> |
2101 |
|
} |
2102 |
|
|
2103 |
|
/** |
2104 |
< |
* Returns a view of the portion of this map whose keys are strictly less |
2105 |
< |
* than <tt>toKey</tt>. The returned sorted map is backed by this map, so |
2106 |
< |
* changes in the returned sorted map are reflected in this map, and |
2107 |
< |
* vice-versa. |
2104 |
> |
* Returns a view of the portion of this map whose keys are |
2105 |
> |
* strictly less than <tt>toKey</tt>. The returned sorted map is |
2106 |
> |
* backed by this map, so changes in the returned sorted map are |
2107 |
> |
* reflected in this map, and vice-versa. |
2108 |
|
* @param toKey high endpoint (exclusive) of the headMap. |
2109 |
< |
* @return a view of the portion of this map whose keys are strictly |
2110 |
< |
* less than <tt>toKey</tt>. |
2109 |
> |
* @return a view of the portion of this map whose keys are |
2110 |
> |
* strictly less than <tt>toKey</tt>. |
2111 |
|
* |
2112 |
|
* @throws ClassCastException if <tt>toKey</tt> is not compatible |
2113 |
< |
* with this map's comparator (or, if the map has no comparator, |
2114 |
< |
* if <tt>toKey</tt> does not implement <tt>Comparable</tt>). |
2113 |
> |
* with this map's comparator (or, if the map has no comparator, |
2114 |
> |
* if <tt>toKey</tt> does not implement <tt>Comparable</tt>). |
2115 |
|
* @throws NullPointerException if <tt>toKey</tt> is <tt>null</tt>. |
2116 |
|
*/ |
2117 |
|
public ConcurrentNavigableMap<K,V> headMap(K toKey) { |
2126 |
|
* map is backed by this map, so changes in the returned sorted |
2127 |
|
* map are reflected in this map, and vice-versa. |
2128 |
|
* @param fromKey low endpoint (inclusive) of the tailMap. |
2129 |
< |
* @return a view of the portion of this map whose keys are greater |
2130 |
< |
* than or equal to <tt>fromKey</tt>. |
2131 |
< |
* @throws ClassCastException if <tt>fromKey</tt> is not compatible |
2132 |
< |
* with this map's comparator (or, if the map has no comparator, |
2133 |
< |
* if <tt>fromKey</tt> does not implement <tt>Comparable</tt>). |
2129 |
> |
* @return a view of the portion of this map whose keys are |
2130 |
> |
* greater than or equal to <tt>fromKey</tt>. |
2131 |
> |
* @throws ClassCastException if <tt>fromKey</tt> is not |
2132 |
> |
* compatible with this map's comparator (or, if the map has no |
2133 |
> |
* comparator, if <tt>fromKey</tt> does not implement |
2134 |
> |
* <tt>Comparable</tt>). |
2135 |
|
* @throws NullPointerException if <tt>fromKey</tt> is <tt>null</tt>. |
2136 |
|
*/ |
2137 |
|
public ConcurrentNavigableMap<K,V> tailMap(K fromKey) { |
2144 |
|
|
2145 |
|
/** |
2146 |
|
* Returns a key-value mapping associated with the least key |
2147 |
< |
* greater than or equal to the given key, or null if there is |
2148 |
< |
* no such entry. The returned entry does <em>not</em> support |
2149 |
< |
* the <tt>Entry.setValue</tt> method. |
2147 |
> |
* greater than or equal to the given key, or <tt>null</tt> if |
2148 |
> |
* there is no such entry. The returned entry does <em>not</em> |
2149 |
> |
* support the <tt>Entry.setValue</tt> method. |
2150 |
|
* |
2151 |
|
* @param key the key. |
2152 |
< |
* @return an Entry associated with ceiling of given key, or null |
2153 |
< |
* if there is no such Entry. |
2154 |
< |
* @throws ClassCastException if key cannot be compared with the keys |
2155 |
< |
* currently in the map. |
2152 |
> |
* @return an Entry associated with ceiling of given key, or |
2153 |
> |
* <tt>null</tt> if there is no such Entry. |
2154 |
> |
* @throws ClassCastException if key cannot be compared with the |
2155 |
> |
* keys currently in the map. |
2156 |
|
* @throws NullPointerException if key is <tt>null</tt>. |
2157 |
|
*/ |
2158 |
|
public Map.Entry<K,V> ceilingEntry(K key) { |
2161 |
|
|
2162 |
|
/** |
2163 |
|
* Returns a key-value mapping associated with the greatest |
2164 |
< |
* key strictly less than the given key, or null if there is no |
2164 |
> |
* key strictly less than the given key, or <tt>null</tt> if there is no |
2165 |
|
* such entry. The returned entry does <em>not</em> support |
2166 |
|
* the <tt>Entry.setValue</tt> method. |
2167 |
|
* |
2168 |
|
* @param key the key. |
2169 |
|
* @return an Entry with greatest key less than the given |
2170 |
< |
* key, or null if there is no such Entry. |
2170 |
> |
* key, or <tt>null</tt> if there is no such Entry. |
2171 |
|
* @throws ClassCastException if key cannot be compared with the keys |
2172 |
|
* currently in the map. |
2173 |
|
* @throws NullPointerException if key is <tt>null</tt>. |
2177 |
|
} |
2178 |
|
|
2179 |
|
/** |
2180 |
< |
* Returns a key-value mapping associated with the greatest |
2181 |
< |
* key less than or equal to the given key, or null if there is no |
2182 |
< |
* such entry. The returned entry does <em>not</em> support |
2180 |
> |
* Returns a key-value mapping associated with the greatest key |
2181 |
> |
* less than or equal to the given key, or <tt>null</tt> if there |
2182 |
> |
* is no such entry. The returned entry does <em>not</em> support |
2183 |
|
* the <tt>Entry.setValue</tt> method. |
2184 |
|
* |
2185 |
|
* @param key the key. |
2186 |
< |
* @return an Entry associated with floor of given key, or null |
2186 |
> |
* @return an Entry associated with floor of given key, or <tt>null</tt> |
2187 |
|
* if there is no such Entry. |
2188 |
|
* @throws ClassCastException if key cannot be compared with the keys |
2189 |
|
* currently in the map. |
2194 |
|
} |
2195 |
|
|
2196 |
|
/** |
2197 |
< |
* Returns a key-value mapping associated with the least |
2198 |
< |
* key strictly greater than the given key, or null if there is no |
2199 |
< |
* such entry. The returned entry does <em>not</em> support |
2197 |
> |
* Returns a key-value mapping associated with the least key |
2198 |
> |
* strictly greater than the given key, or <tt>null</tt> if there |
2199 |
> |
* is no such entry. The returned entry does <em>not</em> support |
2200 |
|
* the <tt>Entry.setValue</tt> method. |
2201 |
|
* |
2202 |
|
* @param key the key. |
2203 |
|
* @return an Entry with least key greater than the given key, or |
2204 |
< |
* null if there is no such Entry. |
2204 |
> |
* <tt>null</tt> if there is no such Entry. |
2205 |
|
* @throws ClassCastException if key cannot be compared with the keys |
2206 |
|
* currently in the map. |
2207 |
|
* @throws NullPointerException if key is <tt>null</tt>. |
2212 |
|
|
2213 |
|
/** |
2214 |
|
* Returns a key-value mapping associated with the least |
2215 |
< |
* key in this map, or null if the map is empty. |
2215 |
> |
* key in this map, or <tt>null</tt> if the map is empty. |
2216 |
|
* The returned entry does <em>not</em> support |
2217 |
|
* the <tt>Entry.setValue</tt> method. |
2218 |
|
* |
2219 |
< |
* @return an Entry with least key, or null |
2219 |
> |
* @return an Entry with least key, or <tt>null</tt> |
2220 |
|
* if the map is empty. |
2221 |
|
*/ |
2222 |
|
public Map.Entry<K,V> firstEntry() { |
2232 |
|
|
2233 |
|
/** |
2234 |
|
* Returns a key-value mapping associated with the greatest |
2235 |
< |
* key in this map, or null if the map is empty. |
2235 |
> |
* key in this map, or <tt>null</tt> if the map is empty. |
2236 |
|
* The returned entry does <em>not</em> support |
2237 |
|
* the <tt>Entry.setValue</tt> method. |
2238 |
|
* |
2239 |
< |
* @return an Entry with greatest key, or null |
2239 |
> |
* @return an Entry with greatest key, or <tt>null</tt> |
2240 |
|
* if the map is empty. |
2241 |
|
*/ |
2242 |
|
public Map.Entry<K,V> lastEntry() { |
2252 |
|
|
2253 |
|
/** |
2254 |
|
* Removes and returns a key-value mapping associated with |
2255 |
< |
* the least key in this map, or null if the map is empty. |
2255 |
> |
* the least key in this map, or <tt>null</tt> if the map is empty. |
2256 |
|
* The returned entry does <em>not</em> support |
2257 |
|
* the <tt>Entry.setValue</tt> method. |
2258 |
|
* |
2259 |
< |
* @return the removed first entry of this map, or null |
2259 |
> |
* @return the removed first entry of this map, or <tt>null</tt> |
2260 |
|
* if the map is empty. |
2261 |
|
*/ |
2262 |
|
public Map.Entry<K,V> pollFirstEntry() { |
2263 |
< |
return doRemoveFirstEntry(); |
2263 |
> |
return (SnapshotEntry<K,V>)doRemoveFirst(false); |
2264 |
|
} |
2265 |
|
|
2266 |
|
/** |
2267 |
|
* Removes and returns a key-value mapping associated with |
2268 |
< |
* the greatest key in this map, or null if the map is empty. |
2268 |
> |
* the greatest key in this map, or <tt>null</tt> if the map is empty. |
2269 |
|
* The returned entry does <em>not</em> support |
2270 |
|
* the <tt>Entry.setValue</tt> method. |
2271 |
|
* |
2272 |
< |
* @return the removed last entry of this map, or null |
2272 |
> |
* @return the removed last entry of this map, or <tt>null</tt> |
2273 |
|
* if the map is empty. |
2274 |
|
*/ |
2275 |
|
public Map.Entry<K,V> pollLastEntry() { |
2276 |
< |
return doRemoveLastEntry(); |
2276 |
> |
return (SnapshotEntry<K,V>)doRemoveLast(false); |
2277 |
|
} |
2278 |
|
|
2279 |
|
/* ---------------- Iterators -------------- */ |
2304 |
|
|
2305 |
|
/** |
2306 |
|
* Create a submap iterator starting at given least key, or |
2307 |
< |
* first node if least is null, but not greater or equal to |
2308 |
< |
* fence, or end if fence is null. |
2307 |
> |
* first node if least is <tt>null</tt>, but not greater or equal to |
2308 |
> |
* fence, or end if fence is <tt>null</tt>. |
2309 |
|
*/ |
2310 |
|
ConcurrentSkipListMapIterator(K least, K fence) { |
2311 |
|
for (;;) { |
2536 |
|
} |
2537 |
|
|
2538 |
|
/** |
2539 |
+ |
* Remove first entry; return key or null if empty. |
2540 |
+ |
*/ |
2541 |
+ |
K removeFirstKey() { |
2542 |
+ |
return (K)doRemoveFirst(true); |
2543 |
+ |
} |
2544 |
+ |
|
2545 |
+ |
/** |
2546 |
+ |
* Remove last entry; return key or null if empty. |
2547 |
+ |
*/ |
2548 |
+ |
K removeLastKey() { |
2549 |
+ |
return (K)doRemoveLast(true); |
2550 |
+ |
} |
2551 |
+ |
|
2552 |
+ |
/** |
2553 |
|
* Return SnapshotEntry for results of findNear ofter screening |
2554 |
|
* to ensure result is in given range. Needed by submaps. |
2555 |
|
* @param kkey the key |
2556 |
|
* @param rel the relation -- OR'ed combination of EQ, LT, GT |
2557 |
|
* @param least minimum allowed key value |
2558 |
|
* @param fence key greater than maximum allowed key value |
2559 |
< |
* @return Entry fitting relation, or null if no such |
2559 |
> |
* @return Entry fitting relation, or <tt>null</tt> if no such |
2560 |
|
*/ |
2561 |
|
SnapshotEntry<K,V> getNear(K kkey, int rel, K least, K fence) { |
2562 |
|
K key = kkey; |
2581 |
|
// Methods expanding out relational operations for submaps |
2582 |
|
|
2583 |
|
/** |
2584 |
< |
* Return ceiling, or first node if key is null |
2584 |
> |
* Return ceiling, or first node if key is <tt>null</tt> |
2585 |
|
*/ |
2586 |
|
Node<K,V> findCeiling(K key) { |
2587 |
|
return (key == null)? findFirst() : findNear(key, GT|EQ); |
2588 |
|
} |
2589 |
|
|
2590 |
|
/** |
2591 |
< |
* Return lower node, or last node if key is null |
2591 |
> |
* Return lower node, or last node if key is <tt>null</tt> |
2592 |
|
*/ |
2593 |
|
Node<K,V> findLower(K key) { |
2594 |
|
return (key == null)? findLast() : findNear(key, LT); |
2759 |
|
if (!(o instanceof Map.Entry)) |
2760 |
|
return false; |
2761 |
|
Map.Entry<K,V> e = (Map.Entry<K,V>)o; |
2762 |
< |
return ConcurrentSkipListMap.this.remove(e.getKey(), e.getValue()); |
2762 |
> |
return ConcurrentSkipListMap.this.remove(e.getKey(), |
2763 |
> |
e.getValue()); |
2764 |
|
} |
2765 |
|
public boolean isEmpty() { |
2766 |
|
return ConcurrentSkipListMap.this.isEmpty(); |
2820 |
|
|
2821 |
|
/** |
2822 |
|
* Creates a new submap. |
2823 |
< |
* @param least inclusive least value, or null if from start |
2824 |
< |
* @param fence exclusive upper bound or null if to end |
2823 |
> |
* @param least inclusive least value, or <tt>null</tt> if from start |
2824 |
> |
* @param fence exclusive upper bound or <tt>null</tt> if to end |
2825 |
|
* @throws IllegalArgumentException if least and fence nonnull |
2826 |
|
* and least greater than fence |
2827 |
|
*/ |
2828 |
|
ConcurrentSkipListSubMap(ConcurrentSkipListMap<K,V> map, |
2829 |
|
K least, K fence) { |
2830 |
< |
if (least != null && fence != null && map.compare(least, fence) > 0) |
2830 |
> |
if (least != null && |
2831 |
> |
fence != null && |
2832 |
> |
map.compare(least, fence) > 0) |
2833 |
|
throw new IllegalArgumentException("inconsistent range"); |
2834 |
|
this.m = map; |
2835 |
|
this.least = least; |
2876 |
|
|
2877 |
|
/** |
2878 |
|
* Returns least key. Needed by ConcurrentSkipListSet |
2879 |
< |
* @return least key or null if from start |
2879 |
> |
* @return least key or <tt>null</tt> if from start |
2880 |
|
*/ |
2881 |
|
K getLeast() { |
2882 |
|
return least; |
2884 |
|
|
2885 |
|
/** |
2886 |
|
* Returns fence key. Needed by ConcurrentSkipListSet |
2887 |
< |
* @return fence key or null of to end |
2887 |
> |
* @return fence key or <tt>null</tt> of to end |
2888 |
|
*/ |
2889 |
|
K getFence() { |
2890 |
|
return fence; |
2893 |
|
/** |
2894 |
|
* Non-exception throwing version of firstKey needed by |
2895 |
|
* ConcurrentSkipListSubSet |
2896 |
< |
* @return first key, or null if empty |
2896 |
> |
* @return first key, or <tt>null</tt> if empty |
2897 |
|
*/ |
2898 |
|
K lowestKey() { |
2899 |
|
ConcurrentSkipListMap.Node<K,V> n = firstNode(); |
2906 |
|
/** |
2907 |
|
* Non-exception throwing version of highestKey needed by |
2908 |
|
* ConcurrentSkipListSubSet |
2909 |
< |
* @return last key, or null if empty |
2909 |
> |
* @return last key, or <tt>null</tt> if empty |
2910 |
|
*/ |
2911 |
|
K highestKey() { |
2912 |
|
ConcurrentSkipListMap.Node<K,V> n = lastNode(); |
3121 |
|
* </pre> |
3122 |
|
* except that the action is performed atomically. |
3123 |
|
* @param key key with which the specified value is associated. |
3124 |
< |
* @param oldValue value expected to be associated with the specified key. |
3124 |
> |
* @param oldValue value expected to be associated with the |
3125 |
> |
* specified key. |
3126 |
|
* @param newValue value to be associated with the specified key. |
3127 |
|
* @return true if the value was replaced |
3128 |
|
* @throws ClassCastException if the key cannot be compared |
3294 |
|
|
3295 |
|
/** |
3296 |
|
* Returns a key-value mapping associated with the least key |
3297 |
< |
* greater than or equal to the given key, or null if there is |
3298 |
< |
* no such entry. The returned entry does <em>not</em> support |
3299 |
< |
* the <tt>Entry.setValue</tt> method. |
3297 |
> |
* greater than or equal to the given key, or <tt>null</tt> if |
3298 |
> |
* there is no such entry. The returned entry does |
3299 |
> |
* <em>not</em> support the <tt>Entry.setValue</tt> method. |
3300 |
|
* |
3301 |
|
* @param key the key. |
3302 |
< |
* @return an Entry associated with ceiling of given key, or null |
3303 |
< |
* if there is no such Entry. |
3302 |
> |
* @return an Entry associated with ceiling of given key, or |
3303 |
> |
* <tt>null</tt> if there is no such Entry. |
3304 |
|
* @throws ClassCastException if key cannot be compared with the keys |
3305 |
|
* currently in the map. |
3306 |
|
* @throws NullPointerException if key is <tt>null</tt>. |
3311 |
|
|
3312 |
|
/** |
3313 |
|
* Returns a key-value mapping associated with the greatest |
3314 |
< |
* key strictly less than the given key, or null if there is no |
3315 |
< |
* such entry. The returned entry does <em>not</em> support |
3316 |
< |
* the <tt>Entry.setValue</tt> method. |
3314 |
> |
* key strictly less than the given key, or <tt>null</tt> if |
3315 |
> |
* there is no such entry. The returned entry does |
3316 |
> |
* <em>not</em> support the <tt>Entry.setValue</tt> method. |
3317 |
|
* |
3318 |
|
* @param key the key. |
3319 |
|
* @return an Entry with greatest key less than the given |
3320 |
< |
* key, or null if there is no such Entry. |
3321 |
< |
* @throws ClassCastException if key cannot be compared with the keys |
3322 |
< |
* currently in the map. |
3320 |
> |
* key, or <tt>null</tt> if there is no such Entry. |
3321 |
> |
* @throws ClassCastException if key cannot be compared with |
3322 |
> |
* the keys currently in the map. |
3323 |
|
* @throws NullPointerException if key is <tt>null</tt>. |
3324 |
|
*/ |
3325 |
|
public Map.Entry<K,V> lowerEntry(K key) { |
3328 |
|
|
3329 |
|
/** |
3330 |
|
* Returns a key-value mapping associated with the greatest |
3331 |
< |
* key less than or equal to the given key, or null if there is no |
3332 |
< |
* such entry. The returned entry does <em>not</em> support |
3333 |
< |
* the <tt>Entry.setValue</tt> method. |
3331 |
> |
* key less than or equal to the given key, or <tt>null</tt> |
3332 |
> |
* if there is no such entry. The returned entry does |
3333 |
> |
* <em>not</em> support the <tt>Entry.setValue</tt> method. |
3334 |
|
* |
3335 |
|
* @param key the key. |
3336 |
< |
* @return an Entry associated with floor of given key, or null |
3337 |
< |
* if there is no such Entry. |
3338 |
< |
* @throws ClassCastException if key cannot be compared with the keys |
3339 |
< |
* currently in the map. |
3336 |
> |
* @return an Entry associated with floor of given key, or |
3337 |
> |
* <tt>null</tt> if there is no such Entry. |
3338 |
> |
* @throws ClassCastException if key cannot be compared with |
3339 |
> |
* the keys currently in the map. |
3340 |
|
* @throws NullPointerException if key is <tt>null</tt>. |
3341 |
|
*/ |
3342 |
|
public Map.Entry<K,V> floorEntry(K key) { |
3344 |
|
} |
3345 |
|
|
3346 |
|
/** |
3347 |
< |
* Returns a key-value mapping associated with the least |
3348 |
< |
* key strictly greater than the given key, or null if there is no |
3349 |
< |
* such entry. The returned entry does <em>not</em> support |
3350 |
< |
* the <tt>Entry.setValue</tt> method. |
3347 |
> |
* Returns a key-value mapping associated with the least key |
3348 |
> |
* strictly greater than the given key, or <tt>null</tt> if |
3349 |
> |
* there is no such entry. The returned entry does |
3350 |
> |
* <em>not</em> support the <tt>Entry.setValue</tt> method. |
3351 |
|
* |
3352 |
|
* @param key the key. |
3353 |
|
* @return an Entry with least key greater than the given key, or |
3354 |
< |
* null if there is no such Entry. |
3355 |
< |
* @throws ClassCastException if key cannot be compared with the keys |
3356 |
< |
* currently in the map. |
3354 |
> |
* <tt>null</tt> if there is no such Entry. |
3355 |
> |
* @throws ClassCastException if key cannot be compared with |
3356 |
> |
* the keys currently in the map. |
3357 |
|
* @throws NullPointerException if key is <tt>null</tt>. |
3358 |
|
*/ |
3359 |
|
public Map.Entry<K,V> higherEntry(K key) { |
3362 |
|
|
3363 |
|
/** |
3364 |
|
* Returns a key-value mapping associated with the least |
3365 |
< |
* key in this map, or null if the map is empty. |
3365 |
> |
* key in this map, or <tt>null</tt> if the map is empty. |
3366 |
|
* The returned entry does <em>not</em> support |
3367 |
|
* the <tt>Entry.setValue</tt> method. |
3368 |
|
* |
3369 |
< |
* @return an Entry with least key, or null |
3369 |
> |
* @return an Entry with least key, or <tt>null</tt> |
3370 |
|
* if the map is empty. |
3371 |
|
*/ |
3372 |
|
public Map.Entry<K,V> firstEntry() { |
3382 |
|
|
3383 |
|
/** |
3384 |
|
* Returns a key-value mapping associated with the greatest |
3385 |
< |
* key in this map, or null if the map is empty. |
3385 |
> |
* key in this map, or <tt>null</tt> if the map is empty. |
3386 |
|
* The returned entry does <em>not</em> support |
3387 |
|
* the <tt>Entry.setValue</tt> method. |
3388 |
|
* |
3389 |
< |
* @return an Entry with greatest key, or null |
3389 |
> |
* @return an Entry with greatest key, or <tt>null</tt> |
3390 |
|
* if the map is empty. |
3391 |
|
*/ |
3392 |
|
public Map.Entry<K,V> lastEntry() { |
3402 |
|
|
3403 |
|
/** |
3404 |
|
* Removes and returns a key-value mapping associated with |
3405 |
< |
* the least key in this map, or null if the map is empty. |
3405 |
> |
* the least key in this map, or <tt>null</tt> if the map is empty. |
3406 |
|
* The returned entry does <em>not</em> support |
3407 |
|
* the <tt>Entry.setValue</tt> method. |
3408 |
|
* |
3409 |
< |
* @return the removed first entry of this map, or null |
3409 |
> |
* @return the removed first entry of this map, or <tt>null</tt> |
3410 |
|
* if the map is empty. |
3411 |
|
*/ |
3412 |
|
public Map.Entry<K,V> pollFirstEntry() { |
3414 |
|
} |
3415 |
|
|
3416 |
|
/** |
3417 |
< |
* Removes and returns a key-value mapping associated with |
3418 |
< |
* the greatest key in this map, or null if the map is empty. |
3419 |
< |
* The returned entry does <em>not</em> support |
3420 |
< |
* the <tt>Entry.setValue</tt> method. |
3417 |
> |
* Removes and returns a key-value mapping associated with the |
3418 |
> |
* greatest key in this map, or <tt>null</tt> if the map is |
3419 |
> |
* empty. The returned entry does <em>not</em> support the |
3420 |
> |
* <tt>Entry.setValue</tt> method. |
3421 |
|
* |
3422 |
< |
* @return the removed last entry of this map, or null |
3422 |
> |
* @return the removed last entry of this map, or <tt>null</tt> |
3423 |
|
* if the map is empty. |
3424 |
|
*/ |
3425 |
|
public Map.Entry<K,V> pollLastEntry() { |
3609 |
|
} |
3610 |
|
} |
3611 |
|
} |
3568 |
– |
|
3612 |
|
} |