使用结构体指针增加一半的结构体大小

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;

“raw”节点数组可以通过以下方式访问

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

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

这归结为我的问题 - 当偏移量不能表示为整数个元素时，您是否看到了一种简洁的方法来增加指针？

如果找到一种不需要过多转换的方法，将获得额外的奖励分数 :)。

- Christoffer

---

我对oldBuffer和newBuffer在转换为size_t时都是sizeof(node_t)的倍数，但它们之间的差异却不是倍数感到困惑。通常情况下，任何缓冲区地址都没有理由成为sizeof(node_t)的倍数 - 结构体的对齐要求通常是所有成员中最大的对齐要求，而不是总大小。 - Steve Jessop

“这个工作很好很长时间”纯粹是运气。正如onebyone所说，两个缓冲区的地址为size_t（node_t）的倍数并没有理由，它只需要是对齐要求的倍数。请注意，除非graph_t的对齐要求与node_t的要求相同或更严格，否则您分配事物的方式也无法保证node_t数组的对齐性。 - Michael Burr

稍作更正：对于分配，它被指定为与结构体大小小于其的任何类型的最大对齐要求对齐，它不必实际上是成员。我说“指定”而不是“保证”，因为据我所知，Linux内核正在与gcc争论到底由谁来实际执行此操作。但如果node_t的sizeof为16，则在某个特定平台上，所有足够大的分配都以16字节对齐并不是不可行的。当然，这可能是由于分配器的工作方式，而不是因为有一个16字节的类型。 - Steve Jessop

Answer 1

关于ptrdiff_t：这是两个指针相减运算返回的类型。这是一种有符号整数类型，因此可以转换为兼容的基本数据类型。两个指针的减法只有在指向同一个数组的元素时才能保证具有有效的定义值(或者是数组中最后一个元素的下一个元素)。对于其他值，行为取决于系统特性和编译器实现。

由于您使用了realloc，所以您不在这种情况下。因此，您的偏移量不会是一个int。这解释了你的问题。

没有奖励点的解决方案是将指针强制转换为char*以计算偏移量。你最终会得到一个字节偏移量。然后，您可以使用强制转换添加字节偏移量。为了最小化强制转换，您可以编写一个辅助函数来为节点指针设置正确的值。

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

您可以calloc您的缩小数组，复制节点，然后释放旧数组。但是，当重新分配在原地完成时，您失去了realloc的优势。

其他解决方案强制您更改数据结构。您可以使用malloc独立分配节点，并且缩小操作更加简单。您只需要释放不再需要的节点即可。这似乎是最干净的方法，但您必须进行重构...

希望可以帮到您。如果我有误解，请告诉我...

- neuro

---

啊，当然！你对于ptrdiff_t问题是完全正确的。 - Christoffer

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;

- Dingo

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]，其中0 <= i < nMaxNodes，无需进行任何强制转换。

现在，如果您可以声明node_t nodes[0]，计算分配大小时避免了 off-by-one，这将更好，但即使有些编译器可以接受它，我不认为它被标准所接受。

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

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

这与实际标准定义的基本相同。一些例外情况：灵活的数组成员只能放置在结构的末尾，sizeof(pNewBuffer->nodes)是无效的（虽然GCC返回0）。否则，sizeof(graph_t)等于如果node_t[]数组有零个元素，则大小将是多少。

- ephemient

---

是的，我更喜欢使用灵活的C数组，但这个特定的模块需要是C89：( 不过，我不理解你关于typedef的评论，实际上这些是在不同的文件中声明的（typedef在头文件中，结构体声明在C文件中）。 - Christoffer

我只是在评论你的真实代码必须写成struct _foo_t {...}而不是像你在这里写成的struct {...} _foo_t。 - ephemient