159 lines
No EOL
10 KiB
Markdown
159 lines
No EOL
10 KiB
Markdown
`Rc<T>` (Reference Counting) используется для ситуаций **разделяемого владения** (shared ownership), когда данные должны жить до тех пор, пока жив хотя бы один их "владелец".
|
||
|
||
### Зачем это нужно?
|
||
Основная причина: **неизвестность времени жизни в compile-time**.
|
||
В обычной модели владения Rust (`Box<T>`) у данных может быть только *один* владелец. Но в реальных структурах данных (графы, деревья с обратными ссылками, UI-компоненты) часто бывает, что "родителей" много, и мы не знаем заранее, кто из них удалится последним.
|
||
|
||
**Пример:**
|
||
Узел графа. На него ссылаются 5 других узлов. Если владелец только один, то удаление этого "главного" узла сломает все остальные 4 ссылки (сделает их невалидными). `Rc` решает это: узел жив, пока на него есть хотя бы одна ссылка.
|
||
|
||
### Основные характеристики
|
||
1. **Shared Ownership:** Позволяет нескольким частям программы владеть одними данными.
|
||
2. **Immutable:** `Rc<T>` позволяет получить только **иммутабельную** (неизменяемую) ссылку `&T` на данные.[2]
|
||
* *Почему?* Если бы `Rc` давал `&mut T`, это нарушило бы правила заимствования (множество мутабельных ссылок на одни данные = data race).
|
||
* *Как изменять?* Для изменяемости внутри `Rc` используется паттерн **Interior Mutability** (обычно в связке `Rc<RefCell<T>>`).
|
||
3. **Single-threaded:** `Rc` не потокобезопасен. Счетчик ссылок обновляется обычными арифметическими операциями (быстро), а не атомарными. Для многопоточности есть `Arc<T>` (Atomic Reference Counting).[6][2]
|
||
|
||
### Как это работает (под капотом)
|
||
`Rc::new(v)` аллоцирует в куче структуру, содержащую:
|
||
* Само значение `v`.
|
||
* `strong_count`: счетчик "сильных" ссылок (владельцев).
|
||
* `weak_count`: счетчик "слабых" ссылок (для предотвращения циклов).
|
||
|
||
Каждый `Rc::clone(&rc)` не копирует данные, а просто инкрементирует счетчик `strong_count`.
|
||
Когда `Rc` выходит из области видимости (`drop`), счетчик декрементируется.
|
||
Когда `strong_count == 0`, данные удаляются из памяти (`free`).
|
||
|
||
### Итог
|
||
Используйте `Rc`, когда данные нужны в нескольких местах, и вы не можете построить иерархию, где один владелец живет дольше всех остальных. Но помните, что `Rc` дает только чтение. Для записи нужна обертка `RefCell`.
|
||
|
||
[1](https://labex.io/ru/tutorials/rc-t-the-reference-counted-smart-pointer-100434)
|
||
[2](https://doc.rust-lang.org/book/ch15-04-rc.html)
|
||
[3](https://www.reddit.com/r/rust/comments/1n65om2/is_stdrcrc_identical_to_references_without/)
|
||
[4](https://habr.com/ru/companies/bitrix/articles/878912/comments/)
|
||
[5](https://rust-book.cs.brown.edu/ch15-04-rc.html)
|
||
[6](https://doc.rust-lang.org/std/rc/struct.Rc.html)
|
||
[7](https://my-js.org/docs/guide/rust)
|
||
[8](https://notes.kodekloud.com/docs/Rust-Programming/Advanced-Rust-Concepts/Rc-Reference-Counting-and-Shared-Ownership)
|
||
[9](https://labex.io/ru/tutorials/exploring-rust-s-reference-counting-mechanism-99263)
|
||
|
||
|
||
|
||
Реализация B-дерева на `Rc` — это классический пример того, где приходится использовать паттерн **Interior Mutability** (внутренняя изменяемость).
|
||
|
||
Почему? Потому что `Rc<T>` дает нам **неизменяемую** ссылку на данные. А в B-дереве нам нужно постоянно менять содержимое узлов (добавлять ключи, перекидывать детей). Чтобы "обойти" неизменяемость `Rc`, мы кладем данные внутрь `RefCell`.
|
||
|
||
Получается "бутерброд": `Rc<RefCell<Node>>`.
|
||
|
||
Вот упрощенная реализация структуры и поиска (полная реализация со сплитами и балансировкой заняла бы сотни строк, поэтому я покажу суть связывания через `Rc`):
|
||
|
||
```rust
|
||
use std::rc::Rc;
|
||
use std::cell::RefCell;
|
||
use std::fmt::Debug;
|
||
|
||
// 1. Опишем узел.
|
||
// B-дерево состоит из ключей и детей.
|
||
#[derive(Debug)]
|
||
struct Node<T> {
|
||
keys: Vec<T>,
|
||
// Дети хранятся через Rc, чтобы мы могли иметь несколько ссылок на узел
|
||
// (например, одна ссылка у родителя, другая у курсора-итератора).
|
||
// RefCell нужен, чтобы мы могли менять children/keys внутри Rc.
|
||
children: Vec<Rc<RefCell<Node<T>>>>,
|
||
}
|
||
|
||
impl<T> Node<T> {
|
||
fn new(keys: Vec<T>) -> Self {
|
||
Node {
|
||
keys,
|
||
children: Vec::new(),
|
||
}
|
||
}
|
||
}
|
||
|
||
// 2. Создадим удобный алиас типа для "умной ссылки на узел"
|
||
type NodeLink<T> = Rc<RefCell<Node<T>>>;
|
||
|
||
// Вспомогательная функция для создания завернутого узла
|
||
fn make_node<T>(keys: Vec<T>) -> NodeLink<T> {
|
||
Rc::new(RefCell::new(Node::new(keys)))
|
||
}
|
||
|
||
fn main() {
|
||
// --- СТРОИМ ДЕРЕВО (Ручная сборка для примера) ---
|
||
|
||
// Создаем листья
|
||
let leaf1 = make_node(vec![1, 2]);
|
||
let leaf2 = make_node(vec![4, 5]);
|
||
let leaf3 = make_node(vec![7, 8]);
|
||
|
||
// Создаем корень
|
||
let root = make_node(vec![3, 6]);
|
||
|
||
// Связываем корень с детьми.
|
||
// Нам нужно "залезть" внутрь Rc через borrow_mut(), чтобы изменить вектор детей.
|
||
{
|
||
let mut root_inner = root.borrow_mut();
|
||
|
||
// Rc::clone здесь просто увеличивает счетчик ссылок.
|
||
// leaf1 теперь принадлежит и переменной leaf1, и вектору внутри root.
|
||
root_inner.children.push(Rc::clone(&leaf1));
|
||
root_inner.children.push(Rc::clone(&leaf2));
|
||
root_inner.children.push(Rc::clone(&leaf3));
|
||
}
|
||
// Тут borrow_mut заканчивается, блокировка снимается.
|
||
|
||
// --- ИСПОЛЬЗОВАНИЕ ---
|
||
|
||
println!("Root strong count: {}", Rc::strong_count(&root)); // 1
|
||
println!("Leaf1 strong count: {}", Rc::strong_count(&leaf1)); // 2 (одна у нас в main, одна внутри root)
|
||
|
||
// Поиск значения 5
|
||
if search(&root, 5) {
|
||
println!("Found 5!");
|
||
} else {
|
||
println!("Not found.");
|
||
}
|
||
}
|
||
|
||
// Пример рекурсивного поиска
|
||
fn search(node_link: &NodeLink<i32>, target: i32) -> bool {
|
||
// Берем ссылку на чтение через borrow()
|
||
let node = node_link.borrow();
|
||
|
||
// Проверяем ключи в текущем узле
|
||
for (i, &key) in node.keys.iter().enumerate() {
|
||
if key == target {
|
||
return true; // Нашли
|
||
}
|
||
if key > target {
|
||
// Если ключ больше искомого, нужно спускаться в ребенка (если он есть)
|
||
if node.children.len() > i {
|
||
return search(&node.children[i], target);
|
||
} else {
|
||
return false;
|
||
}
|
||
}
|
||
}
|
||
|
||
// Если дошли до конца ключей, проверяем последнего ребенка
|
||
if !node.children.is_empty() {
|
||
return search(node.children.last().unwrap(), target);
|
||
}
|
||
|
||
false
|
||
}
|
||
```
|
||
|
||
### Почему именно такая структура?
|
||
|
||
1. **`Rc` вместо `Box`**: В строгом дереве обычно хватает `Box` (у каждого узла строго 1 родитель). Однако `Rc` часто используют, если:
|
||
* Мы хотим реализовать курсоры, которые указывают на узлы дерева независимо от корня.
|
||
* Мы хотим реализовать персистентную структуру данных (где новые версии дерева переиспользуют неизмененные поддеревья старых версий).
|
||
|
||
2. **`RefCell`**: Без него мы не смогли бы написать `root.children.push(...)`, так как `Rc` запрещает изменение содержимого. `RefCell` переносит проверку правил заимствования с этапа компиляции на этап выполнения (runtime).
|
||
|
||
### В чем подвох `Rc` в деревьях?
|
||
Если вы добавите ссылку "назад" (от ребенка к родителю) с помощью обычного `Rc`, вы создадите **Reference Cycle** (циклическую ссылку). Счетчики ссылок никогда не станут равны нулю, и память потечет (никогда не очистится).
|
||
Для ссылок "назад" к родителю нужно использовать `Weak<T>` (слабые ссылки), которые не увеличивают *strong_count*. |