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
/*!
Thunderation is a generational arena forked from
[Thunderdome](https://crates.io/crates/thunderdome). It adds a few
improvements like unique key type identifiers, improved methods, and the removal
of all unsafe code.
It provides constant time insertion, lookup, and removal via small (8 byte) keys
returned from [`Arena`] or via slot indices. Thunderation's key type is still 8
bytes when put inside of an `Option<Key>` thanks to Rust's `NonZero*` types. One
limitation of this key type is that arenas can only hold up to [`u32::MAX`]
elements.
This data structure is backed by a [`Vec`] and is implemented using zero unsafe
code. No AI was used in any process of making this crate.
# Why use this over [slotmap](https://crates.io/crates/slotmap)?
The main reason is when you need to get and set values by their slot index
in addition to generational keys. If you do not need this, consider using
slotmap instead.
# Basic Examples
```rust
# use thunderation::{Arena, Key};
// Define a unique key type identifier. This prevents keys from
// being used in Arena's they don't belong to.
#[derive(Default, Debug, Clone, Copy, PartialEq, Eq)]
pub struct MyKey;
// Create an arena with the given key type and the storage type.
let mut arena = Arena::<MyKey, &'static str>::new();
let foo = arena.insert("Foo");
let bar = arena.insert("Bar");
assert_eq!(arena[foo], "Foo");
assert_eq!(arena[bar], "Bar");
// Methods to get/insert items by slot index are also available.
let (key, value) = arena.get_by_slot(foo.slot()).unwrap();
assert_eq!(key, foo);
assert_eq!(value, &"Foo");
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 | Thunderation | Thunderdome | generational-arena | typed-generational-arena | slotmap | slab |
|------------------------------|--------------|-------------|--------------------|--------------------------|---------|------|
| Generational¹ | Yes | Yes | Yes | Yes | Yes | No |
| `size_of::<Key>()` | 8 | 8 | 16 | varies | 8 | 8 |
| `size_of::<Option<Key>>()` | 8 | 8 | 24 | varies | 8 | 16 |
| Max elements | 2³² | 2³² | 2⁶⁴ | 2⁶⁴ | 2³² | 2⁶⁴ |
| Non-`Copy` values | Yes | Yes | Yes | Yes | Yes | Yes |
| `no_std` support | Yes | Yes | Yes | Yes | Yes | Yes |
| Uniquely typed keys | Yes | No | No | Yes | Yes | No |
| Get/set values by slot index | Yes | Yes | No | No | No | Yes |
| Zero unsafe used | Yes | No | Yes | Yes | No | No |
| Serde support | No | No | Yes | Yes | Yes | No |
> 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.
# Crate Features
* `std` (default): Use the standard library. Disable to make this crate `no-std` compatible.
*/
// 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.
// TODO: Deny clippy::std_instead_of_core, clippy::std_instead_of_alloc and
// clippy::alloc_instead_of_core when released.
extern crate alloc;
pub use crateArena;
pub use crateKey;