List container strawman 1.3

List container strawman 1.3

[Ted Dennison]

The latest (1.3) version of the list container strawman is available on my
website at
http://www.telepath.com/dennison/Ted/Containers-Lists-Unbounded.ads.html .

This version has the following changes:

Routines were added to convert between unbounded arrays and lists, and unbounded
array versions of "&" were added.

A direction type was added. Pop and Push were changed to use this type (and were
changed to more algorithm-neutral names). Many of the iterator routines have
been changed to use this type as well. In some cases this adds new
functionality.

The iterator has been changed to support a totally "safe" (error detecting)
implementation. Many of the iterator routines were redesigned a bit to support
this.

The Splice routine was added to support moving list elements from one list to
another efficiently. (Perhaps version with "from" and "to" iterators for the
source list would be useful too?)

Two companion routines for "Sort" were added. An embedded package, rather than a
child, was used to support this (thanks to Nick for this idea). This gives
sorted lists the same level of functionality as the STL supports for the
equivalent concept.

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

Re: List container strawman 1.3

[Ted Dennison]

In article <DzdP7.48986$xS6.81471@www.newsranger.com>, Ted Dennison says...
>
>The latest (1.3) version of the list container strawman is available on my
>website at
>http://www.telepath.com/dennison/Ted/Containers-Lists-Unbounded.ads.html .

OK. I will say that right now I'm pretty satisfied with this version. However
there are two issues with it already. :-(

The first is this:
>The Splice routine was added to support moving list elements from one list to
>another efficiently. (Perhaps version with "from" and "to" iterators for the
>source list would be useful too?)

I think the "from" and "to" version may be nessecary.

The other issue is that this version won't actually compile as-is under Gnat.
(!) Every routine with both List and Iterator types complains that it can't
dispatch on both types. Frankly, I'm not sure I want it dispatching at all. I'd
think that since the user's view at this point is simply a private type, then
these routines would not be created as tagged primitives. 

Anyway, the only way I know to un-primitive a subprogram is to tack 'Class on
the end of the type. Gnat rejects that too, saying that 'Class only works on
tagged types. So first it says the types are tagged, then it says they aren't. I
sure wish it would make up its mind! :-)

Assuming these are valid errors, does anyone know how to fix this?

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

Re: List container strawman 1.3

[Vincent Marciante]

Ted Dennison wrote:
> 
> Anyway, the only way I know to un-primitive a subprogram is to tack 'Class on
> the end of the type. Gnat rejects that too, saying that 'Class only works on
> tagged types. So first it says the types are tagged, then it says they aren't. I
> sure wish it would make up its mind! :-)


You could try something like:


package xxxxx is

    type y_type is ....

    procedure primative (p : y_type);

    ...

    package nonprimative is
        procedure z (p : y_type);
        ...
    end nonprimative;

    procedure z (p : y_type) renames nonprimative.z;
    
    ...

end xxxxx;


I did not compile to check for sure that xxxx.z is not primative
but nonprimative.z definately is.


Vinny

Re: List container strawman 1.3

[Jeffrey Carter]

Ted Dennison wrote:
> 
> Routines were added to convert between unbounded arrays and lists, and unbounded
> array versions of "&" were added.

A couple of nits:

That's not an unbounded array; that's an unconstrained array, as the
package comments correctly say.

> The iterator has been changed to support a totally "safe" (error detecting)
> implementation. Many of the iterator routines were redesigned a bit to support
> this.

I thought we'd agreed not to call the type that indicates a position in
the list "Iterator". IIRC, you thought "Location" was a better name.

> The Splice routine was added to support moving list elements from one list to
> another efficiently. (Perhaps version with "from" and "to" iterators for the
> source list would be useful too?)

I have no idea what Splice does.

-- 
Jeff Carter
"You empty-headed animal-food-trough wiper."
Monty Python & the Holy Grail

Re: List container strawman 1.3

[Ted Dennison]

In article <3C0D8D06.DD4F09F2@acm.org>, Jeffrey Carter says...
>
>I thought we'd agreed not to call the type that indicates a position in
>the list "Iterator". IIRC, you thought "Location" was a better name.

Part of the logic for that was that we weren't dealing with a full safe
iterator, but rather with something that represents a certian location within a
certian associated list. Thus "iterator" was a bit misleading for some. Now it
isn't.

