Как создать циклическую ссылку с Arc и Weak? - PullRequest
0 голосов
/ 19 мая 2018

У меня есть две структуры:

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

struct B {
    weak: Weak<A>
}

Когда построено A, ему будет принадлежать несколько B, каждая из которых связана с только что построенным 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]);

Детская площадка

Это не работает, поскольку Arc не позволяет изменять карту.Arc::get_mut не работает, поскольку Weak уже сконструировано для значения.

Как можно построить A с некоторыми B?Я пытаюсь избежать проверок во время выполнения при доступе к map, потому что после создания он никогда не будет изменен снова.У меня нет проблем с использованием небезопасного кода или проверенных ночных функций.

Ответы [ 2 ]

0 голосов
/ 19 мая 2018

Я бы подошел к этому с противоположной стороны, на самом деле.

HashMap гораздо более сложный тип, чем Weak<T: Sized>, и поэтому намного проще поменять Weak на факт.Поэтому мой подход будет следующим:

  1. Создать B с фиктивной ссылкой.
  2. Создать A, передать владение B.
  3. Итерируйте по B, заменяя A на действительное.

AFAIK, стандартная библиотека не предоставляет никакого способа (1) создать ноль Weak и (2) атомно поменять их местами.У Crossbeam есть пример ArcCell: просто поиск / замена всех Arc на Weak дает нам 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!
}

Что вы можете увидеть в действии на игровой площадке .

Должна быть возможность изменить WeakCell, чтобы построить его из 0 (гарантируя, что это будетбудет инициализирован позже), таким образом, избегая необходимости фиктивной ссылки.Это упражнение, оставленное читателю;)

0 голосов
/ 19 мая 2018

Arc::get_mut() потерпит неудачу, если у вас есть даже Weak ссылки, поэтому вам следует рассмотреть возможность использования внутренняя изменчивость .Поскольку вы используете 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 используйте другой тип построения, который идентичен A, за исключением UnsafeCell.Эти типы могут затем использоваться взаимозаменяемо с 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
}
...