Implement Arc in Rust

This challenge involves creating a thread-safe reference-counting pointer, commonly known as Arc (Atomically Reference Counted), in Rust. Arc is crucial for sharing data across multiple threads safely by managing ownership through atomic reference counting. This exercise will deepen your understanding of Rust's ownership, concurrency, and atomic operations.

Problem Description

Your task is to implement a simplified version of std::sync::Arc<T> in Rust. This implementation should allow multiple owners of a value of type T to exist simultaneously and ensure that the value is deallocated only when the last owner is dropped. The key requirement is thread-safety, meaning that multiple threads can safely access and modify the reference count.

Key Requirements:

1. Shared Ownership: The Arc<T> type should allow multiple references to the same data.
2. Reference Counting: It must track the number of active references to the data.
3. Thread-Safety: Reference count updates (incrementing and decrementing) must be atomic to prevent data races in concurrent environments.
4. Deallocation: The inner data T should be deallocated when the last Arc<T> pointing to it goes out of scope.
5. Cloneability: Cloning an Arc<T> should increase the reference count and return a new Arc pointing to the same data.
6. Dereferencing: It should be possible to access the inner data T through dereferencing (*).

Expected Behavior:

• Creating an Arc<T> should initialize the reference count to 1.
• Cloning an Arc<T> should atomically increment the count.
• Dropping an Arc<T> should atomically decrement the count. If the count reaches zero, the inner data should be deallocated.
• The type T must be Send and Sync to be safely shared across threads. Your Arc implementation should reflect this.

Edge Cases:

• Handling the deallocation when the count drops to zero.
• Ensuring atomic operations are used correctly for thread-safety.

Examples

Example 1: Basic Usage

// Assume we have a struct `MyData`
struct MyData {
    value: i32,
}

impl Drop for MyData {
    fn drop(&mut self) {
        println!("MyData with value {} is being dropped.", self.value);
    }
}

let data = MyData { value: 42 };
let arc1 = Arc::new(data); // Reference count: 1

{
    let arc2 = Arc::clone(&arc1); // Reference count: 2
    println!("Value from arc2: {}", arc2.value);
} // arc2 is dropped, reference count becomes 1

println!("Value from arc1: {}", arc1.value);
// arc1 is dropped here, reference count becomes 0, MyData is dropped.

Output:

Value from arc2: 42
MyData with value 42 is being dropped.
Value from arc1: 42

Explanation: arc1 initially holds MyData. arc2 is created by cloning arc1, increasing the reference count. When arc2 goes out of scope, its reference is dropped, reducing the count. Finally, when arc1 goes out of scope, the count becomes zero, triggering the drop implementation for MyData.

Example 2: Threaded Usage

use std::thread;

let data = Arc::new(vec![1, 2, 3]);
let mut handles = vec![];

for i in 0..3 {
    let data_clone = Arc::clone(&data); // Clone for each thread
    let handle = thread::spawn(move || {
        println!("Thread {}: Vector length = {}", i, data_clone.len());
    });
    handles.push(handle);
}

for handle in handles {
    handle.join().unwrap();
}
// `data` is dropped here. If the threads are still running and holding clones,
// MyData will not be dropped until the last thread finishes.

Output: (Order of thread output may vary)

Thread 0: Vector length = 3
Thread 1: Vector length = 3
Thread 2: Vector length = 3

Explanation: Multiple threads are created, each receiving a clone of the Arc. This demonstrates how Arc allows sharing data safely across threads. The vec! will only be deallocated after all threads have finished and dropped their respective Arc clones.

Constraints

• The internal reference count must be an unsigned integer type capable of holding large values (e.g., usize or u64).
• All operations modifying the reference count must use atomic primitives from std::sync::atomic.
• The inner type T must satisfy the Send and Sync traits.
• Your implementation should aim for performance comparable to std::sync::Arc, meaning minimal overhead.
• Do not use std::sync::Arc or std::sync::Mutex (or other locking primitives) in your implementation of Arc itself. You may use them in test cases.

Notes

• You'll need to manage the allocation of the inner data T and the reference count. Consider using a Box (Box<T>) for the data and potentially a Box for the control block containing the count and the data.
• The Drop trait will be crucial for decrementing the reference count and deallocating the data when the last reference is gone.
• Pay close attention to the memory layout and how you store the reference count and the data. A common pattern is to store them together in a "control block."
• The Clone trait implementation for your Arc type should handle the atomic increment.
• The Deref trait implementation should allow access to the inner data T.
• Consider the use of std::ptr::NonNull for managing the pointer to the control block to avoid null pointer issues and optimize for non-null cases.
• You'll need to use std::sync::atomic::AtomicUsize or std::sync::atomic::AtomicU64 for the reference count.
• When the reference count reaches zero, you'll need to deallocate the data and the control block itself. Box::from_raw and unsafe blocks will likely be involved here.
• Your Arc<T> should enforce that T: Send + Sync. This can be done with trait bounds.