>> The Splice routine was added to support moving list elements from one list to
>> another efficiently. (Perhaps version with "from" and "to" iterators for the
>> source list would be useful too?)
>
>I have no idea what Splice does.

It basicly moves list items from one list to another without copying them.
Insert does roughly the same thing, but makes copies rather than moving the
actual elements from one list to another.

I picked the name because that is what the STL named the same routine, and it
seemed like a good enough name to me.

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

Re: List container strawman 1.3

[Jeffrey Carter]

Ted Dennison wrote:
> 
> In article <3C0D8D06.DD4F09F2@acm.org>, Jeffrey Carter says...
> >
> >I thought we'd agreed not to call the type that indicates a position in
> >the list "Iterator". IIRC, you thought "Location" was a better name.
> 
> Part of the logic for that was that we weren't dealing with a full safe
> iterator, but rather with something that represents a certian location within a
> certian associated list. Thus "iterator" was a bit misleading for some. Now it
> isn't.

Yes, it is. An iterator, by definition, is something that iterates.
Given

X : Iterator;

X does not Iterate.

-- 
Jeff Carter
"You empty-headed animal-food-trough wiper."
Monty Python & the Holy Grail

Re: List container strawman 1.3

[Jean-Marc Bourguet]

Ted Dennison<dennison@telepath.com> writes:

> Assuming these are valid errors, does anyone know how to fix this?

Make the List and Iterator type a simple record containing one element
of the tagged record type.

-- 
Jean-Marc

Re: List container strawman 1.3

[John English]

Ted Dennison wrote:
> 
> The latest (1.3) version of the list container strawman is available on my
> website at
> http://www.telepath.com/dennison/Ted/Containers-Lists-Unbounded.ads.html .

1) Would it be a good idea to rename the Direction values Front, Back
   as Forwards, Backwards or To_Front, To_Back to make it clearer
   what they mean?

2) Would it also be a good idea to have a default value of Forward
   (whichever of Front and Back that corresponds to) for all Direction
   parameters?

-----------------------------------------------------------------
 John English              | mailto:je@brighton.ac.uk
 Senior Lecturer           | http://www.comp.it.bton.ac.uk/je
 Dept. of Computing        | ** NON-PROFIT CD FOR CS STUDENTS **
 University of Brighton    |    -- see http://burks.bton.ac.uk
-----------------------------------------------------------------

Re: List container strawman 1.3

[John English]

Ted Dennison wrote:
> The other issue is that this version won't actually compile as-is under Gnat.
> (!) Every routine with both List and Iterator types complains that it can't
> dispatch on both types. Frankly, I'm not sure I want it dispatching at all. I'd
> think that since the user's view at this point is simply a private type, then
> these routines would not be created as tagged primitives.

Why does the iterator type need to be controlled? What's your mental
model of what an iterator consists of? Mine generally says that an
iterator contains a couple of pointers to a list somewhere else,
but that the iterators aren't responsible for deallocating that
list... is this something caused by the safe iterator requirement
perhaps? (Which I disagree with, incidentally... safe iterators
can probably be built on top of unsafe ones, but starting with
safe ones means a lot of possibly unnecessary overhead.)

-----------------------------------------------------------------
 John English              | mailto:je@brighton.ac.uk
 Senior Lecturer           | http://www.comp.it.bton.ac.uk/je
 Dept. of Computing        | ** NON-PROFIT CD FOR CS STUDENTS **
 University of Brighton    |    -- see http://burks.bton.ac.uk
-----------------------------------------------------------------

Re: List container strawman 1.3

[Ted Dennison]

In article <3c0ddc67$0$196$626a54ce@news.free.fr>, Jean-Marc Bourguet says...
>
>Ted Dennison<dennison@telepath.com> writes:
>
>> Assuming these are valid errors, does anyone know how to fix this?
>
>Make the List and Iterator type a simple record containing one element
>of the tagged record type.

I tried that and it works. That may end up being the solution.

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

Re: List container strawman 1.3

[Ted Dennison]

In article <3C0E1E7E.CA7113F4@brighton.ac.uk>, John English says...
>Ted Dennison wrote:
>> 
>> The latest (1.3) version of the list container strawman is available on my
>> website at
>> http://www.telepath.com/dennison/Ted/Containers-Lists-Unbounded.ads.html .
>
>1) Would it be a good idea to rename the Direction values Front, Back
>   as Forwards, Backwards or To_Front, To_Back to make it clearer
>   what they mean?

