基于两种可能结构的未知空指针的访问类型标志？

Question

我目前正在用 C 编写自己的八叉树。该树将包含数十亿个对象，因此内存效率是关键。为了实现这一点，我目前使用一个带有标志和联合的结构，但我认为它不干净并且它在内部节点上浪费 space 因为我只需要一个 8 位标志但内存被保留用于64 位索引。我目前的代码如下：

typedef struct _OctreeNode
{
    uint64_t location_code;
    union
    {
        uint8_t child_exists;
        uint64_t object_index;
    } data;
    uint8_t type;
} OctreeNode;

我想把它分成两个不同的结构。一个叶子节点和一个内部节点。如下：

typedef struct _OctreeInnerNode
{
    uint64_t location_code;
    uint8_t child_exists;
    uint8_t type;
} OctreeInnerNode;

typedef struct _OctreeLeafNode
{
    uint64_t location_code;
    uint64_t object_index;
    uint8_t type;
} OctreeLeafNode;

现在我的基于位置代码哈希的无序地图出现了问题。它使用 void 指针，因此存储两个不同的结构不是问题。我知道有一种可能性是让标志成为第一个元素并取消引用指向标志数据类型的指针来派生类型，如下所示：

typedef struct _OctreeLeafNode
{
    uint8_t type;
    uint64_t location_code;
    uint64_t object_index;
} OctreeLeafNode;

void
func(void* node)
{
    uint8_t type = *(uint8_t*)node;
    if (type == LEAF_NODE) {
        OctreeLeafNode* leaf_node = (OctreeLeafNode*)node;
    }
}

我想知道是否有更清洁的方法。还是不推荐这样做？我应该如何处理结构和 void 指针的多种可能性？

提前致谢！

Answer 1

这是C中常用的方法。

但只需将这些字段放在结构的 start（第一个字段）并且永远不要改变它们的位置。此外，您需要将它们保留在所有结构中。

此方法的一个常见示例是结构中的 version 字段（或在您的情况下为 type）。您可以将它们保留在结构的开头，然后通过类似的方法检查结构版本。像这样：

struct _base {
    uint8_t ver;
};

#define TYPE_OLD 0
struct _a_old {
    struct _base info;
    uint8_t a;
};

#define TYPE_NEW 1
struct _a_new {
    struct _base info;
    uint8_t a;
    uint8_t b;
};

现在您可以通过将数据转换为 struct _base 并检查 ver 字段来识别不同的类型。

unsigned char* buf = ...
switch (((struct _base*)buf)->ver)
{
    case TYPE_OLD:
    {
        struct _a_old* old = (struct _a_old*)buf;
        // ...
        break;
    }
    case TYPE_NEW:
    {
        struct _a_new* old = (struct _a_new*)buf;
        // ...
        break;
    }
    default:
        // ...
}

Answer 2

假设 type 字段在每个结构中位于第一个，这将起作用。指向结构的指针可以安全地转换为指向其第一个成员的指针，因此假设您的结构如下所示：

typedef struct _OctreeInnerNode
{
    uint8_t type;    // type goes first
    uint8_t child_exists;   // put uint8_t members together to keep size down
    uint64_t location_code;
} OctreeInnerNode;

typedef struct _OctreeLeafNode
{
    uint8_t type;   // type goes first
    uint64_t object_index;
    uint64_t location_code;
} OctreeLeafNode;

您可以将 OctreeInnerNode * 或 OctreeLeafNode * 转换为 uint8_t *。那么这是可能的：

void func(void* node) {
    uint8_t type = *(uint8_t*)node;
    if (type == LEAF_NODE) {
        OctreeLeafNode *leafNode = node;
        ...
    } else if (type == INNER_NODE) {
        OctreeInnerNode *innerNode = node;
        ...
    }
}

...

OctreeLeafNode leaf = { LEAF_NODE, 2, 3 };
OctreeInnerNode inner = { INNER_NODE, 5, 1 };

func(&leaf);
func(&inner);

这是根据 C standard 的第 6.7.2.1p15 节保证的：

Within a structure object, the non-bit-field members and the units in which bit-fields reside have addresses that increase in the order in which they are declared. A pointer to a structure object, suitably converted, points to its initial member (or if that member is a bit-field, then to the unit in which it resides), and vice versa. There may be unnamed padding within a structure object, but not at its beginning

基于两种可能结构的未知空指针的访问类型标志？

Access type flag of unknown void pointer based on two possible structs?

c

void-pointers

octree