Связанный список без кучи в no_std без malloc

Question

Чего не хватает в моей попытке создать кучу связанного списка?

Моя цель - получить приведенный ниже код для генерации последовательности [1, 2, 3] в стеке, а затем распечатать эти значения в отдельных строках без использования Box или чего-либо еще, требующего кучи или std или malloc.

Я пролистал https://rust -unofficial.github.io / too-many-lists но, похоже, все "хорошие" списки зависят от Rc, Box и т. Д.

Ящик heapless аккуратен, но требует заранее знать размер списка.

Мой Google-фу недостаточно силен, чтобы найти большую помощь. Любые указатели будут высоко оценены. Но вот что я думаю:

struct Node<'a, T> {
    value: T,
    next: Option<&'a Node<'a, T>>
}

struct List<'a, T> {
    head: Option<&'a Node<'a, T>>,
    tail: Option<&'a Node<'a, T>>
}

impl<'a, T> List<'a, T> {
    fn new() -> Self {
        Self {
            head: None,
            tail: None
        }
    }

    fn push(self, value: T) ->Self {
        unimplemented!(); // What's missing here?
    }
}

struct Iter<'a, T> {
    next: Option<&'a Node<'a, T>>
}

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;

    fn next(&mut self) -> Option<&'a T> {
        match self.next.take() {
            Some(next) => {
                self.next = next.next;
                Some(&next.value)
            },
            None => None
        }
    }
}

impl<'a, T> IntoIterator for List<'a, T> {
    type Item = &'a T;
    type IntoIter = Iter<'a, T>;

    fn into_iter(self) -> Self::IntoIter {
        Iter {
            next: self.head
        }
    }
}

fn main() {
    let list = List::new();
    let list = list.push(1);
    let list = list.push(2);
    let list = list.push(3);
    for item in list {
        println!("{}", item);
    }
}

Как видите, я застрял, пытаясь реализовать List.push.

Answer 1

Размещение вещей в стеке без знания их размера (или, по крайней мере, верхней границы их размера) возводит квадрат в круг и не будет работать.Вы можете позволить компилятору определить размер для вас, но это в значительной степени так.Причина этого проста: распределение стеков может не дать сбоя, и компилятор должен убедиться, что все подходит.

Если вы хотите пойти дальше и придерживаться подписи push(T), просто примите значение Matt Thomas'ответ - путь.

Вот мой взгляд на проблему, которая позволяет избежать создания вложенных типов:

struct Node<'a, T> {
    value: T,
    next: Option<&'a Node<'a, T>>,
}

impl<'a, T> Node<'a, T> {
    pub fn new(value: T, next: Option<&'a Self>) -> Self {
        Node { value, next }
    }

    pub fn iter(&'a self) -> Iter<'a, T> {
        Iter {
            current: Some(self),
        }
    }
}

struct Iter<'a, T> {
    current: Option<&'a Node<'a, T>>,
}

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;
    fn next(&mut self) -> Option<&'a T> {
        match self.current {
            Some(Node { value, next }) => {
                self.current = *next;
                Some(value)
            }
            None => None,
        }
    }
}

fn main() {
    // Allocation of the Nodes directly on the stack,
    // not inside a push method. <= Solves lifetime issues
    // Reversed order solves mutability issues.
    let three = Node::new(3, None);
    let two = Node::new(2, Some(&three));
    let one = Node::new(1, Some(&two));

    for item in one.iter() {
        println!("{}", item)
    }
}

Answer 2

Вот стек без кучи, который выполняет цели, указанные в ОП:

https://play.rust -lang.org /? Версия = стабильные и режим = отлаживать и издание = 2018 & сути = fb26b12270bd0a523a693276ec36014f

#[derive(Debug)]
struct Cons<T, U>(T, U);

#[derive(Debug)]
struct MyOption<T>(Option<T>);

trait Push<T>: Sized {
    fn push(self, value: T) -> Cons<Self, T>;
}

impl<T, U> Push<U> for Cons<T, U> {
    fn push(self, value: U) -> Cons<Self, U> {
        Cons(self, value)
    }
}

impl<T> Push<T> for T {
    fn push(self, value: T) -> Cons<Self, Self> {
        Cons(self, value)
    }
}

impl<T: Iterator<Item = U>, U> Cons<T, MyOption<U>> {
    fn next(&mut self) -> Option<U> {
        match (self.1).0.take() {
            Some(u) => Some(u),
            None => self.0.next()
        }
    }
}

impl<T> Iterator for Cons<MyOption<T>, MyOption<T>> {
    type Item = T;
    fn next(&mut self) -> Option<Self::Item> {
        match (self.1).0.take() {
            Some(t) => Some(t),
            None => (self.0).0.take()
        }
    }
}

impl<T: Iterator<Item = U>, U> Iterator for Cons<Cons<T, MyOption<U>>, MyOption<U>> {
    type Item = U;
    fn next(&mut self) -> Option<Self::Item> {
        match (self.1).0.take() {
            Some(u) => Some(u),
            None => self.0.next()
        }
    }
}

impl<T> Iterator for MyOption<T> {
    type Item = T;
    fn next(&mut self) -> Option<Self::Item> {
        self.0.take()
    }
}

fn create_stack() -> impl Iterator<Item = i32> + core::fmt::Debug {
          MyOption(Some(0))
    .push(MyOption(Some(1)))
    .push(MyOption(Some(2)))
    .push(MyOption(Some(3)))
    .push(MyOption(Some(4)))
}

fn main() {
    let stack = create_stack();
    println!("Here's the stack:");
    println!("{:?}", stack);

    println!("Here are the items in reverse order");
    for item in stack {
        println!("{}", item);
    }
}

Выход:

Here's the stack:
Cons(Cons(Cons(Cons(MyOption(Some(0)), MyOption(Some(1))), MyOption(Some(2))), MyOption(Some(3))), MyOption(Some(4)))
Here are the items in reverse order
4
3
2
1
0

Предостережения

• Вы не можете сделать stack = stack.push(...) в цикле (потому что stack.push(...) возвращает другой тип)
• Я совсем не думал о Drop поведении. Я думаю, это будет рекурсивно и взорвется для больших стеков
• Это может создать огромные структуры. Старайтесь не перемещать их слишком много
• Есть ли способ создать Iterator, для которого не требуется, чтобы структуры Cons содержали типы Option? И способ, который можно повторить более одного раза? Может быть,
• Я подозреваю, что каждая из этих функций impl дублируется для каждого элемента в результирующем стеке (поскольку каждый элемент имеет различный тип и все функции являются общими)
• Каждый вызов .push() потенциально может копировать self (не так, как в черте Copy, но, как в Rust, можно сделать memcpy за кулисами как часть движения владения, чтобы держать вещи в порядке. стек)