CAPTAINAI/BLOG

LibCSTL开发手记

2025-04-02

前言

项目地址：https://github.com/jelasin/LibCSTL

移植Linux内核一些优秀的数据结构和算法和一些其他的常用数据结构和算法模板。

Linux Kernel list 移植优化

移植后我们只需要将list_node定义在你自己的结构体中即可。为了可读性和操作简化，请把list_node定义在结构体头部，虽然对于list来说你不把它定义在头部也没有关系。

数据结构

kernel_list

container_of 宏

这是Linux内核中很常用的一个宏定义，配合offsetof可以轻松根据结构体成员计算出结构体首地址，内核通用链表实现依赖于这个宏。

我么先来看 offsetof 宏：

#ifndef offsetof
typedef unsigned long size_t;
// 获取结构体成员偏移，因为常量指针的值为0，即可以看作结构体首地址为0
#define offsetof(TYPE,MEMBER)((size_t)&((TYPE *)0)->MEMBER)
#endif

这个宏用来获取结构体成员的偏移，通过将结构体首地址定义为 0 ，从而获取结构体成员相对于 0 的偏移， 也就是相对于结构体首地址的偏移。

再来看 container_of 宏：

#ifndef container_of
/*ptr 成员指针
* type 结构体 比如struct Stu
* member 成员变量，跟指针对应
* */
// 最后一句的意义就是，取结构体某个成员member的地址，减去这个成员在结构体type中的偏移，运算结果就是结构体type的首地址
#define container_of(ptr, type, member) ({          \
        const typeof( ((type *)0)->member ) *__mptr = (const typeof( ((type *)0)->member ) *)(ptr); \
        (type *)( (char *)__mptr - offsetof(type,member) );})
#endif

const typeof( ((type *)0)->member ) *__mptr = (const typeof( ((type *)0)->member ) *)(ptr); 用于获取我们传入的成员变量指针的地址，在用他减去他相对于 0 的偏移（相对于结构体首地址的偏移）即可得到结构体的首地址。

container_of

表达式语句

container_of 宏使用了表达式语句，这里做一下介绍。

GNU C对C语言标准作了扩展，允许在一个表达式里内嵌语句，允许在表达式内部使用局部变量、for循环和goto跳转语句。这种类型的表达式，我们称为语句表达式。语句表达式的格式如下。

c ({a; b; c;})

语句表达式最外面使用小括号()括起来，里面一对大括号{}包起来的是代码块，代码块里允许内嵌各种语句。语句的格式可以是一般表达式，也可以是循环、跳转语句。和一般表达式一样，语句表达式也有自己的值。语句表达式的值为内嵌语句中最后一个表达式的值。我们举个例子，使用语句表达式求值。

c int sum = ({ int i; for(i = 0; i < 10; ++i); i; })

最后 sum = 10;

list.h

#ifndef __LIST_H__
#define __LIST_H__

#ifndef offsetof
typedef unsigned long size_t;
// 获取结构体成员偏移，因为常量指针的值为0，即可以看作结构体首地址为0
#define offsetof(TYPE,MEMBER)((size_t)&((TYPE *)0)->MEMBER)
#endif

#ifndef container_of
/*ptr 成员指针
* type 结构体 比如struct Stu
* member 成员变量，跟指针对应
* */
// 最后一句的意义就是，取结构体某个成员member的地址，减去这个成员在结构体type中的偏移，运算结果就是结构体type的首地址
#define container_of(ptr, type, member) ({          \
        const typeof( ((type *)0)->member ) *__mptr = (const typeof( ((type *)0)->member ) *)(ptr); \
        (type *)( (char *)__mptr - offsetof(type,member) );})
#endif

#ifndef list_entry
// 获取结构体指针的成员变量地址
#define list_entry(ptr, type, member) \
    container_of(ptr, type, member)
#endif

struct list_head {
    struct list_head *next, *prev;
};

typedef struct list_head list_head;
typedef struct list_head list_node;

// 初始化链表头
extern void init_list_head(list_head *list);

// 插入节点到当前节点之前
extern void list_add_prev(list_node *node, list_node *cur);

// 插入节点到当前节点之后
extern void list_add_next(list_node *node, list_node *cur);

// 链表头插入元素
extern void list_add_head(list_node *node, list_head *head);

// 链表尾插入元素
extern void list_add_tail(list_node *node, list_head *head);

// 链表删除元素
extern void list_del(list_node *node);

// 链表判断是否为空
extern int list_empty(const list_head *head);

// 链表遍历
// 只进行遍历,不进行危险操作.
#define list_for_each_entry(pos, head, member)                \
    for (pos = list_entry((head)->next, typeof(*pos), member); \
         &pos->member != (head);                              \
         pos = list_entry(pos->member.next, typeof(*pos), member))

