Re: Generic Embedded List Nodes

[Niklas Holsti <niklas.holsti@tidorum.invalid>]

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