Crate bump_stack 

bump-stack

Getting Started

Stack<T> is a LIFO collection that uses bump allocation inside. Stack mostly implements a subset of Vec’s API, but it also have some own features and specific behaviors.

Add bump_stack dependency to your crate

To start using bump_stack, add it to your Cargo.toml:

[dependencies]
bump_stack = "*"

Populating

In order to populate a new stack, use different From trait implementations:

use bump_stack::Stack;

let _ = Stack::from([1, 2, 3]);

Also, as expected, Stack allows to add new elements by pushing them on the stack.

use bump_stack::Stack;

let stack = Stack::new();

assert_eq!(stack.push(1), &1);
assert_eq!(stack.push(2), &2);
assert_eq!(stack.push(3), &3);

Note, that, in contrast to Vec, we push new elements using immutable reference (more about that read in the Allocation part). Also push returns a reference to the just pushed element.

Removing elements

Remove an element is possible only by calling pop method.

use bump_stack::Stack;

let mut stack = Stack::from([1, 2, 3]);

assert_eq!(stack.pop(), Some(3));
assert_eq!(stack.pop(), Some(2));
assert_eq!(stack.pop(), Some(1));

Iteration

Pushing new elements by immutable reference allows to do that during iteration. To avoid infinite loop, iteration runs over elements that have already existed at the moment of creating the iterator.

use bump_stack::Stack;

let stk = Stack::from([1, 2, 4]);

for elem in stk.iter() {
    stk.push(*elem);
}
assert_eq!(stk.len(), 6);
assert_eq!(stk, [1, 2, 4, 4, 2, 1]);

Also, note that iteration runs over elements in reverse order of their insertion, corresponding to LIFO paradigm.

Allocation

Stack<T> uses a linked list of memory chunks that contain elements of the type T. If the current memory chunk is full, the stack allocates another one from the global allocator (usually two times bigger than the previous chunk), and keeps pushing new elements to this new chunk. So, in contrast to Vec, Stack doesn’t move old elements from the smaller chunk into the bigger one. Exactly this property allows to push new elements by immutable reference, because adding element never causes moving old elements, and reference invalidation doesn’t happen.

As a process’s stack memory, our Stack grows downwards as well, starting from the top of the memory chunk. This is one of the reasons why iterators run over elements in reverse order. To get the usual vector-like behavior, you can use Iterator::rev() method.

When we pop elements from the stack, if the current chunk becomes empty, then there are possible two steps:

1. If the chunk is the last chunk in the list, it is not deallocated, but it’s kept for future use as a cache.

2. If the chunk is not the last one, and we already have another chunk as a cache, the smallest from both is deallocated, and the biggest is kept as a cache.

Some notes

This crate was heavily inspired by bumpalo crate, and originally used it code as a start point. So, although most of the code is different now, it still can contain some bumpalo’s code snippets.

I am not an expert in licensing, but if my choice of license (MPL 2.0 is more copyleftish than bumpalo’s MIT or Apache 2.0) in some way breaks the spirit of the bumpalo crate, please let me know.

Structs

Stack