Semantics of dual push m-list

[WillyJL]

I understand the reason why m-list grows "from the back" and therefore iterates from the back to the front as the structure holds a reference to the last item pushed, but I feel like this becomes a bit confusing when applied to a dual push list.

With a dual push m-list, _push() and _push_back() add to the back, while iterating is also done from the back. _push_front() adds to the front, which is the last item to get iterated over. From what I could tell, there is no other way of addressing the list other than iterating, so whether it is "from the back" or "from the front" is just semantics, and indexes are not a concern of m-list from what I can see.

So I believe that when using a dual push m-list's _push_back() and the newly added item is the first to be iterated over, to the user this seems confusing and just backwards of the expected behavior.

I wanted to ask if adding an option, whether as an optional argument to LIST_DUAL_PUSH_DEF() or as a new type like LIST_DUAL_PUSH_REVERSE_DEF() (not ideal, first name that came to mind, suggestions welcome), that essentially just swaps the behavior of _push()/_push_back() with _push_front(), would be a possibility and/or it would be a welcome addition to upstream M*LIB.

I would be open to try implementing it myself, though I am not super familiar with M*LIB's internals so I could use a few pointers and general ideas of where to start implementing such an option, unless it is indeed a welcome idea and you'd prefer to implement it yourself of course.

Also, thank you for this awesome library!

[P-p-H-d]

I understand your argument. It seems valid and pertinent.

To implement such container you'll need to add new user macros and add an additional argument for the chain of internal macros (1 or 0), which is to test if it the old container or new container (Using a M_IF(newArg)(_push_back, _push_front) as argument for the function definition), which is not complicated.

However I wonder if it wouldn't be better to fix the semantics of the dual push list instead of creating another container. It will need its own OPLIST definition (in order not to export the REVERSE operator, which is used by algorithm). But it will be the same for creating another container. Still thinking....

Thank you for your report!

[P-p-H-d]

Additional information on open source code that uses LIST_DUAL_PUSH_DEF:
https://github.com/flipperdevices/flipperzero-firmware/blob/d1c3b0bc680c4eb4c79bbbc1f969b8756781aa34/furi/core/event_loop_i.h#L78

[WillyJL]

Funny that you link to flipper zero code, I've been active in that community for the last 2 years and that's how I found M*LIB 😆 I hadn't necessarily noticed that FuriEventLoop used a dual push m-list however; I came across this concern working on a separate project of mine where I wanted a linked list that i could iterate front to back and grow from the back, and dual push m-list worked for that though the naming semantics indicated the opposite.

However I wonder if it wouldn't be better to fix the semantics of the dual push list instead of creating another container.

I proposed adding a parameter / making a new container to avoid breaking changes in API behavior, since in this case especially it would change behavior without causing any noticeable compilation issues indicating something changed, so someone upgrading from older versions of M*LIB and not paying too much attention could end up in trouble. But I do also see the value in fixing it once and for all.

Maybe making a new container with a different name and get rid of LIST_DUAL_PUSH? This way upgrading without reading notes about breaking changes would still prevent the change going unnoticed, but question remains on the naming.

[WillyJL]

Also had a look at the example you linked from the flipperzero firmware, looks like their use of dual push list for PendingQueue is for a queue type container (duh) where they use _push_front() and _pop_back(), in which case I would argue the new semantics proposed here would make this usage clearer: _push_back() and _pop_front() sound more logical for this kind of usage, one tends to imagine a queue as growing from the back and shrinking at the front.

[P-p-H-d]

Pro:

• Iteration more natural
• API more compatible with ARRAY

Against:

• API Break
• API incompatible with simple list

[P-p-H-d]

Considering this, I don't think fixing the existing container is the best solution. I would probably go the path of adding a new data structure (LIST_BI_PUSH_DEF ?)

[P-p-H-d]

An implementation is available in https://github.com/P-p-H-d/mlib/tree/feature/bi-push-list but I struggle with the name:

• LIST_BI_PUSH_DEF
• LIST_BIF_DEF ? (aka for Bi-push pop Front allowing LIST_BIB_DEF -aka for Bi-push pop Back)
• LIST_BIPPF_DEF (Bi-Push PopFront)
• Other naming?

[WillyJL]

Yeah I'm not super sure on the naming either, it's a tough one. BI_PUSH is easier to remember, but doesn't explain the difference in the name itself. Going for a longer acronym like BIPPF would make it harder to use imo, but the name has more meaning to it (once one reads what the acronym is). I think the best compromise is LIST_BIF, as you mention this also allows for a LIST_BIB which is what the current LIST_DUAL_PUSH is for the most part (except growing/iterating being the other way around).

Also, the "F" and "B" can be seen as indicating which way it is iterated in, so LIST_BIF is Bi-push pop Front iterate Front-back, LIST_BIB is Bi-push pop Back iterate Back-front.

I was thinking maybe LIST_BIF for the new one, soft-rename LIST_DUAL_PUSH to LIST_BIB, and keep an LIST_DUAL_PUSH alias with the obsolete names macro but realized while typing this that it's "M_USE_SMALL_NAME" without mentioning "obsolete". So maybe just an alias from LIST_BIB to LIST_DUAL_PUSH, with no renaming; up to you of course.

So yeah I would go for LIST_BIF out of these options. I tried to come up with others but it's hard to convey the idea without getting a huge name, this seems like a good compromise that is also easy to remember.

Also I see you did a much better job of implementing this than my lazy attempt (as expected) 😆 , I'll close my PR; thank you for taking the time!