Chainlink

Another linked list?

Chainlink provides both singly and doubly linked lists backed by a generational arena allocator. By using an arena allocator, we can avoid unsafe code entirely (chainlink is #[deny(unsafe)]), and we can improve on cache locality by eliminating pointer chasing. Everything is stored contiguously.

That's why it's called "chainlink". In a real chainlink fence, links are contiguous. Also the name was available on crates.io.

Limitations

Size

Because we use generational-arena indices instead of pointers, our internal links in the linked list will use more memory, all else being equal. An index for a generational-arena will necessarily have to store both the pointer-equivalent―here just a usize, which is equal in size to a pointer―and a generation number.

We've chosen a different tradeoff for our default linked lists. The indices are the same size as pointers, but can hold fewer elements. This means that our default lists can hold 4 billion (really 2^32 - 1) elements, each of which can be updated a maximum for 4 billion times.

For most applications, this is probably a reasonable limit. However, if you feel you're in danger of bumping up against either of those limits, we provide alternate implementations with increased size for the vector offset and for the generation.

Appending

Because std's linked lists use a shared, general-purpose allocator, nodes from different lists can be connected to each other without reallocating and copying. This lets the user create two separate lists of arbitrary size and append them in constant memory and contant time.

Chainlink is currently unable to perform the same operation efficiently. If we were to move all the nodes from list B into list A, it would take us time proportional to the number of elements in list B.