com.hazelcast.elastic.tree.impl

Class RedBlackTreeStore

java.lang.Object

com.hazelcast.elastic.tree.impl.RedBlackTreeStore

All Implemented Interfaces:

OffHeapTreeStore, Iterable<OffHeapTreeEntry>

public class RedBlackTreeStore
extends Object
implements OffHeapTreeStore

This is a classic Red Black tree implementation using off-heap memory. Every node can hold multiple values in linked-list approach. The algorithm is based on the CLRS book, Introduction to Algorithms.

Constructor Summary

Constructors

Constructor and Description
RedBlackTreeStore(com.hazelcast.internal.memory.MemoryAllocator malloc, OffHeapComparator offHeapKeyComparator)
RedBlackTreeStore(com.hazelcast.internal.memory.MemoryAllocator malloc, OffHeapComparator offHeapKeyComparator, boolean disableConsistencyAssertions)

Method Summary

Modifier and Type	Method and Description
void	dispose(boolean releasePayload) Release of memory (of all keys,values and entries) associated with storage **WARNING** Special attention is required when disposing a tree this way, if NOT empty.
Iterator<OffHeapTreeEntry>	entries()
Iterator<OffHeapTreeEntry>	entries(OffHeapTreeEntry root)
Iterator<OffHeapTreeEntry>	entries(OffHeapTreeEntry entry, OrderingDirection direction)
Iterator<OffHeapTreeEntry>	entries(OrderingDirection direction)
OffHeapTreeEntry	getEntry(com.hazelcast.internal.serialization.impl.HeapData key) Looking for key equal to blob;
OffHeapTreeEntry	getEntry(MemoryBlock key) Looking for key equal to blob;
OffHeapTreeEntry	getEntry(MemoryBlock key, OffHeapComparator comparator) Looking for key equal to blob using the given comparator; In case if not-found - if createIfNotExists==true - create new key entry; if createIfNotExists==false - don't create new key entry - return null;
Iterator<OffHeapTreeEntry>	iterator()
OffHeapTreeEntry	put(MemoryBlock key, MemoryBlock value) Looking for key equal to blob; In case if found - append value represented by value to the chain of key's values; In case if not-found - adds new key to the corresponding place in the tree and assign value to this 'new' key;
OffHeapTreeEntry	put(MemoryBlock key, MemoryBlock value, OffHeapComparator comparator)
void	remove(OffHeapTreeEntry entry) Removes the entry from the tree and disposes used space associated with that entry including Key and Value blobs.
OffHeapTreeEntry	searchEntry(MemoryBlock key) Looking for key equal or closest to blob;

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Constructor Detail

RedBlackTreeStore

public RedBlackTreeStore(com.hazelcast.internal.memory.MemoryAllocator malloc,
                         OffHeapComparator offHeapKeyComparator)

RedBlackTreeStore

public RedBlackTreeStore(com.hazelcast.internal.memory.MemoryAllocator malloc,
                         OffHeapComparator offHeapKeyComparator,
                         boolean disableConsistencyAssertions)

Method Detail

put

public OffHeapTreeEntry put(MemoryBlock key,
                            MemoryBlock value)

Description copied from interface: OffHeapTreeStore

Looking for key equal to blob; In case if found - append value represented by value to the chain of key's values;

In case if not-found - adds new key to the corresponding place in the tree and assign value to this 'new' key;

Specified by:

put in interface OffHeapTreeStore

Parameters:

key - - The key blob;

value - - The value blob;

Returns:

The Entry associated with the key;

put

public OffHeapTreeEntry put(MemoryBlock key,
                            MemoryBlock value,
                            OffHeapComparator comparator)

getEntry

public OffHeapTreeEntry getEntry(MemoryBlock key)

Description copied from interface: OffHeapTreeStore

Looking for key equal to blob;

Specified by:

getEntry in interface OffHeapTreeStore

Parameters:

key - - The key blob;

Returns:

The Entry associated with the key or null if not found

getEntry

public OffHeapTreeEntry getEntry(com.hazelcast.internal.serialization.impl.HeapData key)

Description copied from interface: OffHeapTreeStore

Looking for key equal to blob;

Specified by:

getEntry in interface OffHeapTreeStore

Parameters:

key - - The key blob;

Returns:

The Entry associated with the key or null if not found

getEntry

public OffHeapTreeEntry getEntry(MemoryBlock key,
                                 OffHeapComparator comparator)

Description copied from interface: OffHeapTreeStore

Looking for key equal to blob using the given comparator; In case if not-found - if createIfNotExists==true - create new key entry; if createIfNotExists==false - don't create new key entry - return null;

Specified by:

getEntry in interface OffHeapTreeStore

Parameters:

key - - The key blob;

comparator - - comparator to be used, if null default passed in constructor will be used

Returns:

address of the key entry

searchEntry

public OffHeapTreeEntry searchEntry(MemoryBlock key)

Description copied from interface: OffHeapTreeStore

Looking for key equal or closest to blob;

Specified by:

searchEntry in interface OffHeapTreeStore

Parameters:

key - - The key blob;

Returns:

address of the key entry equal od closest to, or zero address if map empty

dispose

public void dispose(boolean releasePayload)

Description copied from interface: OffHeapTreeStore

Release of memory (of all keys,values and entries) associated with storage **WARNING** Special attention is required when disposing a tree this way, if NOT empty. When a tree contains duplicate values, either on the same entry or different ones, this can cause the VM to crash when free'ing the same address twice. The safe way is to always dispose the entries one by one, and the key/values should be disposed by their original owner.

Specified by:

dispose in interface OffHeapTreeStore

remove

public void remove(OffHeapTreeEntry entry)

Description copied from interface: OffHeapTreeStore

Removes the entry from the tree and disposes used space associated with that entry including Key and Value blobs. All resources associated with the entry will be disposed, however the actual Entry (Key & Value(s)) are assumed to be managed by their owners, therefore no attempt is made to dispose them. To release their resources, first fetch them with OffHeapTreeStore.getEntry(MemoryBlock) and dispose the allocated chunks on the addresses of the returned Entry Key & Values. Eg.

 OffHeapTreeEntry entry = getEntry(...);
 dispose(entry.getKey());
 for (MemoryBlock value : entry) {
     dispose(value);
 }
 remove(entry);
 

Specified by:

remove in interface OffHeapTreeStore

Parameters:

entry - The tree entry to be removed

iterator

public Iterator<OffHeapTreeEntry> iterator()

Specified by:

iterator in interface Iterable<OffHeapTreeEntry>

entries

public Iterator<OffHeapTreeEntry> entries()

Specified by:

entries in interface OffHeapTreeStore

Returns:

iterate over keys of the store from root in ascending order

entries

public Iterator<OffHeapTreeEntry> entries(OrderingDirection direction)

Specified by:

entries in interface OffHeapTreeStore

Returns:

iterate over keys of the store from root with the given direction

entries

public Iterator<OffHeapTreeEntry> entries(OffHeapTreeEntry root)

Specified by:

entries in interface OffHeapTreeStore

Returns:

iterate over keys of the store from entry

entries

public Iterator<OffHeapTreeEntry> entries(OffHeapTreeEntry entry,
                                          OrderingDirection direction)

Specified by:

entries in interface OffHeapTreeStore

Returns:

iterate over keys of the store from the entry with the given direction