Package io.grpc

Class PersistentHashArrayMappedTrie

java.lang.Object

io.grpc.PersistentHashArrayMappedTrie

final class PersistentHashArrayMappedTrie
extends java.lang.Object

A persistent (copy-on-write) hash tree/trie. Collisions are handled linearly. Delete is not supported, but replacement is. The implementation favors simplicity and low memory allocation during insertion. Although the asymptotics are good, it is optimized for small sizes like less than 20; "unbelievably large" would be 100.

Inspired by popcnt-based compression seen in Ideal Hash Trees, Phil Bagwell (2000). The rest of the implementation is ignorant of/ignores the paper.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
(package private) static class	PersistentHashArrayMappedTrie.CollisionLeaf<K,V>
(package private) static class	PersistentHashArrayMappedTrie.CompressedIndex<K,V>
(package private) static class	PersistentHashArrayMappedTrie.Leaf<K,V>
(package private) static interface	PersistentHashArrayMappedTrie.Node<K,V>

Constructor Summary

Constructors

Modifier	Constructor	Description
private	PersistentHashArrayMappedTrie()

Method Summary

Modifier and Type	Method	Description
(package private) static <K,V> V	get(PersistentHashArrayMappedTrie.Node<K,V> root, K key)	Returns the value with the specified key, or null if it does not exist.
(package private) static <K,V> PersistentHashArrayMappedTrie.Node<K,V>	put(PersistentHashArrayMappedTrie.Node<K,V> root, K key, V value)	Returns a new trie where the key is set to the specified value.

Methods inherited from class java.lang.Object

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

Constructor Detail

PersistentHashArrayMappedTrie

private PersistentHashArrayMappedTrie()

Method Detail

get

static <K,V> V get(PersistentHashArrayMappedTrie.Node<K,V> root,
                         K key)

Returns the value with the specified key, or null if it does not exist.

put

static <K,V> PersistentHashArrayMappedTrie.Node<K,V> put(PersistentHashArrayMappedTrie.Node<K,V> root,
                                                                     K key,
                                                                     V value)

Returns a new trie where the key is set to the specified value.