W3C home > Mailing lists > Public > www-dom@w3.org > October to December 1998

RE: Walking the DOM (was: XML APIs)

From: Miles Sabin <msabin@cromwellmedia.co.uk>
Date: Fri, 13 Nov 1998 12:34:56 -0000
Message-ID: <c=US%a=_%p=Cromwell_Media%l=ODIN-981113123456Z-22042@odin.cromwellmedia.co.uk>
To: "'John Cowan'" <cowan@locke.ccil.org>, "'DOM List'" <www-dom@w3.org>
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).



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

This archive was generated by hypermail 2.3.1 : Tuesday, 20 October 2015 10:46:05 UTC