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,LOTS_OF_MONEY autolearn=ham autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,ce0900b60ca3f616 X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 2001-11-10 12:29:05 PST Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!dispose.news.demon.net!demon!xara.net!gxn.net!server6.netnews.ja.net!server4.netnews.ja.net!news5-gui.server.ntli.net!ntli.net!news11-gui.server.ntli.net.POSTED!tinuviel!ramint From: ramatthews@tinuviel.com Newsgroups: comp.lang.ada Subject: Re: List container strawman References: <3BE29AF4.80804@telepath.com><3BE29BD4.10401@telepath.com><3BE2DB99.B707D409@boeing.com><3BE32A18.18404AD1@boeing.com><3BE443DE.574D669C@acm.org><3BE58FDD.E1FB1815@san.rr.com> X-Newsreader: Pan 0.7.6 Message-ID: <4d2ks9.vk2.ln@127.0.0.1> Date: Sat, 10 Nov 2001 20:24:04 +0000 NNTP-Posting-Host: 62.252.9.144 X-Complaints-To: abuse@ntlworld.com X-Trace: news11-gui.server.ntli.net 1005423821 62.252.9.144 (Sat, 10 Nov 2001 20:23:41 GMT) NNTP-Posting-Date: Sat, 10 Nov 2001 20:23:41 GMT Organization: ntlworld News Service Xref: archiver1.google.com comp.lang.ada:16244 Date: 2001-11-10T20:24:04+00:00 List-Id: In article , Ted Dennison wrote: > > 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: > > o Add extra dynamic memory operations to any list modification (there were some > there already). > o Add a (usually small) internal list traversal to any element deletion. > o Add a small validity check (or possibly two) to every iterator operation. > o Possibly make iterator creation non-determistic (time-wise). > o Possibly make iterator assignment non-deterministic. Note that functions are > currently used for iterating, so that would make just about any use of iterators > non-determinstic, unless procedure variants are introduced. > You express some implementation concerns that, for the implementation I have to hand, I hope I can clarify. The list contains two doubly-linked lists: one for the data, the other for the enumerators (also called Iterators and Positions in this discussion on cla). The enumerators list is traversed when the following subprograms are called: Prepend, Append, Delete_All, Insert, Delete and Finalize (for a list). In addition Update will cause a traversal of the enumerators list when the new value cannot be assigned to the existing data element (eg when the new value has a different tag); in this case the new value is assigned to a new data element and the old data element deleted - hence the need to update the enumerators. (Note that the package specification gives an incorrect comment on this). When a list is declared in client code, two data items are created: (1) the list that the client code directly sees (List_Type), and (2) the list header (List_Header_Type) that is created on the heap. A similar situation exists for an enumerator (Enumerator_Type and the heap held Enumerator_Envelope_Type). This split was made, on stylistic grounds, to avoid use of the attribute Unchecked_Access in the body. Having 'safe' enumerators does introduce some extra checking. For example when retrieving the data denoted by an enumerator the subprogram 'Current' checks: (1) that the enumerator's list exists: "Enumerator.Header.List_Header /= null", (2) that the data exists: "Enumerator.Header.Current /= null". Enumerator creation, assignment and finalization involves manipulation of the affected enumerator lists - but does not require list traversal. Robert Matthews.