Currently we have two separate linked list implementations:
clist/list: our native list implememations in core implementing singly-linked linear (list) and circular lists (clist).
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).
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?
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 ;-).
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 ;-))
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.
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.
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?
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
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.
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.
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.
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.
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.
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.
Currently we have two separate linked list implementations:
clist/list: our native list implememations incoreimplementing singly-linked linear (list) and circular lists (clist).utlist: imported linked-list implementation insysimplementing singly-linked linear lists (LL_and doubly-linked linear (DL_) and circular lists (CDL_).Both implementations have their respective benefits and drawbacks:
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?
Though it is hard to the eye to read the macro magic (especially, since
->nextcan be renamed) it's a pretty straight forward implementation based around looping over the list and doing the specific implementation ;-).Agreed. I counted that as a drawback with 'non-RIOT coding style'
I don't intend to merge those two (that's why I took care to always mention them as a pair ;-))
Yeah, well, now that you say it. I thought they used a quantum walk algorithm to traverse the lists.
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.
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?
as clist is singly-linked list, and
utlistonly has doubly-liked circular lists I would more look into the features lacking inlist;-). Otherwise you compare apples and oranges.listis "lacking" (in quotes because for the constrained usage oflistit makes sense) compared toutlist'sLL:+1:
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.
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.
I think we still should continue to discuss this. As for
gnrc_pktsnip_t(which usesutlist): a soft migration tolist_t(via e.g. some wrapper functions around theutlistmacros that then get ported tolist) might give some insights about what is more usable.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.
https://github.com/RIOT-OS/RIOT/issues/6209#issuecomment-529933152 still applies.
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.
GNRC has moved away from utlist now. Maybe we should just deprecate and drop utlist?