Re: Generic Embedded List Nodes

[Warren <ve3wwg@gmail.com>]

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