Trying Out Rust Binary Tree Maps
alphabet binary tree
I wanted to be able to use Hashmaps in my Raspberry Pi Pico projects. While I think it’s possible to get them running on there, I wanted to explore alternatives before I violate best practices to see if something suitable exists.
In that search, I found that in the alloc crate, there is a neat lil’ tool that I can use as an adequate stand-in.
This post will be rather short, but if you’re interested in a very deep dive by a contributor of Rust, please read this post. It’s very long but is coming from a person who deeply understands this tech, whereas I am learning about it literally as I am writing this.
alloc::collections::btree_map
At first glance, btree_map has all the makings of the super-fast, key-value store system that I have come to use as my go-to for all things state-management.
Let’s look at some code:
#[test] fn test_btree_map() {
// instantiate the tree map
let mut btm = BTreeMap::new();
// Insert some super basic test data
btm.insert("a", 32);
btm.insert("b", 64);
btm.insert("c", 128);
// expect to see that the key “a” is 32
assert_eq!(btm.get("a"), Some(&32));
btm.insert("a", 256);
println!("{:?}", btm);
// expect that the key “a” is no longer 32, and is now 256
assert_eq!(btm.get("a"), Some(&256));
}
// The println! in the code above shows this: {"a": 256, "b": 64, "c": 128}
So above we create a binary tree map, insert 3 key-value pairs, and then update the first key-value pair. The beauty of that is we never needed to create logic to isolate that first key, “a”. Just by asking the map to get “a” the appropriate key is found, and that value is replaced.
This is great because it eliminates complexity from the application side. Just find “a” for me, please!
Often times it’s required in application code to not only have the context of “why” the key “a” needs to be retrieved, but then also write and maintain code then hunt down “a” from the structure where it’s being stored. Not so here!
Removing Keys
The next step after adding and updating is of course removal.
btm.remove("a"); assert_eq!(btm.get("a"), None);
I added these two lines to the test I had above, and it worked.
So just like that I now have a dynamic structure that will handle memory allocation
on its own. This is wildly more efficient than how I approached this in my initial designs, as I wasn’t aware that I would be able to handle memory allocations this simply.
I won’t get too exhaustive here
The Rust Docs for this feature are fantastic and are adequate for a Rust newb like myself to get work done. The fact that the alloc crate is available and works in my Raspberry Pi Pico projects which that the #![no_std] declaration is really going to make a difference in my efforts.
Over time if I find some other great bits that are useful I’ll come back here and update this; or at least link to newer posts that contain the goodies.
