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
22//! [`MaybeSend`] and `'static`: a replaced or removed entry is freed by kovan once no reader can
23//! reach it, on whichever thread frees it, so its destructor may run on another thread. Wherever
24//! threads can share memory that means `Send`; on wasm32 without the `atomics` feature, which has
25//! one thread, it asks nothing.
26//!
27//! ```compile_fail
28//! // `Rc` is not `Send`: where threads share memory, a map of them does not compile.
29//! let map = kovan_map::HashMap::with_capacity(8);
30//! map.insert(1, std::rc::Rc::new(1));
31//! ```
32//!
33//! # Example
34//!
35//! ```rust
36//! use kovan_map::HashMap;
37//! use std::sync::Arc;
38//! use std::thread;
39//!
40//! // Create a shared hash map
41//! let map = Arc::new(HashMap::new());
42//!
43//! // Spawn multiple threads for concurrent inserts
44//! let mut handles = vec![];
45//! for thread_id in 0..4 {
46//!     let map = Arc::clone(&map);
47//!     let handle = thread::spawn(move || {
48//!         for i in 0..1000 {
49//!             let key = thread_id * 1000 + i;
50//!             map.insert(key, key * 2);
51//!         }
52//!     });
53//!     handles.push(handle);
54//! }
55//!
56//! // Wait for all threads to complete
57//! for handle in handles {
58//!     handle.join().unwrap();
59//! }
60//!
61//! // Read values from any thread
62//! assert_eq!(map.get(&0), Some(0));
63//! assert_eq!(map.get(&1000), Some(2000));
64//!
65//! // Remove values
66//! assert_eq!(map.remove(&0), Some(0));
67//! assert_eq!(map.remove(&0), None);
68//! ```
69//!
70//! # Safety
71//!
72//! The implementation uses `unsafe` code internally for performance but provides a safe API.
73//! Memory safety is guaranteed through the Kovan memory reclamation system, which ensures
74//! nodes are only deallocated when no threads are accessing them.
75
76#![warn(missing_docs)]
77#![no_std]
78
79#[cfg(feature = "std")]
80extern crate std;
81
82mod hashmap;
83mod hopscotch;
84mod maybe_send;
85mod sync;
86#[cfg(test)]
87mod test_support;
88
89pub use hashmap::*;
90pub use hopscotch::*;
91pub use maybe_send::MaybeSend;
kovan_map/lib.rs

kovan_map/
lib.rs
