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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171

//! This library offers a variety of weak hash tables:
//!
//!   - For a hash map where the keys are held by weak pointers and compared by key value, see
//!     [`WeakKeyHashMap`](struct.WeakKeyHashMap.html).
//!
//!   - For a hash map where the keys are held by weak pointers and compared by pointer, see
//!     [`PtrWeakKeyHashMap`](struct.PtrWeakKeyHashMap.html).
//!
//!   - For a hash map where the values are held by weak pointers, see
//!     [`WeakValueHashMap`](struct.WeakValueHashMap.html).
//!
//!   - For a hash map where the keys and values are both held by weak pointers and the keys are
//!     compared by value, see
//!     [`WeakWeakHashMap`](struct.WeakWeakHashMap.html).
//!
//!   - For a hash map where the keys and values are both held by weak pointers and the keys are
//!     compared by pointer, see
//!     [`PtrWeakWeakHashMap`](struct.PtrWeakWeakHashMap.html).
//!
//!   - For a hash set where the elements are held by weak pointers and compared by element value, see
//!     [`WeakHashSet`](struct.WeakHashSet.html).
//!
//!   - For a hash set where the elements are held by weak pointers and compared by pointer, see
//!     [`PtrWeakHashSet`](struct.PtrWeakHashSet.html).
//!
//! # Examples
//!
//! ```
//! use weak_table::WeakHashSet;
//! use std::sync::{Arc, Weak};
//!
//! type Table = WeakHashSet<Weak<String>>;
//!
//! let mut set = Table::new();
//! let a = Arc::new("a".to_string());
//! let b = Arc::new("b".to_string());
//!
//! set.insert(a.clone());
//!
//! assert!(   set.contains("a") );
//! assert!( ! set.contains("b") );
//!
//! set.insert(b.clone());
//!
//! assert!(   set.contains("a") );
//! assert!(   set.contains("b") );
//!
//! drop(a);
//!
//! assert!( ! set.contains("a") );
//! assert!(   set.contains("b") );
//! ```

use std::collections::hash_map::RandomState;

pub mod traits;
pub mod weak_key_hash_map;
pub mod ptr_weak_key_hash_map;
pub mod weak_value_hash_map;
pub mod weak_weak_hash_map;
pub mod ptr_weak_weak_hash_map;
pub mod weak_hash_set;
pub mod ptr_weak_hash_set;

mod util;
mod by_ptr;
mod size_policy;

#[derive(Copy, Clone, Debug, PartialEq, Eq)]
struct HashCode(u64);

type FullBucket<K, V> = (K, V, HashCode);
type Bucket<K, V> = Option<FullBucket<K, V>>;
type TablePtr<K, V> = Box<[Bucket<K, V>]>;

/// A hash map with weak keys, hashed on key value.
///
/// When a weak pointer expires, its mapping is lazily removed.
#[derive(Clone)]
pub struct WeakKeyHashMap<K, V, S = RandomState> {
    hash_builder: S,
    inner: WeakKeyInnerMap<K, V>,
}

#[derive(Clone)]
struct WeakKeyInnerMap<K, V> {
    buckets: TablePtr<K, V>,
    len: usize,
}

/// A hash map with weak keys, hashed on key pointer.
///
/// When a weak pointer expires, its mapping is lazily removed.
///
/// # Examples
///
/// ```
/// use weak_table::PtrWeakKeyHashMap;
/// use std::rc::{Rc, Weak};
///
/// type Table = PtrWeakKeyHashMap<Weak<String>, usize>;
///
/// let mut map = Table::new();
/// let a = Rc::new("hello".to_string());
/// let b = Rc::new("hello".to_string());
///
/// map.insert(a.clone(), 5);
///
/// assert_eq!( map.get(&a), Some(&5) );
/// assert_eq!( map.get(&b), None );
///
/// map.insert(b.clone(), 7);
///
/// assert_eq!( map.get(&a), Some(&5) );
/// assert_eq!( map.get(&b), Some(&7) );
/// ```
#[derive(Clone)]
pub struct PtrWeakKeyHashMap<K, V, S = RandomState>(
    WeakKeyHashMap<by_ptr::ByPtr<K>, V, S>
);

/// A hash map with weak values.
///
/// When a weak pointer expires, its mapping is lazily removed.
#[derive(Clone)]
pub struct WeakValueHashMap<K, V, S = RandomState> {
    hash_builder: S,
    inner: WeakValueInnerMap<K, V>,
}

#[derive(Clone)]
struct WeakValueInnerMap<K, V> {
    buckets: TablePtr<K, V>,
    len: usize,
}

/// A hash map with weak keys and weak values, hashed on key value.
///
/// When a weak pointer expires, its mapping is lazily removed.
#[derive(Clone)]
pub struct WeakWeakHashMap<K, V, S = RandomState> {
    hash_builder: S,
    inner: WeakWeakInnerMap<K, V>,
}

#[derive(Clone)]
struct WeakWeakInnerMap<K, V> {
    buckets: TablePtr<K, V>,
    len: usize,
}

/// A hash map with weak keys and weak values, hashed on key pointer.
///
/// When a weak pointer expires, its mapping is lazily removed.
#[derive(Clone)]
pub struct PtrWeakWeakHashMap<K, V, S = RandomState>(
    WeakWeakHashMap<by_ptr::ByPtr<K>, V, S>
);

/// A hash set with weak elements, hashed on element value.
///
/// When a weak pointer expires, its mapping is lazily removed.
#[derive(Clone)]
pub struct WeakHashSet<T, S = RandomState>(WeakKeyHashMap<T, (), S>);

/// A hash set with weak elements, hashed on element pointer.
///
/// When a weak pointer expires, its mapping is lazily removed.
#[derive(Clone)]
pub struct PtrWeakHashSet<T, S = RandomState>(PtrWeakKeyHashMap<T, (), S>);