I don't think those alternatives would make sense in the case of the list end
insertion routines. However, I'll grant that the terminology makes one of the
other routine parameter names a bit awkward (iterator-based "Remove:). But the
alternatives make it even moreso. I'm also generally not a fan of putting
articles in identifiers. Perhaps that's just an overreaction to seeing people
abuse it by making whole phrases. :-)

There is essentially a choice between biasing the terminology toward ends,
directions, or making two types. I think we should be able to get by without two
types. Biasing it toward directions makes at least two non-defaulted parameters
a bit awkward. Biasing it toward ends makes one defaulted paremeter a little
more awkward (it would still be awkward either way because its a complicated
concept to start with).

What we have right now for usage (assuming instantiation as "Lists") is:
1)
  Lists.Insert
     (Target      => Car_List,
      New_Element => Honda,
      List_End    => Lists.Front);

  Lists.Next
     (Location => Car_Location,
      Toward   => Lists.Front
     );

Re: List container strawman 1.3

[Ted Dennison]

In article <3C0E1FA1.45A38A75@brighton.ac.uk>, John English says...
>
>Ted Dennison wrote:
>> The other issue is that this version won't actually compile as-is under Gnat.
>> (!) Every routine with both List and Iterator types complains that it can't
>> dispatch on both types. Frankly, I'm not sure I want it dispatching at all. I'd
>> think that since the user's view at this point is simply a private type, then
>> these routines would not be created as tagged primitives.
>
>Why does the iterator type need to be controlled? What's your mental
>model of what an iterator consists of? Mine generally says that an

An iterator doesn't but a *safe* iterator does (as the list needs to know when
its iterators go away). Perhaps I should have given this bit more fanfare, but
this strawman version is using the fully-safe iterator approach. That rounds out
the list of approaches used nicely. 

I think from a user-perspective it isn't a big change. The main change is that
you no longer have to provide a list with the iterator for every op, which has
to be viewed as an improvement. From an implementation perspective it
complicates things a bit, but I don't think its fatal to real-time use anymore,
which was my main concern. 

I've now provided an example of each kind of iterator. We need to make a
decision on this issue.

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

Re: List container strawman 1.3

[Simon Wright]

John English <je@brighton.ac.uk> writes:

> Why does the iterator type need to be controlled? What's your mental
> model of what an iterator consists of? Mine generally says that an
> iterator contains a couple of pointers to a list somewhere else, but
> that the iterators aren't responsible for deallocating that
> list... is this something caused by the safe iterator requirement
> perhaps? (Which I disagree with, incidentally... safe iterators can
> probably be built on top of unsafe ones, but starting with safe ones
> means a lot of possibly unnecessary overhead.)

The BC Iterators are controlled so that creating an Iterator _can_
Lock the container it's iterating over, and deleting the Iterator (by
exiting the scope) will Unlock.

That said, the implication is that only one Iterator can be active for
a given container at any one time. Actually using such a beast is
going to be tricky, I think.

The C++ BCs didn't address this problem as far as I can see (there are
no substantive comments in the source ..)

-- 
Simon Wright                         Email: simon.j.wright@amsjv.com
Alenia Marconi Systems                     Voice: +44(0)23 9270 1778
Integrated Systems Division                  FAX: +44(0)23 9270 1800

Re: List container strawman 1.3

[Ted Dennison]

In article <3C0E1E7E.CA7113F4@brighton.ac.uk>, John English says...
Arg! About 2/3's of my reply to this seems to have gotten cut off. Perhaps
that's not such a bad thing, but I really should address John's second point.

>2) Would it also be a good idea to have a default value of Forward
>   (whichever of Front and Back that corresponds to) for all Direction
>   parameters?

If we do this for the end insertion/deletion routines, we bias this package
towards being either a stack or a queue (stack if they are both the same value).
I suppose one possible middle postion would be to default insertion to go on the
"back", but not to put a default on remove.

"Side" wouldn't seem to have a natural default either.

"Next" probably should have a default. I'd think "Toward=>Lists.Back" would be
the natural one. Defaulting the end insertion routine to use "Back" would put
more teeth in this argument.

The rest have defaults already.

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

