Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

Building a Low-Level Trie With Rust

DZone's Guide to

Building a Low-Level Trie With Rust

This is interesting because it's complex enough problem to require thinking for experienced developers, but it isn’t that complex — it just has a lot of details.

· Performance Zone
Free Resource

Evolve your approach to Application Performance Monitoring by adopting five best practices that are outlined and explored in this e-book, brought to you in partnership with BMC.

Before getting to grips with a distributed gossip system in Rust, I decided that it would be better to look at something a bit more challenging, but smaller in scope. I decided to implement the low-level trie challenge in Rust.

This is interesting because it is complex enough problem to require thinking even for experienced developers, but at the same time, it isn’t that complex — it just has a lot of details. It also requires us to do a lot of low-level stuff and manipulate memory directly, so that is something that would be an interesting test for a system level programming language.

On the one hand, even with just a few hours with Rust, I can see some elegance coming out of certain pieces. For example, take a look at the following code:

fn find_node(self: &Trie, key: &str) -> Result<NodeAndParent, TrieErrors> {
let header = self.trie_header();
if header.items == 0 {
return Err(TrieErrors::ValNotFound);
}
​
let node = self.node_header(mem::size_of::<TrieHeader>() as isize);
​
match node.find_match(None, 0, key) {
Err(NodeErrors::ValNotFound) |
Err(NodeErrors::PartialMatch{ closest: _})
=> Err(TrieErrors::ValNotFound),
Ok(matching_node) => Ok(matching_node)
}
}

This is responsible for searching on the trie for a value, and I like that the find_match function traverses the tree and allow me to return both an enum value and the closest match to this when it fails (so I can continue the process directly from there).

On the other hand, we have pieces of code like this:

image

And any line that has four casts in it is already suspect. And as I’m dealing with the raw memory, I have quite a bit of this.

And I certainly feeling the pain of the borrow checker. Here is where I’m currently stumped.

struct MyTrie{
/* fields */
}
​
struct Node {
/* fields */
}
​
impl MyTrie {
fn find(self: &MyTrie, key: &str) -> Option<&Node> {
unimplemented!()
}
​
fn delete(self: &mut MyTrie, key: &str) {
let result = self.find(key);
​
match result {
None => {}, // not there, nothing to do
Some(node) => {
self.delete_internal(node);
}
}
}
​
fn delete_internal(self: &mut MyTrie, node: &Node) {
unimplemented!()
}
}

This is a small and simple example that shows the issue. It fails to compile:

image

I have a method that takes a mutable MyTrie reference and passes it to a method that expects an immutable reference. This is fine and would work, but I need to use the value from the find method in the delete_internal method, which again needs a mutable instance. However, this fails with error[E0502]: cannot borrow `*self` as mutable because it is also borrowed as immutable.

I understand the problem, but I am not really sure how to solve it. The problem is that I kind of want the find method to remain immutable since it is also used in the read method, which can run on immutable instances.

Technically speaking, I could copy the values that I want out of the node reference and do a lexical scope that would force the immutable borrow to end, but I’m unsure yet what would be the best option.

It seems like a lot of work to get what I want in spite, and not with the help, of the compiler.

Learn tips and best practices for optimizing your capacity management strategy with the Market Guide for Capacity Management, brought to you in partnership with BMC.

Topics:
trie ,rust ,performance

Published at DZone with permission of Oren Eini, DZone MVB. See the original article here.

Opinions expressed by DZone contributors are their own.

THE DZONE NEWSLETTER

Dev Resources & Solutions Straight to Your Inbox

Thanks for subscribing!

Awesome! Check your inbox to verify your email so you can start receiving the latest in tech news and resources.

X

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}