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
//! rc-hashmap: A single-threaded, handle-based map with Rc-like
//! references to entries that allow fast access and cleanup on drop.
//!
//! Internal Design:
//!
//! Summary
//! - Goal: build RcHashMap in safe, verifiable layers so each piece can
//! be reasoned about independently.
//! - Layers:
//! - HandleHashMap<K, V, S>: structural map that returns stable
//! handles for O(1) average access without re-hashing; includes a
//! debug-only reentrancy guard to keep internals consistent while
//! mutating.
//! - CountedHashMap<K, V, S>: wraps HandleHashMap and adds per-entry
//! reference counting (increments on get/clone, decrements on put).
//! - RcHashMap<K, V, S>: public API that exposes `Ref` handles; drops
//! free entries when the last `Ref` is dropped.
//!
//! Constraints
//! - Single-threaded: `!Send`/`!Sync` by design (no atomics).
//! - No per-entry heap allocations beyond the map’s own storage.
//! - Stable, generational keys behind small `Handle` wrappers.
//! - O(1) average lookups with unique keys; duplicate inserts fail.
//! - Reentrancy: disallowed during critical sections of HandleHashMap
//! (only `K: Eq/Hash` may run); allowed elsewhere.
//!
//! Why this split?
//! - Localize invariants: each layer has a small, precise contract.
//! - Minimize unsafe: raw-pointer handling is isolated in `tokens::RcCount`;
//! structural indexing uses safe Rust.
//! - Clear failure boundaries: HandleHashMap never calls into user code
//! once the structure is consistent.
//!
//! Reentrancy policy and interior mutability
//! - HandleHashMap employs an internal exclusive-access discipline and a
//! debug-only reentrancy guard at the start of each method to prevent
//! nested entry while its internal state can be transiently
//! inconsistent. These methods only invoke user code via `K: Eq/Hash`
//! during probing.
//! - Upper layers (CountedHashMap, RcHashMap) rely on HandleHashMap’s
//! guarantees and do not need their own guard. After
//! `HandleHashMap::remove` returns `(K, V)`, the structure is again
//! consistent; `Drop` for `K`/`V` may reenter safely.
//!
//! Overflow semantics
//! - Reference-count overflow is considered undefined behavior, matching
//! `Rc`. The crate assumes there are fewer than `usize::MAX` references
//! to any entry; no runtime checks are performed.
//!
//! Hasher and rehashing invariants
//! - Each entry stores a precomputed `u64` hash and indexing always uses
//! the stored hash; `K: Hash` is never invoked after insertion. This
//! avoids rehash-time calls into user code.
//!
//! Notes and non-goals
//! - Still single-threaded; enforced with marker types on `Ref`/`Inner`.
//! - No weak handles (could be added later).
//! - No explicit `clear()`/`remove()`/`drain()` on RcHashMap; removal
//! occurs when the last `Ref` is dropped to preserve refcount
//! semantics.
//! - RcHashMap does not implement `Clone`.
//! - Keys are immutable post-insert; there is no `key_mut`.
//! - Public API surface is `RcHashMap` and its `Ref`; lower layers are
//! implementation details.
//!
//! Implementation note
//! - The internal `RcCount<T>` helper (in `tokens`) encapsulates the
//! raw-pointer based use of `std::rc::Rc` increment/decrement APIs.
// Public surface
pub use InsertError;
pub use DefaultHashBuilder;
pub use ;