Current implementation is macro-based and sometimes it is hard to identify issues during build stage or debugging.
*_FOREACH_* equivalents weren't implemented intentionally to avoid confusion. Also I don't see huge advantage in it.
Details
Details
- Reviewers
brooks - Group Reviewers
Contributor Reviews (src) manpages
Write a dummy program to run this following new examples in queue(3).
Diff Detail
Diff Detail
- Repository
- rG FreeBSD src repository
- Lint
Lint Passed - Unit
No Test Coverage - Build Status
Buildable 69950 Build 66833: arc lint + arc unit
Event Timeline
Comment Actions
Unfortunately parsing diffs from git format-patch from phabricator side seems to be broken. It only shows the first (and the most trivial) commit. I'm using basic git diff here.
| share/man/man3/queue.3 | ||
|---|---|---|
| 1983 | 15.1 or 16.0? This shouldn't be MFCed for sure. | |
| share/man/man3/queue.3 | ||
|---|---|---|
| 62 | Please test this by adding this to your MANPATH and apropos tailq. | |
Comment Actions
Unfortunately parsing diffs from git format-patch from phabricator side seems to be broken. It only shows the first (and the most trivial) commit. I'm using basic git diff here.
We usually make a review for each commit, and link them together in a stack. Git arc does this, or you can click "add parent" in Phab.
| share/man/man3/queue.3 | ||
|---|---|---|
| 62 | $ apropos tailq | cat queue(3), SLIST_CLASS_ENTRY(3), SLIST_CLASS_HEAD(3), SLIST_CONCAT(3), SLIST_EMPTY(3), SLIST_EMPTY_ATOMIC(3), SLIST_ENTRY(3), SLIST_FIRST(3), SLIST_FOREACH(3), SLIST_FOREACH_FROM(3), SLIST_FOREACH_FROM_SAFE(3), SLIST_FOREACH_SAFE(3), SLIST_HEAD(3), SLIST_HEAD_INITIALIZER(3), SLIST_INIT(3), SLIST_INSERT_AFTER(3), SLIST_INSERT_HEAD(3), SLIST_NEXT(3), SLIST_REMOVE(3), SLIST_REMOVE_AFTER(3), SLIST_REMOVE_HEAD(3), SLIST_SPLIT_AFTER(3), SLIST_SWAP(3), STAILQ_CLASS_ENTRY(3), STAILQ_CLASS_HEAD(3), STAILQ_CONCAT(3), STAILQ_EMPTY(3), STAILQ_EMPTY_ATOMIC(3), STAILQ_ENTRY(3), STAILQ_FIRST(3), STAILQ_FOREACH(3), STAILQ_FOREACH_FROM(3), STAILQ_FOREACH_FROM_SAFE(3), STAILQ_FOREACH_SAFE(3), STAILQ_HEAD(3), STAILQ_HEAD_INITIALIZER(3), STAILQ_INIT(3), STAILQ_INSERT_AFTER(3), STAILQ_INSERT_HEAD(3), STAILQ_INSERT_TAIL(3), STAILQ_LAST(3), STAILQ_NEXT(3), STAILQ_REMOVE(3), STAILQ_REMOVE_AFTER(3), STAILQ_REMOVE_HEAD(3), STAILQ_REVERSE(3), STAILQ_SPLIT_AFTER(3), STAILQ_SWAP(3), LIST_CLASS_ENTRY(3), LIST_CLASS_HEAD(3), LIST_CONCAT(3), LIST_EMPTY(3), LIST_EMPTY_ATOMIC(3), LIST_ENTRY(3), LIST_FIRST(3), LIST_FOREACH(3), LIST_FOREACH_FROM(3), LIST_FOREACH_FROM_SAFE(3), LIST_FOREACH_SAFE(3), LIST_HEAD(3), LIST_HEAD_INITIALIZER(3), LIST_INIT(3), LIST_INSERT_AFTER(3), LIST_INSERT_BEFORE(3), LIST_INSERT_HEAD(3), LIST_NEXT(3), LIST_PREV(3), LIST_REMOVE(3), LIST_REPLACE(3), LIST_SPLIT_AFTER(3), LIST_SWAP(3), TAILQ_CLASS_ENTRY(3), TAILQ_CLASS_HEAD(3), TAILQ_CONCAT(3), TAILQ_EMPTY(3), TAILQ_EMPTY_ATOMIC(3), TAILQ_ENTRY(3), TAILQ_FIRST(3), TAILQ_FOREACH(3), TAILQ_FOREACH_FROM(3), TAILQ_FOREACH_FROM_SAFE(3), TAILQ_FOREACH_REVERSE(3), TAILQ_FOREACH_REVERSE_FROM(3), TAILQ_FOREACH_REVERSE_FROM_SAFE(3), TAILQ_FOREACH_REVERSE_SAFE(3), TAILQ_FOREACH_SAFE(3), TAILQ_HEAD(3), TAILQ_HEAD_INITIALIZER(3), TAILQ_INIT(3), TAILQ_INSERT_AFTER(3), TAILQ_INSERT_BEFORE(3), TAILQ_INSERT_HEAD(3), TAILQ_INSERT_TAIL(3), TAILQ_LAST(3), TAILQ_NEXT(3), TAILQ_PREV(3), TAILQ_REMOVE(3), TAILQ_REPLACE(3), TAILQ_SPLIT_AFTER(3), TAILQ_SWAP(3), slist_concat(3), slist_empty(3), slist_empty_atomic(3), slist_first(3), slist_init(3), slist_next(3), slist_insert_after(3), slist_insert_head(3), slist_remove(3), slist_remove_after(3), slist_remove_head(3), slist_remove_prevptr(3), slist_split_after(3), slist_swap(3), stailq_concat(3), stailq_empty(3), stailq_empty_atomic(3), stailq_first(3), stailq_init(3), stailq_next(3), stailq_insert_after(3), stailq_insert_head(3), stailq_insert_tail(3), stailq_last(3), stailq_remove(3), stailq_remove_after(3), stailq_remove_head(3), stailq_reverse(3), stailq_split_after(3), stailq_swap(3), list_concat(3), list_empty(3), list_empty_atomic(3), list_first(3), list_init(3), list_next(3), list_insert_after(3), list_insert_before(3), list_insert_head(3), list_prev(3), list_remove(3), list_remove_head(3), list_replace(3), list_split_after(3), list_swap(3), tailq_concat(3), tailq_empty(3), tailq_empty_atomic(3), tailq_first(3), tailq_init(3), tailq_next(3), tailq_insert_after(3), tailq_insert_before(3), tailq_insert_head(3), tailq_insert_tail(3), tailq_last(3), tailq_prev(3), tailq_remove(3), tailq_remove_head(3), tailq_replace(3), tailq_split_after(3), tailq_swap(3) - implementations of singly-linked lists, singly-linked tail queues, lists and tail queues | |
| share/man/man3/queue.3 | ||
|---|---|---|
| 62 | Thanks Minsoo. This one name, of one manual, is multiple screen fulls on standard console or even my cell phone. That's very difficult to read. I can't even select all of the lines to suggest a comment on desktop firefox. Is there a way we can make this more usable? Would it make sense if we did something like this? This renders to two standard lines. .Sh NAME .Nm SLISTP , .Nm STAILQ , .Nm LIST , .Nm TAILQ , .Nm slist , .Nm stailq , .Nm list , .Nm tailq , .Nd implementations of singly-linked lists, singly-linked tail queues, lists and tail queues | |
Comment Actions
@ziaee I splitted queue.3 into four man pages, so each of them should have length of 50% of the original NAME section (1/4 * 2 for function-based API).
| share/man/man3/list.3 | ||
|---|---|---|
| 5 | Can I keep BSD-3-Clause for the original and use BSD-2-Clause for myself, or should I use existing 3-clause for my new function-based API as well? | |
Comment Actions
generally I like the concept. If this isn't just text motion, though, I'd split it into (1) move things to new man page with as few other changes as is needed to make them work and (2) improvements, etc as a second commit.
I'm just commenting on the copyright / spdx issues at the moment.
| share/man/man3/list.3 | ||
|---|---|---|
| 5 | That's tricky to communicate with SPDX. But you can't use SPDX for the old code. You have to include the whole thing (or at least that's the project's policy since the regents haven't consented to using an indirect pointer to their license). If it were me, since SDPX expressions make it tough, I'd just do BSD-3-Clause since it's close enough to my preferred license and it would make things simpler. However, it isn't up to me. I think it would be up to the Foundation, though, since they are the indicated copyright holder. I know their contracts require specific language for wok done for them, so best check with them for the details. I helped them craft a sane policy, and I'd rather not second guess it unless there's a really compelling reason (eg, something we didn't think of at the time). | |
| sys/sys/tailq.h | ||
| 253 | opps? | |
| share/man/man3/list.3 | ||
|---|---|---|
| 5 | Then I guess we need to wait until Monday... | |
Comment Actions
To be honest, I'm not thrilled to have a whole new set of functions for doing something already covered by queue.h and used extensively throughout the tree. These functions don't provide any type checking or debug assertions/poisoning like the queue.h macros do. These functions might be easier to use for someone not used to queue.h, but there are tons of examples of queue.h macro usage in the tree to draw from.
Comment Actions
@imp separated commits. I'll keep the 3-clause license and ask the foundation on Monday.
Comment Actions
asserts I wrote were... nonsense. We should let users declare their own asserts instead.
Comment Actions
Type checking is done here and there is no need for (void *) casting. containerof() will return the structure that contains the node and other data. For assertion, we can let users to declare their own assert functions and call it in the headers, but I forgot to implement it here.
This might look like reinventing the wheel because the problem of macro hell isn't that significant in queue(3), but things are worse in tree(3). Tweaking logics in WAVL tree implementation often fails due to macro generate/prototype, which wouldn't have happened with function-based implementation. It also comes as a barrier to first-time contributors or junior programmers because most data structure courses at university teach struct+function mechanism, not macro-based ones. I'm also one of those junior developers, and building and debugging my scheduler patch with the macro-based API would be nightmare.
Existing code and developers who prefer the macro-based APIs can stick with it. IMHO it will never be deprecated.
Comment Actions
No, I mean that when when I define a list or queue head with LIST_HEAD, etc., I also declare the type of the item within that list. Attempting to insert an item of a different type results in a compile error rather than runtime memory corruption. This checking is useful, and is the entire reason for using macros in the first place. containerof doesn't provide any checking.
This might look like reinventing the wheel because the problem of macro hell isn't that significant in queue(3), but things are worse in tree(3). Tweaking logics in WAVL tree implementation often fails due to macro generate/prototype, which wouldn't have happened with function-based implementation. It also comes as a barrier to first-time contributors or junior programmers because most data structure courses at university teach struct+function mechanism, not macro-based ones. I'm also one of those junior developers, and building and debugging my scheduler patch with the macro-based API would be nightmare.
This is really just an argument for moving away from C entirely. And I'd quite like that personally, but it's easier said than done.
I'll also point out that a good way to confuse developers, especially junior developers, is to have more than one standard way to accomplish a common task.
Existing code and developers who prefer the macro-based APIs can stick with it. IMHO it will never be deprecated.
I'm not worried about writing code, but rather reading and debugging it. There are lots of ways to implement linked lists, learning a new one isn't hard. What's more painful is dealing with code written using multiple styles, conventions, etc. because various authors think their style is superior for some subjective reason, versus something that is written in a consistent way. To wit, keeping in mind that we also have list.h, llist.h, etc. in the linuxkpi: https://xkcd.com/927/
My aim isn't to discourage you from improve upon system headers like queue.h or tree.h, but there's a lot of value in trying to familiarize oneself with existing conventions in a codebase before deciding that something needs to be replaced.
Comment Actions
Fair point.
This might look like reinventing the wheel because the problem of macro hell isn't that significant in queue(3), but things are worse in tree(3). Tweaking logics in WAVL tree implementation often fails due to macro generate/prototype, which wouldn't have happened with function-based implementation. It also comes as a barrier to first-time contributors or junior programmers because most data structure courses at university teach struct+function mechanism, not macro-based ones. I'm also one of those junior developers, and building and debugging my scheduler patch with the macro-based API would be nightmare.
This is really just an argument for moving away from C entirely. And I'd quite like that personally, but it's easier said than done.
My original implementation of minmax caching on wavl (using prev and next) always failed CI build on github, and only succeeded when I changed the logic to do full search from root. The issue was macro generation/prototype thing and it was hard to understand for me. Most cases macros are less flexible than functions. Many developers' first language is not C, and C macros could be quite challenging for them. Functions not only helps improving their DX but also prevents programming errors that comes from unfamiliarity with C macros (Other languages I use don't have C-style macros).
I'll also point out that a good way to confuse developers, especially junior developers, is to have more than one standard way to accomplish a common task.
Existing code and developers who prefer the macro-based APIs can stick with it. IMHO it will never be deprecated.
I'm not worried about writing code, but rather reading and debugging it. There are lots of ways to implement linked lists, learning a new one isn't hard. What's more painful is dealing with code written using multiple styles, conventions, etc. because various authors think their style is superior for some subjective reason, versus something that is written in a consistent way. To wit, keeping in mind that we also have list.h, llist.h, etc. in the linuxkpi: https://xkcd.com/927/
My aim isn't to discourage you from improve upon system headers like queue.h or tree.h, but there's a lot of value in trying to familiarize oneself with existing conventions in a codebase before deciding that something needs to be replaced.
I started working on this when it was clear that cached wavl implementation needs a groundup implementation. It won't be implemented in macros like the existing RB_* for my sanity, and in that case users will question why cached rbtree is implemented in non-macro way and its usage differs from other data structures. Either case there will be multiple ways to work with data structures.
I minimized the confusion of having two implementations by documenting them in the same man page. Splitting queue(3) is inevitable anyways because its name section is too long, and this gives a good opportunity to do so.
Comment Actions
I would strongly encourage you to work towards having a build-compile-test loop that does not rely on github or any third-party CI. You will be much more productive if you don't have to wait for CI to run in order to discover compile errors. It should take maybe 5 seconds to check whether your latest edits build.
and only succeeded when I changed the logic to do full search from root. The issue was macro generation/prototype thing and it was hard to understand for me. Most cases macros are less flexible than functions. Many developers' first language is not C, and C macros could be quite challenging for them. Functions not only helps improving their DX but also prevents programming errors that comes from unfamiliarity with C macros (Other languages I use don't have C-style macros).
I don't know what to say to this. C macros can be painful to read, are hard to write, and you can do terrible and magical things with them.
Comment Actions
I usually do. But it's snowing really bad outside while my PC is in the office, so I had to work from home with my macbook. I created PR to see my changes build or not.