3

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
    }
}

上面这行是有问题的，因为当移除 head 元素时，它会将prev新 head 的指针设置为不确定的值。例如，新prev指针可以是 a 之后的未初始化指针的副本insertToFrontOptimized()，或者它可以指向 a 之后的已释放元素removeFrontOptimized()。

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

对使用不确定指针的限制是否会阻止这种优化？有办法吗？

4

2 回答 2

3

如果我理解正确，您担心线路

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

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

即使您的体系结构没有陷阱表示，也最好担心这一点。C 编译器倾向于将对不确定对象的访问视为未定义的行为，即使最近的标准似乎比这更细微。

如果我是你，我会用这行代替来安慰自己：

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

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

这就是说，这是一个真正有助于回答 C 的形式语义的问题，而我所知道的形式语义（KCC，CompCert，...）都允许您将不确定的变量复制到另一个确切的变量上同类型。

于 2013-05-20T21:26:12.710 回答
3

为什么需要触摸未定义的指针？考虑这个变体：

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?
    }
}
于 2013-05-20T21:59:26.887 回答