Package com.apple.foundationdb.async.rtree

Interface Node

public interface Node
Interface to capture the common aspects of nodes being either LeafNodes or IntermediateNodes. All nodes have a node id and slots and can be linked up to a parent. Note that while the root node mostly is an intermediate node it can also be a leaf node if the tree is nearly empty.
This interface is then implemented by AbstractNode in a stronger-typed way. A node for most practical purposes interacts with e.f. NodeSlots, only some specific use-cases including the internals of nodes and node slots themselves need to be aware of the pairing of specific node type and specific belonging node slot type. A Node hides these private typing details much like a private method is hidden. Other languages have built-in features to do similar things. Scala uses an approach called type aliases to allow generic type variables to become private to be only used by implementations of the inner classes.

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Interface
    Description
    static interface 
    Node.ChangeSet
    A change set for slots.

  • Method Summary

    Modifier and Type
    Method
    Description
    Node
    deleteAllSlots(com.apple.foundationdb.async.rtree.StorageAdapter storageAdapter, int level)
    Delete all slots from the node.
    Node
    deleteSlot(com.apple.foundationdb.async.rtree.StorageAdapter storageAdapter, int level, int slotIndex)
    Delete a slot from the node.
    Node.ChangeSet
    getChangeSet()
    Returns the change set that need to be applied in order to correctly persist the node.
    byte[]
    getId()
    Return the id of this node.
    NodeKind
    getKind()
    Return the kind of the node, i.e.
    com.apple.foundationdb.async.rtree.IntermediateNode
    getParentNode()
    Return the parent of this node.
    NodeSlot
    getSlot(int index)
    Return the NodeSlot at the position indicated by index.
    int
    getSlotIndexInParent()
     
    default ChildSlot
    getSlotInParent()
    Return the ChildSlot of this node in this node's parent node.
    Iterable<? extends NodeSlot>
    getSlots()
    Return an iterable of all node slots.
    Iterable<? extends NodeSlot>
    getSlots(int startIndexInclusive, int endIndexExclusive)
    Return an iterable of a sub range of node slots.
    Node
    insertSlot(com.apple.foundationdb.async.rtree.StorageAdapter storageAdapter, int level, int slotIndex, NodeSlot slot)
    Insert a new slot into the node.
    boolean
    isEmpty()
    Return if this node does not hold any slots.
    default boolean
    isRoot()
    Returns if this node is the root node.
    void
    linkToParent(com.apple.foundationdb.async.rtree.IntermediateNode parentNode, int slotInParent)
    Link this node to its parent node.
    Node
    moveInSlots(com.apple.foundationdb.async.rtree.StorageAdapter storageAdapter, Iterable<? extends NodeSlot> slots)
    Move slots into this node that were previously part of another node (of the same kind).
    Node
    moveOutAllSlots(com.apple.foundationdb.async.rtree.StorageAdapter storageAdapter)
    Move all slots out of this node.
    Node
    newOfSameKind(byte[] nodeId)
    Create a new node that is of the same NodeKind as this node.
    int
    size()
    Return the number of used slots of this node.
    Stream<? extends NodeSlot>
    slotsStream()
    Return a stream of node slots.
    Node
    updateSlot(com.apple.foundationdb.async.rtree.StorageAdapter storageAdapter, int level, int slotIndex, NodeSlot updatedSlot)
    Update an existing slot of this node.
    default void
    validate()
    Method to validate the invariants of this node.
    default void
    validateParentNode(com.apple.foundationdb.async.rtree.IntermediateNode parentNode, ChildSlot childSlotInParentNode)
    Method to validate the invariants of the relationships of this node and this node's parent's ChildSlot corresponding to this node.

  • Method Details

    • getId

      @Nonnull byte[] getId()
      Return the id of this node.
      Returns:
      a byte array that represents the unique identifier of this node

    • size

      int size()
      Return the number of used slots of this node.
      Returns:
      the number of used slots

    • isEmpty

      boolean isEmpty()
      Return if this node does not hold any slots. Note that a node can ony be temporarily empty, for instance when slots are moved out of a node before other slots get moved in. Such a node must not be persisted as it violates the invariants of ancR-tree.
      Returns:
      true if the node currently does not hold any node slots.

    • getSlots

      @Nonnull Iterable<? extends NodeSlot> getSlots()
      Return an iterable of all node slots. Note that the slots are returned as an Iterable of ? extends NodeSlot rather than the particular actual node slot type.
      Returns:
      an Iterable of node slots.

    • getSlots

      @Nonnull Iterable<? extends NodeSlot> getSlots(int startIndexInclusive, int endIndexExclusive)
      Return an iterable of a sub range of node slots. Note that the slots are returned as an Iterable of ? extends NodeSlot rather than the particular actual node slot type.
      Parameters:
      startIndexInclusive - start index (inclusive)
      endIndexExclusive - end index (exclusive)
      Returns:
      an Iterable of node slots.

    • getSlot

      @Nonnull NodeSlot getSlot(int index)
      Return the NodeSlot at the position indicated by index.
      Parameters:
      index - the index
      Returns:
      a NodeSlot at position index

    • slotsStream

      @Nonnull Stream<? extends NodeSlot> slotsStream()
      Return a stream of node slots. Note that the slots are returned as a Stream of ? extends NodeSlot rather than the particular actual node slot type.
      Returns:
      a Stream of node slots

    • getChangeSet

      @Nullable Node.ChangeSet getChangeSet()
      Returns the change set that need to be applied in order to correctly persist the node.
      Returns:
      the change set, or null if the node has not been altered since it was read from the database

    • moveInSlots

      @CanIgnoreReturnValue @Nonnull Node moveInSlots(@Nonnull com.apple.foundationdb.async.rtree.StorageAdapter storageAdapter, @Nonnull Iterable<? extends NodeSlot> slots)
      Move slots into this node that were previously part of another node (of the same kind). This operation differs from the semantics of insertSlot(StorageAdapter, int, int, NodeSlot) as it does not update the node slot index as the node slots were part of another node before and are assumed to have been persisted in that index before. This method represents the counterpart of moveOutAllSlots(StorageAdapter).
      Parameters:
      storageAdapter - the storage adapter in use
      slots - an iterable of slots to be moved in
      Returns:
      this node

    • moveOutAllSlots

      @CanIgnoreReturnValue @Nonnull Node moveOutAllSlots(@Nonnull com.apple.foundationdb.async.rtree.StorageAdapter storageAdapter)
      Move all slots out of this node. This operation differs from the semantics of deleteAllSlots(StorageAdapter, int) as it does not update the node slot index. It is the counterpart of moveInSlots(StorageAdapter, Iterable).
      Parameters:
      storageAdapter - the storage adapter in use
      Returns:
      this node

    • insertSlot

      @CanIgnoreReturnValue @Nonnull Node insertSlot(@Nonnull com.apple.foundationdb.async.rtree.StorageAdapter storageAdapter, int level, int slotIndex, @Nonnull NodeSlot slot)
      Insert a new slot into the node.
      Parameters:
      storageAdapter - storage adapter in use
      level - level (for use in the node slot index)
      slotIndex - ordinal position where slot is inserted
      slot - the new slot
      Returns:
      this node

    • updateSlot

      @CanIgnoreReturnValue @Nonnull Node updateSlot(@Nonnull com.apple.foundationdb.async.rtree.StorageAdapter storageAdapter, int level, int slotIndex, @Nonnull NodeSlot updatedSlot)
      Update an existing slot of this node.
      Parameters:
      storageAdapter - storage adapter in use
      level - level (for use in the node slot index)
      slotIndex - ordinal position of the slot to be updated
      updatedSlot - the updated slot
      Returns:
      this node

    • deleteSlot

      @CanIgnoreReturnValue @Nonnull Node deleteSlot(@Nonnull com.apple.foundationdb.async.rtree.StorageAdapter storageAdapter, int level, int slotIndex)
      Delete a slot from the node.
      Parameters:
      storageAdapter - storage adapter in use
      level - level (for use in the node slot index)
      slotIndex - ordinal position where slot is inserted
      Returns:
      this node

    • deleteAllSlots

      @CanIgnoreReturnValue @Nonnull Node deleteAllSlots(@Nonnull com.apple.foundationdb.async.rtree.StorageAdapter storageAdapter, int level)
      Delete all slots from the node.
      Parameters:
      storageAdapter - storage adapter in use
      level - level (for use in the node slot index)
      Returns:
      this node

    • isRoot

      default boolean isRoot()
      Returns if this node is the root node. Note that a node is considered the root node if its node id is equal to RTree.rootId
      Returns:
      true if this node is the root node, false otherwise

    • getKind

      @Nonnull NodeKind getKind()
      Return the kind of the node, i.e. NodeKind.LEAF or NodeKind.INTERMEDIATE.
      Returns:
      the kind of this node as a NodeKind

    • getParentNode

      @Nullable com.apple.foundationdb.async.rtree.IntermediateNode getParentNode()
      Return the parent of this node.
      Returns:
      the parent of this node. Note that a result of null does not imply that this node is the rooot node. It simply means that the parent node linked up to this node yet. Usually that means that the actual parent node has not yet been fetched from the database.

    • getSlotIndexInParent

      int getSlotIndexInParent()

    • getSlotInParent

      @Nullable default ChildSlot getSlotInParent()
      Return the ChildSlot of this node in this node's parent node. Note that this method returns null if the parent node has not been linked up yet. Also, the invariant (parent node == null) <=> (slot in parent == null) holds.
      Returns:
      the ChildSlot corresponding to this node in the parent node or null if the parent node has not been linked up yet or this node is the root node

    • linkToParent

      void linkToParent(@Nonnull com.apple.foundationdb.async.rtree.IntermediateNode parentNode, int slotInParent)
      Link this node to its parent node. This sets upwards references allowing a bottom-up traversal of the levels of the tree.
      Parameters:
      parentNode - the parent node to link up to
      slotInParent - the slot index indicating the ChildSlot in the parent node that corresponds to this node

    • newOfSameKind

      @Nonnull Node newOfSameKind(@Nonnull byte[] nodeId)
      Create a new node that is of the same NodeKind as this node.
      Parameters:
      nodeId - node id for the new node
      Returns:
      a new empty node using the unique node id passed in

    • validate

      default void validate()
      Method to validate the invariants of this node.

    • validateParentNode

      default void validateParentNode(@Nullable com.apple.foundationdb.async.rtree.IntermediateNode parentNode, @Nullable ChildSlot childSlotInParentNode)
      Method to validate the invariants of the relationships of this node and this node's parent's ChildSlot corresponding to this node.
      Parameters:
      parentNode - a parent node if it exists
      childSlotInParentNode - the ChildSlot in the parent node handed in that corresponds to this node