// 遍历过程中需要删除节点，我们通过next记录了下一个节点的位置。
#define list_for_each_entry_safe(pos, next, head, member)           \
    for (pos = list_entry((head)->next, typeof(*pos), member),   \
         next = list_entry(pos->member.next, typeof(*pos), member);  \
         &pos->member != (head);                                 \
         pos = next, next = list_entry(next->member.next, typeof(*next), member))

#endif // __LIST_H__

list.c

#include "list.h"

// 不小心访问到已经释放的内存，便于调试
static void* LIST_POSTION1 = (void*)0xdeadbeef;
static void* LIST_POSTION2 = (void*)0xdeadbeef;

static void __list_add(list_node *new, list_node *prev, list_node *next)
{
    next->prev = new;
    new->next = next;
    new->prev = prev;
    prev->next = new;
}

static void __list_del(list_node *node)
{
    node->next->prev = node->prev;
    node->prev->next = node->next;
}

// 初始化链表头
void init_list_head(list_head *list)
{
    list->next = list->prev = list;
}

// 插入节点到当前节点之前
void list_add_prev(list_node *node, list_node *cur)
{
    __list_add(node, cur->prev, cur);
}

// 插入节点到当前节点之后
void list_add_next(list_node *node, list_node *cur)
{
    __list_add(node, cur, cur->next);
}

// 链表头插入元素
void list_add_head(list_node *node, list_head *head)
{
    __list_add(node, head, head->next);
}

// 链表尾插入元素
void list_add_tail(list_node *node, list_head *head)
{
    __list_add(node, head->prev, head);
}

// 链表删除元素
void list_del(list_node *node)
{
    __list_del(node);
    node->next = LIST_POSTION1;
    node->prev = LIST_POSTION2;
}

// 链表判断是否为空
int list_empty(const list_head *head)
{
    return head->next == head;
}

example

#include "list.h"
#include <stdio.h>

struct example {
    // 虽然这对于链表来说并不是必须的, 但还是为了可读性, 请将list_node 定义为第一个成员变量
    list_node list;
    int value;
};

int main(int argc, char const *argv[])
{
    // 初始化链表头
    list_head head;
    init_list_head(&head);
    // 初始化链表元素
    struct example e1, e2, e3;
    e1.value = 1;
    e2.value = 2;
    e3.value = 3;
    fprintf(stdout, "list_add_head: %d %d %d\n", e1.value, e2.value, e3.value);
    // 链表头插入元素
    list_add_head(&e1.list, &head);
    list_add_head(&e2.list, &head);
    list_add_head(&e3.list, &head);

    struct example e4, e5, e6;
    e4.value = 4;
    e5.value = 5;
    e6.value = 6;
    fprintf(stdout, "list_add_tail: %d %d %d\n", e4.value, e5.value, e6.value);
    // 链表尾插入元素
    list_add_tail(&e4.list, &head);
    list_add_tail(&e5.list, &head);
    list_add_tail(&e6.list, &head);
    // 遍历链表
    struct example *pos;
    list_for_each_entry(pos, &head, list)
    {
        fprintf(stdout, "value: %d\n", pos->value);
    }
    fprintf(stdout, "list_del %d\n", e2.value);
    // 删除链表元素
    list_del(&e2.list);
    // 遍历链表
    list_for_each_entry(pos, &head, list)
    {
        fprintf(stdout, "value: %d\n", pos->value);
    }

    fprintf(stdout, "list_add_prev list_add_next: in = %d cur = 5\n", e2.value);
    // 遍历添加节点
    struct example *next, *cur;
    list_for_each_entry_safe(pos, next, &head, list)
    {
        if (pos->value == 5)
        {
            cur = pos;
            break;
        }
    }
    struct example e7, e8;
    e7.value = 7;
    e8.value = 8;
    fprintf(stdout, "prev in = %d cur = %d\n", e7.value, cur->value);
    // // 插入节点到当前节点之前
    list_add_prev(&e7.list, &cur->list);
    fprintf(stdout, "next in = %d cur = %d\n", e8.value, cur->value);
    // // 插入节点到当前节点之后
    list_add_next(&e8.list, &cur->list);

    // 遍历链表
    list_for_each_entry(pos, &head, list)
    {
        fprintf(stdout, "value: %d\n", pos->value);
    }
    fprintf(stdout, "list_del all\n");
    // 遍历删除链表
    list_for_each_entry_safe(pos, next, &head, list)
    {
        fprintf(stdout, "del value: %d\n", pos->value);
        list_del(&pos->list);
        // 如果需要, 在这里释放内存
        // free(pos);
    }
    if (list_empty(&head))
    {
        fprintf(stdout, "list is empty\n");
    }

    return 0;
}

// ➜  list git:(master) ✗ ./exp 
// list_add_head: 1 2 3
// list_add_tail: 4 5 6
// value: 3
// value: 2
// value: 1
// value: 4
// value: 5
// value: 6
// list_del 2
// value: 3
// value: 1
// value: 4
// value: 5
// value: 6
// list_add_prev list_add_next: in = 2 cur = 5
// prev in = 7 cur = 5
// next in = 8 cur = 5
// value: 3
// value: 1
// value: 4
// value: 7
// value: 5
// value: 8
// value: 6
// list_del all
// del value: 3
// del value: 1
// del value: 4
// del value: 7
// del value: 5
// del value: 8
// del value: 6
// list is empty

