3

対処すべき興味深い問題が発生しましたが、それをうまく解決する方法がわかりません。

複雑なグラフを表す 2 つの基本データ構造があり、次のように宣言されています。

typedef struct _node_t node_t;
typedef struct _graph_t graph_t;

struct {
    /* Data fields omitted */
    node_t * pNextByLevel;
    node_t * pNextByProximity;
    node_t * pNextByRank;
} node_t;

struct {
    /* Data fields omitted */
    size_t nNodes;
    size_t nMaxNodes;
    node_t * pFirstByLevel;
    node_t * pFirstByProximity;
    node_t * pFirstByRank;
} graph_t;

実際のノードはヘッダーの直後に配置されるため、通常、「graph_t」は次のように作成されます

graph_t * pNewBuffer = calloc(1, sizeof(graph_t) + nMaxNodes * sizeof(node_t));
pNewBuffer->nMaxNodes = nMaxNodes;

ノードの「生の」配列には、次のようにアクセスします

node_t * pNewBufferNodes = (node_t *) &pNewBuffer[1];

現在、ノード数を削減するバッファ上で動作するサポート関数があります。次のようになります。

status_t reduce(graph_t** ppBuffer)
{
    graph_t * pReplacement, * pOld = *ppBuffer;
    size_t nRequired; 
    node_t * oldBuffer = (node_t *) &pOld[1];

    /* complex calculation ultimately computes 'nRequired' */

    pReplacement = realloc(pOld, sizeof(graph_t) + nRequired * sizeof(node_t));

    if ( pReplacement != pOld )
    {
        int i;
        node_t * newBuffer = (node_t *) &pReplacement[1];
        ptrdiff_t offset = newBuffer - oldBuffer;

        for ( i = 0; i < requiredNodes; i++ )
        {
            newBuffer[i].pFirstByLevel += offset;
            newBuffer[i].pFirstBySimilarity += offset;
            newBuffer[i].pFirstByRank += offset;
        }
        *ppBuffer = pReplacement;
    }
}

さて、これは長い間美しく機能しています。上記のエラーは、私が記憶から書いているという事実から来ています。アイデアを説明しようとしているだけです。

今私を困惑させているのは、新しいモジュールからリダクション関数を使用すると、入力が「適切に」調整されないことです。アドレスを調べると、次のプロパティに注意してください。

 ((char *) newBuffer - (char *) oldBuffer) % sizeof(graph_t) == 0
 ((size_t) newBuffer) % sizeof(node_t) == 0
 ((size_t) oldBuffer) % sizeof(node_t) == 0
 ((char *) newBuffer - (char *) oldBuffer) % sizeof(node_t) == sizeof(node_t) / 2

もちろん、「オフセット」値が正しくなくなるため、少し問題が発生しますが、データ構造の他のすべての使用が機能するため、それほど明白ではありません (「実際の」アライメントの問題はありません)。

私の質問に要約すると、オフセットを要素の整数として表現できない場合に、ポインターをインクリメントするきちんとした方法がわかりますか?

過度のキャストに頼らない方法を見つけるためのボーナスポイント:)

4

3 に答える 3

3

ptrdiff_t について: 「これは、2 つのポインター間の減算操作によって返される型です。これは符号付き整数型であり、互換性のある基本データ型にキャストできます。2 つのポインターの減算は、有効な定義済みの値を持つ場合にのみ許可されます。同じ配列の要素へのポインター (または配列の最後の要素の直後の要素) の場合。他の値の場合、動作はシステムの特性とコンパイラの実装によって異なります。"

realloc を使用しているため、この場合ではありません。したがって、オフセットはintではありません。それはあなたの問題を説明しています。

ボーナス ポイントのない解決策は、ポインターを char* にキャストしてオフセットを計算することです。オフセットはバイト単位になります。その後、キャストを使用してバイト オフセットを追加できます。キャストを最小限に抑えるために、ノード ポインターに正しい値を設定するヘルパー関数を作成できます。

realloc を使用する場合、最初の配列が realloc によって解放されたため、別の解決策はありません。バイトオフセットが唯一の方法のようです。

削減された配列を呼び出し、ノードをコピーしてから、古い配列を解放できます。ただし、再割り当てが適切に行われると、再割り当ての利点が失われます。

他のソリューションでは、データ構造を変更する必要があります。malloc を使用してノードを個別に割り当てることができ、リダクションがより簡単になります。不要になったノードを解放するだけです。それは最もクリーンな方法のようですが、リファクタリングする必要があります...

お役に立てば幸いです。誤解していたら教えて...

于 2009-07-10T16:10:31.667 に答える
1

キャストしたくない場合：

newBuffer[i].pFirstByLevel = newBuffer[i].pFirstByLevel - oldBuffer + newBuffer;            
newBuffer[i].pFirstBySimilarity = newBuffer[i].pFirstBySimilarity - oldBuffer + newBuffer;            
newBuffer[i].pFirstByRank = newBuffer[i].pFirstByRank - oldBuffer + newBuffer;
于 2009-07-10T17:14:36.823 に答える