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
//! A high-performance lock-free concurrent hash map built on top of the Kovan memory reclamation system.
//!
//! This crate provides two lock-free hash map implementations:
//!
//! - [`HashMap`]: A chaining-based hash map with fixed capacity and minimal collisions
//! - [`HopscotchMap`]: A growing/shrinking hopscotch hash map with dynamic resizing
//!
//! Both implementations are thread-safe and allow concurrent reads, writes,
//! and deletions without any locks or blocking. They achieve this through:
//!
//! - **Lock-free algorithms**: All operations use compare-and-swap (CAS) based techniques
//! - **Kovan memory reclamation**: Safe memory management in concurrent environments without garbage collection
//! - **FoldHash**: Fast, high-quality hashing for minimal collision rates
//! - **Large bucket arrays**: Pre-allocated oversized tables (524,288 buckets) that fit in L3 cache
//!
//! # Features
//!
//! - `std` (default): Enables standard library support for additional functionality
//! - `no_std` compatible when the `std` feature is disabled
//!
//! # Performance Characteristics
//!
//! The hash map is optimized for high-throughput concurrent workloads:
//!
//! - **Memory footprint**: ~4MB for the bucket array (fits in modern L3 caches)
//! - **Load factor**: ~0.19 at 100k items with 524k buckets
//! - **Collision rate**: Near-zero collisions in typical workloads
//! - **Lookup performance**: Often a single pointer dereference due to minimal collisions
//! - **Cache-optimized**: Node layout ordered for efficient CPU cache line usage
//!
//! # Architecture
//!
//! The implementation uses:
//! - **Bucket array**: Fixed-size array of atomic pointers (null-initialized)
//! - **Collision resolution**: Singly-linked lists for hash collisions
//! - **Node layout**: `hash -> key -> value -> next` for optimal cache performance
//! - **Updates**: Copy-on-write style replacements for existing keys
//!
//! # Example
//!
//! ```rust
//! use kovan_map::HashMap;
//! use std::sync::Arc;
//! use std::thread;
//!
//! // Create a shared hash map
//! let map = Arc::new(HashMap::new());
//!
//! // Spawn multiple threads for concurrent inserts
//! let mut handles = vec![];
//! for thread_id in 0..4 {
//! let map = Arc::clone(&map);
//! let handle = thread::spawn(move || {
//! for i in 0..1000 {
//! let key = thread_id * 1000 + i;
//! map.insert(key, key * 2);
//! }
//! });
//! handles.push(handle);
//! }
//!
//! // Wait for all threads to complete
//! for handle in handles {
//! handle.join().unwrap();
//! }
//!
//! // Read values from any thread
//! assert_eq!(map.get(&0), Some(0));
//! assert_eq!(map.get(&1000), Some(2000));
//!
//! // Remove values
//! assert_eq!(map.remove(&0), Some(0));
//! assert_eq!(map.remove(&0), None);
//! ```
//!
//! # Limitations
//!
//! - **Copy values**: Currently requires `V: Copy` for simplicity and performance
//! - **Clone keys**: Keys must implement `Clone` for update operations
//! - **Static lifetimes**: Both `K` and `V` must be `'static` for safe memory reclamation
//! - **Fixed capacity**: Uses a pre-allocated bucket array (cannot grow dynamically)
//!
//! # Use Cases
//!
//! This hash map is ideal for:
//! - High-throughput concurrent caching
//! - Lock-free data structures in systems programming
//! - Real-time applications where blocking is unacceptable
//! - Scenarios with many readers and occasional writers
//!
//! # Safety
//!
//! The implementation uses `unsafe` code internally for performance but provides a safe API.
//! Memory safety is guaranteed through the Kovan memory reclamation system, which ensures
//! nodes are only deallocated when no threads are accessing them.
pub use *;
pub use *;