如何使用父指针创建高效的不可变树

Question

我正在构建一个“场景图”，它是

Shape

节点的分层数据结构（例如球体、立方体、网格等，示例代码中未显示）。一个

Shape

可以拥有零个或多个子

Shape

实例。这形成了一棵树，它被完全构建，然后不可变地传递给一组工作线程，这些线程根据该场景图渲染图像的不同部分。场景图一旦构建就不需要更改，因此线程只需要读取访问权限。

我的问题涉及场景葡萄的构建。最初，我的形状拥有子形状。 IE。 Shape 拥有其所有子项。因此我没有使用指针或引用。这工作得很好，直到我需要添加父指针。

Shape

的每个子级现在必须维护一个指向其父级的指针。我走上了使用

Arc

的道路（因为最终场景图在线程之间共享），这让我对父级使用

Weak

ptr 来避免循环问题。但这意味着主要拥有关系（形状拥有子形状）现在也必须是

Arc

，并且该指针比父指针被遍历很多很多次。

我的理解是，

Arc

的特性只有在构造这个数据结构并移交给线程池时才需要。在渲染期间，这些

Arc

指针是不幸的开销。此时数据结构被认为是不可变的，因此不再需要 Arc 的功能。仅在构建数据结构期间需要它们，以支持创建

Weak

父指针。

有趣的是，我无法在 safe 代码中找到一种方法来将子项设置为 Shape 所拥有 并在子项中设置父指针。这是一种双向链表，我知道这在 Rust 中很难。最后我不得不使用一行unsafe

来将指针设置在下面的

Shape::set_parent()

中：

use std::sync::{Arc, Weak};

pub trait LocalIntersect {
    fn local_intersect(&self);
}

#[derive(Debug, Default)]
pub struct Shape {
    id: usize,
    members: Vec<Arc<Shape>>,
    parent: Option<Weak<Shape>>,
}

impl Shape {
    fn new(id: usize) -> Self {
        Self { id, members: vec![], parent: None }
    }

    fn add(&mut self, shape: Arc<Shape>) {
        self.members.push(shape);
    }

    fn set_parent(&self, parent: Weak<Shape>) {
        let this = self as *const Shape as *mut Shape;
        unsafe {
            (*this).parent = Some(parent);
        }
    }

    fn set_parent_to_all(&self, parent_weak: Weak<Shape>) {
        for member in &self.members {
            member.set_parent(parent_weak.clone());
        }
    }
}

impl LocalIntersect for Shape {
    fn local_intersect(&self) {
        // For now, check if there is a parent and if so, print its ID
        // (Later, we'll combine parent transforms, but not now)
        if let Some(parent_weak) = &self.parent {
            if let Some(parent) = parent_weak.upgrade() {
                println!("local_intersect {}, parent {}", self.id, parent.id);
            }
        }
    }
}

fn main() {
    let mut parent_shape = Shape::new(0);
    let child_shape = Shape::new(1);

    let child_arc = Arc::new(child_shape);

    // Add child to the parent's group
    parent_shape.add(Arc::clone(&child_arc));

    // Wrap the parent shape in Arc
    let parent_arc = Arc::new(parent_shape);

    // Set the parent pointer of each child in the group
    parent_arc.set_parent_to_all(Arc::downgrade(&parent_arc));

    // Share across threads (example with a thread)
    let shared_node = Arc::clone(&child_arc);
    let thread = std::thread::spawn(move || {
        shared_node.local_intersect();
    });
    thread.join().unwrap();

    // Output is:
    //   local_intersect 1, parent 0
}

铁锈游乐场

鉴于性能是该应用程序的首要任务，Rust 中是否有一种惯用的方法来处理这个问题？这是

unsafe

 代码的良好候选者吗？我应该放弃 

Arc

 和 

Weak

 并只使用正常的子所有权和父指针的原始指针吗？如果是这样，我稍后将如何处理该数据结构的删除？

我可以使用诸如

id_tree

 或 

petgraph

 之类的东西，但是这些也会在查找孩子或父母时提供开销。我真的只是想要一个渲染器可以直接返回到父级的指针，而不影响非常常见的“获取子级”查找的性能。

我对 Rust 或 C/C++ 并不陌生，但我对编写

unsafe

 Rust 代码很陌生。

编辑：例如，在 C 程序中，我只需在渲染之前向所有子形状添加一个原始父指针，然后在释放任何形状之前将它们全部清空，并且它不会影响所有权或导致悬空指针问题。我正在 Rust 中寻找类似的过程 - 只是在最终不可变的数据结构中一个漂亮、简单、快速的父指针，但没有先有鸡还是先有蛋的问题。

Answer 1

如果你真的认为树一旦构建起来就不可变，也许你可以将所有节点打包在一个向量中并使用索引而不是引用（也许这被称为竞技场，不确定是否有微妙之处）。 在构建树时我们必须格外小心索引，但这可以完全封装在实现中（我们永远不必自己分配 id）。 在多线程上下文中，我们只需共享/传递整个节点向量即可。

这是您的示例，根据这个想法稍作修改。 （我不明白

local_intersect()

功能，也许它没有达到你想要的效果）。

use std::sync::Arc;

pub trait LocalIntersect {
    fn local_intersect(
        &self,
        shapes: &Vec<Shape>,
    );
}

#[derive(Debug)]
pub struct Shape {
    id: usize,
    members: Vec<usize>,
    parent_id: usize,
}

impl Shape {
    fn new(
        shapes: &mut Vec<Self>,
        parent_id: Option<usize>,
    ) -> usize {
        let id = shapes.len();
        shapes.push(Self {
            id,
            members: Vec::new(),
            parent_id: usize::MAX,
        });
        if let Some(parent_id) = parent_id {
            shapes[parent_id].members.push(id);
            shapes[id].parent_id = parent_id;
        };
        id
    }

    fn parent<'a>(
        &self,
        shapes: &'a Vec<Self>,
    ) -> Option<&'a Self> {
        if self.parent_id == usize::MAX {
            None
        } else {
            Some(&shapes[self.parent_id])
        }
    }
}

impl LocalIntersect for Shape {
    fn local_intersect(
        &self,
        shapes: &Vec<Shape>,
    ) {
        // For now, check if there is a parent and if so, print its ID
        // (Later, we'll combine parent transforms, but not now)
        if let Some(parent) = self.parent(shapes) {
            println!("local_intersect {}, parent {}", self.id, parent.id);
        }
    }
}

fn main() {
    let mut shapes = Vec::new();
    let parent_id = Shape::new(&mut shapes, None);
    let child_id = Shape::new(&mut shapes, Some(parent_id));

    let shared_shapes = Arc::new(shapes);
    let thread = std::thread::spawn({
        let shapes = Arc::clone(&shared_shapes);
        move || {
            println!("in thread");
            shapes[child_id].local_intersect(&shapes);
        }
    });
    thread.join().unwrap();

    println!("back to main");
    shared_shapes[child_id].local_intersect(&shared_shapes);
}
/*
in thread
local_intersect 1, parent 0
back to main
local_intersect 1, parent 0
*/