]>
Commit | Line | Data |
---|---|---|
8bb4bdeb | 1 | # Layout |
c1a9b12d SL |
2 | |
3 | First off, we need to come up with the struct layout. A Vec has three parts: | |
4 | a pointer to the allocation, the size of the allocation, and the number of | |
5 | elements that have been initialized. | |
6 | ||
7 | Naively, this means we just want this design: | |
8 | ||
9 | ```rust | |
10 | pub struct Vec<T> { | |
11 | ptr: *mut T, | |
12 | cap: usize, | |
13 | len: usize, | |
14 | } | |
15 | # fn main() {} | |
16 | ``` | |
17 | ||
18 | And indeed this would compile. Unfortunately, it would be incorrect. First, the | |
19 | compiler will give us too strict variance. So a `&Vec<&'static str>` | |
20 | couldn't be used where an `&Vec<&'a str>` was expected. More importantly, it | |
21 | will give incorrect ownership information to the drop checker, as it will | |
22 | conservatively assume we don't own any values of type `T`. See [the chapter | |
23 | on ownership and lifetimes][ownership] for all the details on variance and | |
24 | drop check. | |
25 | ||
26 | As we saw in the ownership chapter, we should use `Unique<T>` in place of | |
27 | `*mut T` when we have a raw pointer to an allocation we own. Unique is unstable, | |
28 | so we'd like to not use it if possible, though. | |
29 | ||
30 | As a recap, Unique is a wrapper around a raw pointer that declares that: | |
31 | ||
32 | * We are variant over `T` | |
33 | * We may own a value of type `T` (for drop check) | |
34 | * We are Send/Sync if `T` is Send/Sync | |
c1a9b12d SL |
35 | * Our pointer is never null (so `Option<Vec<T>>` is null-pointer-optimized) |
36 | ||
37 | We can implement all of the above requirements except for the last | |
38 | one in stable Rust: | |
39 | ||
40 | ```rust | |
41 | use std::marker::PhantomData; | |
42 | use std::ops::Deref; | |
43 | use std::mem; | |
44 | ||
45 | struct Unique<T> { | |
46 | ptr: *const T, // *const for variance | |
47 | _marker: PhantomData<T>, // For the drop checker | |
48 | } | |
49 | ||
50 | // Deriving Send and Sync is safe because we are the Unique owners | |
51 | // of this data. It's like Unique<T> is "just" T. | |
52 | unsafe impl<T: Send> Send for Unique<T> {} | |
53 | unsafe impl<T: Sync> Sync for Unique<T> {} | |
54 | ||
55 | impl<T> Unique<T> { | |
56 | pub fn new(ptr: *mut T) -> Self { | |
57 | Unique { ptr: ptr, _marker: PhantomData } | |
58 | } | |
c1a9b12d | 59 | |
7cac9316 XL |
60 | pub fn as_ptr(&self) -> *mut T { |
61 | self.ptr as *mut T | |
c1a9b12d SL |
62 | } |
63 | } | |
7cac9316 | 64 | |
c1a9b12d SL |
65 | # fn main() {} |
66 | ``` | |
67 | ||
68 | Unfortunately the mechanism for stating that your value is non-zero is | |
69 | unstable and unlikely to be stabilized soon. As such we're just going to | |
70 | take the hit and use std's Unique: | |
71 | ||
72 | ||
73 | ```rust | |
2c00a5a8 | 74 | #![feature(ptr_internals)] |
c1a9b12d SL |
75 | |
76 | use std::ptr::{Unique, self}; | |
77 | ||
78 | pub struct Vec<T> { | |
79 | ptr: Unique<T>, | |
80 | cap: usize, | |
81 | len: usize, | |
82 | } | |
83 | ||
84 | # fn main() {} | |
85 | ``` | |
86 | ||
87 | If you don't care about the null-pointer optimization, then you can use the | |
88 | stable code. However we will be designing the rest of the code around enabling | |
7cac9316 | 89 | this optimization. It should be noted that `Unique::new` is unsafe to call, because |
b039eaaf | 90 | putting `null` inside of it is Undefined Behavior. Our stable Unique doesn't |
c1a9b12d SL |
91 | need `new` to be unsafe because it doesn't make any interesting guarantees about |
92 | its contents. | |
93 | ||
94 | [ownership]: ownership.html |