LibCSTL开发手记

韩乔落
  2025-04-02 18:16:19 2025-04-02 18:16:19 Created   2025-04-07 11:48:55 2025-04-07 11:48:55 Updated  

前言

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

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

Linux Kernel list 移植优化

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

数据结构

kernel_list

container_of 宏

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

我么先来看 offsetof 宏：

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

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

再来看 container_of 宏：

1
2
3
4
5
6
7
8
9
10
#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跳转语句。这种类型的表达式，我们称为语句表达式。语句表达式的格式如下。

1
({a; b; c;})

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

1
2
3
4
5
int sum = ({
    int i;
    for(i = 0; i < 10; ++i);
    i;
})

最后 sum = 10;

list.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#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 移植优化

基于kernel list实现单调栈

基于kernel list实现单调队列

基于kernel list实现双端队列

自定义优先级的优先队列

智能排序算法

  • Title: LibCSTL开发手记
  • Author: 韩乔落
  • Created at : 2025-04-02 18:16:19
  • Updated at : 2025-04-07 11:48:55
  • Link: https://jelasin.github.io/2025/04/02/LibCSTL开发手记/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
LibCSTL开发手记
  1. 前言
  2. Linux Kernel list 移植优化
    1. list.h
    2. list.c
    3. example
  3. Linux kernel hlist 移植优化
  4. 基于kernel list实现单调栈
  5. 基于kernel list实现单调队列
  6. 基于kernel list实现双端队列
  7. 自定义优先级的优先队列
  8. 智能排序算法