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.155.208 with SMTP id d199mr1733003lfe.10.1466425213882; Mon, 20 Jun 2016 05:20:13 -0700 (PDT) X-Received: by 10.157.45.136 with SMTP id g8mr410379otb.3.1466425213775; Mon, 20 Jun 2016 05:20:13 -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!w10no4067043lbo.0!news-out.google.com!di11ni7736lbb.1!nntp.google.com!oe3no5866766lbb.1!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail Newsgroups: comp.lang.ada Date: Mon, 20 Jun 2016 05:20:13 -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> User-Agent: G2/1.0 MIME-Version: 1.0 Message-ID: <7b001b5d-96d2-4cd8-80fc-795af0807e11@googlegroups.com> Subject: Re: Generic Embedded List Nodes From: Warren Injection-Date: Mon, 20 Jun 2016 12:20:13 +0000 Content-Type: text/plain; charset=UTF-8 Xref: news.eternal-september.org comp.lang.ada:30836 Date: 2016-06-20T05:20:13-07:00 List-Id: On Monday, 20 June 2016 02:08:45 UTC-4, Niklas Holsti wrote: > On 16-06-19 01:52 , Warren wrote: > > Getting back to Ada after a hiatus, I currently have a need to build a > > generic package to implement "embedded list node" lists. The advantage > > is high performance in a server setting to avoid underlying malloc/free > > calls. > > > > The idea is that the list node resides within the structure/tagged type, > > and acts as a doubly linked list node when in a list. The Emb_Node can > > be used as a list head when itself (or as part of another structure). This > > kind of thing is done in the Linux kernel, for example. > > > > The Emb_Node and its operations are trivial. The problem occurs when > > you traverse a linked list of Emb_Nodes (or its derived type). With > > a given node, I need to then access the object that _contains_ it. > > Is there some reason why you cannot derive all the "node" types from a > root type that has the link components you need in the Emb_Nodes? > > Something like this: > > type Node_T is tagged; > > type Node_Ref_T is access all Node_T'Class; > > type Node_T is tagged record > Prev, Next : Node_Ref_T; > end record; > > type Integer_Node_T is new Node_T with record > Value : Integer; > end record; > > type Float_Node_T is new Node_T with record > Value : Float; > end record; > > -- and so on. > > If you don't derive the list-node types from some common root type (or > interface), I don't see how you can traverse a list and do something > useful with some or all list elements. Or is it the case that all nodes > in any given list are of one and the same type, and you know (somehow) > what type they are? > > Another way to avoid extra heap-allocation/release calls but still have > separate objects for the list nodes is to keep your own pool of list > nodes, with a free-list. Allocating a new node from such a pool is quite > fast and can be inlined. The idea above works if you only hold one list node. But I use at least two. Warren