#map #overlay #update #two-layer

overlay-map

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

5 releases

Uses new Rust 2024

new 0.1.4 Apr 5, 2025
0.1.3 Apr 5, 2025
0.1.2 Apr 5, 2025
0.1.1 Apr 4, 2025
0.1.0 Apr 4, 2025

#418 in Data structures

Download history

115 downloads per month

MIT license

42KB
524 lines

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.

⚠️ Work in progress: The library is still evolving.

📦 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

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

📚 Documentation

🔒 License

MIT

✨ Contributing

Contributions, bug reports, and feature ideas welcome.

Dependencies

~1MB
~11K SLoC