Riot: RFC: Merge utlist with clist/list

[kaspar030]

Well, for me utlist was a foreign code macro magic black box, that's why I started with clist initially. I actually don't thing that utlist.h would make it through our current review standards.

Some points:

• there's list and clist for performance reasons: clist does have to keep the list circular, list doesn't. That's only a couple of instructions, but list is used by RIOT's hottest code paths, so it matters (if some percent context switch throughput in benchmarks matter)

• clist can be used as-is as FIFO (queue) or LIFO (stack), with O(1) operations for adding/removing head or adding tail, but only requiring one pointer per object in the list

• maybe the latter is true for utlist, but who knows?

[miri64]

Well, for me utlist was a foreign code macro magic black box

Though it is hard to the eye to read the macro magic (especially, since ->next can be renamed) it's a pretty straight forward implementation based around looping over the list and doing the specific implementation ;-).

[miri64]

I actually don't thing that utlist.h would make it through our current review standards.

Agreed. I counted that as a drawback with 'non-RIOT coding style'

[miri64]

there's list and clist for performance reasons: clist does have to keep the list circular, list doesn't. That's only a couple of instructions, but list is used by RIOT's hottest code paths, so it matters (if some percent context switch throughput in benchmarks matter)

I don't intend to merge those two (that's why I took care to always mention them as a pair ;-))

[kaspar030]

Though it is hard to the eye to read the macro magic (especially, since ->next can be renamed) it's a pretty straight forward implementation based around looping over the list and doing the specific implementation ;-).

Yeah, well, now that you say it. I thought they used a quantum walk algorithm to traverse the lists.

[OlegHahm]

I would tend to keep both and maybe improve the documentation. Saying that, e.g., core/list is an optimized implementation that doesn't implement all features.

[kaspar030]

I would rather state that list/clist should be used unless it is missing a feature.
What features are missing in clist? Do we use the sorting? Need doubly linked lists?

[miri64]

What features are missing in clist? Do we use the sorting? Need doubly linked lists?

as clist is singly-linked list, and utlist only has doubly-liked circular lists I would more look into the features lacking in list ;-). Otherwise you compare apples and oranges. list is "lacking" (in quotes because for the constrained usage of list it makes sense) compared to utlist's LL

• name independence for "next" element
• sorting
• appending
• arbitrary insertion
• concatenation
• arbitrary deletion (fixed in #6211)
• member counting
• iterator, safe iteration
• search, scalar search
• item replacemend

[miri64]

I would tend to keep both and maybe improve the documentation. Saying that, e.g., core/list is an optimized implementation that doesn't implement all features.

:+1:

[kaspar030]

as clist is singly-linked list, and utlist only has doubly-liked circular lists I would more look into the features lacking in list ;-).

I consider clist the singly-linked list implementation of choice (over list), even if the circular nature is not needed. It can be used wherever a linked list is needed, but has a much cleaner API and more features.

list is only for the hottest code paths.

[stale[bot]]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. If you want me to ignore this issue, please mark it with the "State: don't stale" label. Thank you for your contributions.

[miri64]

I think we still should continue to discuss this. As for gnrc_pktsnip_t (which uses utlist): a soft migration to list_t (via e.g. some wrapper functions around the utlist macros that then get ported to list) might give some insights about what is more usable.

[stale[bot]]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. If you want me to ignore this issue, please mark it with the "State: don't stale" label. Thank you for your contributions.

[miri64]

https://github.com/RIOT-OS/RIOT/issues/6209#issuecomment-529933152 still applies.

[stale[bot]]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. If you want me to ignore this issue, please mark it with the "State: don't stale" label. Thank you for your contributions.