Linux kernel hlist 移植优化

基本数据结构

// 哈希链表头
typedef struct hlist_head {
    struct hlist_node *first;  // 指向第一个节点
} hlist_head;

// 哈希链表节点
typedef struct hlist_node {
    struct hlist_node *next;   // 指向下一个节点
    struct hlist_node **pprev; // 指向前一个节点的next字段地址
} hlist_node;

空链表

hlist_head
+------------+
| first = 0  |
+------------+

含一个节点的链表

hlist_head           hlist_node (节点1)
+-----------+        +---------------+
| first     |------->| next = NULL   |
+-----------+        | pprev         |
                     +---------------+
                            |
                            |
                            v
                     &(head->first)

含多个节点的链表

hlist_head         节点1                节点2                节点3
+-----------+    +--------------+     +--------------+     +--------------+
| first     |--->| next         |---->| next         |---->| next = NULL  |
+-----------+    | pprev        |     | pprev        |     | pprev        |
                 +--------------+     +--------------+     +--------------+
                       |                    |                    |
                       v                    v                    v
                 &(head->first)       &(节点1->next)       &(节点2->next)

头部添加节点操作

步骤分解

步骤1: 保存原来的第一个节点

struct hlist_node *first = head->first;

原始链表:
hlist_head         节点A
+-----------+    +--------------+
| first     |--->| next         |---->...
+-----------+    | pprev        |
                 +--------------+
                       |
                       v
                 &(head->first)

新节点:
节点N
+--------------+
| next = ?     |
| pprev = ?    |
+--------------+

步骤2: 更新新节点的 next 指针

node->next = first;

hlist_head         节点A
+-----------+    +--------------+
| first     |--->| next         |---->...
+-----------+    | pprev        |
                 +--------------+
                       |
                       v
                 &(head->first)

节点N
+--------------+
| next         |----+
| pprev = ?    |    |
+--------------+    |
                    v
                  节点A

步骤3: 如果原来有第一个节点，更新其 pprev 指针

if (first)
{
    first->pprev = &node->next;
}

hlist_head         节点A
+-----------+    +--------------+
| first     |--->| next         |---->...
+-----------+    | pprev        |
                 +--------------+
                       |
                       v
                 &(节点N->next)

节点N
+--------------+
| next         |----+
| pprev = ?    |    |
+--------------+    |
                    v
                  节点A

步骤4: 更新头节点的 first 指针

head->first = node;

hlist_head         节点N                节点A
+-----------+    +--------------+     +--------------+
| first     |--->| next         |---->| next         |---->...
+-----------+    | pprev = ?    |     | pprev        |
                 +--------------+     +--------------+
                                            |
                                            v
                                      &(节点N->next)

步骤5: 更新新节点的 pprev 指针

node->pprev = &head->first;

hlist_head         节点N                节点A
+-----------+    +--------------+     +--------------+
| first     |--->| next         |---->| next         |---->...
+-----------+    | pprev        |     | pprev        |
      ^          +--------------+     +--------------+
      |                |                    |
      |                v                    v
      +----------&(head->first)       &(节点N->next)

在指定节点后添加节点

步骤分解

初始状态:

        节点P                节点C
    +--------------+     +--------------+
--->| next         |---->| next         |---->...
    | pprev        |     | pprev        |
    +--------------+     +--------------+
          ^                    |
          |                    v
    &(前节点->next)      &(节点P->next)

步骤1: 设置新节点的 next 指针

node->next = prev->next;

步骤2: 设置新节点的 pprev 指针

node->pprev = &prev->next;

步骤3: 如果后继节点存在，更新其 pprev 指针

if (prev->next)
{
    prev->next->pprev = &node->next;
}

步骤4: 更新前驱节点的 next 指针

prev->next = node;

最终状态:

        节点P                节点N                节点C
    +--------------+     +--------------+     +--------------+
--->| next         |---->| next         |---->| next         |---->...
    | pprev        |     | pprev        |     | pprev        |
    +--------------+     +--------------+     +--------------+
          ^                    |                    |
          |                    v                    v
    &(前节点->next)      &(节点P->next)       &(节点N->next)

删除节点操作

初始状态:

        节点A                节点N                节点B
    +--------------+     +--------------+     +--------------+
--->| next         |---->| next         |---->| next         |---->...
    | pprev        |     | pprev        |     | pprev        |
    +--------------+     +--------------+     +--------------+
          ^                    |                    |
          |                    v                    v
    &(前节点->next)      &(节点A->next)       &(节点N->next)

步骤1&2: 获取要删除节点的 next 和 pprev

struct hlist_node *next = node->next;
struct hlist_node **pprev = node->pprev;

步骤3: 更新前驱节点的 next 指针

*pprev = next;

