将结构指针增加一半的结构大小

Question

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

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

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

这当然会导致一些问题，因为“偏移”值变得不正确，但它并不那么明显，因为数据结构的所有其他使用都有效（没有“真正的”对齐问题）。

这归结为我的问题 - 当偏移量无法表示为元素的整数时，您是否看到一种增加指针的巧妙方法？

找到一种不诉诸过度铸造的方法的奖励积分:)

Answer 1

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

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

无奖励积分的解决方案是将指针转换为 char* 来计算偏移量。您最终将得到以字节为单位的偏移量。 然后您可以使用强制转换添加字节偏移量。 为了最大限度地减少转换，您可以编写一个辅助函数，为节点指针设置正确的值。

如果您想使用 realloc，我没有看到其他解决方案，因为您的初始数组已由 realloc 释放。 字节偏移似乎是唯一的方法。

您可以调用减少的数组，复制节点，然后释放旧数组。 但是当重新分配完成后，您就失去了重新分配的优势。

其他解决方案迫使您更改数据结构。 您可以使用 malloc 独立分配节点，并且减少更简单。 您只需释放不再需要的节点即可。 这似乎是最干净的方式，但你必须重构......

我希望它有帮助。 如果我理解错了请告诉我...

Answer 2

如果您不想投射：

newBuffer[i].pFirstByLevel = newBuffer[i].pFirstByLevel - oldBuffer + newBuffer;            
newBuffer[i].pFirstBySimilarity = newBuffer[i].pFirstBySimilarity - oldBuffer + newBuffer;            
newBuffer[i].pFirstByRank = newBuffer[i].pFirstByRank - oldBuffer + newBuffer;

Answer 3

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

要么

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_tnodes[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[] 数组有零个元素时的大小。