4 ms·

I have one here: https://github.com/dschatzberg/intrusive https://github.com/dschatzberg/intrusive It can be used in a freestanding (nostd) environment such as

by dschatz 11y ago

I have one here: https://github.com/dschatzberg/intrusive 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 11y ago
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 11y ago
  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.
bluetech 11y ago
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 11y ago
  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.
cesarb 11y ago
> 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.

by dschatz 11y ago

detrino 11y ago

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 11y ago
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.

bluetech 11y ago

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 11y ago
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.

cesarb 11y ago

> 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.