Class Art

java.lang.Object
org.roaringbitmap.art.Art

public class Art extends Object
See: https://db.in.tum.de/~leis/papers/ART.pdf a cpu cache friendly main memory data structure. At our case, the LeafNode's key is always 48 bit size. The high 48 bit keys here are compared using the byte dictionary comparison.
  • Field Details

    • root

      private Node root
    • keySize

      private long keySize
    • EMPTY_BYTES

      private static byte[] EMPTY_BYTES
  • Constructor Details

    • Art

      public Art()
  • Method Details

    • isEmpty

      public boolean isEmpty()
    • insert

      public void insert(byte[] key, long containerIdx)
      insert the 48 bit key and the corresponding containerIdx
      Parameters:
      key - the high 48 bit of the long data
      containerIdx - the container index
    • findByKey

      public long findByKey(byte[] key)
      Parameters:
      key - the high 48 bit of the long data
      Returns:
      the key's corresponding containerIdx
    • findByKey

      private Node findByKey(Node node, byte[] key, int depth)
    • iterator

      public KeyIterator iterator(Containers containers)
      a convenient method to traverse the key space in ascending order.
      Parameters:
      containers - input containers
      Returns:
      the key iterator
    • remove

      public long remove(byte[] key)
      remove the key from the art if it's there.
      Parameters:
      key - the high 48 bit key
      Returns:
      the corresponding containerIdx or -1 indicating not exist
    • removeSpecifyKey

      protected Art.Toolkit removeSpecifyKey(Node node, byte[] key, int dep)
    • leafMatch

      private boolean leafMatch(LeafNode leafNode, byte[] key, int dep)
    • insert

      private Node insert(Node node, byte[] key, int depth, long containerIdx)
    • commonPrefixLength

      static int commonPrefixLength(byte[] key1, int aFromIndex, int aToIndex, byte[] key2, int bFromIndex, int bToIndex)
    • getRoot

      public Node getRoot()
    • getExtremeLeaf

      private LeafNode getExtremeLeaf(boolean reverse)
    • first

      public LeafNode first()
    • last

      public LeafNode last()
    • serializeArt

      public void serializeArt(DataOutput dataOutput) throws IOException
      Throws:
      IOException
    • deserializeArt

      public void deserializeArt(DataInput dataInput) throws IOException
      Throws:
      IOException
    • serializeArt

      public void serializeArt(ByteBuffer byteBuffer) throws IOException
      Throws:
      IOException
    • deserializeArt

      public void deserializeArt(ByteBuffer byteBuffer) throws IOException
      Throws:
      IOException
    • leafNodeIterator

      public LeafNodeIterator leafNodeIterator(boolean reverse, Containers containers)
    • leafNodeIteratorFrom

      public LeafNodeIterator leafNodeIteratorFrom(long bound, boolean reverse, Containers containers)
    • serialize

      private void serialize(Node node, DataOutput dataOutput) throws IOException
      Throws:
      IOException
    • serialize

      private void serialize(Node node, ByteBuffer byteBuffer) throws IOException
      Throws:
      IOException
    • deserialize

      private Node deserialize(DataInput dataInput) throws IOException
      Throws:
      IOException
    • deserialize

      private Node deserialize(ByteBuffer byteBuffer) throws IOException
      Throws:
      IOException
    • serializeSizeInBytes

      public long serializeSizeInBytes()
    • getKeySize

      public long getKeySize()
    • serializeSizeInBytes

      private long serializeSizeInBytes(Node node)