步骤4: 如果存在后继节点，更新其 pprev 指针

if (next)
{
    next->pprev = pprev;
}

步骤5: 设置被删除节点的指针为危险值

node->next = HLIST_POISONED_POINTER;
node->pprev = HLIST_POISONED_POINTER;

最终状态:

        节点A                                节点B
    +--------------+                     +--------------+
--->| next         |-------------------->| next         |---->...
    | pprev        |                     | pprev        |
    +--------------+                     +--------------+
          ^                                    |
          |                                    v
    &(前节点->next)                      &(节点A->next)


        被删除的节点N
    +-------------------------+
    | next = 0xdeadbeef      |
    | pprev = 0xdeadbeef     |
    +-------------------------+

这种设计的特点是： 1. 节点删除操作不需要知道前一个节点是什么，只需通过 pprev 指针间接操作即可 2. 头节点只需一个指针字段，节约内存 3. 所有操作都是 O(1) 时间复杂度

代码实现

hlist.h

#ifndef __HLIST_H__
#define __HLIST_H__

#ifndef offsetof
typedef unsigned long size_t;
// 获取结构体成员偏移，常量指针的值为0，可视为结构体首地址为0
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
#endif

#ifndef container_of
/* ptr 成员指针
 * type 结构体类型
 * member 成员变量名
 */
#define container_of(ptr, type, member) ({          \
        const typeof( ((type *)0)->member ) *__mptr = (const typeof( ((type *)0)->member ) *)(ptr); \
        (type *)( (char *)__mptr - offsetof(type, member) );})
#endif

// 哈希表节点定义
struct hlist_node {
    struct hlist_node *next, **pprev;
};

// 哈希表头定义
struct hlist_head {
    struct hlist_node *first;
};

typedef struct hlist_node hlist_node;
typedef struct hlist_head hlist_head;

#ifndef hlist_entry
#define hlist_entry(ptr, type, member) \
    container_of(ptr, type, member)
#endif

// 初始化哈希表头
extern void hlist_init_head(hlist_head *head);

// 在头部添加节点
extern void hlist_add_head(hlist_node *node, hlist_head *head);

// 在指定节点后添加节点
extern void hlist_add_after(hlist_node *node, hlist_node *prev);

// 在指定节点前添加节点
extern void hlist_add_before(hlist_node *node, hlist_node *next);

// 从哈希表中删除节点
extern void hlist_del(hlist_node *node);

// 判断哈希表是否为空
extern int hlist_empty(const hlist_head *head);

// 遍历哈希表
#define hlist_for_each(pos, head) \
    for (pos = (head)->first; pos; pos = pos->next)

// 安全遍历哈希表，允许删除
#define hlist_for_each_safe(pos, n, head) \
    for (pos = (head)->first; pos && ({ n = pos->next; 1; }); pos = n)

// 遍历哈希表，获取结构体指针
#define hlist_for_each_entry(pos, head, member) \
    for (pos = hlist_entry_safe((head)->first, typeof(*(pos)), member); \
         pos; \
         pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))

// 安全的哈希表遍历，获取结构体指针，允许删除
#define hlist_for_each_entry_safe(pos, n, head, member) \
    for (pos = hlist_entry_safe((head)->first, typeof(*(pos)), member); \
         pos && ({ n = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member); 1; }); \
         pos = n)

// 安全获取哈希表节点对应的结构体指针
#define hlist_entry_safe(ptr, type, member) \
    ({ typeof(ptr) ____ptr = (ptr); \
       ____ptr ? hlist_entry(____ptr, type, member) : NULL; \
    })

#endif // __HLIST_H__

hlist.c

#include "hlist.h"

// 不小心访问到已经释放的内存
static void* HLIST_POISONED_POINTER = (void*)0xdeadbeef;

// 初始化哈希表头
void hlist_init_head(hlist_head *head)
{
    head->first = (void*)0;
}

// 在头部添加节点
void hlist_add_head(hlist_node *node, hlist_head *head)
{
    struct hlist_node *first = head->first;
    node->next = first;

    if (first)
    {
        first->pprev = &node->next;
    }

    head->first = node;
    node->pprev = &head->first;
}

// 在指定节点后添加节点
void hlist_add_after(hlist_node *node, hlist_node *prev)
{
    node->next = prev->next;
    node->pprev = &prev->next;

    if (prev->next)
    {
        prev->next->pprev = &node->next;
    }

    prev->next = node;
}

// 在指定节点前添加节点
void hlist_add_before(hlist_node *node, hlist_node *next)
{
    node->pprev = next->pprev;
    node->next = next;
    *node->pprev = node;
    next->pprev = &node->next;
}

// 从哈希表中删除节点
void hlist_del(hlist_node *node)
{
    struct hlist_node *next = node->next;
    struct hlist_node **pprev = node->pprev;

    // 更新前一个节点的next指针
    *pprev = next;

    // 如果存在后继节点，更新其pprev指针
    if (next)
    {
        next->pprev = pprev;
    }

    // 设置被删除节点的指针为危险值
    node->next = HLIST_POISONED_POINTER;
    node->pprev = HLIST_POISONED_POINTER;
}

