deferred-map

A high-performance generational arena (slotmap) with handle-based deferred insertion for Rust.

Features

🚀 O(1) Operations: Constant-time insertion, lookup, and removal
🔒 Memory Safety: Generational indices prevent use-after-free bugs
⏳ Deferred Insertion: Separate handle allocation from value insertion
💾 Memory Efficient: Union-based slot storage optimizes memory usage
🎯 Type Safe: Handles cannot be cloned, ensuring single-use semantics
⚡ Zero-Copy: Direct access to stored values without copying

Why Deferred Insertion?

Traditional slot maps require you to have the value ready when allocating space. DeferredMap separates these concerns:

Allocate Handle - Reserve a slot and get a handle (cheap, no value needed)
Insert Value - Later, use the handle to insert the actual value

This is particularly useful when:

Building complex data structures with circular references
Need to know the key before constructing the value
Want to reserve capacity before expensive computation
Coordinating multi-step initialization processes

Installation

Add this to your Cargo.toml:

[dependencies]

deferred-map = "0.1"

Quick Start

use deferred_map::DeferredMap;

fn main() {
    let mut map = DeferredMap::new();
    
    // Step 1: Allocate a handle (reserves a slot)
    let handle = map.allocate_handle();
    
    // Step 2: Insert value using the handle
    let key = map.insert(handle, "Hello, World!").unwrap();
    
    // Access the value
    assert_eq!(map.get(key), Some(&"Hello, World!"));
    
    // Remove the value
    assert_eq!(map.remove(key), Some("Hello, World!"));
}

Usage Examples

Basic Operations

use deferred_map::DeferredMap;

let mut map = DeferredMap::new();

// Allocate and insert
let handle = map.allocate_handle();
let key = map.insert(handle, 42).unwrap();

// Get immutable reference
assert_eq!(map.get(key), Some(&42));

// Get mutable reference
if let Some(value) = map.get_mut(key) {
    *value = 100;
}
assert_eq!(map.get(key), Some(&100));

// Check existence
assert!(map.contains_key(key));

// Remove value
assert_eq!(map.remove(key), Some(100));
assert_eq!(map.get(key), None);

Building Self-Referential Structures

use deferred_map::DeferredMap;

struct Node {
    value: i32,
    next: Option<u64>, // Key to next node
}

let mut graph = DeferredMap::new();

// Allocate handles first
let handle1 = graph.allocate_handle();
let handle2 = graph.allocate_handle();

// Get the keys before inserting
let key1 = handle1.raw_value();
let key2 = handle2.raw_value();

// Now we can create nodes that reference each other
let node1 = Node { value: 1, next: Some(key2) };
let node2 = Node { value: 2, next: Some(key1) };

// Insert the nodes
graph.insert(handle1, node1).unwrap();
graph.insert(handle2, node2).unwrap();

Iteration

use deferred_map::DeferredMap;

let mut map = DeferredMap::new();

for i in 0..5 {
    let handle = map.allocate_handle();
    map.insert(handle, i * 10).unwrap();
}

// Iterate over all entries
for (key, value) in map.iter() {
    println!("Key: {}, Value: {}", key, value);
}

// Mutable iteration
for (_, value) in map.iter_mut() {
    *value *= 2;
}

Releasing Unused Handles

use deferred_map::DeferredMap;

let mut map = DeferredMap::<String>::new();

// Allocate a handle
let handle = map.allocate_handle();

// Decide not to use it
map.release_handle(handle).unwrap();

// The slot is returned to the free list

API Overview

Core Types

DeferredMap<T>: The main map structure
Handle: A one-time token for deferred insertion (cannot be cloned)
DeferredMapError: Error types for handle operations

Main Methods

Creating a Map

DeferredMap::new() -> Self
DeferredMap::with_capacity(capacity: usize) -> Self

Handle Operations

allocate_handle(&mut self) -> Handle
insert(&mut self, handle: Handle, value: T) -> Result<u64, DeferredMapError>
release_handle(&mut self, handle: Handle) -> Result<(), DeferredMapError>

Value Access

get(&self, key: u64) -> Option<&T>
get_mut(&mut self, key: u64) -> Option<&mut T>
remove(&mut self, key: u64) -> Option<T>
contains_key(&self, key: u64) -> bool

Metadata & Iteration

len(&self) -> usize
is_empty(&self) -> bool
capacity(&self) -> usize
clear(&mut self)
iter(&self) -> impl Iterator<Item = (u64, &T)>
iter_mut(&mut self) -> impl Iterator<Item = (u64, &mut T)>

How It Works

Three-State Slot System

Each slot in the map can be in one of three states:

Vacant (0b00): Empty slot, part of the free list
Reserved (0b01): Handle allocated, awaiting value insertion
Occupied (0b11): Contains a valid value

Generational Indices

Keys are 64-bit values encoding:

Lower 32 bits: Slot index
Upper 32 bits: Version (including state bits)

This prevents the ABA problem: if you remove a value and reuse the slot, the generation increments, invalidating old keys.

Memory Layout

Slots use a union for memory efficiency:

union SlotUnion<T> {
    value: ManuallyDrop<T>,  // When occupied
    next_free: u32,           // When vacant (free list pointer)
}

Performance Characteristics

Insertion: O(1) - Pop from free list
Lookup: O(1) - Direct array indexing with generation check
Removal: O(1) - Push to free list
Memory: Slots are reused, minimal allocation overhead
Cache Friendly: Contiguous memory layout

Error Handling

The library uses a dedicated error type:

pub enum DeferredMapError {
    InvalidHandle,        // Handle refers to invalid slot
    GenerationMismatch,   // Handle generation doesn't match slot
    HandleAlreadyUsed,    // Attempting to reuse a handle
}

Safety Guarantees

No Use-After-Free: Generational indices ensure old keys are rejected
No Double-Use: Handles are consumed on use (move semantics)
No Leaks: Proper Drop implementation for occupied slots
Memory Safe: All unsafe code is carefully encapsulated and documented

Comparison with Other Crates

Feature	deferred-map	slotmap	slab
Deferred Insertion	✅	❌	❌
Generational Indices	✅	✅	❌
O(1) Operations	✅	✅	✅
Handle-based API	✅	❌	❌
Memory Efficient	✅	✅	✅

Minimum Supported Rust Version (MSRV)

Rust 1.75 or later (edition 2024)

License

Licensed under either of:

Apache License, Version 2.0 (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)

at your option.

Contributing

Contributions are welcome! Please feel free to submit a Pull Request.

Author

ShaoG shaog.rs@gmail.com

deferred-map 0.1.1