在Rust中使用Rc时如何防止递归释放的堆栈溢出？

Question

在Rust中使用Rc时，有什么好方法可以防止堆栈从递归释放中溢出吗？就我而言，我有一种可以增长到很大的图。当图表的一部分不再使用时，我希望它会被释放。但是，这会创建一系列的释放，最终使堆栈溢出。作为示例，请考虑以下代码：

// This is a test to see how long of a DAG that we can make before we have a 
// problem freeing the graph due to a stack overflow from the memory frees.

// External libraries
use std::rc::Rc;              

// Graph that contains integers
struct MyGraph {    

    // Random data
    data : u32,               

    // Previous link                                  
    previous : Option <Rc <MyGraph>>,            
} 

// Show that we're freeing    
impl Drop for MyGraph {
    fn drop(&mut self) {
        println!("{}",self.data);
    }   
}   


// Create a long graph of things
fn main() {

    // Set the size of the problem.  This should crash things.
    let m:u32 = 100000;      

    // Create the first node
    let mut node = Rc::new(MyGraph {                           
        data : 0,                              
        previous : None});

    // Add a bunch of additional nodes
    for i in 1..m {             
        node = Rc::new(MyGraph {            
            data : i,                                   
            previous : Some(node.clone())});            
    }

    // Zip through the nodes to make sure we created the graph
    {   
        let mut node_p = node.clone();           
        while node_p.previous.is_some() {
            print!("{} ",node_p.data);    
            node_p = node_p.previous.as_ref().unwrap().clone()
        }
    }
    println!("");

    // Free the memory in the graph by constructing a new single element
    node = Rc::new(MyGraph {                
        data : 0,    
        previous : None});    

    // Denote we finished  
    println!("Fin");
}   

它可能取决于底层计算机，但取决于我的计算机最终会崩溃

52418
52417

thread 'main' has overflowed its stack
fatal runtime error: stack overflow
Aborted

如果图形的大小较小，例如3，则程序将返回

2 1 
2
1
0
Fin
0

现在，这并不意外。完全相同的事情发生在C ++中。在C ++中，我可以通过实现自己的迭代计数释放的引用计数类型来解决此问题。我的问题是，Rust中是否有更好的选择来处理这些释放。

Answer 1

您可以通过从递归取消分配切换到迭代取消分配来防止堆栈溢出。在您的具体示例中，改用以下Dropimpl：

// Show that we're freeing
impl Drop for MyGraph {
    fn drop(&mut self) {
        let mut prev = self.previous.take();

        while let Some(rc) = prev {
            if let Ok(mut graph) = Rc::try_unwrap(rc) {
                prev = graph.previous.take();
            } else {
                break;
            }
        }
    }
}

也就是说，删除所有可以释放的先前图形（仅具有一个引用），但是在删除之前，将其previous字段设置为None（就是previous.take()这样），然后继续删除由返回的图形previous.take()。

我建议您看一看教程，如果您还没有学习过“用太多的链表进行生锈”，它会涉及到包括此递归释放在内的链接结构的常见危害。