Class ConcurrentRadixTree<O>

java.lang.Object
com.googlecode.concurrenttrees.radix.ConcurrentRadixTree<O>
All Implemented Interfaces:
PrettyPrintable, RadixTree<O>, Serializable
public class ConcurrentRadixTree<O> extends Object implements RadixTree<O>, PrettyPrintable, Serializable
An implementation of RadixTree which supports lock-free concurrent reads, and allows items to be added to and to be removed from the tree atomically by background thread(s), without blocking reads.

Unlike reads, writes require locking of the tree (locking out other writing threads only; reading threads are never blocked). Currently write locks are coarse-grained; in fact they are tree-level. In future branch-level write locks might be added, but the current implementation is targeted at high concurrency read-mostly use cases.

Author:
Niall Gallagher
See Also:

  • Field Details

    • root

      protected volatile Node root

  • Constructor Details

    • ConcurrentRadixTree

      public ConcurrentRadixTree(NodeFactory nodeFactory)
      Creates a new ConcurrentRadixTree which will use the given NodeFactory to create nodes.
      Parameters:
      nodeFactory - An object which creates Node objects on-demand, and which might return node implementations optimized for storing the values supplied to it for the creation of each node

  • Method Details

    • acquireWriteLock

      protected void acquireWriteLock()

    • releaseWriteLock

      protected void releaseWriteLock()

    • put

      public O put(CharSequence key, O value)
      Associates the given value with the given key; replacing any previous value associated with the key. Returns the previous value associated with the key, if any.

      This operation is performed atomically.

      Specified by:
      put in interface RadixTree<O>
      Parameters:
      key - The key with which the specified value should be associated
      value - The value to associate with the key, which cannot be null
      Returns:
      The previous value associated with the key, if there was one, otherwise null

    • putIfAbsent

      public O putIfAbsent(CharSequence key, O value)
      If a value is not already associated with the given key in the tree, associates the given value with the key; otherwise if an existing value is already associated, returns the existing value and does not overwrite it.

      This operation is performed atomically.

      Specified by:
      putIfAbsent in interface RadixTree<O>
      Parameters:
      key - The key with which the specified value should be associated
      value - The value to associate with the key, which cannot be null
      Returns:
      The existing value associated with the key, if there was one; otherwise null in which case the new value was successfully associated

    • getValueForExactKey

      public O getValueForExactKey(CharSequence key)
      Returns the value associated with the given key (exact match), or returns null if no such value is associated with the key.
      Specified by:
      getValueForExactKey in interface RadixTree<O>
      Parameters:
      key - The key with which a sought value might be associated
      Returns:
      The value associated with the given key (exact match), or null if no value was associated with the key

    • getKeysStartingWith

      public Iterable<CharSequence> getKeysStartingWith(CharSequence prefix)
      Returns a lazy iterable which returns the set of keys in the tree which start with the given prefix.

      This is inclusive - if the given prefix is an exact match for a key in the tree, that key is also returned.

      Specified by:
      getKeysStartingWith in interface RadixTree<O>
      Parameters:
      prefix - A prefix of sought keys in the tree
      Returns:
      The set of keys in the tree which start with the given prefix, inclusive

    • getValuesForKeysStartingWith

      public Iterable<O> getValuesForKeysStartingWith(CharSequence prefix)
      Returns a lazy iterable which returns the set of values associated with keys in the tree which start with the given prefix.

      This is inclusive - if the given prefix is an exact match for a key in the tree, the value associated with that key is also returned.

      Note that although the same value might originally have been associated with multiple keys, the set returned does not contain duplicates (as determined by the value objects' implementation of Object.equals(Object)).

      Specified by:
      getValuesForKeysStartingWith in interface RadixTree<O>
      Parameters:
      prefix - A prefix of keys in the tree for which associated values are sought
      Returns:
      The set of values associated with keys in the tree which start with the given prefix, inclusive

    • getKeyValuePairsForKeysStartingWith

      public Iterable<KeyValuePair<O>> getKeyValuePairsForKeysStartingWith(CharSequence prefix)
      Returns a lazy iterable which returns the set of KeyValuePairs for keys and their associated values in the tree, where the keys start with the given prefix.

      This is inclusive - if the given prefix is an exact match for a key in the tree, the KeyValuePair for that key is also returned.

      Specified by:
      getKeyValuePairsForKeysStartingWith in interface RadixTree<O>
      Parameters:
      prefix - A prefix of keys in the tree for which associated KeyValuePairs are sought
      Returns:
      The set of KeyValuePairs for keys in the tree which start with the given prefix, inclusive

    • remove

      public boolean remove(CharSequence key)
      Removes the value associated with the given key (exact match). If no value is associated with the key, does nothing.
      Specified by:
      remove in interface RadixTree<O>
      Parameters:
      key - The key for which an associated value should be removed
      Returns:
      True if a value was removed (and therefore was associated with the key), false if no value was associated/removed

    • getClosestKeys

      public Iterable<CharSequence> getClosestKeys(CharSequence candidate)
      Returns a lazy iterable which returns the set of keys in the tree which are the closest match for the given candidate key.

      Example:
      Tree contains: Ford Focus, Ford Mondeo, BMW M3
      getClosestKeys("Ford F150") -> returns Ford Focus, Ford Mondeo

      This is inclusive - if the given candidate is an exact match for a key in the tree, that key is also returned.

      Specified by:
      getClosestKeys in interface RadixTree<O>
      Parameters:
      candidate - A candidate key
      Returns:
      The set of keys in the tree which most closely match the candidate key, inclusive

    • getValuesForClosestKeys

      public Iterable<O> getValuesForClosestKeys(CharSequence candidate)
      Returns a lazy iterable which returns the set of values associated with keys in the tree which are the closest match for the given candidate key.

      See {#getClosestKeys} for more details.

      Specified by:
      getValuesForClosestKeys in interface RadixTree<O>
      Parameters:
      candidate - A candidate key
      Returns:
      The set of values associated with keys in the tree which most closely match the candidate key, inclusive

    • getKeyValuePairsForClosestKeys

      public Iterable<KeyValuePair<O>> getKeyValuePairsForClosestKeys(CharSequence candidate)
      Returns a lazy iterable which returns the set of KeyValuePairs for keys and their associated values in the tree which are the closest match for the given candidate key.

      See {#getClosestKeys} for more details.

      Specified by:
      getKeyValuePairsForClosestKeys in interface RadixTree<O>
      Parameters:
      candidate - A candidate key
      Returns:
      The set of KeyValuePairs for keys and their associated values in the tree which most closely match the candidate key, inclusive

    • size

      public int size()
      Counts the number of keys/values stored in the tree.

      In the current implementation, this is an expensive operation, having O(n) time complexity.

      Specified by:
      size in interface RadixTree<O>
      Returns:
      The number of keys/values stored in the tree

    • lazyTraverseDescendants

      protected Iterable<ConcurrentRadixTree.NodeKeyPair> lazyTraverseDescendants(CharSequence startKey, Node startNode)
      Traverses the tree using depth-first, preordered traversal, starting at the given node, using lazy evaluation such that the next node is only determined when next() is called on the iterator returned. The traversal algorithm uses iteration instead of recursion to allow deep trees to be traversed without requiring large JVM stack sizes.

      Each node that is encountered is returned from the iterator along with a key associated with that node, in a NodeKeyPair object. The key will be prefixed by the given start key, and will be generated by appending to the start key the edges traversed along the path to that node from the start node.

      Parameters:
      startKey - The key which matches the given start node
      startNode - The start node
      Returns:
      An iterator which when iterated traverses the tree using depth-first, preordered traversal, starting at the given start node

    • transformKeyForResult

      protected CharSequence transformKeyForResult(CharSequence rawKey)
      A hook method which may be overridden by subclasses, to transform a key just before it is returned to the application, for example by the getKeysStartingWith(CharSequence) or the getKeyValuePairsForKeysStartingWith(CharSequence) methods.

      This hook is expected to be used by ReversedRadixTree implementations, where keys are stored in the tree in reverse order but results should be returned in normal order.

      This default implementation simply returns the given key unmodified.

      Parameters:
      rawKey - The raw key as stored in the tree
      Returns:
      A transformed version of the key

    • getNode

      public Node getNode()
      Specified by:
      getNode in interface PrettyPrintable