Package org.kingdoms.utils.internal

Class UnsafeHashMap.TreeNode<K,V>

java.lang.Object
org.kingdoms.utils.internal.UnsafeHashMap.Node<K,V>
org.kingdoms.utils.internal.UnsafeHashMap.Entry<K,V>
org.kingdoms.utils.internal.UnsafeHashMap.TreeNode<K,V>
All Implemented Interfaces:
Map.Entry<K,V>
Enclosing class:
UnsafeHashMap<K,V>
public static final class UnsafeHashMap.TreeNode<K,V> extends UnsafeHashMap.Entry<K,V>
Entry for Tree bins. Extends LinkedHashMap.Entry (which in turn extends Node) so can be used as extension of either regular or linked node.

  • Method Details

    • moveRootToFront

      public static <K, V> void moveRootToFront(UnsafeHashMap.Node<K,V>[] tab, UnsafeHashMap.TreeNode<K,V> root)
      Ensures that the given root is the first node of its bin.

    • tieBreakOrder

      public static int tieBreakOrder(Object a, 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.

    • rotateLeft

      public static <K, V> UnsafeHashMap.TreeNode<K,V> rotateLeft(UnsafeHashMap.TreeNode<K,V> root, UnsafeHashMap.TreeNode<K,V> p)

    • rotateRight

      public static <K, V> UnsafeHashMap.TreeNode<K,V> rotateRight(UnsafeHashMap.TreeNode<K,V> root, UnsafeHashMap.TreeNode<K,V> p)

    • balanceInsertion

      public static <K, V> UnsafeHashMap.TreeNode<K,V> balanceInsertion(UnsafeHashMap.TreeNode<K,V> root, UnsafeHashMap.TreeNode<K,V> x)

    • balanceDeletion

      public static <K, V> UnsafeHashMap.TreeNode<K,V> balanceDeletion(UnsafeHashMap.TreeNode<K,V> root, UnsafeHashMap.TreeNode<K,V> x)

    • checkInvariants

      public static <K, V> boolean checkInvariants(UnsafeHashMap.TreeNode<K,V> t)
      Recursive invariant check

    • root

      public final UnsafeHashMap.TreeNode<K,V> root()
      Returns root of tree containing this node.

    • find

      public final UnsafeHashMap.TreeNode<K,V> find(int h, Object k, Class<?> kc)
      Finds the node starting at root p with the given hash and key. The kc argument caches comparableClassFor(key) upon first use comparing keys.

    • getTreeNode

      public final UnsafeHashMap.TreeNode<K,V> getTreeNode(int h, Object k)
      Calls find for root node.

    • treeify

      public final void treeify(UnsafeHashMap.Node<K,V>[] tab)
      Forms tree of the nodes linked from this node. return root of tree

    • untreeify

      public final UnsafeHashMap.Node<K,V> untreeify(UnsafeHashMap<K,V> map)
      Returns a list of non-TreeNodes replacing those linked from this node.

    • putTreeVal

      public final @Nullable UnsafeHashMap.TreeNode<K,V> putTreeVal(@NonNull UnsafeHashMap<K,V> map, @NonNull UnsafeHashMap.Node<K,V>[] tab, int h, @NonNull K k, @Nullable V v)
      Tree version of putVal.

    • removeTreeNode

      public final void removeTreeNode(UnsafeHashMap<K,V> map, UnsafeHashMap.Node<K,V>[] tab, boolean movable)
      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 during traversal. So instead we swap the tree linkages. If the current tree appears to have too few nodes, the bin is converted back to a plain bin. (The test triggers somewhere between 2 and 6 nodes, depending on tree structure).

    • split

      public final void split(UnsafeHashMap<K,V> map, UnsafeHashMap.Node<K,V>[] tab, int index, int bit)
      Splits nodes in a tree bin into lower and upper tree bins, or untreeifies if now too small. Called only from resize; see above discussion about split bits and indices.
      Parameters:
      map - the map
      tab - the table for recording bin heads
      index - the index of the table being split
      bit - the bit of hash to split on