Re: Generic Embedded List Nodes

[Warren <ve3wwg@gmail.com>]

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