解释使用联合的循环双链表实现 [英] Interpreting circular doubly linked list implementation which uses union

问题描述

我在解释这个双向链接列表时遇到了一些麻烦：

I am having some trouble interpreting this doubly-linked list:

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;

在此列表上定义了进一步的功能，例如，查找给定节点是否为列表：

And further functions are defined on this list, like, for example finding if given node is head of the list:

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

现在，我的问题是-

（i）为什么我们这里需要工会？

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

（ii）列表和 node 将会是相同类型的指针吗？ （请参见 typedef 声明）

(ii) How come both the list and node of the list are going to be pointers of same type? (see typedef declaration)

（iii）如果我声明了此类列表，即 data_node 项目将是 sys_dlist_t 类型的元素：

(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:

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

，然后声明一个节点，使得：

and I declare a node such that:

sys_dnode_t *node = NULL;

然后如果我要遍历列表以检查数据 data_node 元素的匹配说一个数字3。我可以通过类型转换 node （当前是指向 sys_dnode_t 的指针）到指向 data_node 的指针？

and then if I want to iterate over my list to check if the data of the data_node element matches say, a number 3. Can I do that by typecasting node (which is currently a pointer to type sys_dnode_t) to a pointer to type data_node?

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

Now, in the code, this has been done, and it is like:

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

这让我感到困惑。我可能错过了一些代码来解决这个问题，所以请告诉我是否需要更多信息。我们是否可以强制转换一个 node 指针以指向某个包含 node 的结构，然后访问该结构的其他数据？

This bewilders me. I may have missed some code to figure this out, so please tell me if you need more information. Can we typecast a node pointer to point to some struct that contains node and then access other data of the struct? How does this work?

编辑1：
该列表上的更多信息：

EDIT 1: Few more info on this list:

应该初始化列表，以便头和尾指针都指向列表本身。以这种方式初始化列表可以简化向列表中添加节点或从列表中删除节点的过程。 。

初始化如下：

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

推荐答案

（i）为什么我们这里需要工会？

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

那么方便，因为该列表是循环的。列表结构是列表中的伪节点。因此，可以将节点视为列表结构和列表中的节点。

So convenient, since this list is cyclic. The list structure is a pseudo node in the list. Therefore, the node can be viewed as a list structure and as node in a list.

另一个定义可能是：

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声明）

(ii) How come both the list and node of the list are going to be pointers of same type? (see typedef declaration)

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

This is also convenient to do, since these pointers refer to the same structure in memory.

（iii）如果我声明了这种类型的列表，即data_node项目将成为sys_dlist_t类型的元素...我可以通过将节点（当前是指向sys_dnode_t类型的指针）的类型转换为指向data_node类型的指针的方法来做到这一点？

(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?

可以，因为指向结构中第一个字段的指针和指向结构的指针是相同的。

You can, because the pointer to the first field in the structure and the pointer to the structure are the same.

A node字段不必是第一个，但是简单的类型转换不能做到这一点。例如：

A node field need not be the first, but then a simple typecasting can not do that. For example:

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

这篇关于解释使用联合的循环双链表实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！