RFC: Merge utlist with clist/list

[miri64]

Currently we have two separate linked list implementations:

1. clist/list: our native list implememations in core implementing singly-linked linear (list) and circular lists (clist).
2. utlist: imported linked-list implementation in sys implementing singly-linked linear lists (LL_ and doubly-linked linear (DL_) and circular lists (CDL_).

Both implementations have their respective benefits and drawbacks:

Implementation	Benefits	Drawbacks
core	accessible from core optimized (for RIOT) used by other RIOT structures (mutex, mbox, scheduler, ...)	only sub-set of operations implemented (compared to utlist) no doubly linked lists
utlist	more complete implementation well tested beyond RIOT very generalized (usage without casting possible)	macro-magic non-RIOT coding style may not be ideal code-size wise (e.g. `gnrc_pktbuf_search_type()` is better size-wise of as a function rather than using `LL_SEARCH_SCALAR()`)

I see benefits in keeping both, but the risk of code duplication exists (and in case of singly-linked lists is already present).

[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 core/list: add remove method #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.

👍

[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]

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]

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]

#6209 (comment) still applies.

[stale]

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.

[maribu]

GNRC has moved away from utlist now. Maybe we should just deprecate and drop utlist?