Связный список на Rust в стиле С/C++

Просто мой пет-проект это шашечная программа, в которой есть большая сеть из позиций, которая ссылается друг на друга, все они в двусвязных циклических списках. А если весь код выбора хода обернуть unsafe, то какбы ничего и не останется, кроме там парсинга команд из консоли :)

Связный список на Rust в стиле С/C++

Нет, я скорее говорю о том, что Си и Rust достаточно разные инструменты, и я не готов рассматривать Rust как замену для C. Если брать сишный код, то его можно полностью переписать на Rust переосмыслив, но нельзя перевести. И кстати, C++ в этом плане куда ближе к Rust, чем Си. Поэтому лично я готов переходить на Rust из плюсов, там STL навязывает контейнерное мышление. Я понимаю понимаю преимущества Rust для конкурентного программирования и чего-нить более бизнес-ориентированого. Но несколько не готов переходить из Си.

Опять же, мой опыт такой, что я пробовал начинать какие-то пет-проекты на Rust и... не осилил (в основном логические игры типа шашек, футбол на листе бумаги, ...). Большей частью потому, что у тебя сразу возникает видение всего с использованием разных двусвязных кольцевых списков, указателей, несколько децентрализированная система без контейнеров но со ссылками. И ты начинаешь много парится, читать все те ссылки, что тут возникали, через пару дней я чувствую, что "I am wasting fucking life", никакого прогресса и берёшь в руки Си. Поэтому тема списков в Rust несколько больная.

Связный список на Rust в стиле С/C++

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

struct dlist
{
    struct dlist * next;
    struct dlist * prev;
};

static inline void dlist_init(struct dlist * restrict me)
{
    me->next = me;
    me->prev = me;
}

static inline void dlist_insert_after(struct dlist * me infant, struct dlist * prev)
{
    dlist_remove(me);

    struct dlist * next = prev->next;
    me->next = next;
    me->prev = prev;
    next->prev = me;
    prev->next = me;
};

static inline void dlist_insert_before(struct dlist * me infant, struct dlist * next)
{
    dlist_remove(me);

    struct dlist * prev = next->prev;
    me->next = next;
    me->prev = prev;
    next->prev = me;
    prev->next = me;
}


static inline void dlist_remove(struct dlist * me)
{
    me->prev->next = me->next;
    me->next->prev = me->prev;
    dlist_init(me);
}

Связный список на Rust в стиле С/C++

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

Если у тебя есть молоток, ты везде видишь гвозди. Если ты не знаешь типичное использование списков, то и не увидишь, где их можно применить.

Связный список на Rust в стиле С/C++

В том то и дело, что не должна. Двусвязный циклический список это такая структура, чтобы удалится из которой не надо вообще знать, откуда удаляться. Я приводил синшный код удаления элемента

struct dlist
{
    struct dlist * next;
    struct dlist * prev;
};

static inline void dlist_remove(struct dlist * elem)
{
    elem->prev->next = elem->next;
    elem->next->prev = elem->prev;
}

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

Связный список на Rust в стиле С/C++

Мы хотим из него удалить элемент — какой?

Мы хотим удалить себя. Откуда-нибудь, нам это не важно.

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

O1 {O1 O1 }; O2 {O2 O2 }; O3 {O3 O3}; O4 {O4 O4}; O5 {O5 O5}

Потому добавили первый объект к третьему, что в общем-то не отличается от того, что мы добавили третий к первому:

O1 {O3 O3}; O2 {O2 O2}; O3 {O1 O1}; O4 {O4 O4}; O5 {O5 O5}
И у нас четыре контейнера.

Теперь можно добавить пятый после третьему, тогда получится кольцо первый, третий, пятый

O1 {O3 O5}; O2 {O2 O2}; O3 {O5 O1}; O4 {O4 O4}; O5 {O1, O3}
И по сути три контейнера. И т. п.

Получается, что у нас нигде специально выделенного головного контейнера нету. Сам элемент по сути и есть контейнер. Не говоря о том, что в двусвязном списке могут быть элементы самых разных типов.

А все реализации двусвязных циклических списков, которые я видел на Rust, обычно подразумевает, что есть некая единая сущность, которая занимается вопросами удаления/добавления. И строго задают тип элементов в структуре.

