3 ms·

How can you? (genuine question) I found this project: https://git.sr.ht/~vlmutolo/chainlink https://git.sr.ht/~vlmutolo/chainlink But they use generational in

How can you? (genuine question) I found this project: https://git.sr.ht/~vlmutolo/chainlink https://git.sr.ht/~vlmutolo/chainlink But they use generational indices into a vector. You can't append two doubly-linked lists because they have their own vectors. I was thinking of two separate doubly-linked lists using real pointers (not indices into a vector), but since they were allocated by the same arena allocator, they can be appended. Is that already possible (in safe Rust)? If so, I guess I should have done more research, sorry :) Edit: Oh, do you mean the normal one from the standard library? https://doc.rust-lang.org/std/collections/struct.LinkedList.html https://doc.rust-lang.org/std/collections/struct.LinkedList.... My bad. I was thinking of something similar, just not implemented with raw pointers underneath, but it already takes an allocator argument in the type, so there would be no benefit to this. Kind of embarrassed now.

steveklabnik 2y ago
I wasn't thinking "use std::collections::LinkedList with an allocator parameter," just that like: 1. The reason linked lists in Rust are difficult is due to lifetimes. 2. Arenas in Rust are parameterized by a lifetime, and that does the stuff you want here, that is, make sure that they can't go away until the arena does. 3. This means this should Just Work. I haven't written the code because I don't think it would be that useful. I already wrote one terrible linked list based on generational indices that's not useful for anything, so doing it again doesn't sound that fun, haha. Looking at chainlink, it's roughly the same design, except with a Vec instead of the arena, which isn't much of a difference. > Kind of embarrassed now. No need to be embarrassed by asking good-faith questions.
oconnor663 2y ago
You can put nodes in a Slab or a SlotMap, use keys/indexes for your next pointers, and create multiple interacting (possibly overlapping) lists that way. You have to be careful not to combine nodes from different collections, but that's also sort of true with memory allocators.

steveklabnik 2y ago

I wasn't thinking "use std::collections::LinkedList with an allocator parameter," just that like: 1. The reason linked lists in Rust are difficult is due to lifetimes. 2. Arenas in Rust are parameterized by a lifetime, and that does the stuff you want here, that is, make sure that they can't go away until the arena does. 3. This means this should Just Work. I haven't written the code because I don't think it would be that useful. I already wrote one terrible linked list based on generational indices that's not useful for anything, so doing it again doesn't sound that fun, haha. Looking at chainlink, it's roughly the same design, except with a Vec instead of the arena, which isn't much of a difference. > Kind of embarrassed now. No need to be embarrassed by asking good-faith questions.

oconnor663 2y ago

You can put nodes in a Slab or a SlotMap, use keys/indexes for your next pointers, and create multiple interacting (possibly overlapping) lists that way. You have to be careful not to combine nodes from different collections, but that's also sort of true with memory allocators.