214 lines
13 KiB
HTML
214 lines
13 KiB
HTML
<!DOCTYPE html>
|
||
<html lang="en">
|
||
<head>
|
||
<meta charset="UTF-8">
|
||
<title>Rc<T>, the Reference Counted Smart Pointer</title>
|
||
</head>
|
||
<body>
|
||
<h2 id="rct-the-reference-counted-smart-pointer"><a class="header" href="#rct-the-reference-counted-smart-pointer"><code>Rc<T></code>, the Reference-Counted Smart Pointer</a></h2>
|
||
<p>In the majority of cases, ownership is clear: You know exactly which variable
|
||
owns a given value. However, there are cases when a single value might have
|
||
multiple owners. For example, in graph data structures, multiple edges might
|
||
point to the same node, and that node is conceptually owned by all of the edges
|
||
that point to it. A node shouldn’t be cleaned up unless it doesn’t have any
|
||
edges pointing to it and so has no owners.</p>
|
||
<p>You have to enable multiple ownership explicitly by using the Rust type
|
||
<code>Rc<T></code>, which is an abbreviation for <em>reference counting</em>. The <code>Rc<T></code> type
|
||
keeps track of the number of references to a value to determine whether or not
|
||
the value is still in use. If there are zero references to a value, the value
|
||
can be cleaned up without any references becoming invalid.</p>
|
||
<p>Imagine <code>Rc<T></code> as a TV in a family room. When one person enters to watch TV,
|
||
they turn it on. Others can come into the room and watch the TV. When the last
|
||
person leaves the room, they turn off the TV because it’s no longer being used.
|
||
If someone turns off the TV while others are still watching it, there would be
|
||
an uproar from the remaining TV watchers!</p>
|
||
<p>We use the <code>Rc<T></code> type when we want to allocate some data on the heap for
|
||
multiple parts of our program to read and we can’t determine at compile time
|
||
which part will finish using the data last. If we knew which part would finish
|
||
last, we could just make that part the data’s owner, and the normal ownership
|
||
rules enforced at compile time would take effect.</p>
|
||
<p>Note that <code>Rc<T></code> is only for use in single-threaded scenarios. When we discuss
|
||
concurrency in Chapter 16, we’ll cover how to do reference counting in
|
||
multithreaded programs.</p>
|
||
<!-- Old headings. Do not remove or links may break. -->
|
||
<p><a id="using-rct-to-share-data"></a></p>
|
||
<h3 id="sharing-data"><a class="header" href="#sharing-data">Sharing Data</a></h3>
|
||
<p>Let’s return to our cons list example in Listing 15-5. Recall that we defined
|
||
it using <code>Box<T></code>. This time, we’ll create two lists that both share ownership
|
||
of a third list. Conceptually, this looks similar to Figure 15-3.</p>
|
||
<p><img alt="A linked list with the label 'a' pointing to three elements. The first element contains the integer 5 and points to the second element. Th
|
||
e second element contains the integer 10 and points to the third element. The third element contains the value 'Nil' that signifies the end of the l
|
||
ist; it does not point anywhere. A linked list with the label 'b' points to an element that contains the integer 3 and points to the first element o
|
||
f list 'a'. A linked list with the label 'c' points to an element that contains the integer 4 and also points to the first element of list 'a' so th
|
||
at the tails of lists 'b' and 'c' are both list 'a'." src="../img/trpl15-03.svg" class="center" /></p>
|
||
<p><span class="caption">Figure 15-3: Two lists, <code>b</code> and <code>c</code>, sharing ownership of
|
||
a third list, <code>a</code></span></p>
|
||
<p>We’ll create list <code>a</code> that contains <code>5</code> and then <code>10</code>. Then, we’ll make two
|
||
more lists: <code>b</code> that starts with <code>3</code> and <code>c</code> that starts with <code>4</code>. Both the <code>b</code>
|
||
and <code>c</code> lists will then continue on to the first <code>a</code> list containing <code>5</code> and
|
||
<code>10</code>. In other words, both lists will share the first list containing <code>5</code> and
|
||
<code>10</code>.</p>
|
||
<p>Trying to implement this scenario using our definition of <code>List</code> with <code>Box<T></code>
|
||
won’t work, as shown in Listing 15-17.</p>
|
||
<figure class="listing" id="listing-15-17">
|
||
<span class="file-name">Filename: src/main.rs</span>
|
||
<pre><code class="language-rust ignore does_not_compile">enum List {
|
||
Cons(i32, Box<List>),
|
||
Nil,
|
||
}
|
||
|
||
use crate::List::{Cons, Nil};
|
||
|
||
fn main() {
|
||
let a = Cons(5, Box::new(Cons(10, Box::new(Nil))));
|
||
let b = Cons(3, Box::new(a));
|
||
let c = Cons(4, Box::new(a));
|
||
}</code></pre>
|
||
<figcaption><a href="#listing-15-17">Listing 15-17</a>: Demonstrating that we’re not allowed to have two lists using <code>Box<T></code> that try to share ownership of a third list</figcaption>
|
||
</figure>
|
||
<p>When we compile this code, we get this error:</p>
|
||
<pre><code class="language-console">$ cargo run
|
||
Compiling cons-list v0.1.0 (file:///projects/cons-list)
|
||
error[E0382]: use of moved value: `a`
|
||
--> src/main.rs:11:30
|
||
|
|
||
9 | let a = Cons(5, Box::new(Cons(10, Box::new(Nil))));
|
||
| - move occurs because `a` has type `List`, which does not implement the `Copy` trait
|
||
10 | let b = Cons(3, Box::new(a));
|
||
| - value moved here
|
||
11 | let c = Cons(4, Box::new(a));
|
||
| ^ value used here after move
|
||
|
|
||
note: if `List` implemented `Clone`, you could clone the value
|
||
--> src/main.rs:1:1
|
||
|
|
||
1 | enum List {
|
||
| ^^^^^^^^^ consider implementing `Clone` for this type
|
||
...
|
||
10 | let b = Cons(3, Box::new(a));
|
||
| - you could clone this value
|
||
|
||
For more information about this error, try `rustc --explain E0382`.
|
||
error: could not compile `cons-list` (bin "cons-list") due to 1 previous error
|
||
</code></pre>
|
||
<p>The <code>Cons</code> variants own the data they hold, so when we create the <code>b</code> list, <code>a</code>
|
||
is moved into <code>b</code> and <code>b</code> owns <code>a</code>. Then, when we try to use <code>a</code> again when
|
||
creating <code>c</code>, we’re not allowed to because <code>a</code> has been moved.</p>
|
||
<p>We could change the definition of <code>Cons</code> to hold references instead, but then
|
||
we would have to specify lifetime parameters. By specifying lifetime
|
||
parameters, we would be specifying that every element in the list will live at
|
||
least as long as the entire list. This is the case for the elements and lists
|
||
in Listing 15-17, but not in every scenario.</p>
|
||
<p>Instead, we’ll change our definition of <code>List</code> to use <code>Rc<T></code> in place of
|
||
<code>Box<T></code>, as shown in Listing 15-18. Each <code>Cons</code> variant will now hold a value
|
||
and an <code>Rc<T></code> pointing to a <code>List</code>. When we create <code>b</code>, instead of taking
|
||
ownership of <code>a</code>, we’ll clone the <code>Rc<List></code> that <code>a</code> is holding, thereby
|
||
increasing the number of references from one to two and letting <code>a</code> and <code>b</code>
|
||
share ownership of the data in that <code>Rc<List></code>. We’ll also clone <code>a</code> when
|
||
creating <code>c</code>, increasing the number of references from two to three. Every time
|
||
we call <code>Rc::clone</code>, the reference count to the data within the <code>Rc<List></code> will
|
||
increase, and the data won’t be cleaned up unless there are zero references to
|
||
it.</p>
|
||
<figure class="listing" id="listing-15-18">
|
||
<span class="file-name">Filename: src/main.rs</span>
|
||
<pre class="playground"><code class="language-rust edition2024">enum List {
|
||
Cons(i32, Rc<List>),
|
||
Nil,
|
||
}
|
||
|
||
use crate::List::{Cons, Nil};
|
||
use std::rc::Rc;
|
||
|
||
fn main() {
|
||
let a = Rc::new(Cons(5, Rc::new(Cons(10, Rc::new(Nil)))));
|
||
let b = Cons(3, Rc::clone(&a));
|
||
let c = Cons(4, Rc::clone(&a));
|
||
}</code></pre>
|
||
<figcaption><a href="#listing-15-18">Listing 15-18</a>: A definition of <code>List</code> that uses <code>Rc<T></code></figcaption>
|
||
</figure>
|
||
<p>We need to add a <code>use</code> statement to bring <code>Rc<T></code> into scope because it’s not
|
||
in the prelude. In <code>main</code>, we create the list holding <code>5</code> and <code>10</code> and store it
|
||
in a new <code>Rc<List></code> in <code>a</code>. Then, when we create <code>b</code> and <code>c</code>, we call the
|
||
<code>Rc::clone</code> function and pass a reference to the <code>Rc<List></code> in <code>a</code> as an
|
||
argument.</p>
|
||
<p>We could have called <code>a.clone()</code> rather than <code>Rc::clone(&a)</code>, but Rust’s
|
||
convention is to use <code>Rc::clone</code> in this case. The implementation of
|
||
<code>Rc::clone</code> doesn’t make a deep copy of all the data like most types’
|
||
implementations of <code>clone</code> do. The call to <code>Rc::clone</code> only increments the
|
||
reference count, which doesn’t take much time. Deep copies of data can take a
|
||
lot of time. By using <code>Rc::clone</code> for reference counting, we can visually
|
||
distinguish between the deep-copy kinds of clones and the kinds of clones that
|
||
increase the reference count. When looking for performance problems in the
|
||
code, we only need to consider the deep-copy clones and can disregard calls to
|
||
<code>Rc::clone</code>.</p>
|
||
<!-- Old headings. Do not remove or links may break. -->
|
||
<p><a id="cloning-an-rct-increases-the-reference-count"></a></p>
|
||
<h3 id="cloning-to-increase-the-reference-count"><a class="header" href="#cloning-to-increase-the-reference-count">Cloning to Increase the Reference Count</a></h3>
|
||
<p>Let’s change our working example in Listing 15-18 so that we can see the
|
||
reference counts changing as we create and drop references to the <code>Rc<List></code> in
|
||
<code>a</code>.</p>
|
||
<p>In Listing 15-19, we’ll change <code>main</code> so that it has an inner scope around list
|
||
<code>c</code>; then, we can see how the reference count changes when <code>c</code> goes out of
|
||
scope.</p>
|
||
<figure class="listing" id="listing-15-19">
|
||
<span class="file-name">Filename: src/main.rs</span>
|
||
<pre class="playground"><code class="language-rust edition2024"><span class="boring">enum List {
|
||
</span><span class="boring"> Cons(i32, Rc<List>),
|
||
</span><span class="boring"> Nil,
|
||
</span><span class="boring">}
|
||
</span><span class="boring">
|
||
</span><span class="boring">use crate::List::{Cons, Nil};
|
||
</span><span class="boring">use std::rc::Rc;
|
||
</span><span class="boring">
|
||
</span>// --snip--
|
||
|
||
fn main() {
|
||
let a = Rc::new(Cons(5, Rc::new(Cons(10, Rc::new(Nil)))));
|
||
println!("count after creating a = {}", Rc::strong_count(&a));
|
||
let b = Cons(3, Rc::clone(&a));
|
||
println!("count after creating b = {}", Rc::strong_count(&a));
|
||
{
|
||
let c = Cons(4, Rc::clone(&a));
|
||
println!("count after creating c = {}", Rc::strong_count(&a));
|
||
}
|
||
println!("count after c goes out of scope = {}", Rc::strong_count(&a));
|
||
}</code></pre>
|
||
<figcaption><a href="#listing-15-19">Listing 15-19</a>: Printing the reference count</figcaption>
|
||
</figure>
|
||
<p>At each point in the program where the reference count changes, we print the
|
||
reference count, which we get by calling the <code>Rc::strong_count</code> function. This
|
||
function is named <code>strong_count</code> rather than <code>count</code> because the <code>Rc<T></code> type
|
||
also has a <code>weak_count</code>; we’ll see what <code>weak_count</code> is used for in <a href="ch15-06-reference-cycles.html#preventing-reference-cycles-turning-an-rct-into-a-weakt">“Preventing
|
||
Reference Cycles Using <code>Weak<T></code>”</a><!-- ignore -->.</p>
|
||
<p>This code prints the following:</p>
|
||
<pre><code class="language-console">$ cargo run
|
||
Compiling cons-list v0.1.0 (file:///projects/cons-list)
|
||
Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.45s
|
||
Running `target/debug/cons-list`
|
||
count after creating a = 1
|
||
count after creating b = 2
|
||
count after creating c = 3
|
||
count after c goes out of scope = 2
|
||
</code></pre>
|
||
<p>We can see that the <code>Rc<List></code> in <code>a</code> has an initial reference count of 1;
|
||
then, each time we call <code>clone</code>, the count goes up by 1. When <code>c</code> goes out of
|
||
scope, the count goes down by 1. We don’t have to call a function to decrease
|
||
the reference count like we have to call <code>Rc::clone</code> to increase the reference
|
||
count: The implementation of the <code>Drop</code> trait decreases the reference count
|
||
automatically when an <code>Rc<T></code> value goes out of scope.</p>
|
||
<p>What we can’t see in this example is that when <code>b</code> and then <code>a</code> go out of scope
|
||
at the end of <code>main</code>, the count is 0, and the <code>Rc<List></code> is cleaned up
|
||
completely. Using <code>Rc<T></code> allows a single value to have multiple owners, and
|
||
the count ensures that the value remains valid as long as any of the owners
|
||
still exist.</p>
|
||
<p>Via immutable references, <code>Rc<T></code> allows you to share data between multiple
|
||
parts of your program for reading only. If <code>Rc<T></code> allowed you to have multiple
|
||
mutable references too, you might violate one of the borrowing rules discussed
|
||
in Chapter 4: Multiple mutable borrows to the same place can cause data races
|
||
and inconsistencies. But being able to mutate data is very useful! In the next
|
||
section, we’ll discuss the interior mutability pattern and the <code>RefCell<T></code>
|
||
type that you can use in conjunction with an <code>Rc<T></code> to work with this
|
||
immutability restriction.</p>
|
||
</body>
|
||
</html>
|