// 判断哈希表是否为空
int hlist_empty(const hlist_head *head)
{
    return head->first == (void*)0;
}

example.c

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

#define HASH_SIZE 8

struct person {
    hlist_node node;  // 哈希表节点
    int id;
    char name[32];
};

// 简单的哈希函数
static unsigned int hash_func(int key) 
{
    return key % HASH_SIZE;
}

int main() 
{
    // 创建哈希表
    hlist_head hash_table[HASH_SIZE];
    int i;

    // 初始化哈希表头
    for (i = 0; i < HASH_SIZE; i++) 
    {
        hlist_init_head(&hash_table[i]);
    }

    // 创建一些数据
    struct person p1 = {.id = 1, .name = "Alice"};
    struct person p2 = {.id = 9, .name = "Bob"};    // hash到相同位置(9%8=1)
    struct person p3 = {.id = 5, .name = "Charlie"};
    struct person p4 = {.id = 13, .name = "David"}; // hash到相同位置(13%8=5)

    // 插入哈希表
    hlist_add_head(&p1.node, &hash_table[hash_func(p1.id)]);
    hlist_add_head(&p2.node, &hash_table[hash_func(p2.id)]);
    hlist_add_head(&p3.node, &hash_table[hash_func(p3.id)]);
    hlist_add_head(&p4.node, &hash_table[hash_func(p4.id)]);

    printf("哈希表内容:\n");
    for (i = 0; i < HASH_SIZE; i++) 
    {
        printf("桶 %d: ", i);
        if (hlist_empty(&hash_table[i])) 
        {
            printf("空\n");
            continue;
        }

        struct person *pos;
        hlist_for_each_entry(pos, &hash_table[i], node) 
        {
            printf("(%d, %s) ", pos->id, pos->name);
        }
        printf("\n");
    }

    // 查找id为9的人
    int id_to_find = 9;
    unsigned int hash = hash_func(id_to_find);
    struct person *found = NULL;
    struct person *pos;

    hlist_for_each_entry(pos, &hash_table[hash], node) 
    {
        if (pos->id == id_to_find) 
        {
            found = pos;
            break;
        }
    }

    if (found) 
    {
        printf("\n找到: ID=%d, Name=%s\n", found->id, found->name);

        // 删除找到的节点
        printf("删除 ID=%d\n", found->id);
        hlist_del(&found->node);
    } 
    else 
    {
        printf("\nID=%d 未找到\n", id_to_find);
    }

    // 再次打印哈希表内容
    printf("\n删除后的哈希表内容:\n");
    for (i = 0; i < HASH_SIZE; i++) 
    {
        printf("桶 %d: ", i);
        if (hlist_empty(&hash_table[i])) 
        {
            printf("空\n");
            continue;
        }

        struct person *pos;
        hlist_for_each_entry(pos, &hash_table[i], node) 
        {
            printf("(%d, %s) ", pos->id, pos->name);
        }
        printf("\n");
    }

    return 0;
}

// 哈希表内容:
// 桶 0: 空
// 桶 1: (9, Bob) (1, Alice) 
// 桶 2: 空
// 桶 3: 空
// 桶 4: 空
// 桶 5: (13, David) (5, Charlie) 
// 桶 6: 空
// 桶 7: 空

// 找到: ID=9, Name=Bob
// 删除 ID=9

// 删除后的哈希表内容:
// 桶 0: 空
// 桶 1: (1, Alice) 
// 桶 2: 空
// 桶 3: 空
// 桶 4: 空
// 桶 5: (13, David) (5, Charlie) 
// 桶 6: 空
// 桶 7: 空

基于kernel list 的通用栈

数据结构概览

stack_head               stack_node (元素1)        stack_node (元素2)
+--------------+        +------------------+      +------------------+
| list         |        | list             |      | list             |
|  - next -----|------->|  - next  --------|----->|  - next  ------  |
|  - prev -----|---+    |  - prev  --------|--+   |  - prev  --------|--+
+--------------+   |    | [用户数据]        |  |   | [用户数据]        |  |
                   |    +------------------+  |   +------------------+  |
                   |                          |                         |
                   +--------------------------+--------------------------+

初始化栈 (stack_init_head)

初始状态:                                初始化后:
                                        +-------------+
                                        | stack_head  |
                                        |   list      |
                                        |    +-----+  |
                                        |    | next|--+
                                        |    |     |  |
                                        |    | prev|--+
                                        |    +-----+  |
                                        +-------------+

代码: head->list.next = head->list.prev = &head->list;

入栈操作 (stack_push)

