concurrent_avl_tree 0.1.0

Lock-free readable AVL tree with epoch-based reclamation and background batch rebalancing.
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

# Concurrent AVL Tree


[![Crates.io](https://img.shields.io/crates/v/concurrent_avl_tree.svg)](https://crates.io/crates/concurrent_avl_tree)
[![Documentation](https://docs.rs/concurrent_avl_tree/badge.svg)](https://docs.rs/concurrent_avl_tree)
[![License](https://img.shields.io/crates/l/concurrent_avl_tree)](LICENSE)
[![Rust Version](https://img.shields.io/badge/rustc-1.91.1+-blue.svg)](https://blog.rust-lang.org)
![CI](https://img.shields.io/badge/CI-ready-brightgreen)

Lock-free readable AVL tree with epoch-based memory reclamation and background batch rebalancing. Designed for high-concurrency, high-read workloads with deterministic traversal latency.

## Table of Contents

- [Features](#features)
- [Installation](#installation)
- [Quick Start](#quick-start)
- [Architecture Overview](#architecture-overview)
  - [Append Phase](#append-phase)
  - [Rebuild Phase](#rebuild-phase)
  - [Swap Phase](#swap-phase)
  - [Reclaim Phase](#reclaim-phase)
- [Benchmarking & Testing](#benchmarking--testing)
- [Contributing & Changelog](#contributing--changelog)
- [License](#license)

## Features

- **Lock-Free Reads** \
Readers traverse without acquiring mutexes or spinlocks.
- **Epoch-Based Reclamation** \
Zero use-after-free guarantees via deferred memory disposal.
- **Batched Rebuilds** \
Writes are collected, sorted, and applied by a background thread that atomically swaps the root pointer.
- **Generational Arena** \
Double-buffered, cache-line aligned allocator eliminates dynamic allocation during rebuilds.
- **Production-Ready Documentation** \
Strict `rustdoc` compliance, exhaustive examples, and CI-enforced lints.

## Installation

Add to `Cargo.toml`:
```toml
[dependencies]
concurrent_avl_tree = "0.1.0"
```
Or via CLI:
```bash
cargo add concurrent_avl_tree
```
*Requires Rust 1.91.1 or newer.*

## Quick Start

```rust
use concurrent_avl_tree::concurrent_avl_tree::ConcurrentAVLTree;

fn main() {
    let tree = ConcurrentAVLTree::new();
    tree.insert_key_value(42, "hello".to_string());
    tree.insert_key_value(10, "world".to_string());

    // Allow background rebuild to complete
    std::thread::sleep(std::time::Duration::from_millis(50));

    let value = tree.get_value(42);
    assert_eq!(value, Some("hello".to_string()));
}
```

## Architecture Overview

```
┌─────────────┐       ┌──────────────┐        ┌───────────────────┐
│   Writers   │──────▶│ Batch Queue  │──────▶│ Background Thread │
└─────────────┘       └──────────────┘        └─────────┬─────────┘
                                                        │
                                                        ▼
┌─────────────┐       ┌──────────────┐        ┌───────────────────┐
│   Readers   │◀──────│ Root Pointer │◀──────│    Arena Swap     │
└─────────────┘       └──────────────┘        └───────────────────┘
```
1. **Append Phase** \
Writers push `BatchEntry` to a mutex-protected collector.
2. **Rebuild Phase** \
Background thread extracts, sorts, and constructs a new AVL tree in the inactive arena buffer.
3. **Swap Phase** \
Root `AtomicPtr` is exchanged. Previous root is queued for epoch-based disposal.
4. **Reclaim Phase** \
EBR tracks active reader epochs. After a two-epoch grace period, queued callbacks free memory safely.

## Benchmarking & Testing

Run unit & doc tests:
```bash
cargo test
cargo test --doc
```
Execute benchmarks (headless safe):
```bash
cargo bench -- --noplot
```
Generate coverage report:
```bash
cargo install cargo-llvm-cov
cargo llvm-cov --all-features --open
```

## Contributing & Changelog

- See [CONTRIBUTING.md](CONTRIBUTING.md) for setup, code style, and PR workflow.
- View release history in [CHANGELOG.md](CHANGELOG.md).

## License

SPDX-License-Identifier: MIT  
© 2026 Dzulkifli Anwar  
See `LICENSE` for full terms.
```