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

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[2] 的随机 struct foo* 是否指向第一个或第二个成员。

要获得足够对齐的内存，请编写自定义分配器或使用 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;
}

Answer 2

另一种设计，技巧较少，但每个 foo 使用单字节；或位，如果您将值与其他字段打包在一起。

#include 
#include 

struct foo {
    char Index; // can be packed together with some other field
    /* ... */
};

typedef struct foo pair[2];

void init_pair(pair *p){
    for(size_t i = 0; i < sizeof(*p); i++){
        (*p)[i].Index = (char)(i);
    }
}

struct foo *pair_index(struct foo *piece, size_t index){
    return &piece[index - (size_t)piece->Index];
}

struct foo *pair_other(struct foo *piece){
    return pair_index(piece, piece->Index ^ 0x01);
}

示例：

int main(int argc, char const *argv[])
{
    pair p;
    init_pair(&p);

    struct foo *first = &(p[0]);
    struct foo *second = &(p[1]);

    printf("%p %p\n", pair_index(first, 0), pair_index(first, 1));
    printf("%p %p\n", pair_index(second, 0), pair_index(second, 1));
    printf("%p %p\n", pair_other(second), pair_other(first));
    return 0;
}

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

How to portably save two words of memory in paired structures?

c

bit-manipulation

pointer-arithmetic