This class is a kind of specialized type-safe Map, from char array to String value. Specialization means that in addition to type-safety and specific access patterns (key char array, Value optionally interned String; values added on access if necessary), and that instances are meant to be used concurrently, but by using well-defined mechanisms to obtain such concurrently usable instances. Main use for the class is to store symbol table information for things like compilers and parsers; especially when number of symbols (keywords) is limited.

For optimal performance, usage pattern should be one where matches should be very common (esp. after "warm-up"), and as with most hash-based maps/sets, that hash codes are uniformly distributed. Also, collisions are slightly more expensive than with HashMap or HashSet, since hash codes are not used in resolving collisions; that is, equals() comparison is done with all symbols in same bucket index.
Finally, rehashing is also more expensive, as hash codes are not stored; rehashing requires all entries' hash codes to be recalculated. Reason for not storing hash codes is reduced memory usage, hoping for better memory locality.

Usual usage pattern is to create a single "master" instance, and either use that instance in sequential fashion, or to create derived "child" instances, which after use, are asked to return possible symbol additions to master instance. In either case benefit is that symbol table gets initialized so that further uses are more efficient, as eventually all symbols needed will already be in symbol table. At that point no more Symbol String allocations are needed, nor changes to symbol table itself.

Note that while individual SymbolTable instances are NOT thread-safe (much like generic collection classes), concurrently used "child" instances can be freely used without synchronization. However, using master table concurrently with child instances can only be done if access to master instance is read-only (ie. no modifications done).

Modifier and Type	Class and Description
pack-priv static class	SymbolTable.Bucket This class is a symbol table entry.

Field Summary

Modifier and Type	Field and Description
protected static final float	DEFAULT_FILL_FACTOR
protected static final int	DEFAULT_TABLE_SIZE Default initial table size; no need to make it miniscule, due to couple of things: first, overhead of array reallocation is significant, and second, overhead of rehashing is also non-negligible.
protected static final String	EMPTY_STRING
protected SymbolTable.Bucket[]	mBuckets Overflow buckets; if primary doesn't match, lookup is done from here.
protected boolean	mDirty Flag that indicates if any changes have been made to the data; used to both determine if bucket array needs to be copied when (first) change is made, and potentially if updated bucket list is to be resync'ed back to master instance.
protected int	mIndexMask Mask used to get index from hash values; equal to `mBuckets.length - 1`, when mBuckets.length is a power of two.
protected boolean	mInternStrings Flag that determines whether Strings to be added need to be interned before being added or not.
protected int	mSize Current size (number of entries); needed to know if and when rehash.
protected int	mSizeThreshold Limit that indicates maximum size this instance can hold before it needs to be expanded and rehashed.
protected String[]	mSymbols Primary matching symbols; it's expected most match occur from here.
protected int	mThisVersion Version of this table instance; used when deriving new concurrently used versions from existing 'master' instance.

Constructor Summary

Access	Constructor and Description
public	SymbolTable() Method for constructing a master symbol table instance; this one will create master instance with default size, and with interning enabled.
public	SymbolTable(boolean internStrings) Method for constructing a master symbol table instance.
public	SymbolTable(boolean internStrings, int initialSize) Method for constructing a master symbol table instance.
public	SymbolTable(boolean Whether Strings to add are intern()ed or not internStrings, int Minimum initial size for bucket array; internally will always use a power of two equal to or bigger than this value. initialSize, float Maximum fill factor allowed for bucket table; when more entries are added, table will be expanded. fillFactor) Main method for constructing a master symbol table instance; will be called by other public constructors.
private	SymbolTable(boolean internStrings, String[] symbols, SymbolTable.Bucket[] buckets, int size, int sizeThreshold, int indexMask, int version) Internal constructor used when creating child instances.

Method Summary