Re: List container strawman 1.3

[Larry Kilgallen]

In article <3C0E1E7E.CA7113F4@brighton.ac.uk>, John English <je@brighton.ac.uk> writes:

> 1) Would it be a good idea to rename the Direction values Front, Back
>    as Forwards, Backwards or To_Front, To_Back to make it clearer
>    what they mean?

To Front and To Back in several graphics programs means "all the way".
I prefer Forward and Backward for direction names.

Re: List container strawman 1.3

[Georg Bauhaus]

Ted Dennison <dennison@telepath.com> wrote:

:  Lists.Insert
:     (Target      => Car_List,
:      New_Element => Honda,
:      List_End    => Lists.Front);

Will "List_End" not be confusing if the abstract data type
is used for something other than a list?

Georg

Re: List container strawman 1.3

[Ted Dennison]

In article <9ulni1$d58$1@a1-hrz.uni-duisburg.de>, Georg Bauhaus says...
>
>Ted Dennison <dennison@telepath.com> wrote:
>
>:  Lists.Insert
>:     (Target      => Car_List,
>:      New_Element => Honda,
>:      List_End    => Lists.Front);
>
>Will "List_End" not be confusing if the abstract data type
>is used for something other than a list?

Perhaps, although I'd expect the package to typically be named something with
the word "List" in it, so its already there. 

The problem here is that the logical name seemed to be "End", but that's a
reserved word. Perhaps we should use "Side"?

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

Re: List container strawman 1.3

[Mark Lundquist]

"Ted Dennison" <dennison@telepath.com> wrote in message
news:%7sP7.49836$xS6.82296@www.newsranger.com...
> In article <3C0E1FA1.45A38A75@brighton.ac.uk>, John English says...
> >
> >Why does the iterator type need to be controlled? What's your mental
> >model of what an iterator consists of? Mine generally says that an
>
> An iterator doesn't but a *safe* iterator does (as the list needs to know
when
> its iterators go away).

Ted, why does a list need to "know" when its iterators go away?

Did you mean to say that safe iterator needs to know when its list has gone
away?

If so, a more lightweight approach is to use an access discriminant denoting
the list, e.g.:

    type Iterator (My_List : access List) is limited record
        My_Item : Item_Ptr;
    end record;

Then it is simply impossible for an Iterator to outlive its list!  The lack
of assignment is easily overcome:

    procedure Set (This : in out Iterator; To : Iterator) is
    begin
        This.My_Item := To.My_Item;
    end Set;

since composing ":=" is probably not an issue for iterators (i.e. the
ability to assign composite types having Iterator components).

Best,
Mark

Re: List container strawman 1.3

[Mark Lundquist]

"Mark Lundquist" <mlundquist2@attbi.com> wrote in message
news:aewP7.2149$dp6.152302@rwcrnsc54...
>
>
>     type Iterator (My_List : access List) is limited record
>         My_Item : Item_Ptr;
>     end record;
>

I should have added...:

The way you get one of these Iterators is like this:

    L : aliased List;
    .
    .
    .
    I : Iterator (L'Access);

(or allocate the List using 'new');

Re: List container strawman 1.3

[Ted Dennison]

In article <aewP7.2149$dp6.152302@rwcrnsc54>, Mark Lundquist says...
>Ted, why does a list need to "know" when its iterators go away?
>
>Did you mean to say that safe iterator needs to know when its list has gone
>away?

Yes in both cases. 

The iterator needs to know when its list goes away, so that users don't try to
whack at deallocated memory using the iterator. The list itself will have to
keep a mini-list of iterators to support invalidating iterators whoose
pointed-to item is removed. The list needs to know when an iterator has gone
away so that the iterator's entry can be removed from this internal list of
iterators.


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

Re: List container strawman 1.3

[Mark Lundquist]

"Ted Dennison" <dennison@telepath.com> wrote in message
news:DpxP7.50285$xS6.83694@www.newsranger.com...
> In article <aewP7.2149$dp6.152302@rwcrnsc54>, Mark Lundquist says...
> >Ted, why does a list need to "know" when its iterators go away?
> >
> >Did you mean to say that safe iterator needs to know when its list has
gone
> >away?
>
> Yes in both cases.
>
> The iterator needs to know when its list goes away, so that users don't
try to
> whack at deallocated memory using the iterator. The list itself will have
to
> keep a mini-list of iterators to support invalidating iterators whoose
> pointed-to item is removed. The list needs to know when an iterator has
gone
> away so that the iterator's entry can be removed from this internal list
of
> iterators.

That's what I figured you had in mind :-)...

Is there an advantage of this over the approach I described, viz. lifetime
"binding" of an iterator to a list using an access discriminant?  Maybe I'm
missing something...

In the access discriminator way, any state of affairs that could give rise
to a dangling iterator results in a compile-time error, and the safety comes
at no added run-time expense.  The chained iterator approach results in a
run-time exception if a dangling iterator is dereferenced, and it seems like
it takes a lot of overhead to set things up.  Just assigning an iterator

    I, J : Iterator
    .
    .
    I := J;

is going to entail a Finalize of I (unchain it), then an Adjust to link it
back in again.  It would be best to provide the Set procedure from my
example to circumvent this, but then you might as well make the Iterator
limited.

Also of course the control structure for the list must be allocated from the
heap, so that it can outlive the user's handle (since we have to keep the
iterator chain alive until the last one goes away)...

