rust 如何使用Arc和Weak创建循环引用?

guykilcj  于 2023-04-30  发布在  其他
关注(0)|答案(3)|浏览(241)

我有两个struct:

struct A { 
    map: HashMap<u32, Vec<B>>,
}

struct B {
    weak: Weak<A>
}

A被构造时,它将拥有几个B,每个A都链接到刚刚构造的A,类似于这样:

let a = Arc::new(A { map: HashMap::new() });

let b1 = B { weak: Arc::downgrade(&a) };
let b3 = B { weak: Arc::downgrade(&a) };
let b2 = B { weak: Arc::downgrade(&a) };

a.map.insert(5, vec![b1, b2]);
a.map.insert(10, vec![b3]);

Playground
由于Arc不提供修改Map的方法,因此这不起作用。Arc::get_mut不起作用,因为Weak已经构造为该值。
如何用一些B构造一个A?在访问map时,我尽量避免运行时检查,因为在构建之后,它将永远不会被再次修改。我没有问题使用不安全的代码或批准的夜间功能。

r7s23pms

r7s23pms1#

如果你已经有了Weak引用,Arc::get_mut()也会失败,所以你需要考虑使用 interior mutability。由于您使用的是Arc,因此我假设您处于多线程环境中,因此我将使用线程安全的RwLock

use std::sync::{Arc, Weak, RwLock};
use std::collections::HashMap;

struct A { 
    map: RwLock<HashMap<u32, Vec<B>>>,
}

struct B {
    weak: Weak<A>
}

现在你可以像这样构造这些对象:

fn init_a(a: Arc<A>) -> Arc<A> {
    let b1 = B { weak: Arc::downgrade(&a) };
    let b2 = B { weak: Arc::downgrade(&a) };
    // extra block is required so that the Mutex's write lock is dropped 
    // before we return a
    {
        let mut map = a.map.write().unwrap();
        let vec = map.entry(0).or_insert(Vec::new());
        vec.push(b1);
        vec.push(b2);
    }
    a
}

fn main() {
    let mut a = Arc::new(A { map: RwLock::new(HashMap::new()) });
    a = init_a(a);
}

如果你真的想摆脱Mutex的所有运行时开销,并且你不介意使用unsafe代码,你可以使用UnsafeCell。它的开销为零,但它的接口需要一个unsafe块,这是代码中额外的一层解包。另外,UnsafeCell不是Sync,因此无法在线程之间共享它。
为了解决这些问题,通过确保在构建过程中只需要考虑UnsafeCell,您可以利用UnsafeCell具有零大小成本并且不影响布局的事实。代替A,使用不同的类型进行构造,除了UnsafeCell之外,它与A相同。这些类型可以与mem::transmute互换使用。

use std::collections::HashMap;
use std::sync::{Arc, Weak};
use std::cell::UnsafeCell;
use std::mem;

struct A { 
    map: HashMap<u32, Vec<B>>,
}

struct B {
    weak: Weak<A>
}

impl A {
    fn new() -> Arc<A> {
        let a = A { map: HashMap:: new() };
        Self::init_a(Arc::new(a))
    }

    fn init_a(a: Arc<A>) -> Arc<A> {
        // Important: The layout is identical to A
        struct AConstruct {
            map: UnsafeCell<HashMap<u32, Vec<B>>>,
        }
        // Treat the object as if was an AConstruct instead
        let a: Arc<AConstruct> = unsafe { mem::transmute(a) };
        let map = unsafe { &mut *a.map.get() };
        // B's weak references are to Arc<A> not to Arc<AConstruct> 
        let weak_a: Weak<A> = unsafe { mem::transmute(Arc::downgrade(&a)) };

        // Actual initialization here
        let vec = map.entry(0).or_insert(Vec::new());
        let b1 = B { weak: weak_a.clone() };
        let b2 = B { weak: weak_a.clone() };
        vec.push(b1);
        vec.push(b2);

        // We're done. Pretend the UnsafeCells never existed
        unsafe { mem::transmute(a) }
    }
}

你也可以使用原始指针来实现这一点,但我觉得使用UnsafeCell会更“安全”一点!LLVM在保证某些数据不可变时会做一些优化,而UnsafeCell在违反这些保证时会做一些魔法来保护您。所以我不能100%确定这样做的安全性:

fn init_a(a: Arc<A>) -> Arc<A> {
    // Raw IMMUTABLE pointer to the HashMap 
    let ptr = &a.map as *const HashMap<_, _>;
    // Unsafely coerce it to MUTABLE
    let map: &mut HashMap<_, _> = unsafe { mem::transmute(ptr) };
    let weak_a: Weak<A> = Arc::downgrade(&a);

    // Actual initialization here
    let vec = map.entry(0).or_insert(Vec::new());
    let b1 = B { weak: weak_a.clone() };
    let b2 = B { weak: weak_a.clone() };
    vec.push(b1);
    vec.push(b2);

    a
}
6qfn3psc

6qfn3psc2#

实际上,我会从相反的方向来处理。
HashMap是一个比Weak<T: Sized>复杂得多的类型,因此事后交换Weak要容易得多。因此,我的方法是:
1.使用虚拟引用创建B
1.创建A,转移B的所有权。
1.迭代B,将A替换为真实的的A
AFAIK,标准库不提供任何方法来(1)创建null Weak和(2)原子交换它们。Crossbeam有一个ArcCell的例子:只需搜索/替换所有Arc就可以得到一个WeakCell
我们可以使用WeakCell<T>

#[derive(Default)]
struct A { 
    map: HashMap<u32, Vec<B>>,
}

struct B {
    weak: WeakCell<A>,
}

impl A {
    pub fn new(map: HashMap<u32, Vec<B>>) -> Arc<A> {
        let a = Arc::new(A { map });
        let weak = Arc::downgrade(&a);
        for (_, bs) in &a.map {
            for b in bs {
                b.weak.set(weak.clone());
            }
        }
        a
    }
}

impl B {
    pub fn new(a: &Arc<A>) -> B { B { weak: WeakCell::new(Arc::downgrade(a)), } }
}

fn main() {
    let dummy = Arc::new(A::default());

    let (b1, b2, b3) = (B::new(&dummy), B::new(&dummy), B::new(&dummy));

    let mut map = HashMap::new();
    map.insert(5, vec![b1, b2]);
    map.insert(10, vec![b3]);

    let _a = A::new(map);

    //  Do something!
}

你可以在on the playground中看到。
应该可以修改WeakCell以从0构造它(保证它稍后会被初始化),从而避免对伪引用的需要。这是留给读者的练习)

wqlqzqxt

wqlqzqxt3#

这是一个老问题,但我有类似的dillema,显然有一个比UnsafeCell更好的解决方案,如果你真的不想要互斥(像我一样)。
Rust 1.60有Arc::new_cyclic(https://doc.rust-lang.org/std/sync/struct.Arc.html#method.new_cyclic),它以闭包作为参数:

let a = Arc::new_cyclic(|weak_a| {
   let mut a = A { map: HashMap::new() };
   let b1 = B { weak: weak_a.clone() };
   let b3 = B { weak: weak_a.clone() };
   let b2 = B { weak: weak_a.clone() };

   a.map.insert(5, vec![b1, b2]);
   a.map.insert(10, vec![b3]);
   a
});

该解决方案:

  • 不需要一行unsafe
  • 不使用Mutex
  • 给你一个弧与周期
  • 但它不会导致内存泄漏,因为它使用的是Weak

相关问题