rust-lockless-slotmap 0.1.3

A (mostly) lockless slotmap implementation in Rust
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

# rust-lockless-slotmap

## Lockless Slotmap

Lockless Slotmap is a lockless implementation of a slotmap. A slotmap is a data structure that
allows for stable references to elements while providing fast insertion (in O(1) time) and
removal (in O(1) time).

This implementation is (mostly) lockless, meaning that it can be used in a high performance
environment where locks are not desired. The only place where locks are used is when the slotmap
becomes saturated and a new block needs to be allocated. Because of the ever-growing exponential
size of the blocks, this should be a rare occurrence.

## Limitations

Each slot in the slotmap can only be reused so many times. 16-bit generation numbers are kept as
guard against ABA problems, this means that each slot can only be reused 65536 times (after which
the slot is considered "dead" and will not be reused which can lead to slowly increasing memory
usage). Therefore for very long running applications with high insertion and removal rates, this
implementation may not be suitable.

## Example

```rust
use rust_lockless_slotmap::LocklessSlotmap;
use std::sync::Arc;
use parking_lot::RawRwLock;

let slotmap: Arc<LocklessSlotmap<usize, RawRwLock>> = Arc::new(LocklessSlotmap::new());
let ticket = slotmap.insert(42);

let slotmap_clone = Arc::clone(&slotmap);
let handle = std::thread::spawn(move || {
   let entry = slotmap_clone.get(ticket).unwrap();
   assert_eq!(*entry, 42);
   drop(entry); // Deadlock if this is not dropped

   slotmap_clone.insert(45);
   slotmap_clone.erase(ticket);
});

handle.join().unwrap();

assert_eq!(slotmap.len(), 1);
assert!(slotmap.get(ticket).is_none());
```


License: MIT