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

prevhead 要素を削除すると、新しい head のポインタが不確定な値に設定されるため、上記の行には問題があります。たとえば、新しいprevポインタは、 の後の初期化されていないポインタのコピーであるinsertToFrontOptimized()か、 の後の解放された要素を指している可能性がありremoveFrontOptimized()ます。

しかし、これは C 言語の観点からのみ問題があります。prev新しい head 要素のポインターは不定値を持つことが許可されているため、リストの不変条件は壊れていません。

不確定ポインタの使用に関する制限は、この最適化を妨げますか? 回避策はありますか？

4

2 に答える 2

3

私の理解が正しければ、あなたはラインを心配しています

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 の正式なセマンティクスで答えることが本当に役立つ 1 つの質問であり、私が知っている正式なセマンティクス (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 に答える