Связный список на Rust в стиле С/C++

Я этот ответ уже принял, по сути это то, о чём писал

@ozkrif
то ты берешь unsafe и пишешь свою реализацию на сырых указателях, а потом заворачиваешь в безопасное API

Просто точно так же я могу написать всё на си, и обернуть в so-файл какой-нить.

Связный список на Rust в стиле С/C++

Я не спорю. Я не утверждаю, что такого не может быть в принципе. Я написал "не вижу большой проблемы", а не "такое невозможно в принципе".

Мой мойнт больше в том, что такая ситуация больше характерна для C++ где есть контейнеры и неявные операции. И гораздо меньше возникает при чистом сишном стиле кодирования, если мы только не будет писать в нём свою реализацию STL.

Связный список на Rust в стиле С/C++

Ну вот у автора

list.push_left(5);                      // [5, _, 3, 4, 1]
assert_eq!(list.pop_right(), Some(3));  // [5, _, 4, 1]
assert_eq!(list.pop_left(), Some(5));   // [_, 4, 1]

но это совсем не в духе сишных двусвязных списков. Хочется иметь что-то в духе

list.get_front().link.unlink()

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

struct dlist
{
    struct dlist * next;
    struct dlist * prev;
};

static inline void dlist_remove(struct dlist * elem)
{
    elem->prev->next = elem->next;
    elem->next->prev = elem->prev;
}

Собственно говоря интересно, как эти две строки нормально реализовать в Rust.

Связный список на Rust в стиле С/C++

Ок, давай более конкретный пример. Например,по твоей ссылке
intrusive_collections

Там пример использования

// Insert the objects at the front of the list
list.push_front(a);
list.push_front(b);
list.push_front(c);

// .....
let a = list.pop_front().unwrap();

Но для того, чтобы удалиться из двусвязного списка, не надо знать в каком ты списке вообще. Достаточно a.link.unlink() или list.get_front().link.unlink()

Связный список на Rust в стиле С/C++

Ну... я больше на примере конкретной задачи типа перебора методом танцующих связей. В этом случае у нас все элементы известных заранее, мы просто добавляем-удаляем их из двусвязных циклических списков. Почему тогда бы тогда не выделить один раз массив и не использовать индексы в нём? Это 100% достаточно для этой задачи. Ну а главное (1) сразу понятно как решать, не надо ничего гуглить и думать, подходит оно или нет (2) не наступишь на грабли, что ты что-то выбрал, начал преализовывать и застакался, потому что кто-то при удалении элемента их списка очищает указатели внутри него, а это ценная информация о том, куда его надо будет вставить назад. А целочисленные переменные Rust точно обнулять не станет.

Связный список на Rust в стиле С/C++

Что насчет автоматического освобождения ресурсов, обобщенных типов, контроля за явной инициализацией всех полей структур, решения проблемы висячих ссылок? Еще есть такая приятная мелочь как "каждое значение имеет одного и только одного владельца-переменную".

Ну... в целом я не вижу большой проблемы в случае автоматического освобождения ресурсов. Сейчас санитайзер в общем-то покажет большую часть таких проблем, и на практике такое фиксится достаточно быстро. Один владелец тоже, если у тебя однопоточный код, что может немного напрягать. И уж точно деля меня это не причина переходить на Rust.

Для меня куда большей плюшкой является паттерн-матчинг на алгебраических типах, что в общем-то заставляет зафорсить обработку всех состояний, которые ты постоянно забываешь. Лично мне это приятнее, чем ООП.

Связный список на Rust в стиле С/C++

#include <stdlib.h>
#include <stdio.h>

struct test {
  int len;
  int data[0];
};

struct test * create(int len)
{
    struct test * result = malloc(sizeof(struct test) + len * sizeof(int));
    result->len = len;
    for (int i=0; i<len; ++i) {
        result->data[i] = 1 + i * 2;
    }
    return result;
}

void echo(const struct test * test)
{
    printf("Data:");
    for (int i=0; i<test->len; ++i) {
        printf(" %d", test->data[i]);
    }
    printf("\n");
}

