| 138 | } |
| 139 | |
| 140 | unsafe fn put_dth<T>( |
| 141 | x: Option<NonNull<Node<T>>>, |
| 142 | key: &str, |
| 143 | val: Option<T>, |
| 144 | d: usize, |
| 145 | ) -> Option<NonNull<Node<T>>> { |
| 146 | let c = common::util::byte_at(key, d); |
| 147 | let mut x = x.unwrap_or_else(|| Node::new(c)); |
| 148 | match c.cmp(&x.as_ref().c) { |
| 149 | Ordering::Less => { |
| 150 | let p = put_dth(x.as_ref().left(), key, val, d); |
| 151 | x.as_mut().set_left(p); |
| 152 | } |
| 153 | Ordering::Greater => { |
| 154 | let p = put_dth(x.as_ref().right(), key, val, d); |
| 155 | x.as_mut().set_right(p); |
| 156 | } |
| 157 | Ordering::Equal => { |
| 158 | if d < key.len() - 1 { |
| 159 | let p = put_dth(x.as_ref().mid(), key, val, d + 1); |
| 160 | x.as_mut().set_mid(p); |
| 161 | } else { |
| 162 | x.as_mut().val = val; |
| 163 | } |
| 164 | } |
| 165 | } |
| 166 | |
| 167 | if x.as_ref().is_empty() { |
| 168 | // x.val is None and subtries all None, just release x itself |
| 169 | // println!("release x c = {}", x.as_ref().c as u8 as char); |
| 170 | let _ = Box::from_raw(x.as_ptr()); |
| 171 | None |
| 172 | } else { |
| 173 | Some(x) |
| 174 | } |
| 175 | } |
| 176 | |
| 177 | unsafe fn collect_prefix<T>( |
| 178 | x: Option<NonNull<Node<T>>>, |