genref/
lib.rs

1#![feature(assert_matches)]
2
3//! # Generational counting
4//!
5//! This crate implements Vale's generational reference counting memory
6//! management. Intended as an alternative to Rc with slightly different
7//! semantics.
8//!
9//! Advantages over `Rc`:
10//! - Sharing references are `Copy` and therefore extremely cheap
11//! - RAII semantics
12//!
13//! Disadvantages:
14//! - Only one owned reference, requiring management
15//! - Dereferencing returns `Option`
16//! - Not `Deref`
17//!
18//! The locking system is non-granular for ease of implementation (and possibly
19//! speed.)
20
21#[cfg(test)]
22mod tests;
23
24#[cfg(feature = "global")]
25mod global;
26
27use std::{
28    cell::{Cell, RefCell},
29    mem,
30};
31
32#[repr(transparent)]
33#[derive(Clone, Copy)]
34struct Generation(NonNull<Cell<u32>>);
35
36impl Generation
37{
38    fn new() -> Self { FreeList::unfree().unwrap_or_else(FreshList::fresh) }
39
40    fn get(&self) -> u32 { unsafe { self.0.as_ref() }.get() }
41
42    fn free(this: Self)
43    {
44        let c = unsafe { this.0.as_ref() };
45
46        if c.get() == u32::MAX {
47            c.set(0);
48        } else {
49            c.set(c.get() + 1);
50            FreeList::free(this);
51        }
52    }
53}
54
55thread_local! {
56    static FREELIST : RefCell<FreeList> = RefCell::new(FreeList::new());
57    static FRESHLIST : RefCell<FreshList> = RefCell::new(FreshList::new());
58    static LOCK : Lock = Lock::new();
59    static DROPQUEUE : RefCell<DropQueue> = RefCell::new(DropQueue::new());
60}
61
62struct Lock(Cell<isize>);
63
64/// Non-exclusive lock (ZST)
65///
66/// Used to create shared references to underlying objects,
67/// its existence defers dropping of allocated objects.
68#[derive(Debug)]
69pub struct Reading(());
70pub fn reading() -> Option<Reading> { Lock::reading() }
71
72/// Exclusive lock (ZST)
73///
74/// Used to create mutable references to underlying objects,
75/// its existence defers dropping of allocated objects.
76#[derive(Debug)]
77pub struct Writing(());
78pub fn writing() -> Option<Writing> { Lock::writing() }
79
80impl Lock
81{
82    fn new() -> Self { Self(Cell::new(0)) }
83    fn reading() -> Option<Reading>
84    {
85        if Self::readable() {
86            unsafe { Self::read() }
87            Some(Reading(()))
88        } else {
89            None
90        }
91    }
92
93    fn writing() -> Option<Writing>
94    {
95        if Self::writable() {
96            unsafe { Self::write() }
97            Some(Writing(()))
98        } else {
99            None
100        }
101    }
102
103    fn writable() -> bool { LOCK.with(|l| l.0.get() == 0) }
104    unsafe fn write() { LOCK.with(|l| l.0.set(-1)) }
105    unsafe fn unwrite() { LOCK.with(|l| l.0.set(0)) }
106
107    fn readable() -> bool { LOCK.with(|l| l.0.get() >= 0) }
108    unsafe fn read() { LOCK.with(|l| l.0.set(l.0.get() + 1)) }
109    unsafe fn unread() { LOCK.with(|l| l.0.set(l.0.get() - 1)) }
110}
111
112impl Drop for Reading
113{
114    fn drop(&mut self)
115    {
116        unsafe { Lock::unread() }
117        if let Some(mut wl) = Lock::writing() {
118            let d = DropQueue::clear(&mut wl);
119            mem::drop(wl);
120            mem::drop(d);
121        }
122    }
123}
124
125impl Clone for Reading
126{
127    fn clone(&self) -> Self
128    {
129        unsafe { Lock::read() }
130        Self(())
131    }
132}
133
134impl Drop for Writing
135{
136    fn drop(&mut self)
137    {
138        let q = DropQueue::clear(self);
139        unsafe { Lock::unwrite() }
140        mem::drop(q);
141    }
142}
143
144struct FreeList(Vec<Generation>);
145struct FreshList(usize, Vec<Cell<u32>>, Vec<Vec<Cell<u32>>>);
146
147impl FreeList
148{
149    fn new() -> Self { Self(Vec::with_capacity(32)) }
150
151    fn free_(&mut self, gen: Generation) { self.0.push(gen) }
152    fn free(gen: Generation) { FREELIST.with(|fl| fl.borrow_mut().free_(gen)) }
153
154    fn unfree_(&mut self) -> Option<Generation> { self.0.pop() }
155    fn unfree() -> Option<Generation> { FREELIST.with(|fl| fl.borrow_mut().unfree_()) }
156}
157
158impl FreshList
159{
160    const INIT: u32 = 1;
161    fn new() -> Self { Self(0, Self::more(32), vec![]) }
162
163    fn fresh_(&mut self) -> Generation
164    {
165        if self.0 == self.1.len() {
166            self.refresh()
167        }
168        self.0 += 1;
169        Generation(NonNull::from(&self.1[self.0 - 1]))
170    }
171
172    fn fresh() -> Generation { FRESHLIST.with(|fl| fl.borrow_mut().fresh_()) }
173
174    fn refresh(&mut self)
175    {
176        self.2
177            .push(mem::replace(&mut self.1, Self::more(self.0 + self.0 / 2)));
178        self.0 = 0;
179    }
180
181    fn more(n: usize) -> Vec<Cell<u32>> { vec![Cell::new(Self::INIT); n] }
182}
183
184trait DropLater {}
185impl<T> DropLater for T {}
186struct DropQueue(Vec<Box<dyn DropLater>>);
187
188impl DropQueue
189{
190    fn new() -> Self { Self(Vec::with_capacity(32)) }
191
192    fn clear_(&mut self, _wl: &mut Writing) -> impl Drop
193    {
194        let re = Vec::with_capacity(self.0.len());
195        mem::replace(&mut self.0, re)
196    }
197
198    fn clear(wl: &mut Writing) -> impl Drop { DROPQUEUE.with(|dq| dq.borrow_mut().clear_(wl)) }
199
200    fn defer_(&mut self, val: Box<dyn DropLater>) { self.0.push(val) }
201    fn defer(val: Box<dyn DropLater>) { DROPQUEUE.with(|dq| dq.borrow_mut().defer_(val)) }
202}
203
204use std::{mem::ManuallyDrop, ptr::NonNull};
205
206/// Strong reference
207///
208/// Owns its underlying allocation.
209///
210/// The generation counter is allocated separately, since it must persist for
211/// the entire lifetime of all `Weak` references.
212pub struct Strong<T: 'static>
213{
214    gen: Generation,
215    ptr: ManuallyDrop<Box<T>>,
216}
217
218/// Weak reference
219///
220/// Stores its reference generation locally and cross-checks it everytime an
221/// access is made.
222pub struct Weak<T: 'static>
223{
224    genref: u32,
225    gen: Generation,
226    ptr: NonNull<T>,
227}
228
229impl<T: 'static> Drop for Strong<T>
230{
231    fn drop(&mut self)
232    {
233        Generation::free(self.gen);
234        if let Some(wl) = Lock::writing() {
235            let d = unsafe { ManuallyDrop::take(&mut self.ptr) };
236            mem::drop(wl);
237            mem::drop(d);
238        } else {
239            DropQueue::defer(unsafe { ManuallyDrop::take(&mut self.ptr) } as Box<dyn DropLater>);
240        }
241    }
242}
243
244impl<T: 'static> Strong<T>
245{
246    pub fn new(t: T) -> Self { Self::from(Box::new(t)) }
247
248    pub fn alias(&self) -> Weak<T>
249    {
250        Weak {
251            genref: self.gen.get(),
252            gen: self.gen,
253            ptr: NonNull::from((*self.ptr).as_ref()),
254        }
255    }
256
257    pub fn take(mut self, _wl: &mut Writing) -> Box<T>
258    {
259        Generation::free(self.gen);
260        let b = unsafe { ManuallyDrop::take(&mut self.ptr) };
261        mem::forget(self);
262        b
263    }
264
265    pub fn as_ref(&self, _rl: &Reading) -> &T { &self.ptr }
266    pub fn as_mut(&mut self, _wl: &mut Writing) -> &mut T { &mut self.ptr }
267
268    pub fn map<F, U>(&self, rl: &Reading, f: F) -> Weak<U>
269    where
270        for<'a> F: Fn(&'a T) -> &'a U,
271    {
272        Weak {
273            genref: self.gen.get(),
274            gen: self.gen,
275            ptr: NonNull::from(f(self.as_ref(rl))),
276        }
277    }
278}
279
280impl<T: 'static> From<Box<T>> for Strong<T>
281{
282    fn from(b: Box<T>) -> Self
283    {
284        Self {
285            gen: Generation::new(),
286            ptr: ManuallyDrop::new(b),
287        }
288    }
289}
290
291impl<T: 'static> Weak<T>
292{
293    pub fn dangling() -> Self
294    {
295        static mut ZERO: Cell<u32> = Cell::new(0);
296        Weak {
297            genref: u32::MAX,
298            gen: Generation(NonNull::from(unsafe { &mut ZERO })),
299            ptr: NonNull::dangling(),
300        }
301    }
302
303    pub fn is_valid(&self) -> bool { self.genref == self.gen.get() }
304
305    pub fn try_ref(&self, _rl: &Reading) -> Option<&T>
306    {
307        if self.is_valid() {
308            Some(unsafe { self.ptr.as_ref() })
309        } else {
310            None
311        }
312    }
313
314    pub fn try_mut(&mut self, _wl: &mut Writing) -> Option<&mut T>
315    {
316        if self.is_valid() {
317            Some(unsafe { self.ptr.as_mut() })
318        } else {
319            None
320        }
321    }
322
323    pub fn try_map<F, U>(&self, rl: &Reading, f: F) -> Option<Weak<U>>
324    where
325        for<'a> F: Fn(&'a T) -> &'a U,
326    {
327        if let Some(a) = self.try_ref(rl) {
328            Some(Weak {
329                genref: self.genref,
330                gen: self.gen,
331                ptr: NonNull::from(f(a)),
332            })
333        } else {
334            None
335        }
336    }
337}
338
339impl<T: 'static> Clone for Weak<T>
340{
341    fn clone(&self) -> Self { *self }
342}
343
344impl<T: 'static> Copy for Weak<T> {}
345
346pub enum Ref<T: 'static>
347{
348    Strong(Strong<T>),
349    Weak(Weak<T>),
350}
351
352impl<T: 'static> Ref<T>
353{
354    /// New strong reference
355    pub fn new(t: T) -> Self { Self::Strong(Strong::new(t)) }
356
357    pub fn try_as_ref(&self, rl: &Reading) -> Option<&T>
358    {
359        match self {
360            Ref::Strong(s) => Some(s.as_ref(rl)),
361            Ref::Weak(w) => w.try_ref(rl),
362        }
363    }
364
365    pub fn try_mut(&mut self, wl: &mut Writing) -> Option<&mut T>
366    {
367        match self {
368            Ref::Strong(s) => Some(s.as_mut(wl)),
369            Ref::Weak(w) => w.try_mut(wl),
370        }
371    }
372
373    pub fn try_map<F, U>(&self, rl: &Reading, f: F) -> Option<Ref<U>>
374    where
375        for<'a> F: Fn(&'a T) -> &'a U,
376    {
377        match self {
378            Ref::Strong(s) => Some(Ref::Weak(s.map(rl, f))),
379            Ref::Weak(w) => w.try_map(rl, f).map(Ref::Weak),
380        }
381    }
382
383    pub fn is_weak(&self) -> bool
384    {
385        match self {
386            Ref::Strong(_) => false,
387            Ref::Weak(_) => true,
388        }
389    }
390
391    pub fn is_strong(&self) -> bool
392    {
393        match self {
394            Ref::Strong(_) => false,
395            Ref::Weak(_) => true,
396        }
397    }
398
399    pub fn is_valid(&self) -> bool
400    {
401        match self {
402            Ref::Strong(_) => true,
403            Ref::Weak(w) => w.is_valid(),
404        }
405    }
406}
407
408impl<T: 'static> Clone for Ref<T>
409{
410    fn clone(&self) -> Self
411    {
412        match self {
413            Self::Strong(s) => Self::Weak(s.alias()),
414            Self::Weak(w) => Self::Weak(*w),
415        }
416    }
417}
418
419impl<T: 'static> From<Weak<T>> for Ref<T>
420{
421    fn from(w: Weak<T>) -> Self { Ref::Weak(w) }
422}
423
424impl<T: 'static> From<Strong<T>> for Ref<T>
425{
426    fn from(s: Strong<T>) -> Self { Ref::Strong(s) }
427}
genref/lib.rs

genref/
lib.rs
