public class ConcurrentRadixTree<O> extends Object implements RadixTree<O>, PrettyPrintable, Serializable
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.Modifier and Type | Class and Description |
---|---|
static class |
ConcurrentRadixTree.KeyValuePairImpl<O>
Implementation of the
KeyValuePair interface. |
protected static class |
ConcurrentRadixTree.NodeKeyPair
Encapsulates a node and its associated key.
|
Constructor and Description |
---|
ConcurrentRadixTree(NodeFactory nodeFactory)
Creates a new
ConcurrentRadixTree which will use the given NodeFactory to create nodes. |
ConcurrentRadixTree(NodeFactory nodeFactory,
boolean restrictConcurrency)
Creates a new
ConcurrentRadixTree which will use the given NodeFactory to create nodes. |
Modifier and Type | Method and Description |
---|---|
protected void |
acquireReadLockIfNecessary() |
protected void |
acquireWriteLock() |
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.
|
Iterable<CharSequence> |
getKeysStartingWith(CharSequence prefix)
Returns a lazy iterable which returns the set of keys in the tree which start with the given prefix.
|
Iterable<KeyValuePair<O>> |
getKeyValuePairsForClosestKeys(CharSequence candidate)
Returns a lazy iterable which returns the set of
KeyValuePair s for keys and their associated values in
the tree which are the closest match for the given candidate key. |
Iterable<KeyValuePair<O>> |
getKeyValuePairsForKeysStartingWith(CharSequence prefix)
Returns a lazy iterable which returns the set of
KeyValuePair s for keys and their associated values
in the tree, where the keys start with the given prefix. |
Node |
getNode() |
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.
|
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.
|
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.
|
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.
|
O |
put(CharSequence key,
O value)
Associates the given value with the given key; replacing any previous value associated with the key.
|
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.
|
protected void |
releaseReadLockIfNecessary() |
protected void |
releaseWriteLock() |
boolean |
remove(CharSequence key)
Removes the value associated with the given key (exact match).
|
int |
size()
Counts the number of keys/values stored in the tree.
|
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. |
protected volatile Node root
public ConcurrentRadixTree(NodeFactory nodeFactory)
ConcurrentRadixTree
which will use the given NodeFactory
to create nodes.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 nodepublic ConcurrentRadixTree(NodeFactory nodeFactory, boolean restrictConcurrency)
ConcurrentRadixTree
which will use the given NodeFactory
to create nodes.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 noderestrictConcurrency
- If true, configures use of a ReadWriteLock
allowing
concurrent reads, except when writes are being performed by other threads, in which case writes block all reads;
if false, configures lock-free reads; allows concurrent non-blocking reads, even if writes are being performed
by other threadsprotected void acquireWriteLock()
protected void releaseWriteLock()
protected void acquireReadLockIfNecessary()
protected void releaseReadLockIfNecessary()
public O put(CharSequence key, O value)
public O putIfAbsent(CharSequence key, O value)
putIfAbsent
in interface RadixTree<O>
key
- The key with which the specified value should be associatedvalue
- The value to associate with the key, which cannot be nullpublic O getValueForExactKey(CharSequence key)
getValueForExactKey
in interface RadixTree<O>
key
- The key with which a sought value might be associatedpublic Iterable<CharSequence> getKeysStartingWith(CharSequence prefix)
getKeysStartingWith
in interface RadixTree<O>
prefix
- A prefix of sought keys in the treepublic Iterable<O> getValuesForKeysStartingWith(CharSequence prefix)
#equals(Object)
).getValuesForKeysStartingWith
in interface RadixTree<O>
prefix
- A prefix of keys in the tree for which associated values are soughtpublic Iterable<KeyValuePair<O>> getKeyValuePairsForKeysStartingWith(CharSequence prefix)
KeyValuePair
s 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.getKeyValuePairsForKeysStartingWith
in interface RadixTree<O>
prefix
- A prefix of keys in the tree for which associated KeyValuePair
s are soughtKeyValuePair
s for keys in the tree which start with the given prefix, inclusivepublic boolean remove(CharSequence key)
public Iterable<CharSequence> getClosestKeys(CharSequence candidate)
Ford Focus
, Ford Mondeo
, BMW M3
getClosestKeys("Ford F150")
-> returns Ford Focus
, Ford Mondeo
getClosestKeys
in interface RadixTree<O>
candidate
- A candidate keypublic Iterable<O> getValuesForClosestKeys(CharSequence candidate)
getValuesForClosestKeys
in interface RadixTree<O>
candidate
- A candidate keypublic Iterable<KeyValuePair<O>> getKeyValuePairsForClosestKeys(CharSequence candidate)
KeyValuePair
s for keys and their associated values in
the tree which are the closest match for the given candidate key.
See {#getClosestKeys} for more details.getKeyValuePairsForClosestKeys
in interface RadixTree<O>
candidate
- A candidate keyKeyValuePair
s for keys and their associated values in the tree which most closely
match the candidate key, inclusivepublic int size()
protected Iterable<ConcurrentRadixTree.NodeKeyPair> lazyTraverseDescendants(CharSequence startKey, Node startNode)
startKey
- The key which matches the given start nodestartNode
- The start nodeprotected CharSequence transformKeyForResult(CharSequence rawKey)
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.rawKey
- The raw key as stored in the treepublic Node getNode()
getNode
in interface PrettyPrintable
Copyright © 2017. All Rights Reserved.