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,FREEMAIL_FROM autolearn=unavailable autolearn_force=no version=3.4.4 X-Received: by 10.28.166.73 with SMTP id p70mr171510wme.0.1466425577363; Mon, 20 Jun 2016 05:26:17 -0700 (PDT) X-Received: by 10.157.39.133 with SMTP id c5mr412701otb.6.1466425577250; Mon, 20 Jun 2016 05:26:17 -0700 (PDT) Path: eternal-september.org!reader01.eternal-september.org!reader02.eternal-september.org!news.eternal-september.org!mx02.eternal-september.org!feeder.eternal-september.org!goblin1!goblin.stu.neva.ru!w10no4073275lbo.0!news-out.google.com!di11ni7797lbb.1!nntp.google.com!w10no4073267lbo.0!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail Newsgroups: comp.lang.ada Date: Mon, 20 Jun 2016 05:26:16 -0700 (PDT) In-Reply-To: Complaints-To: groups-abuse@google.com Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=198.135.236.252; posting-account=ENgozAkAAACH-stq5yXctoDQeZQP2E6J NNTP-Posting-Host: 198.135.236.252 References: <66c14298-c62d-4f4b-b0c0-e969454f9334@googlegroups.com> <2e39857a-7121-476b-807a-d2bff1e598f4@googlegroups.com> <431af616-7df3-4e4d-9262-26ed68cb74c7@googlegroups.com> <037df2b8-b9c4-4447-87ee-cc89d7072b30@googlegroups.com> <15914c54-191c-4f37-b754-282855d1aeaf@googlegroups.com> User-Agent: G2/1.0 MIME-Version: 1.0 Message-ID: <3e25c9a0-469c-4487-b78e-6f87434f87fa@googlegroups.com> Subject: Re: Generic Embedded List Nodes From: Warren Injection-Date: Mon, 20 Jun 2016 12:26:17 +0000 Content-Type: text/plain; charset=UTF-8 Xref: news.eternal-september.org comp.lang.ada:30837 Date: 2016-06-20T05:26:16-07:00 List-Id: On Monday, 20 June 2016 03:25:48 UTC-4, Dmitry A. Kazakov wrote: > On 20/06/2016 04:42, Warren wrote: > > On Sunday, 19 June 2016 16:35:32 UTC-4, Dmitry A. Kazakov wrote: > >> No, doubly-linked list deletion is O(1). > > > > Ok you're tracking the link in Element, which is fine. However, your > > Element also needs a reference to the separately allocated object (which > > is a problem for me). This requires two allocations instead of one. > > No, that is the point. The object and the element (links) are in one > continuous chunk of memory. I believe this is what you meant under being > "embedded" nodes. > > When an object is allocated, element + object is instead and the address > to the object's part is returned back from Allocate. Deallocate takes > the object's address, subtracts the offset and deallocates the whole chunk. > > > I only need to insert head, traversal and delete. That's it! > > Yes, and the schema above is as effective as it can be. > > >>> In the embedded node case, I already have direct access to the > >>> affected link node. To remove the node from a list I simply say: > >>> > >>> R.Link_Node.Unlink; > >> > >> The operation Delete has the list head parameter (Container) not for > >> traversing the list, but for modifying the list head if the first > >> element is deleted from the list. > > > >> If you don't have it, you must maintain a dedicated list head element > >> with no object attached. That is a less safe and clean because it > >> ultimately leads to run-time type checks in the client code. > > > > I agree with the dedicated list head statement, but not the "less > > safe" part. You either have container or you have a list head (each > > represents one list, though yours potentially several). > > > > There is nothing to check about a list head- you simply begin there. > > If you have no "head.next", you have an empty list. > > Not with doubly-linked lists. There is always Next, because the list is > circular. Mine ain't. > When you delete an element from the list you always get two > lists. Deletion of a single element is an idempotent operation unless > you have a dedicated head or else have the list head pointer corrected. In my list, when the last item is removed from the list, Head.Next = Null. Simple. > List traversal when the list head is a pointer is performed like this: > > if Head /= null then > This := Head; > loop > ... -- Do something > This := This.Next; > exit when This = Head; > end loop; > end if; delcare Node: access Emb_Node := Head.Next; begin while Node loop -- do something with node Node := Node.Next; end loop; end; Anyway folks- thanks for your help but I now have a working solution. I'm signing off this thread. Warren