3

我刚刚处理了一个有趣的问题，但我看不出有什么巧妙的方法来解决它。

我有两个表示复杂图形的基本数据结构，声明如下：

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 上：“这是两个指针之间的减法运算返回的类型。这是一个有符号整数类型，因此可以转换为兼容的基本数据类型。两个指针的减法仅被授予具有有效的定义值对于指向同一数组元素的指针（或者对于刚刚超过数组中最后一个元素的元素）。对于其他值，行为取决于系统特性和编译器实现。

当您使用 realloc 时，您不在这种情况下。所以你的偏移量不会是一个整数。这解释了你的问题。

没有奖励积分的解决方案是将您的指针转换为 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 回答
1

你的语法搞砸了。结构标记名称位于结构定义之前；之后的任何内容都是声明。

任何一个

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

或者

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

这就是你要写的。

这是一种常见的解决方法，但需要对现有代码进行一些重组。

/* same node_t as before */
typedef struct _node_t {...} node_t;
/* same graph_t as before */
typedef struct _graph_header_t {...} graph_header_t;
/* new type */
typedef struct _graph_t {
    graph_header_t header;
    node_t nodes[1];
} graph_t;

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

它允许访问pNewBuffer->nodes[i]for 0 <= i < nMaxNodes，无需在任何地方进行强制转换。

现在，如果您可以声明，这会更好node_t nodes[0]，在计算分配大小时避免一对一，但即使一些编译器对此感到满意，我不相信它被标准所接受。

C99 引入“灵活的数组成员”

typedef struct _graph_t {
    graph_header_t header;
    node_t nodes[];
} graph_t;

这几乎是同一件事，但由实际标准定义。一些例外：灵活的数组成员只能放在结构的末尾，并且sizeof(pNewBuffer->nodes)是无效的（尽管 GCC 返回 0）。否则，如果数组有零个元素，sizeof(graph_t)则等于任何大小。node_t[]

于 2009-07-10T20:54:34.727 回答