Skip to content

Как работает счётчик ссылок (Rc) в Rust?

В этой статье я хочу рассказать, как создать свой Rc на Rust. Для этого мы будем использовать только стандартную библиотеку. Зачем это нужно? Это хорошая практика, чтобы лучше понять, как работает Rc. Разумеется, статья расчитана на тех, кто начинает изучать Rust.

Что такое Rc?

У данных есть владелец (owner). Владелец — это переменная, которая хранит в себе данные. Когда владелец удаляется, данные удаляются из памяти. Удаление происходит автоматически, когда владелец выходит из области видимости. По умолчанию, владелец может быть только один и компилятор нам это гарантирует.

Представим ситуацию, когда есть несколько владельцев. Такое возможно, если у нас есть несколько переменных, которые хранят в себе одни и те же данные, например, структура дерево (Tree).

srtuct TreeNode {
    left: Option<Rc<RefCell<TreeNode>>>,
    right: Option<Rc<RefCell<TreeNode>>>,
}

Как тогда компилятор будет понимать, когда удалять данные? Для этого мы можем использовать умный указатель Rc. По сути, мы переносим управление памятью в runtime.

Rc — это счетчик ссылок. Он позволяет считать, сколько раз мы используем один и тот же объект. Когда счетчик ссылок становится равным нулю, объект удаляется из памяти. Примерно так работает стандартный Rc.

Немного теории

Для начала, давайте разберем базовые понятия, которые нам понадобятся для создания своего Rc. Rust — это язык протоколов (автор приносит свою терминологию). Протокол — это набор методов, которые должны быть реализованы для определенного типа данных. Подобно magic methods в Python, Rust реализует это через traits, вызывая их (методы) в нужный момент. С помощью traits мы можем переопределить поведение операторов +-/..., добавлять логику при создании/удалении объектов и т.д.

Trait Clone

Clone — это trait, который позволяет создавать копию объекта (не путать с трейтом Copy, который копирует по битно на стеке). Мы можешь переопределить метод clone, чтобы создавать якобы копию объекта. Таким образом, компилятор не будет ругаться, что мы пытаемся иметь несколько владельцев, так как мы якобы создаем копию объекта и говорим это компилятоору.

let a = S::new();
let b = a.clone();

Trait Drop

Drop — это trait, метод которого вызывается, когда переменная выходит из области видимости. Мы также можем определить метод drop, чтобы выполнять какие-то действия, когда переменная выходит из блока.

let a = S::new();
{
    let b = S::new();
} // b выходит из области видимости и вызывается метод drop

Trait Deref/DerefMut

Deref — это trait, который позволяет нам определить поведение для оператора разыменования.

println!("{:?}", *a);

Только синтаскический сахар, чтобы было проще использовать объекты.

DerefMut — аналогично, только для изменяемых ссылок.

Итог

Возможно вы догадались, что переопределив методы clone и drop мы можем создать свой Rc.

Алгоритм будет следующий:

  1. let a = MyRc::new(val) — создаем объект и счетчик ссылок равный 1. Важно отметить, что мы создаем наш счетчик и данные в куче, а не на стеке. Подумайте, почему.
  2. a.clone() — увеличиваем счетчик ссылок и копируем указатель на данные. Счетчик ссылок хранится в структуре Rc.
  3. Drop — уменьшаем счетчик ссылок и удаляем данные, если счетчик ссылок равен 1.

Реализация

Давайте реализуем наш Rc. Для начала, создадим структуру, которая будет хранить данные и наш счетчик.

#[repr(C)]
#[derive(Debug)]
struct MyRcBox<T: ?Sized> {
    count: Cell<usize>,
    val: T,
}
  • ?Sized — означает, что мы можем использовать любой тип данных, который неизвестен на этапе компиляции.
  • Cell — типаж, который позволяет нам изменять данные внутри структуры, даже если она неизменяемая. Работает только с типами, которые реализуют типаж Copy.
  • repr(C) — говорит компилятору, что мы хотим, чтобы данные хранились в памяти в том же порядке, что и в структуре. Не обязательно, но это может быть полезно, если мы хотим взаимодействовать с кодом на других языках.

Теперь, создадим структуру, которая будет хранить указатель на данные и счетчик ссылок.

struct MyRc<T: ?Sized> {
    ptr: NonNull<MyRcBox<T>>,
}

NonNull — это указатель, который гарантирует, что он не равен None.

Теперь, давайте реализуем методы для нашего Rc.

impl<T> MyRc<T> {
    fn new(val: T) -> Self {
        Self {
            ptr: Box::leak(Box::new(MyRcBox {
                count: Cell::new(1),
                val,
            }))
            .into(),
        }
    }
}

Box::leak — это метод, который позволяет нам получить указатель на данные, которые хранятся в куче. Также данный метод гарантирует, что данные не будут удалены из памяти при выходе из области видимости. Это может привести к утечкам памяти, think about it.

Дальше, реализуем метод clone.

impl<T: ?Sized> Clone for MyRc<T> {
    fn clone(&self) -> Self {
        unsafe {
            *(*self.ptr.as_ptr()).count.get_mut() += 1;
        }
        Self { ptr: self.ptr }
    }
}

unsafe — это ключевое слово, которое говорит компилятору, что мы знаем, что делаем. Разыменовываем указатель, чтобы получить доступ к данным и увеличиваем счетчик ссылок. Обратите внимание, что наш Rc не является потокобезопасным. Можете попробовать реализовать потокобезопасность самостоятельно в качестве упражнения.

Далее определим методы deref, чтобы можно было использовать оператор разыменования.

impl<T: ?Sized> Deref for MyRc<T> {
    type Target = T;

    fn deref(&self) -> &Self::Target {
        unsafe { &(*self.ptr.as_ptr()).val }
    }
}

impl<T: ?Sized> DerefMut for MyRc<T> {
    fn deref_mut(&mut self) -> &mut Self::Target {
        unsafe { &mut (*self.ptr.as_ptr()).val }
    }
}

Теперь, реализуем метод drop.

impl<T: ?Sized> Drop for MyRc<T> {
    fn drop(&mut self) {
        unsafe {
            // comment this and memory will leak
            let count = (*self.ptr.as_ptr()).count.get_mut();
            *count -= 1;
            if *count == 1 {
                let _ = Box::from_raw(self.ptr.as_ptr());
            }
        }
    }
}

Данная конструкция уже знакома вам. Мы уменьшаем счетчик ссылок и удаляем данные, если счетчик ссылок равен 1. Почему 1? Потому что мы создаем объект сразу с счётчиком ссылок равным 1, так как фактически у нас уже есть один владелец. Данные мы удаляем, создавая новую переменную, далее всю работу делает компилятор. При выходе из области видимости, вызывается метод drop и удаляются данные.

И, наконец, функция main для проверки. Важно отметить, что мы используем unsafe, только чтобы вывести данные на экран.

fn main() {
    let data = String::from("data");
    let val = MyRc::new(data);
    let mut cloned_val = val.clone();
    let p = val.ptr.as_ptr();
    unsafe {
        println!("{:?}", *p);
    }
    *cloned_val = String::from("new data");
    println!("Changed to {:?}", &*val);
    {
        let other = val;
    }
    unsafe {
        println!("{:?}", *p);
    }
}

Заключение

В этой статье мы рассмотрели, как создать свой Rc на Rust. Мы использовали только стандартную библиотеку и немного теории. Надеюсь, что статья была полезной и вы узнали что-то новое. Теперь вы знаете, как работает Rc и можете использовать эту информацию на собеседованиях.

Ссылки

Comments