Re: Generic Embedded List Nodes

["Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de>]

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