Флаг типа доступа неизвестного пустого указателя на основе двух возможных структур? - PullRequest
Новая
       16

Флаг типа доступа неизвестного пустого указателя на основе двух возможных структур?

0 голосов
/ 14 ноября 2018

В настоящее время я работаю над своим собственным октри в C. Это дерево будет содержать несколько миллиардов объектов, поэтому эффективность использования памяти является ключевым фактором. Чтобы достичь этого, я в настоящее время использую одну структуру с флагом и объединением, но я думаю, что она не чистая, и она тратит пространство для внутреннего узла, потому что мне нужен только 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;

Теперь проблема возникает с моей неупорядоченной картой, основанной на хеше кода местоположения. Он использует пустой указатель, поэтому сохранение двух разных структур не является проблемой. Я знаю, что существует возможность иметь флаг первым элементом и разыменовывать указатель на тип данных флага для получения типа, например так: 

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

Мне было интересно, есть ли более чистый способ. Или это не рекомендуется? Как бы я имел дело с множеством возможностей для структур и указателей на пустоту?

Заранее спасибо!

Ответы [ 2 ]

0 голосов
/ 14 ноября 2018

Это будет работать при условии, что поле 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);

Это гарантировано в соответствии с разделом 6.7.2.1p15 стандарта C :

Внутри объекта структурыэлементы, не являющиеся битовыми полями, и блоки, в которых находятся битовые поля, имеют адреса, которые увеличиваются в порядке их объявления. Указатель на объект структуры, соответствующим образом преобразованный, указывает на его начальный элемент (или, если этот элемент является битовым полем, то на модуль, в котором он находится), и наоборот.Внутри объекта структуры может быть безымянный отступ, но не в его начале

0 голосов
/ 14 ноября 2018

Этот метод обычно используется в 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:
        // ...
}
...