-- mark

Re: List container strawman 1.3

[Jeffrey Carter]

Georg Bauhaus wrote:
> 
> Ted Dennison <dennison@telepath.com> wrote:
> 
> :  Lists.Insert
> :     (Target      => Car_List,
> :      New_Element => Honda,
> :      List_End    => Lists.Front);
> 
> Will "List_End" not be confusing if the abstract data type
> is used for something other than a list?

Why would you use a list for anything other than a list?

-- 
Jeffrey Carter

Re: List container strawman 1.3

[Georg Bauhaus]

Jeffrey Carter <jeffrey.carter@boeing.com> wrote:
 
: Why would you use a list for anything other than a list?

If a queue/deque/stack is separately provided, I wouldn't.
(Java 1.2 has explicit advice to use List as base for the
these ADTs).

Re: List container strawman 1.3

[Georg Bauhaus]

Ted Dennison <dennison@telepath.com> wrote:
 
: The problem here is that the logical name seemed to be "End", but that's a
: reserved word. Perhaps we should use "Side"?

I've had a quick look into the outside world; there is an abundance of
good names, IMHO, to be found in GLIB, STL, Haskell lib, and also the
existing Ada libraries. In particular, in GLIB, there is a POSITION
argument name (in insert iirc), and there are prepend and append
operations, which could easily be provided by a renaming declaration
that provides a default value to the position (or whatever) argument.
If I'm not missing something.

Georg

Iterator approach (was: List container strawman 1.3)

[Ted Dennison]

In article <DxyP7.309$w85.20109@rwcrnsc54>, Mark Lundquist says...
>In the access discriminator way, any state of affairs that could give rise
>to a dangling iterator results in a compile-time error, and the safety comes
>at no added run-time expense.  The chained iterator approach results in a

I don't think that's true at all. Suppose I have the following (using your
example):

   type List_Ptr     is access My_Lists.List;
   type Iterator_Ptr is access My_Lists.Iterator;
   function Free is new Unchecked_Deallocation (My_Lists.List, List_Ptr);
   function Free is new Unchecked_Deallocation (My_Lists.Iterator,
Iterator_Ptr);  

Re: List container strawman 1.3

[Ted Dennison]

In article <9untes$j8f$2@a1-hrz.uni-duisburg.de>, Georg Bauhaus says...
>
>existing Ada libraries. In particular, in GLIB, there is a POSITION
>argument name (in insert iirc), and there are prepend and append

Position implies to me it could be anywhere in the list. Side seems more
appropriate. Also, its already used to mean this in one of the iterator
constructors.

>operations, which could easily be provided by a renaming declaration
>that provides a default value to the position (or whatever) argument.
>If I'm not missing something.

That's true. However, there could be a bit of confusion as to which end of
"Front" and "Back" is the "pre" end and which is the "ap" end. Its a lot clearer
the current way as to where the new element will go, because we are using a
consistent terminology.

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

Re: Iterator approach (was: List container strawman 1.3)

[Ted Dennison]

