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!newsfeed0.kamp.net!newsfeed.kamp.net!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail
From: Niklas Holsti <niklas.holsti@tidorum.invalid>
Newsgroups: comp.lang.ada
Subject: Re: Generic Embedded List Nodes
Date: Mon, 20 Jun 2016 09:08:43 +0300
Organization: Tidorum Ltd
Message-ID: <dspfjbFjc1qU1@mid.individual.net>
References: <66c14298-c62d-4f4b-b0c0-e969454f9334@googlegroups.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 7bit
X-Trace: individual.net jCe9Ui4UBtFqcVpfxDqHzAqfrLmauuMTVW/SGYzVww+U0wli2d
Cancel-Lock: sha1:sD8WChKF2DNpAZAS8LUL61p7CLs=
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:45.0)
 Gecko/20100101 Thunderbird/45.1.1
In-Reply-To: <66c14298-c62d-4f4b-b0c0-e969454f9334@googlegroups.com>
Xref: news.eternal-september.org comp.lang.ada:30824
Date: 2016-06-20T09:08:43+03:00
List-Id: <comp.lang.ada>

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.

-- 
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
       .      @       .