Re: List container strawman

[Jean-Marc Bourguet <jbourguet@free.fr>]

Ted Dennison<dennison@telepath.com> writes:

> In article <po0cs9.dt.ln@127.0.0.1>, ramatthews@tinuviel.com says...
> > In article <bgR13FMw5mIK@eisner.encompasserve.org>, Kilgallen@SpamCop.net
> >(Larry Kilgallen) wrote:
> >> In article <3BE58FDD.E1FB1815@san.rr.com>, Darren New <dnew@san.rr.com>
> >>writes:
> >> 
> >>> If you really want it to be foolproof,
> >>  Yes please.
> >
> >
> >While I see a foolproof list does not have universal appeal I have been
> >successfully using one for some time so I thought its specification would
> >help discussions.
> 
> Yup. That does exactly what is needed to make it safe. I never said it was
> impossible, just that its a lot of work, inculding some extra runtime work
> that might not endear the facility to real-time users. One problem is that
> creating an iterator with this facility involves dynamic allocation and
> linked-list traversal. 

Why do you need dynamic allocation.  The pointer can be in the
iterator and put at the start of the list.  As most lists have few
iterators and when they have more than one, a majority of the uses are
nested the list traversal will be done only on list modifications.

> That violates our general principle of avoiding
> runtime vs. setup overhead, but that could probably(?) be fixed or at least
> avoided by the user if noted. Another issue is that it puts a controlled
> type in the generic package, which I was trying to avoid so that it was
> instantiateable at lower levels.  However, it turned out that List has to
> be controlled anyway, so perahps this isn't so bad.
> 
> I'm interested in what the general consensus is here. Should we do the
> extra work to make iterators safe, given that this will have at least the
> following effects:

I'm for.
 
> o Add extra dynamic memory operations to any list modification (there were
> some there already).  

I don't think so.

> o Add a (usually small) internal list traversal to any element
> deletion.

Agree.

> o Add a small validity check (or possibly two) to every iterator
> operation.

Agree.

> o Possibly make iterator creation non-determistic (time-wise).  

I don't think so. (Iterator deletion would be made non deterministic
if they are assigned in a non nested way and the iterator list is a
singly linked one).

> o Possibly make iterator assignment non-deterministic. 

Not if the iterator list is doubly linked.

-- 
Jean-Marc