[dschatz]

I have one here: https://github.com/dschatzberg/intrusive

It can be used in a freestanding (nostd) environment such as a kernel. It uses unsafe code but provides a safe interface. The primary technique is to embed the type that is iterated over in a larger struct which contains the links. This way I can give out references to the inner type without fear of invalidating the iterator.

[detrino]

How is it possible to write a no-allocation intrusive linked list without move constructors ? When you move one of the nodes (or sentinel if you use one) it would invalidate the links in other nodes.

[dschatz]

The list takes an OwningPointer to the object to be inserted. One of the requirements of this trait (which is unsafe to implement) is "the object cannot be moved while in the `LinkedList`." So Box would work, or a mutable reference would as well (the library implements the trait for these types already). The list itself doesn't do the allocation though.

[cesarb]

> The primary technique is to embed the type that is iterated over in a larger struct which contains the links. This way I can give out references to the inner type without fear of invalidating the iterator.

I see. I was too fixated in embedding a small struct with the links within the larger struct (in the style of the Linux kernel "struct list_head"), and didn't think of doing the opposite.

It probably makes being in several intrusive structs at the same time much more complicated, but I think it's possible to do without breaking anything.

[bluetech]

Off topic, but: I thought in rust they like to statically link everything. So how does that go with the LGPL license you chose?

[dschatz]

I think that the requirement is that anyone who releases a program that was linked with my library must also release it in a form that allows it to be relinked without the library. I'm not sure how that applies to Rust's linkage model.