如何在配对结构中可移植地保存两个字的内存？

Question

我有一个struct foo总是成对出现的数据结构.现在,每个人都struct foo携带指向另一struct foo对的指针:

struct foo {
    struct foo *other_half;
    /* ... */
};

由于我的程序需要很多(> 1'000'000)struct foo,我迫切希望减小每个程序的大小.有没有办法摆脱other_half指针,并struct foo通过其他方式找到一对的另一半？

Answer 1

考虑struct foo foos[2]两个struct foo对齐2 * sizeof (struct foo)或更大的数组.观察到foos[0]对齐2 * sizeof (struct foo)或更大,而foos[1]仅对齐sizeof (struct foo).您可以使用该信息来确定struct foo*指向这样的对齐struct foo[2]点的随机点是否指向第一个或第二个成员.

要获得充分对齐的内存,请编写自定义分配器或使用C11 aligned_alloc函数.注意,实际上并不需要使存储器完全对齐,只需将我们测试的位other_half清零就足够了.

一个简单的函数实现,找到struct foo给出一半指针的另一半的另一半看起来像这样:

struct foo *other_half(struct foo *half) {
    if ((uintptr_t)half % (2 * sizeof *half) == 0)
        return half + 1;
    else
        return half - 1;
}

然而,如果sizeof (struct foo)不是2的幂,则该函数不是非常有效,因为它涉及慢模运算.为了加快速度,可以考虑其因子分解sizeof (struct foo)形式为2 ⁿ · q.很容易看出,检查是足够的,((uintptr_t)half & (uintptr_t)1 << n) == 0因为它是2 * sizeof (struct foo)2 ^{n + 1}的倍数,因此位置0到n的位被关闭.

在编译时计算n有点棘手,但幸运的是我们只需要1 << n,可以用一点点魔法来计算-sizeof (struct foo) & sizeof (struct foo):

struct foo *other_half(struct foo *half) {
    if ((uintptr_t)half & -sizeof *half & sizeof *half)
        return half - 1;
    else
        return half + 1;
}