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.28.168.69 with SMTP id r66mr661640wme.1.1466290321035;
        Sat, 18 Jun 2016 15:52:01 -0700 (PDT)
X-Received: by 10.157.37.168 with SMTP id q37mr284361ota.13.1466290320924;
 Sat, 18 Jun 2016 15:52:00 -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!oe3no4451874lbb.1!news-out.google.com!f5ni6333lbb.0!nntp.google.com!oe3no4451872lbb.1!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail
Newsgroups: comp.lang.ada
Date: Sat, 18 Jun 2016 15:52:00 -0700 (PDT)
Complaints-To: groups-abuse@google.com
Injection-Info: glegroupsg2000goo.googlegroups.com;
 posting-host=216.121.226.25;
 posting-account=ENgozAkAAACH-stq5yXctoDQeZQP2E6J
NNTP-Posting-Host: 216.121.226.25
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <66c14298-c62d-4f4b-b0c0-e969454f9334@googlegroups.com>
Subject: Generic Embedded List Nodes
From: Warren <ve3wwg@gmail.com>
Injection-Date: Sat, 18 Jun 2016 22:52:01 +0000
Content-Type: text/plain; charset=UTF-8
Xref: news.eternal-september.org comp.lang.ada:30798
Date: 2016-06-18T15:52:00-07:00
List-Id: <comp.lang.ada>

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.