| 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. |
| 714 |
|
*/ |
| 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 |
| 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 |
| 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); |
| 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); |
| 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); |
| 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); |
| 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 |
| 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 |
| 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 |
| 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)) { |
