Re: list strawman

[Ted Dennison<dennison@telepath.com>]

In article <u7kqu3yux.fsf@gsfc.nasa.gov>, Stephen Leake says...
>One issue I did not point out is the changes I had to make to the
>spec. In particular, I had to declare "List" as tagged, and use 'class
>in a couple places. Do you have any objections to that?

If you could move the tagged-ness to the private section, I'd prefer that done.
Since its done entirely for implmentation reasons (right?), that's where it
goes. There's no need to dictate taggedness onto someone who might not need it.

>> 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.
>
>Hmm. Adjust (List) explicitly sets the new list's iterator list to
>null. The source list iterators are preserved, and the new list has no
>iterators. 

Ahhh, that's right. I see it now.

>> 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)
>
>Actually Unchecked_Deallocation. That eventually calls Finalize on the
>iterator list, which should invalidate all of them. A test case
>proving this is needed.

I don't see how this makes the jump from your List object to the iterator
object. In order for an iterator to know that its list is gone, you'd have to
tell the iterator somehow. Something would have to set the Iterator's IA field
to null, or its IA.List or IA.I fields to null or something. Just dynamicly
deallocating the List's iterators from its iterator list isn't going to do that.
Instead you'd leave the iterator's IA field pointing off into space somewhere.
Are you setting that to null somewhere that I'm not seeing?

>There is a tradeoff between putting stuff in Initialize, and doing
>stuff with aggregates when an object is created. If you assign an
>aggregate to a Controlled object, Initialize is _not_ called (LRM 7.6
>(10)). So any place you assign an aggregate to a Controlled object,
>you have to be sure you do everything Initialize would do. I'm pretty
>sure I haven't got that right yet.

I wouldn't call it a trade-off exactly. I use initialize for allocating
nessecary substructures (with default clean values), and nothing else. Finalize
needs to undo that, along with undoing any bookeeping work that other routines
might do. Adjust needs to take the copied fields and make newly-allocated unique
copies of any pointed-to objects (or not in the case of iterators). Every
Initialize will eventually get a finalize, as will every Adjust.

I think it would have helped me to see a matrix something like this:

Operation
Example           Controlled Primitives called
------------------------------------------------------------
Declaration  
A : Mytype;       Initialize (A);
Initialization 
A : Mytype := B;  Adjust (A);
Assignment
A := B;           Finalize (A); {fields copied} Adjust (A);

{Note: Often a temporary B will be created during assinment too,
in which case we have:
                 Adjust (Temp_B); Finalize (A); Adjust (A); Finalize (Temp_B);
)

>I just noticed that the No_Item exception is declared within the
>generic Lists.Unbounded package, which means we get a different one
>for each instantiation. We probably want to move that up to Lists or
>ACL.

That's a good point. We may want to move that up when we get more than one. Then
again, we could leave a renaming of it down here too.

>> It also looks like it is possible to get rid of all list searches in iterator
>> manipulations. <snip>
>
>Are you sure you are considering all the nasty things users can do?
>Like declaring several iterators to a list, but not actually using
>them for anything.

Yup. It doesn't matter. This is related to my previous point about getting rid
of dynamic allocations. If the list's iterator list node is actually part of the
iterator itself, then the iterator can just go straight to its own node to move
itself from one iterator list to another. Unfortunately, this requires that the
List's iterator lists are doubly-linked. It gets to be a bit hairy.

>> 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.
>
>I think that's a Bad Thing. But if it were clearly documented, maybe
>it would be ok.

I think its mostly an issue of how it could be used. If its reasonable to do
splices inside of an iteration loop, then we may want to do it. I'm not feeling
creative enough to visualise a need for it though.

>> Anyway, sorry for all the criticism. Good work. Believe me, I know
>> how much effort it is to try to get this right. :-)
>
>Hey, it was actually fun! It made me appreciate having written SAL;
>having a working low-level list abstraction makes it easier to
>implement the safe iterators. And doing this clarified some of the
>design issues in SAL.

I think it will actually be quite useful for 3rd-party component libraries to do
this, as they will be able to provide their own functionality as sort of an
extension to the "training-wheels" standard version. :-)

>You might consider using my Test_Storage_Pools package in your test
>harness; it makes it possible to find memory leaks as part of testing.

I actually have been checking for leaks too, with some code internal to the
package. I essentially increment an alloction counter at every "new" call,
decrement it at every Unchecked_Deallocation, and make sure its 0 when the Empty
list (declared in the spec) gets finalized. Its not task-safe, but it works for
a test.

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