Top Description Inners Fields Constructors Methods
org.eclipse.jgit.internal.storage.memory

public final Class TernarySearchTree<Value>

extends Object
Class Inheritance
Type Parameters
<Value>
type of values in this tree
Imports
java.util.ArrayDeque, .ArrayList, .HashMap, .List, .Map, .Map.Entry, .Queue, java.util.concurrent.atomic.AtomicInteger, java.util.concurrent.locks.ReadWriteLock, .ReentrantReadWriteLock, org.eclipse.jgit.annotations.Nullable, org.eclipse.jgit.internal.JGitText, org.eclipse.jgit.util.StringUtils
A ternary search tree with String keys and generic values. TernarySearchTree is a type of trie (sometimes called a prefix tree) where nodes are arranged in a manner similar to a binary search tree, but with up to three children rather than the binary tree's limit of two. Like other prefix trees, a ternary search tree can be used as an associative map structure with the ability for incremental string search. However, ternary search trees are more space efficient compared to standard prefix trees, at the cost of speed. Keys must not be null or empty. Values cannot be null. This class is thread safe.
Since
6.5

Nested and Inner Type Summary

Modifier and TypeClass and Description
public static interface
TernarySearchTree.Loader<
type of values
Value>

Loader to load key-value pairs to be cached in the tree

private static class
TernarySearchTree.Node<Value>

Field Summary

Modifier and TypeField and Description
private final ReadWriteLock
lock

private TernarySearchTree.Node<Value>
root

private final AtomicInteger
size

private static final char
WILDCARD

Constructor Summary

AccessConstructor and Description
public
TernarySearchTree()

Construct a new ternary search tree

Method Summary

Modifier and TypeMethod and Description
public void
clear()

Remove all key value pairs from this tree

public boolean

Returns:

whether this tree contains this key
contains(String
a key
key)

Check whether this tree contains the given key.

public int

Returns:

number of key-value pairs
delete(Iterable<String>
iterable providing keys of entries to be deleted
delete)

Delete entries

public int

Returns:

number of key-value pairs after the deletion
delete(String
the key
key)

Delete a key-value pair.

private void
findKeysWithPrefix(TernarySearchTree.Node<Value> node, StringBuilder prefix, Queue<String> keys)

private void
findKeysWithPrefix(TernarySearchTree.Node<Value> node, StringBuilder prefix, int i, String pattern, Queue<String> keys)

private void
findValuesWithPrefix(TernarySearchTree.Node<Value> node, StringBuilder prefix, List<Value> values)

private void
findWithPrefix(TernarySearchTree.Node<Value> node, StringBuilder prefix, Map<String, Value> entries)

public Value

Returns:

the value associated to this key
get(String
the key
key)

Get the value associated to a key or null.

private TernarySearchTree.Node<Value>
get(TernarySearchTree.Node<Value> node, String key, int depth)

public Map<String, Value>

Returns:

all entries
getAll()

Get all entries.

public List<Value>

Returns:

all values
getAllValues()

Get all values.

public Iterable<String>

Returns:

all keys
getKeys()

Get all keys.

public Iterable<String>

Returns:

keys matching given pattern.
getKeysMatching(String
search pattern
pattern)

Get keys matching given pattern using '?' as wildcard character.

public Iterable<String>

Returns:

keys starting with given prefix
getKeysWithPrefix(String
key prefix
prefix)

Get keys starting with given prefix

public ReadWriteLock

Returns:

lock guarding read and write access to the cache
getLock()

Get the lock guarding read and write access to the cache.

public List<Value>

Returns:

entries with given prefix
getValuesWithPrefix(String
key prefix
prefix)

Get all values with given key prefix

public Map<String, Value>

Returns:

entries with given prefix
getWithPrefix(String
key prefix
prefix)

Get all entries with given prefix

public int

Returns:

number of key-value pairs after adding the entry
insert(String
the key
key, Value
the value
value)

Insert a key-value pair.

public int

Returns:

number of key-value pairs after adding entries
insert(Map<String, Value>
map of key-value pairs to insert
map)

