Блог

Мне нужна структура данных двоичного дерева в C, и в Rust уже существует реализация двоичного дерева. Поэтому я решил завернуть это.

Я создал структуру, совместимую с C, содержащую необработанный указатель на BTreeMap, и добавил некоторые методы, которые принимают указатель на мою структуру-оболочку.

Проблема заключается в тестировании модуля. Тест пройден, если я использую только свои методы, но всякий раз, когда я ставлю println! макрос между вызовами методов, Тест не удался.

 use std::collections::BTreeMap;  #[repr(C)] pub struct my_btree {  btree: *mut BTreeMaplt;u64, u64gt;, }  #[no_mangle] pub extern "C" fn my_btree_new() -gt; *mut my_btree {  let boxed = Box::new(BTreeMap::lt;u64, u64gt;::new());  let mut ret = my_btree {  btree: Box::into_raw(boxed),  };   amp;mut ret as *mut my_btree }  #[no_mangle] pub extern "C" fn my_btree_insert(  btree: *mut my_btree,  key: u64,  val: u64, ) -gt; bool {  unsafe {  let mut boxed = Box::from_raw((*btree).btree);  let contains = (*boxed).contains_key(amp;key);  if contains {  return false;  }   (*boxed).insert(key, val);  println!("{:?}", boxed);  Box::into_raw(boxed);   return true;  } }  #[no_mangle] pub extern "C" fn my_btree_contains(btree: *mut my_btree, key: u64) -gt; bool {  unsafe {  let boxed = Box::from_raw((*btree).btree);  println!("{:?}", boxed);  let ret = (*boxed).contains_key(amp;key);   Box::into_raw(boxed);   ret  } }  #[no_mangle] pub extern "C" fn my_btree_free(btree: *mut my_btree) {  unsafe {  let _boxed = Box::from_raw((*btree).btree);  } }  #[cfg(test)] mod tests {  use super::*;    #[test]  fn insert() {  let map = my_btree_new();  my_btree_insert(map, 1, 1);  my_btree_insert(map, 2, 2);  my_btree_insert(map, 3, 30);  let err = my_btree_contains(map, 1);  assert_eq!(err, true);  println!("???"); // If this line commented out, then test success without error.  my_btree_free(map);  } }  

когда я запускаю тест с помощью команды ниже,

 $ cargo test -- --nocapture  

В моем терминале,

 running 1 test {1: 1} {1: 1, 2: 2} {1: 1, 2: 2, 3: 30} {1: 1, 2: 2, 3: 30} ??? error: test failed, to rerun pass '--lib'  

Но если я закомментирую println!("???"); , то тест пройдет без каких-либо ошибок.

И если я помещу println между вызовами my_btree_insert, при следующем вызове произойдет сбой. Это странно. Почему это произошло?

У вас есть несколько проблем.

1. В my_btree_new , вы создаете экземпляр my_btree в стеке (т. е. локально для функции) , а затем возвращает указатель на нее.
2. В my_btree_insert , вы берете свой указатель, а затем строите Box вокруг него. Перед возвращением вы деконструируете элемент Box так, чтобы он не был освобожден, но у вас также есть ранний путь возврата, который не деконструирует элемент Box . В вашем тестовом примере этот путь кода не используется, но я ожидаю, что в этом случае он выйдет из строя.

Почему он падает только тогда, когда вы вставляете println! его ? Просто — дополнительные вызовы функций, которые генерируются в области стека, содержащей my_btree .

Вот несколько советов по его исправлению:

• На самом деле вам не нужна структура оболочки (по крайней мере, для этого базового примера). Но если у вас будет такая структура, вся структура должна быть в куче, а не только структура BTree.
• Вам не нужно вставлять/распаковывать указатель в каждый метод; это не добавляет ценности и просто увеличивает вероятность того, что вы забудете вставить его в какой-либо кодовый путь, что приведет к двойному свободному сбою. Только снова вставьте его в my_btree_free функцию.
• Вы сделали все эти функции безопасными с помощью кода внутри, завернутого в небезопасный блок. Это не совсем правильно — компилятор не может проверить правильность указателя, поэтому функция небезопасна (или, другими словами, безопасная функция не должна аварийно завершаться независимо от аргументов, которые вы предоставляете).

Вот версия, которая работает:

 use std::collections::BTreeMap;  #[repr(C)] pub struct my_btree {  btree: BTreeMaplt;u64, u64gt;, }  #[no_mangle] pub extern "C" fn my_btree_new() -gt; *mut my_btree {  let boxed = Box::new(my_btree { btree: BTreeMap::lt;u64, u64gt;::new() } );  Box::into_raw(boxed) }  #[no_mangle] pub unsafe extern "C" fn my_btree_insert(  btree: *mut my_btree,  key: u64,  val: u64, ) -gt; bool {  let contains = (*btree).btree.contains_key(amp;key);  if contains {  return false;  }  (*btree).btree.insert(key, val);   return true; }  #[no_mangle] pub unsafe extern "C" fn my_btree_contains(btree: *mut my_btree, key: u64) -gt; bool {  (*btree).btree.contains_key(amp;key) }  #[no_mangle] pub unsafe extern "C" fn my_btree_free(btree: *mut my_btree) {  let _boxed = Box::from_raw(btree); }  #[cfg(test)] mod tests {  use super::*;    #[test]  fn insert() {  let map = my_btree_new();  unsafe {  my_btree_insert(map, 1, 1);  my_btree_insert(map, 2, 2);  my_btree_insert(map, 3, 30);  let err = my_btree_contains(map, 1);  assert_eq!(err, true);  println!("???"); // If this line commented out, then test success without error.  my_btree_free(map);  }  } }