如何在共享内存中分配结构体内的链表（C语言）

Question

我想我需要在C语言中的结构体中包含一个链表。 这些结构体如下:

//Structure of the domain list
typedef struct domains *domain_list;
    struct domains{
    char *domain;
    domain_list next;
}domains_node;

//Structure of the configuration of the server
typedef struct{
    int n_threads;
    domain_list domain_list;
    char* local_domain;
    char* named_pipe_statistics;
}server_config;

我尝试将它们输入共享内存，我确定结构体没问题，但我不确定链表是否正确（使用了全局变量）：

//Initialize shared memory
if((config_shmid = shmget(IPC_PRIVATE, sizeof(server_config), IPC_CREAT|0777)) < 0){
    perror("Error in config shmid\n");
    exit(1);
}
if((config = (server_config*)shmat(config_shmid, NULL, 0)) == (server_config *)-1){
    perror("Error in config shmat\n");
    exit(1);
}

if((config_domain_shmid = shmget(IPC_PRIVATE, sizeof(struct domains), IPC_CREAT|0777)) < 0){
    perror("Error in domain_list config shmid\n");
    exit(1);
}
if((config->domain_list = (domain_list)shmat(config_domain_shmid, NULL, 0)) == (domain_list)-1){
    perror("Error in domain_list config shmat\n");
    exit(1);
}

这是关于进程通信的内容。我需要一个在共享内存中的结构体内部的动态（非固定）链接列表。因此，我需要一种方法来为我创建的新节点在内存中分配空间，并且如何连接它们。我知道这不是用malloc实现的，但对于这个问题的回答只是“适当的分配”，我不知道这是什么意思。

- André Almeida

---

http://stackoverflow.com/q/27218618/992406 - houssam

Answer 1

你虽然没有明说，但我猜测你使用了共享内存，以便多个进程可以同时或顺序地访问同一链接列表。

如果是这种情况，可以创建一个共享内存段，其中包含一些控制数据和节点池。

但是，整个信息必须包含在该段中，以便其他进程能够看到它。因此，你的domain成员应该是char缓冲区，而不是指向内存中其他位置的字符串的指针。

所有非空节点指针值将是池中的地址，但是不同进程上的共享内存段可能映射到不同的地址。因此，节点不能具有绝对的next指针。但是，它们可以保持相对于共享节点池的索引。同样适用于列表的heads。

在你的链接列表代码中，应该用自定义函数替换malloc和free，以从池中获取节点或将其放回。由于池具有固定大小，自定义malloc可能会返回NULL，因为这一点需要检查。

下面的代码实现了一个简单的链接列表，其中包含一个位于共享内存段中的固定大小的池。它将所有可见数据保留为相对大小，但操作节点指针，你可以使用dnode进行本地迭代。因为0是一个有效的池索引，所以有一个特殊值DNULL，它通过size_t描述了空指针。

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#include <unistd.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <sys/shm.h>



typedef struct DNode DNode;
typedef struct DList DList;

#define MAX_DNODE 32            // Max. domain string length
#define MAX_DLEN 64             // Max. number of list nodes

#define DNULL (MAX_DLEN + 1)    // NULL value

struct DNode {
    char domain[64];
    size_t next;
};

struct DList {
    DNode pool[MAX_DNODE];      // fixed-size space for nodes
    size_t npool;               // used space in pool
    size_t pfree;               // pointer to re-use freed nodes
    size_t head;                // global list head
};

DList *dlist;

DNode *dnode_alloc(void)
{
    if (dlist->pfree != DNULL) {
        DNode *node = dlist->pool + dlist->pfree;

        dlist->pfree = dlist->pool[dlist->pfree].next;
        return node;
    } else {
        if (dlist->npool < MAX_DNODE) return &dlist->pool[dlist->npool++];
    }

    return NULL;
}

