Package org.apache.cassandra.db.tries

Class InMemoryTrie<T>

java.lang.Object
org.apache.cassandra.db.tries.Trie<T>
org.apache.cassandra.db.tries.InMemoryReadTrie<T>
org.apache.cassandra.db.tries.InMemoryTrie<T>
public class InMemoryTrie<T> extends InMemoryReadTrie<T>
In-memory trie built for fast modification and reads executing concurrently with writes from a single mutator thread. This class can currently only provide atomicity (i.e. reads seeing either the content before a write, or the content after it; any read seeing the write enforcing any subsequent (i.e. started after it completed) reads to also see it) for singleton writes (i.e. calls to putRecursive(org.apache.cassandra.utils.bytecomparable.ByteComparable, R, org.apache.cassandra.db.tries.InMemoryTrie.UpsertTransformer<T, R>), putSingleton(org.apache.cassandra.utils.bytecomparable.ByteComparable, R, org.apache.cassandra.db.tries.InMemoryTrie.UpsertTransformer<T, ? super R>) or apply(org.apache.cassandra.db.tries.Trie<U>, org.apache.cassandra.db.tries.InMemoryTrie.UpsertTransformer<T, U>) with a singleton trie as argument). Because it uses 32-bit pointers in byte buffers, this trie has a fixed size limit of 2GB.

  • Constructor Details

    • InMemoryTrie

      public InMemoryTrie(BufferType bufferType)

  • Method Details

    • discardBuffers

      public void discardBuffers()

    • apply

      public <U> void apply(Trie<U> mutation, InMemoryTrie.UpsertTransformer<T,U> transformer) throws InMemoryTrie.SpaceExhaustedException
      Modify this trie to apply the mutation given in the form of a trie. Any content in the mutation will be resolved with the given function before being placed in this trie (even if there's no pre-existing content in this trie).
      Parameters:
      mutation - the mutation to be applied, given in the form of a trie. Note that its content can be of type different than the element type for this memtable trie.
      transformer - a function applied to the potentially pre-existing value for the given key, and the new value. Applied even if there's no pre-existing value in the memtable trie.
      Throws:
      InMemoryTrie.SpaceExhaustedException

    • putSingleton

      public <R> void putSingleton(ByteComparable key, R value, InMemoryTrie.UpsertTransformer<T,? super R> transformer) throws InMemoryTrie.SpaceExhaustedException
      Map-like put method, using the apply machinery above which cannot run into stack overflow. When the correct position in the trie has been reached, the value will be resolved with the given function before being placed in the trie (even if there's no pre-existing content in this trie).
      Parameters:
      key - the trie path/key for the given value.
      value - the value being put in the memtable trie. Note that it can be of type different than the element type for this memtable trie. It's up to the transformer to return the final value that will stay in the memtable trie.
      transformer - a function applied to the potentially pre-existing value for the given key, and the new value (of a potentially different type), returning the final value that will stay in the memtable trie. Applied even if there's no pre-existing value in the memtable trie.
      Throws:
      InMemoryTrie.SpaceExhaustedException

    • putSingleton

      public <R> void putSingleton(ByteComparable key, R value, InMemoryTrie.UpsertTransformer<T,? super R> transformer, boolean useRecursive) throws InMemoryTrie.SpaceExhaustedException
      A version of putSingleton which uses recursive put if the last argument is true.
      Throws:
      InMemoryTrie.SpaceExhaustedException

    • putRecursive

      public <R> void putRecursive(ByteComparable key, R value, InMemoryTrie.UpsertTransformer<T,R> transformer) throws InMemoryTrie.SpaceExhaustedException
      Map-like put method, using a fast recursive implementation through the key bytes. May run into stack overflow if the trie becomes too deep. When the correct position in the trie has been reached, the value will be resolved with the given function before being placed in the trie (even if there's no pre-existing content in this trie).
      Parameters:
      key - the trie path/key for the given value.
      value - the value being put in the memtable trie. Note that it can be of type different than the element type for this memtable trie. It's up to the transformer to return the final value that will stay in the memtable trie.
      transformer - a function applied to the potentially pre-existing value for the given key, and the new value (of a potentially different type), returning the final value that will stay in the memtable trie. Applied even if there's no pre-existing value in the memtable trie.
      Throws:
      InMemoryTrie.SpaceExhaustedException

    • reachedAllocatedSizeThreshold

      public boolean reachedAllocatedSizeThreshold()
      Returns true if the allocation threshold has been reached. To be called by the the writing thread (ideally, just after the write completes). When this returns true, the user should switch to a new trie as soon as feasible. The trie expects up to 10% growth above this threshold. Any growth beyond that may be done inefficiently, and the trie will fail altogether when the size grows beyond 2G - 256 bytes.

    • sizeOffHeap

      public long sizeOffHeap()
      Returns the off heap size of the memtable trie itself, not counting any space taken by referenced content.

    • sizeOnHeap

      public long sizeOnHeap()
      Returns the on heap size of the memtable trie itself, not counting any space taken by referenced content.

    • valuesUnordered

      public Iterable<T> valuesUnordered()
      Description copied from class: Trie
      Returns the values in any order. For some tries this is much faster than the ordered iterable.
      Overrides:
      valuesUnordered in class Trie<T>

    • valuesCount

      public int valuesCount()

    • unusedReservedMemory

      public long unusedReservedMemory()