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.25.31.131 with SMTP id f125mr1340649lff.2.1466390532384; Sun, 19 Jun 2016 19:42:12 -0700 (PDT) X-Received: by 10.157.41.105 with SMTP id d96mr366205otb.19.1466390532210; Sun, 19 Jun 2016 19:42:12 -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!w10no3643116lbo.0!news-out.google.com!di11ni3646lbb.1!nntp.google.com!w10no3643111lbo.0!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail Newsgroups: comp.lang.ada Date: Sun, 19 Jun 2016 19:42:11 -0700 (PDT) In-Reply-To: Complaints-To: groups-abuse@google.com Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=216.121.226.25; posting-account=ENgozAkAAACH-stq5yXctoDQeZQP2E6J NNTP-Posting-Host: 216.121.226.25 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: Subject: Re: Generic Embedded List Nodes From: Warren Injection-Date: Mon, 20 Jun 2016 02:42:12 +0000 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Xref: news.eternal-september.org comp.lang.ada:30822 Date: 2016-06-19T19:42:11-07:00 List-Id: On Sunday, 19 June 2016 16:35:32 UTC-4, Dmitry A. Kazakov wrote: > On 2016-06-19 22:13, Warren wrote: > > On Sunday, 19 June 2016 15:04:05 UTC-4, Dmitry A. Kazakov wrote: > >> Maybe I don't understand the problem, but it seems you want externally > >> linked objects that themselves were of any type. > > > > Close, but not quite. I had been toying with the idea that each node > > point back to the containing object, but I've dropped that clumsy idea = now. >=20 > You don't need that as you can calculate it from the object address. You= =20 > know the element head size and the alignment of the object (from=20 > Allocate). This gives you the offset. With the embedded list nodes, the calculation is a little different, but do= ne along the same lines. You take the Node address and subtract to get to t= he containing object. But this design means you only allocate ONE object fo= r list node and object together. Like I've said in the beginning, I am only considering embedded list nodes = for higher performance reasons. The embedded list operations are so simple = they can be inlined with virtually no code or performance penalty. > >> The best way to do it is IMO a custom memory pool. > > > > The problem I have with that is performance. For example deleting a > > node from a list. > > > > procedure Delete > > ( Brand : List_Identification_Type; > > Container : in out Web; > > Element : in out Node > > ); > > > > To delete the node, in the worst case, requires traversing the > > entire list. My lists can be 30,000+ long. >=20 > No, doubly-linked list deletion is O(1). Ok you're tracking the link in Element, which is fine. However, your Elemen= t also needs a reference to the separately allocated object (which is a pro= blem for me). This requires two allocations instead of one.=20 I only need to insert head, traversal and delete. That's it! > > 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; >=20 > The operation Delete has the list head parameter (Container) not for=20 > traversing the list, but for modifying the list head if the first=20 > element is deleted from the list. > If you don't have it, you must maintain a dedicated list head element=20 > with no object attached. That is a less safe and clean because it=20 > ultimately leads to run-time type checks in the client code. I agree with the dedicated list head statement, but not the "less safe" par= t. You either have container or you have a list head (each represents one l= ist, though yours potentially several).=20 There is nothing to check about a list head- you simply begin there. If you= have no "head.next", you have an empty list. Warren