~vlmutolo/chainlink

An arena-backed doubly linked list in 100% safe Rust.
change incorrect reference into iter_fast in docs
add append limitation to crate docs
point to docs in README

refs

master
browse  log 

clone

read-only
https://git.sr.ht/~vlmutolo/chainlink
read/write
git@git.sr.ht:~vlmutolo/chainlink

You can also use your local clone with git send-email.

For quick usage examples and more info, please see the official docs.

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