Top Description Inners Fields Constructors Methods
com.sun.msv.grammar

public Class ExpressionPool

extends Object
implements Serializable
Class Inheritance
All Implemented Interfaces
java.io.Serializable
Imports
java.io.IOException, .ObjectInputStream, .ObjectOutputStream, .ObjectStreamField, org.relaxng.datatype.Datatype, com.sun.msv.datatype.xsd.XSDatatype, com.sun.msv.util.StringPair
Creates a new Expression by combining existing expressions. all expressions are memorized and unified so that every subexpression will be shared and reused. Optimization will be also done transparently. For example, createChoice(P,P) will result in P. createSequence(P,nullSet) will result in nullSet. Furthermore, associative operators are grouped to the left. createChoice( (P|Q), (R|S) ) will be ((P|Q)|R)|S.

Although this unification is essential, this is also the performance bottle neck. In particular, createChoice and createSequence are two most commonly called methods.

For example, when validating a DocBook XML (150KB) twice against DocBook.trex(237KB), createChoice is called 63000 times and createSequence called 23000 times. (the third is the createOptional method and only 1560 times.) And they took more than 10% of validation time, which is the worst time-consuming method.

Therefore, please beware that this class includes several ugly code optimization.

Author
Kohsuke KAWAGUCHI

Nested and Inner Type Summary

Modifier and TypeClass and Description
public static class
ExpressionPool.ClosedHash

expression cache by closed hash.

Field Summary

Modifier and TypeField and Description
private final ExpressionPool.ClosedHash
expTable

hash table that contains all expressions currently known to this table.

private static final long
serialVersionUID

Constructor Summary

AccessConstructor and Description
public
ExpressionPool(ExpressionPool parent)

creates new expression pool as a child pool of the given parent pool.

public
ExpressionPool()

Method Summary

Modifier and TypeMethod and Description
public final Expression
createAnyString()

public final Expression
createAttribute(NameClass nameClass)

public final Expression
createAttribute(NameClass nameClass, Expression content, String defaultValue)

public final Expression
createChoice(Expression left, Expression right)

public final Expression
createConcur(Expression left, Expression right)

public final Expression
createData(XSDatatype dt)

public final Expression
createData(Datatype dt, StringPair typeName)

public final Expression
createData(Datatype dt, StringPair typeName, Expression except)

public final Expression
createEpsilon()

public final Expression
createInterleave(Expression left, Expression right)

public final Expression
createList(Expression exp)

public final Expression
createMixed(Expression body)

public final Expression
createNullSet()

public final Expression
createOneOrMore(Expression child)

public final Expression
createOptional(Expression child)

public final Expression
createSequence(Expression left, Expression right)

public final Expression
createValue(XSDatatype dt, Object value)

public final Expression
createValue(Datatype dt, StringPair typeName, Object value)

public final Expression
createZeroOrMore(Expression child)

protected final Expression
unify(Expression exp)

unifies expressions.

Inherited from java.lang.Object:
cloneequalsfinalizegetClasshashCodenotifynotifyAlltoStringwaitwaitwait

Field Detail

expTableback to summary
private final ExpressionPool.ClosedHash expTable

hash table that contains all expressions currently known to this table.

serialVersionUIDback to summary
private static final long serialVersionUID

Constructor Detail

ExpressionPoolback to summary
public ExpressionPool(ExpressionPool parent)

creates new expression pool as a child pool of the given parent pool.

Every expression memorized in the parent pool can be retrieved, but update operations are only performed upon the child pool. In this way, the parent pool can be shared among the multiple threads without interfering performance.

Furthermore, you can throw away a child pool after a certain time period to prevent it from eating up memory.

ExpressionPoolback to summary
public ExpressionPool()

Method Detail

