c - 解释使用 union 的循环双向链表实现

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) 为什么我们需要一个 union ？也是这样，以这种特定的方式吗？

(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:此列表中的更多信息:

“列表预计会被初始化，以便头指针和尾指针都指向列表本身。以这种方式初始化列表可以简化在列表中添加和删除节点的过程。”

初始化如下:

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);