在C语言中复制不确定指针

Question

C11标准规定如下(6.2.4p2)：

对象的生命周期是程序执行期间为其保留存储空间的部分。对象在其生命周期内存在，具有恒定的地址，并保留其上次存储的值。如果对象在其生命周期外被引用，则行为未定义。当指向的对象(或刚好在其之后)到达其生命周期终点时，指针的值变得不确定。

未确定值的定义是(3.19.2)：

既可以是未指定的值，也可以是陷阱表示。

我遇到了这个限制的问题。如果接受复制未确定指针，那么双向链表的小优化就可能实现。该优化依赖于以下不变量：

头元素的prev指针是不确定的。

对于双端列表，空列表的tail指针是不确定的。

除此之外，其他所有内容与普通的双向链表相同。利用这些不变量，可以轻微地优化从前面插入和删除的操作。特别是(代码仅适用于单向列表)：

insertToFront(e)
{
    e->next = head;
    e->prev = NULL;
    if (head) {
        head->prev = e;
    }
    head = e;
}

insertToFrontOptimized(e)
{
    e->next = head;
    if (head) {
        head->prev = e;
    }
    head = e;
}

removeFront()
{
    head = head->next;
    if (head) {
        head->prev = NULL;
    }
}

removeFrontOptimized()
{
    head = head->next;
}

其他操作仍然可以继续工作，例如：

remove(e)
{
    if (e != head) {
        e->prev->next = e->next;
    } else {
        head = e->next;
    }

    if (e->next) {
        e->next->prev = e->prev; // problem here
    }
}

上面的代码存在问题，因为在删除头元素时，它会将新头部的prev指针设置为一个不确定的值。例如，在insertToFrontOptimized()之后，新的prev指针可能是未初始化指针的副本，或者在removeFrontOptimized()之后它可能指向被释放的元素。

但是这只在C语言方面存在问题；列表不变式并没有被破坏，因为允许新头元素的prev指针具有不确定的值。

禁止使用不确定指针的限制是否阻止了这种优化？有没有绕过的方法？

- Ambroz Bizjak

---

但是 head->prev 指向垃圾的问题是什么？你永远不会读取 head->prev，你只会写入它。 - Porkbutts

问题在于remove()函数删除第一个元素时会读取head->prev并将新头部的->prev设置为该值。添加一个检查，只有在不删除第一个元素时才执行此操作，将会降低性能。 - Ambroz Bizjak

Answer 1

如果我理解正确，您担心的是这行代码。

e->next->prev = e->prev; // problem here

调用未定义行为，因为在执行时e->prev可能是不确定的。

即使您的架构没有陷阱表示，担心这一点可能是明智的。 C编译器倾向于将对不确定对象的访问视为未定义行为，即使最近的标准似乎更加微妙。

如果我是你，我会通过使用以下行来安抚自己：

memcpy(&e->next->prev, &e->prev, sizeof(e->prev);

它可能会被编译为与原始赋值相同的指令。唯一的缺点是，根据 memcpy() 的规范，在调用时 &e->next->prev 和 &e->prev 必须是不同的，而赋值 e->next->prev = e->prev; 允许它们完全重叠。

这就是一个需要正式的 C 语义来回答的问题，我所知道的正式语义（KCC、CompCert 等）都允许你将一个不确定的变量复制到另一个完全相同类型的变量上。

- Pascal Cuoq

---

谢谢提供的信息。不过我认为将指针包装在结构体中也可以解决问题（可能更加优雅，而且不依赖于memcpy优化），因为结构体保证不会有陷阱表示。抱歉，我被迫接受Roman的答案，因为那是我解决问题的方法 ;) - Ambroz Bizjak

Answer 2

为什么你需要操作未定义指针？考虑以下情况：

remove(e)
{
    if (e != head) {
        e->prev->next = e->next;
        if (e->next) {
            e->next->prev = e->prev; // NO problem here
        }
    } else {
        head = e->next;
        // OK, new head->prev is undefined now. Who cares?
    }
}

- Roman Nikitchenko

---

谢谢，这就是我为我的代码所做的，其他操作也可以像这样修复，而不需要额外的分支。多么显而易见 :) - Ambroz Bizjak