[cfe-dev] [libc++] debug mode

[Steven Watanabe]

AMDG

On 09/19/2011 09:07 AM, M.E. O'Neill wrote:
> 
> As outlined, yes, I was doing all-iterator invalidation, as happens in std::string, because that's simpler and quick to explain (and I've experience implementing it!).
> 
> But I think the method does generalize.  In situations where *some* of the iterators get invalidated, you need to do a little bit more work.  You need to maintain an invalidation log:
> 
> - For each (active) tag value, associate an optional record.  Initially there is no record for a tag.
> 
> - When an object updates in a way that invalidates iterators, add a record to its (now former) tag saying enough about what the operation was that you can know what got invalidated (e.g., for vector, the invalidated range, or possibly better, the range that remains valid).  Also, record the container's new tag.
> 
> Now when the tags don't match, instead of just blowing up, you use your tag to follow update chain through all the tags and see if you're still valid through the operations that have occurred.  You'll either find the new tag you need, or find you're invalid.
> 
> There are details, of course, such as reference counting things so that it all cleans up nicely (i.e., you only keep as much of the invalidation log as you actually need), and handling tag collisions for record information (because you really shouldn't *ever* fail for valid code, even if it is more likely that the user will be struck by lightning while in the bathroom).  But I think those details are pretty straightforward.
> 

Reference counting the history doesn't sound
at all straightforward to me.  The methods I
can think of all have some problem:

a) When a history element is created, set the
   reference count to the number of iterators
   it affects.  Counting these iterators requires
   as much work as just marking them as invalid.
b) When a history element is created, set the
   reference count to the total number of
   iterators that currently exist.
   1) When an iterator is destroyed, it has
      to adjust the reference counts of all
      the iterators
   2) A single long-lived iterator can cause
      the history to accumulate indefinitely.
c) We can solve b.2 by storing the reference
   count incrementally.  i.e. If the reference
   count of history item 1 is 3 and the reference
   count of history item 2 is 5, then store
   the values 3 and 2.  Then we one need to
   count in the first item in the list.  This
   still leaves problem b.2, however.

In Christ,
Steven Watanabe

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 490 bytes
Desc: OpenPGP digital signature
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20110919/4895b31a/attachment.sig>