在现代C (C99/C11联合)中使用位字段作为排序键

Question

Requirement：

对于我的小图形引擎，我需要一个数组的所有对象来绘制。出于性能原因，该数组需要对属性进行排序。简言之：

1. 在每个结构中存储大量属性，将结构添加到结构数组中。
2. 对数组进行有效排序
3. 遍历数组并根据属性执行操作(模式设置和绘图)

Approach：联合中的位字段(即:让编译器为我做掩蔽和移位)

我认为我有一个很好的计划来实现这一点，基于本文：http://realtimecollisiondetection.net/blog/?p=86。其思想如下:每个属性都是一个位字段，可以读取和写入(步骤1)。写入后，排序过程将位字段结构视为整数，并对其进行排序(步骤2)。之后(步骤3)，将再次读取位字段。

有时代码会显示1000多个单词，一个高级视图：

union key {
    /* useful for accessing */
    struct {
        unsigned int some_attr : 2;
        unsigned int another_attr : 3;
        /* ... */
    } bitrep;

    /* useful for sorting */
    uint64_t intrep;
};

我只需确保位表示与整数表示一样大(在本例中为64位)。我的第一个方法是这样的：

union key {
    /* useful for accessing */
    struct {
        /* generic part: 11 bits */
        unsigned int layer : 2;
        unsigned int viewport : 3;
        unsigned int viewportLayer : 3;
        unsigned int translucency : 2;
        unsigned int type : 1;

        /* depends on type-bit: 64 - 11 bits = 53 bits */
        union {
            struct {
                unsigned int sequence : 8;
                unsigned int id : 32;
                unsigned int padding : 13;
            } cmd;
            struct {
                unsigned int depth : 24;
                unsigned int material : 29;
            } normal;
        };
    };

    /* useful for sorting */
    uint64_t intrep;
};

请注意，在本例中，有一个名为type的决策位字段。在此基础上，将填充cmd结构或普通结构，就像前面提到的文章一样。然而，这个严重地失败了。在OSX10.9 (x86 macbook )上使用clang3.3，键联合是16字节，而应该是8字节。

由于无法强迫clang更好地打包结构，我采取了基于其他堆栈溢出答案和预处理器的另一种方法，以避免我不得不重复：

/* 2 + 3 + 3 + 2 + 1 + 5 = 16 bits */
#define GENERIC_FIELDS \
 unsigned int layer : 2; \
 unsigned int viewport : 3; \
 unsigned int viewportLayer : 3; \
 unsigned int translucency : 2; \
 unsigned int type : 1; \
 unsigned int : 5;

/* 8 + 32 + 8 = 48 bits */
#define COMMAND_FIELDS \
 unsigned int sequence : 8; \
 unsigned int id : 32; \
 unsigned int : 8;

/* 24 + 24 = 48 bits */
#define MODEL_FIELDS \
 unsigned int depth : 24; \
 unsigned int material : 24;

struct generic {
    /* 16 bits */
    GENERIC_FIELDS
};

struct command {
    /* 16 bits */
    GENERIC_FIELDS

    /* 48 bits */
    COMMAND_FIELDS
} __attribute__((packed));

struct model {
    /* 16 bits */
    GENERIC_FIELDS

    /* 48 bits */
    MODEL_FIELDS
} __attribute__((packed));

union alkey {
    struct generic gen;
    struct command cmd;
    struct model mod;
    uint64_t intrep;
};

不包括__attribute__((packed))，command和model结构是12个字节。但是对于__attribute__((packed))，它们是8个字节，这正是我想要的！因此，我似乎找到了解决办法。然而，我在比特菲尔德的小经验让我学会了警惕。所以我有几个问题：

我的问题是：

• 我能让这个变得更干净吗(例如:更像我的第一个大联合-内部-结构-在联合)，仍然保持8字节的键，为了快速排序？
• 有什么更好的方法来实现这一点吗？
• 这安全吗？这在x86/ARM上会失败吗？(非常异国情调的架构并不是什么大问题，我的目标是两个最流行的架构)。如何设置一个位字段，然后发现一个相邻的字段已经写入。不同的编译器会在这方面大相径庭吗？
• 我能从不同的编译器那里得到什么问题？目前我的目标是-std=c11.的clang 3.3+和gcc 4.9+不过，如果我将来也能使用MSVC的话，那就太好了。

我查过的相关问题和网页：

• Variable-sized bitfields with aliasing
• Unions within unions
• 对于那些(像我一样)为不对字节和不对齐的位域所发生的事情而绞尽脑汁的人来说，不要再看下去了：http://mjfrazer.org/mjfrazer/bitfields/。

遗憾的是，没有任何答案让我一路顺风。

编辑：在实验中，设置一些值并读取整数表示。我注意到了一些我已经忘记的事情:痴呆症。这又打开了一罐虫子。是否可以使用位字段来做我想做的事，还是必须进行位转换操作？

Answer 1

位字段的布局高度依赖于实现(=编译器)。本质上，编译器可以自由地将连续的位字段放置在相同的字节/单词中，如果它认为合适的话。因此，如果没有像您提到的packed属性这样的扩展，您就永远无法确定您的位字段被压缩到一个单词中。

然后，如果比特字段没有压缩到一个单词中，或者您只有一些不使用的备用位，那么您可能会遇到更大的麻烦。这些所谓的填充位可以具有任意的值，因此排序的思想永远不能在可移植的设置中工作。

由于所有这些原因，位字段在实际代码中相对较少使用。您可以更经常地看到的是在您需要的uint64_t中使用宏。对于您现在拥有的每个位字段，您将需要两个宏，一个用于提取位元，另一个用于设置它们。这样的代码就可以移植到所有具有C99/C11编译器的平台上，而不会出现问题。

小问题：

在union的声明中，最好先使用基本的整数字段。union的默认初始化程序使用第一个字段，因此这将确保通过这样的初始化器将union初始化为所有位零。struct的初始化程序将只保证将各个字段设置为0，如果存在填充位，则将不具体。