Re: Generic Embedded List Nodes

[Warren <ve3wwg@gmail.com>]

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