In article <CALP7.51313$xS6.84388@www.newsranger.com>, Ted Dennison says...
>
>In article <DxyP7.309$w85.20109@rwcrnsc54>, Mark Lundquist says...
>>In the access discriminator way, any state of affairs that could give rise
>>to a dangling iterator results in a compile-time error, and the safety comes
>>at no added run-time expense.  The chained iterator approach results in a
>
>I don't think that's true at all. Suppose I have the following (using your
>example):
>
>.   type List_Ptr     is access My_Lists.List;
>.   type Iterator_Ptr is access My_Lists.Iterator;
>.   function Free is new Unchecked_Deallocation (My_Lists.List, List_Ptr);
>.   function Free is new Unchecked_Deallocation (My_Lists.Iterator,
>Iterator_Ptr);  


Damn. Got cut off again.

The idea here is that I dynamicly allocate both the list and an associated
iterator, then use Free to deallocate only one of them. I don't believe the
compiler would give that code any error, and I end up having a pointer to
nowhere that the List facility has no way to detect. Not "safe".

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

Re: List container strawman 1.3

[Jeffrey Carter]

Georg Bauhaus wrote:
> 
> Jeffrey Carter <jeffrey.carter@boeing.com> wrote:
> 
> : Why would you use a list for anything other than a list?
> 
> If a queue/deque/stack is separately provided, I wouldn't.
> (Java 1.2 has explicit advice to use List as base for the
> these ADTs).

Even if they're not, I would build any I needed , using a list as
implementation, rather than using a list directly. No matter how
disciplined I am, it's too tempting to future modifiers of the code to
leave all those general list operations available.

-- 
Jeffrey Carter

Re: Iterator approach (was: List container strawman 1.3)

[Mark Lundquist]

"Ted Dennison" <dennison@telepath.com> wrote in message
news:CALP7.51313$xS6.84388@www.newsranger.com...
> In article <DxyP7.309$w85.20109@rwcrnsc54>, Mark Lundquist says...
> >In the access discriminator way, any state of affairs that could give
rise
> >to a dangling iterator results in a compile-time error, and the safety
comes
> >at no added run-time expense.  The chained iterator approach results in a
>
> I don't think that's true at all. Suppose I have the following (using your
> example):
>
>    type List_Ptr     is access My_Lists.List;
>    type Iterator_Ptr is access My_Lists.Iterator;
>    function Free is new Unchecked_Deallocation (My_Lists.List, List_Ptr);
>    function Free is new Unchecked_Deallocation (My_Lists.Iterator,
> Iterator_Ptr);

I guess that's why they call it "unchecked" deallocation :-) :-).

OK, so I shouldn't have said it was safe under "any" circumstance permitted
by the language...

But I don't think Unchecked_Deallocation can ever be made safe, because of
pointer aliasing:

    Lost : List_Ptr := List;
    .
    .
    Free (List);
    Do_Something (Lost);

I guess my view is that using Unchecked_Deallocation is like signing a
waiver that says "I accept full responsibility for whatever happens".  So a
high-overhead scheme to protect the user from any bad consequence of that
seems to me not to be in the right spirit, or something like that.

Just one person's opinion... :-)

-- mark

Re: List container strawman 1.3

[Darren New]

Ted Dennison wrote:
> The list itself will have to
> keep a mini-list of iterators to support invalidating iterators whoose
> pointed-to item is removed. 

This could be done by checking at the time of access thru the invalid
iterator, rather than by checking during deletes.

For efficiency, keep track in each iterator and each list head the
number of deletes (or other operations that might invalidate an
iterator) that have occurred. If an iterator is accessed when that
counter in the iterator is smaller than the counter in the list it's
iterating, run through the list (O(N)) and check if the iterator is
pointing to one of the still-existant nodes.

It's a performance trade-off that works well when you're doing a lot of
list manipulations with few iterators per list, which I would assume is
a common case.

-- 
Darren New 
San Diego, CA, USA (PST). Cryptokeys on demand.
   You will soon read a generic fortune cookie.

Re: Iterator approach (was: List container strawman 1.3)

[Preben Randhol]

On Thu, 06 Dec 2001 17:41:00 GMT, Mark Lundquist wrote:
> But I don't think Unchecked_Deallocation can ever be made safe, because of
> pointer aliasing:
> 
>     Lost : List_Ptr := List;
>     .
>     .
>     Free (List);
>     Do_Something (Lost);

This is why I in my simple list don't allow pointers outside the list
implementation and use an internal list iterator only.

Preben
-- 
 ()   Join the worldwide campaign to protect fundamental human rights.