int main() {
    struct test * restrict test = create(5);
    echo(test);
    free(test);
    return 0;
}

Связный список на Rust в стиле С/C++

Вектор это плюсы, я говорю про чистый сишный код. Да, возможно это сделать, но в общем-то не могу сказать, что это частая ситуация именно в Си.

Связный список на Rust в стиле С/C++

Вызвать malloc проблем нет. Вот только в реальном сишном коде у тебя перемешивается malloc разные преобразования к intptr_t, offsetof разные прогулки по памяти и т. п. И в Rust это всё делается и более многословно, и с меньшим контролем. Вот, например, если я знаю, что последний элемент типа T это массив, то могу ли я добавить в malloc некоторое количество элементов для него?

Мощь Rust я понимаю больше как гарантию отсутствия race conditions в сложном многопоточном коде. Но если код однопоточный или достаточно замкнут на свой контекст, вычислительный, то как-бы borrow чекер мне не сильно поможет. И зачем мучиться?

Связный список на Rust в стиле С/C++

Во-первых со всем этим не так просто разобраться мне. Это раз. Во-вторых, не факт, что там всё что мне надо. Например, отменить последнее удаление из списке, как в случае реализации алгоритма танцующих связей. Такого метода навскидку я не нашёл. Поэтому то время, что ты потратишь на изучение, не факт, что не придёшь к выводу, что это под это не заточено. Что скорее всего наталкивает на мысль, что в практической реализации я скорее всего использовал бы массив объектов и индексы, так куда больше контроля.

Связный список на Rust в стиле С/C++

Ну... если брать Си, то там чаще для списка есть базовая структура, для которой реализуется общая работа со списками для всех, и есть струтктура, которая содержит поле связи. И часто чтобы получить родительскую структуру, используют offsetof


struct dlist {
struct list * next;
struct list * prev;
};

struct payload {
int data;
struct dlist link;
};

Ну и мне, в общем-то непонятно, почему Rust замена Си, если вещи, которые легко делать на Си, вызывают проблемы в Rust? Это два разных подхода к написанию софта, которые очень плохо взаимозаменяются и сочетаются, два разных инструмента.

Собственно говоря, для меня это достаточно большая проблема, если рассматривать миграцию на Rust: я беру свой сишны проект, который хочу переписать на Rust, Вижу там агрегацию нескольких malloc в один, вижу там двусвязныё двусвязные циклические списки, где элемент может и не знать, в каком он контейнере расположен, или можно сказать, что он сам по себе контейнер. Какие-то пулы аллокации. И понимаю, что это надо переписывать как-то совершенно по-другому.

В C++ да, там мышление контейнерно-оринетированное (STL) и в общем-то перевести его на Rust в общем-то достаточно техническая задача, ИМХО.

Как Rust-разработчики делают Веб безопаснее

Вот попробуй реализовать на досуге, там каждый объект находится в двух двусвязных циклических списках, плюс используется хак, что если объект был только что удалён из списка, то можно его быстро вставить назад двумя операциями... И всё это очень сильно противоречит тому, что на объект может быть только одна мутабельная ссылка.

А утечек памяти там не будет, потому что все объекты можно выделить один раз в векторе каком-нить. Меняются только связи между ними. Так что скорее всего в данном случае лучше хранить не ссылки, а индексы элементов, чтобы хоть как-то легло.

Как Rust-разработчики делают Веб безопаснее

Я не думаю, что bounds checking такая большая проблема. Ну напиши unsafe там где это влияет на производительность.

Про GC... Ну на главной странице я как раз прочитал

> Rust is blazingly fast and memory-efficient: with no runtime or garbage collector, it can power performance-critical services, run on embedded devices, and easily integrate with other languages.

Как Rust-разработчики делают Веб безопаснее

Мне непонятно, почему в статье про Rust основной упор делается на управлению памятью. Эту проблему частично решают языки с автоматическим управлением памяти, санитайзеры, чекеры и т. д. Как по мне, гораздо более важно то, что Rust решает большой пласт проблем конкурентного программирования.

К недостаткам Rust я бы отметил, что его концепция плохо ложиться на списочные структуры данных: какой-нить алгоритм танцующих связей будет выглядеть на Rust просто ужасно :)