Skip to content

Instantly share code, notes, and snippets.

@DutchGhost
Created May 16, 2021 12:43
Show Gist options
  • Select an option

  • Save DutchGhost/52ba1dd238cd8627a94dbd5eb995237a to your computer and use it in GitHub Desktop.

Select an option

Save DutchGhost/52ba1dd238cd8627a94dbd5eb995237a to your computer and use it in GitHub Desktop.
Rc with custom counter
extern crate alloc;
use {
alloc::alloc::dealloc,
core::{
alloc::Layout,
cell::Cell,
marker::PhantomData,
ops::{Add, Sub},
ptr::{self, NonNull},
},
};
pub unsafe trait Counter: Copy + Add<Output = Self> + Sub<Output = Self> + Eq {
const ZERO: Self;
const INIT: Self;
}
macro_rules! impl_counter {
($t:ty) => {
unsafe impl Counter for $t {
const ZERO: Self = 0;
const INIT: Self = 1;
}
};
}
impl_counter!(usize);
impl_counter!(u8);
impl_counter!(u32);
#[repr(C)]
struct RcBox<T: ?Sized, C: Counter> {
strong: Cell<C>,
weak: Cell<C>,
value: T,
}
impl<T: ?Sized, C: Counter> RcBox<T, C> {
fn inc_strong(&self) {
let old_strong = self.strong.get();
self.strong.set(old_strong + C::INIT);
}
fn dec_strong(&self) {
let old_strong = self.strong.get();
self.strong.set(old_strong - C::INIT);
}
fn dec_weak(&self) {
let old_strong = self.weak.get();
self.weak.set(old_strong - C::INIT);
}
fn strong(&self) -> C {
self.strong.get()
}
fn weak(&self) -> C {
self.weak.get()
}
}
/// A single-threaded reference-counting pointer. 'Rc' stands for 'Reference
/// Counted'.
///
/// See the [module-level documentation](./index.html) for more details.
///
/// The inherent methods of `Rc` are all associated functions, which means
/// that you have to call them as e.g., [`Rc::get_mut(&mut value)`][get_mut] instead of
/// `value.get_mut()`. This avoids conflicts with methods of the inner type `T`.
///
/// [get_mut]: Rc::get_mut
pub struct Rc<T: ?Sized, C: Counter> {
ptr: NonNull<RcBox<T, C>>,
phantom: PhantomData<RcBox<T, C>>,
}
impl<T, C: Counter> Rc<T, C> {
fn new(value: T) -> Self {
Self::from_inner(NonNull::from(Box::leak(Box::new(RcBox {
strong: Cell::new(C::INIT),
weak: Cell::new(C::INIT),
value,
}))))
}
}
impl<T: ?Sized, C: Counter> Rc<T, C> {
pub fn weak_count(this: &Self) -> C {
this.inner().weak() - C::INIT
}
#[inline]
pub fn strong_count(this: &Self) -> C {
this.inner().strong()
}
fn is_unique(this: &Self) -> bool {
Rc::weak_count(this) == C::ZERO && Rc::strong_count(this) == C::INIT
}
pub unsafe fn get_mut_unchecked(this: &mut Self) -> &mut T {
unsafe { &mut (*this.ptr.as_ptr()).value }
}
pub fn get_mut(this: &mut Self) -> Option<&mut T> {
if Rc::is_unique(this) {
unsafe { Some(Rc::get_mut_unchecked(this)) }
} else {
None
}
}
}
impl<T: ?Sized, C: Counter> Rc<T, C> {
fn inner(&self) -> &RcBox<T, C> {
unsafe { self.ptr.as_ref() }
}
fn from_inner(ptr: NonNull<RcBox<T, C>>) -> Self {
Self {
ptr,
phantom: PhantomData,
}
}
}
impl<T: ?Sized, C: Counter> Clone for Rc<T, C> {
#[inline]
fn clone(&self) -> Rc<T, C> {
self.inner().inc_strong();
Self::from_inner(self.ptr)
}
}
impl<T: ?Sized, C: Counter> Drop for Rc<T, C> {
fn drop(&mut self) {
unsafe {
self.inner().dec_strong();
if self.inner().strong() == C::ZERO {
// destroy the contained object
ptr::drop_in_place(Self::get_mut_unchecked(self));
// remove the implicit "strong weak" pointer now that we've
// destroyed the contents.
self.inner().dec_weak();
if self.inner().weak() == C::ZERO {
dealloc(
self.ptr.cast().as_ptr(),
Layout::for_value(self.ptr.as_ref()),
);
}
}
}
}
}
fn main() {
let mut x: Rc<String, u8> = Rc::new(String::new());
let v = (0u8..254).map(|_| Rc::clone(&x)).collect::<Vec<_>>();
drop(v);
let foo = Rc::clone(&x);
drop(foo);
dbg!(Rc::get_mut(&mut x));
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment