Skip navigation links

Oracle® Coherence Java API Reference
Release 3.7.0.0

E18683-01


com.tangosol.util
Class BinaryRadixTree

java.lang.Object
  extended by com.tangosol.util.BinaryRadixTree


public class BinaryRadixTree
extends java.lang.Object

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 by 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
protected  class BinaryRadixTree.AllKeyIterator
          An Iterator that iterates all of the Binary keys in the radix tree.
static class BinaryRadixTree.BinaryLongMap
          A Map of Binary to Long.
protected  class BinaryRadixTree.FilteredIterator
          An Iterator that iterates only the Binary keys in the radix tree whose associated value matches (via some bit-mask) a specified value.
protected  class BinaryRadixTree.KeyIterator
          An Iterator that iterates Binary keys from Nodes.

 

Constructor Summary
BinaryRadixTree()
          Construct an empty BinaryRadixTree.

 

Method Summary
 void clear()
          Initialize the tree to an empty state.
 java.util.Iterator findAll(long lMask, long lValue)
          Obtain an iterator of all of the keys that have values that match the specified value as seen through the passed bit-mask.
 long get(Binary binKey)
          Find the specified key in the tree and return the value associated with it.
 void internKeys(byte[][] aab)
          To reduce memory footprint, the tree supports de-duplication of byte[] values used internally by the tree.
 java.util.Iterator keys()
          Obtain an iterator of the keys stored in the tree.
 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 tree, or replacing the current value if the key is in the tree.
 boolean putIfAbsent(Binary binKey, long lValue)
          Store the passed value for the specified key, only if the key does not currently exist in the tree.
 void remove(Binary binKey)
          Blindly remove the specified Binary key from the tree.
 boolean remove(Binary binKey, long lValue)
          Remove the specified Binary key from the tree iff it exists in the tree 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 tree.

 

Constructor Detail

BinaryRadixTree

public BinaryRadixTree()
Construct an empty BinaryRadixTree.

Method Detail

get

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

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 tree, or replacing the current value if the key is in the tree.

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

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 tree.

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).

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 tree, and now it is present in the tree 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.

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 tree.
Parameters:
binKey - a Binary key

remove

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

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

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

clear

public void clear()
Initialize the tree to an empty state.

size

public int size()
Determine the size of the tree.
Returns:
the number of unique keys stored in the tree

keys

public java.util.Iterator keys()
Obtain an iterator of the keys stored in the tree.
Returns:
an Iterate of Binary keys

findAll

public java.util.Iterator findAll(long lMask,
                                  long lValue)
Obtain an iterator of all of the keys that have values that match the specified value as seen through the passed bit-mask. For each key in the tree associated with a value v, the key is included in the Iterator iff (v & lMask) == (lValue & lMask).
Parameters:
lMask - a long bit-mask value
lValue - a long value to compare to
Returns:
an Iterator of the keys in the tree whose values match the passed value bitmask

internKeys

public void internKeys(byte[][] aab)
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.

Parameters:
aab - an opaque array used to accumulate "intern()" byte[] values

Skip navigation links

Oracle® Coherence Java API Reference
Release 3.7.0.0

E18683-01


Copyright © 2000, 2011, Oracle and/or its affiliates. All rights reserved.