Top Description Inners Constructors Methods
io.grpc

pack-priv final Class PersistentHashArrayMappedTrie

extends Object
Class Inheritance
Imports
java.util.Arrays
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 and Inner Type Summary

Modifier and TypeClass and Description
pack-priv static class
PersistentHashArrayMappedTrie.CollisionLeaf<K, V>

pack-priv static class
PersistentHashArrayMappedTrie.CompressedIndex<K, V>

pack-priv static class
PersistentHashArrayMappedTrie.Leaf<K, V>

pack-priv static interface
PersistentHashArrayMappedTrie.Node<K, V>

Constructor Summary

AccessConstructor and Description
private
PersistentHashArrayMappedTrie()

Method Summary

Modifier and TypeMethod and Description
pack-priv 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.

pack-priv 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.

Inherited from java.lang.Object:
cloneequalsfinalizegetClasshashCodenotifynotifyAlltoStringwaitwaitwait

Constructor Detail

PersistentHashArrayMappedTrieback to summary
private PersistentHashArrayMappedTrie()

Method Detail

getback to summary
pack-priv 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.

putback to summary
pack-priv 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.

io.grpc back to summary

pack-priv final Class PersistentHashArrayMappedTrie.CollisionLeaf<K, V>

extends Object
implements PersistentHashArrayMappedTrie.Node<K, V>
Class Inheritance
All Implemented Interfaces
io.grpc.PersistentHashArrayMappedTrie.Node

Field Summary

Modifier and TypeField and Description
private final K[]
keys

private final V[]
values

Constructor Summary

AccessConstructor and Description
pack-priv
CollisionLeaf(K key1, V value1, K key2, V value2)

private
CollisionLeaf(K[] keys, V[] values)

Method Summary

Modifier and TypeMethod and Description
public V
get(K key, int hash, int bitsConsumed)

Implements io.grpc.PersistentHashArrayMappedTrie.Node.get.

private int
indexOfKey(K key)

public PersistentHashArrayMappedTrie.Node<K, V>
put(K key, V value, int hash, int bitsConsumed)

Implements io.grpc.PersistentHashArrayMappedTrie.Node.put.

public int
size()

Implements io.grpc.PersistentHashArrayMappedTrie.Node.size.

public String
toString()

Overrides java.lang.Object.toString.

Returns a string representation of the object.
Inherited from java.lang.Object:
cloneequalsfinalizegetClasshashCodenotifynotifyAllwaitwaitwait

Field Detail

keysback to summary
private final K[] keys
valuesback to summary
private final V[] values

Constructor Detail

CollisionLeafback to summary
pack-priv CollisionLeaf(K key1, V value1, K key2, V value2)
Annotations
@SuppressWarnings:unchecked
CollisionLeafback to summary
private CollisionLeaf(K[] keys, V[] values)

Method Detail

getback to summary
public V get(K key, int hash, int bitsConsumed)

Implements io.grpc.PersistentHashArrayMappedTrie.Node.get.

Annotations
@Override
indexOfKeyback to summary
private int indexOfKey(K key)
putback to summary
public PersistentHashArrayMappedTrie.Node<K, V> put(K key, V value, int hash, int bitsConsumed)

Implements io.grpc.PersistentHashArrayMappedTrie.Node.put.

Annotations
@Override
sizeback to summary
public int size()

Implements io.grpc.PersistentHashArrayMappedTrie.Node.size.

Annotations
@Override
toStringback to summary
public String toString()

Overrides java.lang.Object.toString.

Doc from java.lang.Object.toString.

Returns a string representation of the object.

Returns:String

a string representation of the object.

Annotations
@Override
io.grpc back to summary

pack-priv final Class PersistentHashArrayMappedTrie.CompressedIndex<K, V>

extends Object
implements PersistentHashArrayMappedTrie.Node<K, V>
Class Inheritance
All Implemented Interfaces
io.grpc.PersistentHashArrayMappedTrie.Node

Field Summary

Modifier and TypeField and Description
pack-priv final int
bitmap

private static final int
BITS

private static final int
BITS_MASK

private final int
size

pack-priv final PersistentHashArrayMappedTrie.Node<K, V>[]
values

Constructor Summary

AccessConstructor and Description
private
CompressedIndex(int bitmap, PersistentHashArrayMappedTrie.Node<K, V>[] values, int size)

Method Summary

Modifier and TypeMethod and Description
pack-priv static <K, V> PersistentHashArrayMappedTrie.Node<K, V>
combine(PersistentHashArrayMappedTrie.Node<K, V> node1, int hash1, PersistentHashArrayMappedTrie.Node<K, V> node2, int hash2, int bitsConsumed)

private int
compressedIndex(int indexBit)

public V
get(K key, int hash, int bitsConsumed)

Implements io.grpc.PersistentHashArrayMappedTrie.Node.get.

private static int
indexBit(int hash, int bitsConsumed)

public PersistentHashArrayMappedTrie.Node<K, V>
put(K key, V value, int hash, int bitsConsumed)

Implements io.grpc.PersistentHashArrayMappedTrie.Node.put.

