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

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 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Friday, 22 June 2012 06:13:46 GMT