'||}
{||'                                           http://www.amnesty.org/

Re: List container strawman 1.3

[Georg Bauhaus]

Jeffrey Carter <jeffrey.carter@boeing.com> wrote:
 
: Even if they're not, I would build any I needed , using a list as
: implementation, rather than using a list directly.

Yep. I think I felt uncomfortable with List_End, even when working
on an implementation,  because of the "_End" which in a sense is not
the beginning, so Side is nice :-)  (If I keep on talking, this will
be about angels and pin tops so I'm looking forward to
{name | name internationally means one Side}.)

Georg

Re: List container strawman 1.3

[Nick Roberts]

Forgive me, but I want to take time to (re-)study your proposal, Ted
(perhaps over the weekend). I'll post my response after that.

--
Best wishes,
Nick Roberts

Re: List container strawman 1.3

[Ted Dennison]

In article <3C0FAF0C.A46BB265@san.rr.com>, Darren New says...
>
>For efficiency, keep track in each iterator and each list head the
>number of deletes (or other operations that might invalidate an
>iterator) that have occurred. If an iterator is accessed when that
>counter in the iterator is smaller than the counter in the list it's
>iterating, run through the list (O(N)) and check if the iterator is
>pointing to one of the still-existant nodes.

Suppose a new node got added right after the deletion? In that case its quite
possible that your iterator is now unintentionally pointing to the new node
instead of the old deleted one.


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

Re: Iterator approach (was: List container strawman 1.3)

[Ted Dennison]

In article <M4OP7.1278$L51.9683@rwcrnsc54>, Mark Lundquist says...
>
>OK, so I shouldn't have said it was safe under "any" circumstance permitted
>by the language...

Dynamic deallocation isn't exactly some bizzare rarely-used feature.

>I guess my view is that using Unchecked_Deallocation is like signing a
>waiver that says "I accept full responsibility for whatever happens". 

.. to that object, yes. The situation we are talking about is that nasty things
happen to *other* objects as well, because we have purposely designed things in
a way that allows that. If we want to take the attitude that it is the user's
responsibility to keep iterators and lists consistent, than we can take that
attitude. If instead we want to take the attitude that its the package's
responsibility then we can take that attitude. I think trying to take some
middle ground is dangerous.


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

Re: List container strawman 1.3

[Ted Dennison]

In article <9uoh6a$l3k$1@a1-hrz.uni-duisburg.de>, Georg Bauhaus says...
>
>Yep. I think I felt uncomfortable with List_End, even when working
>on an implementation,  because of the "_End" which in a sense is not
>the beginning, so Side is nice :-)  (If I keep on talking, this will
>be about angels and pin tops so I'm looking forward to
>{name | name internationally means one Side}.)

I think this makes two votes for "Side". Does anyone have huge problems with
that name? 

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

Re: List container strawman 1.3

[Darren New]

Ted Dennison wrote:
> Suppose a new node got added right after the deletion? In that case its quite
> possible that your iterator is now unintentionally pointing to the new node
> instead of the old deleted one.

True, I'd forgotten about that. There's ways around that too, but
they're higher overhead. Or you could do something with storage pools to
prevent it, perhaps. Doing the invalidation at the time of the operation
is probably a good idea, given that 'iterators' would need to be
controlled (if not limited) anyway, eliminating the need to check on
iterators you don't know about when you make the changes to the list.

-- 
Darren New 
San Diego, CA, USA (PST). Cryptokeys on demand.
   You will soon read a generic fortune cookie.

Re: List container strawman 1.3

[Mark Lundquist]

"Darren New" <dnew@san.rr.com> wrote in message
news:3C10F9CC.175B3159@san.rr.com...
> Ted Dennison wrote:
> > Suppose a new node got added right after the deletion? In that case its
quite
> > possible that your iterator is now unintentionally pointing to the new
node
> > instead of the old deleted one.
>
> True, I'd forgotten about that. There's ways around that too, but
> they're higher overhead. Or you could do something with storage pools to
> prevent it, perhaps. Doing the invalidation at the time of the operation
> is probably a good idea, given that 'iterators' would need to be
> controlled (if not limited) anyway, eliminating the need to check on
> iterators you don't know about when you make the changes to the list.

Plus, it seems dubious to optimize deletion in favor of access!
-- mark