createAnyStringback to summary
public final Expression createAnyString()
createAttributeback to summary
public final Expression createAttribute(NameClass nameClass)
createAttributeback to summary
public final Expression createAttribute(NameClass nameClass, Expression content, String defaultValue)
createChoiceback to summary
public final Expression createChoice(Expression left, Expression right)
createConcurback to summary
public final Expression createConcur(Expression left, Expression right)
createDataback to summary
public final Expression createData(XSDatatype dt)
createDataback to summary
public final Expression createData(Datatype dt, StringPair typeName)
createDataback to summary
public final Expression createData(Datatype dt, StringPair typeName, Expression except)
createEpsilonback to summary
public final Expression createEpsilon()
createInterleaveback to summary
public final Expression createInterleave(Expression left, Expression right)
createListback to summary
public final Expression createList(Expression exp)
createMixedback to summary
public final Expression createMixed(Expression body)
createNullSetback to summary
public final Expression createNullSet()
createOneOrMoreback to summary
public final Expression createOneOrMore(Expression child)
createOptionalback to summary
public final Expression createOptional(Expression child)
createSequenceback to summary
public final Expression createSequence(Expression left, Expression right)
createValueback to summary
public final Expression createValue(XSDatatype dt, Object value)
createValueback to summary
public final Expression createValue(Datatype dt, StringPair typeName, Object value)
createZeroOrMoreback to summary
public final Expression createZeroOrMore(Expression child)
unifyback to summary
protected final Expression unify(Expression exp)

unifies expressions. If the equivalent expression is already registered in the table, destroy newly created one (so that no two objects represents same expression structure). If it's not registered, then register it and return it.

com.sun.msv.grammar back to summary

public final Class ExpressionPool.ClosedHash

extends Object
implements Serializable
Class Inheritance
All Implemented Interfaces
java.io.Serializable
expression cache by closed hash. Special care has to be taken wrt threading. This implementation allows get and put method to be called simulatenously.

Field Summary

Modifier and TypeField and Description
private int
count

The total number of mappings in the hash table.

private static final int
initialCapacity

private static final float
loadFactor

The load factor for the hashtable.

private ExpressionPool.ClosedHash
parent

The parent hash table.

private static final ObjectStreamField[]
serialPersistentFields

private static final long
serialVersionUID

private Expression[]
table

The hash table data.

private int
threshold

The table is rehashed when its size exceeds this threshold.

Constructor Summary

AccessConstructor and Description
public
ClosedHash()

public
ClosedHash(ExpressionPool.ClosedHash parent)

Method Summary

Modifier and TypeMethod and Description
public Expression
get(int hash, Expression child, Class<?> type)

public Expression
get(Expression key)

public Expression
getBinExp(Expression left, Expression right, Class<?> type)

private Expression
getBinExp(int hash, Expression left, Expression right, Class<?> type)

public void
put(Expression newExp)

put method.

private void
readObject(ObjectInputStream s)

private void
rehash()

rehash.

private void
writeObject(ObjectOutputStream s)

Inherited from java.lang.Object:
cloneequalsfinalizegetClasshashCodenotifynotifyAlltoStringwaitwaitwait

Field Detail

countback to summary
private int count

The total number of mappings in the hash table.

initialCapacityback to summary
private static final int initialCapacity
loadFactorback to summary
private static final float loadFactor

The load factor for the hashtable.

parentback to summary
private ExpressionPool.ClosedHash parent

The parent hash table. can be null. items in the parent hash table will be returned by get method.

The field is essentially final but because of the serialization support we cannot mark it as such.

serialPersistentFieldsback to summary
private static final ObjectStreamField[] serialPersistentFields
serialVersionUIDback to summary
private static final long serialVersionUID
tableback to summary
private Expression[] table

The hash table data.

thresholdback to summary
private int threshold

The table is rehashed when its size exceeds this threshold. (The value of this field is (int)(capacity * loadFactor).)

Constructor Detail

ClosedHashback to summary
public ClosedHash()
ClosedHashback to summary
public ClosedHash(ExpressionPool.ClosedHash parent)

Method Detail

getback to summary
public Expression get(int hash, Expression child, Class<?> type)
getback to summary
public Expression get(Expression key)
getBinExpback to summary
public Expression getBinExp(Expression left, Expression right, Class<?> type)
getBinExpback to summary
private Expression getBinExp(int hash, Expression left, Expression right, Class<?> type)
putback to summary
public void put(Expression newExp)

put method. No two threads can call this method simulatenously, and it's the caller's responsibility to enforce it.

readObjectback to summary
private void readObject(ObjectInputStream s) throws IOException, ClassNotFoundException
rehashback to summary
private void rehash()

rehash. It is possible for one thread to call get method while another thread is performing rehash. Keep this in mind.

writeObjectback to summary
private void writeObject(ObjectOutputStream s) throws IOException