382
Chapter 10 JSP Taglib: The bonForum Custom Tags
the
transform
tag is called, invoking the methods of its handler class.The following
code in that handler, from TransformTag.java, takes care of getting the style-sheet para-
meter:
String param1 = (String)pageContext.getSession( ).getAttribute( “param1” );
if( param1 == null) {
param1 = “”;
}
The
TransformTag
class invokes an XSLT processing method in one of several ways,
depending on the tag attribute values. Every such invocation, whether for Xalan-Java 1
or Xalan-Java 2, passes the style-sheet parameter as an argument, like this:
transformer.transform(inXML, inXSL, outDoc, param1)
10.9.5 How the Style Sheet works
The first template in the style sheet matches the root node. It begins an HTML
select
element and then applies templates to all the
bonForum.things
nodes. A chat
element is found whose
itemKey
value matches the
param1
value passed by the JSP tag
action.That is the current chat for the session.The children of that chat element are
iterated looking for any
guestKey

and customizable using technologies designed for such purposes.The two most pow-
erful ways to turn the bonForum prototype into a chat that is visually appealing and
full of features are JSP custom tags and XSLT processing.
10 1089-9 CH10 6/26/01 7:35 AM Page 382
Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark.
383
10.9 Displaying the Guests in a Chat
10.9.7 Sending Feedback to the Author
We hope that you enjoy altering and improving the JSP documents and the XSL style
sheets as much as we enjoyed creating the ones shown here.To send your own solu-
tions, improvements, donations, and flames, or to discuss the contents of this book, feel
free to email the author of this book at

, or use the forums and
mailing lists provided by SourceForge to reach the bonForum project Web site:

.
10 1089-9 CH10 6/26/01 7:35 AM Page 383
Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark.
10 1089-9 CH10 6/26/01 7:35 AM Page 384
Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark.
XML Data Storage Class:
ForestHashtable
11
I
N THIS CHAPTER
,
YOU CAN LEARN HOW
we implemented data storage for the XML
data in the bonForum chat application. A descendant of the

The
de.tarent.ForestHashtable
class extends the
java.util.Hashtable
class. In this
chapter, we assume that you are familiar with the
Hashtable
class. If you are not, or if
you have questions about it, consult the API documentation for the Java SDK you are
using.
Briefly, a
Hashtable
instance keeps track of a number of objects called elements.
When you add an element to a
Hashtable
, you associate it with another object called
a key.You can later use this key to find the element again. Because our
ForestHashtable
class is a descendant of a
Hashtable
, it can serve as the object storage
facility for our Web application example project.
Note that the term element is used in this chapter with two different definitions: an
object held by a
Hashtable
, and a type of XML node. Hopefully, each time the term
appears, context will differentiate between the two meanings.
11.1.1 ForestHashtable Stores Simple XML
A
ForestHashtable

The
ForestHashtable
is a customized
Hashtable
whose elements are
BonNode
objects and whose keys are
NodeKey
objects.
11 1089-9 CH11 6/26/01 7:36 AM Page 386
Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark.
387
11.2 The NodeKey Class
n
The
BonNode
objects can represent XML elements together with their attributes
and text content.
n
The
NodeKey
objects, which simulate three “key columns” in a database table,
can map the hierarchical relationships between the XML elements and facilitate
some optimized data-access operations.
In the rest of this chapter, our discussion of
ForestHashtable
will focus less on its the-
oretical aspects and more on its practical aspects. Here is a list of some major areas we
will cover:
n

is ini-
tialized, and we also will discuss an example of
bonForumXML
data after a couple
chats were started.
11.2 The NodeKey Class
The following excerpt from the file NodeKey.java is the definition of the
NodeKey
class:
class NodeKey {
String aKey;
String bKey;
String cKey;
public NodeKey() {
this.aKey = “”;
this.bKey = “”;
this.cKey = “”;
}
public String toString() {
return aKey + “.” + bKey + “.” + cKey;
}
}
As you can see, a
NodeKey
instance simply encapsulates three strings, which together
form a three-part key.The three parts are known as
aKey
,
bKey
, and

