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=0.6 required=5.0 tests=BAYES_00,TO_NO_BRKTS_FROM_MSSP autolearn=no 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 07:56:09 PST Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!newsfeed.wirehub.nl!news-out.visi.com!hermes.visi.com!newsranger.com!www.newsranger.com!not-for-mail Newsgroups: comp.lang.ada From: Ted Dennison References: Subject: Re: list strawman Message-ID: X-Abuse-Info: When contacting newsranger.com regarding abuse please X-Abuse-Info: forward the entire news article including headers or X-Abuse-Info: else we will not be able to process your request X-Complaints-To: abuse@newsranger.com NNTP-Posting-Date: Mon, 07 Jan 2002 10:56:02 EST Organization: http://www.newsranger.com Date: Mon, 07 Jan 2002 15:56:02 GMT Xref: archiver1.google.com comp.lang.ada:18601 Date: 2002-01-07T15:56:02+00:00 List-Id: 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. >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.