Re: Generic Embedded List Nodes

[Warren <ve3wwg@gmail.com>]

On Monday, 20 June 2016 15:47:12 UTC-4, Shark8  wrote:
> 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.

If you read upstream, I am looking for an _extremely_ high performance set of operations, requiring only:

 - insert head
 - traverse (head to tail only)
 - delete from list

The implementation I have used on a C++ server works extremely well (inspired by the Linux kernel code), and costs almost nothing. The three operations above are inlined and amount to a few pointer related operations. 

Even a few microseconds of overhead drops your transaction throughput considerably, so using something like Ada containers (or STL in C++) is definitely out for this application. Also any use of malloc/free where possible must be avoided because these are performance killers (even when using jremalloc).

Warren