Package com.tangosol.util

Class BinaryRadixTree

java.lang.Object
com.tangosol.util.BinaryRadixTree
All Implemented Interfaces:
BinaryLongMap
public class BinaryRadixTree extends Object implements BinaryLongMap
A BinaryRadixTree is a memory-optimized radix tree (aka a Patricia trie) that is intended to efficiently store a mapping from Binary values to long values. The BinaryRadixTree is not thread safe; to make it safe in a multi-threaded scenario, access must be synchronized and the Iterators returned from the BinaryRadixTree can only be used within the scope of synchronization within which they were obtained.
Since:
Coherence 3.7
Author:
cp 2010-06-06

  • Nested Class Summary

    Nested classes/interfaces inherited from interface com.tangosol.util.BinaryLongMap

    BinaryLongMap.Entry, BinaryLongMap.EntryVisitor, BinaryLongMap.SimpleMapImpl

  • Constructor Summary

    Constructors
    Constructor
    Description
    BinaryRadixTree()
    Construct an empty BinaryRadixTree.

  • Method Summary

    Modifier and Type
    Method
    Description
    void
    clear()
    Initialize the map to an empty state.
    long
    get(Binary binKey)
    Find the specified key in the map and return the value associated with it.
    void
    internKeys(Object o)
    Internal opaque method: De-duplicate keys.
    Iterator<Binary>
    keys()
    Obtain an iterator of the keys stored in the map.
    Iterator<Binary>
    keys(Predicate<BinaryLongMap.Entry> predicate)
    Obtain an iterator of the keys stored in the map whose corresponding Entry matches the passed Predicate<Entry>.
    void
    put(Binary binKey, long lValue)
    Blindly store the passed value for the specified key, adding the key if it is not already in the map, or replacing the current value if the key is in the map.
    boolean
    putIfAbsent(Binary binKey, long lValue)
    Store the passed value for the specified key, only if the key does not currently exist in the map.
    void
    remove(Binary binKey)
    Blindly remove the specified Binary key from the map.
    boolean
    remove(Binary binKey, long lValue)
    Remove the specified Binary key from the map iff it exists in the map and is associated with the specified value.
    boolean
    replace(Binary binKey, long lValueOld, long lValueNew)
    Store the passed "new" value for the specified key, only if the current value associated with the specified key is the same as the specified "old" value.
    int
    size()
    Determine the size of the map.
    protected long
    sizeof()
    Return the number of bytes retained by this BinaryLongMap.
    void
    visit(Binary binKey, BinaryLongMap.EntryVisitor visitor)
    Apply the specified visitor to the entry associated with the specified key, if the entry exists or may be added.
    void
    visitAll(BinaryLongMap.EntryVisitor visitor)
    Apply the specified visitor to all entries in the BinaryLongMap.

    Methods inherited from class java.lang.Object

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

  • Constructor Details

    • BinaryRadixTree

      public BinaryRadixTree()
      Construct an empty BinaryRadixTree.

  • Method Details

    • get

      public long get(Binary binKey)
      Find the specified key in the map and return the value associated with it.
      Specified by:
      get in interface BinaryLongMap
      Parameters:
      binKey - a Binary key
      Returns:
      the value associated with the specified key, or 0L if the specified key is not in the map

    • put

      public void put(Binary binKey, long lValue)
      Blindly store the passed value for the specified key, adding the key if it is not already in the map, or replacing the current value if the key is in the map.

      Note that associating the value zero with a key is analogous to removing the key.

      Specified by:
      put in interface BinaryLongMap
      Parameters:
      binKey - the Binary key to add or update
      lValue - the value to associate with the key

    • putIfAbsent

      public boolean putIfAbsent(Binary binKey, long lValue)
      Store the passed value for the specified key, only if the key does not currently exist in the map.

      Note that associating the value zero with a key using this method will have no effect, since were that key already present, there would be no change, and were it not present, the value zero is analogous to removing the key, which again is no change (since it is not present).

      Specified by:
      putIfAbsent in interface BinaryLongMap
      Parameters:
      binKey - a Binary key
      lValue - the new value to associate with the passed key
      Returns:
      true iff the key was not present in the map, and now it is present in the map associated with the passed value

    • replace

      public boolean replace(Binary binKey, long lValueOld, long lValueNew)
      Store the passed "new" value for the specified key, only if the current value associated with the specified key is the same as the specified "old" value.

      Note that replacing the value of zero is analogous to putIfAbsent, and associating the value zero with a key using this method is the same as remove passing the old value to match.

      Specified by:
      replace in interface BinaryLongMap
      Parameters:
      binKey - a Binary key
      lValueOld - the assumed old value to replace
      lValueNew - the new value to associate with the passed key
      Returns:
      true iff the key was associated with the passed "old" value, and now it is associated with the passed "new" value

    • remove

      public void remove(Binary binKey)
      Blindly remove the specified Binary key from the map.
      Specified by:
      remove in interface BinaryLongMap
      Parameters:
      binKey - a Binary key

    • remove

      public boolean remove(Binary binKey, long lValue)
      Remove the specified Binary key from the map iff it exists in the map and is associated with the specified value.

      Note that removing an association whose value is zero has no effect.

      Specified by:
      remove in interface BinaryLongMap
      Parameters:
      binKey - a Binary key
      lValue - the value that the key must have in order to be removed
      Returns:
      true iff the map contained the key, it was associated with the specified value, and has now been removed

    • clear

      public void clear()
      Initialize the map to an empty state.
      Specified by:
      clear in interface BinaryLongMap

    • size

      public int size()
      Determine the size of the map.
      Specified by:
      size in interface BinaryLongMap
      Returns:
      the number of unique keys stored in the map

    • keys

      public Iterator<Binary> keys()
      Obtain an iterator of the keys stored in the map.
      Specified by:
      keys in interface BinaryLongMap
      Returns:
      an Iterator of Binary keys

    • keys

      public Iterator<Binary> keys(Predicate<BinaryLongMap.Entry> predicate)
      Obtain an iterator of the keys stored in the map whose corresponding Entry matches the passed Predicate<Entry>.

      The entry passed to the predicate should be treated as read-only, and any attempt to modify the entry may have undefined behavior and/or throw an Exception. Modifications to entries should instead be performed using an BinaryLongMap.EntryVisitor via the BinaryLongMap.visit(com.tangosol.util.Binary, com.tangosol.util.BinaryLongMap.EntryVisitor) or BinaryLongMap.visitAll(com.tangosol.util.BinaryLongMap.EntryVisitor) methods.

      Specified by:
      keys in interface BinaryLongMap
      Parameters:
      predicate - a Predicate<Entry> to apply to each Entry
      Returns:
      an Iterator of Binary keys

    • visit

      public void visit(Binary binKey, BinaryLongMap.EntryVisitor visitor)
      Apply the specified visitor to the entry associated with the specified key, if the entry exists or may be added. The visited entry may or may not logically exist in the BinaryLongMap (e.g. it may be associated with a value of 0L) but is guaranteed to be safe to be added or removed (via BinaryLongMap.Entry.setValue(long)).
      Specified by:
      visit in interface BinaryLongMap
      Parameters:
      binKey - the key to visit
      visitor - the visitor to apply

    • visitAll

      public void visitAll(BinaryLongMap.EntryVisitor visitor)
      Apply the specified visitor to all entries in the BinaryLongMap.
      Specified by:
      visitAll in interface BinaryLongMap
      Parameters:
      visitor - the visitor to apply

    • internKeys

      public void internKeys(Object o)
      Internal opaque method: De-duplicate keys.

      To reduce memory footprint, the tree supports de-duplication of byte[] values used internally by the tree. To execute the de-duping process, create an empty byte[][] of a prime size, and pass it to the internKeys() method of each available BinaryRadixTree.

      Do not pre-populate the byte[][] or modify any of its contents.

      Note: This method does not require external synchronization.

      Specified by:
      internKeys in interface BinaryLongMap
      Parameters:
      o - an opaque byte[][] used to accumulate "intern()" byte[] values

    • sizeof

      protected long sizeof()
      Return the number of bytes retained by this BinaryLongMap.
      Returns:
      the number of bytes retained by this BinaryLongMap