Class ConcurrentHashMapV8.TreeBin<K,V>
java.lang.Object
org.glassfish.jersey.internal.util.collection.ConcurrentHashMapV8.Node<K,V>
org.glassfish.jersey.internal.util.collection.ConcurrentHashMapV8.TreeBin<K,V>
- All Implemented Interfaces:
Map.Entry<K,
V>
- Enclosing class:
ConcurrentHashMapV8<K,
V>
TreeNodes used at the heads of bins. TreeBins do not hold user
keys or values, but instead point to list of TreeNodes and
their root. They also maintain a parasitic read-write lock
forcing writers (who hold bin lock) to wait for readers (who do
not) to complete before tree restructuring operations.
-
Field Summary
FieldsModifier and TypeFieldDescription(package private) ConcurrentHashMapV8.TreeNode
<K, V> (package private) int
private static final long
(package private) static final int
(package private) ConcurrentHashMapV8.TreeNode
<K, V> private static final sun.misc.Unsafe
(package private) Thread
(package private) static final int
(package private) static final int
Fields inherited from class org.glassfish.jersey.internal.util.collection.ConcurrentHashMapV8.Node
hash, key, next, val
-
Constructor Summary
ConstructorsConstructorDescriptionCreates bin with initial set of nodes headed by b. -
Method Summary
Modifier and TypeMethodDescription(package private) static <K,
V> ConcurrentHashMapV8.TreeNode <K, V> balanceDeletion
(ConcurrentHashMapV8.TreeNode<K, V> root, ConcurrentHashMapV8.TreeNode<K, V> x) (package private) static <K,
V> ConcurrentHashMapV8.TreeNode <K, V> balanceInsertion
(ConcurrentHashMapV8.TreeNode<K, V> root, ConcurrentHashMapV8.TreeNode<K, V> x) (package private) static <K,
V> boolean Recursive invariant checkprivate final void
Possibly blocks awaiting root lock.(package private) final ConcurrentHashMapV8.Node
<K, V> Returns matching node or null if none.private final void
lockRoot()
Acquires write lock for tree restructuring.(package private) final ConcurrentHashMapV8.TreeNode
<K, V> putTreeVal
(int h, K k, V v) Finds or adds a node.(package private) final boolean
Removes the given node, that must be present before this call.(package private) static <K,
V> ConcurrentHashMapV8.TreeNode <K, V> rotateLeft
(ConcurrentHashMapV8.TreeNode<K, V> root, ConcurrentHashMapV8.TreeNode<K, V> p) (package private) static <K,
V> ConcurrentHashMapV8.TreeNode <K, V> rotateRight
(ConcurrentHashMapV8.TreeNode<K, V> root, ConcurrentHashMapV8.TreeNode<K, V> p) (package private) static int
tieBreakOrder
(Object a, Object b) Tie-breaking utility for ordering insertions when equal hashCodes and non-comparable.private final void
Releases write lock for tree restructuring.
-
Field Details
-
root
ConcurrentHashMapV8.TreeNode<K,V> root -
first
-
waiter
-
lockState
volatile int lockState -
WRITER
static final int WRITER- See Also:
-
WAITER
static final int WAITER- See Also:
-
READER
static final int READER- See Also:
-
U
private static final sun.misc.Unsafe U -
LOCKSTATE
private static final long LOCKSTATE
-
-
Constructor Details
-
TreeBin
TreeBin(ConcurrentHashMapV8.TreeNode<K, V> b) Creates bin with initial set of nodes headed by b.
-
-
Method Details
-
tieBreakOrder
Tie-breaking utility for ordering insertions when equal hashCodes and non-comparable. We don't require a total order, just a consistent insertion rule to maintain equivalence across rebalancings. Tie-breaking further than necessary simplifies testing a bit. -
lockRoot
private final void lockRoot()Acquires write lock for tree restructuring. -
unlockRoot
private final void unlockRoot()Releases write lock for tree restructuring. -
contendedLock
private final void contendedLock()Possibly blocks awaiting root lock. -
find
Returns matching node or null if none. Tries to search using tree comparisons from root, but continues linear search when lock not available.- Overrides:
find
in classConcurrentHashMapV8.Node<K,
V>
-
putTreeVal
Finds or adds a node.- Returns:
- null if added
-
removeTreeNode
Removes the given node, that must be present before this call. This is messier than typical red-black deletion code because we cannot swap the contents of an interior node with a leaf successor that is pinned by "next" pointers that are accessible independently of lock. So instead we swap the tree linkages.- Returns:
- true if now too small, so should be untreeified
-
rotateLeft
static <K,V> ConcurrentHashMapV8.TreeNode<K,V> rotateLeft(ConcurrentHashMapV8.TreeNode<K, V> root, ConcurrentHashMapV8.TreeNode<K, V> p) -
rotateRight
static <K,V> ConcurrentHashMapV8.TreeNode<K,V> rotateRight(ConcurrentHashMapV8.TreeNode<K, V> root, ConcurrentHashMapV8.TreeNode<K, V> p) -
balanceInsertion
static <K,V> ConcurrentHashMapV8.TreeNode<K,V> balanceInsertion(ConcurrentHashMapV8.TreeNode<K, V> root, ConcurrentHashMapV8.TreeNode<K, V> x) -
balanceDeletion
static <K,V> ConcurrentHashMapV8.TreeNode<K,V> balanceDeletion(ConcurrentHashMapV8.TreeNode<K, V> root, ConcurrentHashMapV8.TreeNode<K, V> x) -
checkInvariants
Recursive invariant check
-