Package org.apache.orc.impl

Class StringRedBlackTree

java.lang.Object
org.apache.orc.impl.StringRedBlackTree
All Implemented Interfaces:
Dictionary
public class StringRedBlackTree extends Object implements Dictionary
A red-black tree that stores strings. The strings are stored as UTF-8 bytes and an offset for each entry.

  • Nested Class Summary

    Nested classes/interfaces inherited from interface org.apache.orc.impl.Dictionary

    Dictionary.IMPL, Dictionary.Visitor, Dictionary.VisitorContext

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    protected int
    lastAdd
     
    static final int
    NULL
     
    protected int
    root
     
    protected int
    size
     

    Fields inherited from interface org.apache.orc.impl.Dictionary

    INITIAL_DICTIONARY_SIZE

  • Constructor Summary

    Constructors
    Constructor
    Description
    StringRedBlackTree(int initialCapacity)
     

  • Method Summary

    Modifier and Type
    Method
    Description
    protected boolean
    add()
    Add the new key to the tree.
    int
    add(byte[] bytes, int offset, int length)
     
    int
    add(String value)
     
    int
    add(Text value)
     
    void
    clear()
    Reset the table to empty.
    protected int
    compareValue(int position)
    Compare the value at the given position to the new value.
    int
    getCharacterSize()
    Get the size of the character data in the table.
    protected int
    getLeft(int position)
    Get the left field of the given position.
    protected int
    getRight(int position)
    Get the right field of the given position.
    long
    getSizeInBytes()
    Calculate the approximate size in memory.
    ByteBuffer
    getText(int positionInKeyOffset)
     
    void
    getText(Text result, int originalPosition)
    Given the position index, return the original string before being encoded.
    protected boolean
    isRed(int position)
    Is the given node red as opposed to black? To prevent having an extra word in the data array, we just the low bit on the left child index.
    int
    size()
    Get the number of elements in the set.
    void
    visit(Dictionary.Visitor visitor)
    Visit all of the nodes in the tree in sorted order.
    int
    writeTo(OutputStream out, int position)
    Given the position index, write the original string, before being encoded, to the OutputStream.

    Methods inherited from class java.lang.Object

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

    Methods inherited from interface org.apache.orc.impl.Dictionary

    size

  • Field Details

    • NULL

      public static final int NULL
      See Also:

    • size

      protected int size

    • root

      protected int root

    • lastAdd

      protected int lastAdd

  • Constructor Details

    • StringRedBlackTree

      public StringRedBlackTree(int initialCapacity)

  • Method Details

    • add

      public int add(String value)

    • add

      public int add(Text value)

    • add

      public int add(byte[] bytes, int offset, int length)
      Specified by:
      add in interface Dictionary

    • compareValue

      protected int compareValue(int position)
      Compare the value at the given position to the new value.
      Returns:
      0 if the values are the same, -1 if the new value is smaller and 1 if the new value is larger.

    • visit

      public void visit(Dictionary.Visitor visitor) throws IOException
      Visit all of the nodes in the tree in sorted order.
      Specified by:
      visit in interface Dictionary
      Parameters:
      visitor - the action to be applied to each node
      Throws:
      IOException

    • clear

      public void clear()
      Reset the table to empty.
      Specified by:
      clear in interface Dictionary

    • getText

      public void getText(Text result, int originalPosition)
      Description copied from interface: Dictionary
      Given the position index, return the original string before being encoded. The value of the Text in the Dictionary is copied into result.
      Specified by:
      getText in interface Dictionary
      Parameters:
      result - the holder to copy the dictionary text into
      originalPosition - the position where the key was added

    • getText

      public ByteBuffer getText(int positionInKeyOffset)
      Specified by:
      getText in interface Dictionary

    • writeTo

      public int writeTo(OutputStream out, int position) throws IOException
      Description copied from interface: Dictionary
      Given the position index, write the original string, before being encoded, to the OutputStream.
      Specified by:
      writeTo in interface Dictionary
      Parameters:
      out - the output stream to which to write the data
      position - the position where the key was originally added
      Returns:
      the number of byte written to the stream
      Throws:
      IOException - if an I/O error occurs

    • getCharacterSize

      public int getCharacterSize()
      Get the size of the character data in the table.
      Returns:
      the bytes used by the table

    • getSizeInBytes

      public long getSizeInBytes()
      Calculate the approximate size in memory.
      Specified by:
      getSizeInBytes in interface Dictionary
      Returns:
      the number of bytes used in storing the tree.

    • isRed

      protected boolean isRed(int position)
      Is the given node red as opposed to black? To prevent having an extra word in the data array, we just the low bit on the left child index.

    • getLeft

      protected int getLeft(int position)
      Get the left field of the given position.

    • getRight

      protected int getRight(int position)
      Get the right field of the given position.

    • add

      protected boolean add()
      Add the new key to the tree.
      Returns:
      true if the element is a new one.

    • size

      public int size()
      Get the number of elements in the set.