Crate ptab 

A lock-free, cache-line-aware concurrent table.

ptab provides PTab, a fixed-capacity table for storing entries and accessing them by opaque indices. It is optimized for read-heavy workloads where entries are looked up frequently from multiple threads simultaneously.

Overview

The table assigns each inserted value a Detached index that uniquely identifies that entry. This index can be used to look up, access, or remove the entry. Indices include a generational component to mitigate the ABA problem in concurrent algorithms.

Usage

use ptab::PTab;

// Create a table with default capacity
let table: PTab<String> = PTab::new();

// Insert an entry and get its index
let index = table.insert("hello".to_string()).unwrap();

// Access the entry by index
let greeting = table.with(index, |s| s.to_uppercase());
assert_eq!(greeting, Some("HELLO".to_string()));

// Remove the entry
assert!(table.remove(index));

// The entry is gone
assert!(!table.exists(index));

Configuration

Table capacity is configured at compile time through the Params trait. The default configuration (DefaultParams) provides Capacity::DEF slots:

use ptab::{PTab, DefaultParams};

// These are equivalent:
let table1: PTab<u64> = PTab::new();
let table2: PTab<u64, DefaultParams> = PTab::new();

For custom capacities, use ConstParams:

use ptab::{PTab, ConstParams};

let table: PTab<u64, ConstParams<512>> = PTab::new();
assert_eq!(table.capacity(), 512);

Capacity is always rounded up to the nearest power of two and clamped to the range Capacity::MIN..=Capacity::MAX.

Concurrency

All operations on PTab are thread-safe and lock-free. Multiple threads can concurrently insert, remove, and access entries without blocking.

use ptab::{PTab, ConstParams};
use std::sync::Arc;
use std::thread;

let table: Arc<PTab<u64, ConstParams<1024>>> = Arc::new(PTab::new());

let handles: Vec<_> = (0..4)
  .map(|thread_id| {
    let table = Arc::clone(&table);
    thread::spawn(move || {
      for i in 0..100 {
        if let Some(idx) = table.insert(thread_id * 1000 + i) {
          table.remove(idx);
        }
      }
    })
  })
  .collect();

for handle in handles {
  handle.join().unwrap();
}

Memory Reclamation

Removed entries are reclaimed using a pluggable memory management strategy. By default, epoch-based reclamation via sdd ensures safe concurrent access. In no-std environments, a leak-based fallback is available.

See memory for reclamation trait details and custom implementations.

Memory Layout

The table uses a cache-line-aware memory layout to minimize false sharing between threads. Consecutive allocations are distributed across different cache lines, reducing contention when multiple threads operate on recently-allocated entries. See CACHE_LINE_SLOTS for the distribution stride.

Capacity Limits

Capacity is bounded by Capacity::MIN and Capacity::MAX. The default is Capacity::DEF. When full, PTab::insert() returns None.

Modules

config

Configuration parameters which can be used to override the default table settings.

implementation

Implementation Notes

memory

Memory reclamation traits and built-in strategies.

Structs

Capacity

A type storing a usize which is a power of two in the range MIN..=MAX, and thus represents a possible table capacity.

ConstParams

A Params implementation with compile-time configurable capacity.

DefaultParams

The default table configuration with Capacity::DEF slots.

Detached

An opaque index identifying a table entry.

PTab

A lock-free concurrent table.

WeakKeys

Iterator over indices in a PTab with weak snapshot semantics.

Traits

Params

Compile-time configuration for a PTab.