I learn how to write linklists from https://rust-unofficial.github.io/too-many-lists/sixth-random-bits.html, and I try to write an AvlTree with what I learned from it , but when I write a bit code, I'm stuck with this exception:
hello-rust(23862,0x204488600) malloc: *** error for object 0x600003b79140: pointer being freed was not allocated hello-rust(23862,0x204488600) malloc: *** set a breakpoint in malloc_error_break to debug I dont't know where should I change the code to make it right. Here's my all code:
use std::ptr::NonNull; type Link<T> = Option<NonNull<Node<T>>>; #[derive(Debug)] pub struct Node<T> { elem: T, parent: Link<T>, left: Link<T>, right: Link<T>, bf: i8, } impl<T> Node<T> { pub fn new_with_elem(elem: T) -> Node<T> { Node { elem, parent: None, left: None, right: None, bf: 0, } } } #[derive(Debug)] pub struct AvlTree<T> { root: Link<T>, count: usize, } impl<T: PartialEq + Eq + std::cmp::PartialOrd + Clone+std::fmt::Display> AvlTree<T> { pub fn new() -> AvlTree<T> { AvlTree { root: None, count: 0 } } pub fn insert(&mut self, elem: T) { let elem_clone = elem.clone(); let mut new_node = Node::new_with_elem(elem); if self.count == 0 { self.root = new_link_with_node(new_node); self.count += 1; return; } let mut bf = 0; let mut parent: Link<T> = None; let mut n = self.root; while n.is_some() { n.map(|node| { unsafe { println!("elem={}", &elem_clone); let box_node = Box::from_raw(node.clone().as_ptr()); if elem_clone == box_node.elem { return; } parent = n; bf <<= 1; if elem_clone < box_node.elem { n = box_node.left; } else { n = box_node.right; bf |= 1; } } }); } } } impl<T: std::fmt::Display> std::fmt::Display for Node<T> { fn fmt(&self, fmt: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error> { write!(fmt, " elem:{},bf:{} | ", self.elem, self.bf) } } impl<T: std::fmt::Display> std::fmt::Display for AvlTree<T> { fn fmt(&self, fmt: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error> { if self.root.is_none() { write!(fmt, " empty tree! ") } else { show_node(&self.root); write!(fmt, " print over ") } } } fn show_node<T: std::fmt::Display>(node: &Link<T>) { node.map(|n| { unsafe { let box_node = Box::from_raw(n.as_ptr()); println!("{}", box_node); if box_node.left.is_some() { show_node(&box_node.left) } if box_node.right.is_some() { show_node(&box_node.right) } } }); } fn new_link_with_node<T: PartialEq + Eq + std::cmp::PartialOrd + Clone>(node: Node<T>) -> Link<T> { NonNull::new(Box::into_raw(Box::new(node))) } 
