Я пытаюсь создать небезопасную, но более производительную 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)};
.
Теперь я хотел бы понять, почему это работает, а предыдущая версия - нет.
add
при присвоении значения неинициализированной памяти. - person Marin Veršić   schedule 21.05.2019buff.resize_with(size, T::default);
вместоset_len
, сбой больше не будет. - person hellow   schedule 21.05.2019test0
, где также есть объект (строка), выделенный кучей? Я понимаю, что могу использовать значения по умолчанию, я специально пытался этого избежать - person Marin Veršić   schedule 21.05.2019mem::forget
, чтобы не вызывать деструктор элемента, который вы пытаетесь поменять местами. В общем, не делай этого. Инициализация - это единовременные затраты, которые не являются дорогостоящими. ИМХО, вы зря уничтожаете безопасную цель Rust. - person hellow   schedule 21.05.2019String
, потому что это неопределенное поведение. Вы не можете предсказать, что и когда произойдет. Он может сломаться в другой операционной системе, другой архитектуре процессора или в будущем компиляторе Rust. - person Peter Hall   schedule 21.05.2019