打包原始数据中的有效类型

Question

为了避免在非常大的数据集上出现内存碎片，我实现了一个双向链表，避免调用 malloc 两次：一个 malloc 用于数据，另一个用于 [=15] =] 和 next 个节点。相反，它使用 alignof 一次分配所需的 space 以获得包含 prev 和 next 节点的 struct 的偏移量。

实施是here但提取相关部分：

#include <stdlib.h>
#include <stdint.h>
#include <stdalign.h>

struct node
{
    struct node *prev;
    struct node *next;
};

typedef struct
{
    struct node *head;
    struct node *tail;
    size_t offset;
    size_t size;
} klist;

klist *klist_create(size_t size)
{
    klist *list = calloc(1, sizeof *list);

    if (list != NULL)
    {
        size_t align = alignof(struct node);

        // Round size up to nearest multiple of alignof(struct node)
        list->offset = (size + (align - 1)) / align * align;
    }
    return list;
}

#define klist_node(list, data) ((void *)((uintptr_t)(const void *)data + list->offset))
#define klist_data(list, node) ((void *)((uintptr_t)(const void *)node - list->offset))

void *klist_push_head(klist *list)
{
    void *data = calloc(1, list->offset + sizeof(struct node));

    if (data == NULL)
    {
        return NULL;
    }

    struct node *node = klist_node(list, data);

    if (list->head != NULL)
    {
        list->head->prev = node;
        node->next = list->head;
    }
    else
    {
        list->tail = node;
    }
    list->head = node;
    list->size++;
    return data;
}

void *klist_head(const klist *list)
{
    if (list->head != NULL)
    {
        return klist_data(list, list->head);
    }
    return NULL;
}

...

然后，在main：

struct data
{
    int key;
    char *value;
};

klist *list = klist_create(sizeof(struct data));
struct data *data = klist_push_head(list);

data->key = 1;
data->value = "one";

其中 data 可以是指向任何基本类型或复合类型的指针。

问题在于，它不是包含所有相关成员的典型打包结构：

struct node
{
    void *data;
    struct node *prev;
    struct node *next;
};

我关注有效类型规则：

If a value is stored into an object having no declared type through an lvalue having a type that is not a character type, then the type of the lvalue becomes the effective type of the object for that access and for subsequent accesses that do not modify the stored value.

这条规则对清单的实施有何影响？

是legal/portable代码吗？

Answer 1

我没有清楚地看到 OP 方法缺点的所有方面，但某些部分（例如通过 (uintptr_t)(void*) 添加整数指针）并未指定用于形成所需的最终指针。

另一种方法是使用 flexible member array 来处理填充问题。

类似于下面的内容。

// Error checking omitted for brevity.   

struct node {
  struct node *prev;
  struct node *next;
  max_align_t data[]; // FMA member at worst case alignment.
};

typedef struct {
  struct node *head;
  struct node *tail;
  size_t data_size;
  size_t size;
} klist;

klist* klist_create(size_t data_size) {
  klist *list = calloc(1, sizeof *list);
  list->data_size = data_size;
  return list;
}

struct node* klist_push_head(klist *list) {
  struct node *nd = calloc(1, sizeof *nd + list->data_size);
  if (list->head) {
    list->head->prev = nd;
    nd->next = list->head;
  } else {
    list->tail = nd;
  }
  list->head = nd;
  list->size++;
  return nd;
}

#define klist_data(/* struct node* */ nd) ((void *)&((nd)->data))

打包原始数据中的有效类型

Effective type in packed raw data

c

memory

language-lawyer

raw-data

alignof