From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,cda33fc7f63c2885 X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 2002-01-07 08:37:13 PST Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!canoe.uoregon.edu!hammer.uoregon.edu!skates!not-for-mail From: Stephen Leake Newsgroups: comp.lang.ada Subject: Re: list strawman Date: 07 Jan 2002 11:33:10 -0500 Organization: NASA Goddard Space Flight Center Message-ID: References: NNTP-Posting-Host: anarres.gsfc.nasa.gov Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: skates.gsfc.nasa.gov 1010421420 4163 128.183.220.71 (7 Jan 2002 16:37:00 GMT) X-Complaints-To: dscoggin@cne-odin.gsfc.nasa.gov NNTP-Posting-Date: 7 Jan 2002 16:37:00 GMT User-Agent: Gnus/5.0808 (Gnus v5.8.8) Emacs/20.7 Xref: archiver1.google.com comp.lang.ada:18607 Date: 2002-01-07T16:37:00+00:00 List-Id: Ted Dennison writes: > In article , 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. Cool. Great minds think alike? or just common environments lead to common evolution :). 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? > >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: Well, I have _not_ done thorough testing, so it is quite possible you've uncovered real bugs. > 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. Are you saying I should "wipe out" the source iterators, and not preserve them? That's not what I would expect. > 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. > 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). Yes, I've only used the passive generic (to print the lists), so maybe I am missing something. 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. > 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"). Yes. SAL just raises Constraint_Error for the No_Item condition; I do not map that to the No_Item exception everywhere yet. 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. > 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). Yes, I haven't put that in yet. I wanted to write a test that failed first, so I would know the test was valid :). > Efficiency issues: > > I discovered it is possible to get rid of all dynamic allocations in iterator > manipulations. I'd definitely like to see this. > It also looks like it is possible to get rid of all list searches in iterator > manipulations. 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. > 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. > 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. 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. -- -- Stephe