LibCSTL开发手记

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

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

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

数据结构

container_of 宏

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

我么先来看 offsetof 宏：

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

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

再来看 container_of 宏：

12345678910#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 宏使用了表达式语句，这里做一下介绍。

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

1({a; b; c;})

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

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

最后 sum = 10;

list.h123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869#ifndef __LIST_H__#define __LIST_H__#ifndef offsetoftypedef 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)#endifstruct 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.c123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263#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;}

example123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126#include "list.h"#include 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 移植优化基本数据结构12345678910// 哈希链表头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;

空链表1234hlist_head+------------+| first = 0 |+------------+

含一个节点的链表123456789hlist_head hlist_node (节点1)+-----------+ +---------------+| first |------->| next = NULL |+-----------+ | pprev | +---------------+ | | v &(head->first)

含多个节点的链表12345678hlist_head 节点1 节点2 节点3+-----------+ +--------------+ +--------------+ +--------------+| first |--->| next |---->| next |---->| next = NULL |+-----------+ | pprev | | pprev | | pprev | +--------------+ +--------------+ +--------------+ | | | v v v &(head->first) &(节点1->next) &(节点2->next)

头部添加节点操作步骤分解步骤1: 保存原来的第一个节点

1struct hlist_node *first = head->first;

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

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

1node->next = first;

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

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

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

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

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

1head->first = node;

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

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

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

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

在指定节点后添加节点步骤分解初始状态:

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

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

1node->next = prev->next;

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

1node->pprev = &prev->next;

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

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

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

1prev->next = node;

最终状态:

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

删除节点操作初始状态:

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

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

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

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

1*pprev = next;

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

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

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

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

最终状态:

123456789101112131415 节点A 节点B +--------------+ +--------------+--->| next |-------------------->| next |---->... | pprev | | pprev | +--------------+ +--------------+ ^ | | v &(前节点->next) &(节点A->next) 被删除的节点N +-------------------------+ | next = 0xdeadbeef | | pprev = 0xdeadbeef | +-------------------------+

这种设计的特点是：

节点删除操作不需要知道前一个节点是什么，只需通过 pprev 指针间接操作即可

头节点只需一个指针字段，节约内存

所有操作都是 O(1) 时间复杂度

代码实现hlist.h

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182#ifndef __HLIST_H__#define __HLIST_H__#ifndef offsetoftypedef 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

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374#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

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133#include "hlist.h"#include #include #include #define HASH_SIZE 8struct 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 的通用栈数据结构概览123456789stack_head stack_node (元素1) stack_node (元素2)+--------------+ +------------------+ +------------------+| list | | list | | list || - next -----|------->| - next --------|----->| - next ------ || - prev -----|---+ | - prev --------|--+ | - prev --------|--++--------------+ | | [用户数据] | | | [用户数据] | | | +------------------+ | +------------------+ | | | | +--------------------------+--------------------------+

初始化栈 (stack_init_head)123456789101112初始状态: 初始化后: +-------------+ | stack_head | | list | | +-----+ | | | next|--+ | | | | | | prev|--+ | +-----+ | +-------------+代码: head->list.next = head->list.prev = &head->list;

入栈操作 (stack_push)1234567891011121314151617181920212223242526初始状态: 入栈后:+-------------+ +-------------+| 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)1234567891011121314151617181920212223242526272829出栈前: 出栈后:+-------------+ +-------------+| 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)1234567891011121314151617181920212223242526空栈: 非空栈:+-------------+ +-------------+| stack_head | | stack_head || list | | list || +-----+ | | +-----+ || | next|--+ | | next|----+| | | | | | | || | prev|--+ | | prev|--+ || +-----+ | | +-----+ | |+-------------+ +-------------+ | | +---------------+ | v +--------------+ | stack_node | | list | | +-----+ | | | next| | | | | | | | prev| | | +-----+ | | [用户数据] | +--------------+代码: return head->list.next == &head->list;

获取栈顶元素 (stack_top)123456789101112131415161718192021222324252627+-------------+| 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

123456789101112131415161718192021222324252627282930#ifndef __STACK_H__#define __STACK_H__#include "list.h"#ifndef stack_entrytypedef unsigned long size_t;#define stack_entry(ptr, type, member) \ container_of(ptr, type, member)#endifstruct 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

123456789101112131415161718192021222324252627282930313233343536373839#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

12345678910111213141516171819202122232425262728293031323334353637383940#include "stack.h"#include 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的通用队列数据结构概览12345678910111213queue_head 队列头部 队列尾部+--------------+ +--------------+ ... +--------------+| list | | queue_node 1 | | queue_node n || - next -----|-------->| - list | | - list || - prev -----|---+ | - next ---|-----> ... -------->| - next ---|---------++--------------+ | | - prev ---|--+ | - prev ---|--+ | | | [用户数据] | | | [用户数据] | | | | +--------------+ | +--------------+ | | | | | | | | | | +-----------------------------------------------------------|------+ | | +-----------------------------------+

初始化队列 (queue_init_head)123456789101112初始状态: 初始化后: +-------------+ | queue_head | | list | | +-----+ | | | next|--+ | | | | | | prev|--+ | +-----+ | +-------------+代码: head->list.next = head->list.prev = &head->list;

入队操作 (queue_enqueue)1234567891011121314151617181920212223242526初始状态: 入队后:+-------------+ +-------------+| queue_head | | queue_head || list | | list || +-----+ | | +-----+ || | next|--+ | | next|-------+| | | | | | | || | prev|--+ | | prev|--+ || +-----+ | | +-----+ | |+-------------+ +-------------+ | | +-----------------+ | v +-------------+ | queue_node | (新节点) | list | | +-----+ | | | next|--+ | | | | | | prev|--+ | +-----+ | | [用户数据] | +-------------+代码: list_add_head(&node->list, &head->list);

状态变化 - 多个元素入队后1234567891011121314+-------------+ +-------------+ +-------------+ +-------------+| 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)1234567891011121314151617181920212223242526272829303132333435363738394041424344出队前:+-------------+ +-------------+ +-------------+| 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)1234567891011121314151617181920212223242526空队列: 非空队列:+-------------+ +-------------+| queue_head | | queue_head || list | | list || +-----+ | | +-----+ || | next|--+ | | next|----+| | | | | | | || | prev|--+ | | prev|--+ || +-----+ | | +-----+ | |+-------------+ +-------------+ | | +---------------+ | v +--------------+ | queue_node | | list | | +-----+ | | | next| | | | | | | | prev| | | +-----+ | | [用户数据] | +--------------+代码: return head->list.next == &head->list;

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

这个队列实现的特点是：

基于kernel list实现

结构体不存储数据，通用实现。

队列头节点 (queue_head) 仅作为标记节点，不存储实际数据

代码实现queue.h

123456789101112131415161718192021222324252627282930#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)#endifstruct 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

1234567891011121314151617181920212223242526272829303132333435363738394041#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

12345678910111213141516171819202122232425262728293031323334353637#include "queue.h"#include 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语言实现