RE: Walking the DOM (was: XML APIs)

John Cowan wrote,

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

OK, I agree that this check is O(1). However, that's only
because the granularity of the check is so coarse: a single
document-level timestamp will cause a lot of unnecessary
invalidation ... I suspect that it would make the performance
of modifying a document via iterators unacceptably poor.

Moving to per-node timestamps would reduce the amount of
unnecessary invalidation, and preserve the O(1) check,
but at the cost of making tree modifications O(log n).

Cheers,


Miles

-- 
Miles Sabin                          Cromwell Media
Internet Systems Architect           5/6 Glenthorne Mews
+44 (0)181 410 2230                  London, W6 0LJ
msabin@cromwellmedia.co.uk           England

Received on Friday, 13 November 1998 07:36:30 UTC