Re: [musl] [PATCH] search: provide twalk_r()

[Markus Wichmann <nullplan@gmx.net>]

On Fri, Feb 10, 2023 at 09:35:02AM +0100, Bartosz Golaszewski wrote:
> These extensions exist for a reason - they are simply useful and
> programs do use them out in the wild. twalk() on its own is brain-dead
> and only useful to small programs that can afford to have global
> variables. If you have a variable that tries to hold no global
> context, then the possibility to pass data to the walk callback is
> absolutely required. This is a general problem with those hash-map,
> binary tree etc. APIs in POSIX - they don't seem to be designed very
> well. GNU extensions try to address some of those issues.
>

Nobody ever questioned the usefulness of these extensions. The reason
musl does not adopt them immediately, however, is that without
standardization, we run the risk of future incompatible standardization,
and therefore, musl developing quirks. musl cannot remove functionality
without breaking ABI, and it is currently not built in a way that would
allow breaking ABI. So only new functions can be added, old ones must
remain indefinitely.

Case in point: qsort_r(). The BSDs had added another function of the
same name, but with different argument order (both in the qsort_r() call
and the comparison function). If musl had added the BSD version and then
the GNU version got standardized, musl would have had to work around the
incompatibility somehow. Or else be stuck with the nonconforming
version.

I concur that the hashmap and binary tree POSIX APIs are not very well
designed, and I question the need for them in libc. Personally, I would
counsel against using anything from search.h, especially when it does
not fit your needs. That would also get rid of the requirement for libc
to support nonstandard APIs. I mean, we are talking about data
structures here; it is not like there is a shortage of libraries
implementing these for all sorts of things.

> For me this means, that it's either limiting the availability of
> libgpiosim to glibc, implementing my own binary search tree (that
> would take up 300+ LOC for no reason and just end up copying existing
> code anyway) or pulling in some library that provides it in C (which
> would have to be something well maintained like GLib - which is huge)
> just to get that single functionality which I'd really like to avoid.
> In this context making musl provide twalk_r() upstream sounds like the
> best solution and I'm sure my library is not the only user.

But rolling your own would allow you to tune the tree to your needs. 300
LOC? Seems excessive to me. One sec, let me see... yes, I found an
intrusive red-black tree in my archives which clocks in at 209 lines.
Admittedly without twalk_r()-equivalent, but the existing traversal
function can be turned into that with no additional line. Since it is
intrusive, it does not even call malloc(). It has absolutely no ties to
the system. It could work on bare metal if needed. Well, OK, my
insertion conflict resolution strategy is to define that they don't
happen by way of assert(), so that could be done better, but otherwise,
no external dependencies happen.

And it wouldn't be for no reason, it would be for the reason that the
POSIX interface is lacking and not all environments your library runs on
support the extension you need.

Rolling your own would also make your library portable beyond Linux.
Beyond POSIX, even. This may not matter to you right now. It would also
mean you don't have to make demands of other libraries to get your own
stuff to work.

Ciao,
Markus