Re: In a pickle.

["chris.danx" <spamoff.danx@ntlworld.com>]

Stephen Leake wrote:
> "chris.danx" <spamoff.danx@ntlworld.com> writes:
 >
> I've just put up my Grace.Lists implementation; see 
> 
> http://users.erols.com/leakstan/Stephe/index.html
> 
> It does "safe" iterators; iterators are invalidated if the item they
> point to is deleted, etc.

Nice.

>>I want operations on a node which would invalidate iterators to take
>>place only when one iterator references a node. For example deleting
>>a node should only occur when one, and only one iterator points to
>>it (if more than one iterator points to the node an exception should
>>occur).
> 
> 
> Grace does not require this. I guess you're doing something like
> "reference counting garbage collection". 
> 
> So Grace iterators are not exactly what you want. But there may be
> some implementation ideas you can use.

I am undecided whether to invalidate all iterators like your Grace 
implementation or disallow deletion when multiple iterators point to the 
same iterator.  Chris Greins code has shed some light on the using 
aggregates which I was unaware of and this makes the use of temporaries 
unnecessary (didn't know how to use tagged types with aggregates).



>>First I tried a scheme involving counting the number of iterators
>>that reference a node, but this approach lead to a very complex
>>implementation, so it's back to the drawing board. :(
> 
> Complexity is sometimes necessary :).

It's a simple idea though.  Why do simple ideas have to be so complex? :)


> Yes, using temporaries causes complexity. You might try using
> aggregates instead; that gives you more direct control over what's
> going on. Neither Initialize nor Finalize is called on an aggregate.

Will do!

>>Now I know why John English skipped the issue in "ada: the craft..."
>>(I didn't fully appreciate Johns' warning on this) and why other
>>list implementations either skip the issue or are quite complex.
> 
> Welcome to the club :). Implementing the Grace iterators was much more
> challenging than I thought it would be. And I haven't really tested it
> yet; that's more work than I want to do right now.

Glad to see I'm not the only one :)

>>Is there a better solution to this problem???
> 
> Since I'm not sure what your real top level problem is, I can't say.
> Can you say more about why you want reference counted iterators?

I don't really know why.  My logic was that if the programmer calls 
delete on a node referenced by more than one iterator, there's a good 
chance it is an error and they should be warned.  I suppose a better 
idea would be to let the programmer delete the node and raise a 
constraint error when an attempt is made to use the iterator (just 
realised the programmer may really want to delete the node).

I'm really not sure what do, but after looking at Chris Greins paper the 
method of pointing Iterators directly at nodes doesn't seem so good. 
Maybe pointing Iterators to a unique object which points the node is 
better.  Need to experiment and have a look at how others have got round 
this problem.


Chris
-- 

to reply change 'spamoff' to 'chris'