解释使用联合的循环双向链表实现

Question

我在解释这个双向链表时遇到了一些问题：

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_node 元素的 data 是否匹配，比如说，数字 3。我可以通过类型转换来做到这一点 node （当前是指向类型 sys_dnode_t 的指针）指向指向类型 data_node?

的指针

现在，在代码中，这已经完成，就像：

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

这让我很困惑。我可能遗漏了一些代码来解决这个问题，所以如果您需要更多信息，请告诉我。我们可以类型转换一个 node 指针指向某个包含 node 的结构，然后访问该结构的其他数据吗？这是如何工作的？

编辑 1： 关于此列表的更多信息：

"The lists are expected to be initialized such that both the head and tail pointers point to the list itself. Initializing the lists in such a fashion simplifies the adding and removing of nodes to/from the list."

初始化如下：

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

Answer 1

(i) Why would we need a union here? That too, in this specific way?

很方便，因为这个列表是循环的。链表结构是链表中的一个伪节点。因此，节点可以看作是一个链表结构，也可以看作链表中的节点。

另一个定义可能是：

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) How come both the list and node of the list are going to be pointers of same type? (see typedef declaration)

这样做也很方便，因为这些指针指向内存中的同一个结构。

(iii) If I declare a list of such a type, ie. the data_node items will be the elements of the sys_dlist_t type... Can I do that by typecasting node (which is currently a pointer to type sys_dnode_t) to a pointer to type 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);

解释使用联合的循环双向链表实现

Interpreting circular doubly linked list implementation which uses union

c

pointers

doubly-linked-list