c - glibc - 列表和其他数据结构实现

Question

我觉得我的谷歌搜索技能现在很差，在 glibc 中找不到列表实现，找到哈希和树实现但不是列表之一。

是否有任何 glibc 实现？我不想重新格式化linux 内核链表宏并在用户空间中使用它们。

Answer 1

您可以使用insque(3)和remque(3)

Answer 2

其中/usr/include/sys/queue.h包含各种链表变体。（比手册页文档更多）

下面是一个 TAIL_QUEUE 的示例：通过预处理器运行它（gcc -E -c prog.c），以便更容易地了解它是如何工作的）

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <sys/queue.h>



struct Block {
    char text[64];
    //linked list entry
    TAILQ_ENTRY(Block) blocks;
};
struct File {
   char name[128];
   //list of blocks in the "file"
   TAILQ_HEAD(,Block) head; 
};


void add_block(struct File *f, const char *txt)
{
   struct Block *b = malloc(sizeof *b);
   strcpy(b->text,txt); 
   TAILQ_INSERT_TAIL(&f->head, b, blocks);
}

void print_file(struct File *f)
{
    struct Block *b;
    printf("File: %s\n", f->name);
    TAILQ_FOREACH(b, &f->head, blocks) {
        printf("Block: %s\n", b->text);
    }
}
void delete_block(struct File *f, const char *txt)
{
    struct Block *b, *next;
    for(b = TAILQ_FIRST(&f->head) ; b != NULL ; b = next) {
        next = TAILQ_NEXT(b, blocks);
        if(strcmp(b->text, txt) == 0) {
            TAILQ_REMOVE(&f->head, b, blocks);
            free(b);
        }
    }

}

void delete_all_blocks(struct File *f)
{
    struct Block *b;
    while((b = TAILQ_FIRST(&f->head))) {
        TAILQ_REMOVE(&f->head, b, blocks);
        free(b);
    }
}

int main(void)
{
    struct File f;
    TAILQ_INIT(&f.head);
    strcpy(f.name,"Test.f");
    add_block(&f,"one");
    add_block(&f,"two");
    add_block(&f,"three");

    print_file(&f);

    puts("\nDeleting three");
    delete_block(&f, "three");
    print_file(&f);

    puts("\nAdding 2 blocks");
    add_block(&f,"three");
    add_block(&f,"three");
    print_file(&f);

    puts("\nDeleting three");
    delete_block(&f, "three");
    print_file(&f);

    delete_all_blocks(&f);


    return 0;
}