bump-stack 0.1.0

A stack implementation using bump allocation
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113

# `bump-stack`

**`Stack<T>` is a [LIFO] collection that uses bump allocation inside.**

[LIFO]: https://en.wikipedia.org/wiki/Stack_(abstract_data_type)

## Getting Started

[`Stack`] mostly implements a subset of [`Vec`]'s API, but it also have some own
features.

[`Stack`]: crate::Stack
[`Vec`]: https://doc.rust-lang.org/std/vec/struct.Vec.html

### Add `bump_stack` dependency to your crate

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

```toml
[dependencies]
bump_stack = "*"
```

### Populating

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

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

```rust
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 (why? read in the [Allocation](#allocation) part). Also `push` returns
a reference to the just pushed element.

### Removing elements

Remove an element is possible only by calling [`pop`] method.

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

```rust
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, 1, 2, 4]);
```

## 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 small chunk into the bigger one. Exactly this
property allows to push new elements by immutable reference, because adding
element never causes moving old elements.

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

[`bumpalo`]: https://crates.io/crates/bumpalo