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

Question

I am currently working on my own octree in C. The tree will contain a few billion objects, so memory efficiency is key. To achieve this I currently use one struct with a flag and a union, but I think it is not clean and it is wasting space for the inner node because I only need an 8-bit flag but memory is being reserved for the 64-bit index. My code currently is as follows:

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

I would like to split this up into two different structs. One leaf node and one inner node. As follows:

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;

Now the problem arises with my unordered map based on the hash of the location code. It uses a void pointer, so storing two different structs is not a problem. I know a possibility would be to have the flag be the first element and dereference the pointer to the flag datatype to derive the type, like so:

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;
    }
}

I was wondering if there is a cleaner way. Or is this not recommended? How would I be supposed to deal with multiple possibilities for structs and void pointers?

Thanks in advance!

Afshin · Accepted Answer · 2018-11-14T17:03:37.087

This a method that is used commonly in C.

But just put these field at start of structure (first field) and never change their position. In addition, you need to keep them in all your structures.

A common sample for this approach is the version field in structures (or type in your case). You can keep them at start of structure, and then check structure version by similar method. something like this:

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;
};

Now you can identify different types by casting your data to struct _base and checking ver field.

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:
        // ...
}

Thanks for the reply! After thinking it through I think this might be the most consistent. Sneakily I had hoped there would be an even cleaner way, but I think this is already pretty clean in its own way. — Lightningstorms, Nov 14 '18 at 18:32

dbush · Answer 2 · 2018-11-14T16:55:26.337

This will work, assuming the type field is first in each struct. A pointer to a struct may safely be converted to a pointer to its first member, so assuming your structs look like this:

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;

You can cast either a OctreeInnerNode * or a OctreeLeafNode * to a uint8_t *. Then this is possible:

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);

This is guaranteed as per section 6.7.2.1p15 of the C standard:

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

Thanks for the reply! Together with the reference, I can get a good understanding. After seeing the other example, I do think it might be better practice to use a struct as the base with the node type and the location_code. This way I can guarantee equal naming and avoid repetition. — Lightningstorms, Nov 14 '18 at 18:28

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

2 Answers2