Insert map of key-value pairs.

private TernarySearchTree.Node<Value>
insert(TernarySearchTree.Node<Value> node, String key, Value val, int depth)

private void
insertImpl(String key, Value value)

public String

Returns:

the key which is the longest prefix of the given query string or null if none exists.
keyLongestPrefixOf(String
the query string
query)

Find the key which is the longest prefix of the given query string.

public int

Returns:

number of key-value pairs
reload(Iterable<Map.Entry<String, Value>>
iterable providing key-value pairs to load
loader)

Reload the tree entries provided by loader

public int

Returns:

number of key-value pairs after replacing finished
replace(Iterable<Map.Entry<String, Value>>
iterable providing key-value pairs to load
loader)

Replace the tree with a new tree containing all entries provided by an iterable

public int

Returns:

number of key value pairs in this trie
size()

Get the number of key value pairs in this trie

private static void
validateKey(String key)

private static <V> void
validateValue(V value)

Inherited from java.lang.Object:
cloneequalsfinalizegetClasshashCodenotifynotifyAlltoStringwaitwaitwait

Field Detail

lockback to summary
private final ReadWriteLock lock
rootback to summary
private TernarySearchTree.Node<Value> root
sizeback to summary
private final AtomicInteger size
WILDCARDback to summary
private static final char WILDCARD

Constructor Detail

TernarySearchTreeback to summary
public TernarySearchTree()

Construct a new ternary search tree

Method Detail

clearback to summary
public void clear()

Remove all key value pairs from this tree

containsback to summary
public boolean contains(String key)

Check whether this tree contains the given key.

Parameters
key:String

a key

Returns:boolean

whether this tree contains this key

deleteback to summary
public int delete(Iterable<String> delete)

Delete entries

Parameters
delete:Iterable<String>

iterable providing keys of entries to be deleted

Returns:int

number of key-value pairs

deleteback to summary
public int delete(String key)

Delete a key-value pair. Does nothing if the key doesn't exist.

Parameters
key:String

the key

Returns:int

number of key-value pairs after the deletion

findKeysWithPrefixback to summary
private void findKeysWithPrefix(TernarySearchTree.Node<Value> node, StringBuilder prefix, Queue<String> keys)
findKeysWithPrefixback to summary
private void findKeysWithPrefix(TernarySearchTree.Node<Value> node, StringBuilder prefix, int i, String pattern, Queue<String> keys)
findValuesWithPrefixback to summary
private void findValuesWithPrefix(TernarySearchTree.Node<Value> node, StringBuilder prefix, List<Value> values)
findWithPrefixback to summary
private void findWithPrefix(TernarySearchTree.Node<Value> node, StringBuilder prefix, Map<String, Value> entries)
getback to summary
public Value get(String key)

Get the value associated to a key or null.

Parameters
key:String

the key

Returns:Value

the value associated to this key

Annotations
@Nullable
getback to summary
private TernarySearchTree.Node<Value> get(TernarySearchTree.Node<Value> node, String key, int depth)
getAllback to summary
public Map<String, Value> getAll()

Get all entries.

Returns:Map<String, Value>

all entries

getAllValuesback to summary
public List<Value> getAllValues()

Get all values.

Returns:List<Value>

all values

getKeysback to summary
public Iterable<String> getKeys()

Get all keys.

Returns:Iterable<String>

all keys

getKeysMatchingback to summary
public Iterable<String> getKeysMatching(String pattern)

Get keys matching given pattern using '?' as wildcard character.

Parameters
pattern:String

search pattern

Returns:Iterable<String>

keys matching given pattern.

getKeysWithPrefixback to summary
public Iterable<String> getKeysWithPrefix(String prefix)

Get keys starting with given prefix

Parameters
prefix:String

key prefix

Returns:Iterable<String>

keys starting with given prefix

getLockback to summary
public ReadWriteLock getLock()

Get the lock guarding read and write access to the cache.

Returns:ReadWriteLock

lock guarding read and write access to the cache

