Re: Walking the DOM (was: XML APIs)

Miles Sabin wrote:

> Yes, but how can an implementation tell whether or not an iterator
> is active? The only way is for it to wait for it to become
> unreferenced, and the only way of knowing that is to wait for it
> to be GC'd and have it's finalize method called ... weak
> references work in more or less the same way: there's a bit of JVM
> support, but the mechanism is still dependent on GC.

No, the way is for the iterator to check "Have I been invalidated?"
and if so take recovery action (notify the user, restart the
tree walk, or whatever).

This can be achieved by having a per-document timestamp and one
in each iterator.  An iterator captures the document timestamp
when it is created, and checks on each operation.  These are O(1)
actions.  Whenever the document is modified, the timestamp is
updated (O(1) action).  An iterator is invalid iff its timestamp
is older than the document timestamp.

> The upshot is that whatever you as the programmer might think of
> as the number of "active" iterators, the implemenations idea of
> the number of active (or, equivalently, not known to be inactive)
> iterators could be significantly greater ... potentially
> unnacceptably so.

There is no cost under the above scheme to invalidating iterators
that are not active, because it is done lazily: the iterator doesn't
find out that it is invalid until the next iter is taken.

The cost is that an iterator may be inactivated when the change to
the doc was in a region that the iterator will not traverse.

-- 
John Cowan	http://www.ccil.org/~cowan		cowan@ccil.org
	You tollerday donsk?  N.  You tolkatiff scowegian?  Nn.
	You spigotty anglease?  Nnn.  You phonio saxo?  Nnnn.
		Clear all so!  'Tis a Jute.... (Finnegans Wake 16.5)

Received on Thursday, 12 November 1998 15:54:10 UTC