void dnode_free(DNode *node)
{
    if (node) {
        node->next = dlist->pfree;
        dlist->pfree = node - dlist->pool;
    }
}

DNode *dnode(size_t index)
{
    return (index == DNULL) ? NULL : dlist->pool + index;
}

DNode *dnode_next(const DNode *node)
{
    return dnode(node->next);
}

DNode *dnode_push(size_t *head, const char *str)
{
    DNode *node = dnode_alloc();

    if (node) {
        strncpy(node->domain, str, sizeof(node->domain));
        node->next = *head;
        *head = node - dlist->pool;
    }

    return node;
}

void dnode_pop(size_t *head)
{
    if (*head != DNULL) {
        size_t next = dlist->pool[*head].next;

        dnode_free(&dlist->pool[*head]);
        *head = next;
    }
}



int main(int argc, char* argv[])
{
    int shmid;

    shmid = shmget(IPC_PRIVATE, sizeof(DList), IPC_CREAT | 0660);
    if (shmid < 0) exit(1);

    dlist = shmat(shmid, NULL, 0);
    if (dlist == (void *) (-1)) exit(1);

    dlist->head = DNULL;
    dlist->pfree = DNULL;
    dlist->npool = 0;

    dnode_push(&dlist->head, "Alpha");
    dnode_push(&dlist->head, "Bravo");
    dnode_push(&dlist->head, "Charlie");
    dnode_push(&dlist->head, "Delta");
    dnode_push(&dlist->head, "Echo");

    while (dlist->head != DNULL) {
        puts(dnode(dlist->head)->domain);
        dnode_pop(&dlist->head);
    }

    shmdt(dlist);

    return 0;
}

- M Oehm

---

是的，我使用共享内存让多个进程可以访问它。不，我不能使用线程池。我认为每次想要添加一个节点时，我都必须执行shmid和shmat，但这只是猜测。 - André Almeida

这不是线程池，而是节点池。如果你真的想为每个节点创建一个共享内存段，你需要将下一个指针设置为shmid或其他什么东西，但在我看来这真的没有意义。顺便说一句，我已经在不同的进程（父/子进程和顺序进程）中测试了上述代码，它可以正常工作。 - M Oehm

拼写错误，是我的错。但由于我无法使用固定大小的池，我将不得不用另一种方式来解决它。 - André Almeida

你误解了代码：它是一个链表。你可以轻松地插入和删除节点，并更改它们之间的链接。数组只是分配池。它具有固定大小，使用索引而不是指针，并使用char缓冲区而不是指向主结构体外存储器的指针，以便所有信息在进程间都可用。这在你的设计中是不可能的。固定大小实际上是一个固定的最大值。 - M Oehm

DList 结构体只是一些全局变量的包装器，以便将所有内容映射到单个共享内存段中。 - M Oehm

Answer 2

这篇文章非常有帮助，感谢您的发布。以下是一些微调和修改：

1. dnode_alloc 需要在 dlist->pfree != DNULL 时增加 npool（在返回语句之前添加 list->npool++;）。
2. 同样地，dnode_free 在返回之前需要减少 npool（在返回语句之前添加 list->npool--;）。
3. 在 dnode_alloc 中，dlist->npool < MAX_DNODE 应该改为 dlist->npool < MAX_DLEN。

- Jeffrey Schwartz

---

看起来你是在评论另一个答案。答案区域不是为此而设计的。 - trincot

这并没有回答问题。一旦您拥有足够的 声望，您就可以对任何帖子发表评论； 而是，提供不需要询问者澄清的答案。-【来自审核】 - trincot

是的，我在评论M Oehm的答案，他提供了一个非常有用的代码片段，我复制、增强并在我目前正在构建的系统中使用。我发现了一些需要纠正的问题，所以我的评论是为了为任何想要使用它的人提供上下文。 - Jeffrey Schwartz

请勿在答案部分发表此类评论。该区域不是为此而设计的。 - trincot