Modifier and Type	Method and Description
public double	calcAvgSeek()
public static int	calcHash(char[] buffer, int start, int Length of String; has to be at least 1 (caller guarantees this pre-condition) len) Implementation of a hashing method for variable length Strings.
public static int	calcHash(String key)
private void	copyArrays() Method called when copy-on-write is needed; generally when first change is made to a derived symbol table.
public String	Returns: The symbol matching String in input array findSymbol(char[] buffer, int start, int len, int hash) Main access method; will check if actual symbol String exists; if so, returns it; if not, will create, add and return it.
public String	findSymbol(String str) Similar to to `findSymbol(char[], int, int, int)`; used to either do potentially cheap intern() (if table already has intern()ed version), or to pre-populate symbol table with known values.
public String	findSymbolIfExists(char[] buffer, int start, int len, int hash) Similar to {link #findSymbol}, but will not add passed in symbol if it is not in symbol table yet.
public boolean	isDirectChildOf(SymbolTable t)
public boolean	isDirty()
public SymbolTable	makeChild() "Factory" method; will create a new child instance of this symbol table.
public synchronized void	mergeChild(SymbolTable child) Method that allows contents of child table to potentially be "merged in" with contents of this symbol table.
private void	rehash() Method called when size (number of entries) of symbol table grows so big that load factor is exceeded.
public void	setInternStrings(boolean state)
public int	size()
public int	version()

Inherited from java.lang.Object:: clone equals finalize getClass hashCode notify notifyAll toString wait wait wait

Field Detail

DEFAULT_FILL_FACTOR	back to summary
protected static final float DEFAULT_FILL_FACTOR

DEFAULT_TABLE_SIZE	back to summary
protected static final int DEFAULT_TABLE_SIZE Default initial table size; no need to make it miniscule, due to couple of things: first, overhead of array reallocation is significant, and second, overhead of rehashing is also non-negligible. Let's use 128 as the default; it allows for up to 96 symbols, and uses about 512 bytes on 32-bit machines.

DEFAULT_TABLE_SIZE

back to summary

protected static final int DEFAULT_TABLE_SIZE

Default initial table size; no need to make it miniscule, due to couple of things: first, overhead of array reallocation is significant, and second, overhead of rehashing is also non-negligible.

Let's use 128 as the default; it allows for up to 96 symbols, and uses about 512 bytes on 32-bit machines.

EMPTY_STRING	back to summary
protected static final String EMPTY_STRING

mBuckets	back to summary
protected SymbolTable.Bucket[] mBuckets Overflow buckets; if primary doesn't match, lookup is done from here. Note Number of buckets is half of number of symbol entries, on assumption there's less need for buckets.

mDirty	back to summary
protected boolean mDirty Flag that indicates if any changes have been made to the data; used to both determine if bucket array needs to be copied when (first) change is made, and potentially if updated bucket list is to be resync'ed back to master instance.

mIndexMask	back to summary
protected int mIndexMask Mask used to get index from hash values; equal to `mBuckets.length - 1`, when mBuckets.length is a power of two.

mInternStrings	back to summary
protected boolean mInternStrings Flag that determines whether Strings to be added need to be interned before being added or not. Forcing intern()ing will add some overhead when adding new Strings, but may be beneficial if such Strings are generally used by other parts of system. Note that even without interning, all returned String instances are guaranteed to be comparable with equality (==) operator; it's just that such guarantees are not made for Strings other classes return.

mInternStrings

back to summary

protected boolean mInternStrings

Flag that determines whether Strings to be added need to be interned before being added or not. Forcing intern()ing will add some overhead when adding new Strings, but may be beneficial if such Strings are generally used by other parts of system. Note that even without interning, all returned String instances are guaranteed to be comparable with equality (==) operator; it's just that such guarantees are not made for Strings other classes return.

mSize	back to summary
protected int mSize Current size (number of entries); needed to know if and when rehash.

mSizeThreshold	back to summary
protected int mSizeThreshold Limit that indicates maximum size this instance can hold before it needs to be expanded and rehashed. Calculated using fill factor passed in to constructor.

mSymbols	back to summary
protected String[] mSymbols Primary matching symbols; it's expected most match occur from here.

mThisVersion	back to summary
protected int mThisVersion Version of this table instance; used when deriving new concurrently used versions from existing 'master' instance.

Constructor Detail

SymbolTable	back to summary
public SymbolTable() Method for constructing a master symbol table instance; this one will create master instance with default size, and with interning enabled.

SymbolTable	back to summary
public SymbolTable(boolean internStrings) Method for constructing a master symbol table instance.

SymbolTable	back to summary
public SymbolTable(boolean internStrings, int initialSize) Method for constructing a master symbol table instance.

SymbolTable	back to summary
public SymbolTable(boolean internStrings, int initialSize, float fillFactor) Main method for constructing a master symbol table instance; will be called by other public constructors. Parameters internStrings:boolean Whether Strings to add are intern()ed or not initialSize:int Minimum initial size for bucket array; internally will always use a power of two equal to or bigger than this value. fillFactor:float Maximum fill factor allowed for bucket table; when more entries are added, table will be expanded.

SymbolTable

back to summary

public SymbolTable(boolean internStrings, int initialSize, float fillFactor)

Main method for constructing a master symbol table instance; will be called by other public constructors.

Parameters

internStrings:boolean: Whether Strings to add are intern()ed or not
initialSize:int: Minimum initial size for bucket array; internally will always use a power of two equal to or bigger than this value.
fillFactor:float: Maximum fill factor allowed for bucket table; when more entries are added, table will be expanded.

SymbolTable	back to summary
private SymbolTable(boolean internStrings, String[] symbols, SymbolTable.Bucket[] buckets, int size, int sizeThreshold, int indexMask, int version) Internal constructor used when creating child instances.

Method Detail

calcAvgSeek	back to summary
public double calcAvgSeek()

calcHash	back to summary
public static int calcHash(char[] buffer, int start, int len) Implementation of a hashing method for variable length Strings. Most of the time intention is that this calculation is done by caller during parsing, not here; however, sometimes it needs to be done for parsed "String" too. Parameters len:int Length of String; has to be at least 1 (caller guarantees this pre-condition) Annotations @SuppressWarnings:cast

calcHash

back to summary

public static int calcHash(char[] buffer, int start, int len)

Implementation of a hashing method for variable length Strings. Most of the time intention is that this calculation is done by caller during parsing, not here; however, sometimes it needs to be done for parsed "String" too.

Parameters

len:int: Length of String; has to be at least 1 (caller guarantees this pre-condition)

Annotations

@SuppressWarnings:cast

calcHash	back to summary
public static int calcHash(String key) Annotations @SuppressWarnings:cast

copyArrays	back to summary
private void copyArrays() Method called when copy-on-write is needed; generally when first change is made to a derived symbol table.

findSymbol	back to summary
public String findSymbol(char[] buffer, int start, int len, int hash) Main access method; will check if actual symbol String exists; if so, returns it; if not, will create, add and return it. Returns:String The symbol matching String in input array

findSymbol

back to summary

public String findSymbol(char[] buffer, int start, int len, int hash)

Main access method; will check if actual symbol String exists; if so, returns it; if not, will create, add and return it.

Returns:String: The symbol matching String in input array

findSymbol	back to summary
public String findSymbol(String str) Similar to to `findSymbol(char[], int, int, int)`; used to either do potentially cheap intern() (if table already has intern()ed version), or to pre-populate symbol table with known values.

findSymbolIfExists	back to summary
public String findSymbolIfExists(char[] buffer, int start, int len, int hash) Similar to {link #findSymbol}, but will not add passed in symbol if it is not in symbol table yet.

isDirectChildOf	back to summary
public boolean isDirectChildOf(SymbolTable t)

isDirty	back to summary
public boolean isDirty()

makeChild	back to summary
public SymbolTable makeChild() "Factory" method; will create a new child instance of this symbol table. It will be a copy-on-write instance, ie. it will only use read-only copy of parent's data, but when changes are needed, a copy will be created. Note while data access part of this method is synchronized, it is generally not safe to both use makeChild/mergeChild, AND to use instance actively. Instead, a separate 'root' instance should be used on which only makeChild/mergeChild are called, but instance itself is not used as a symbol table.

makeChild

back to summary

public SymbolTable makeChild()

"Factory" method; will create a new child instance of this symbol table. It will be a copy-on-write instance, ie. it will only use read-only copy of parent's data, but when changes are needed, a copy will be created.

Note

while data access part of this method is synchronized, it is generally not safe to both use makeChild/mergeChild, AND to use instance actively. Instead, a separate 'root' instance should be used on which only makeChild/mergeChild are called, but instance itself is not used as a symbol table.

mergeChild	back to summary
public synchronized void mergeChild(SymbolTable child) Method that allows contents of child table to potentially be "merged in" with contents of this symbol table. Note that caller has to make sure symbol table passed in is really a child or sibling of this symbol table.

mergeChild

back to summary

public synchronized void mergeChild(SymbolTable child)

Method that allows contents of child table to potentially be "merged in" with contents of this symbol table.

Note that caller has to make sure symbol table passed in is really a child or sibling of this symbol table.

rehash	back to summary
private void rehash() Method called when size (number of entries) of symbol table grows so big that load factor is exceeded. Since size has to remain power of two, arrays will then always be doubled. Main work is really redistributing old entries into new String/Bucket entries.

setInternStrings	back to summary
public void setInternStrings(boolean state)

size	back to summary
public int size()

version	back to summary
public int version()

com.ctc.wstx.util back to summary

pack-priv final Class SymbolTable.Bucket

Class Inheritance

extends Object

java.lang.Object
com.ctc.wstx.util.SymbolTable.Bucket

This class is a symbol table entry. Each entry acts as a node in a linked list.

Field Summary

Modifier and Type	Field and Description
private final SymbolTable.Bucket	mNext
private final String	mSymbol

Constructor Summary

Access	Constructor and Description
public	Bucket(String symbol, SymbolTable.Bucket next)

Method Summary

Modifier and Type	Method and Description
public String	find(char[] buf, int start, int len)
public String	find(String str)
public SymbolTable.Bucket	getNext()
public String	getSymbol()

Inherited from java.lang.Object:: clone equals finalize getClass hashCode notify notifyAll toString wait wait wait

Field Detail

mNext	back to summary
private final SymbolTable.Bucket mNext

mSymbol	back to summary
private final String mSymbol

Constructor Detail

Bucket	back to summary
public Bucket(String symbol, SymbolTable.Bucket next)

Method Detail

find	back to summary
public String find(char[] buf, int start, int len)

find	back to summary
public String find(String str)

getNext	back to summary
public SymbolTable.Bucket getNext()

getSymbol	back to summary
public String getSymbol()

public Class SymbolTable

Nested and Inner Type Summary

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

Method Detail

pack-priv final Class SymbolTable.Bucket

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

Method Detail