public int
size()

Implements io.grpc.PersistentHashArrayMappedTrie.Node.size.

public String
toString()

Overrides java.lang.Object.toString.

Returns a string representation of the object.
private static int
uncompressedIndex(int hash, int bitsConsumed)

Inherited from java.lang.Object:
cloneequalsfinalizegetClasshashCodenotifynotifyAllwaitwaitwait

Field Detail

bitmapback to summary
pack-priv final int bitmap
BITSback to summary
private static final int BITS
BITS_MASKback to summary
private static final int BITS_MASK
sizeback to summary
private final int size
valuesback to summary
pack-priv final PersistentHashArrayMappedTrie.Node<K, V>[] values

Constructor Detail

CompressedIndexback to summary
private CompressedIndex(int bitmap, PersistentHashArrayMappedTrie.Node<K, V>[] values, int size)

Method Detail

combineback to summary
pack-priv static <K, V> PersistentHashArrayMappedTrie.Node<K, V> combine(PersistentHashArrayMappedTrie.Node<K, V> node1, int hash1, PersistentHashArrayMappedTrie.Node<K, V> node2, int hash2, int bitsConsumed)
compressedIndexback to summary
private int compressedIndex(int indexBit)
getback to summary
public V get(K key, int hash, int bitsConsumed)

Implements io.grpc.PersistentHashArrayMappedTrie.Node.get.

Annotations
@Override
indexBitback to summary
private static int indexBit(int hash, int bitsConsumed)
putback to summary
public PersistentHashArrayMappedTrie.Node<K, V> put(K key, V value, int hash, int bitsConsumed)

Implements io.grpc.PersistentHashArrayMappedTrie.Node.put.

Annotations
@Override
sizeback to summary
public int size()

Implements io.grpc.PersistentHashArrayMappedTrie.Node.size.

Annotations
@Override
toStringback to summary
public String toString()

Overrides java.lang.Object.toString.

Doc from java.lang.Object.toString.

Returns a string representation of the object.

Returns:String

a string representation of the object.

Annotations
@Override
uncompressedIndexback to summary
private static int uncompressedIndex(int hash, int bitsConsumed)
io.grpc back to summary

pack-priv final Class PersistentHashArrayMappedTrie.Leaf<K, V>

extends Object
implements PersistentHashArrayMappedTrie.Node<K, V>
Class Inheritance
All Implemented Interfaces
io.grpc.PersistentHashArrayMappedTrie.Node

Field Summary

Modifier and TypeField and Description
private final K
key

private final V
value

Constructor Summary

AccessConstructor and Description
public
Leaf(K key, V value)

Method Summary

Modifier and TypeMethod and Description
public V
get(K key, int hash, int bitsConsumed)

Implements io.grpc.PersistentHashArrayMappedTrie.Node.get.

public PersistentHashArrayMappedTrie.Node<K, V>
put(K key, V value, int hash, int bitsConsumed)

Implements io.grpc.PersistentHashArrayMappedTrie.Node.put.

public int
size()

Implements io.grpc.PersistentHashArrayMappedTrie.Node.size.

public String
toString()

Overrides java.lang.Object.toString.

Returns a string representation of the object.
Inherited from java.lang.Object:
cloneequalsfinalizegetClasshashCodenotifynotifyAllwaitwaitwait

Field Detail

keyback to summary
private final K key
valueback to summary
private final V value

Constructor Detail

Leafback to summary
public Leaf(K key, V value)

Method Detail

getback to summary
public V get(K key, int hash, int bitsConsumed)

Implements io.grpc.PersistentHashArrayMappedTrie.Node.get.

Annotations
@Override
putback to summary
public PersistentHashArrayMappedTrie.Node<K, V> put(K key, V value, int hash, int bitsConsumed)

Implements io.grpc.PersistentHashArrayMappedTrie.Node.put.

Annotations
@Override
sizeback to summary
public int size()

Implements io.grpc.PersistentHashArrayMappedTrie.Node.size.

Annotations
@Override
toStringback to summary
public String toString()

Overrides java.lang.Object.toString.

Doc from java.lang.Object.toString.

Returns a string representation of the object.

Returns:String

a string representation of the object.

Annotations
@Override
io.grpc back to summary

pack-priv Interface PersistentHashArrayMappedTrie.Node<K, V>

Known Direct Implementers
io.grpc.PersistentHashArrayMappedTrie.Leaf, io.grpc.PersistentHashArrayMappedTrie.CollisionLeaf, io.grpc.PersistentHashArrayMappedTrie.CompressedIndex

Method Summary

Modifier and TypeMethod and Description
public V
get(K key, int hash, int bitsConsumed)

public PersistentHashArrayMappedTrie.Node<K, V>
put(K key, V value, int hash, int bitsConsumed)

public int
size()

Method Detail

getback to summary
public V get(K key, int hash, int bitsConsumed)
putback to summary
public PersistentHashArrayMappedTrie.Node<K, V> put(K key, V value, int hash, int bitsConsumed)
sizeback to summary
public int size()