getValuesWithPrefixback to summary
public List<Value> getValuesWithPrefix(String prefix)

Get all values with given key prefix

Parameters
prefix:String

key prefix

Returns:List<Value>

entries with given prefix

getWithPrefixback to summary
public Map<String, Value> getWithPrefix(String prefix)

Get all entries with given prefix

Parameters
prefix:String

key prefix

Returns:Map<String, Value>

entries with given prefix

insertback to summary
public int insert(String key, Value value)

Insert a key-value pair. If the key already exists the old value is overwritten.

Parameters
key:String

the key

value:Value

the value

Returns:int

number of key-value pairs after adding the entry

insertback to summary
public int insert(Map<String, Value> map)

Insert map of key-value pairs. Values of existing keys are overwritten. Use this method to insert multiple key-value pairs.

Parameters
map:Map<String, Value>

map of key-value pairs to insert

Returns:int

number of key-value pairs after adding entries

insertback to summary
private TernarySearchTree.Node<Value> insert(TernarySearchTree.Node<Value> node, String key, Value val, int depth)
insertImplback to summary
private void insertImpl(String key, Value value)
keyLongestPrefixOfback to summary
public String keyLongestPrefixOf(String query)

Find the key which is the longest prefix of the given query string.

Parameters
query:String

the query string

Returns:String

the key which is the longest prefix of the given query string or null if none exists.

Annotations
@Nullable
reloadback to summary
public int reload(Iterable<Map.Entry<String, Value>> loader)

Reload the tree entries provided by loader

Parameters
loader:Iterable<Map.Entry<String, Value>>

iterable providing key-value pairs to load

Returns:int

number of key-value pairs

replaceback to summary
public int replace(Iterable<Map.Entry<String, Value>> loader)

Replace the tree with a new tree containing all entries provided by an iterable

Parameters
loader:Iterable<Map.Entry<String, Value>>

iterable providing key-value pairs to load

Returns:int

number of key-value pairs after replacing finished

sizeback to summary
public int size()

Get the number of key value pairs in this trie

Returns:int

number of key value pairs in this trie

validateKeyback to summary
private static void validateKey(String key)
validateValueback to summary
private static <V> void validateValue(V value)
org.eclipse.jgit.internal.storage.memory back to summary

public Interface TernarySearchTree.Loader<Value>

Type Parameters
<Value>
type of values
Loader to load key-value pairs to be cached in the tree

Method Summary

Modifier and TypeMethod and Description
public Map<String, Value>

Returns:

map of all key value pairs to cache in the tree
loadAll()

Load map of all key value pairs

Method Detail

loadAllback to summary
public Map<String, Value> loadAll()

Load map of all key value pairs

Returns:Map<String, Value>

map of all key value pairs to cache in the tree

org.eclipse.jgit.internal.storage.memory back to summary

private Class TernarySearchTree.Node<Value>

extends Object
Class Inheritance
  • java.lang.Object
  • org.eclipse.jgit.internal.storage.memory.TernarySearchTree.Node

Field Summary

Modifier and TypeField and Description
pack-priv final char
c

pack-priv TernarySearchTree.Node<Value>
eq

pack-priv TernarySearchTree.Node<Value>
hi

pack-priv TernarySearchTree.Node<Value>
lo

pack-priv Value
val

Constructor Summary

AccessConstructor and Description
pack-priv
Node(char c)

Method Summary

Modifier and TypeMethod and Description
pack-priv boolean
hasValue()

Inherited from java.lang.Object:
cloneequalsfinalizegetClasshashCodenotifynotifyAlltoStringwaitwaitwait

Field Detail

cback to summary
pack-priv final char c
eqback to summary
pack-priv TernarySearchTree.Node<Value> eq
hiback to summary
pack-priv TernarySearchTree.Node<Value> hi
loback to summary
pack-priv TernarySearchTree.Node<Value> lo
valback to summary
pack-priv Value val

Constructor Detail

Nodeback to summary
pack-priv Node(char c)

Method Detail

hasValueback to summary
pack-priv boolean hasValue()