cs431_homework/
arc.rs

1//! Thread-safe reference-counting pointers.
2//!
3//! See the [`Arc<T>`][Arc] documentation for more details.
4
5use std::marker::PhantomData;
6use std::ops::Deref;
7use std::ptr::NonNull;
8#[cfg(not(feature = "check-loom"))]
9use std::sync::atomic::{AtomicUsize, Ordering, fence};
10use std::{fmt, mem};
11
12#[cfg(feature = "check-loom")]
13use loom::sync::atomic::{AtomicUsize, Ordering, fence};
14
15const MAX_REFCOUNT: usize = (isize::MAX) as usize;
16
17/// A thread-safe reference-counting pointer. 'Arc' stands for 'Atomically
18/// Reference Counted'.
19///
20/// The type `Arc<T>` provides shared ownership of a value of type `T`,
21/// allocated in the heap. Invoking [`clone`][clone] on `Arc` produces
22/// a new `Arc` instance, which points to the same allocation on the heap as the
23/// source `Arc`, while increasing a reference count. When the last `Arc`
24/// pointer to a given allocation is destroyed, the value stored in that allocation (often
25/// referred to as "inner value") is also dropped.
26///
27/// Shared references in Rust disallow mutation by default, and `Arc` is no
28/// exception: you cannot generally obtain a mutable reference to something
29/// inside an `Arc`. If you need to mutate through an `Arc`, use
30/// [`Mutex`][mutex], [`RwLock`][rwlock], or one of the [`Atomic`][atomic]
31/// types.
32///
33/// ## Thread Safety
34///
35/// Unlike [`Rc<T>`], `Arc<T>` uses atomic operations for its reference
36/// counting. This means that it is thread-safe. The disadvantage is that
37/// atomic operations are more expensive than ordinary memory accesses. If you
38/// are not sharing reference-counted allocations between threads, consider using
39/// [`Rc<T>`] for lower overhead. [`Rc<T>`] is a safe default, because the
40/// compiler will catch any attempt to send an [`Rc<T>`] between threads.
41/// However, a library might choose `Arc<T>` in order to give library consumers
42/// more flexibility.
43///
44/// `Arc<T>` will implement [`Send`] and [`Sync`] as long as the `T` implements
45/// [`Send`] and [`Sync`]. Why can't you put a non-thread-safe type `T` in an
46/// `Arc<T>` to make it thread-safe? This may be a bit counter-intuitive at
47/// first: after all, isn't the point of `Arc<T>` thread safety? The key is
48/// this: `Arc<T>` makes it thread safe to have multiple ownership of the same
49/// data, but it  doesn't add thread safety to its data. Consider
50/// <code>Arc<[RefCell\<T>]></code>. [`RefCell<T>`] isn't [`Sync`], and if `Arc<T>` was always
51/// [`Send`], <code>Arc<[RefCell\<T>]></code> would be as well. But then we'd have a problem:
52/// [`RefCell<T>`] is not thread safe; it keeps track of the borrowing count using
53/// non-atomic operations.
54///
55/// In the end, this means that you may need to pair `Arc<T>` with some sort of
56/// [`std::sync`] type, usually [`Mutex<T>`][mutex].
57///
58/// # Cloning references
59///
60/// Creating a new reference from an existing reference-counted pointer is done using the
61/// `Clone` trait implemented for [`Arc<T>`][Arc].
62///
63/// ```
64/// use cs431_homework::Arc;
65/// let foo = Arc::new(vec![1.0, 2.0, 3.0]);
66/// // The two syntaxes below are equivalent.
67/// let a = foo.clone();
68/// let b = Arc::clone(&foo);
69/// // a, b, and foo are all Arcs that point to the same memory location
70/// ```
71///
72/// ## `Deref` behavior
73///
74/// `Arc<T>` automatically dereferences to `T` (via the [`Deref`] trait),
75/// so you can call `T`'s methods on a value of type `Arc<T>`. To avoid name
76/// clashes with `T`'s methods, the methods of `Arc<T>` itself are associated
77/// functions, called using [fully qualified syntax]:
78///
79/// ```
80/// use cs431_homework::Arc;
81///
82/// let my_arc = Arc::new(5);
83/// let my_five = Arc::try_unwrap(my_arc).unwrap();
84/// ```
85///
86/// `Arc<T>`'s implementations of traits like `Clone` may also be called using
87/// fully qualified syntax. Some people prefer to use fully qualified syntax,
88/// while others prefer using method-call syntax.
89///
90/// ```
91/// use cs431_homework::Arc;
92///
93/// let arc = Arc::new(());
94/// // Method-call syntax
95/// let arc2 = arc.clone();
96/// // Fully qualified syntax
97/// let arc3 = Arc::clone(&arc);
98/// ```
99///
100/// [`Rc<T>`]: std::rc::Rc
101/// [clone]: Clone::clone
102/// [mutex]: ../../std/sync/struct.Mutex.html
103/// [rwlock]: ../../std/sync/struct.RwLock.html
104/// [atomic]: core::sync::atomic
105/// [RefCell\<T>]: core::cell::RefCell
106/// [`RefCell<T>`]: core::cell::RefCell
107/// [`std::sync`]: ../../std/sync/index.html
108/// [`Arc::clone(&from)`]: Arc::clone
109/// [fully qualified syntax]: https://doc.rust-lang.org/book/ch19-03-advanced-traits.html#fully-qualified-syntax-for-disambiguation-calling-methods-with-the-same-name
110///
111/// # Examples
112///
113/// Sharing some immutable data between threads:
114///
115/// ```no_run
116/// use cs431_homework::Arc;
117/// use std::thread;
118///
119/// let five = Arc::new(5);
120///
121/// for _ in 0..10 {
122///     let five = Arc::clone(&five);
123///
124///     thread::spawn(move || {
125///         println!("{five:?}");
126///     });
127/// }
128/// ```
129///
130/// Sharing a mutable [`AtomicUsize`]:
131///
132/// [`AtomicUsize`]: core::sync::atomic::AtomicUsize "sync::atomic::AtomicUsize"
133///
134/// ```no_run
135/// use cs431_homework::Arc;
136/// use std::sync::atomic::{AtomicUsize, Ordering};
137/// use std::thread;
138///
139/// let val = Arc::new(AtomicUsize::new(5));
140///
141/// for _ in 0..10 {
142///     let val = Arc::clone(&val);
143///
144///     thread::spawn(move || {
145///         let v = val.fetch_add(1, Ordering::SeqCst);
146///         println!("{v:?}");
147///     });
148/// }
149/// ```
150///
151/// See the [`rc` documentation][rc_examples] for more examples of reference
152/// counting in general.
153///
154/// [rc_examples]: std::rc#examples
155pub struct Arc<T> {
156    ptr: NonNull<ArcInner<T>>,
157    phantom: PhantomData<ArcInner<T>>,
158}
159
160unsafe impl<T: Sync + Send> Send for Arc<T> {}
161unsafe impl<T: Sync + Send> Sync for Arc<T> {}
162
163impl<T> Arc<T> {
164    fn from_inner(ptr: NonNull<ArcInner<T>>) -> Self {
165        Self {
166            ptr,
167            phantom: PhantomData,
168        }
169    }
170}
171
172struct ArcInner<T> {
173    count: AtomicUsize,
174    data: T,
175}
176
177unsafe impl<T: Sync + Send> Send for ArcInner<T> {}
178unsafe impl<T: Sync + Send> Sync for ArcInner<T> {}
179
180impl<T> Arc<T> {
181    /// Constructs a new `Arc<T>`.
182    #[inline]
183    pub fn new(data: T) -> Arc<T> {
184        let x = Box::new(ArcInner {
185            count: AtomicUsize::new(1),
186            data,
187        });
188        Self::from_inner(Box::leak(x).into())
189    }
190
191    /// Returns a mutable reference into the given `Arc` if there are
192    /// no other `Arc`. Otherwise, return `None`.
193    ///
194    /// # Examples
195    ///
196    /// ```
197    /// use cs431_homework::Arc;
198    ///
199    /// let mut x = Arc::new(3);
200    /// *Arc::get_mut(&mut x).unwrap() = 4;
201    /// assert_eq!(*x, 4);
202    ///
203    /// let y = Arc::clone(&x);
204    /// assert!(Arc::get_mut(&mut x).is_none());
205    ///
206    /// drop(y);
207    /// assert!(Arc::get_mut(&mut x).is_some());
208    /// ```
209    #[inline]
210    pub fn get_mut(this: &mut Self) -> Option<&mut T> {
211        todo!()
212    }
213
214    // Used in `get_mut` and `make_mut` to check if the given `Arc` is the unique reference to the
215    // underlying data.
216    #[inline]
217    fn is_unique(&mut self) -> bool {
218        todo!()
219    }
220
221    /// Returns a mutable reference into the given `Arc` without any check.
222    ///
223    /// # Safety
224    ///
225    /// Any other `Arc` to the same allocation must not be dereferenced for the duration of the
226    /// returned borrow.  Specifically, call to this function must happen-after destruction of all
227    /// the other `Arc` to the same allocation.
228    ///
229    /// # Examples
230    ///
231    /// ```
232    /// use cs431_homework::Arc;
233    ///
234    /// let mut x = Arc::new(String::new());
235    /// unsafe {
236    ///     Arc::get_mut_unchecked(&mut x).push_str("foo")
237    /// }
238    /// assert_eq!(*x, "foo");
239    /// ```
240    pub unsafe fn get_mut_unchecked(this: &mut Self) -> &mut T {
241        // We are careful to *not* create a reference covering the "count" fields, as
242        // this would alias with concurrent access to the reference counts (e.g. by `Weak`).
243        unsafe { &mut (*this.ptr.as_ptr()).data }
244    }
245
246    /// Gets the number of `Arc`s to this allocation. In addition, synchronize with the update that
247    /// this function reads from.
248    ///
249    /// # Safety
250    ///
251    /// This method by itself is safe, but using it correctly requires extra care.
252    /// Another thread can change the reference count at any time,
253    /// including potentially between calling this method and acting on the result.
254    ///
255    /// # Examples
256    ///
257    /// ```
258    /// use cs431_homework::Arc;
259    ///
260    /// let five = Arc::new(5);
261    /// let _also_five = Arc::clone(&five);
262    ///
263    /// // This assertion is deterministic because we haven't shared
264    /// // the `Arc` between threads.
265    /// assert_eq!(2, Arc::count(&five));
266    /// ```
267    #[inline]
268    pub fn count(this: &Self) -> usize {
269        todo!()
270    }
271
272    #[inline]
273    fn inner(&self) -> &ArcInner<T> {
274        // This unsafety is ok because while this arc is alive we're guaranteed
275        // that the inner pointer is valid. Furthermore, we know that the
276        // `ArcInner` structure itself is `Sync` because the inner data is
277        // `Sync` as well, so we're ok loaning out an immutable pointer to these
278        // contents.
279        unsafe { self.ptr.as_ref() }
280    }
281
282    /// Returns `true` if the two `Arc`s point to the same allocation
283    /// (in a vein similar to `ptr::eq`).
284    ///
285    /// # Examples
286    ///
287    /// ```
288    /// use cs431_homework::Arc;
289    ///
290    /// let five = Arc::new(5);
291    /// let same_five = Arc::clone(&five);
292    /// let other_five = Arc::new(5);
293    ///
294    /// assert!(Arc::ptr_eq(&five, &same_five));
295    /// assert!(!Arc::ptr_eq(&five, &other_five));
296    /// ```
297    #[inline]
298    pub fn ptr_eq(this: &Self, other: &Self) -> bool {
299        this.ptr.as_ptr() == other.ptr.as_ptr()
300    }
301
302    /// Returns the inner value, if the given `Arc` is unique.
303    ///
304    /// Otherwise, an `Err` is returned with the same `Arc` that was passed in.
305    ///
306    /// # Examples
307    ///
308    /// ```
309    /// use cs431_homework::Arc;
310    ///
311    /// let x = Arc::new(3);
312    /// assert_eq!(Arc::try_unwrap(x).unwrap(), 3);
313    ///
314    /// let x = Arc::new(4);
315    /// let _y = Arc::clone(&x);
316    /// assert_eq!(*Arc::try_unwrap(x).unwrap_err(), 4);
317    /// ```
318    #[inline]
319    pub fn try_unwrap(this: Self) -> Result<T, Self> {
320        todo!()
321    }
322}
323
324impl<T: Clone> Arc<T> {
325    /// Makes a mutable reference into the given `Arc`.
326    ///
327    /// If there are other `Arc` to the same allocation, then `make_mut` will create a new
328    /// allocation and invoke `clone` on the inner value to ensure unique ownership. This is also
329    /// referred to as clone-on-write.
330    ///
331    /// See also `get_mut`, which will fail rather than cloning.
332    ///
333    /// # Examples
334    ///
335    /// ```
336    /// use cs431_homework::Arc;
337    ///
338    /// let mut data = Arc::new(5);
339    ///
340    /// *Arc::make_mut(&mut data) += 1;         // Won't clone anything
341    /// let mut other_data = Arc::clone(&data); // Won't clone inner data
342    /// *Arc::make_mut(&mut data) += 1;         // Clones inner data
343    /// *Arc::make_mut(&mut data) += 1;         // Won't clone anything
344    /// *Arc::make_mut(&mut other_data) *= 2;   // Won't clone anything
345    ///
346    /// // Now `data` and `other_data` point to different allocations.
347    /// assert_eq!(*data, 8);
348    /// assert_eq!(*other_data, 12);
349    /// ```
350    #[inline]
351    pub fn make_mut(this: &mut Self) -> &mut T {
352        todo!()
353    }
354}
355
356impl<T> Clone for Arc<T> {
357    /// Makes a clone of the `Arc` pointer.
358    ///
359    /// This creates another pointer to the same allocation, increasing the
360    /// reference count.
361    ///
362    /// # Panics
363    ///
364    /// This panics if the number of `Arc`s is larger than `isize::Max`.
365    ///
366    /// # Examples
367    ///
368    /// ```
369    /// use cs431_homework::Arc;
370    ///
371    /// let five = Arc::new(5);
372    ///
373    /// let _ = Arc::clone(&five);
374    /// ```
375    #[inline]
376    fn clone(&self) -> Arc<T> {
377        todo!()
378    }
379}
380
381impl<T> Deref for Arc<T> {
382    type Target = T;
383
384    #[inline]
385    fn deref(&self) -> &T {
386        &self.inner().data
387    }
388}
389
390impl<T> Drop for Arc<T> {
391    /// Drops the `Arc`.
392    ///
393    /// This will decrement the reference count. If the reference
394    /// count reaches zero, we `drop` the inner value.
395    ///
396    /// # Examples
397    ///
398    /// ```
399    /// use cs431_homework::Arc;
400    ///
401    /// struct Foo;
402    ///
403    /// impl Drop for Foo {
404    ///     fn drop(&mut self) {
405    ///         println!("dropped!");
406    ///     }
407    /// }
408    ///
409    /// let foo  = Arc::new(Foo);
410    /// let foo2 = Arc::clone(&foo);
411    ///
412    /// drop(foo);    // Doesn't print anything
413    /// drop(foo2);   // Prints "dropped!"
414    /// ```
415    fn drop(&mut self) {
416        todo!()
417    }
418}
419
420impl<T: fmt::Display> fmt::Display for Arc<T> {
421    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
422        fmt::Display::fmt(&**self, f)
423    }
424}
425
426impl<T: fmt::Debug> fmt::Debug for Arc<T> {
427    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
428        fmt::Debug::fmt(&**self, f)
429    }
430}
431
432impl<T> fmt::Pointer for Arc<T> {
433    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
434        fmt::Pointer::fmt(&(&**self), f)
435    }
436}
cs431_homework/arc.rs

cs431_homework/
arc.rs
