On Jan 14, 2007, at 22:51, J.Pietschmann wrote:

Andreas L Delmelle wrote:
Based on Jörgs statistics, I'd say that the number of children will most likely never reach the level where using direct index- based access (ArrayList) has its benefits over traversing a tree of references (LinkedList).

There may be FOs, specifically fo:flow and fo:table-body, which may
have hundreds of children in real documents.

If the FOs use access functions for the children, even for adding,
each FO can implement a mechanism which suites its purposes best. In
particular, page masters and tables can store the regions in typed
fields, FOs which don't have children can get rid of the field
completely.

This happens already for some FOs. Tables for instance, override addChildNode() and store only bodies as their 'child nodes'. The header and footer have separate typed fields, the columns end up in a separate standard List. Behavior for markers is another example, they too end up in a separate collection (map).

I've already been experimenting locally with removing the List member, and replacing it with pointers to the neighbors. As I re- implemented FObj.addChildNode(), it occurred to me that FOs with a possibly larger amount of children would need to traverse the entire list to append child nodes to the end. For a handful of children, this costs virtually nothing, but as the list gets bigger... Could easily be solved though for the applicable FOs, by keeping a reference to the last added child, and giving it an addSibling() method.


I'm not sure whether the layout engine places any restrictions on the
access to FO children. Is it possible that access is not random?

FTM, there are only a handful of places in the code where the childNodes list is accessed using an index. The only way it can be accessed by classes outside the fo package is through FObj.getChildNodes(), and that method returns a ListIterator, not the list itself. The LMs only need access to these iterators while creating their childLMs, which is done in forward sequential order, i.e.

for (Iterator i = AbstractLM.fobjIter; i.hasNext();) { ... }

[Note: these are ArrayLists we're talking about. Iterators are far from the best approach with lists implementing RandomAccess. Not that this matters much if the lists are small...]

This fobjIter is created in the constructor of the LM. IIC, this means that there is currently no way to, for example, instantiate the FlowLM as soon as the first endBlock() event occurs, and keep extending the flow's list of child nodes in a different thread. The FlowLM's fobjIter will then throw a ConcurrentModificationException().

In the structure I'm currently playing with, it would be possible to construct an iterator over an FObj whose child nodes are not all known, move to the last node in the list, put the iterator in a stack (or keep a reference as an instance member), continue adding nodes in another thread, return, and continue iterating (a call to next() will then return the first node that was added after the iterator was paused).

That would be mighty dangerous if the access to the nodes was not so predictable, but as it stands now, this could turn out to be a benefit, if documented properly. Removal from and addition to the tail of the list are never a problem. The iterator will simply keep following the following- sibling reference until it is null. The head of the list might become a problem if one needs a decent implementation of nextIndex() and previousIndex(). If we never really need the index, then the fact that a child was added at a previous position will simply make the iterator go back a few steps further than where it started.



Cheers,

Andreas



Reply via email to