aKey
) is
different for each
NodeKey
instance, something that allows each
NodeKey
object to
function as a unique key for a
BonNode
object in the
ForestHashtable
.The
aKey
is
derived from the system time in milliseconds, which gives a way to order
NodeKeys
in
time and also ensures that each
NodeKey
can be given a unique value, as long as only
one source of
NodeKey
values is present.
11.3 The BonNode Class
Here is the definition of the
BonNode
class, from the file BonNode.java:
class BonNode {
NodeKey nodeKey;
NodeKey parentNodeKey;

kept in the
BonNode
, we can determine hierarchical rela-
tionships between
BonNode
objects from the objects themselves.
11 1089-9 CH11 6/26/01 7:36 AM Page 388
Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark.
389
11.3 The BonNode Class
11.3.2 parentNodeKey in a BonNode
Note that the
BonNode
string member known as
parentNodeKey
is not needed for rep-
resenting the hierarchical position of a node, as long as the
NodeKey
member is a mul-
tipart key object, such as the triple-key values that we use in the bonForum project
and which are discussed fully later.
Why is the
parentNodeKey
in the
BonNode
class, then? There are two reasons for
that. (Hint:You might want to revisit these two items after reading about forest tables.)
1. You could use the
BonNode
class with different types of keys that are not multi-

any) of an XML document.The only thing that the
BonNode
must keep to faithfully
map an XML element node is its hierarchical position (in the
NodeKey
member) and
its name (in the
nodeName
string member).
11.3.4 Attributes of a BonNode
From a low-level XML programming view, it is advantageous to access the attributes
of an element as child nodes of the element node that they are attributes of. So, attrib-
utes are best represented as nodes in their own right, so to speak. Such “attribute
nodes” would have to be specialized in some fashion, of course, to distinguish them
from true children and ensure that the original XML could be reproduced. However,
for the purposes of the bonForum Web application, all that is needed is to keep the list
of name=value items associated with the associated XML element. A
BonNode
object
keeps such a list as a single string member of itself, which is called
nodeAttributes
.
11.3.5 Content of a BonNode
The third thing that a
BonNode
can represent from an XML document is a concatena-
tion of all the text nodes that are children of the element named by the
nodeName
string member.The concatenated text is kept in the
nodeContent

11.3.7 Flagging Visits to a BonNode
Another flag in each node is called
flagged
.This is used by the
getXMLForest()
method that converts the data in a
ForestHashtable
into XML trees.This conversion
requires repeated iterations of the
Hashtable
contents, first to get the root nodes, then
to get their children, and finally to recursively visit all the other nodes.We “hide” each
node that has already been processed by setting its
flagged
member to a value of
True
.
This enables us to simplify the code that we use to test the depth of a node in the
hierarchy.
Someone might raise the objection that this is mixing procedural with OOP and
can introduce multithreading and data integrity problems, and that it would be much
safer to have this method keep its own separate list of
nodeKeys
visited and check
against that.We hope that this objection will no longer hold when our simulation (the
ForestHashtable
class) is implemented in a relational database.The
getXMLForest()
method should be seen as a convenience for the simulation and not essential to the
design.

table, the one that represents that node’s parent.
If a node has no parent, then it is a root node.The parent key of a root node is set
to point to the root node itself.Therefore, if the values of the node and parent key are
equal, the node in question is a root node. Usually, in Java APIs, the parent of a root
node is null—that is, it represents the absence of a parent. Notice that making the par-
ent equal to the node means that to traverse a tree, you cannot use this “usual” phrase:
for (node = someNode; node.getParent() != null; node = node.getParent()){…}
Neither can you use this stock phrase:
while ((node = node.getParent()) != null){…}
Instead, for tree traversal, you would use this:
while (node != node.getParent()) {…}
These examples were cited as a source of potential confusion stemming from our
design. However, it does seem to us that the third example is simpler, at least.
Let’s use an example to help you visualize such a table.We call the two keys
node
and
parent
, and we give each node just two columns for a name and type. For pri-
mary key values we will use sequential integers. First we will display part of the table
in Table 11.1.
11 1089-9 CH11 6/26/01 7:36 AM Page 391
Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark.
392
Chapter 11 XML Data Storage Class: ForestHashtable
Table 11.1 Tree of Life in a Double-Key Table
Node Parent Name Type
1 1 Animalia Kingdom
2 1 Mollusca Phylum
3 1 Chordata Phylum
4 3 Mammalia Class

class uses three
key columns. In each row, we keep track of both the node’s parent and its grandparent.
We should point out here that some might think that the grandparent key is super-
fluous and redundant and that it promotes bad design/coding practices. Normalized
database design would use either the two-key approach (for single-parent trees) or a
single key and a mapping table (for multiparent relationships).
11 1089-9 CH11 6/26/01 7:36 AM Page 392
Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark.
393
11.4 ForestHashtable Maps Data Trees
Here is the same partial table example, this time with an additional key called
grandparent
. Note that in the
NodeKey
used by the
ForestHashtable
, the three keys
are called
aKey
,
bKey,
and
cKey
instead of
node
,
parent
, and
grandparent
.

