org.codehaus.jackson.util
Class SymbolTable

java.lang.Object
  org.codehaus.jackson.util.SymbolTable

public final class SymbolTable
extends Object

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).

Field Summary

protected static int	DEFAULT_TABLE_SIZE Default initial table size.
protected static boolean	INTERN_STRINGS Config setting that determines whether Strings to be added need to be interned before being added or not.
protected org.codehaus.jackson.util.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 SymbolTable	mParent Sharing of learnt symbols is done by optional linking of symbol table instances with their parents.
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.

Constructor Summary

SymbolTable()
Method for constructing a master symbol table instance.

SymbolTable(int initialSize)
Main method for constructing a master symbol table instance; will be called by other public constructors.

Method Summary

static int	calcHash(char[] buffer, int start, int len) Implementation of a hashing method for variable length Strings.
static int	calcHash(String key)
static SymbolTable	createRoot()
String	findSymbol(char[] buffer, int start, int len, int hash)
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.
SymbolTable	makeChild() "Factory" method; will create a new child instance of this symbol table.
boolean	maybeDirty()
void	release()
int	size()

Methods inherited from class java.lang.Object

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

Field Detail

DEFAULT_TABLE_SIZE

protected static final int DEFAULT_TABLE_SIZE

Default initial table size. Shouldn't be miniscule (as there's cost to both array realloc and rehashing), but let's keep it reasonably small nonetheless. For systems that properly reuse factories it doesn't matter either way; but when recreating factories often, initial overhead may dominate.

See Also:

Constant Field Values

INTERN_STRINGS

protected static final boolean INTERN_STRINGS

Config setting 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.

See Also:

Constant Field Values

mParent

protected SymbolTable mParent

Sharing of learnt symbols is done by optional linking of symbol table instances with their parents. When parent linkage is defined, and child instance is released (call to release), parent's shared tables may be updated from the child instance.

mSymbols

protected String[] mSymbols

Primary matching symbols; it's expected most match occur from here.

mBuckets

protected org.codehaus.jackson.util.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.

mSize

protected int mSize

Current size (number of entries); needed to know if and when rehash.

mSizeThreshold

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.

mIndexMask

protected int mIndexMask

Mask used to get index from hash values; equal to mBuckets.length - 1, when mBuckets.length is a power of two.

mDirty

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.

Constructor Detail

SymbolTable

public SymbolTable()

Method for constructing a master symbol table instance.

SymbolTable

public SymbolTable(int initialSize)

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

Parameters:

initialSize - Minimum initial size for bucket array; internally will always use a power of two equal to or bigger than this value.

Method Detail

createRoot

public static SymbolTable createRoot()

makeChild

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

release

public void release()

size

public int size()

maybeDirty

public boolean maybeDirty()

findSymbol

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

findSymbol

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.

calcHash

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 - Length of String; has to be at least 1 (caller guarantees this pre-condition)

calcHash

public static int calcHash(String key)