LINUX.ORG.RU

Подскажите классификацию структур данных

 ,


0

2

Затруднительно сформулировать вопрос, поэтому посмотрим на примере, а пример - связный список.

Можно представлять список таким образом:

struct integer_list_node
{
    int data;
    struct integer_list_node *next;
    struct integer_list_node *prev;
};

К примеру, так реализованы списки (и другие структуры данных) в C++.

А можно так:

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

struct integer_list_node
{
    int data;
    struct list node;
};

При этом обычно используют макрос типа container_of, чтобы по указателю на list получить указатель на контейнер. Так, например, списки используются в ядре Linux.

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


Так вот, существуют термины для обозначения этих двух способов представления

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

Может еще нужен специальный термин для какого-то такого варианта:

#define GEN_NEXT_PREV(type) \
type *next; \
type *prev;

struct integer_list_node
{
    int data;
    GEN_NEXT_PREV(struct integer_list_node)
};
?

Или такого?

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

struct data
{
    int data;
};

struct list_and_data
{
  struct data;
  struct list;
};

Или такого: https://wandbox.org/permlink/Ky8fnuqyE0Ahxftm ?

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

Может еще нужен специальный термин для какого-то такого варианта

Это разновидность первого моего примера.

Или такого?

$ gcc -pedantic -o sample sample.c
sample.c:14:14: warning: declaration does not declare anything
   struct data;
              ^
sample.c:15:14: warning: declaration does not declare anything
   struct list;
              ^
sample.c:12:8: warning: struct has no members [-Wpedantic]
 struct list_and_data

Что вы имели ввиду?

Или такого: https://wandbox.org/permlink/Ky8fnuqyE0Ahxftm ?

А какая разница, как указатели кодировать? Это тоже вариант первого примера.

eve
() автор топика

Так, например, списки используются в ядре Linux.

Наследование, ООП.

upd. Особенно если «родителя» сделать первым полем структуры.

im-0
()
Последнее исправление: im-0 (всего исправлений: 1)
Ответ на: комментарий от SZT

Или такого?

А тут скорее композиция.

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

im-0
()
Ответ на: комментарий от eve

Что вы имели ввиду?

Очевидно, что я имел ввиду отдельно описывать данные, отдельно связывающую часть, а потом одной структурой из сцеплять

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

struct data
{
    int data1;
    int data2;
    char data3;
};

struct list_and_data
{
  struct data d;
  struct list l;
};

SZT ★★★★★
()
Ответ на: комментарий от im-0

Ну не совсем классификация, а скорее просто обозначение.

eve
() автор топика
Ответ на: комментарий от SZT

Очевидно, что это второй вариант.

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

Нет, intrusive это не про то. Intrusive это к вопросу о том, торчит ли у тебя указатель на данные из двусвязного списка, или оно там все в одном месте. См. https://www.data-structures-in-practice.com/intrusive-linked-lists/

In an intrusive linked list implementation, the list node contains next pointer to the next list node, but no data pointer because the list is embedded in the linked object itself.

У тебя оба примера интрузивны

SZT ★★★★★
()

Если next, prev cделать первыми полями в структуре, то код управления списком можно написать один раз и использовать для любого списка, внутри достаточно struct node_t* и размера реальной структуры, который вызывающему известен ;)

struct node_t {
  struct node_t *next, *prev;
}

bormant ★★★★★
()
Ответ на: комментарий от eve

Это не intrusive.

Это вообще просто структура, тут некорректно говорить, intrusive это или нет.

In a typical linked list implementation, a list node contains a data pointer to the linked data and a next pointer to the next node in the list.

Неинтрузивное это вот:

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

struct data
{
    int data1;
    int data2;
    char data3;
};

struct list_and_data
{
  struct data *d; // указатель на данные, а не сами данные
  struct list l;
};

https://d33wubrfki0l68.cloudfront.net/950ed36bc66a8845134d8d13540ca1d25005bd2... - понимаешь смысл этой картинки?

SZT ★★★★★
()
Ответ на: комментарий от bormant

Тогда, каждый раз обращаясь к функциям, придется приводить к node_t*, что не очень удобно.

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

Это не диалектические тонкости. Интрузивность это не про то что ты спрашиваешь. Оба приведенных тобой примера в теме - интрузивны. Потому что там данные в одном месте с next prev размещены. Неинтрузивно это если у тебя указатель на данные и next prev.

SZT ★★★★★
()
Ответ на: комментарий от eve

придется приводить к node_t*, что не очень удобно

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

Или достаточно требовать на вход в прототипе void* вместо node_t*?

bormant ★★★★★
()
Ответ на: комментарий от eve

И? Выход-то какой?

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

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

Singularity 1.0 была завершена в 2007 году. Исследовательский пакет Singularity 1.1 Research Development Kit (RDK) был выпущен под лицензией Shared Source и допускает академическое некоммерческое использование; пакет доступен на CodePlex. 14 ноября 2008 г. был выпущен Singularity RDK 2.0. Дальнейшая разработка прекращена.

SZT ★★★★★
()
Ответ на: комментарий от eve

И поди там вставки неуправляемого c++ кода, я прав? Просто виртуалка без загрузчика, работающего на голом железе не работает...

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

The lowest-level x86 interrupt dispatch code is written in assembly language and C. Once this code has done its job, it invokes the kernel, which runtime system and garbage collector are written in Sing# (an extended version of Spec#, itself an extension of C#) and runs in unprotected mode. The hardware abstraction layer is written in C++ and runs in protected mode.

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

Дальнейшая разработка прекращена.

Вроде бы я peregrine отвечал.

eve
() автор топика
Ответ на: комментарий от peregrine

Работает, причем не только на x86.

eve
() автор топика
Ответ на: комментарий от peregrine

Ну конечно там есть нативный код. Должно же что-то исполнять байткод .NET. Кстати, забавно было смотреть, как эта виртуалка отжирала память просто циклом бездействия.

i-rinat ★★★★★
()
Ответ на: комментарий от eve

Это не intrusive.

Вот если вообще без всего, то не intrusive. Но тогда в таком списке смысла нет, потому что к узлам не прикрепишь данные. Чтобы сделать с struct list что-то полезное, придётся экземпляр этой структуры внедрить в структуру с данными. И вот эта комбинация уже будет intrusive list.

i-rinat ★★★★★
()

покопай в сторону аналогии гарвардской vs манчестерской архитектуры кодаИданных применительно к ДанныеОбслуживанияVSДанныеИнформации

где ДО накладные данные которые в идеале стремятся к нулю чем башковитее примёнёная структура данных при прочих равных

и

ДИ - то что важно - информационное наполнение - ну там котики али делящиеся бактерии в соляном растворе и их фоточки.

qulinxao3 ★★
()

так же терминология баз данных ( ну там инвертированные индексы как пример «повёрнутости» сд)

qulinxao3 ★★
()
Ответ на: комментарий от eve

одна из структур в стартовом посте стремится отделить скелет данных от мяса данных

такое в структурах данных например характерно (было?!) для таблиц кортежей с блобами где удобней не сами блобы в таблице а указатели на иное пространство с блобами.

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

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

qulinxao3 ★★
()

инфо-поля с отрицательным смещением относительно адреса_назначения склето-полей

«хак» для того что бы можно пространственно разнести и унифицировать методы обхода по структуре данных от типа инфо-поля.

Си всёж ассемблер.

qulinxao3 ★★
()

я особо не вникнул, но может это называется линейные структуры данных и иерархические?

da17
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.