9.3.1 Class Reptilia
11.11.11 Kingdom Plantae
11.4.5 Advantages of a Triple-Key Forest Table
The simpler “double-key” table can provide all the functionality that we required for
the Web chat application project in this book.Why then did we use a solution that
11 1089-9 CH11 6/26/01 7:36 AM Page 393
Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark.
394
Chapter 11 XML Data Storage Class: ForestHashtable
uses three keys? The reason is that we wanted our simplified chat application to
become the basis for a full Web e-commerce application. Using “three-key” tables to
hold hierarchical data enables some additional methods that provide superior perfor-
mance and simplified programming requirements.
Table 11.3 lists some of the methods that are especially easy and efficient to imple-
ment using a triple-key table to contain nodes.We will discuss these methods and oth-
ers as well. For further elucidation, try to implement these methods using only a
double-key table design, and then use a triple-key table design.
Table 11.3 Methods Made Easy by Triple-Key Table Design
Method of Node Key Relation to Implement Method
isNodeAChildOfRoot() aKey <> bKey and bKey = = cKey
hasNodeAGrandParent() bKey <> cKey
getGrandParentOfNode() cKey = = Grandparent’s aKey
getGrandChildrenOfNode() aKey = = Grandchildren’s cKey
Some might say that if these methods are necessary to obtain sufficient speed from a
tree, the tree is not well-designed in the first place.The argument is that putting in
extended family methods defeats the purpose of the structure and draws arbitrary,
nonintuitive boundaries between objects. (To take this to an extreme, why not have a
getGreatGrandparent()
or a
getGreatGreatGrandparent()

Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark.
395
11.4 ForestHashtable Maps Data Trees
as well.This information is thus also intrinsic to the design of the
ForestHashtable
’s
triple-key table data storage (remember, although this is stored here in a
Hashtable
,it
could as well be in a relational or object-oriented database table).
Again, trying to find the Boolean return value for this method is more difficult
with a double-valued key system.You have to access the parent node keys and deter-
mine whether the parent has a parent, which is equivalent to determining whether the
parent is a root node.The information is not intrinsic to the node, in other words.
Remember, a node can be big and expensive to request over a network.You might
want to just get the parents’ keys, not all the objects in the node. But then, if you are
asking this question, you probably will access the rest of the node as well, which means
that you have a choice of either two object retrievals sometimes or one object retrieval
always.
11.4.8 getGrandParentOfNode( )
If you use triple-key tables, then you can directly index the grandparent node of any
node in a forest. Besides getting the value of the
hasNodeAGrandparent()
method, the
triple key gives you the index for the nodes row in the table. As the second column in
Table 11.3 shows, you only need to find the row in the table with a primary key value
equal to the third value in the triple key of the current node (that is, the grandchild
node).
With double-key tables, you must retrieve the keys from the parent node of a given
node to find and retrieve the grandparent of the given node. Again, how big a deal

used to traverse and display filesystem contents in a user interface display.
Drilling Down the Hierarchy
When it becomes necessary to drill down into a tree data structure, the selected child
becomes the new parent, and its child nodes, if any, must now be found by the soft-
ware and displayed in the user interface.Would it not be advantageous to have already
retrieved the required child nodes? Of course, we do not mean that we should try to
guess successfully which new parent node will be selected by the user ahead of time.
Using a
ForestHashtable
, we can easily prefetch and cache all the “next-genera-
tion” nodes in an XML data store.We can do this using the
getGrandchildrenOfNode()
method, discussed previously.This way, we can search
through a much smaller data set that is guaranteed to contain all the new child nodes
that we must find instead of making many new requests from a database.
Climbing Up the Hierarchy
In the opposite direction, the
ForestHashtable
can more quickly find the parent of a
node (if available) and the grandparent of a node (if available).This might not be
important if the parent can be retrieved quickly and used in turn to find the grandpar-
ent. However, there may be cases in which small savings add up over time.Try iterat-
ing cousin nodes with two-valued versus three-valued keys to see the difference that
the grandparent key can make.
11.4.12 Faster Response and Reduced Bandwidth
As you have seen, this capability of the
ForestHashtable
to prefetch grandchildren of
a node comes from the fact that it simulates a database table that uses three keys.The
advantages of this design show themselves in two ways: faster response to user actions

</Class>
</Phylum>
<Phylum name=” Chordata”>
<Class name=” Mammalia”>
<Order name=”Carnivora”>
</Order>
<Order name=”Primates”>
<Family name=”Hominidae”>
<Genus name=”Homo”>
<Species name=”sapiens”>
</Species>
<Species name=”hacker”>
</Species>
</Genus>
</Family>
</Order>
</Class>
<Class name=” Reptilia”>
</Class>
</Phylum>
</Kingdom>
The plant kingdom classification would have to be in a different XML document,
unless we added another higher-level root element (for example, using the tag pair
<Life></Life>
.That would then be the parent of both the animal kingdom and the
plant kingdom nodes.
11 1089-9 CH11 6/26/01 7:36 AM Page 397
Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark.
398
Chapter 11 XML Data Storage Class: ForestHashtable

, and that is where it contains the nodes of data. However, it also con-
tains two other
Hashtable
member objects that it uses to optimize the processing of
the
BonNode
objects that it stores.
11.5.1 NodeKey Gives Direct Access to a BonNode
As we have seen,
NodeKey
objects are used as
Hashtable
keys for keeping the
BonNode
s
objects in a
ForestHashtable
.Therefore, having a
NodeKey
allows direct access to its
associated
BonNode
. If you do not have a
NodeKey
for a
BonNode
, you have to search the
entire
ForestHashtable
using an

Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark.
399
11.5 Caching Keys for Fast Node Access
There are two different
NodeKey
caches because each uses a different type of key
object to store its
NodeKey
objects.The
Hashtable
key used by
nodeNameHashtable
contains the
nodeName
value for the
BonNode
whose
NodeKey
is being cached (some-
times with a prefix identifying the HTTP session, and optionally the node-creation
time). The
pathNameHashtable
object uses instead a key that describes the path in the
data tree from a root node to the
BonNode
whose
NodeKey
is being cached.
The two different caches for
NodeKey

class.There
we point out that it eventually depends on the
addChildNodeToNonRootNode()
method
in the
ForestHashtable
class, which will be discussed in the section “Session-Visible
Children of Nonroot Nodes.” You should see by now that to get a full understanding
of how a
nodeKeyHashtable
works, you will need to understand both the
BonForumEngine
and the
ForestHashtable
classes.That will most likely require study-
ing their source code, as well as Chapter 8.
The addNode() Method’s nodeKeyHashtable Cache
In the
ForestHashtable
class, the public classes that add data nodes all call a private
class called
addNode()
.The
addNode()
method uses the
nodeNameHashtable
to cache
the
NodeKey
of the

nodeKeyKeyPrefix
that is set to
the value
NO_NODEKEY_KEY_PREFIX
when the root node and its children are added to
initialize the Web application database.The same argument is set instead to the value
SESSION_ID
or
SESSION_ID_AND_CREATION_TIME
whenever a node is added that is at
least a grandchild of the root node.
if(nodeKeyHashtableName.equals(“nodeNameHashtable”)) {
// Hashtable is synchronized, but we need to sync two together here:
String nodeKeyKey = null;
synchronized(this) {
try {
this.put(nodeKey, node);
}
catch(Exception ee) {
log(sessionId, “err”, “EXCEPTION in addNode():” + ee.getMessage());
ee.printStackTrace();
}
if(nodeKeyKeyPrefix == SESSION_ID) {
// allows only one key per session
// use this option to reduce size of table
// by not storing key to nodeKeys not needed
// (examples: message keys, messageKey keys).
nodeKeyKey = sessionId + “:” + nodeName;
}
else if(nodeKeyKeyPrefix == SESSION_ID_AND_CREATION_TIME) {

portion of the key for a selected list of node
names (see
ForestHashtable
, property
UniqueNodeKeyKeyList
).That option reduces
the size requirements of the
nodeKeyHashtable
(for example, by not storing all the
message
nodeKey
keys).
String hostNodeKeyKey = sessionId + “_” + creationTimeMillis + “:host”;
session.setAttribute( “hostNodeKeyKey”, hostNodeKeyKey );
nameAndAttributes = “actorNickname”;
content = actorNickname;
forestHashtableName = “bonForumXML”;
obj = bonForumStore.add( “bonAddElement”, hostNodeKeyKey, nameAndAttributes,
content, forestHashtableName, “nodeNameHashtable”, sessionId );
11.5.4 PathNameHashtable
The other
Hashtable
that a
ForestHashtable
uses, besides itself and the
nodeNameHashtable
, is called the
pathNameHashtable
.The source code that creates that
variable is shown here:

, however, you should also refer to the
information in Chapter 8.
Hashtable Key Used by pathNameHashtable
The
pathNameHashtable
uses a key for each
NodeKey
stored in it that is made by con-
catenating the names of all the data nodes starting from the root node and ending
with the node whose
NodeKey
is being cached, with a period separating each node
name used. An example of one of these keys is the following string value:
bonForum.things.Subjects.Animals.Fish.Piranha
PathNameHashtable and Chat Subjects
At present, the
pathNameHashtable
is used only when adding the tree of subject cate-
gories to the
bonForumXML ForestHashtable
.We have adopted a rule that no duplicate
11 1089-9 CH11 6/26/01 7:36 AM Page 401
Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark.