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=unavailable autolearn_force=no version=3.4.4 Path: eternal-september.org!reader01.eternal-september.org!reader02.eternal-september.org!news.eternal-september.org!mx02.eternal-september.org!feeder.eternal-september.org!aioe.org!.POSTED!not-for-mail From: "Dmitry A. Kazakov" Newsgroups: comp.lang.ada Subject: Re: Generic Embedded List Nodes Date: Sun, 19 Jun 2016 22:35:24 +0200 Organization: Aioe.org NNTP Server Message-ID: 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> NNTP-Posting-Host: w/2xSGckQeJEFvqsQFNodA.user.gioia.aioe.org Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit X-Complaints-To: abuse@aioe.org User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:45.0) Gecko/20100101 Thunderbird/45.1.1 X-Notice: Filtered by postfilter v. 0.8.2 Xref: news.eternal-september.org comp.lang.ada:30821 Date: 2016-06-19T22:35:24+02:00 List-Id: 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. You don't need that as you can calculate it from the object address. You know the element head size and the alignment of the object (from Allocate). This gives you the offset. >> 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. No, doubly-linked list deletion is O(1). > 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. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de