Generic Embedded List Nodes

Generic Embedded List Nodes

[Warren]

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.

Re: Generic Embedded List Nodes

[Jeffrey R. Carter]

On 06/18/2016 03:52 PM, Warren wrote:
> 
> 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.

Let me make sure I understand this. You have type Emb_Node, and you can string
Emb_Nodes together to make a list. You want to make a composite type with an
Emb_Node component:

type Outer is record
   ...
   Node : Emb_Node;
   ...
end record;

and declare objects of this type:

O1 : Outer;
O2 : Outer;

type O_Set is array (Positive range <>) of Outer;

O_List : O_Set (1 .. 10);

type Something is record
   ...
   O : Outer;
   ...
end record;

S : Something;

and then be able to string the Node components of all these Outers together into
a list, and then treat that list as a list of Outers.

Is that correct?

-- 
Jeff Carter
"My legs are gray, my ears are gnarled, my eyes are old and bent."
Monty Python's Life of Brian
81

Re: Generic Embedded List Nodes

[Jeremiah]

On Saturday, June 18, 2016 at 6:52:06 PM UTC-4, 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;

Change Node_Type to:
type Node_Type(Obj: access Object_Type) is new Emb_Node with null record;

You need an extension, even if it is a null record.

> 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.

Well, I'm only a novice, but the only way I have gotten something like that was to use incomplete types:

   type Something_New_Type;
   package SNT_Pkg is new Emb_List.Nodes(Object_Type => Something_New_Type);
   use SNT_Pkg;
   
   type Something_New_Type is tagged limited
      record
         Stuff:                  Natural;
         Timeout_Node:  Node_Type(Something_New_Type'Access);
      end record; 

This means, however, that you would need to change Emp_List.Nodes to use incomplete types:

generic
   type Object_Type;
package Emb_List.Nodes is
   
   type Node_Type(Obj: access Object_Type) is new Emb_Node with null record;
   
end Emb_List.Nodes; 

However, you would need to rethink your function to return the Object as you cannot return a complete type when using incomplete types.  You might be stuck with just using the access value instead or perhaps with some other design changes you can come up with a better solution.

Again, I am still learning, so maybe some of the more experienced users can comment.

Re: Generic Embedded List Nodes

[Warren]

On Saturday, 18 June 2016 19:40:31 UTC-4, Jeffrey R. Carter  wrote:
> On 06/18/2016 03:52 PM, Warren wrote:
> > 
> > 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.
> 
> Let me make sure I understand this. You have type Emb_Node, and you can string
> Emb_Nodes together to make a list. 

Yes.

> You want to make a composite type with an
> Emb_Node component:
> 
> type Outer is record
>    ...
>    Node : Emb_Node;
>    ...
> end record;

Yes.

> and declare objects of this type:
> 
> O1 : Outer;
> O2 : Outer;

Yes.

From this point, we add "heads of lists". They can be stand alone, or part of another object (for now let's assume stand alone ):

Timeouts: Emb_Node;

Timeouts.Insert_Head(O1);
Timeouts.Insert_Head(O2);

etc.

Then if you did:

 O1.Node.Unlink; 

the object O1 becomes removed from the linked list it was in (if any).

> and then be able to string the Node components of all these Outers together into
> a list, and then treat that list as a list of Outers.
> 
> Is that correct?

Essentially, yes.  

With one or more Head nodes, you create one or more lists.

Not all of the members need be in any list. Obviously, with only one
given embedded node, that node can be a member of at most one list.

Of course more lists can be supported by adding additional 
embedded nodes, but clearly one needs to be careful not to mix them
up.

Warren

Re: Generic Embedded List Nodes

[Warren]

On Saturday, 18 June 2016 22:14:22 UTC-4, Jeremiah  wrote:
> On Saturday, June 18, 2016 at 6:52:06 PM UTC-4, 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;
> 
> Change Node_Type to:
> type Node_Type(Obj: access Object_Type) is new Emb_Node with null record;
> 
> You need an extension, even if it is a null record. 

I had clearly forgotten about "with null record". I will try that.

Warren

Re: Generic Embedded List Nodes

[Warren]

On Saturday, 18 June 2016 22:21:18 UTC-4, Warren  wrote:
> On Saturday, 18 June 2016 22:14:22 UTC-4, Jeremiah  wrote:
> > On Saturday, June 18, 2016 at 6:52:06 PM UTC-4, 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;
> > 
> > Change Node_Type to:
> > type Node_Type(Obj: access Object_Type) is new Emb_Node with null record;
> > 
> > You need an extension, even if it is a null record. 
> 
> I had clearly forgotten about "with null record". I will try that.
> 
> Warren

generic
   type Object_Type is tagged private;
package Emb_List.Nodes is

   type Node_Type(Obj: access Object_Type := Obj'Access) is new Emb_Node  
      with null record;  
   
   function Object(Node: Node_Type) return Object_Type;
   
end Emb_List.Nodes;

The problem with this now is "discriminant "Obj" cannot be used before end of discriminant part".

This is intended to allow extension of My_Recd with a Node that knows My_Recd'Access.

declare
         type My_Recd is tagged
            record
               Id:         Natural := 99;
            end record;
   
         package EMB is new Emb_List.Nodes(Object_Type => My_Recd);

Is there another way that I could do this: i.e. determine My_Recd'Access from some list node object, embedded in My_Recd?

Warren

Re: Generic Embedded List Nodes

[Jeffrey R. Carter]

On 06/18/2016 07:15 PM, Warren wrote:
> On Saturday, 18 June 2016 19:40:31 UTC-4, Jeffrey R. Carter  wrote:
>>
>> Let me make sure I understand this. You have type Emb_Node, and you can string
>> Emb_Nodes together to make a list. 
> 
> Yes.
> 
>> You want to make a composite type with an
>> Emb_Node component:
> 
> Yes.
> 
>> and declare objects of this type:
> 
> Yes.
> 
>> and then be able to string the Node components of all these Outers together into
>> a list, and then treat that list as a list of Outers.
>>
>> Is that correct?
> 
> Essentially, yes.  

That's a terrible idea. It sounds like something that only someone who thinks
doing "some offset calculation from the node address back to
the owning struct/class" is a good idea would think up.

-- 
Jeff Carter
"My legs are gray, my ears are gnarled, my eyes are old and bent."
Monty Python's Life of Brian
81

Re: Generic Embedded List Nodes

[Simon Wright]

Warren <ve3wwg@gmail.com> writes:

> type Node_Type(Obj: access Object_Type := Obj'Access) is new Emb_Node  
>   with null record;

You could try

   type Node_Type(Discr : access Object_Type := Obj'Access) is new Emb_Node
     with null record;

to avoid the name clash, but there is no Obj here to take 'Access of.

The compilable way to write this would be

   type Node_Type(Obj: access Object_Type) is new Emb_Node
     with null record;

or, better in most cases,

   type Node_Type(Obj: access Object_Type) is new Emb_Node
     with null record;

Re: Generic Embedded List Nodes

[Warren]

On Sunday, 19 June 2016 00:45:54 UTC-4, Simon Wright  wrote:
> Warren <ve3wwg@gmail.com> writes:
> 
>    type Node_Type(Obj: access Object_Type) is new Emb_Node
>      with null record;

I've come to the conclusion that my original idea in Ada terms is too half baked. 

What it will come down to in the end is doing an offset calculation from the Node back to the Object when its access is required (through a function). 

Even in C/C++ this is a bit of a problem. While there is an offsetof(type,member) macro, this is only usable on non-dynamic types. Calculating an offset of a struct is trivial when you have it allocated. But when the class has a constructor, then you may not want to invoke that overhead only to create one for offset calculations.

In Ada for some record Type R.M where R is the record and M is the member, you cannot do R.M'Position when R is just a type. But you can cheat this, similar to how I have done it in C/C++:

with System;
with Ada.Integer_Text_IO;

procedure T is
   use Ada.Integer_Text_IO;

   type R_Type is
      record
         I : Integer;
         F : Float;
      end record;

   A:    System.Address;

   R:    R_Type;
   for R'Address use A;
   
begin
   Put(R.I'Position);
   Put(R.F'Position);
end;

This never allocates the object, but assumes it already exists at address A. Since the record and its members are never actually used, it is possible to have the compiler do the necessary calculations. This will complain "warning: variable "A" is read but never assigned", however.

I suppose a tagged R.Initialize could also establish an 'Access value in all Emb_Node members, using some other procedure call for Emb_Node (perhaps Set_Object). But it is desireable not to have to carry the object reference in the Emb_Node at all.

Warren

Re: Generic Embedded List Nodes

[Dmitry A. Kazakov]

On 2016-06-19 20:27, Warren wrote:
> On Sunday, 19 June 2016 00:45:54 UTC-4, Simon Wright  wrote:
>> Warren <ve3wwg@gmail.com> writes:
>>
>>    type Node_Type(Obj: access Object_Type) is new Emb_Node
>>      with null record;
>
> I've come to the conclusion that my original idea in Ada terms is too half baked.
>
> What it will come down to in the end is doing an offset calculation
> from the Node back to the Object when its access is required (through a
> function).
>
> Even in C/C++ this is a bit of a problem. While there is an
> offsetof(type,member) macro, this is only usable on non-dynamic types.
> Calculating an offset of a struct is trivial when you have it allocated.
> But when the class has a constructor, then you may not want to invoke
> that overhead only to create one for offset calculations.
>
> In Ada for some record Type R.M where R is the record and M is the
> member, you cannot do R.M'Position when R is just a type. But you can
> cheat this, similar to how I have done it in C/C++:
>
> with System;
> with Ada.Integer_Text_IO;
>
> procedure T is
>    use Ada.Integer_Text_IO;
>
>    type R_Type is
>       record
>          I : Integer;
>          F : Float;
>       end record;
>
>    A:    System.Address;
>
>    R:    R_Type;
>    for R'Address use A;
>
> begin
>    Put(R.I'Position);
>    Put(R.F'Position);
> end;
>
> This never allocates the object, but assumes it already exists at
> address A.. Since the record and its members are never actually used, it
> is possible to have the compiler do the necessary calculations. This
> will complain "warning: variable "A" is read but never assigned", however.
>
> I suppose a tagged R.Initialize could also establish an 'Access value
> in all Emb_Node members, using some other procedure call for Emb_Node
> (perhaps Set_Object). But it is desireable not to have to carry the
> object reference in the Emb_Node at all.

Maybe I don't understand the problem, but it seems you want externally 
linked objects that themselves were of any type. The best way to do it 
is IMO a custom memory pool.

My implementation of linked list uses this approach.

http://www.dmitry-kazakov.de/ada/components.htm#Generic_Doubly_Linked_Web

The object is allocated in the custom pool, which actually takes memory 
from another, e.g. standard, pool. But before that adds links just in 
front of the object. The pool-specific pointer carries the operations 
Next, Previous etc. Yes, it uses address arithmetic to get to the links, 
but no record member offsets or other crazy stuff because you deal with 
pointers to the objects, not the pointers to the list elements.

The only problem you must be aware of is that X'Address attribute is 
broken in Ada when X is an array:

    X'Address = X (X'First)'Address

which if of course not the address of the array. If you are going to 
instantiate your package with an array type, you must calculate the 
offset to the array object beginning.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Generic Embedded List Nodes

[Warren]

On Sunday, 19 June 2016 15:04:05 UTC-4, Dmitry A. Kazakov  wrote:
> Maybe I don't understand the problem, but it seems you want externally 
> linked objects that themselves were of any type. 

Close, but not quite. I had been toying with the idea that each node point back to the containing object, but I've dropped that clumsy idea now.

Now I am back to the original C idea of converting a Node reference back to its containing object through pointer arithmetic (I know: Ada fans gasping). In short, given a Node, I need to get its containing Object.

> The best way to do it is IMO a custom memory pool.

The problem I have with that is performance. For example deleting a node from a list. 

procedure Delete
          (  Brand     : List_Identification_Type;
             Container : in out Web;
             Element   : in out Node
          );

To delete the node, in the worst case, requires traversing the entire list. My lists can be 30,000+ long.

In the embedded node case, I already have direct access to the affected link node. To remove the node from a list I simply say:

    R.Link_Node.Unlink;

and it removes itself out of the doubly linked list (else does nothing if not already in a list).

I have considered a memory pool and not ruled it out. 

Presently I have an generic Object_Of(Node) function working, which makes use of System.Storage_Elements."+" (gasp!) The only drawback is that I need a fake instance of the Object to determine Node'Position at startup. 

Warren

Re: Generic Embedded List Nodes

[Dmitry A. Kazakov]

On 2016-06-19 22:13, Warren wrote:
> On Sunday, 19 June 2016 15:04:05 UTC-4, Dmitry A. Kazakov  wrote:
>> Maybe I don't understand the problem, but it seems you want externally
>> linked objects that themselves were of any type.
>
> Close, but not quite. I had been toying with the idea that each node
> point back to the containing object, but I've dropped that clumsy idea now.

You don't need that as you can calculate it from the object address. You 
know the element head size and the alignment of the object (from 
Allocate). This gives you the offset.

>> The best way to do it is IMO a custom memory pool.
>
> The problem I have with that is performance. For example deleting a
> node from a list.
>
> procedure Delete
>           (  Brand     : List_Identification_Type;
>              Container : in out Web;
>              Element   : in out Node
>           );
>
> To delete the node, in the worst case, requires traversing the
> entire  list. My lists can be 30,000+ long.

No, doubly-linked list deletion is O(1).

> In the embedded node case, I already have direct access to the
> affected link node. To remove the node from a list I simply say:
>
>     R.Link_Node.Unlink;

The operation Delete has the list head parameter (Container) not for 
traversing the list, but for modifying the list head if the first 
element is deleted from the list.

If you don't have it, you must maintain a dedicated list head element 
with no object attached. That is a less safe and clean because it 
ultimately leads to run-time type checks in the client code.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Generic Embedded List Nodes

[Warren]

On Sunday, 19 June 2016 16:35:32 UTC-4, Dmitry A. Kazakov  wrote:
> On 2016-06-19 22:13, Warren wrote:
> > On Sunday, 19 June 2016 15:04:05 UTC-4, Dmitry A. Kazakov  wrote:
> >> Maybe I don't understand the problem, but it seems you want externally
> >> linked objects that themselves were of any type.
> >
> > Close, but not quite. I had been toying with the idea that each node
> > point back to the containing object, but I've dropped that clumsy idea now.
> 
> You don't need that as you can calculate it from the object address. You 
> know the element head size and the alignment of the object (from 
> Allocate). This gives you the offset.

With the embedded list nodes, the calculation is a little different, but done along the same lines. You take the Node address and subtract to get to the containing object. But this design means you only allocate ONE object for list node and object together.

Like I've said in the beginning, I am only considering embedded list nodes for higher performance reasons. The embedded list operations are so simple they can be inlined with virtually no code or performance penalty.

> >> The best way to do it is IMO a custom memory pool.
> >
> > The problem I have with that is performance. For example deleting a
> > node from a list.
> >
> > procedure Delete
> >           (  Brand     : List_Identification_Type;
> >              Container : in out Web;
> >              Element   : in out Node
> >           );
> >
> > To delete the node, in the worst case, requires traversing the
> > entire  list. My lists can be 30,000+ long.
> 
> No, doubly-linked list deletion is O(1).

Ok you're tracking the link in Element, which is fine. However, your Element also needs a reference to the separately allocated object (which is a problem for me). This requires two allocations instead of one. 

I only need to insert head, traversal and delete. That's it!

> > In the embedded node case, I already have direct access to the
> > affected link node. To remove the node from a list I simply say:
> >
> >     R.Link_Node.Unlink;
> 
> The operation Delete has the list head parameter (Container) not for 
> traversing the list, but for modifying the list head if the first 
> element is deleted from the list.

> If you don't have it, you must maintain a dedicated list head element 
> with no object attached. That is a less safe and clean because it 
> ultimately leads to run-time type checks in the client code.

I agree with the dedicated list head statement, but not the "less safe" part. You either have container or you have a list head (each represents one list, though yours potentially several). 

There is nothing to check about a list head- you simply begin there. If you have no "head.next", you have an empty list.

Warren

Re: Generic Embedded List Nodes

[Niklas Holsti]

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
       .      @       .

Re: Generic Embedded List Nodes

[Dmitry A. Kazakov]

On 20/06/2016 04:42, Warren wrote:
> On Sunday, 19 June 2016 16:35:32 UTC-4, Dmitry A. Kazakov  wrote:
>> No, doubly-linked list deletion is O(1).
>
> Ok you're tracking the link in Element, which is fine. However, your
> Element also needs a reference to the separately allocated object (which
> is a problem for me). This requires two allocations instead of one.

No, that is the point. The object and the element (links) are in one 
continuous chunk of memory. I believe this is what you meant under being 
"embedded" nodes.

When an object is allocated, element + object is instead and the address 
to the object's part is returned back from Allocate. Deallocate takes 
the object's address, subtracts the offset and deallocates the whole chunk.

> I only need to insert head, traversal and delete. That's it!

Yes, and the schema above is as effective as it can be.

>>> In the embedded node case, I already have direct access to the
>>> affected link node. To remove the node from a list I simply say:
>>>
>>>     R.Link_Node.Unlink;
>>
>> The operation Delete has the list head parameter (Container) not for
>> traversing the list, but for modifying the list head if the first
>> element is deleted from the list.
>
>> If you don't have it, you must maintain a dedicated list head element
>> with no object attached. That is a less safe and clean because it
>> ultimately leads to run-time type checks in the client code.
>
> I agree with the dedicated list head statement, but not the "less
> safe" part. You either have container or you have a list head (each
> represents one list, though yours potentially several).
>
> There is nothing to check about a list head- you simply begin there.
> If you have no "head.next", you have an empty list.

Not with doubly-linked lists. There is always Next, because the list is 
circular. When you delete an element from the list you always get two 
lists. Deletion of a single element is an idempotent operation unless 
you have a dedicated head or else have the list head pointer corrected.

List traversal when the list head is a pointer is performed like this:

    if Head /= null then
       This := Head;
       loop
          ... -- Do something
          This := This.Next;
          exit when This = Head;
       end loop;
    end if;

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Generic Embedded List Nodes

[Warren]

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

Re: Generic Embedded List Nodes

[Warren]

On Monday, 20 June 2016 03:25:48 UTC-4, Dmitry A. Kazakov  wrote:
> On 20/06/2016 04:42, Warren wrote:
> > On Sunday, 19 June 2016 16:35:32 UTC-4, Dmitry A. Kazakov  wrote:
> >> No, doubly-linked list deletion is O(1).
> >
> > Ok you're tracking the link in Element, which is fine. However, your
> > Element also needs a reference to the separately allocated object (which
> > is a problem for me). This requires two allocations instead of one.
> 
> No, that is the point. The object and the element (links) are in one 
> continuous chunk of memory. I believe this is what you meant under being 
> "embedded" nodes.
> 
> When an object is allocated, element + object is instead and the address 
> to the object's part is returned back from Allocate. Deallocate takes 
> the object's address, subtracts the offset and deallocates the whole chunk.
> 
> > I only need to insert head, traversal and delete. That's it!
> 
> Yes, and the schema above is as effective as it can be.
> 
> >>> In the embedded node case, I already have direct access to the
> >>> affected link node. To remove the node from a list I simply say:
> >>>
> >>>     R.Link_Node.Unlink;
> >>
> >> The operation Delete has the list head parameter (Container) not for
> >> traversing the list, but for modifying the list head if the first
> >> element is deleted from the list.
> >
> >> If you don't have it, you must maintain a dedicated list head element
> >> with no object attached. That is a less safe and clean because it
> >> ultimately leads to run-time type checks in the client code.
> >
> > I agree with the dedicated list head statement, but not the "less
> > safe" part. You either have container or you have a list head (each
> > represents one list, though yours potentially several).
> >
> > There is nothing to check about a list head- you simply begin there.
> > If you have no "head.next", you have an empty list.
> 
> Not with doubly-linked lists. There is always Next, because the list is 
> circular.

Mine ain't.

> When you delete an element from the list you always get two 
> lists. Deletion of a single element is an idempotent operation unless 
> you have a dedicated head or else have the list head pointer corrected.

In my list, when the last item is removed from the list, Head.Next = Null. Simple.
> List traversal when the list head is a pointer is performed like this:
> 
>     if Head /= null then
>        This := Head;
>        loop
>           ... -- Do something
>           This := This.Next;
>           exit when This = Head;
>        end loop;
>     end if;

delcare
  Node: access Emb_Node := Head.Next;
begin
  while Node loop
    -- do something with node
    Node := Node.Next;
  end loop;
end;

Anyway folks- thanks for your help but I now have a working solution. I'm signing off this thread.

Warren

Re: Generic Embedded List Nodes

[Niklas Holsti]

On 16-06-20 15:26 , Warren wrote:

> Anyway folks- thanks for your help but I now have a working solution. I'm signing off this thread.

Before signing off, do please describe your solution.

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

Re: Generic Embedded List Nodes

[Shark8]

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.

Re: Generic Embedded List Nodes

[Warren]

On Monday, 20 June 2016 15:33:16 UTC-4, Niklas Holsti  wrote:
> On 16-06-20 15:26 , Warren wrote:
> 
> > Anyway folks- thanks for your help but I now have a working solution. I'm signing off this thread.
> 
> Before signing off, do please describe your solution.

I thought I had the problem licked using the following generic Object_Of function, but when I whipped up an example, the compile problem returned (or there was pilot error):

   function Object_Of(
      Node: access Emb_Node; 
      Member: Natural
   ) return Object_Type is
      use System.Storage_Elements;
   
      A:    constant System.Address := Node.all'Address;
      B:    constant System.Address := A - Storage_Offset(Member);
      R:    Object_Type;
      for R'Address use B;
      pragma Import(Convention => Ada, Entity => R);
   begin
      return R;
   end Object_Of;

The compiler is complaining with:

warning: controlled object "R" must not be overlaid.

The test record looks like this:

   type My_Recd is
      record
         ID:         Natural;
         Node:       aliased Emb_Node;
         Name:       Unbounded_String;  
      end record;

and the Emb_Node looks like this:

   type Emb_Node is
      record
         Next:    access Emb_Node;
         Prev:    access Emb_Node;
      end record;

The Node member is one culprit because it has two Access members (which count as members needing initialization).   Unbounded_String may be another factor.

What is particularly galling about this is that the record already exists, and does NOT need initialization at this point. All I need the compiler do is return it to me based upon its address.  Arg!

To accomplish this, I may have to resort to invoking a C function. But I don't think that will work either. Not by System.Address at least. More head scratching to follow.

Warren

Re: Generic Embedded List Nodes

[Warren]

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

Re: Generic Embedded List Nodes

[Niklas Holsti]

On 16-06-21 05:20 , Warren wrote:
> On Monday, 20 June 2016 15:33:16 UTC-4, Niklas Holsti  wrote:
>> On 16-06-20 15:26 , Warren wrote:
>>
>>> Anyway folks- thanks for your help but I now have a working solution. I'm signing off this thread.
>>
>> Before signing off, do please describe your solution.
>
> I thought I had the problem licked using the following generic
> Object_Of function, but when I whipped up an example, the compile
> problem returned (or there was pilot error):
>
>    function Object_Of(
>       Node: access Emb_Node;
>       Member: Natural
>    ) return Object_Type is
>       use System.Storage_Elements;
>
>       A:    constant System.Address := Node.all'Address;
>       B:    constant System.Address := A - Storage_Offset(Member);
>       R:    Object_Type;
>       for R'Address use B;
>       pragma Import(Convention => Ada, Entity => R);
>    begin
>       return R;
>    end Object_Of;
>
> The compiler is complaining with:
>
> warning: controlled object "R" must not be overlaid.

The component My_Recd.Name, of the controlled type Unbounded_String, is 
making Object_Type also controlled. I well understand that the compiler 
does not want controlled objects to be overlaid with address clauses.

Instead of a function returning Object_Type, you could try returning an 
access to Object_Type, as produced by an instance of 
System.Address_To_Access_Conversions. In fact, if I understand your 
goals, you do not want Object_Of to return a _copy_ of the object 
containing the Emb_Node, the need is to _find_ that very object. 
Returning an access value is closer to what you want, I believe.

> The test record looks like this:
>
>    type My_Recd is
>       record
>          ID:         Natural;
>          Node:       aliased Emb_Node;
>          Name:       Unbounded_String;
>       end record;

If you don't get the address arithmetic to work, I believe that a set of 
mixin-generics could be used to add as many embedded Emb_Nodes to a 
tagged limited record, with access discriminants pointing to the 
containing record. This would eliminate the address arithmetic, at the 
cost of increasing the size of the record by the sizes of the 
discriminants (not a great deal).

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

Re: Generic Embedded List Nodes

[Dmitry A. Kazakov]

On 21/06/2016 07:52, Niklas Holsti wrote:

> If you don't get the address arithmetic to work,

There is a subtle difference between access and X'Address, but otherwise 
address arithmetic works. E.g. I can instantiate my implementation of 
linked lists with any type including unconstrained and non-tagged ones.

> I believe that a set of
> mixin-generics could be used to add as many embedded Emb_Nodes to a
> tagged limited record, with access discriminants pointing to the
> containing record.

Adding links afterwards is even worse than deriving objects from a 
abstract list node. Any derivation must be used sparingly in Ada which 
does not have full multiple inheritance. Once you have spent the proper 
parent type you won't get another one.

> This would eliminate the address arithmetic, at the
> cost of increasing the size of the record by the sizes of the
> discriminants (not a great deal).

The advantage of pool-based design is that no address arithmetic is 
needed for object operations. The list element is access to the object 
type. Address arithmetic is needed for list operations only.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Generic Embedded List Nodes

[Dmitry A. Kazakov]

On 21/06/2016 04:28, Warren wrote:

>  Also any use of malloc/free where
> possible must be avoided because these are performance killers (even
> when using jremalloc).

That is no problem, if node life cycle is known a custom pool deploying 
a FIFO arena in some chunk of memory is used.

One should avoid controlled object because killing the arena would not 
do any finalization.

This technique is used in compilers which need a lot of dynamic memory 
but always know when to free allocated objects.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Generic Embedded List Nodes

[Warren]

On Tuesday, 21 June 2016 01:52:51 UTC-4, Niklas Holsti  wrote:
> On 16-06-21 05:20 , Warren wrote:
> > On Monday, 20 June 2016 15:33:16 UTC-4, Niklas Holsti  wrote:
> >> On 16-06-20 15:26 , Warren wrote:
> >>
> >>> Anyway folks- thanks for your help but I now have a working solution. I'm signing off this thread.
> >>
> >> Before signing off, do please describe your solution.
> >
> > I thought I had the problem licked using the following generic
> > Object_Of function, but when I whipped up an example, the compile
> > problem returned (or there was pilot error):
> >
> >    function Object_Of(
> >       Node: access Emb_Node;
> >       Member: Natural
> >    ) return Object_Type is
> >       use System.Storage_Elements;
> >
> >       A:    constant System.Address := Node.all'Address;
> >       B:    constant System.Address := A - Storage_Offset(Member);
> >       R:    Object_Type;
> >       for R'Address use B;
> >       pragma Import(Convention => Ada, Entity => R);
> >    begin
> >       return R;
> >    end Object_Of;
> >
> > The compiler is complaining with:
> >
> > warning: controlled object "R" must not be overlaid.
> 
> The component My_Recd.Name, of the controlled type Unbounded_String, is 
> making Object_Type also controlled. I well understand that the compiler 
> does not want controlled objects to be overlaid with address clauses.
> 
> Instead of a function returning Object_Type, you could try returning an 
> access to Object_Type, as produced by an instance of 
> System.Address_To_Access_Conversions. In fact, if I understand your 
> goals, you do not want Object_Of to return a _copy_ of the object 
> containing the Emb_Node, the need is to _find_ that very object. 
> Returning an access value is closer to what you want, I believe.

That is correct (no copy). The suggestion for System.Address_To_Access_Conversions seems like a potential solution. The only other thing I can do is try to cheat with a C routine returning an address, but GNAT is just as likely to complain.

Warren

Re: Generic Embedded List Nodes

[Warren]

On Tuesday, 21 June 2016 03:22:11 UTC-4, Dmitry A. Kazakov  wrote:
> On 21/06/2016 04:28, Warren wrote:
> 
> >  Also any use of malloc/free where
> > possible must be avoided because these are performance killers (even
> > when using jremalloc).
> 
> That is no problem, if node life cycle is known a custom pool deploying 
> a FIFO arena in some chunk of memory is used.

My C++ implementation maintains a pool of objects. But I want to combine Node and Object as one.

Warren

Re: Generic Embedded List Nodes

[Dmitry A. Kazakov]

On 21/06/2016 12:32, Warren wrote:
> On Tuesday, 21 June 2016 03:22:11 UTC-4, Dmitry A. Kazakov  wrote:
>> On 21/06/2016 04:28, Warren wrote:
>>
>>>  Also any use of malloc/free where
>>> possible must be avoided because these are performance killers (even
>>> when using jremalloc).
>>
>> That is no problem, if node life cycle is known a custom pool deploying
>> a FIFO arena in some chunk of memory is used.
>
> My C++ implementation maintains a pool of objects. But I want to
> combine Node and Object as one.

No problem either. The pool takes care of that.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Generic Embedded List Nodes

[Warren]

On Tuesday, 21 June 2016 07:57:12 UTC-4, Dmitry A. Kazakov  wrote:
> On 21/06/2016 12:32, Warren wrote:
> > On Tuesday, 21 June 2016 03:22:11 UTC-4, Dmitry A. Kazakov  wrote:
> >> On 21/06/2016 04:28, Warren wrote:
> >>
> >>>  Also any use of malloc/free where
> >>> possible must be avoided because these are performance killers (even
> >>> when using jremalloc).
> >>
> >> That is no problem, if node life cycle is known a custom pool deploying
> >> a FIFO arena in some chunk of memory is used.
> >
> > My C++ implementation maintains a pool of objects. But I want to
> > combine Node and Object as one.
> 
> No problem either. The pool takes care of that.

That's not completely true- you would have the overhead of TWO pools, instead of one.

Warren

Re: Generic Embedded List Nodes

[Dmitry A. Kazakov]

On 21/06/2016 15:39, Warren wrote:
> On Tuesday, 21 June 2016 07:57:12 UTC-4, Dmitry A. Kazakov  wrote:
>> On 21/06/2016 12:32, Warren wrote:
>>> On Tuesday, 21 June 2016 03:22:11 UTC-4, Dmitry A. Kazakov  wrote:
>>>> On 21/06/2016 04:28, Warren wrote:
>>>>
>>>>>  Also any use of malloc/free where
>>>>> possible must be avoided because these are performance killers (even
>>>>> when using jremalloc).
>>>>
>>>> That is no problem, if node life cycle is known a custom pool deploying
>>>> a FIFO arena in some chunk of memory is used.
>>>
>>> My C++ implementation maintains a pool of objects. But I want to
>>> combine Node and Object as one.
>>
>> No problem either. The pool takes care of that.
>
> That's not completely true- you would have the overhead of TWO pools, instead of one.

No, it is one pool and one single call to allocate the Object_Type. 
Allocation in FIFO arena pool is a couple of machine instructions.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Generic Embedded List Nodes

[Jeffrey R. Carter]

On Tuesday, 21 June 2016 01:52:51 UTC-4, Niklas Holsti  wrote:
>
> The component My_Recd.Name, of the controlled type Unbounded_String, is 
> making Object_Type also controlled. I well understand that the compiler 
> does not want controlled objects to be overlaid with address clauses.

Funny how this application cannot possibly meet its timing requirements if it
does any allocation/deallocation, yet can meet its timing requirements using
Unbounded_String, which does allocation/deallocation internally.

-- 
Jeff Carter
"You couldn't catch clap in a brothel, silly English K...niggets."
Monty Python & the Holy Grail
19

Re: Generic Embedded List Nodes

[Niklas Holsti]

On 16-06-21 10:15 , Dmitry A. Kazakov wrote:
> On 21/06/2016 07:52, Niklas Holsti wrote:
>
>> If you don't get the address arithmetic to work,
>
> There is a subtle difference between access and X'Address, but otherwise
> address arithmetic works. E.g. I can instantiate my implementation of
> linked lists with any type including unconstrained and non-tagged ones.
>
>> I believe that a set of
>> mixin-generics could be used to add as many embedded Emb_Nodes to a
>> tagged limited record, with access discriminants pointing to the
>> containing record.
>
> Adding links afterwards is even worse than deriving objects from a
> abstract list node.

Why do you think so? For philosophical or practical reasons?

> Any derivation must be used sparingly in Ada which
> does not have full multiple inheritance. Once you have spent the proper
> parent type you won't get another one.

Mixin-generics are a work-around, but can be practical, IMO. On the 
other hand, it seems the OP is in control of and defines the object 
types, so embedded link nodes can be added manually without using 
generics, just by deriving object-specific types with suitable access 
discriminants from a root "embedded-link-node" type.

>> This would eliminate the address arithmetic, at the
>> cost of increasing the size of the record by the sizes of the
>> discriminants (not a great deal).
>
> The advantage of pool-based design is that no address arithmetic is
> needed for object operations. The list element is access to the object
> type. Address arithmetic is needed for list operations only.

But your pool-based design restricts objects to be linked into at most 
one list. The OP said that an object can be placed in two or more lists 
at the same time, and apparently the number of such lists varies 
according to the type of the object, depending on the number of embedded 
list nodes within the object.

The pool-based design can no doubt be extended to allow multiple lists, 
but it then becomes more complex.

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

Re: Generic Embedded List Nodes

[Niklas Holsti]

On 16-06-21 20:13 , Jeffrey R. Carter wrote:
> On Tuesday, 21 June 2016 01:52:51 UTC-4, Niklas Holsti  wrote:
>>
>> The component My_Recd.Name, of the controlled type Unbounded_String, is
>> making Object_Type also controlled. I well understand that the compiler
>> does not want controlled objects to be overlaid with address clauses.
>
> Funny how this application cannot possibly meet its timing requirements if it
> does any allocation/deallocation, yet can meet its timing requirements using
> Unbounded_String, which does allocation/deallocation internally.

Perhaps the Unbounded_Strings are altered very rarely, but the 
linked-list operations are frequent.

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

Re: Generic Embedded List Nodes

[Dmitry A. Kazakov]

On 2016-06-21 20:54, Niklas Holsti wrote:
> On 16-06-21 10:15 , Dmitry A. Kazakov wrote:
>> On 21/06/2016 07:52, Niklas Holsti wrote:
>>
>>> If you don't get the address arithmetic to work,
>>
>> There is a subtle difference between access and X'Address, but otherwise
>> address arithmetic works. E.g. I can instantiate my implementation of
>> linked lists with any type including unconstrained and non-tagged ones.
>>
>>> I believe that a set of
>>> mixin-generics could be used to add as many embedded Emb_Nodes to a
>>> tagged limited record, with access discriminants pointing to the
>>> containing record.
>>
>> Adding links afterwards is even worse than deriving objects from a
>> abstract list node.
>
> Why do you think so? For philosophical or practical reasons?

Practical reasons. If you derive from the list element base you cannot 
have scalar or other non-tagged objects as elements, but you still can 
have a class of elements. When you add links last, you cannot have a 
class, that in effect finalizes the list item.

> But your pool-based design restricts objects to be linked into at most
> one list. The OP said that an object can be placed in two or more lists
> at the same time, and apparently the number of such lists varies
> according to the type of the object, depending on the number of embedded
> list nodes within the object.
>
> The pool-based design can no doubt be extended to allow multiple lists,
> but it then becomes more complex.

It is no more complex. In fact my design is multiple lists from the 
start. Doubly-linked list is a specialization of.

BTW, a design based on inheritance requires multiple additive 
inheritance for lists. Ada does not have this even for interfaces. E.g.

    type Abstract_List_Item is abstract tagged record
       Next : not null access Abstract_List_Item'Class :=
                  Abstract_List_Item'Access;
       Previous : not null access Abstract_List_Item'Class :=
                  Abstract_List_Item'Access;
    end record;

    type My_List_Item is -- This is not Ada!
       new Abstract_List_Item as List_One
       or  Abstract_List_Item as List_Two with
    record
       X : Integer;
    end record;

Members and primitive operations are renamed to resolve name clashes.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Generic Embedded List Nodes

[Warren]

On Tuesday, 21 June 2016 14:56:06 UTC-4, Niklas Holsti  wrote:
> On 16-06-21 20:13 , Jeffrey R. Carter wrote:
> > On Tuesday, 21 June 2016 01:52:51 UTC-4, Niklas Holsti  wrote:
> >>
> >> The component My_Recd.Name, of the controlled type Unbounded_String, is
> >> making Object_Type also controlled. I well understand that the compiler
> >> does not want controlled objects to be overlaid with address clauses.
> >
> > Funny how this application cannot possibly meet its timing requirements if it
> > does any allocation/deallocation, yet can meet its timing requirements using
> > Unbounded_String, which does allocation/deallocation internally.
> 
> Perhaps the Unbounded_Strings are altered very rarely, but the 
> linked-list operations are frequent.

I only added the Unbounded_String for an example test program because Niklas wanted to see what I was going to use. So now I'll just leave the group to expend their excess energy on any further debate.

Warren

Re: Generic Embedded List Nodes

[Niklas Holsti]

On 16-06-21 13:31 , Warren wrote:
> On Tuesday, 21 June 2016 01:52:51 UTC-4, Niklas Holsti  wrote:
>> On 16-06-21 05:20 , Warren wrote:
>>> On Monday, 20 June 2016 15:33:16 UTC-4, Niklas Holsti  wrote:
>>>> On 16-06-20 15:26 , Warren wrote:
>>>>
>>>>> Anyway folks- thanks for your help but I now have a working solution. I'm signing off this thread.
>>>>
>>>> Before signing off, do please describe your solution.
>>>
>>> I thought I had the problem licked using the following generic
>>> Object_Of function, but when I whipped up an example, the compile
>>> problem returned (or there was pilot error):
>>>
>>>    function Object_Of(
>>>       Node: access Emb_Node;
>>>       Member: Natural
>>>    ) return Object_Type is
>>>       use System.Storage_Elements;
>>>
>>>       A:    constant System.Address := Node.all'Address;
>>>       B:    constant System.Address := A - Storage_Offset(Member);
>>>       R:    Object_Type;
>>>       for R'Address use B;
>>>       pragma Import(Convention => Ada, Entity => R);
>>>    begin
>>>       return R;
>>>    end Object_Of;
>>>
>>> The compiler is complaining with:
>>>
>>> warning: controlled object "R" must not be overlaid.
>>
>> The component My_Recd.Name, of the controlled type Unbounded_String, is
>> making Object_Type also controlled. I well understand that the compiler
>> does not want controlled objects to be overlaid with address clauses.
>>
>> Instead of a function returning Object_Type, you could try returning an
>> access to Object_Type, as produced by an instance of
>> System.Address_To_Access_Conversions. In fact, if I understand your
>> goals, you do not want Object_Of to return a _copy_ of the object
>> containing the Emb_Node, the need is to _find_ that very object.
>> Returning an access value is closer to what you want, I believe.
>
> That is correct (no copy). The suggestion for System.Address_To_Access_Conversions seems like a potential solution. The only other thing I can do is try to cheat with a C routine returning an address, but GNAT is just as likely to complain.

It now seems to me that the solutions suggested so far are too 
elaborate, and that a very simple solution exists: an embedded list node 
is just an ordinary component, derived from a tagged root type which 
holds the Prev and Next links, with an access discriminant referring to 
the containing object. The OP asked for a "generic" solution, but IMO a 
generic would not be simpler than this direct form.

Example code follows. Compiled but not tested.

package Emb_List
is

    -- The class of "embedded list nodes":

    type Emb_Node_T is tagged;

    type Emb_Node_Ref_T is access all Emb_Node_T'Class;

    type Emb_Node_T is tagged record
       Prev, Next : Emb_Node_Ref_T;
       -- Prev and Next are null if the node is not in any list.
       -- When the node is first in a list, Prev points to the list head.
       -- When the node is last in a list, Next is null.
    end record;

    subtype List_T is Emb_Node_T;
    -- A list head.
    -- Next points to the first node in the list.
    -- Prev is null.

    procedure Insert_At_Head (
       List : access List_T;
       Node : in     Emb_Node_Ref_T);
    -- Prepends Node at the head of the list.
    -- Assumes that Node is not in any list, to start with.

    procedure Delete (Node : in Emb_Node_Ref_T);
    -- Deletes the Node from the list it lies in, assuming that
    -- the Node does lie in a list.

    -- An example type with two embedded list nodes:

    type Integer_Object_T;

    type Integer_Emb_Node_T (Obj : access Integer_Object_T)
    is new Emb_Node_T with null record;

    type Integer_Object_T is limited record
       Value : Integer;
       Node1 : aliased Integer_Emb_Node_T (Integer_Object_T'Access);
       Node2 : aliased Integer_Emb_Node_T (Integer_Object_T'Access);
    end record;

    -- An example object:

    Int_Obj : Integer_Object_T;

    -- Two example lists, empty by default:

    List1, List2 : aliased List_T;

end Emb_List;



package body Emb_List
is

    procedure Insert_At_Head (
       List : access List_T;
       Node : in     Emb_Node_Ref_T)
    is
    begin
       List.Next.Prev := Node;
       Node.Next := List.Next;
       List.Next := Node;
       Node.Prev := Emb_Node_Ref_T (List);
    end Insert_At_Head;

    procedure Delete (Node : in Emb_Node_Ref_T)
    is
    begin
       Node.Prev.Next := Node.Next;
       Node.Next.Prev := Node.Prev;
       Node.Prev := null;
       Node.Next := null;
    end Delete;

begin

    -- Add the example object to the example lists:

    Insert_At_Head (List1'Access, Int_Obj.Node1'Access);
    Insert_At_Head (List2'Access, Int_Obj.Node2'Access);

    -- Delete from List2:

    Delete (Int_Obj.Node2'Access);

end Emb_List;


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

Re: Generic Embedded List Nodes

[G.B.]

On 21.06.16 12:31, Warren wrote:
> The suggestion for System.Address_To_Access_Conversions seems like a potential solution. The only other thing I can do is try to cheat with a C routine returning an address, but GNAT is just as likely to complain.

At the risk of being non-C-ish, could you require the
outer objects' type to have an operation that delivers
its own 'Access, so that when linking the object via
its embedded list thing, the latter could call said
operation?

Re: Generic Embedded List Nodes

[Randy Brukardt]

"Warren" <ve3wwg@gmail.com> wrote in message 
news:6100770a-774c-41a7-b1d9-498f80426835@googlegroups.com...
On Monday, 20 June 2016 15:47:12 UTC-4, Shark8  wrote:
...
>> 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 bounded containers are designed for the purpose of low-overhead 
operations; in particular, they don't do allocation/deallocation of memory 
for individual objects. You ought to check out whether those are high enough 
performance for your purposes before reinventing the wheel... (especially 
using the check suppression implemented in the latest GNAT versions).

(Most programmers, myself included, are terrible at determining what matters 
for performance of a particular application. The only way to be sure that 
something is too slow is to try it...)

                           Randy.

Re: Generic Embedded List Nodes

[Warren]

On Tuesday, 21 June 2016 17:38:36 UTC-4, Niklas Holsti  wrote:
...
>     type Emb_Node_T is tagged;
> 
>     type Emb_Node_Ref_T is access all Emb_Node_T'Class;
> 
>     type Emb_Node_T is tagged record
>        Prev, Next : Emb_Node_Ref_T;
>        -- Prev and Next are null if the node is not in any list.
>        -- When the node is first in a list, Prev points to the list head.
>        -- When the node is last in a list, Next is null.
>     end record;
> 
>     subtype List_T is Emb_Node_T;
>     -- A list head.
>     -- Next points to the first node in the list.
>     -- Prev is null.
...

The insertion, traversal and deletes are generally no problem. The problem occurs when traversing to access the object. Let's say you have a list of timed out sockets (in pseudo code):

node := head.next;
while node /= null loop
    next_node := node.next;
    -- now access the object holding "node" so that it can be freed
    node.unlink;
    Free(node's object);
    node := node_next;
end loop; 

I keep bumping back into this Ada compiler restriction, which is maddening. It doesn't seem easily fooled.

I think the only simple way to do this in Ada, is to allocate a very large array of 
Access to record values, for each socket (I know what the max # of sockets are). The descriptors start at zero so this works well.

The list link nodes can easily save and allow me to retrieve the POSIX socket (fd) number without any compiler restrictions. So when I traverse to a given node, I can pull the fd out of the link node, and know that I have socket 90345, for example. Then I can index to the socket's event record access value in the array.

Normally, I already know the fd in the event handler epoll/kqueue, but the lists get traversed for timeouts and deferred closes. So given a timeout node for example, I need to be able to get the object that belongs to it so I can do things like free it etc.

Warren

Re: Generic Embedded List Nodes

[Warren]

On Wednesday, 22 June 2016 20:37:08 UTC-4, Randy Brukardt  wrote:
...
> The bounded containers are designed for the purpose of low-overhead 
> operations; in particular, they don't do allocation/deallocation of memory 
> for individual objects. You ought to check out whether those are high enough 
> performance for your purposes before reinventing the wheel... (especially 
> using the check suppression implemented in the latest GNAT versions).

I just posted (to Niklas) what will likely be the solution- a large array indexed by socket number. That is prolly the cleanest way I can do this cheap, at the expense of a little bit of memory.

> (Most programmers, myself included, are terrible at determining what matters 
> for performance of a particular application. The only way to be sure that 
> something is too slow is to try it...)
> 
>                            Randy.

Agreed. In my day job (where we try lots of things), I do benchmarks on the C++ servers I write and maintain.  Experience shows that it takes very little to slow down the transaction rate and there are often surprises.  

Here though, in Ada, I'm just playing around with a version of it as a hobby horse. It would be nice if I could someday compare the Ada version against the C++ version. So I'm just chipping away at this.

Warren

Re: Generic Embedded List Nodes

[Warren]

On Wednesday, 22 June 2016 09:01:48 UTC-4, G.B.  wrote:
> On 21.06.16 12:31, Warren wrote:
> > The suggestion for System.Address_To_Access_Conversions seems like a potential solution. The only other thing I can do is try to cheat with a C routine returning an address, but GNAT is just as likely to complain.
> 
> At the risk of being non-C-ish, could you require the
> outer objects' type to have an operation that delivers
> its own 'Access, so that when linking the object via
> its embedded list thing, the latter could call said
> operation?

The issue is that you're starting with a Node_Type of some sort, which is present in the record.  GNAT won't let me do anything to compute the start of the record (actually computing it is ok, but won't let me use the record based upon that address). This is so messed up, that I've decided to abandon any semblance of this idea. Lucky for me, I can use a lookup array to do what I need efficiently.

Warren

Re: Generic Embedded List Nodes

[Niklas Holsti]

On 16-06-23 05:12 , Warren wrote:
> On Tuesday, 21 June 2016 17:38:36 UTC-4, Niklas Holsti  wrote:
> ...
>>     type Emb_Node_T is tagged;
>>
>>     type Emb_Node_Ref_T is access all Emb_Node_T'Class;
>>
>>     type Emb_Node_T is tagged record
>>        Prev, Next : Emb_Node_Ref_T;
>>        -- Prev and Next are null if the node is not in any list.
>>        -- When the node is first in a list, Prev points to the list head.
>>        -- When the node is last in a list, Next is null.
>>     end record;
>>
>>     subtype List_T is Emb_Node_T;
>>     -- A list head.
>>     -- Next points to the first node in the list.
>>     -- Prev is null.
> ...
>
> The insertion, traversal and deletes are generally no problem. The problem
> occurs when traversing to access the object.

Indeed I left out an example of traversal, sorry.

> Let's say you have a list of  timed out sockets (in pseudo code):
>
> node := head.next;
> while node /= null loop
>     next_node := node.next;
>     -- now access the object holding "node" so that it can be freed
>     node.unlink;
>     Free(node's object);
>     node := node_next;

(You surely meant next_node, above.)

> end loop;
>
> I keep bumping back into this Ada compiler restriction, which is
> maddening. It doesn't seem easily fooled.

That's the reason for having the derived descendants of Emb_Node_T, with 
the access discriminants. In my example, the discriminant Obj of an 
embedded Integer_Emb_Node_T points to the enclosing Integer_Object_T. 
Here is the relevant part of the example; to place it in the context of 
your example, above, imagine that Integer_Object_T is a potentially 
"time out socket":

    type Integer_Object_T;

    type Integer_Emb_Node_T (Obj : access Integer_Object_T)
    is new Emb_Node_T with null record;
    -- (Explanation added:) Obj accesses the Integer_Object_T
    -- which contains this Integer_Emb_Node_T.

    type Integer_Object_T is limited record
       Value : Integer;
       Node1 : aliased Integer_Emb_Node_T (Integer_Object_T'Access);
       Node2 : aliased Integer_Emb_Node_T (Integer_Object_T'Access);
    end record;

The Obj pointers are set automatically by the expressions 
Integer_Object_T'Access, which access the current instance of 
Integer_Object_T.

Here's a procedure to print out the Value components of all 
Integer_Object_T elements in a list of such elements:

    procedure Print_Integer_Values (List : in List_T'Class)
    is
       Node : Emb_Node_Ref_T := List.Next;
    begin
       while Node /= null loop
          if Node.all in Integer_Emb_Node_T'Class then
             Ada.Integer_Text_IO.Put (
                Integer_Emb_Node_T (Node.all).Obj.Value);
          end if;
          Node := Node.Next;
       end loop;
    end Print_Values;

(Compiled, not tested.)

By the way, the solution example I gave assumed that you want 
heterogeneous lists, in which any list can contain any type of object. 
That's why the above procedure Print_Integer_Values has to check if the 
current Node is an Integer_Obj_T before it can use the Obj discriminant 
to get to the object.

If you actually want homogeneous lists, in which any given list contains 
only elements of one and the same type, which corresponds to the type of 
the list head, I would drop the root type Emb_Node_T and define each 
embedded-node type separately from scratch. In this case a generic 
package to create doubly linked lists of a given type could be useful. 
If this is your preference, say it and I will make an example for you.

> I think the only simple way to do this in Ada, is to allocate
> a very large array of Access to record values, for each socket
> (I know what the max # of sockets are). The descriptors start at
> zero so this works well.

That would also work. Your choice, of course.

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

Re: Generic Embedded List Nodes

[Warren]

On Thursday, 23 June 2016 04:19:35 UTC-4, Niklas Holsti  wrote:
> On 16-06-23 05:12 , Warren wrote:
> > On Tuesday, 21 June 2016 17:38:36 UTC-4, Niklas Holsti  wrote:
> > ...
> >>     type Emb_Node_T is tagged;
> >>
> >>     type Emb_Node_Ref_T is access all Emb_Node_T'Class;
> >>
> >>     type Emb_Node_T is tagged record
> >>        Prev, Next : Emb_Node_Ref_T;
> >>        -- Prev and Next are null if the node is not in any list.
> >>        -- When the node is first in a list, Prev points to the list head.
> >>        -- When the node is last in a list, Next is null.
> >>     end record;
> >>
> >>     subtype List_T is Emb_Node_T;
> >>     -- A list head.
> >>     -- Next points to the first node in the list.
> >>     -- Prev is null.
> > ...
> >
> > The insertion, traversal and deletes are generally no problem. The problem
> > occurs when traversing to access the object.
> 
> Indeed I left out an example of traversal, sorry.

No problem. The other issue is that I need to support at least two lists. It gets rather messy when extending the object for each additional list, IMO.

I think the large array is going to work best with a list of nodes carrying file descriptors. That's not a general solution but it works where I need it. The array wasn't necessary for the C++ version, but I could have used that there as well.

Warren

Re: Generic Embedded List Nodes

[Niklas Holsti]

On 16-06-23 15:37 , Warren wrote:
> On Thursday, 23 June 2016 04:19:35 UTC-4, Niklas Holsti  wrote:
>> On 16-06-23 05:12 , Warren wrote:
>>> On Tuesday, 21 June 2016 17:38:36 UTC-4, Niklas Holsti  wrote:
>>> ...
>>>>     type Emb_Node_T is tagged;
>>>>
>>>>     type Emb_Node_Ref_T is access all Emb_Node_T'Class;
>>>>
>>>>     type Emb_Node_T is tagged record
>>>>        Prev, Next : Emb_Node_Ref_T;
>>>>        -- Prev and Next are null if the node is not in any list.
>>>>        -- When the node is first in a list, Prev points to the list head.
>>>>        -- When the node is last in a list, Next is null.
>>>>     end record;
>>>>
>>>>     subtype List_T is Emb_Node_T;
>>>>     -- A list head.
>>>>     -- Next points to the first node in the list.
>>>>     -- Prev is null.
>>> ...
>>>
>>> The insertion, traversal and deletes are generally no problem. The problem
>>> occurs when traversing to access the object.
>>
>> Indeed I left out an example of traversal, sorry.
>
> No problem. The other issue is that I need to support at least
> two lists. It gets rather messy when extending the object for
> each additional list, IMO.

My example had two embedded list nodes in the object, so the object 
could be a member of two lists. You can define as many nodes as you 
like, in the same record type, at the same time.

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

Re: Generic Embedded List Nodes

[Warren]

On Thursday, 23 June 2016 11:36:25 UTC-4, Niklas Holsti  wrote:
> On 16-06-23 15:37 , Warren wrote:
> > On Thursday, 23 June 2016 04:19:35 UTC-4, Niklas Holsti  wrote:
> >> On 16-06-23 05:12 , Warren wrote:
> >>> On Tuesday, 21 June 2016 17:38:36 UTC-4, Niklas Holsti  wrote:
> >>> ...
> >>>>     type Emb_Node_T is tagged;
> >>>>
> >>>>     type Emb_Node_Ref_T is access all Emb_Node_T'Class;
> >>>>
> >>>>     type Emb_Node_T is tagged record
> >>>>        Prev, Next : Emb_Node_Ref_T;
> >>>>        -- Prev and Next are null if the node is not in any list.
> >>>>        -- When the node is first in a list, Prev points to the list head.
> >>>>        -- When the node is last in a list, Next is null.
> >>>>     end record;
> >>>>
> >>>>     subtype List_T is Emb_Node_T;
> >>>>     -- A list head.
> >>>>     -- Next points to the first node in the list.
> >>>>     -- Prev is null.
> >>> ...
> >>>
> >>> The insertion, traversal and deletes are generally no problem. The problem
> >>> occurs when traversing to access the object.
> >>
> >> Indeed I left out an example of traversal, sorry.
> >
> > No problem. The other issue is that I need to support at least
> > two lists. It gets rather messy when extending the object for
> > each additional list, IMO.
> 
> My example had two embedded list nodes in the object, so the object 
> could be a member of two lists. You can define as many nodes as you 
> like, in the same record type, at the same time.

Ok, I see now (my eyes get bad by end of day after staring at screens all day).

I've been thinking today that by using the file descriptor as an index into a large array (of access to records), I can make this relatively clean in Ada. The array would not only act as a lookup for the event structures, but serve as a cache of such. I never really need to release them.

If I did want to reclaim any, I could start at the high end of the array, since those will be used under heaviest use. This is one of the nice features of the Unix kernel- open files always have the lowest available unit numbers assigned.

Warren

Re: Generic Embedded List Nodes

[Warren]

On Thursday, 23 June 2016 11:36:25 UTC-4, Niklas Holsti  wrote:
> My example had two embedded list nodes in the object, so the object 
> could be a member of two lists. You can define as many nodes as you 
> like, in the same record type, at the same time.

Sorry, yes I see it now.

>  type Integer_Object_T; 
>
>    type Integer_Emb_Node_T (Obj : access Integer_Object_T) 
 >   is new Emb_Node_T with null record; 

I think when I had tried to do this, I had the chicken and egg problem. But I see you used the forward undefined type mechanism. I may explore this further at some point-- it certainly seems to solve the problem as I laid it out.  I just need to find some quiet time. Thanks for the help.

Warren

Re: Generic Embedded List Nodes

[Warren]

On Thursday, 23 June 2016 11:36:25 UTC-4, Niklas Holsti  wrote:
...
> My example had two embedded list nodes in the object, so the object 
> could be a member of two lists. You can define as many nodes as you 
> like, in the same record type, at the same time.

I've tried twice now to post through google groups, but no luck. If this gets through, then know that I see those two lists. I'll reply more in full, if google sorts out the issue soon.

Warren

Re: Generic Embedded List Nodes

[Niklas Holsti]

On 16-06-24 15:49 , Warren wrote:
> On Thursday, 23 June 2016 11:36:25 UTC-4, Niklas Holsti  wrote:
>> My example had two embedded list nodes in the object, so the object
>> could be a member of two lists. You can define as many nodes as you
>> like, in the same record type, at the same time.
>
> Sorry, yes I see it now.
>
>>  type Integer_Object_T;
>>
>>    type Integer_Emb_Node_T (Obj : access Integer_Object_T)
>  >   is new Emb_Node_T with null record;
>
> I think when I had tried to do this, I had the chicken and egg problem.
> But I see you used the forward undefined type mechanism. I may explore
> this further at some point-- it certainly seems to solve the problem
> as I laid it out.  I just need to find some quiet time. Thanks for the help.

You are very welcome, Warren.

By the way, for record (so to speak), the procedures "Insert_At_Head" 
and "Delete" shown in my example each has an error: a possible use of a 
null reference. The versions below should be better, but they are still 
not tested.

    procedure Insert_At_Head (
       List : access List_T;
       Node : in     Emb_Node_Ref_T)
    is
    begin
       if List.Next /= null then
          List.Next.Prev := Node;
       end if;
       Node.Next := List.Next;
       List.Next := Node;
       Node.Prev := Emb_Node_Ref_T (List);
    end Insert_At_Head;

    procedure Delete (Node : in Emb_Node_Ref_T)
    is
    begin
       Node.Prev.Next := Node.Next;
       if Node.Next /= null then
          Node.Next.Prev := Node.Prev;
       end if;
       Node.Prev := null;
       Node.Next := null;
    end Delete;

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

Re: Generic Embedded List Nodes

[Warren]

On Saturday, 25 June 2016 01:50:41 UTC-4, Niklas Holsti  wrote:
...
> By the way, for record (so to speak), the procedures "Insert_At_Head" 
> and "Delete" shown in my example each has an error: a possible use of a 
> null reference. The versions below should be better, but they are still 
> not tested.

I see google groups finally posted my attempts to reply.  At this point, I think my best approach for this project will be to use a large array, since that will act as a cache in addition to a table of event records by file descriptor. Your approach may have application in another project.

Warren

Re: Generic Embedded List Nodes

[Warren]

On Saturday, 25 June 2016 01:50:41 UTC-4, Niklas Holsti  wrote:
> On 16-06-24 15:49 , Warren wrote:
..
>     procedure Insert_At_Head (
>        List : access List_T;
>        Node : in     Emb_Node_Ref_T)
>     is
>     begin
>        if List.Next /= null then
>           List.Next.Prev := Node;
>        end if;
>        Node.Next := List.Next;
>        List.Next := Node;
>        Node.Prev := Emb_Node_Ref_T (List);
>     end Insert_At_Head;

Niklas: I finally got a few minutes to revisit this and worked up a full example based upon yours.  I fear that the design is still flawed. I'm using a slightly modified version of this, but basically, the problem occurs at the line:

>        Node.Prev := Emb_Node_Ref_T (List);

with the exception:

raised PROGRAM_ERROR : niklas.adb:14 accessibility check failed

My example code is located on github here:  https://github.com/ve3wwg/ada_embedded_list

Maybe there is pilot error somewhere. I'm using: GNATMAKE 6.1.0.

Warren

Re: Generic Embedded List Nodes

[Warren]

On Friday, 1 July 2016 09:49:19 UTC-4, Warren  wrote:
> On Saturday, 25 June 2016 01:50:41 UTC-4, Niklas Holsti  wrote:
> > On 16-06-24 15:49 , Warren wrote:
> ..
> >     procedure Insert_At_Head (
> >        List : access List_T;
> >        Node : in     Emb_Node_Ref_T)
> >     is
> >     begin
> >        if List.Next /= null then
> >           List.Next.Prev := Node;
> >        end if;
> >        Node.Next := List.Next;
> >        List.Next := Node;
> >        Node.Prev := Emb_Node_Ref_T (List);
> >     end Insert_At_Head;
> 
> Niklas: I finally got a few minutes to revisit this and worked up a full example based upon yours.  I fear that the design is still flawed. I'm using a slightly modified version of this, but basically, the problem occurs at the line:
> 
> >        Node.Prev := Emb_Node_Ref_T (List);
> 
> with the exception:
> 
> raised PROGRAM_ERROR : niklas.adb:14 accessibility check failed
> 
> My example code is located on github here:  https://github.com/ve3wwg/ada_embedded_list
> 
> Maybe there is pilot error somewhere. I'm using: GNATMAKE 6.1.0.
> 
> Warren

Sorry, nevermind. When I allocate the list with:

    List1:   aliased access List_T := new List_T;

it is fine.  I suppose that the runtime was worried about dangling pointers when it was originally allocated on the stack frame in:

    List1:   aliased List_T;

Warren

Re: Generic Embedded List Nodes

[brbarkstrom]

Another suggestion is to add a numerical index to each node, as well as some
identifier (maybe a string or some other suitable type), and use a hash function
to calculate the index from the identifier.  Assuming you also use Ada access
variable to link the nodes together, this might be a useful way to implement
the type of design you seem to have in mind.  Linkages in a triply linked
list (see Knuth, Vol I index) can be handled this way, so you can have 
hierarchical structures.

Bruce B.

Re: Generic Embedded List Nodes

[Warren]

On Friday, 1 July 2016 15:50:40 UTC-4, brbar...@gmail.com  wrote:
> Another suggestion is to add a numerical index to each node, as well as some
> identifier (maybe a string or some other suitable type), and use a hash function
> to calculate the index from the identifier.  Assuming you also use Ada access
> variable to link the nodes together, this might be a useful way to implement
> the type of design you seem to have in mind.  Linkages in a triply linked
> list (see Knuth, Vol I index) can be handled this way, so you can have 
> hierarchical structures.
> 
> Bruce B.

I do actually have a numerical index already (as I mentioned before). I can use the socket file descriptor (POSIX) to index an array to directly arrive at a lookup.  But where that [fd] approach is clumsy is having to copy that file descriptor into each list node of the same object.

Warren