C-like List implementation in rust

[tcaputi]

Hello. I'm a c programmer, but I'm trying to learn Rust. One of the first things that I sat down and tried to do is re-implement one of my other projects using Rust's language features. I immediately hit issues when the first thing I tried to port over was my c implementation of a list with inline links. I can't figure out a way to do this in Rust. My implementation (which is very similar to the Linux kernel's and several other projects) looks something like this:

/* list node for linking structures via a pil_list_t */
typedef struct pil_list_node {
	struct pil_list_node *ln_prev;		/* pointer to previous list node */
	struct pil_list_node *ln_next;		/* pointer to next list node */
} pil_list_node_t;

/* structure representing a list */
typedef struct pil_list {
	u32 l_entries;			/* number of entries in the list */
	u32 l_struct_off;		/* offset of the pil_list_node_t into the struct */
	struct pil_list_node l_head;	/* head of the list */
} pil_list_t;

When I have a struct that I would like to be able to be placed on a list, all I need to do is add a pil_list_node to the struct and use the offset of that node into the struct to create the list head itself:

typedef struct test_listobj {
	u64 tl_id;
	pil_list_node_t tl_node;
} test_listobj_t;

void pil_test_list(void) {
    ...
	pil_list_init(&list, offsetof(test_listobj_t, tl_node));
}

Then I can interact with the list using functions like this:

void pil_list_insert_head(pil_list_t *list, void *obj){
	pil_list_node_t *node = list_obj_node(list, obj);

	list->l_entries++;
	node->ln_prev = &list->l_head;
	node->ln_next = list->l_head.ln_next;
	list->l_head.ln_next->ln_prev = node;
	list->l_head.ln_next = node;
}

With this implementation, I can have a structure that can be placed on as many lists as I would like (simply by adding more pil_list_node_t's to the struct and defining new lists to point to different nodes) and I dont need any extra memory allocations for the nodes themselves. I realize I could create a generic list, but this would perform extra memory allocations for the the list nodes themselves, which I would like to avoid. Is there a way to do this in Rust while retaining these advantages? Thanks a lot.

[kornel]

Linked lists are the worst thing you could try to do in Rust, especially to learn Rust. They don't fit the ownership/borrowing model, so you'll immediately run into a wall:

http://cglab.ca/~abeinges/blah/too-many-lists/book/

I recommend trying to reinvent Vec as an exercise

[tcaputi]

Interesting. I'll take a look at that when I get home tonight. Thanks a lot.

[tcaputi]

Hmmmmm. So it looks like the implementation you linked doesn't use inline nodes. Are you (or anyone else) aware or implementations that do use inline nodes?

[sfackler]

There are a couple of crates implementing intrusive linked lists - e.g. https://crates.io/crates/intrusive-collections

[juleskers]

If you're interested in data structure internals, maybe also the im crate sources are interesting reading; high performance immutable data structures, great talk at RustFest Paris. Be wary though that it will use many of the more advanced Rust-isms.

If you are want to focus more on learning Rust in general, I'd recommend literally any other "toy problem" than linked list implementation
As Kornel says, linked lists an extremely bad fit to Rust's strong points. All the edge cases are virtually impossible to formally prove correct in Rust's syntax, so you end up going against the compiler safety net, instead of being supported by it.

It would be like learning awk by implementing an http-server, or learning Perl by writing an assembly-optimised vector math library. Can be done, but it's so far away from the intended use case that it becomes incredibly unpleasant. Such exercises are better postponed until you are more familiar with the basics.

[tcaputi]

@sfackler I think that's what I'm looking for. I'll look into it more tonight.
@juleskers Thanks for the link. I'll take a look at that as well (I'm not 100% sure what they mean by immutable though)

I appreciate the advice to try simpler problems first. However, what I am more interested in is evaluating whether Rust is a good candidate for a database project I've been working on for a month or 2 in C. I'm at the point where I have a pretty sizable amount of code in C, but not quite enough yet that I couldn't consider switching to a different language at this point. After talking with a few colleagues, they have convinced me to look into Rust for its compile-time safety and better cross-platform support.

I need to keep looking into everything more, but I'm actually very surprised that some things I consider to be basic data structures for low level programming (like inline linked lists) are fairly complicated to implement and work with in Rust. I kind of hope this is just part of the learning curve or else I might be forced to stick with C.

Thanks a lot for the pointers though.

[skysch]

It's not usually that these things are complicated to implement in the abstract, but that they are complicated to implement in a way that ensures they are safe (which is arguably true in C as well.) If you're willing to dip into unsafe and trust yourself to write correct data structures, things are not much harder than they are in C, but if you do that too much, there's less of an advantage to move away from C.

Speaking personally, there are other conveniences that I would miss enough that I'm willing to put up with Rust even when the C implementation easier to write and no less safe: things like std library UTF-8 support, pattern matching, and Cargo are enticing features to me, even if Rust wasn't a safe language.

In any case, I don't see anything in your code that can't be mostly translated straight into Rust using raw pointers. Maybe you'd have to use a trait to specify the type relations rather than offsetof? Generics might be tricky, but C doesn't even offer that, so there's nothing to compare in that direction.

[steveklabnik]

I recently was in a conversation where this came up. Someone said this:

I really want to like Rust.

But writing a doubly linked list was already shown to be difficult [1], and now closures are too ... It really feels like this is not a language to "get things done". Please let someone prove me wrong.

[1] Why Writing a Linked List in (safe) Rust is So Damned Hard

and I replied with this:

The core of it is two things: mindset, and how programmers think about learning languages.

Mindset: there's two things at play here. The first is that C programmers tend to reach for linked lists by default. It's a CS 101 data structure. Not super hard. A Rust programmer, however, would reach for a vector (or a deque) by default. For many use-cases, these structures are better, thanks to amortized allocations + cache reasons. As always, depends on exactly what you're doing. The second mindset issue is write vs use; C programmers tend to write their data structures themselves. Rust programmers tend to use packages. If you've determined that you need a linked list in Rust, you don't start writing one: you "use std::collections::LinkedList;". It's a doubly-linked one, so maybe that's not what you need. In that case, you go on crates.io and see if someone has already written what you need. (225 hits incidentally: https://crates.io/search?q=linked%20list) Only if that fails do you write it yourself. As the ecosystem has filled out, this happens increasingly infrequently. So "a linked list is painful to write" just doesn't apply to the vast, vast majority of Rust programmers who are simply getting work done.

Learning: because linked lists are a CS 101 data structure, they're something people reach for when learning Rust. But different languages are different, and Rust is not C. Writing a good data structure isn't a beginner Rust topic, it's an intermediate to expert one. There's stuff Rust makes easy that C makes hard as well. You can't assume that topics are equally difficult across the languages. Even then, there's Learning Rust With Entirely Too Many Linked Lists.

TL;DR: linked lists being painful to implement is sorta true, but also not really relevant, other than people who try to learn Rust by building them and having a bad time. (Which is unfortunate, but many people don't as well, or have at least heard that they're hard and so have the right expectations going in.)

[tcaputi]

@steveklabnik
Thanks for the reply and I'll try my best to keep an eye out for better uses of "default" data structures while trying to learn Rust. I know that I personally tend to avoid dependency packages in C since I have been burned many times before by things like library version incompatibilities and a complete lack of library distribution standards.

As someone who writes mostly kernel / driver code, it does bother me a little bit that a lot of these default structures will perform extra memory allocations. As a rule of thumb, I try to avoid unnecessary allocations as much as possible in C. This is partially for the performance benefits, but mostly because it makes writing cleanup and error handling code a lot easier to deal with. I hope that using Rust will make the memory management easier and that the performance hit will be mostly unnoticeable. If so, then it will probably be worth the switch, but I will have to see.

[steveklabnik]

What extra allocations are you thinking of? In general, Rust is very concerned about this as well.

[tcaputi]

(I am still very new to Rust so please correct me if I'm wrong). Doesn't a vector live on the heap? And doesn't it need to be resized (potentially) when too many objects are added to it?

[steveklabnik]

Sure. I’d be the same as in C, unless you use alloca, though. If you know the size in advance, you can use an array, which is not heap allocated.

alloca is one of the few things in C that aren’t in Rust, and we may gain a similar feature in the future.

[tcaputi]

I was thinking more along the lines of "if I were to replace my inline linked list with a vector."

[parasyte]

I do a lot of low-level kernel-ish work in Rust, as well. My environment doesn't even have std, or an allocator for that matter. So I've been using a lot of no_std crates like arrayvec to get work done. If you are really deeply concerned about avoiding allocations, I would recommend checking out these kinds of no_std dependencies.

[vitalyd]

@steveklabnik

Sure. I’d be the same as in C, unless you use alloca, though. If you know the size in advance, you can use an array, which is not heap allocated.

alloca is one of the few things in C that aren’t in Rust, and we may gain a similar feature in the future.

This is where intrusive linked lists shine, and why they’re popular in environments that avoid/minimize allocations. So I sympathize with @tcaputi wanting them, and also unfortunately selecting that as the first problem to tackle in Rust .

My view on it is you can always drop down to raw ptrs and travel the familiar grounds that way. It’s no worse than C but you can benefit from Rust in other places and via its other benefits (some already mentioned in this thread). The medium/expert level comes into play when trying to either use safe code only to build the same things or, more likely, minimizing amount of unsafe code and providing a safe API over internally-unsafe code.

The “waaaaait a minute, you’re telling me I can’t build a linked list in this language ... so I have a new shiny car but I can’t drive it out of the parking lot?! ...” reaction is very common The problem is few people realize that this parking lot is full of hazards and Rust simply makes this upfront.

[steveklabnik]

Cool. So, it just really depends on your exact use-case. What vectors do is amortize allocations. So if it needs to reallocate, yes, that will involve a resize, but it doesn't always need to. And when it doesn't, it doesn't allocate at all. This is getting off-topic, so I'll just leave it at that.

If you have a situation where an intrusive linked list makes sense, then you should use one! The point is that you may not have to write one yourself, though. For example, the intrusive-collections crate (mentioned above) has intrusive single and doubly linked lists, as well as a red-black tree.

• Compatible with #[no_std] .
• Intrusive collections don't require any dynamic memory allocation since they simply keep track of existing objects rather than allocating new ones.

I'd be looking at that before bothering to write my own.

And as @vitalyd says:

@vitalyd

My view on it is you can always drop down to raw ptrs and travel the familiar grounds that way. It’s no worse than C but you can benefit from Rust in other places and via its other benefits (some already mentioned in this thread). The medium/expert level comes into play when trying to either use safe code only to build the same things or, more likely, minimizing amount of unsafe code and providing a safe API over internally-unsafe code.

If that package doesn't work for you, you can still do exactly what you'd do in C.

[tcaputi]

Great. Thanks for all the help everyone.

[juleskers]

@tcaputi

I know that I personally tend to avoid dependency packages in C since I have been burned many times

You are not alone in this! It was the prime motivator to include cargo with Rust 1.0.
With that, Rust has a dependency manager that combines all the best features of Java's Maven and Gradle, Ruby's bundler, JavaScript's NPM, python's PyPI combined with dependability on par with any Linux distro. It even avoids most of the mistakes the others made, by learning from their history.
In short, I am of the opinion that Rust has the best dependency management story of any currently available programming language and/or scripting language.

Using external packages ("crates") in Rust is a breeze: add a single line to cargo.toml, and cargo does the downloading, unpacking, linking and dependency locking for reproducible builds.
The community adheres strictly to semver and there is a large focus on painless upgrades in all the "important" packages. additionally, crates.io ensures old versions remain available, so you wont run into problems that way.

Since the rust package ecosystem can be a bit overwhelming to get into, here a few good database inspirations that I think will be relevant for you.

• Anything doing any form of serialisation/deserialisation, be it to disk or to wire formats, should be aware of serde, the default serialisation library in the Rust world. It defines the generic traits/interfaces/contracts for serialisation/deserialisation that make everything interoperable.
• Diesel is the go-to object-relational mapper, with support for PostgreSQL, MySQL and SQLite. It doesn't do its own disk handling or anything, but it can be a good inspiration for how to wire databases to rust structs in an elegant way.
• If you don't feel like writing your own connection pool, r2d2 is your friend!
• TiKV is a distributed key-value store, based on MySQL-compatible TiDB, both written in rust. Probably also interesting inspiration!

Todo: linkify crate names (annoying on mobile) done!