Интерпретация реализации циклического двусвязного списка, использующего объединение

У меня возникли проблемы с интерпретацией этого двусвязного списка:

struct _dnode {
    union {
        struct _dnode *head;
        struct _dnode *next;
    };
    union {
        struct _dnode *tail;
        struct _dnode *prev;
    };
};

typedef struct _dnode sys_dlist_t;
typedef struct _dnode sys_dnode_t;

И в этом списке определены дополнительные функции, например, определение того, является ли данный узел головным в списке:

static inline int sys_dlist_is_head(sys_dlist_t *list, sys_dnode_t *node)
{
    return list->head == node;
}

Теперь мои вопросы -

(i) Зачем нам нужен союз здесь? Тоже таким специфическим образом?

(ii) Почему list и node в списке будут указателями одного и того же типа? (см. декларацию typedef)

(iii) Если я объявлю список такого типа, т.е. элементы data_node будут элементами типа sys_dlist_t:

struct data_node{
    sys_dnode_t node;
    int data = 0;
} data_node[2];

и я объявляю узел так, что:

sys_dnode_t *node = NULL;

а затем, если я хочу выполнить итерацию по своему списку, чтобы проверить, соответствует ли data элемента data_node, скажем, числу 3. Могу ли я сделать это, приведя node (который в настоящее время является указателем на тип sys_dnode_t) к указателю на тип data_node?

Теперь в коде это было сделано, и это выглядит так:

if (((struct data_node *)node)->data == 3) {
    break;
}

Это сбивает меня с толку. Возможно, я пропустил какой-то код, чтобы понять это, поэтому, пожалуйста, сообщите мне, если вам нужна дополнительная информация. Можем ли мы привести указатель типа node к некоторой структуре, содержащей node, а затем получить доступ к другим данным структуры? Как это работает?

EDIT 1: Еще немного информации в этом списке:

"Ожидается, что списки будут инициализированы таким образом, что оба указателя: начало и конец указывают на сам список. Инициализация списков таким образом упрощает добавление и удаление узлов в списке и из него."

Инициализация выглядит следующим образом:

static inline void sys_dlist_init(sys_dlist_t *list)
{
    list->head = (sys_dnode_t *)list;
    list->tail = (sys_dnode_t *)list;
}

person nj2237    schedule 04.04.2018    source источник
comment
Для случая iii структура data_node — это способ эмулировать наследование в C.   -  person Some programmer dude    schedule 04.04.2018
comment
Вы уверены, что в sys_dlist_is_head должно быть сравнение с tail?   -  person freestyle    schedule 04.04.2018
comment
@freestyle, ты прав. позвольте мне исправить это   -  person nj2237    schedule 04.04.2018
comment
В кольцевом двусвязном списке это так удобно делать, так как можно посмотреть на структуру списка как на псевдоузел. Но из вашего описания я не понимаю, является ли этот список круговым. Можете ли вы показать инициализацию списка?   -  person freestyle    schedule 04.04.2018
comment
@freestyle Я добавил часть инициализации, поправьте меня, если я ошибаюсь, но это похоже на круговую dll   -  person nj2237    schedule 04.04.2018
comment
Да, он должен быть круглым.   -  person freestyle    schedule 04.04.2018
comment
i: есть тонкое отличие от повторного использования и неправильного использования. В 80-х идея повторного использования заключалась в том, чтобы писать как можно меньше кода. Однако список не является узлом, но список содержит узлы или список содержит ссылки на головной и хвостовой узлы, поэтому в современных реализациях списков понятия (классы/структуры) списка и узлов обычно хранятся разделенными, с большим количеством кода написанный, но не написанный обескураживающий код (читай: приведение типов). Тот факт, что узел и список имеют одинаковую форму (два указателя на узлы), недостаточен, чтобы позволить двум типам свернуть в один, сегодня, как правило, ИМХО.   -  person Sigi    schedule 11.04.2018


Ответы (1)


(i) Зачем нам нужен союз здесь? Тоже таким специфическим образом?

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

Другое определение может быть:

union _dnode {
    struct {
        union _dnode *head;
        union _dnode *tail;
    };
    struct {
        union _dnode *next;
        union _dnode *prev;
    };
};

typedef union _dnode sys_dlist_t;
typedef union _dnode sys_dnode_t;

(ii) Почему и список, и узел списка будут указателями одного и того же типа? (см. объявление typedef)

Это тоже удобно делать, так как эти указатели ссылаются на одну и ту же структуру в памяти.

(iii) Если я объявлю список такого типа, т.е. элементы data_node будут элементами типа sys_dlist_t... Могу ли я сделать это, приведя узел (который в настоящее время является указателем на тип sys_dnode_t) к указателю на тип data_node?

Можно, потому что указатель на первое поле в структуре и указатель на структуру совпадают.

Поле узла не обязательно должно быть первым, но тогда простое приведение типов не может этого сделать. Например:

struct list_elem {
    int foo;
    char *bar;
    ...
    sys_dnode_t siblings;
};

sys_dnode_t *node;
struct list_elem *elem;

elem = (struct list_elem *)((char *)node - offsetof(struct list_elem, siblings));

или если вы определяете макрос:

#define objectof(_ObjectT,_Field,x) \
    ((_ObjectT *)((char *)(x) - offsetof(_ObjectT,_Field)))

elem = objectof(struct list_elem, siblings, node);
person freestyle    schedule 04.04.2018
comment
вау, спасибо за такое подробное объяснение, теперь мне все ясно. Так что, если это не первое поле, мне нужно будет использовать offsetof при приведении его к типу, верно? - person nj2237; 04.04.2018
comment
да. Кроме того. Если это первое поле, то offsetof тоже будет работать, потому что offsetof будет 0. - person freestyle; 04.04.2018