Re: Generic Embedded List Nodes

[Shark8 <onewingedshark@gmail.com>]

On Saturday, June 18, 2016 at 4:52:06 PM UTC-6, 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. In
> C/C++ you do some offset calculation from the node address back to
> the owning struct/class.
> 
> My idea (in Ada) was to save some kind of access value in a type
> derived from Emb_List. But that is where the trouble starts.
> 
> package Emb_List is
>          
>    type Emb_Node is tagged private;
>              
>    procedure Insert_Head(Head: access Emb_Node; Node: access Emb_Node);
>    procedure Unlink(Node: access Emb_Node);
> 
> private
> 
>    type Emb_Node is tagged
>       record
>          Next:    access Emb_Node;  -- Ptr to next node in list (if any)
>          Prev:    access Emb_Node;  -- Ptr to prev node in list (if any)
>       end record;
>    
> end Emb_List;
>    
> The generic extension (below) was intended to hold the reference to the
> containing object, which is where the trouble starts. I was hoping this
> would work, but running into "missing full declaration for private
> extension".
> 
> generic
>    type Object_Type is tagged private;
> package Emb_List.Nodes is
> 
>    type Node_Type(Obj: access Object_Type) is new Emb_Node;
>    
>    function Object(Node: Node_Type) return Object_Type;
>    
> end Emb_List.Nodes;
> 
> 
> The other end of the challenge will be to have the Node_Type save the
> owning object access value at the time it is created:
> 
>    type Something_New_Type is tagged
>       record
>          Stuff:                  Natural;
>          Timeout_Node:  Node_Type(some access to this record);
>          ...
>       end record;
>       
> I am trying to avoid using 'Address for this, since there is likely a
> way to do this "right".
> 
> Warren.

Hm, have you tried seeing if any Ada.Containers.* fits your needs? You could perhaps use Indefinite_Holder to hold your item or Indefinite_Vector to hold the entire list.