diff options
| author | Wedson Almeida Filho <wedsonaf@gmail.com> | 2024-08-22 16:37:53 +0000 |
|---|---|---|
| committer | Miguel Ojeda <ojeda@kernel.org> | 2024-08-31 17:35:08 +0200 |
| commit | a0d13aac7022f95ec161c18d18e3d81172666ed8 (patch) | |
| tree | 20edfa995ec14cf2b1d1a7d89a2f5ec6fbe503f2 /rust/helpers | |
| parent | 6e6efc5fef4a1cdcccca3cffd5b73fd25d093352 (diff) | |
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/ [1]
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>
Diffstat (limited to 'rust/helpers')
| -rw-r--r-- | rust/helpers/helpers.c | 1 | ||||
| -rw-r--r-- | rust/helpers/rbtree.c | 9 |
2 files changed, 10 insertions, 0 deletions
diff --git a/rust/helpers/helpers.c b/rust/helpers/helpers.c index 173533616c91..30f40149f3a9 100644 --- a/rust/helpers/helpers.c +++ b/rust/helpers/helpers.c @@ -15,6 +15,7 @@ #include "kunit.c" #include "mutex.c" #include "page.c" +#include "rbtree.c" #include "refcount.c" #include "signal.c" #include "slab.c" diff --git a/rust/helpers/rbtree.c b/rust/helpers/rbtree.c new file mode 100644 index 000000000000..6d404b84a9b5 --- /dev/null +++ b/rust/helpers/rbtree.c @@ -0,0 +1,9 @@ +// SPDX-License-Identifier: GPL-2.0 + +#include <linux/rbtree.h> + +void rust_helper_rb_link_node(struct rb_node *node, struct rb_node *parent, + struct rb_node **rb_link) +{ + rb_link_node(node, parent, rb_link); +} |