Not sure if this is of interest to you, but I was able to remove large amounts of unsafe from Node. I used your benchmarks, and it runs about the same speed on my machine as before.
There are a few caveats:
it uses smallvec for the label, which means the label will stay on the stack until it reaches len 10, then afterwards will be moved to the heap. There are a bunch of different sizes that I could've picked here but 10 seemed good for my purposes.
it passes cargo miri test which checks for undefined behaviour, previously patricia_tree would just crash.
I never used the binary_format feature so that part isn't working at all yet and has been removed from my code, I imagine you may want to add that back before something like this merges
The parts that really worried me were the un-aligned allocation combined with ptr::write which the std lib says causes UB. the use of transmute_copy too, which the docs say is one of the most unsafe things you can do, and could be error prone in edge cases.
Not sure if this is of interest to you, but I was able to remove large amounts of unsafe from
Node
. I used your benchmarks, and it runs about the same speed on my machine as before.There are a few caveats:
cargo miri test
which checks for undefined behaviour, previously patricia_tree would just crash.The parts that really worried me were the un-aligned allocation combined with
ptr::write
which the std lib says causes UB. the use oftransmute_copy
too, which the docs say is one of the most unsafe things you can do, and could be error prone in edge cases.