在 Rust FFI 中管理数组

Question

我正在用 Rust 编写一个共享库，它应该与 FFI 兼容。我定义了

struct Message

，一些函数需要接收并返回这个结构体的数组。虽然接收不会造成任何问题，因为分配将由用户处理，但通过 FFI 返回数组则更为复杂。我可以看到 3 种方法来实现这一点，我的问题是最常见的方法是什么

1. 让用户处理分配

#[no_mangle] 
pub extern "C" fn fill_array(array: *mut Message, size: usize) {
   for i in 0..size {
      // fill the array
   }
}

2. 有一个函数分配数组，其他函数则释放它
   [这个方法看起来是最好的，但我不知道如何实现]

#[no_mangle] 
pub extern "C" fn get_array() {
    // implementation????
}

#[no_mangle]
pub unsafe extern "C" fn free_array(arr: *mut Message) {
    // same as the get_array function
}

3. 有一个接受回调的函数

type Callback = extern "C" fn(*mut Message, usize);
#[no_mangle]
pub extern "C" fn pass_array(callback: Callback) {
    let mut arr = vec![...];
    callback(vec.as_mut_raw(), vec.len());
    // arr is dropped here
}

我发现的一个有用的答案是this，但我不喜欢你需要传递要释放的数组的大小。应该有办法解决它，对吧？因为像

Box<T>

这样的类型应该存储有关分配内存的元数据。基本上，我想要类似于

malloc

/

free

的行为。

Answer 1

fn main() {
    let a = vec![3, 5];
    let b = vec![2, 7];
    let c = [a, b].concat();
    a.sort();
    dbg!(a);
}

这很简单，但它确实有 O(nk * log nk) 最坏情况时间复杂度，其中 n 是结果向量的大小，k 是数组的数量。我们可以做得更好吗？

让我们尝试不同的方法。如果不考虑实现，您通常会如何手动排列这些元素？让我们对上面的例子进行提炼，并通过案例分析来思考。

案例一： 举例来说，数组中只有 1 个元素： 一 = [3] b = [2] 在这种情况下，这是非常微不足道的。我们只需将第一项与第二项进行比较，并取两者中最小的一项，并将其作为结果数组中的第一个元素插入：[2]。剩下的是 a 中的 3，然后我们将其附加为 [2, 3] 作为合并序列。

案例2： 现在，让我们考虑一下其中一个数组是否有多个元素： 一 = [3] b = [2, 5] 在这种情况下，我们将从两个数组中的第一项重新开始，并选择两项中最小的一项，即 2。下一个要比较的项是 3（来自 a）和 5（来自 b），其中 3 是选择作为下一个最小的元素。此时，我们已经用尽了数组 a 中的所有项目。现在，剩下要放入合并数组中的内容都必须来自数组 b。这是因为我们总是在每次迭代中选择最小的项，因此如果数组 a 中的所有项都用尽，则所有剩余元素必须大于 a 中的最后一个元素。因此，我们将 b 中的 5 附加到合并数组中，得到：[2, 3, 5]。

通过上面两种情况的演练，你一定已经想到了使用两个变量作为数组的索引，并逐一遍历它们，每次迭代中取下一个最小的元素，直到其中一个耗尽，然后复制剩余数组中的所有项目到我们的合并序列。听起来很简单？让我们实现它：

合并k的实现，其中k = 2 为了简化实现以提高可读性，我们将项目限制为整数 (i32) 值。一旦我们实现到位，就可以轻松地重构它，使其在任何 T 上通用。

以下是我们如何在 Rust 中实现上述基于索引指针的解决方案：

f

n merge(a: &[i32], b: &[i32]) -> Vec<i32> {
    let (mut i, mut j) = (0, 0);
    let mut sorted = vec![];
    let remaining;
    let remaining_idx;
    loop {
        if a[i] < b[j] {
            sorted.push(a[i]);
            i += 1;
            if i == a.len() {remaining = b; remaining_idx = j; break;}
        } else {
            sorted.push(b[j]);
            j += 1;
            if j == b.len() {remaining = a; remaining_idx = i; break;}
        }
    }
    for i in remaining_idx..remaining.len() {
        sorted.push(remaining[i]);
    }

    sorted
}

我们定义了合并函数，它接受两个整数切片（又称为整数数组的引用）并返回 Vec（堆分配值）。在 merge 中，我们创建两个从 0 开始的索引 i、j。我们还创建一个剩余的和剩余的_idx 来指向在另一个数组中的所有项目耗尽后剩下的数组。接下来，我们运行一个循环 {}，在其中选择最小的项目，将其推入排序并增加相应的索引。如果我们到达其中一个数组的末尾，我们还会进行额外的检查，并相应地分配剩余和剩余_idx。循环结束后，我们循环遍历剩余的数组项并推送到已排序。

但是，上述解决方案仅适用于 2 个数组。我们需要将解决方案推广到 k 个排序数组。