lock-free 0.1.2

# Lock-Free Data Structures - API Reference

This library provides high-performance, thread-safe, lock-free data structures with zero external dependencies.

## Table of Contents
- [Primary API](#primary-api)
  - [Stack](#stack)
  - [Queue](#queue)
  - [List](#list)
  - [HashMap](#hashmap)
- [Variant Implementations](#variant-implementations)
  - [UnboundedQueue](#unboundedqueue)
  - [SimpleList](#simplelist)
  - [HazardStack](#hazardstack)
  - [FAAQueue](#faaqueue)
  - [LCRQ](#lcrq)
- [Performance Guide](#performance-guide)

---

## Primary API

### Stack

**Description**: A lock-free LIFO (Last In, First Out) stack using Treiber's algorithm.

**Performance**: 24M+ operations per second

**Use Cases**: 
- Task scheduling
- Undo/redo operations
- Expression evaluation
- Backtracking algorithms

**API**:
```rust
impl<T> Stack<T> {
    pub fn new() -> Self
    pub fn push(&self, data: T)
    pub fn pop(&self) -> Option<T>
    pub fn is_empty(&self) -> bool
}
```

**Example**:
```rust
use lock_free::Stack;
use std::sync::Arc;
use std::thread;

// Single-threaded usage
let stack = Stack::new();
stack.push("first");
stack.push("second");
stack.push("third");

assert_eq!(stack.pop(), Some("third"));  // LIFO order
assert_eq!(stack.pop(), Some("second"));
assert_eq!(stack.pop(), Some("first"));
assert_eq!(stack.pop(), None);
assert!(stack.is_empty());

// Multi-threaded usage
let shared_stack = Arc::new(Stack::new());
let mut handles = vec![];

// Spawn producers
for i in 0..4 {
    let stack = Arc::clone(&shared_stack);
    handles.push(thread::spawn(move || {
        for j in 0..1000 {
            stack.push(i * 1000 + j);
        }
    }));
}

// Spawn consumer
let stack = Arc::clone(&shared_stack);
handles.push(thread::spawn(move || {
    let mut count = 0;
    while count < 4000 {
        if stack.pop().is_some() {
            count += 1;
        }
    }
    println!("Consumed {} items", count);
}));

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

---

### Queue

**Description**: A high-performance bounded lock-free queue using sequence numbers for coordination.

**Performance**: 25M+ operations per second

**Use Cases**:
- Task/job queues
- Message passing between threads
- Producer-consumer patterns
- Event processing

**API**:
```rust
impl<T> Queue<T> {
    pub fn new(capacity: usize) -> Self
    pub fn enqueue(&self, item: T) -> bool
    pub fn dequeue(&self) -> Option<T>
    pub fn is_empty(&self) -> bool
    pub fn is_full(&self) -> bool
}
```

**Example**:
```rust
use lock_free::Queue;
use std::sync::Arc;
use std::thread;
use std::time::Duration;

// Single-threaded usage
let queue = Queue::new(1024);  // Must specify capacity
queue.enqueue("first");
queue.enqueue("second");
queue.enqueue("third");

assert_eq!(queue.dequeue(), Some("first"));   // FIFO order
assert_eq!(queue.dequeue(), Some("second"));
assert_eq!(queue.dequeue(), Some("third"));
assert_eq!(queue.dequeue(), None);
assert!(queue.is_empty());

// Multi-threaded producer-consumer
let queue = Arc::new(Queue::new(10_000));

// Spawn producers
let mut producers = vec![];
for i in 0..2 {
    let q = Arc::clone(&queue);
    producers.push(thread::spawn(move || {
        for j in 0..5000 {
            while !q.enqueue(i * 5000 + j) {
                thread::yield_now(); // Queue full, yield
            }
        }
    }));
}

// Spawn consumers
let mut consumers = vec![];
for _ in 0..2 {
    let q = Arc::clone(&queue);
    consumers.push(thread::spawn(move || {
        let mut count = 0;
        while count < 5000 {
            if q.dequeue().is_some() {
                count += 1;
            } else {
                thread::sleep(Duration::from_micros(1));
            }
        }
        count
    }));
}

// Wait for completion
for p in producers {
    p.join().unwrap();
}
let total: usize = consumers.into_iter()
    .map(|c| c.join().unwrap())
    .sum();
println!("Total consumed: {}", total);
```

---

### List

**Description**: A lock-free ordered key-value store implemented as a skip list with O(log n) operations.

**Performance**: 3M+ operations per second

**Use Cases**:
- Ordered collections
- Leaderboards
- Range queries
- Priority systems
- Caches with ordering

**API**:
```rust
impl<K: Ord + Clone, V> List<K, V> {
    pub fn new() -> Self
    pub fn insert(&self, key: K, value: V) -> bool
    pub fn contains(&self, key: &K) -> bool
    pub fn get(&self, key: &K) -> Option<V> where V: Clone
    pub fn remove(&self, key: &K) -> bool
}
```

**Example**:
```rust
use lock_free::List;
use std::sync::Arc;
use std::thread;

// Basic usage - ordered key-value store
let list = List::new();

// Insert key-value pairs
list.insert(5, "five");
list.insert(2, "two");
list.insert(8, "eight");
list.insert(3, "three");

// Check existence
assert!(list.contains(&5));
assert!(!list.contains(&10));

// Get values
assert_eq!(list.get(&2), Some("two"));
assert_eq!(list.get(&10), None);

// Remove entries
assert!(list.remove(&3));
assert!(!list.contains(&3));

// Concurrent usage - leaderboard example
#[derive(Clone, Debug)]
struct Player {
    name: String,
    score: u32,
}

let leaderboard = Arc::new(List::new());

// Multiple threads updating scores
let mut handles = vec![];
for i in 0..4 {
    let board = Arc::clone(&leaderboard);
    handles.push(thread::spawn(move || {
        for j in 0..100 {
            let player = Player {
                name: format!("Player-{}-{}", i, j),
                score: (i * 100 + j) as u32,
            };
            board.insert(player.score, player);
        }
    }));
}

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

// Check top scores
if let Some(player) = leaderboard.get(&399) {
    println!("Top player: {:?}", player);
}
```

---

### HashMap

**Description**: A high-performance lock-free HashMap using open addressing with linear probing.

**Performance**: 10-30M+ operations per second (scales with thread count)

**Use Cases**:
- Concurrent caching
- Shared configuration stores
- Real-time data lookups
- Thread-safe counters/metrics
- Session storage

**API**:
```rust
impl<K: Hash + Eq + Clone, V: Clone> HashMap<K, V> {
    pub fn new() -> Self
    pub fn with_capacity(capacity: usize) -> Self
    pub fn insert(&self, key: K, value: V) -> Option<V>
    pub fn get(&self, key: &K) -> Option<V>
    pub fn remove(&self, key: &K) -> Option<V>
    pub fn contains_key(&self, key: &K) -> bool
    pub fn len(&self) -> usize
    pub fn is_empty(&self) -> bool
}
```

**Example**:
```rust
use lock_free::HashMap;
use std::sync::Arc;
use std::thread;

// Single-threaded usage
let map = HashMap::new();
map.insert("apple", 5);
map.insert("banana", 3);
map.insert("orange", 7);

assert_eq!(map.get(&"apple"), Some(5));
assert_eq!(map.get(&"grape"), None);
assert!(map.contains_key(&"banana"));

map.remove(&"banana");
assert!(!map.contains_key(&"banana"));

// Multi-threaded usage - concurrent cache
let cache = Arc::new(HashMap::with_capacity(10_000));

// Spawn writers
let mut handles = vec![];
for i in 0..4 {
    let cache = Arc::clone(&cache);
    handles.push(thread::spawn(move || {
        for j in 0..1000 {
            let key = format!("user_{}", i * 1000 + j);
            let value = format!("data_{}", j);
            cache.insert(key, value);
        }
    }));
}

// Spawn readers
for i in 0..4 {
    let cache = Arc::clone(&cache);
    handles.push(thread::spawn(move || {
        let mut found = 0;
        for j in 0..1000 {
            let key = format!("user_{}", i * 1000 + j);
            if cache.get(&key).is_some() {
                found += 1;
            }
        }
        println!("Reader {} found {} entries", i, found);
    }));
}

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

println!("Cache contains {} entries", cache.len());
```

---

## Variant Implementations

### UnboundedQueue

**Description**: Michael & Scott lock-free queue with unlimited capacity.

**When to use**: When you can't determine capacity in advance or need truly unbounded queuing.

**Example**:
```rust
use lock_free::variants::UnboundedQueue;

let queue = UnboundedQueue::new();
// No capacity limit
for i in 0..1_000_000 {
    queue.enqueue(i);  // Always succeeds
}
```

---

### SimpleList

**Description**: A simple O(n) linked list for small collections.

**When to use**: For collections with fewer than 100 items where simplicity matters more than asymptotic performance.

**Example**:
```rust
use lock_free::variants::SimpleList;

let list = SimpleList::new();
list.insert(42);    // Note: only stores values, not key-value pairs
list.insert(17);
list.insert(99);

assert!(list.contains(&42));
assert!(!list.contains(&100));
```

---

### HazardStack

**Description**: Stack with exponential backoff to reduce contention under high load.

**When to use**: When you have many threads competing and want to reduce contention.

**Example**:
```rust
use lock_free::variants::HazardStack;

let stack = HazardStack::new();
// Same API as regular Stack, but with backoff
stack.push("reduces contention");
stack.pop();
```

---

### FAAQueue

**Description**: Fetch-and-Add queue using circular buffer with turn-based coordination.

**When to use**: Alternative queue implementation that may perform better on certain workloads.

**Example**:
```rust
use lock_free::variants::FAAQueue;

let queue = FAAQueue::new(1024);
queue.enqueue(42);      // Returns bool
queue.dequeue();        // Returns Option<T>
queue.try_enqueue(43);  // Returns Result<(), T>
queue.try_dequeue();    // Returns Option<T>
```

---

### LCRQ

**Description**: Loosely-Coupled Ring Queue for high scalability.

**When to use**: When you need maximum scalability with many threads.

**Example**:
```rust
use lock_free::variants::LCRQ;

let queue = LCRQ::new();
queue.enqueue("scales well");
queue.dequeue();
```

---

## Performance Guide

### Choosing the Right Structure

| Use Case | Recommended | Operations/sec |
|----------|-------------|---------------|
| LIFO operations | Stack | 24M+ |
| FIFO with known capacity | Queue | 25M+ |
| FIFO with unknown capacity | UnboundedQueue | 2-3M |
| Ordered key-value store | List | 3M+ |
| Fast key-value lookups | HashMap | 10-30M+ |
| Small ordered set (<100) | SimpleList | 1.5M+ |
| High contention stack | HazardStack | 20M+ |

### Best Practices

1. **Pre-size appropriately**: For `Queue`, choose a capacity that avoids frequent full conditions
2. **Use Arc for sharing**: Wrap in `Arc` when sharing between threads
3. **Batch operations**: When possible, batch multiple operations to reduce contention
4. **Consider variants**: Use specialized variants when they match your use case

### Thread Scaling

All structures scale well up to 8-16 threads. Performance characteristics:
- **Stack**: Excellent scaling, minimal contention
- **Queue**: Good scaling for balanced producer-consumer
- **List**: Good scaling for read-heavy workloads

### Example: High-Performance Task Queue

```rust
use lock_free::Queue;
use std::sync::Arc;
use std::thread;

struct Task {
    id: usize,
    work: fn(),
}

fn create_worker_pool(num_workers: usize) -> Arc<Queue<Task>> {
    let task_queue = Arc::new(Queue::new(100_000));
    
    for _ in 0..num_workers {
        let queue = Arc::clone(&task_queue);
        thread::spawn(move || {
            loop {
                match queue.dequeue() {
                    Some(task) => (task.work)(),
                    None => thread::yield_now(),
                }
            }
        });
    }
    
    task_queue
}

// Usage
let pool = create_worker_pool(4);
for i in 0..1000 {
    pool.enqueue(Task {
        id: i,
        work: || println!("Processing task"),
    });
}
```