org.owasp.esapi.codecs

Class HashTrie<T>

java.lang.Object

org.owasp.esapi.codecs.HashTrie<T>

All Implemented Interfaces:

java.util.Map<java.lang.CharSequence,T>, Trie<T>

public class HashTrie<T>
extends java.lang.Object
implements Trie<T>

Trie implementation for CharSequence keys. This uses HashMaps for each level instead of the traditional array. This is done as with unicode, each level's array would be 64k entries. NOTE:

• Map.remove(Object) is not supported.
• If deletion support is added the max key length will need work or removal.
• Null values are not supported.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
private static class	HashTrie.Entry<T>
private static class	HashTrie.Node<T> Node inside the trie.

Nested classes/interfaces inherited from interface org.owasp.esapi.codecs.Trie

Trie.TrieProxy<T>, Trie.Unmodifiable<T>, Trie.Util

Field Summary

Fields

Modifier and Type	Field and Description
private int	maxKeyLen
private HashTrie.Node<T>	root
private int	size

Constructor Summary

Constructors

Constructor and Description
HashTrie()

Method Summary

Modifier and Type	Method and Description
void	clear() Clear all entries.
boolean	containsKey(java.lang.Object key)
boolean	containsValue(java.lang.Object value)
java.util.Set<java.util.Map.Entry<java.lang.CharSequence,T>>	entrySet()
boolean	equals(java.lang.Object other)
T	get(java.lang.Object key) Get the value for a key.
java.util.Map.Entry<java.lang.CharSequence,T>	getLongestMatch(java.lang.CharSequence key) Get the key value entry who's key is the longest prefix match.
java.util.Map.Entry<java.lang.CharSequence,T>	getLongestMatch(java.io.PushbackReader keyIn) Get the key value entry who's key is the longest prefix match.
int	getMaxKeyLength() Get the maximum key length.
int	hashCode()
boolean	isEmpty()
java.util.Set<java.lang.CharSequence>	keySet()
T	put(java.lang.CharSequence key, T value) Add mapping.
void	putAll(java.util.Map<? extends java.lang.CharSequence,? extends T> map)
T	remove(java.lang.Object key) Remove a entry.
int	size() Get the number of entries.
java.lang.String	toString()
java.util.Collection<T>	values()

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.Map

compute, computeIfAbsent, computeIfPresent, forEach, getOrDefault, merge, putIfAbsent, remove, replace, replace, replaceAll

Field Detail

root

private HashTrie.Node<T> root

maxKeyLen

private int maxKeyLen

size

private int size

Constructor Detail

HashTrie

public HashTrie()

Method Detail

getLongestMatch

public java.util.Map.Entry<java.lang.CharSequence,T> getLongestMatch(java.lang.CharSequence key)

Get the key value entry who's key is the longest prefix match.

Specified by:

getLongestMatch in interface Trie<T>

Parameters:

key - The key to lookup

Returns:

Entry with the longest matching key.

getLongestMatch

public java.util.Map.Entry<java.lang.CharSequence,T> getLongestMatch(java.io.PushbackReader keyIn)
                                                              throws java.io.IOException

Get the key value entry who's key is the longest prefix match.

Specified by:

getLongestMatch in interface Trie<T>

Parameters:

keyIn - Pushback reader to read the key from. This should have a buffer at least as large as getMaxKeyLength() or an IOException may be thrown backing up.

Returns:

Entry with the longest matching key.

Throws:

java.io.IOException - if keyIn.read() or keyIn.unread() does.

getMaxKeyLength

public int getMaxKeyLength()

Get the maximum key length.

Specified by:

getMaxKeyLength in interface Trie<T>

Returns:

max key length.

clear

public void clear()

Clear all entries.

Specified by:

clear in interface java.util.Map<java.lang.CharSequence,T>

containsKey

public boolean containsKey(java.lang.Object key)

Specified by:

containsKey in interface java.util.Map<java.lang.CharSequence,T>

containsValue

public boolean containsValue(java.lang.Object value)

Specified by:

containsValue in interface java.util.Map<java.lang.CharSequence,T>

put

public T put(java.lang.CharSequence key,
             T value)
      throws java.lang.NullPointerException

Add mapping.

Specified by:

put in interface java.util.Map<java.lang.CharSequence,T>

Parameters:

key - The mapping's key.

Throws:

java.lang.NullPointerException - if key or value is null.

remove

public T remove(java.lang.Object key)
         throws java.lang.UnsupportedOperationException

Remove a entry.

Specified by:

remove in interface java.util.Map<java.lang.CharSequence,T>

Returns:

previous value

Throws:

java.lang.UnsupportedOperationException - always.

putAll

public void putAll(java.util.Map<? extends java.lang.CharSequence,? extends T> map)

Specified by:

putAll in interface java.util.Map<java.lang.CharSequence,T>

keySet

public java.util.Set<java.lang.CharSequence> keySet()

Specified by:

keySet in interface java.util.Map<java.lang.CharSequence,T>

values

public java.util.Collection<T> values()

Specified by:

values in interface java.util.Map<java.lang.CharSequence,T>

entrySet

public java.util.Set<java.util.Map.Entry<java.lang.CharSequence,T>> entrySet()

Specified by:

entrySet in interface java.util.Map<java.lang.CharSequence,T>

get

public T get(java.lang.Object key)

Get the value for a key.

Specified by:

get in interface java.util.Map<java.lang.CharSequence,T>

Parameters:

key - The key to look up.

Returns:

The value for key or null if the key is not found.

size

public int size()

Get the number of entries.

Specified by:

size in interface java.util.Map<java.lang.CharSequence,T>

Returns:

the number or entries.

equals

public boolean equals(java.lang.Object other)

Specified by:

equals in interface java.util.Map<java.lang.CharSequence,T>

Overrides:

equals in class java.lang.Object

hashCode

public int hashCode()

Specified by:

hashCode in interface java.util.Map<java.lang.CharSequence,T>

Overrides:

hashCode in class java.lang.Object

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

isEmpty

public boolean isEmpty()

Specified by:

isEmpty in interface java.util.Map<java.lang.CharSequence,T>