bumpish 0.4.0

A set of collections using bump allocations
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

# `BumpStk`

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

[`BumpStk`]: crate::stk::BumpStk
[`BumpStk<T>`]: crate::stk::BumpStk
[`Vec`]: https://doc.rust-lang.org/std/vec/struct.Vec.html
[LIFO]: https://en.wikipedia.org/wiki/Stack_(abstract_data_type)

## Populating

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

```rust
use bumpish::BumpStk;

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

Also, as expected, [`BumpStk`] allows to add new elements by pushing them on the
stack.

```rust
use bumpish::BumpStk;

let stack = BumpStk::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](#allocation) part). Also
[`push`] returns a reference to the just pushed element.

[`From`]: https://doc.rust-lang.org/std/convert/trait.From.html
[`push`]: crate::stk::BumpStk::push

## Removing elements

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

```rust
use bumpish::BumpStk;

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

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

[`pop`]: crate::stk::BumpStk::pop

## 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 bumpish::BumpStk;

let stk = BumpStk::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

[`BumpStk<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`],
[`BumpStk`] 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 [`BumpStk`] 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 [`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.

[`rev`]: https://doc.rust-lang.org/std/iter/trait.Iterator.html#method.rev