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

Question

我觉得我的谷歌搜索技能现在很差，找不到 glibc 中的列表实现，找到了 hash和 tree实现，但不是列表。

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

Answer 1

/usr/include/sys/queue.h 包含各种链表变体。(超过 man page 文档)

这是一个 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;
}