结构指针转换

Question

我正在尝试实现这样的链表：

typedef struct SLnode
{
    void* item;
    void* next;
} SLnode;

typedef struct DLnode
{
    void* item;
    void* next;
    struct DLnode* prev;
} DLnode;

typedef struct LinkedList
{
    void* head; /*SLnode if doubly_linked is false, otherwise DLnode*/
    void* tail; /* here too */
    bool doubly_linked;
} LinkedList;

我想这样访问它：

void* llnode_at(const LinkedList* ll, size_t index)
{
    size_t i;
    SLnode* current;

    current = ll->head;

    for(i = 0; i < index; i++)
    {
        current = current->next;
    }

    return current;
}

所以我的问题是：

我是否可以在这些结构之间转换只要我只访问公共成员？我读到关于这个的不同意见。
我也可以制作相应类型的下一个指针吗？或者如果它真的是 DLnode，那么在我的示例函数中使用它会是 UB 吗？

如果这不起作用，还有其他方法可以做这样的事情吗？我读到 union 可能有效，但这段代码在 C89 中也应该运行，并且 afaik 读取与上次写入的不同的 union 成员是 UB。

Answer 1

只要您使用 union 来包含两个结构，您就可以安全地执行此操作：

union Lnode {
    struct SLnode slnode;
    struct DLnode dlnode;
};

当前 C standard 的第 6.5.2.3 节以及 C89 标准的第 6.3.2.3 节规定如下：

6 One special guarantee is made in order to simplify the use of unions: if a union contains several structures that share a common initial sequence (see below), and if the union object currently contains one of these structures, it is permitted to inspect the common initial part of any of them anywhere that a declaration of the completed type of the union is visible. Two structures share a common initial sequence if corresponding members have compatible types (and, for bit-fields, the same widths) for a sequence of one or more initial members.

因为两个结构的前两个成员属于同一类型，您可以使用任一联合成员自由访问这些成员。

Answer 2

因此您正在尝试在 C 中构建子classes。一种可能的方法是使基本结构成为子结构的第一个元素，因为在这种情况下，C 标准明确允许回退在这两种类型之间来回：

6.7.2.1 Structure and union specifiers

§ 13 ... A pointer to a structure object, suitably converted, points to its initial member (or if that member is a bit-field, then to the unit in which it resides), and vice versa...

缺点是您需要转换为基础 class 才能访问其成员：

示例代码：

typedef struct SLnode
{
    void* item;
    void* next;
} SLnode;

typedef struct DLnode
{
    struct SLnode base;
    struct DLnode* prev;
} DLnode;

然后您可以这样使用它：

    DLnode *node = malloc(sizeof(DLnode));
    ((SLnode*) node)->next = NULL;             // or node->base.next = NULL
    ((SLnode *)node)->item = val;
    node->prev = NULL;

Answer 3

C 标准应该允许您描述的内容。 Common Initial Sequence 规则的混乱源于一个更大的问题：标准未能指定何时使用明显派生自另一个的指针或左值被认为是对原始值的使用。如果答案是 "never"，那么 non-character 类型的任何结构或联合成员都将毫无用处，因为该成员将是一个左值，其类型对于访问结构或联合无效。这种观点显然是荒谬的。如果在结构或联合类型上的答案是 "only when it is formed by directly applying "." 或 "->"，或者指向此类类型的指针，那么在结构和联合成员上使用 "&" 的能力就会变得毫无用处。我我会认为这种观点不那么荒谬。

我认为很明显，为了有用，必须将 C 语言视为至少在某些情况下允许使用派生的左值。您的代码或大多数依赖通用初始序列规则的代码是否可用取决于这些情况。

如果代码不能可靠地使用派生左值来访问结构成员，则该语言将相当愚蠢。不幸的是，尽管这个问题在 1992 年就很明显（它构成了当年发布的缺陷报告 #028 的基础），委员会并没有解决根本问题，而是根据完全荒谬的逻辑得出了正确的结论，并且因为已经消失并以 "Effective Types" 的形式添加了不必要的复杂性，而无需费心实际定义 someStruct.member.

的行为

因此，如果不依赖于比字面阅读标准实际保证的行为更多的行为，则无法编写任何使用结构或联合做任何事情的代码，无论此类访问是通过强制 void* 或指向正确成员类型的指针。

如果有人将 6.5p7 的意图解读为以某种方式允许使用派生自特定类型之一的左值的操作访问该类型的对象，至少在不涉及实际别名的情况下（注意一个巨大的延伸，给定脚注 #88 "The intent of this list is to specify those circumstances in which an object may or may not be aliased."），并认识到别名需要在存在另一个引用 来自 X 的时候使用引用 X 访问存储区域没有明显派生，将来会用于以冲突的方式访问存储，那么尊重该意图的编译器应该能够毫无困难地处理像您这样的代码。

不幸的是，gcc 和 clang 似乎都将 p6.5p7 解释为说从另一种类型派生的左值通常应该被假定为无法实际识别前一种类型的对象，即使在派生是完全可见。

给出类似的东西：

struct s1 {int x;};
struct s2 {int x;};
union u {struct s1 v1; struct s2 v2;};

int test(union u arr[], int i1, int i2)
{
    struct s1 *p1 = &arr[i1].v1;
    if (p1->x)
    {
        struct s2 *p2 = &arr[i2].v2;
        p2->x=23;
    }
    struct s1 *p3 = &arr[i1].v1;
    return p3->x;
}

在访问 p1->x 时，p1 显然是从联合类型的左值派生的，因此应该能够访问这样的对象，并且唯一的其他现有引用将曾经用于访问存储的是对该联合类型的引用。同样，当 p2->x 和 p3->x 被访问时。不幸的是，gcc 和 clang 都将 N1570 6.5p7 解释为它们应该忽略联合和指向其成员的指针之间的关系的指示。如果不能依赖 gcc 和 clang 有效地允许像上面这样的代码访问相同结构的公共初始序列，我也不相信它们能够可靠地处理像你这样的结构。

除非或直到标准被更正以说明在什么情况下可以使用派生左值来访问结构或联合的成员，目前还不清楚任何对结构或联合做任何远程异常的代码都应该特别是预计在 gcc 和 clang 的 -fstrict-aliasing 方言下工作。另一方面，如果人们认识到左值派生的概念是双向工作的，那么编译器可能有理由假设一个结构类型的指针不会以对另一个引用进行别名的方式使用，即使如果指针在使用前被转换为第二种类型。因此，我建议如果标准曾经修正规则，使用 void* 不太可能运行陷入麻烦。

结构指针转换

Struct pointer casts

c

struct

casting

undefined-behavior

c89