From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on inbox.vuxu.org X-Spam-Level: X-Spam-Status: No, score=-1.1 required=5.0 tests=DKIM_SIGNED,DKIM_VALID, DKIM_VALID_AU,FREEMAIL_FROM,MAILING_LIST_MULTI,RCVD_IN_MSPIKE_H2 autolearn=ham autolearn_force=no version=3.4.4 Received: (qmail 30219 invoked from network); 10 Feb 2023 20:08:03 -0000 Received: from second.openwall.net (193.110.157.125) by inbox.vuxu.org with ESMTPUTF8; 10 Feb 2023 20:08:03 -0000 Received: (qmail 26088 invoked by uid 550); 10 Feb 2023 20:08:00 -0000 Mailing-List: contact musl-help@lists.openwall.com; run by ezmlm Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: List-ID: Reply-To: musl@lists.openwall.com Received: (qmail 26051 invoked from network); 10 Feb 2023 20:07:59 -0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=gmx.net; s=s31663417; t=1676059667; bh=+AC5hBhJAO0Mmw1pcVV3/ffXeXlhQF5uMuLulBIdEKs=; h=X-UI-Sender-Class:Date:From:To:Cc:Subject:References:In-Reply-To; b=i0Veo7grUTbZAnl4MSxuhr40pyKlZqDZfUQ4XdZBCPYf6rfZdvGQ0Akk6E37MEWKr Q+prGtiY1a9iTKCqfBlm5QtfeRA4AaLa6NdO9fEddWY7CHJ6Bwc9GWcv0KweXMeZxC oI1RPUba2OOHk+UuVYjPeVulEMzZMpH4Qa3KCwXiLFJsd4sTfMaDvgMfaLvf7A6Tl1 o39P6xnbWwIRqiatOU0EJzdIRCl4BaIf1UTTkZkSMEo6BmEkKq+2gW1zDor1MYO7Md w4r//njgcagy3IpBEfsFEKf2wRPJMc5jiq4jAMwoHCwW03PWovV5wK970E89KQFcsW XZo/7rh+bFdDw== X-UI-Sender-Class: 724b4f7f-cbec-4199-ad4e-598c01a50d3a Date: Fri, 10 Feb 2023 21:07:45 +0100 From: Markus Wichmann To: musl@lists.openwall.com Cc: Rich Felker , Bartosz Golaszewski Message-ID: <20230210200745.GB1903@voyager> References: <20230209204342.643785-1-brgl@bgdev.pl> <20230209211649.GX4163@brightrain.aerifal.cx> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.9.4 (2018-02-28) X-Provags-ID: V03:K1:jP+omB/rzfwX2xUjcIFrjdgBypaL1ab1UgUepqGhQy//FXaidY8 B/nTiWvWsXMIeN6pOXhDS3BsyO4tGRe+L7ocHLa33tkqZqXRk/IuC43gTk0Sy9V/JBl03bl lJHIcg8EatdDUG0PMgqV54CI3m9Q0oanIOQqnREuDuCXTUFrVs8RYHFu/Z4u0TbU3qDV+Cb 1Ej7OWYC4Pxt8fSLghOOQ== UI-OutboundReport: notjunk:1;M01:P0:kJ0ZKLs09fY=;aftcbQpo5CfDkNqZpYGIyBHEiMB SOP/f40Mm7MoDxx1BxtPzVkSFXN1cOJcSMRxg6vAI2YL9MkJUmR5EiTzFFtEnRmu8GJ1dsKls zgo2lnmlGas4vw15LxCPOyzvNSCbBoDUgLhsaoDUcdwZKC91lvPPoXDrxpzRZUnQC/dOa84KG 5jSqJw3vQgXZEIz/p1U/Lv0nxKz9/jD5/svL0lWPkcqGg4nTWHwcZc3Bjt3139ysMNA90uCXv RpX443n3G1d/rX/F7zcWiDg8V7Xmt5Ph1PHBwEBavj9ddGb7NwC6U+oRQxQ1AGnj5SNAkQLfS GlYwcU4anjSnHUYQH5PjXJygpqLdHLzWLARktAVFiNYWyvbZg9zN6fp8Vb7wL5LJ2Z0KBFvNz CGo/a8MGtiATbqWFNpykO3nrfirA9AoPKE+RLGNcRV/nn3shnJI1vrOndK1xBkRNOXdh+nuHB azY2DlyDxfd5o6SuhaGhV08LeuSLGhOjoM8wUCQr2ghBJu6OdxibHsKjAPdf7cWZq7UAHzCu/ DEwONhGXF3kujvK4Jmt+AHpI/re6+LmwhiOs76x5tNKVeRZl6RIXmqzaxJurEmQacOOgyjXSE ACSdNaiAB6/NevEutF4ibH1wDCbkeI5ktgoURaXAc83egXxNSV3PKK6tU15YFYpX1GnP5liTq qWo4fKxusVy/7G4rHWLrbEgLTQmkLPP0A33be1fHH83tZ7eiNmImPRL4LQ639mMXYouTpfACq cnBmIHExSWIHOnUXAATfEPbI1ca14Mj2U2H4//j/X7QBfqxsOrpW9xHmyPB2MPFpNwluALYnL jV4QAe87mjjf9k8FQFHuDauN9s1VOSZM6d2nDllcVcVYboFo2RcT3AJhxZDLzjj2Nv8sAv7Rz IpX6abjAVl9dKQzMh/NhFcUtdS8CqH5pYggYEC0CM1UssMHPObTPWWDVPGZEuR3L6kQoFq38i QTfkZw== Content-Transfer-Encoding: quoted-printable Subject: Re: [musl] [PATCH] search: provide twalk_r() 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