Re: list strawman

[Ted Dennison<dennison@telepath.com>]

In article <ug05j42sp.fsf@gsfc.nasa.gov>, Stephen Leake says...
>
>I've done a priliminary implementation of
>http://www.telepath.com/dennison/Ted/Containers-Lists-Unbounded.ads.html
..
>This was an interesting excersize. I got quite stuck on making the

Yes it is, isn't it? :-)

>iterators safe, while at the same time not requiring the user to use
>'Unchecked_Access. A hint from http://homepage.ntlworld.com/ramatthews/
>(Robert A. Matthews' GAPSE) set me straight; use a layer of indirection.

I ended up doing almost exactly the same thing. 

>The final implementation is quite complex (and I haven't done sort
>yet). I don't think I will ever use this package in a real project.
>Just writing all the tests to prove that iterators actually are safe
>will take quite a while. But it is an interesting example of what can
>be done.

Things that I have stumbled over so far:

The Iterator Adjust routine needs to add the new iterator to its list's iterator
list(s). You do this.

The List Adjust routine should wipe out any iterator lists, as they belong to
the source List (and visa versa), not the target. You don't deal with this.

The List Finalize routine needs to invalidate any iterators on the list's
iterator list. You don't do this. (The comment says you do, but you just seem to
be calling Unchecked_Conversion on the list header, unless I am missing
something)

The Iterator Finalize routine needs to remove its entry from the list it belongs
to's iterator list. You do this.

The List and Iterator Initialize routines have to allocate new list and iterator
structures respectively before they do anything else. The list Initialize does
this, but the iterator one looks like it tries to dereference the (null) pointer
immediately. You say you've tested with iterators, so you must have gotten this
to work somehow, but I'm mystified as to how (unless it was the passive iterator
generic).

A subtle point: Iterators may have the "No_Item" condition, but still be validly
associated with a list (eg: An empty list that you want to add items to with
"Insert").

When elements are removed from a list, you have to invalidate any iterator
entires that may point to that element. It doesn't look like this is being done
in "Remove" (end or iterator versions).

Item doesn't seem to be checking for the No_Item condition. 

Perhaps something is going on in the Sal.Poly.Lists.Double package with
iterators to take care of these last two issues. I don't have it, so I can't
tell. But I'm guessing not, since the iterator is defined in the private part,
and those don't look like child packages.

Efficiency issues:

I discovered it is possible to get rid of all dynamic allocations in iterator
manipulations. This can be accomplished by using an aliased subrecord within the
iterator itself as the List's iterator list node. A greasy hack, but it appears
to work. I think its actually *less* error prone this way, as you don't have to
worry about keeping a 1-to-1 correspondence between iterators and allocated
iterator list nodes from the lists's side. The only safety issue is implementing
the Adjust and Finalize routines correctly, rather than implementing every List
and Iterator manipulation routine correctly.

It also looks like it is possible to get rid of all list searches in iterator
manipulations. This can be accomplished by putting a node for the iterator in
lists for both the list (for splice and merge) and the pointed-to element (for
everything else). I haven't finished implementing this yet, so I'm not entirely
sure, but it looks like this method can also be used to make all iterator ops
O(1). A nice side benifit to doing this is that iterators can be made to travel
with the element when it chages lists (via Splice). We will have to discuss if
this is a Bad Thing or a Good Thing from a user perspective.

Anyway, sorry for all the criticism. Good work. Believe me, I know how much
effort it is to try to get this right. :-)

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.