2

为了避免在非常大的数据集上出现内存碎片，我实现了一个避免调用malloc两次的双向链表：一个malloc用于数据，另一个用于prevandnext节点。相反，它会在一个镜头中分配所需的空间，alignof以获取struct包含prev和next节点的偏移量。

实现在这里，但提取了相关部分：

#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";

wheredata可以是指向任何原始类型或复合类型的指针。

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

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

我担心有效的类型规则：

如果通过具有非字符类型类型的左值将值存储到没有声明类型的对象中，则左值的类型将成为该访问的对象的有效类型以及不修改该类型的后续访问储值。

该规则如何影响清单的实施？

它是合法/可移植的代码吗？

4

1 回答 1

1

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

另一种方法是使用灵活的成员数组，它也可以处理填充问题。

像下面这样的东西。

// 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))
于 2021-10-12T14:00:31.687 回答