Package org.apache.cassandra.io.tries

Class Walker<CONCRETE extends Walker<CONCRETE>>

java.lang.Object
org.apache.cassandra.io.tries.Walker<CONCRETE>
All Implemented Interfaces:
AutoCloseable
Direct Known Subclasses:
PartitionIndex.Reader, ReverseValueIterator, RowIndexReader, TrieTermsDictionaryReader, ValueIterator
@NotThreadSafe public class Walker<CONCRETE extends Walker<CONCRETE>> extends Object implements AutoCloseable
Thread-unsafe trie walking helper. This is analogous to RandomAccessReader for tries -- takes an on-disk trie accessible via a supplied Rebufferer and lets user seek to nodes and work with them.

Assumes data was written using page-aware builder and thus no node crosses a page and thus a buffer boundary.

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 Details

    • NONE

      public static int NONE
      Value used to indicate a branch (e.g. lesser/greaterBranch) does not exist.

    • root

      protected final long root

    • nodeType

      protected TrieNode nodeType

    • buf

      protected ByteBuffer buf

    • position

      protected long position

    • greaterBranch

      protected long greaterBranch

    • lesserBranch

      protected long lesserBranch

    • BYTE_COMPARABLE_VERSION

      public static final ByteComparable.Version BYTE_COMPARABLE_VERSION

  • Constructor Details

    • Walker

      public Walker(Rebufferer source, long root)
      Creates a walker. Rebufferer must be aligned and with a buffer size that is at least 4k.

  • Method Details

    • close

      public void close()
      Specified by:
      close in interface AutoCloseable

    • go

      protected final void go(long position)

    • payloadFlags

      protected final int payloadFlags()

    • hasPayload

      protected final boolean hasPayload()

    • payloadPosition

      protected final int payloadPosition()

    • search

      protected final int search(int transitionByte)

    • transition

      protected final long transition(int childIndex)

    • lastTransition

      protected final long lastTransition()

    • greaterTransition

      protected final long greaterTransition(int searchIndex, long defaultValue)

    • lesserTransition

      protected final long lesserTransition(int searchIndex, long defaultValue)

    • transitionByte

      protected final int transitionByte(int childIndex)

    • transitionRange

      protected final int transitionRange()

    • hasChildren

      protected final boolean hasChildren()

    • goMax

      protected final void goMax(long pos)

    • goMin

      protected final void goMin(long pos)

    • follow

      public int follow(ByteComparable key)
      Follows the given key while there are transitions in the trie for it.
      Returns:
      the first unmatched byte of the key, may be ByteSource.END_OF_STREAM

    • followWithGreater

      public int followWithGreater(ByteComparable key)
      Follows the trie for a given key, remembering the closest greater branch. On return the walker is positioned at the longest prefix that matches the input (with or without payload), and min(greaterBranch) is the immediate greater neighbour.
      Returns:
      the first unmatched byte of the key, may be ByteSource.END_OF_STREAM

    • followWithLesser

      public int followWithLesser(ByteComparable key)
      Follows the trie for a given key, remembering the closest lesser branch. On return the walker is positioned at the longest prefix that matches the input (with or without payload), and max(lesserBranch) is the immediate lesser neighbour.
      Returns:
      the first unmatched byte of the key, may be ByteSource.END_OF_STREAM

    • prefix

      public <RESULT> RESULT prefix(ByteComparable key, Walker.Extractor<RESULT,CONCRETE> extractor) throws IOException
      Takes a prefix of the given key. The prefix is in the sense of a separator key match, i.e. it is only understood as valid if there are no greater entries in the trie (e.g. data at 'a' is ignored if 'ab' or 'abba' is in the trie when looking for 'abc' or 'ac', but accepted when looking for 'aa'). In order to not have to go back to data that may have exited cache, payloads are extracted when the node is visited (instead of saving the node's position), which requires an extractor to be passed as parameter.
      Throws:
      IOException

    • prefixAndNeighbours

      public <RESULT> RESULT prefixAndNeighbours(ByteComparable key, Walker.Extractor<RESULT,CONCRETE> extractor) throws IOException
      Follows the trie for a given key, taking a prefix (in the sense above) and searching for neighboring values. On return min(greaterBranch) and max(lesserBranch) are the immediate non-prefix neighbours for the sought value.

      Note: in a separator trie the closest smaller neighbour can be another prefix of the given key. This method does not take that into account. E.g. if trie contains "abba", "as" and "ask", looking for "asking" will find "ask" as the match, but max(lesserBranch) will point to "abba" instead of the correct "as". This problem can only occur if there is a valid prefix match.

      Throws:
      IOException

    • getMaxTerm

      public ByteComparable getMaxTerm()

    • getMinTerm

      public ByteComparable getMinTerm()

    • nodeTypeOrdinal

      protected int nodeTypeOrdinal()
      To be used only in analysis.

    • nodeSize

      protected int nodeSize()
      To be used only in analysis.

    • dumpTrie

      public void dumpTrie(PrintStream out, Walker.PayloadToString payloadReader, Version version) throws IOException
      Throws:
      IOException

    • toString

      public String toString()
      Overrides:
      toString in class Object