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:
java.util.Map.Entry<K,V>
- Enclosing class:
- ConcurrentHashMapV8<K,V>
static final class ConcurrentHashMapV8.TreeBin<K,V> extends ConcurrentHashMapV8.Node<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
Fields Modifier and Type Field Description (package private) ConcurrentHashMapV8.TreeNode<K,V>
first
(package private) int
lockState
private static long
LOCKSTATE
(package private) static int
READER
(package private) ConcurrentHashMapV8.TreeNode<K,V>
root
private static sun.misc.Unsafe
U
(package private) java.lang.Thread
waiter
(package private) static int
WAITER
(package private) static int
WRITER
-
Fields inherited from class org.glassfish.jersey.internal.util.collection.ConcurrentHashMapV8.Node
hash, key, next, val
-
-
Constructor Summary
Constructors Constructor Description TreeBin(ConcurrentHashMapV8.TreeNode<K,V> b)
Creates bin with initial set of nodes headed by b.
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description (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>
booleancheckInvariants(ConcurrentHashMapV8.TreeNode<K,V> t)
Recursive invariant checkprivate void
contendedLock()
Possibly blocks awaiting root lock.(package private) ConcurrentHashMapV8.Node<K,V>
find(int h, java.lang.Object k)
Returns matching node or null if none.private void
lockRoot()
Acquires write lock for tree restructuring.(package private) ConcurrentHashMapV8.TreeNode<K,V>
putTreeVal(int h, K k, V v)
Finds or adds a node.(package private) boolean
removeTreeNode(ConcurrentHashMapV8.TreeNode<K,V> p)
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(java.lang.Object a, java.lang.Object b)
Tie-breaking utility for ordering insertions when equal hashCodes and non-comparable.private void
unlockRoot()
Releases write lock for tree restructuring.
-
-
-
Field Detail
-
root
ConcurrentHashMapV8.TreeNode<K,V> root
-
first
volatile ConcurrentHashMapV8.TreeNode<K,V> first
-
waiter
volatile java.lang.Thread waiter
-
lockState
volatile int lockState
-
WRITER
static final int WRITER
- See Also:
- Constant Field Values
-
WAITER
static final int WAITER
- See Also:
- Constant Field Values
-
READER
static final int READER
- See Also:
- Constant Field Values
-
U
private static final sun.misc.Unsafe U
-
LOCKSTATE
private static final long LOCKSTATE
-
-
Constructor Detail
-
TreeBin
TreeBin(ConcurrentHashMapV8.TreeNode<K,V> b)
Creates bin with initial set of nodes headed by b.
-
-
Method Detail
-
tieBreakOrder
static int tieBreakOrder(java.lang.Object a, java.lang.Object b)
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
final ConcurrentHashMapV8.Node<K,V> find(int h, java.lang.Object k)
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
final ConcurrentHashMapV8.TreeNode<K,V> putTreeVal(int h, K k, V v)
Finds or adds a node.- Returns:
- null if added
-
removeTreeNode
final boolean removeTreeNode(ConcurrentHashMapV8.TreeNode<K,V> p)
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
static <K,V> boolean checkInvariants(ConcurrentHashMapV8.TreeNode<K,V> t)
Recursive invariant check
-
-