使用 Rust 进行手动锁定

我正在try 用Rust编写一个union-find的实现.这在C等语言中实现起来非常简单，但仍然需要进行复杂的运行时分析.

I'm having trouble getting Rust's mutex semantics to allow iterative hand-over-hand locking.

这就是我现在的处境.

首先，这是我想要在C中实现的 struct 的一部分的一个非常简单的实现:

#include <stdlib.h>

struct node {
  struct node * parent;
};

struct node * create(struct node * parent) {
  struct node * ans = malloc(sizeof(struct node));
  ans->parent = parent;
  return ans;
}

struct node * find_root(struct node * x) {
  while (x->parent) {
    x = x->parent;
  }
  return x;
}

int main() {
  struct node * foo = create(NULL);
  struct node * bar = create(foo);
  struct node * baz = create(bar);
  baz->parent = find_root(bar);
}

请注意，指针的 struct 是inverted tree；多个指针可能指向一个位置，并且没有循环.

此时，没有路径压缩.

这是一个可靠的翻译.我 Select 使用Rust的引用计数指针类型来支持上面提到的倒树类型.

请注意，这个实现要详细得多，可能是因为Rust提供了更高的安全性，但可能是因为我对Rust缺乏经验.

use std::rc::Rc;

struct Node {
    parent: Option<Rc<Node>>
}

fn create(parent: Option<Rc<Node>>) -> Node {
    Node {parent: parent.clone()}
}

fn find_root(x: Rc<Node>) -> Rc<Node> {
    let mut ans = x.clone();
    while ans.parent.is_some() {
        ans = ans.parent.clone().unwrap();
    }
    ans
}

fn main() {
    let foo = Rc::new(create(None));
    let bar = Rc::new(create(Some(foo.clone())));
    let mut prebaz = create(Some(bar.clone()));
    prebaz.parent = Some(find_root(bar.clone()));
}

每次调用find_root时，路径压缩都会沿着根路径 for each node 重新设置父 node .要将此功能添加到C代码中，只需要两个新的小函数:

void change_root(struct node * x, struct node * root) {
  while (x) {
    struct node * tmp = x->parent;
    x->parent = root;
    x = tmp;
  }
}

struct node * root(struct node * x) {
  struct node * ans = find_root(x);
  change_root(x, ans);
  return ans;
}

函数change_root执行所有的重父化，而函数root只是一个包装器，用于使用find_root的结果来重父化根路径上的 node .

为了在Rust中实现这一点，我决定必须使用Mutex，而不仅仅是引用计数指针，因为Rc接口只允许在多个指向该项的指针处于活动状态时，通过写时复制进行可变访问.因此，所有代码都必须更改.在进入路径压缩部分之前，我挂断了find_root:

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

struct Node {
    parent: Option<Arc<Mutex<Node>>>
}

fn create(parent: Option<Arc<Mutex<Node>>>) -> Node {
    Node {parent: parent.clone()}
}

fn find_root(x: Arc<Mutex<Node>>) -> Arc<Mutex<Node>> {
    let mut ans = x.clone();
    let mut inner = ans.lock();
    while inner.parent.is_some() {
        ans = inner.parent.clone().unwrap();
        inner = ans.lock();
    }
    ans.clone()
}

这会产生错误(0.12.0)

error: cannot assign to `ans` because it is borrowed
ans = inner.parent.clone().unwrap();

note: borrow of `ans` occurs here
let mut inner = ans.lock();

What I think I need here is hand-over-hand locking. For the path A -> B -> C -> ..., I need to lock A, lock B, unlock A, lock C, unlock B, ... Of course, I could keep all of the locks open: lock A, lock B, lock C, ... unlock C, unlock B, unlock A, but this seems inefficient.

然而，Mutex不提供解锁，而是使用RAII.How can I achieve hand-over-hand locking in Rust without being able to directly call 101?

EDIT:正如 comments 所指出的，我可以使用Rc<RefCell<Node>>而不是Arc<Mutex<Node>>.这样做会导致相同的编译器错误.

为了清楚地说明我试图通过使用手动锁定来避免什么，这里有一个RefCell版本，它编译但在路径长度上使用了空格线性.

fn find_root(x: Rc<RefCell<Node>>) -> Rc<RefCell<Node>> {
    let mut inner : RefMut<Node> = x.borrow_mut();
    if inner.parent.is_some() {
        find_root(inner.parent.clone().unwrap())
    } else {
        x.clone()
    }
}