On Wed, 2026-02-11 at 12:52 +0000, Alice Ryhl wrote: > > Yes, many people assume "list widely used in kernel" implies "list is a > good idea". Unfortunately it is not the case. > > > > This applies to the red/black tree too, by the way. > > > > Can't fully follow, you mean that RB trees are supposedly overused, > > too? > > When I first suggested adding red/black tree abstractions in Rust > several years ago I was told by Greg that I couldn't do it because the > red/black tree was deprecated and no new users should be added.
Do you have a link or sth? First time in my life that I hear that RB trees shouldn't be used. If something is deprecated for good one would hope that's obvious. What's the justification? Should everyone use the B-Tree? RB trees are super widely used in CS. P. > > Later I found that this was more of a not-written-down recommendation > than a full deprecation, and since Rust Binder has codepaths where an > ENOMEM failure path is unacceptable for the map, we did end up adding a > Rust rb tree abstraction after all. But this is where I first heard of > this issue with lists and rb trees. > > Alice
