Ответы пользователя Дмитрий Беляев

Как исправиться ошибку lifetime?

Дмитрий Беляев @bingo347

Crazy on performance...

impl<'a> List<'a> {
    fn add(&mut self, val: String, referenced_node: &'a Node) {
        self.node = Some(Node {
            data: String::from(String::from(val)),
            next: Some(referenced_node),
        });
    }
}

правда скорее всего будут траблы уже в месте вызова этого метода, но что бы поправить недостаточно контекста

Вообще думаю тут имеет смысл использовать Box/Rc/Arc вместо ссылок

Ответ написан 26 апр. 2024

Комментировать

Как работает этот код?

Дмитрий Беляев @bingo347

Crazy on performance...

Очень упрощенно HashMap можно представить следующим образом:

pub struct HashMap<K, V> {
    table: Table<(K, V)>,
}

struct Table<T> {
    // битовая маска занятых ячеек в items
    mask: u64,
    items: Box<[std::mem::MaybeUninit<Item<T>>; 64]>,
    len: usize,
}

struct Item<T> {
    data: T,
    next: Option<std::ptr::NonNull<Item<T>>>,
}

А Entry так:

pub enum Entry<'a, K, V> {
    Vacant(VacantEntry<'a, K, V>),
    Occupied(OccupiedEntry<'a, K, V>),
}

pub struct VacantEntry<'a, K, V> {
    hash: u64,
    key: K,
    table: &'a mut Table<(K, V)>,
}

pub struct OccupiedEntry<'a, K, V> {
    elem: Bucket<(K, V)>,
    table: &'a mut Table<(K, V)>,
}

// указатель на Item.data
struct Bucket<T> {
    ptr: std::ptr::NonNull<T>,
}

Как можно заметить у Entry есть лайфтайм, который связывает его с HashMap от которой он создан. А внутри есть мутабельная ссылка с этим лайфтаймом на таблицу с данными HashMap.
Метод entry упрощенно выглядит примерно так:

impl<K, V> HashMap<K, V> {
    pub fn entry<'a>(&'a mut self, key: K) -> Entry<'a, K, V>
    where
        K: Eq + std::hash::Hash,
    {
        use std::hash::Hasher as _;
        let mut hasher = self.get_hasher();
        key.hash(&mut hasher);
        let hash = hasher.finish();

        if let Some(elem) = self.table.find(hash, |(k, _)| key == *k) {
            Entry::Occupied(OccupiedEntry {
                elem,
                table: &mut self.table,
            })
        } else {
            Entry::Vacant(VacantEntry {
                hash,
                key,
                table: &mut self.table,
            })
        }
    }

    fn get_hasher(&self) -> impl std::hash::Hasher {
        todo!()
    }
}

impl<T> Table<T> {
    fn find(&self, hash: u64, is_match: impl FnMut(&T) -> bool) -> Option<Bucket<T>> {
        todo!()
    }
}

Как видим мутабельная ссылка всё же есть, только она завернута в структуру, так как одной этой ссылки не достаточно, так как в случае свободной Entry нам нужно хранить ещё и ключ, а заодно и хэш (чтоб не считать его снова), а в случае занятой - указатель на бакет (область памяти где храниться пара ключ и значение).

Ответ написан 19 апр. 2024

Комментировать

Как работают пакеты и крейты?

Дмитрий Беляев @bingo347

Crazy on performance...

Крэйт - это в первую очередь дерево модулей. Каждый крэйт содержит как минимум 1 корневой модуль (обычно это main.rs или lib.rs, но так же это могут быть модули доп бинарников, модули интеграционных тестов, модули примеров). Так же к крэйту относятся модули, которые объявили в других модулях этого крейта (ключевое слово mod).
Помимо этого крэйт - это сущность которой оперирует компилятор rustc, крэйт является единицей компиляции, то есть в rustc на компиляцию попадает крэйт целиком (на вход подаём корневой модуль, а он уже сам бегает по всему дереву согласно объявлениям mod).

Пакет - это сущность которой оперирует cargo. Компилятор rustc ничего не знает про пакеты. По простому пакет это папка с файлом Cargo.toml, в котором есть секция package (бывают ещё Cargo.toml объявляющие только workspace). Пакет состоит из крейтов, притом должен быть как минимум 1 крейт бинарника или библиотеки, а библиотечный крейт может быть только 1 или отсутствовать вовсе.
Пакет - это то, что публикуется в registry (такие как crates.io).
Так же в зависимостях мы указываем именно пакеты (но только те, что содержат крэйт-библиотеку).
Так же именно пакеты указываются в команде cargo install, при этом будут собраны все бинарные крейты входящие в пакет, а получившиеся исполняемые файлы будут помещены .cargo/bin

Войдите на сайт