Package org.roaringbitmap.art
Class Art
- java.lang.Object
-
- org.roaringbitmap.art.Art
-
public class Art extends java.lang.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.
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description (package private) class
Art.Toolkit
-
Field Summary
Fields Modifier and Type Field Description private static byte[]
EMPTY_BYTES
private long
keySize
private Node
root
-
Constructor Summary
Constructors Constructor Description Art()
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description (package private) static int
commonPrefixLength(byte[] key1, int aFromIndex, int aToIndex, byte[] key2, int bFromIndex, int bToIndex)
private Node
deserialize(java.io.DataInput dataInput)
private Node
deserialize(java.nio.ByteBuffer byteBuffer)
void
deserializeArt(java.io.DataInput dataInput)
void
deserializeArt(java.nio.ByteBuffer byteBuffer)
long
findByKey(byte[] key)
private Node
findByKey(Node node, byte[] key, int depth)
LeafNode
first()
private LeafNode
getExtremeLeaf(boolean reverse)
long
getKeySize()
Node
getRoot()
void
insert(byte[] key, long containerIdx)
insert the 48 bit key and the corresponding containerIdxprivate Node
insert(Node node, byte[] key, int depth, long containerIdx)
boolean
isEmpty()
KeyIterator
iterator(Containers containers)
a convenient method to traverse the key space in ascending order.LeafNode
last()
private boolean
leafMatch(LeafNode leafNode, byte[] key, int dep)
LeafNodeIterator
leafNodeIterator(boolean reverse, Containers containers)
LeafNodeIterator
leafNodeIteratorFrom(long bound, boolean reverse, Containers containers)
long
remove(byte[] key)
remove the key from the art if it's there.protected Art.Toolkit
removeSpecifyKey(Node node, byte[] key, int dep)
private void
serialize(Node node, java.io.DataOutput dataOutput)
private void
serialize(Node node, java.nio.ByteBuffer byteBuffer)
void
serializeArt(java.io.DataOutput dataOutput)
void
serializeArt(java.nio.ByteBuffer byteBuffer)
long
serializeSizeInBytes()
private long
serializeSizeInBytes(Node node)
-
-
-
Field Detail
-
root
private Node root
-
keySize
private long keySize
-
EMPTY_BYTES
private static byte[] EMPTY_BYTES
-
-
Method Detail
-
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 datacontainerIdx
- 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
-
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)
-
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(java.io.DataOutput dataOutput) throws java.io.IOException
- Throws:
java.io.IOException
-
deserializeArt
public void deserializeArt(java.io.DataInput dataInput) throws java.io.IOException
- Throws:
java.io.IOException
-
serializeArt
public void serializeArt(java.nio.ByteBuffer byteBuffer) throws java.io.IOException
- Throws:
java.io.IOException
-
deserializeArt
public void deserializeArt(java.nio.ByteBuffer byteBuffer) throws java.io.IOException
- Throws:
java.io.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, java.io.DataOutput dataOutput) throws java.io.IOException
- Throws:
java.io.IOException
-
serialize
private void serialize(Node node, java.nio.ByteBuffer byteBuffer) throws java.io.IOException
- Throws:
java.io.IOException
-
deserialize
private Node deserialize(java.io.DataInput dataInput) throws java.io.IOException
- Throws:
java.io.IOException
-
deserialize
private Node deserialize(java.nio.ByteBuffer byteBuffer) throws java.io.IOException
- Throws:
java.io.IOException
-
serializeSizeInBytes
public long serializeSizeInBytes()
-
getKeySize
public long getKeySize()
-
serializeSizeInBytes
private long serializeSizeInBytes(Node node)
-
-