boxcar 0.2.2

A concurrent, append-only vector
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

# Design

A concurrent vector is represented as an array of lazily allocated buckets, of sizes `1, 2, 4 .. 2^63`:

```text
___________________________________
|  |    |        |                |
|  |    |        |                |
-----------------------------------
```

A buckets holds a number entries, as well as a lock to guard againt concurrent initialization:

```text
_____________
|  |  |  |  |
|  |  |  |  |
-------------
| UNLOCKED  |
-------------
```

An entry holds a slot for a value along with a flag indicating whether the slot is active:

```text
_____________________
| ACTIVE | INACTIVE |
|   42   |   NULL   |
---------------------
```

Writes acquire a unique index into the vector. The bucket holding the given entry is calculated
using the leading zeros instruction. If the bucket is already initialized, the value is written
to the slot, and the slot is marked as active. If the bucket has not been initialized, the thread
acquires the per-bucket initialization lock, allocates the bucket, and then writes the value. Note
that in the general case, writes are lock-free.

Reads use the same calculation to find the entry mapped to the given index, reading the value from
the slot if the flag indicates the slot is active. All reads are guaranteed to be lock-free.