初始状态:                        入栈后:
+-------------+                 +-------------+
| stack_head  |                 | stack_head  |
|   list      |                 |   list      |
|    +-----+  |                 |    +-----+  |
|    | next|--+                 |    | next|----+
|    |     |  |                 |    |     |    |
|    | prev|--+                 |    | prev|--+ |
|    +-----+  |                 |    +-----+  | |
+-------------+                 +-------------+ |
                                               |
                                +---------------+
                                |
                                v
                         +--------------+
                         | stack_node   |
                         |   list       |
                         |    +-----+   |
                         |    | next|---+
                         |    |     |   |
                         |    | prev|---+
                         |    +-----+   |
                         | [用户数据]    |
                         +--------------+

代码: list_add_head(&node->list, &head->list);

出栈操作 (stack_pop)

出栈前:                                  出栈后:
+-------------+                          +-------------+
| stack_head  |                          | stack_head  |
|   list      |                          |   list      |
|    +-----+  |                          |    +-----+  |
|    | next|----+                        |    | next|--+
|    |     |    |                        |    |     |  |
|    | prev|--+ |                        |    | prev|--+
|    +-----+  | |                        |    +-----+  |
+-------------+ |                        +-------------+
               |
+---------------+                        +--------------+
|                                        | stack_node   |  (返回该节点)
v                                        |   list       |
+--------------+                         |    +-----+   |
| stack_node   |                         |    | next|   |  (从链表中移除)
|   list       |                         |    |     |   |
|    +-----+   |                         |    | prev|   |
|    | next|---+                         |    +-----+   |
|    |     |   |                         | [用户数据]    |
|    | prev|---+                         +--------------+
|    +-----+   |
| [用户数据]    |
+--------------+

代码:
1. node = stack_entry((stack_node*)head->list.next, stack_node, list);
2. list_del(&node->list);
3. return (void*)node;

判断栈是否为空 (stack_empty)

空栈:                                非空栈:
+-------------+                     +-------------+
| stack_head  |                     | stack_head  |
|   list      |                     |   list      |
|    +-----+  |                     |    +-----+  |
|    | next|--+                     |    | next|----+
|    |     |  |                     |    |     |    |
|    | prev|--+                     |    | prev|--+ |
|    +-----+  |                     |    +-----+  | |
+-------------+                     +-------------+ |
                                                  |
                                   +---------------+
                                   |
                                   v
                                   +--------------+
                                   | stack_node   |
                                   |   list       |
                                   |    +-----+   |
                                   |    | next|   |
                                   |    |     |   |
                                   |    | prev|   |
                                   |    +-----+   |
                                   | [用户数据]    |
                                   +--------------+

代码: return head->list.next == &head->list;

获取栈顶元素 (stack_top)

+-------------+
| stack_head  |
|   list      |
|    +-----+  |
|    | next|----+
|    |     |    |
|    | prev|--+ |
|    +-----+  | |
+-------------+ |
               |
+---------------+
|
v
+--------------+
| stack_node   | <---- 返回这个节点但不改变栈结构
|   list       |
|    +-----+   |
|    | next|   |
|    |     |   |
|    | prev|   |
|    +-----+   |
| [用户数据]    |
+--------------+

代码:
1. node = stack_entry((stack_node*)head->list.next, stack_node, list);
2. return (void*)node;

代码实现

stack.h

#ifndef __STACK_H__
#define __STACK_H__

#include "list.h"

#ifndef stack_entry
typedef unsigned long size_t;
#define stack_entry(ptr, type, member) \
    container_of(ptr, type, member)
#endif

struct stack_list  {
    list_head list;
};

typedef struct stack_list stack_head;
typedef struct stack_list stack_node;
// 初始化栈头
extern void stack_init_head(stack_head *head);
// 入栈操作
extern void stack_push(stack_node *node, stack_head *head);
// 出栈操作
extern void* stack_pop(stack_head *head);
// 判断栈是否为空
extern int stack_empty(const stack_head *head);
// 查看栈顶元素
extern void* stack_top(const stack_head *head);


#endif /* __STACK_H__ */

stack.c

#include "stack.h"

// 初始化栈头
void stack_init_head(stack_head *head)
{
    head->list.next = head->list.prev = &head->list;
}
// 入栈操作
void stack_push(stack_node *node, stack_head *head)
{
    list_add_head(&node->list, &head->list);
}
// 出栈操作
void *stack_pop(stack_head *head)
{
    if (stack_empty(head))
    {
        return (void*)0;
    }
    stack_node *node = stack_entry((stack_node*)head->list.next, stack_node, list);
    list_del(&node->list);

    return (void*)node;
}
// 判断栈是否为空
int stack_empty(const stack_head *head)
{
    return head->list.next == &head->list;
}
// 获取栈顶元素
void* stack_top(const stack_head *head)
{
    if (stack_empty(head))
    {
        return (void*)0;
    }
    stack_node *node = stack_entry((stack_node*)head->list.next, stack_node, list);
    return (void*)node;
}

example.c

#include "stack.h"
#include <stdio.h>

struct example
{
    // 为了简化操作, 请将stack_node作为第一个成员变量
    stack_node node;
    int data;
};

