不安全队列实现

Question

我尝试创建一个不安全但性能更高的 ArrayQueue 实现。添加测试用例后，其中一个产生了分段错误。这是我简单的最小实现：

use std::mem;

pub struct ArrayQueue<T> {
    buff: Vec<T>,
    head: usize,
    size: usize,
}

impl<T> ArrayQueue<T> {
    pub fn new(size: usize) -> Self {
        let mut buff = Vec::with_capacity(size);

        unsafe {
            buff.set_len(size);
        }

        ArrayQueue {
            buff: buff,
            head: 0,
            size: 0,
        }
    }

    pub fn add(&mut self, elem: T) {
        let idx = (self.head + self.size) % self.buff.len();
        *unsafe { self.buff.get_unchecked_mut(idx) } = elem;
        self.size += 1;
    }

    pub fn remove(&mut self) -> T {
        let idx = self.head;

        self.size -= 1;
        self.head = (self.head + 1) % self.buff.len();
        mem::replace(unsafe { self.buff.get_unchecked_mut(idx) }, unsafe {
            mem::uninitialized()
        })
    }
}

impl<T> Drop for ArrayQueue<T> {
    fn drop(&mut self) {
        let mut idx = self.head;

        for _ in 0..self.size {
            // Drop only valid elements of the queue
            drop(unsafe { self.buff.get_unchecked_mut(idx) });
            idx = (idx + 1) % self.buff.len();
        }

        unsafe {
            // Prevent deallocation of vector elements
            // This still dallocates vector's internal buffer
            self.buff.set_len(0);
        }
    }
}

#[cfg(test)]
mod test {
    use super::ArrayQueue;

    #[test]
    fn test0() {
        let mut x = ArrayQueue::new(10);
        x.add(String::from("K"));
        assert_eq!(x.remove(), String::from("K"));
    }

    #[test]
    fn test1() {
        let mut x: ArrayQueue<Box<String>> = ArrayQueue::new(10);
        x.add(Box::new(String::from("K")));
        assert_eq!(x.remove(), Box::new(String::from("K")));
    }
}

我相信我正在做适当的删除以防止任何内存泄漏。

我附上了两个测试用例，其中一个有效，但另一个因内存引用无效而导致崩溃。

它在 add 方法 (*unsafe {self.buff.get_unchecked_mut(idx)} = elem;) 内崩溃，我怀疑发生这种情况是因为我以某种方式试图写入无效的内存位置。
我在测试中专门为向量元素使用了堆分配对象，但令我惊讶的是 String 可以正常工作，而 Box 不能。

我想了解是否可以像这样进行不安全的实施，以及为什么它目前失败了？

编辑

我已通过将 *unsafe {self.buff.get_unchecked_mut(idx)} = elem; 替换为 unsafe {std::ptr::write(self.buff.get_unchecked_mut(idx), elem)};

来解决问题

现在我想明白为什么这个有效而以前的版本无效

Answer 1

当你运行*unsafe { self.buff.get_unchecked_mut(idx) } = elem;替换一个未初始化的Box或String时，它将运行drop放在这个未初始化的Box 或 String。 Box 和 String 都包含一个指向堆中应该存储数据的部分的指针，当它们被删除时，它将释放该位置的内存。

通过删除未初始化的 Box 或 String，它将在任意位置释放内存，因为未初始化的指针可以是任何东西。取消分配尚未分配的内存是未定义的行为。

不安全队列实现

Unsafe queue implementation

generics

queue

unsafe

segmentation-fault

rust