| 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 |
| 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 |
< |
K removeFirstKey() { |
| 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 n.key; |
| 1237 |
< |
} |
| 1237 |
< |
} |
| 1238 |
< |
|
| 1239 |
< |
/** |
| 1240 |
< |
* Remove first entry; return SnapshotEntry or null if empty. |
| 1241 |
< |
*/ |
| 1242 |
< |
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 |
< |
*/ |
| 1247 |
< |
for (;;) { |
| 1248 |
< |
Node<K,V> b = head.node; |
| 1249 |
< |
Node<K,V> n = b.next; |
| 1250 |
< |
if (n == null) |
| 1251 |
< |
return null; |
| 1252 |
< |
Node<K,V> f = n.next; |
| 1253 |
< |
if (n != b.next) |
| 1254 |
< |
continue; |
| 1255 |
< |
Object v = n.value; |
| 1256 |
< |
if (v == null) { |
| 1257 |
< |
n.helpDelete(b, f); |
| 1258 |
< |
continue; |
| 1259 |
< |
} |
| 1260 |
< |
if (!n.casValue(v, null)) |
| 1261 |
< |
continue; |
| 1262 |
< |
if (!n.appendMarker(f) || !b.casNext(n, f)) |
| 1263 |
< |
findFirst(); // retry |
| 1264 |
< |
clearIndexToFirst(); |
| 1265 |
< |
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 |
| 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 <tt>null</tt>. |
| 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 <tt>null</tt> 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 <tt>null</tt> |
| 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) { |
| 2177 |
|
} |
| 2178 |
|
|
| 2179 |
|
/** |
| 2180 |
< |
* Returns a key-value mapping associated with the greatest |
| 2181 |
< |
* key less than or equal to the given key, or <tt>null</tt> 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. |
| 2194 |
|
} |
| 2195 |
|
|
| 2196 |
|
/** |
| 2197 |
< |
* Returns a key-value mapping associated with the least |
| 2198 |
< |
* key strictly greater than the given key, or <tt>null</tt> 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. |
| 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 |
|
/** |
| 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 -------------- */ |
| 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 |
| 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(); |
| 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; |
| 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 <tt>null</tt> 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 <tt>null</tt> |
| 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 <tt>null</tt> 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 <tt>null</tt> if there is no such Entry. |
| 3321 |
< |
* @throws ClassCastException if key cannot be compared with the keys |
| 3322 |
< |
* currently in the map. |
| 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 <tt>null</tt> 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 <tt>null</tt> |
| 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 <tt>null</tt> 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 |
|
* <tt>null</tt> if there is no such Entry. |
| 3355 |
< |
* @throws ClassCastException if key cannot be compared with the keys |
| 3356 |
< |
* currently in the map. |
| 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) { |
| 3414 |
|
} |
| 3415 |
|
|
| 3416 |
|
/** |
| 3417 |
< |
* Removes and returns a key-value mapping associated with |
| 3418 |
< |
* the greatest key in this map, or <tt>null</tt> 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 <tt>null</tt> |
| 3423 |
|
* if the map is empty. |
| 3609 |
|
} |
| 3610 |
|
} |
| 3611 |
|
} |
| 3568 |
– |
|
| 3612 |
|
} |