int main(int argc, char const *argv[])
{
    stack_head head;
    stack_init_head(&head);

    struct example e1, e2, e3;
    e1.data = 1;
    e2.data = 2;
    e3.data = 3;

    stack_push(&e1.node, &head);
    stack_push(&e2.node, &head);
    stack_push(&e3.node, &head);


    struct example *e;
    e = (typeof(e))stack_top(&head);
    printf("top: %d\n", e->data);
    while(!stack_empty(&head))
    {
        e = (typeof(e))stack_pop(&head);
        printf("pop: %d\n", e->data);
    }
    return 0;
}

// ➜  stack git:(master) ✗ ./exp
// 3
// 2
// 1

基于kernel list的通用队列

数据结构概览

queue_head                  队列头部                               队列尾部
+--------------+         +--------------+       ...          +--------------+
| list         |         | queue_node 1 |                    | queue_node n |
|  - next -----|-------->|  - list      |                    |  - list      |
|  - prev -----|---+     |    - next ---|-----> ... -------->|    - next ---|---------+
+--------------+   |     |    - prev ---|--+                 |    - prev ---|--+      |
                   |     | [用户数据]    |  |                 | [用户数据]    |  |      |
                   |     +--------------+  |                 +--------------+  |      |
                   |                       |                                   |      |
                   |                       |                                   |      |
                   +-----------------------------------------------------------|------+
                                           |                                   |
                                           +-----------------------------------+

初始化队列 (queue_init_head)

初始状态:                                初始化后:
                                        +-------------+
                                        | queue_head  |
                                        |   list      |
                                        |    +-----+  |
                                        |    | next|--+
                                        |    |     |  |
                                        |    | prev|--+
                                        |    +-----+  |
                                        +-------------+

代码: head->list.next = head->list.prev = &head->list;

入队操作 (queue_enqueue)

初始状态:                                           入队后:
+-------------+                                    +-------------+
| queue_head  |                                    | queue_head  |
|   list      |                                    |   list      |
|    +-----+  |                                    |    +-----+  |
|    | next|--+                                    |    | next|-------+
|    |     |  |                                    |    |     |       |
|    | prev|--+                                    |    | prev|--+    |
|    +-----+  |                                    |    +-----+  |    |
+-------------+                                    +-------------+    |
                                                                     |
                                                   +-----------------+
                                                   |
                                                   v
                                                +-------------+
                                                | queue_node  | (新节点)
                                                |   list      |
                                                |    +-----+  |
                                                |    | next|--+
                                                |    |     |  |
                                                |    | prev|--+
                                                |    +-----+  |
                                                | [用户数据]   |
                                                +-------------+

代码: list_add_head(&node->list, &head->list);

状态变化 - 多个元素入队后

+-------------+          +-------------+          +-------------+          +-------------+
| queue_head  |          | queue_node 1|          | queue_node 2|          | queue_node 3|
|   list      |          |   list      |          |   list      |          |   list      |
|    +-----+  |          |    +-----+  |          |    +-----+  |          |    +-----+  |
|    | next|------------>|    | next|------------>|    | next|------------>|    | next|--+
|    |     |  |          |    |     |  |          |    |     |  |          |    |     |  |
|    | prev|<------------|    | prev|<------------|    | prev|<------------|    | prev|  |
|    +-----+  |          |    +-----+  |          |    +-----+  |          |    +-----+  |
+-------------+          | [用户数据]   |          | [用户数据]   |          | [用户数据]   |
     ^                   +-------------+          +-------------+          +-------------+
     |                                                                        |
     +------------------------------------------------------------------------+

注: 元素1最先入队，元素3最后入队。出队时，元素1会最先被移除(先进先出)。

出队操作 (queue_dequeue)

出队前:
+-------------+          +-------------+          +-------------+
| queue_head  |          | queue_node 1|          | queue_node 2|
|   list      |          |   list      |          |   list      |
|    +-----+  |          |    +-----+  |          |    +-----+  |
|    | next|------------>|    | next|------------>|    | next|--+
|    |     |  |          |    |     |  |          |    |     |  |
|    | prev|<------------|    | prev|<------------|    | prev|  |
|    +-----+  |          |    +-----+  |          |    +-----+  |
+-------------+          | [用户数据]   |          | [用户数据]   |
     ^                   +-------------+          +-------------+
     |                        ^                      |
     +------------------------|-----------------------+
                              |
                              | (从队尾出队，移除元素1)

出队后:
+-------------+                             +-------------+
| queue_head  |                             | queue_node 2|
|   list      |                             |   list      |
|    +-----+  |                             |    +-----+  |
|    | next|-------------------------------->|    | next|--+
|    |     |  |                             |    |     |  |
|    | prev|<---------------------------------|    | prev|  |
|    +-----+  |                             |    +-----+  |
+-------------+                             | [用户数据]   |
                                           +-------------+

返回:
+-------------+  
| queue_node 1|  (返回该节点)
|   list      |  
|    +-----+  |  (从链表中移除)
|    | next|   |  
|    |     |   |  
|    | prev|   |  
|    +-----+  |  
| [用户数据]   |  
+-------------+  

