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

/*!
[![GitHub CI Status](https://github.com/LPGhatguy/thunderdome/workflows/CI/badge.svg)](https://github.com/LPGhatguy/thunderdome/actions)
[![thunderdome on crates.io](https://img.shields.io/crates/v/thunderdome.svg)](https://crates.io/crates/thunderdome)
[![thunderdome docs](https://img.shields.io/badge/docs-docs.rs-orange.svg)](https://docs.rs/thunderdome)

Thunderdome is a ~gladitorial~ generational arena inspired by
[generational-arena](https://crates.io/crates/generational-arena),
[slotmap](https://crates.io/crates/slotmap), and
[slab](https://crates.io/crates/slab). It provides constant time insertion,
lookup, and removal via small (8 byte) keys returned from `Arena`.

Thunderdome's key type, `Index`, is still 8 bytes when put inside of an
`Option<T>` thanks to Rust's `NonZero*` types.

## Basic Examples

```rust
# use thunderdome::{Arena, Index};
let mut arena = Arena::new();

let foo = arena.insert("Foo");
let bar = arena.insert("Bar");

assert_eq!(arena[foo], "Foo");
assert_eq!(arena[bar], "Bar");

arena[bar] = "Replaced";
assert_eq!(arena[bar], "Replaced");

let foo_value = arena.remove(foo);
assert_eq!(foo_value, Some("Foo"));

// The slot previously used by foo will be reused for baz
let baz = arena.insert("Baz");
assert_eq!(arena[baz], "Baz");

// foo is no longer a valid key
assert_eq!(arena.get(foo), None);
```

## Comparison With Similar Crates

| Feature                      | Thunderdome | generational-arena | slotmap | slab |
|------------------------------|-------------|--------------------|---------|------|
| Generational Indices¹        | Yes         | Yes                | Yes     | No   |
| `size_of::<Index>()`         | 8           | 16                 | 8       | 8    |
| `size_of::<Option<Index>>()` | 8           | 24                 | 8       | 16   |
| Max Elements                 | 2³²         | 2⁶⁴                | 2³²     | 2⁶⁴  |
| Non-`Copy` Values            | Yes         | Yes                | Sorta²  | Yes  |
| `no_std` Support             | No          | Yes                | No      | No   |
| Serde Support                | No          | Yes                | Yes     | No   |

* Sizes calculated on rustc `1.44.0-x86_64-pc-windows-msvc`
* See [the Thunderdome comparison
  Cargo.toml](https://github.com/LPGhatguy/thunderdome/blob/main/comparison/Cargo.toml)
  for versions of each library tested.

1. Generational indices help solve the [ABA
   Problem](https://en.wikipedia.org/wiki/ABA_problem), which can cause dangling
   keys to mistakenly access newly-inserted data.
2. slotmap's `SlotMap` and `HopSlotMap` require values to be `Copy` on stable
  Rust versions. slotmap's `DenseSlotMap` type supports non-`Copy` types on
  stable, but has different performance trade-offs.

## Minimum Supported Rust Version (MSRV)

Thunderdome supports Rust 1.34.1 and newer. Until Thunderdome reaches 1.0,
changes to the MSRV will require major version bumps. After 1.0, MSRV changes
will only require minor version bumps, but will need significant justification.
*/

#![forbid(missing_docs)]
// This crate is sensitive to integer overflow and wrapping behavior. As such,
// we should usually use methods like `checked_add` and `checked_sub` instead
// of the `Add` or `Sub` operators.
#![deny(clippy::integer_arithmetic)]

mod arena;
mod drain;
mod free_pointer;
mod generation;
mod into_iter;
mod iter;
mod iter_mut;

pub use crate::arena::{Arena, Index};
pub use crate::drain::Drain;
pub use crate::into_iter::IntoIter;
pub use crate::iter::Iter;
pub use crate::iter_mut::IterMut;