kovan_map/
lib.rs

1#![doc(
2    html_logo_url = "https://raw.githubusercontent.com/vertexclique/kovan/master/art/kovan-square.svg"
3)]
4//! Two concurrent hash maps built on kovan's memory reclamation.
5//!
6//! - [`HashMap`]: separate chaining. [`HashMap::new`] starts with 524,288 buckets (about 4 MiB,
7//!   so a large map rarely resizes and a lookup is often one pointer); [`HashMap::with_capacity`]
8//!   starts with as many as asked. It grows when its load passes 3/4 and shrinks below 1/4, never
9//!   under its initial capacity.
10//! - [`HopscotchMap`]: open addressing in hopscotch neighborhoods. It starts at 64 slots and
11//!   grows and shrinks with its contents.
12//!
13//! Reads never wait: a lookup reads the current table under a kovan guard while writers and a
14//! resize run. Writers (inserts, removals, the conditional writes, `clear`) take no lock and race
15//! each other by compare-and-swap; a writer that meets a resize in flight waits for it to finish,
16//! and a hopscotch writer waits for the thread that holds its key's neighborhood. Hashing is
17//! FoldHash (`foldhash::fast::FixedState`) unless a hasher is given.
18//!
19//! # Keys and values
20//!
21//! Keys are `Hash + Eq + Clone` and values `Clone` (a read hands out a clone), both `Send +
22//! 'static`: a replaced or removed entry is freed by kovan once no reader can reach it, on
23//! whichever thread frees it, so its destructor may run on another thread.
24//!
25//! ```compile_fail
26//! // `Rc` is not `Send`: a map of them does not compile.
27//! let map = kovan_map::HashMap::with_capacity(8);
28//! map.insert(1, std::rc::Rc::new(1));
29//! ```
30//!
31//! # Example
32//!
33//! ```rust
34//! use kovan_map::HashMap;
35//! use std::sync::Arc;
36//! use std::thread;
37//!
38//! // Create a shared hash map
39//! let map = Arc::new(HashMap::new());
40//!
41//! // Spawn multiple threads for concurrent inserts
42//! let mut handles = vec![];
43//! for thread_id in 0..4 {
44//!     let map = Arc::clone(&map);
45//!     let handle = thread::spawn(move || {
46//!         for i in 0..1000 {
47//!             let key = thread_id * 1000 + i;
48//!             map.insert(key, key * 2);
49//!         }
50//!     });
51//!     handles.push(handle);
52//! }
53//!
54//! // Wait for all threads to complete
55//! for handle in handles {
56//!     handle.join().unwrap();
57//! }
58//!
59//! // Read values from any thread
60//! assert_eq!(map.get(&0), Some(0));
61//! assert_eq!(map.get(&1000), Some(2000));
62//!
63//! // Remove values
64//! assert_eq!(map.remove(&0), Some(0));
65//! assert_eq!(map.remove(&0), None);
66//! ```
67//!
68//! # Safety
69//!
70//! The implementation uses `unsafe` code internally for performance but provides a safe API.
71//! Memory safety is guaranteed through the Kovan memory reclamation system, which ensures
72//! nodes are only deallocated when no threads are accessing them.
73
74#![warn(missing_docs)]
75#![no_std]
76
77#[cfg(feature = "std")]
78extern crate std;
79
80mod hashmap;
81mod hopscotch;
82mod sync;
83#[cfg(test)]
84mod test_support;
85
86pub use hashmap::*;
87pub use hopscotch::*;
kovan_map/lib.rs

kovan_map/
lib.rs
