bumpish 0.4.1

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
106
107
108
109

# `BumpVec`

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

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

## Populating

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

```rust
use bumpish::BumpVec;

let _ = BumpVec::<_, 3>::from([1, 2, 3]);
```

Also, as expected, [`BumpVec`] allows to add new elements by pushing them to the
vector.

```rust
use bumpish::BumpVec;

let vec = BumpVec::<_, 0>::new();

assert_eq!(vec.push(1), &1);
assert_eq!(vec.push(2), &2);
assert_eq!(vec.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::vec::BumpVec::push

## Removing elements

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

```rust
use bumpish::BumpVec;

let mut vec = BumpVec::<_, 0>::from([1, 2, 3]);

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

[`pop`]: crate::vec::BumpVec::pop

Also, [`swap_remove`] can remove an element by swapping it with the last one and
then popping it out.

```rust
use bumpish::BumpVec;

let mut v = BumpVec::<_, 0>::from(["foo", "bar", "baz", "qux"]);

assert_eq!(v.swap_remove(1), "bar");
assert_eq!(v, ["foo", "qux", "baz"]);
```

[`swap_remove`]: crate::vec::BumpVec::swap_remove

## 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::BumpVec;

let vec = BumpVec::<_, 0>::from([1, 2, 4]);

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

# Allocation

[`BumpVec`] 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`],
[`BumpVec`] 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 an element never causes moving old elements, and reference
invalidation doesn't happen.

When we pop elements from the vector, if the current chunk becomes empty, then
there is possible one of the following steps:

1. If the chunk is the last chunk in the list, it is not deallocated, but 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
   new cache.

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