代码:
1. node = queue_entry((queue_node*)head->list.prev, queue_node, list);
2. list_del(&node->list);
3. return (void*)node;

判断队列是否为空 (queue_is_empty)

空队列:                               非空队列:
+-------------+                     +-------------+
| queue_head  |                     | queue_head  |
|   list      |                     |   list      |
|    +-----+  |                     |    +-----+  |
|    | next|--+                     |    | next|----+
|    |     |  |                     |    |     |    |
|    | prev|--+                     |    | prev|--+ |
|    +-----+  |                     |    +-----+  | |
+-------------+                     +-------------+ |
                                                  |
                                   +---------------+
                                   |
                                   v
                                   +--------------+
                                   | queue_node   |
                                   |   list       |
                                   |    +-----+   |
                                   |    | next|   |
                                   |    |     |   |
                                   |    | prev|   |
                                   |    +-----+   |
                                   | [用户数据]    |
                                   +--------------+

代码: return head->list.next == &head->list;

完整队列操作流程

                +----------------+
                | 初始化队列     |
                +----------------+
                        |
                        v
                +----------------+
                | 队列为空       |
                +----------------+
                        |
                        v
        +-------------------------------+
        | 入队操作 (向队列头部添加元素) |
        +-------------------------------+
                        |
                        v
                +----------------+
                | 队列不为空     |
                +----------------+
                        |
                        v
        +-------------------------------+
        | 出队操作 (从队列尾部移除元素) |
        +-------------------------------+
                        |
                        v
                +----------------+
                | 返回出队元素   |
                +----------------+

这个队列实现的特点是： 1. 基于kernel list实现 2. 结构体不存储数据，通用实现。 3. 队列头节点 (queue_head) 仅作为标记节点，不存储实际数据

代码实现

queue.h

#ifndef __QUEUE_H__
#define __QUEUE_H__

#include "list.h"

#ifndef queue_entry
// 获取队列节点的结构体指针
typedef unsigned long size_t;
#define queue_entry(ptr, type, member) \
    container_of(ptr, type, member)
#endif

struct queue_list {
    struct list_head list;
};
typedef struct queue_list queue_head;
typedef struct queue_list queue_node;

// 初始化队列头
extern void queue_init_head(queue_head *head);
// 入队
extern void queue_enqueue(queue_head *head, queue_node *node);
// 出队
extern void* queue_dequeue(queue_head *head);
// 查看下一个出队元素
extern void* queue_peek(const queue_head *head);
// 判断队列是否为空
extern int queue_is_empty(const queue_head *head);

#endif /* __QUEUE_H__ */

queue.c

#include "queue.h"

// 初始化队列头
void queue_init_head(queue_head *head)
{
    head->list.next = head->list.prev = &head->list;
}
// 入队
void queue_enqueue(queue_head *head, queue_node *node)
{
    list_add_head(&node->list, &head->list);
}
// 出队
void* queue_dequeue(queue_head *head)
{
    if (queue_is_empty(head))
    {
        return (void*)0;
    }

    queue_node *node = queue_entry((queue_node*)head->list.prev, queue_node, list);
    list_del(&node->list);

    return (void*)node;
}
// 查看下一个出队元素
void* queue_peek(const queue_head *head)
{
    if (queue_is_empty(head))
    {
        return (void*)0;
    }

    queue_node *node = queue_entry((queue_node*)head->list.prev, queue_node, list);
    return (void*)node;
}
// 判断队列是否为空
int queue_is_empty(const queue_head *head)
{
    return head->list.next == &head->list;
}

example.c

#include "queue.h"
#include <stdio.h>

struct example {
    // 为了简化操作, 请将queue_node定义为第一个成员变量
    queue_node node;
    int data;
};

int main(int argc, char const *argv[])
{
    queue_head q;
    queue_init_head(&q);

    struct example e1, e2, e3;
    e1.data = 1;
    e2.data = 2;
    e3.data = 3;

    queue_enqueue(&q, &e1.node);
    queue_enqueue(&q, &e2.node);
    queue_enqueue(&q, &e3.node);

    struct example *e;
    while ((e = (typeof(e))queue_dequeue(&q)) != NULL) {
        printf("data: %d\n", e->data);
        // do free or other operations here
    }

    return 0;
}

// ➜  queue git:(master) ✗ ./exp 
// data: 1
// data: 2
// data: 3
// queue is empty: Success

基于kernel list的通用双端队列

通用环形队列的实现

通用共享内存环形队列的实现

通用自定义优先级的优先队列实现

通用智能排序算法

轻量级线程池的C语言实现

常见hashmap底层算法的C语言实现

基于kernel hlist的通用hashmap实现

Linux Kernel 红黑树的通用优化

通用伸展树的C语言实现

通用B树的C语言实现

通用LRU链表的C语言实现

基于红黑树的通用hashmap实现

常见密码学算法的C语言实现