LINUX.ORG.RU

drop односвязного списка на rust

 , ,


0

4

помогите плз разобраться, почему работает мой кусок кода (является ли он корректным на самом деле и почему, или мне повезло)

работаю по гайду: http://cglab.ca/~abeinges/blah/too-many-lists/book/first-drop.html

мотивировка необходимости реализации drop в том, что при дефолтной реализации возможно переполнение стека при большом объеме списка. для проверки я написал тест:

    #[test]
    fn stack_overflow_on_drop() {
        let mut list = List::new();
        for n in 1..1000000 {
            list.push(n);
        }
    }

тест успешно сыплется при дефолтной реализации drop (читай: при отсутствии реализации) и успешно проходит при реализации drop, приведенной в гайде. для сравнения, приведу эту реализацию здесь:

impl Drop for List { // List - это голова списка, а не его элемент
    fn drop(&mut self) {
        let mut cur_link = mem::replace(&mut self.head, Link::Empty); // зачищаем указатель на head
        while let Link::More(mut boxed) = cur_link {
            cur_link = mem::replace(&mut boxed.next, Link::Empty); // зачищаем указатель на каждый next
        }
    }
}

теперь моя реализация:

impl Drop for List { // List - это голова списка, а не его элемент
    fn drop(&mut self) {
        let mut cur_link = mem::replace(&mut self.head, Link::Empty); // зачищаем указатель на head
        while let Link::More(boxed) = cur_link {
            cur_link = boxed.next; // проходим по списку, но ничего не зачищаем
        }
    }
}

вопрос: почему эта реализация не переполняет стек при освобождении списка (проходит тест)? является ли она корректной, или это случайность?

★★★★★

Последнее исправление: MyTrooName (всего исправлений: 1)

структура данных:

pub struct List {
    head: Link,
}

enum Link {
    Empty,
    More(Box<Node>),
}

struct Node {
    elem: i32,
    next: Link,
}

MyTrooName ★★★★★
() автор топика
Последнее исправление: MyTrooName (всего исправлений: 1)

У тебя в цикле в boxed двигается Box<> по значению, а значит в конце каждой итерации он дропается. Заметь, что в оригинальной реализации явного дропа тоже нет, освобождение достигается таким же выдвижением значения в boxed с последующим дропом.

Разница между твоим и оригинальным кодом только в том, что оригинальный код устанавливает boxed.next в Link::Empty, что в общем-то и не нужно в данном случае. Компилятор понимает, что boxed больше нигде не будет использоваться перед освобождением и дает просто выдвинуть boxed.next без mem::replace.

nonimous
()
Ответ на: комментарий от nonimous

спасибо; вроде, дошло.

Заметь, что в оригинальной реализации явного дропа тоже нет

а «явный дроп» вообще бывает?

MyTrooName ★★★★★
() автор топика
Ответ на: комментарий от red75prim

Который тоже неявный — это просто функция, которая ничего не делает =)

loyd
()
Ответ на: комментарий от nonimous

Немного поигрался, все несколько интереснее. Компилятор позволяет таким образом выдвинуть поле из структуры только если для нее не определен трейт Drop, т.е. если drop сводится к простому освобождению памяти, самой структуры и каскадно полей. Видимо он может отследить, что значение из поля было выдвинуто и Drop для него взывать не надо.

Если же Drop определен, то компилятор не даст просто выдивинуть(т.к. в этом случае в пользовательский метод Drop::drop придет структура с неопределенным значением в поле) - https://is.gd/zJLj3L . Поэтому оригинальный код в примере правильнее, т.к. mem::replace будет работать и для Node с определенным Drop.

nonimous
()
Ответ на: комментарий от Virtuos86

да вроде все равно работает.

    struct Droppable {
        int: i32,
    }
    impl Drop for Droppable {
        fn drop(&mut self) {
        }
    }
    #[test]
    fn droppable_contents() {
        let mut list = List::new();
        list.push(Droppable{int: 1});
        list.push(Droppable{int: 2});
    }

для Node, собственно, Drop и не реализован, неважно какой тип элемента подсунуть. значит должно работать и в общем случае.

MyTrooName ★★★★★
() автор топика
Последнее исправление: MyTrooName (всего исправлений: 1)
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.