overlay-map 0.2.0

A two-layered map data structure for Rust that tracks current and previous values for each key — with zero-clone, in-place state transitions.
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
110

# overlay-map

**overlay-map** is a two-layered map data structure for Rust that tracks **current** and **previous** values for each key — with zero-clone, in-place state transitions.

It provides `OverlayMap<K, V>`, a map where each value is an `Overlay<V>`: a compact two-slot container that allows pushing, swapping, and pulling values without cloning or heap allocation.

## 📦 Features

- ✅ **In-place, zero-cost value updates**
- ✅ Foreground and background storage per key
- ✅ On `push`, the current foreground is moved to background
- ✅ No heap allocation or cloning for updates
- ✅ Conditional updates (`push_if`)
- ✅ Automatic removal when entries become empty
- ✅ `Overlay<T>` usable independently from the map

## 🧠 Core types

### `OverlayMap<K, V>`

A map-like wrapper for managing per-key two-layered state.

### `Overlay<T>`

A standalone container that tracks two versions of a value:
- `fg` → the current value
- `bg` → the previous value (optional)

Uses zero-copy, branchless slot flipping via raw memory and bitflags.

## 🚀 Example: Revolving Door of Values

```rust
use overlay_map::Overlay;

fn main() {
    let mut door = Overlay::new_fg("Alice");
    println!("Present: {:?}, {:?}", door.fg(), door.bg());

    for name in ["Bob", "Carol", "Dave", "Eve"] {
        if let Some(evicted) = door.swap(name) {
            println!("{evicted} left");
        }

        println!("Present: {:?}, {:?}", door.bg(), door.fg());
    }

    while let Some(pulled) = door.pull() {
        println!("{pulled} left");
    }

    println!("Present: {:?}, {:?}", door.bg(), door.fg());
}
```

## 🔬 Internal Design

- `Overlay<T>` uses `[MaybeUninit<T>; 2]` with a compact bitflag for presence and slot state.
- No heap allocation, no `Option<T>`, no clone required.
- Operations like `push`, `pull`, `swap` are in-place and branch-minimal.
- Designed for **high-throughput**, **zero-cost** data flow and state management.

## 🧠 Why use this?

`overlay-map` is ideal for:

- Managing *current vs previous* state without full history
- Speculative updates, rollback systems, or caching layers
- Config overlays, merging, and snapshotting
- Avoiding unnecessary cloning, allocation, and indirection in hot code paths

## 🧪 Performance: `Overlay<T>` vs `Option<(T, Option<T>)>`

These benchmarks measure the performance of the `push` operation in both the
`Overlay<T>` and a conventional tuple-based implementation. Recorded on a
MacBook Air M4.

### 📊 Overlay Implementation

![Overlay PDF](./assets/overlay_pdf.svg)
![Overlay Regression](./assets/overlay_regression.svg)

### 📊 Tuple Implementation

![Tuple PDF](./assets/tuple_pdf.svg)
![Tuple Regression](./assets/tuple_regression.svg)

### 📊 Interpretation

- **Overlay**:
  - Operates near L1 cache speeds (sub-100ps per op).
  - Compact, branchless bitfield logic leads to extremely low overhead.
- **Tuple**:
  - Slower and more predictable due to enum tagging and control-flow overhead.
  - Useful baseline, but significantly outperformed by `Overlay`.

> These graphs were generated using [Criterion.rs](https://bheisler.github.io/criterion.rs/book/) and represent measured runtime distribution and scaling with iteration count.

## 📚 Documentation

- [Docs.rs](https://docs.rs/overlay-map)
- [Crates.io](https://crates.io/crates/overlay-map)

## 🔒 License

MIT

## ✨ Contributing

Contributions, bug reports, and feature ideas welcome.