]> www.infradead.org Git - users/jedix/linux-maple.git/commit
rust: rbtree: add red-black tree implementation backed by the C version
authorWedson Almeida Filho <wedsonaf@gmail.com>
Thu, 22 Aug 2024 16:37:53 +0000 (16:37 +0000)
committerMiguel Ojeda <ojeda@kernel.org>
Sat, 31 Aug 2024 15:35:08 +0000 (17:35 +0200)
commita0d13aac7022f95ec161c18d18e3d81172666ed8
tree20edfa995ec14cf2b1d1a7d89a2f5ec6fbe503f2
parent6e6efc5fef4a1cdcccca3cffd5b73fd25d093352
rust: rbtree: add red-black tree implementation backed by the C version

The rust rbtree exposes a map-like interface over keys and values,
backed by the kernel red-black tree implementation. Values can be
inserted, deleted, and retrieved from a `RBTree` by key.

This base abstraction is used by binder to store key/value
pairs and perform lookups, for example the patch
"[PATCH RFC 03/20] rust_binder: add threading support"
in the binder RFC [1].

Link: https://lore.kernel.org/rust-for-linux/20231101-rust-binder-v1-3-08ba9197f637@google.com/
Signed-off-by: Wedson Almeida Filho <wedsonaf@gmail.com>
Reviewed-by: Alice Ryhl <aliceryhl@google.com>
Tested-by: Alice Ryhl <aliceryhl@google.com>
Reviewed-by: Boqun Feng <boqun.feng@gmail.com>
Reviewed-by: Benno Lossin <benno.lossin@proton.me>
Signed-off-by: Matt Gilbride <mattgilbride@google.com>
Link: https://lore.kernel.org/r/20240822-b4-rbtree-v12-1-014561758a57@google.com
[ Updated link to docs.kernel.org. - Miguel ]
Signed-off-by: Miguel Ojeda <ojeda@kernel.org>
rust/helpers/helpers.c
rust/helpers/rbtree.c [new file with mode: 0644]
rust/kernel/lib.rs
rust/kernel/rbtree.rs [new file with mode: 0644]