ibraheemdev
API for getting immutable / mutable references to all values inside a node
My use-case is that I'm writing a tower::Service and I have a Node<Handler> where Handler implements tower::Service. What I want to do is implement poll_ready for this tower::Service, but I can't do it due to not being able to get mutable references to all values inside the node.
Would:
fn routes(&self) -> impl Iterator<Item = (&str, &T)>;
fn routes_mut(&mut self) -> impl Iterator<Item = (&str, &mut T)>;
Work for your use case?
Actually, I would be fine with only getting an iterator over the values. I looked into this a bit and wrote something that would do the job, which was just values and values_mut methods.
EDIT: I have a branch here if you want to check it out.
I would like to provide the routes as well. I think the best way to do this would be to store a list of full paths and indices at the root of the tree. Node prefixes could then just be an index and a range, and providing an iterator would just be self.full.iter()
I would like to provide the routes as well. I think the best way to do this would be to store a list of full paths and indices at the root of the tree. Node prefixes could then just be an index and a range, and providing an iterator would just be
self.full.iter()
How would this be implemented (maybe a general overview?) I'm not very familiar with radix trees. Would like to PR this!
I'm thinking something like:
pub struct Root<T> {
node: Node<T>,
// a list of prefixes, and nested indices
paths: Vec<(Vec<u8>, Vec<u8>)>
}
impl Root<T> {
// this would really be a concrete iterator type
fn routes(&self) -> impl Iterator<Item = (&str, &T)> {
self.paths.iter().map(|(path, indices)| {
unsafe {
&*indices.fold(&self.node, |node, i| &node.children[i]).value.get().unwrap()
}
})
}
// rest of node methods here...
}
When you insert a route, you add the route path, and the path (indices) to the value in the tree. It would need to be updated when the tree is shifted around. As an optimization, Node { prefix: Vec<u8>, .. } could be changed to a (usize, Range<usize>), pointing to a element and prefix in paths, but that isn't necessary at first.
This way iteration is very cheap; we don't have to allocate a stack for traversal.
I have implemented this on: https://github.com/yusdacra/matchit/tree/feat/values
My implementation is pretty different as it does not store indices, instead it takes advantage from the fact that the values don't get moved / removed. I have added tests to verify that it works properly. It however does add new unsafe, so it might not be wanted.
Your code aliases a Box, which is UB. You could do this with NonNull, but I would prefer the index-based solution.
Your code aliases a
Box, which is UB. You could do this withNonNull, but I would prefer the index-based solution.
Hmm, yeah I checked around and it seems it's UB... I will try the index-based solution again then. I first tried the index-based solution but couldn't figure out how to properly get the indices...