1 |
|
/* |
2 |
|
* Written by Doug Lea with assistance from members of JCP JSR-166 |
3 |
|
* Expert Group and released to the public domain, as explained at |
4 |
< |
* http://creativecommons.org/licenses/publicdomain |
4 |
> |
* http://creativecommons.org/publicdomain/zero/1.0/ |
5 |
|
*/ |
6 |
|
|
7 |
|
package jsr166x; |
325 |
|
private transient DescendingEntrySet descendingEntrySet; |
326 |
|
|
327 |
|
/** |
328 |
< |
* Initialize or reset state. Needed by constructors, clone, |
328 |
> |
* Initializes or resets state. Needed by constructors, clone, |
329 |
|
* clear, readObject. and ConcurrentSkipListSet.clone. |
330 |
|
* (Note that comparator must be separately initialized.) |
331 |
|
*/ |
414 |
|
} |
415 |
|
|
416 |
|
/** |
417 |
< |
* Return true if this node is a marker. This method isn't |
417 |
> |
* Returns true if this node is a marker. This method isn't |
418 |
|
* actually called in an any current code checking for markers |
419 |
|
* because callers will have already read value field and need |
420 |
|
* to use that read (not another done here) and so directly |
427 |
|
} |
428 |
|
|
429 |
|
/** |
430 |
< |
* Return true if this node is the header of base-level list. |
430 |
> |
* Returns true if this node is the header of base-level list. |
431 |
|
* @return true if this node is header node |
432 |
|
*/ |
433 |
|
boolean isBaseHeader() { |
465 |
|
} |
466 |
|
|
467 |
|
/** |
468 |
< |
* Return value if this node contains a valid key-value pair, |
468 |
> |
* Returns value if this node contains a valid key-value pair, |
469 |
|
* else null. |
470 |
|
* @return this node's value if it isn't a marker or header or |
471 |
|
* is deleted, else null. |
478 |
|
} |
479 |
|
|
480 |
|
/** |
481 |
< |
* Create and return a new SnapshotEntry holding current |
482 |
< |
* mapping if this node holds a valid value, else null |
481 |
> |
* Creates and returns a new SnapshotEntry holding current |
482 |
> |
* mapping if this node holds a valid value, else null. |
483 |
|
* @return new entry or null |
484 |
|
*/ |
485 |
|
SnapshotEntry<K,V> createSnapshot() { |
696 |
|
} |
697 |
|
|
698 |
|
/** |
699 |
< |
* Compare using comparator or natural ordering. Used when the |
699 |
> |
* Compares using comparator or natural ordering. Used when the |
700 |
|
* ComparableUsingComparator approach doesn't apply. |
701 |
|
*/ |
702 |
|
int compare(K k1, K k2) throws ClassCastException { |
708 |
|
} |
709 |
|
|
710 |
|
/** |
711 |
< |
* Return true if given key greater than or equal to least and |
711 |
> |
* Returns true if given key greater than or equal to least and |
712 |
|
* strictly less than fence, bypassing either test if least or |
713 |
< |
* fence oare null. Needed mainly in submap operations. |
713 |
> |
* fence are null. Needed mainly in submap operations. |
714 |
|
*/ |
715 |
|
boolean inHalfOpenRange(K key, K least, K fence) { |
716 |
|
if (key == null) |
720 |
|
} |
721 |
|
|
722 |
|
/** |
723 |
< |
* Return true if given key greater than or equal to least and less |
723 |
> |
* Returns true if given key greater than or equal to least and less |
724 |
|
* or equal to fence. Needed mainly in submap operations. |
725 |
|
*/ |
726 |
|
boolean inOpenRange(K key, K least, K fence) { |
733 |
|
/* ---------------- Traversal -------------- */ |
734 |
|
|
735 |
|
/** |
736 |
< |
* Return a base-level node with key strictly less than given key, |
736 |
> |
* Returns a base-level node with key strictly less than given key, |
737 |
|
* or the base-level header if there is no such node. Also |
738 |
|
* unlinks indexes to deleted nodes found along the way. Callers |
739 |
|
* rely on this side-effect of clearing indices to deleted nodes. |
766 |
|
} |
767 |
|
|
768 |
|
/** |
769 |
< |
* Return node holding key or null if no such, clearing out any |
769 |
> |
* Returns node holding key or null if no such, clearing out any |
770 |
|
* deleted nodes seen along the way. Repeatedly traverses at |
771 |
|
* base-level looking for key starting at predecessor returned |
772 |
|
* from findPredecessor, processing base-level deletions as |
865 |
|
} |
866 |
|
if (c == 0) { |
867 |
|
Object v = r.node.value; |
868 |
< |
return (v != null)? (V)v : getUsingFindNode(key); |
868 |
> |
return (v != null) ? (V)v : getUsingFindNode(key); |
869 |
|
} |
870 |
|
bound = rk; |
871 |
|
} |
878 |
|
int c = key.compareTo(nk); |
879 |
|
if (c == 0) { |
880 |
|
Object v = n.value; |
881 |
< |
return (v != null)? (V)v : getUsingFindNode(key); |
881 |
> |
return (v != null) ? (V)v : getUsingFindNode(key); |
882 |
|
} |
883 |
|
if (c < 0) |
884 |
|
return null; |
890 |
|
} |
891 |
|
|
892 |
|
/** |
893 |
< |
* Perform map.get via findNode. Used as a backup if doGet |
893 |
> |
* Performs map.get via findNode. Used as a backup if doGet |
894 |
|
* encounters an in-progress deletion. |
895 |
|
* @param key the key |
896 |
|
* @return the value, or null if absent |
965 |
|
} |
966 |
|
|
967 |
|
/** |
968 |
< |
* Return a random level for inserting a new node. |
968 |
> |
* Returns a random level for inserting a new node. |
969 |
|
* Hardwired to k=1, p=0.5, max 31. |
970 |
|
* |
971 |
|
* This uses a cheap pseudo-random function that according to |
987 |
|
} |
988 |
|
|
989 |
|
/** |
990 |
< |
* Create and add index nodes for given node. |
990 |
> |
* Creates and adds index nodes for given node. |
991 |
|
* @param z the node |
992 |
|
* @param level the level of the index |
993 |
|
*/ |
1039 |
|
} |
1040 |
|
|
1041 |
|
/** |
1042 |
< |
* Add given index nodes from given level down to 1. |
1042 |
> |
* Adds given index nodes from given level down to 1. |
1043 |
|
* @param idx the topmost index node being inserted |
1044 |
|
* @param h the value of head to use to insert. This must be |
1045 |
|
* snapshotted by callers to provide correct insertion level |
1221 |
|
} |
1222 |
|
|
1223 |
|
/** |
1224 |
< |
* Remove first entry; return either its key or a snapshot. |
1224 |
> |
* Removes 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 |
1246 |
|
findFirst(); // retry |
1247 |
|
clearIndexToFirst(); |
1248 |
|
K key = n.key; |
1249 |
< |
return (keyOnly)? key : new SnapshotEntry<K,V>(key, (V)v); |
1249 |
> |
return keyOnly ? key : new SnapshotEntry<K,V>(key, (V)v); |
1250 |
|
} |
1251 |
|
} |
1252 |
|
|
1253 |
|
/** |
1254 |
< |
* Clear out index nodes associated with deleted first entry. |
1255 |
< |
* Needed by doRemoveFirst |
1254 |
> |
* Clears out index nodes associated with deleted first entry. |
1255 |
> |
* Needed by doRemoveFirst. |
1256 |
|
*/ |
1257 |
|
private void clearIndexToFirst() { |
1258 |
|
for (;;) { |
1271 |
|
} |
1272 |
|
|
1273 |
|
/** |
1274 |
< |
* Remove first entry; return key or null if empty. |
1274 |
> |
* Removes first entry; return key or null if empty. |
1275 |
|
*/ |
1276 |
|
K pollFirstKey() { |
1277 |
|
return (K)doRemoveFirst(true); |
1306 |
|
Node<K,V> n = b.next; |
1307 |
|
for (;;) { |
1308 |
|
if (n == null) |
1309 |
< |
return (b.isBaseHeader())? null : b; |
1309 |
> |
return b.isBaseHeader() ? null : b; |
1310 |
|
Node<K,V> f = n.next; // inconsistent read |
1311 |
|
if (n != b.next) |
1312 |
|
break; |
1368 |
|
if (head.right == null) |
1369 |
|
tryReduceLevel(); |
1370 |
|
} |
1371 |
< |
return (keyOnly)? key : new SnapshotEntry<K,V>(key, (V)v); |
1371 |
> |
return keyOnly ? key : new SnapshotEntry<K,V>(key, (V)v); |
1372 |
|
} |
1373 |
|
} |
1374 |
|
} |
1405 |
|
} |
1406 |
|
|
1407 |
|
/** |
1408 |
< |
* Remove last entry; return key or null if empty. |
1408 |
> |
* Removes last entry; return key or null if empty. |
1409 |
|
*/ |
1410 |
|
K pollLastKey() { |
1411 |
|
return (K)doRemoveLast(true); |
1432 |
|
Node<K,V> n = b.next; |
1433 |
|
for (;;) { |
1434 |
|
if (n == null) |
1435 |
< |
return ((rel & LT) == 0 || b.isBaseHeader())? null : b; |
1435 |
> |
return ((rel & LT) == 0 || b.isBaseHeader()) ? null : b; |
1436 |
|
Node<K,V> f = n.next; |
1437 |
|
if (n != b.next) // inconsistent read |
1438 |
|
break; |
1448 |
|
(c < 0 && (rel & LT) == 0)) |
1449 |
|
return n; |
1450 |
|
if ( c <= 0 && (rel & LT) != 0) |
1451 |
< |
return (b.isBaseHeader())? null : b; |
1451 |
> |
return b.isBaseHeader() ? null : b; |
1452 |
|
b = n; |
1453 |
|
n = f; |
1454 |
|
} |
1456 |
|
} |
1457 |
|
|
1458 |
|
/** |
1459 |
< |
* Return SnapshotEntry for results of findNear. |
1459 |
> |
* Returns SnapshotEntry for results of findNear. |
1460 |
|
* @param kkey the key |
1461 |
|
* @param rel the relation -- OR'ed combination of EQ, LT, GT |
1462 |
|
* @return Entry fitting relation, or null if no such |
1473 |
|
} |
1474 |
|
|
1475 |
|
/** |
1476 |
< |
* Return ceiling, or first node if key is <tt>null</tt> |
1476 |
> |
* Returns ceiling, or first node if key is <tt>null</tt>. |
1477 |
|
*/ |
1478 |
|
Node<K,V> findCeiling(K key) { |
1479 |
< |
return (key == null)? findFirst() : findNear(key, GT|EQ); |
1479 |
> |
return (key == null) ? findFirst() : findNear(key, GT|EQ); |
1480 |
|
} |
1481 |
|
|
1482 |
|
/** |
1483 |
< |
* Return lower node, or last node if key is <tt>null</tt> |
1483 |
> |
* Returns lower node, or last node if key is <tt>null</tt>. |
1484 |
|
*/ |
1485 |
|
Node<K,V> findLower(K key) { |
1486 |
< |
return (key == null)? findLast() : findNear(key, LT); |
1486 |
> |
return (key == null) ? findLast() : findNear(key, LT); |
1487 |
|
} |
1488 |
|
|
1489 |
|
/** |
1490 |
< |
* Return SnapshotEntry or key for results of findNear ofter screening |
1490 |
> |
* Returns SnapshotEntry or key for results of findNear ofter screening |
1491 |
|
* to ensure result is in given range. Needed by submaps. |
1492 |
|
* @param kkey the key |
1493 |
|
* @param rel the relation -- OR'ed combination of EQ, LT, GT |
1513 |
|
K k = n.key; |
1514 |
|
V v = n.getValidValue(); |
1515 |
|
if (v != null) |
1516 |
< |
return keyOnly? k : new SnapshotEntry<K,V>(k, v); |
1516 |
> |
return keyOnly ? k : new SnapshotEntry<K,V>(k, v); |
1517 |
|
} |
1518 |
|
} |
1519 |
|
|
1520 |
|
/** |
1521 |
< |
* Find and remove least element of subrange. |
1521 |
> |
* Finds and removes least element of subrange. |
1522 |
|
* @param least minimum allowed key value |
1523 |
|
* @param fence key greater than maximum allowed key value |
1524 |
|
* @param keyOnly if true return key, else return SnapshotEntry |
1534 |
|
return null; |
1535 |
|
V v = doRemove(k, null); |
1536 |
|
if (v != null) |
1537 |
< |
return (keyOnly)? k : new SnapshotEntry<K,V>(k, v); |
1537 |
> |
return keyOnly ? k : new SnapshotEntry<K,V>(k, v); |
1538 |
|
} |
1539 |
|
} |
1540 |
|
|
1541 |
|
/** |
1542 |
< |
* Find and remove greatest element of subrange. |
1542 |
> |
* Finds and removes greatest element of subrange. |
1543 |
|
* @param least minimum allowed key value |
1544 |
|
* @param fence key greater than maximum allowed key value |
1545 |
|
* @param keyOnly if true return key, else return SnapshotEntry |
1555 |
|
return null; |
1556 |
|
V v = doRemove(k, null); |
1557 |
|
if (v != null) |
1558 |
< |
return (keyOnly)? k : new SnapshotEntry<K,V>(k, v); |
1558 |
> |
return keyOnly ? k : new SnapshotEntry<K,V>(k, v); |
1559 |
|
} |
1560 |
|
} |
1561 |
|
|
1689 |
|
/* ---------------- Serialization -------------- */ |
1690 |
|
|
1691 |
|
/** |
1692 |
< |
* Save the state of the <tt>Map</tt> instance to a stream. |
1692 |
> |
* Saves 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 |
1714 |
|
} |
1715 |
|
|
1716 |
|
/** |
1717 |
< |
* Reconstitute the <tt>Map</tt> instance from a stream. |
1717 |
> |
* Reconstitutes the <tt>Map</tt> instance from a stream. |
1718 |
|
*/ |
1719 |
|
private void readObject(final java.io.ObjectInputStream s) |
1720 |
|
throws java.io.IOException, ClassNotFoundException { |
1883 |
|
if (n.getValidValue() != null) |
1884 |
|
++count; |
1885 |
|
} |
1886 |
< |
return (count >= Integer.MAX_VALUE)? Integer.MAX_VALUE : (int)count; |
1886 |
> |
return (count >= Integer.MAX_VALUE) ? Integer.MAX_VALUE : (int)count; |
1887 |
|
} |
1888 |
|
|
1889 |
|
/** |
2094 |
|
* This is equivalent to |
2095 |
|
* <pre> |
2096 |
|
* if (!map.containsKey(key)) |
2097 |
< |
* return map.put(key, value); |
2097 |
> |
* return map.put(key, value); |
2098 |
|
* else |
2099 |
< |
* return map.get(key); |
2099 |
> |
* return map.get(key); |
2100 |
|
* </pre> |
2101 |
|
* except that the action is performed atomically. |
2102 |
|
* @param key key with which the specified value is to be associated. |
2115 |
|
} |
2116 |
|
|
2117 |
|
/** |
2118 |
< |
* Remove entry for key only if currently mapped to given value. |
2118 |
> |
* Removes entry for key only if currently mapped to given value. |
2119 |
|
* Acts as |
2120 |
|
* <pre> |
2121 |
|
* if ((map.containsKey(key) && map.get(key).equals(value)) { |
2250 |
|
* <tt>fromKey</tt> and <tt>toKey</tt> are equal, the returned sorted map |
2251 |
|
* is empty.) The returned sorted map is backed by this map, so changes |
2252 |
|
* in the returned sorted map are reflected in this map, and vice-versa. |
2253 |
< |
|
2253 |
> |
* |
2254 |
|
* @param fromKey low endpoint (inclusive) of the subMap. |
2255 |
|
* @param toKey high endpoint (exclusive) of the subMap. |
2256 |
|
* |
2305 |
|
* <tt>Comparable</tt>). |
2306 |
|
* @throws NullPointerException if <tt>fromKey</tt> is <tt>null</tt>. |
2307 |
|
*/ |
2308 |
< |
public ConcurrentNavigableMap<K,V> tailMap(K fromKey) { |
2308 |
> |
public ConcurrentNavigableMap<K,V> tailMap(K fromKey) { |
2309 |
|
if (fromKey == null) |
2310 |
|
throw new NullPointerException(); |
2311 |
|
return new ConcurrentSkipListSubMap(this, fromKey, null); |
2343 |
|
*/ |
2344 |
|
public K ceilingKey(K key) { |
2345 |
|
Node<K,V> n = findNear(key, GT|EQ); |
2346 |
< |
return (n == null)? null : n.key; |
2346 |
> |
return (n == null) ? null : n.key; |
2347 |
|
} |
2348 |
|
|
2349 |
|
/** |
2376 |
|
*/ |
2377 |
|
public K lowerKey(K key) { |
2378 |
|
Node<K,V> n = findNear(key, LT); |
2379 |
< |
return (n == null)? null : n.key; |
2379 |
> |
return (n == null) ? null : n.key; |
2380 |
|
} |
2381 |
|
|
2382 |
|
/** |
2410 |
|
*/ |
2411 |
|
public K floorKey(K key) { |
2412 |
|
Node<K,V> n = findNear(key, LT|EQ); |
2413 |
< |
return (n == null)? null : n.key; |
2413 |
> |
return (n == null) ? null : n.key; |
2414 |
|
} |
2415 |
|
|
2416 |
|
/** |
2443 |
|
*/ |
2444 |
|
public K higherKey(K key) { |
2445 |
|
Node<K,V> n = findNear(key, GT); |
2446 |
< |
return (n == null)? null : n.key; |
2446 |
> |
return (n == null) ? null : n.key; |
2447 |
|
} |
2448 |
|
|
2449 |
|
/** |
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 |
3053 |
> |
* @throws IllegalArgumentException if least and fence non-null |
3054 |
|
* and least greater than fence |
3055 |
|
*/ |
3056 |
|
ConcurrentSkipListSubMap(ConcurrentSkipListMap<K,V> map, |
3128 |
|
|
3129 |
|
public V get(Object key) { |
3130 |
|
K k = (K)key; |
3131 |
< |
return ((!inHalfOpenRange(k)) ? null : m.get(k)); |
3131 |
> |
return (!inHalfOpenRange(k)) ? null : m.get(k); |
3132 |
|
} |
3133 |
|
|
3134 |
|
public V put(K key, V value) { |
3138 |
|
|
3139 |
|
public V remove(Object key) { |
3140 |
|
K k = (K)key; |
3141 |
< |
return (!inHalfOpenRange(k))? null : m.remove(k); |
3141 |
> |
return (!inHalfOpenRange(k)) ? null : m.remove(k); |
3142 |
|
} |
3143 |
|
|
3144 |
|
public int size() { |
3149 |
|
if (n.getValidValue() != null) |
3150 |
|
++count; |
3151 |
|
} |
3152 |
< |
return count >= Integer.MAX_VALUE? Integer.MAX_VALUE : (int)count; |
3152 |
> |
return (count >= Integer.MAX_VALUE) ? |
3153 |
> |
Integer.MAX_VALUE : (int)count; |
3154 |
|
} |
3155 |
|
|
3156 |
|
public boolean isEmpty() { |
3241 |
|
return new ConcurrentSkipListSubMap(m, least, toKey); |
3242 |
|
} |
3243 |
|
|
3244 |
< |
public ConcurrentNavigableMap<K,V> tailMap(K fromKey) { |
3244 |
> |
public ConcurrentNavigableMap<K,V> tailMap(K fromKey) { |
3245 |
|
if (fromKey == null) |
3246 |
|
throw new NullPointerException(); |
3247 |
|
if (!inOpenRange(fromKey)) |