Re:Go makes it easier to write correct, clear and efficient ...
by wahern on Friday May 10, 2019 @12:22PM
(#19879276)
The Linux kernel is the last place anybody should go to find simple, clean interfaces. That's just not how Linux rolls--almost everything else has a higher priority. The classic intrusive data structure in C is the link-list as implemented in BSD (though I'm sure it predated BSD): https://man.openbsd.org/queue#LIST_EXAMPLE
A red-black tree implemented in the same simple style by an OpenBSD developer a couple of decades later was adopted almost overnight by all BSDs: https://man.openbsd.org/tree#EXAMPLES
Unlike the Linux version, the BSD version is as type-safe as a C++ template, permits a node to exist in as many collections as you want (one member field per collection), and like a template the BSD version can inline the comparison function. You even have the option of making all the routines extern or static, which you can't even do with C++ templates.
What the Linux version has going for it is that it doesn't need to rely on the preprocessor so the implementation looks a little neater and more like a C++ template--no columns of backslashes as required with preprocessor-based generation. But that's a horrible tradeoff. queue.h and tree.h have basically been frozen for decades.[1] After initial curiosity wanes (day #2 of many thousands), nobody reads the headers because the interface is simple and never changes.
[1] Various systems have tweaked things here and there (e.g. to add parameterized trace points), but the original APIs never changed and code has always remained portable at the source level. The only big change over all that time was most systems (BSDs, macOS) eventually dropped CIRCLEQ after someone (I think a FreeBSD developer) posted benchmarks showing it sucked relative to TAILQ. I actually preferred CIRCLEQ; the entire header is small enough that for awhile I just copied it around everywhere.
A red-black tree implemented in the same simple style by an OpenBSD developer a couple of decades later was adopted almost overnight by all BSDs: https://man.openbsd.org/tree#EXAMPLES
Unlike the Linux version, the BSD version is as type-safe as a C++ template, permits a node to exist in as many collections as you want (one member field per collection), and like a template the BSD version can inline the comparison function. You even have the option of making all the routines extern or static, which you can't even do with C++ templates.
What the Linux version has going for it is that it doesn't need to rely on the preprocessor so the implementation looks a little neater and more like a C++ template--no columns of backslashes as required with preprocessor-based generation. But that's a horrible tradeoff. queue.h and tree.h have basically been frozen for decades.[1] After initial curiosity wanes (day #2 of many thousands), nobody reads the headers because the interface is simple and never changes.
[1] Various systems have tweaked things here and there (e.g. to add parameterized trace points), but the original APIs never changed and code has always remained portable at the source level. The only big change over all that time was most systems (BSDs, macOS) eventually dropped CIRCLEQ after someone (I think a FreeBSD developer) posted benchmarks showing it sucked relative to TAILQ. I actually preferred CIRCLEQ; the entire header is small enough that for awhile I just copied it around everywhere.