Package org.apache.cassandra.io.tries

Class TrieNode

java.lang.Object
org.apache.cassandra.io.tries.TrieNode
public abstract class TrieNode extends Object
Trie node types and manipulation mechanisms. The main purpose of this is to allow for handling tries directly as they are on disk without any serialization, and to enable the creation of such files.

The serialization methods take as argument a generic SerializationNode and provide a method typeFor for choosing a suitable type to represent it, which can then be used to calculate size and write the node.

To read a file containing trie nodes, one would use at to identify the node type and then the various read methods to retrieve the data. They all take a buffer (usually memory-mapped) containing the data, and a position in it that identifies the node.

These node types do not specify any treatment of payloads. They are only concerned with providing 4 bits of space for payloadFlags, and a way of calculating the position after the node. Users of this class by convention use non-zero payloadFlags to indicate a payload exists, write it (possibly in flag-dependent format) at serialization time after the node itself is written, and read it using the payloadPosition value.

To improve efficiency, multiple node types depending on the number of transitions are provided: -- payload only, which has no outgoing transitions -- single outgoing transition -- sparse, which provides a list of transition bytes with corresponding targets -- dense, where the transitions span a range of values and having the list (and the search in it) can be avoided

For each of the transition-carrying types we also have "in-page" versions where transition targets are the 4, 8 or 12 lowest bits of the position within the same page. To save one further byte, the single in-page versions using 4 or 12 bits cannot carry a payload.

This class is effectively an enumeration; abstract class permits instances to extend each other and reuse code.

See org/apache/cassandra/io/sstable/format/bti/BtiFormat.md for a description of the mechanisms of writing and reading an on-disk trie.

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    static final int
    NONE
    Value used to indicate a branch (e.g.

  • Method Summary

    Modifier and Type
    Method
    Description
    static TrieNode
    at(ByteBuffer src, int position)
    Returns the type of node stored at this position.
    abstract long
    greaterTransition(ByteBuffer src, int position, long positionLong, int searchIndex, long defaultValue)
    Returns a transition that is higher than the index returned by search.
    long
    lastTransition(ByteBuffer src, int position, long positionLong)
    Returns the highest transition for this node, or NONE if none exist (PAYLOAD_ONLY nodes).
    abstract long
    lesserTransition(ByteBuffer src, int position, long positionLong, int searchIndex, long defaultValue)
    Returns a transition that is lower than the index returned by search.
    int
    payloadFlags(ByteBuffer src, int position)
    Returns the 4 payload flag bits.
    abstract int
    payloadPosition(ByteBuffer src, int position)
    Return the position just after the node, where the payload is usually stored.
    abstract int
    search(ByteBuffer src, int position, int transitionByte)
    Returns search index for the given byte in the node.
    abstract void
    serialize(DataOutputPlus out, SerializationNode<?> node, int payloadBits, long nodePosition)
    Serializes the node.
    abstract int
    sizeofNode(SerializationNode<?> node)
    Returns the size needed to serialize this node.
    String
    toString()
     
    long
    transition(ByteBuffer src, int position, long positionLong, int childIndex)
    Returns position of node to transition to for the given search index.
    abstract int
    transitionByte(ByteBuffer src, int position, int childIndex)
    Returns the byte value for this child index, or Integer.MAX_VALUE if there are no transitions with this index or higher to permit listing the children without needing to call transitionRange.
    abstract int
    transitionRange(ByteBuffer src, int position)
    Returns the upper childIndex limit.
    static TrieNode
    typeFor(SerializationNode<?> node, long nodePosition)
    Returns a node type that is suitable to store the node.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

  • Field Details

    • NONE

      public static final int NONE
      Value used to indicate a branch (e.g. for transition and lastTransition) does not exist.
      See Also:

  • Method Details

    • at

      public static TrieNode at(ByteBuffer src, int position)
      Returns the type of node stored at this position. It can then be used to call the methods below.

    • payloadFlags

      public int payloadFlags(ByteBuffer src, int position)
      Returns the 4 payload flag bits. Node types that cannot carry a payload return 0.

    • payloadPosition

      public abstract int payloadPosition(ByteBuffer src, int position)
      Return the position just after the node, where the payload is usually stored.

    • search

      public abstract int search(ByteBuffer src, int position, int transitionByte)
      Returns search index for the given byte in the node. If exact match is present, this is >= 0, otherwise as in binary search.

    • transitionRange

      public abstract int transitionRange(ByteBuffer src, int position)
      Returns the upper childIndex limit. Calling transition with values 0...transitionRange - 1 is valid.

    • transitionByte

      public abstract int transitionByte(ByteBuffer src, int position, int childIndex)
      Returns the byte value for this child index, or Integer.MAX_VALUE if there are no transitions with this index or higher to permit listing the children without needing to call transitionRange.
      Parameters:
      childIndex - must be >= 0, though it is allowed to pass a value greater than transitionRange - 1

    • transition

      public long transition(ByteBuffer src, int position, long positionLong, int childIndex)
      Returns position of node to transition to for the given search index. Argument must be positive. May return NONE if a transition with that index does not exist (DENSE nodes). Position is the offset of the node within the ByteBuffer. positionLong is its global placement, which is the base for any offset calculations.
      Parameters:
      positionLong - although it seems to be obvious, this argument must be "real", that is, each child must have the calculated absolute position >= 0, otherwise the behaviour of this method is undefined
      childIndex - must be >= 0 and < transitionRange(ByteBuffer, int) - note that this is not validated and behaviour of this method is undefined for values outside of that range

    • lastTransition

      public long lastTransition(ByteBuffer src, int position, long positionLong)
      Returns the highest transition for this node, or NONE if none exist (PAYLOAD_ONLY nodes).

    • greaterTransition

      public abstract long greaterTransition(ByteBuffer src, int position, long positionLong, int searchIndex, long defaultValue)
      Returns a transition that is higher than the index returned by search. This may not exist (if the argument was higher than the last transition byte), in which case this returns the given defaultValue.

    • lesserTransition

      public abstract long lesserTransition(ByteBuffer src, int position, long positionLong, int searchIndex, long defaultValue)
      Returns a transition that is lower than the index returned by search. Returns defaultValue for searchIndex equals 0 or -1 as lesser transition for those indexes does not exist.

    • typeFor

      public static TrieNode typeFor(SerializationNode<?> node, long nodePosition)
      Returns a node type that is suitable to store the node.

    • sizeofNode

      public abstract int sizeofNode(SerializationNode<?> node)
      Returns the size needed to serialize this node.

    • serialize

      public abstract void serialize(DataOutputPlus out, SerializationNode<?> node, int payloadBits, long nodePosition) throws IOException
      Serializes the node. All transition target positions must already have been defined. payloadBits must be four bits.
      Throws:
      IOException

    • toString

      public String toString()
      Overrides:
      toString in class Object