search

michaelsproul / rust_radix_trie

Fast generic radix trie implemented in Rust
https://docs.rs/radix_trie/
MIT License
188 stars 33 forks source link

Did get_ancestor match? #53

Open rendaw opened 5 years ago

rendaw commented 5 years ago

My use case is I have http routes like /a /b in the trie, and there are some dynamic routes like /z/* where I want to find the handler for /z and then do something with /*.

Right now you can

  1. Look up a value by exact match
  2. Look up the nearest ancestor, but without the ability to know if it's an exact match

The lookup seems like it keeps track of how much is left of the key while traversing the trie, so if that could be returned somehow the user could at least check if the remaining key length is 0, if not recover the utf8 suffix.

If the nodes stored parent nodes one could potentially walk back up the subtrie and concatenate prefixes to get a full utf8 prefix, and use the lengths to slice the suffix.

I'm not sure what other use cases there are here, so I'm not sure how much information would need to be returned in the general case, or what the interface should look like.

Is there an alternative way to achieve my use case with the current library?

rendaw commented 5 years ago

I might have been looking at the wrong place, it looks like trie node get keeps track of the prefix length, although it's not returned.

michaelsproul commented 5 years ago

You might be able to use subtrie to retrieve the node at /a/, and then iter to iterate through all the children (/a/*). I think the iterator will probably return the values from the subtrie with their prefix intact, but I'm not entirely sure.

rendaw commented 5 years ago

Sorry, I should have been more clear. The only node in there is /a/, so that subtree has no children. This is for something like dynamic routes, where the response is calculated by the part that comes after /a/. Either there are infinite valid routes (ex: /a/2018-07-23) or the routes aren't known before the request is made (referring to resources on external services), etc.

michaelsproul commented 5 years ago

Oh I see what you mean now. I think it would work if the TrieKey trait were made bidirectional (like fn encode(T) -> Vec<u8> and fn decode(&[u8]) -> T), but that would be quite a major change.

As a workaround, you could implement similar logic outside the library by using get_ancestor, retrieving the key from that ancestor node, and then using type-specific logic to strip the prefix. E.g. for a string, you could slice off the length of the prefix key: input_str[ancestor.key().unwrap().len()..]