[Oml-devel] comment on linked list

[Wei D. <wd...@Pr...>]

I think this design will probably satisfy everybody.  A separately allocated
link node containing only the pointers will be cost something like 16~32 
bytes,
and it can be saved by using the embedded style macros.  I think the cost
of keeping a pointer to the linked item inside oml_list_node can be 
neglected
in most cases.

There's one thing left I'm not sure: how can we get back a correct typed 
pointer
from  oml_list_node? Following is the way I think of, assuming we have a 
"void *"
pointer pointing to the value in oml_list_node.

1. "oml_list(myItem *) free_list; " is expanded to something like the 
following

struct {
    oml_list_node head;
    myItem type[0];   /* only keep type information, no memory is used */
}  free_list;

So that the type information is saved in free_list.

2. When we need to extract a value from oml_list_node, we use the following
macro:

#define oml_list_value(list, node) \
(typeof((list)->type[0]))((node)->pvalue)

Should that be something to be implemented in OML?  Maybe you have a
better idea.


Thanks,

- Wei


Cucinotta Tommaso wrote:
> Right. The approach I prefer, in these cases, is to expose
> an embeddable "node" type, which, in at least some cases,
> is identical to the "iterator" type. The embeddable
> node may reside wherever you want, it is not constrained
> to reside within the type you are adding to the collection,
> even if it is probably the most meaningful choice, and you
> may have more than one embeddable node referring to the same
> item, but used in different collections.
>
> When declaring your item type, it resembles really much the list.h 
> approach:
>
> struct myItem {
>   oml_list_node free_node; /**< Node for linking in one list */
>   oml_list_node full_node; /**< Node for linking in another list */
> };
>
> When performing operations, you pass explicitly the pointer
> to the embeddable node, instead of the field name:
>
> oml_list(myItem *) free_list;
> oml_list(myItem *) full_list;
> myItem value;
>
> oml_list_add(&free_list, &value);  // Don't care about the node
> oml_list_add_node(&free_list, &value, &value.free_node); // 
> Application provides the node
>
> With a standard linked list, the first call allocates a node, makes it 
> point to the value, links it to the list.
> The second call only links the provided node into the list and makes 
> it point to the value.
>
> oml_list_del(&list, &value); // OML deallocates the node
> oml_list_del_node(&list, &value.free_node); // OML only unlinks the 
> node, without deallocating it; probably the node is invalidated.
>