【Linux高级编译】list.h的高效应用—单向链表的实现-linux高级程序设计pdf

Linux内核中，有许许多多的精妙设计，比如在内核代码中，运用到了大量的【链表】这种数据结构，而在Linux内核中，针对如此多的链表要进行操作，他们分别是如何定义和管理的呢？本文将给你展示，Linux内核中list.h的高效应用。

通过本文的阅读，你将了解到以下内容：

list.h的全貌 **如何使用list.h创建单向链表并实现链表的基本操作？

list.h的全貌

以下就是它的全部内容，可能不同版本的linux有些许的差异，但精髓都在这：

复制#ifndef _LINUX_LIST_H #define _LINUX_LIST_H /********** include/linux/list.h **********/ /* * These are non-NULL pointers that will result in page faults * under normal circumstances, used to verify that nobody uses * non-initialized list entries. */ #define LIST_POISON1 ((void *) 0x00100100) #define LIST_POISON2 ((void *) 0x00200200) #ifndef ARCH_HAS_PREFETCH #define ARCH_HAS_PREFETCH static inline void prefetch(const void *x) {;} #endif /* * Simple doubly linked list implementation. * * Some of the internal functions (“__xxx”) are useful when * manipulating whole lists rather than single entries, as * sometimes we already know the next/prev entries and we can * generate better code by using them directly rather than * using the generic single-entry routines. */ struct list_head { struct list_head *next, *prev; }; #define LIST_HEAD_INIT(name) { &(name), &(name) } #define LIST_HEAD(name) \ struct list_head name = LIST_HEAD_INIT(name) /** * container_of – cast a member of a structure out to the containing structure * @ptr: the pointer to the member. * @type: the type of the container struct this is embedded in. * @member: the name of the member within the struct. * */ #ifndef offsetof #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER) #endif #define container_of(ptr, type, member) ({ \ const typeof( ((type *)0)->member ) *__mptr = (ptr); \ (type *)( (char *)__mptr – offsetof(type,member) );}) static inline void INIT_LIST_HEAD(struct list_head *list) { list->next = list; list->prev = list; } /* * Insert a new entry between two known consecutive entries. * * This is only for internal list manipulation where we know * the prev/next entries already! */ #ifndef CONFIG_DEBUG_LIST static inline void __list_add(struct list_head *new, struct list_head *prev, struct list_head *next) { next->prev = new; new->next = next; new->prev = prev; prev->next = new; } #else extern void __list_add(struct list_head *new, struct list_head *prev, struct list_head *next); #endif /** * list_add – add a new entry * @new: new entry to be added * @head: list head to add it after * * Insert a new entry after the specified head. * This is good for implementing stacks. */ #ifndef CONFIG_DEBUG_LIST static inline void list_add(struct list_head *new, struct list_head *head) { __list_add(new, head, head->next); } #else extern void list_add(struct list_head *new, struct list_head *head); #endif /** * list_add_tail – add a new entry * @new: new entry to be added * @head: list head to add it before * * Insert a new entry before the specified head. * This is useful for implementing queues. */ static inline void list_add_tail(struct list_head *new, struct list_head *head) { __list_add(new, head->prev, head); } /* * Delete a list entry by making the prev/next entries * point to each other. * * This is only for internal list manipulation where we know * the prev/next entries already! */ static inline void __list_del(struct list_head * prev, struct list_head * next) { next->prev = prev; prev->next = next; } /** * list_del – deletes entry from list. * @entry: the element to delete from the list. * Note: list_empty() on entry does not return true after this, the entry is * in an undefined state. */ #ifndef CONFIG_DEBUG_LIST static inline void list_del(struct list_head *entry) { __list_del(entry->prev, entry->next); entry->next = LIST_POISON1; entry->prev = LIST_POISON2; } #else extern void list_del(struct list_head *entry); #endif /** * list_replace – replace old entry by new one * @old : the element to be replaced * @new : the new element to insert * * If @old was empty, it will be overwritten. */ static inline void list_replace(struct list_head *old, struct list_head *new) { new->next = old->next; new->next->prev = new; new->prev = old->prev; new->prev->next = new; } static inline void list_replace_init(struct list_head *old, struct list_head *new) { list_replace(old, new); INIT_LIST_HEAD(old); } /** * list_del_init – deletes entry from list and reinitialize it. * @entry: the element to delete from the list. */ static inline void list_del_init(struct list_head *entry) { __list_del(entry->prev, entry->next); INIT_LIST_HEAD(entry); } /** * list_move – delete from one list and add as anothers head * @list: the entry to move * @head: the head that will precede our entry */ static inline void list_move(struct list_head *list, struct list_head *head) { __list_del(list->prev, list->next); list_add(list, head); } /** * list_move_tail – delete from one list and add as anothers tail * @list: the entry to move * @head: the head that will follow our entry */ static inline void list_move_tail(struct list_head *list, struct list_head *head) { __list_del(list->prev, list->next); list_add_tail(list, head); } /** * list_is_last – tests whether @list is the last entry in list @head * @list: the entry to test * @head: the head of the list */ static inline int list_is_last(const struct list_head *list, const struct list_head *head) { return list->next == head; } /** * list_empty – tests whether a list is empty * @head: the list to test. */ static inline int list_empty(const struct list_head *head) { return head->next == head; } /** * list_empty_careful – tests whether a list is empty and not being modified * @head: the list to test * * Description: * tests whether a list is empty _and_ checks that no other CPU might be * in the process of modifying either member (next or prev) * * NOTE: using list_empty_careful() without synchronization * can only be safe if the only activity that can happen * to the list entry is list_del_init(). Eg. it cannot be used * if another CPU could re-list_add() it. */ static inline int list_empty_careful(const struct list_head *head) { struct list_head *next = head->next; return (next == head) && (next == head->prev); } static inline void __list_splice(struct list_head *list, struct list_head *head) { struct list_head *first = list->next; struct list_head *last = list->prev; struct list_head *at = head->next; first->prev = head; head->next = first; last->next = at; at->prev = last; } /** * list_splice – join two lists * @list: the new list to add. * @head: the place to add it in the first list. */ static inline void list_splice(struct list_head *list, struct list_head *head) { if (!list_empty(list)) __list_splice(list, head); } /** * list_splice_init – join two lists and reinitialise the emptied list. * @list: the new list to add. * @head: the place to add it in the first list. * * The list at @list is reinitialised */ static inline void list_splice_init(struct list_head *list, struct list_head *head) { if (!list_empty(list)) { __list_splice(list, head); INIT_LIST_HEAD(list); } } /** * list_entry – get the struct for this entry * @ptr: the &struct list_head pointer. * @type: the type of the struct this is embedded in. * @member: the name of the list_struct within the struct. */ #define list_entry(ptr, type, member) \ container_of(ptr, type, member) /** * list_first_entry – get the first element from a list * @ptr: the list head to take the element from. * @type: the type of the struct this is embedded in. * @member: the name of the list_struct within the struct. * * Note, that list is expected to be not empty. */ #define list_first_entry(ptr, type, member) \ list_entry((ptr)->next, type, member) /** * list_for_each – iterate over a list * @pos: the &struct list_head to use as a loop cursor. * @head: the head for your list. */ #define list_for_each(pos, head) \ for (pos = (head)->next; prefetch(pos->next), pos != (head); \ pos = pos->next) /** * __list_for_each – iterate over a list * @pos: the &struct list_head to use as a loop cursor. * @head: the head for your list. * * This variant differs from list_for_each() in that its the * simplest possible list iteration code, no prefetching is done. * Use this for code that knows the list to be very short (empty * or 1 entry) most of the time. */ #define __list_for_each(pos, head) \ for (pos = (head)->next; pos != (head); pos = pos->next) /** * list_for_each_prev – iterate over a list backwards * @pos: the &struct list_head to use as a loop cursor. * @head: the head for your list. */ #define list_for_each_prev(pos, head) \ for (pos = (head)->prev; prefetch(pos->prev), pos != (head); \ pos = pos->prev) /** * list_for_each_prev_safe – iterate over a list safe against removal of list entry backwards * @pos: the &struct list_head to use as a loop cursor. * @n: another &struct list_head to use as temporary storage * @head: the head for your list. */ #define list_for_each_prev_safe(pos, n, head) \ for (pos = (head)->prev, n = pos->prev; prefetch(pos->prev), pos != (head); \ pos =n, n = pos->prev) /** * list_for_each_safe – iterate over a list safe against removal of list entry * @pos: the &struct list_head to use as a loop cursor. * @n: another &struct list_head to use as temporary storage * @head: the head for your list. */ #define list_for_each_safe(pos, n, head) \ for (pos = (head)->next, n = pos->next; pos != (head); \ pos = n, n = pos->next) /** * list_for_each_entry – iterate over list of given type * @pos: the type * to use as a loop cursor. * @head: the head for your list. * @member: the name of the list_struct within the struct. */ #define list_for_each_entry(pos, head, member) \ for (pos = list_entry((head)->next, typeof(*pos), member); \ prefetch(pos->member.next), &pos->member != (head); \ pos = list_entry(pos->member.next, typeof(*pos), member)) /** * list_for_each_entry_reverse – iterate backwards over list of given type. * @pos: the type * to use as a loop cursor. * @head: the head for your list. * @member: the name of the list_struct within the struct. */ #define list_for_each_entry_reverse(pos, head, member) \ for (pos = list_entry((head)->prev, typeof(*pos), member); \ prefetch(pos->member.prev), &pos->member != (head); \ pos = list_entry(pos->member.prev, typeof(*pos), member)) /** * list_prepare_entry – prepare a pos entry for use in list_for_each_entry_continue() * @pos: the type * to use as a start point * @head: the head of the list * @member: the name of the list_struct within the struct. * * Prepares a pos entry for use as a start point in list_for_each_entry_continue(). */ #define list_prepare_entry(pos, head, member) \ ((pos) ? : list_entry(head, typeof(*pos), member)) /** * list_for_each_entry_continue – continue iteration over list of given type * @pos: the type * to use as a loop cursor. * @head: the head for your list. * @member: the name of the list_struct within the struct. * * Continue to iterate over list of given type, continuing after * the current position. */ #define list_for_each_entry_continue(pos, head, member) \ for (pos = list_entry(pos->member.next, typeof(*pos), member); \ prefetch(pos->member.next), &pos->member != (head); \ pos = list_entry(pos->member.next, typeof(*pos), member)) /** * list_for_each_entry_from – iterate over list of given type from the current point * @pos: the type * to use as a loop cursor. * @head: the head for your list. * @member: the name of the list_struct within the struct. * * Iterate over list of given type, continuing from current position. */ #define list_for_each_entry_from(pos, head, member) \ for (; prefetch(pos->member.next), &pos->member != (head); \ pos = list_entry(pos->member.next, typeof(*pos), member)) /** * list_for_each_entry_safe – iterate over list of given type safe against removal of list entry * @pos: the type * to use as a loop cursor. * @n: another type * to use as temporary storage * @head: the head for your list. * @member: the name of the list_struct within the struct. */ #define list_for_each_entry_safe(pos, n, head, member) \ for (pos = list_entry((head)->next, typeof(*pos), member), \ n = list_entry(pos->member.next, typeof(*pos), member); \ &pos->member != (head); \ pos = n, n = list_entry(n->member.next, typeof(*n), member)) /** * list_for_each_entry_safe_continue * @pos: the type * to use as a loop cursor. * @n: another type * to use as temporary storage * @head: the head for your list. * @member: the name of the list_struct within the struct. * * Iterate over list of given type, continuing after current point, * safe against removal of list entry. */ #define list_for_each_entry_safe_continue(pos, n, head, member) \ for (pos = list_entry(pos->member.next, typeof(*pos), member), \ n = list_entry(pos->member.next, typeof(*pos), member); \ &pos->member != (head); \ pos = n, n = list_entry(n->member.next, typeof(*n), member)) /** * list_for_each_entry_safe_from * @pos: the type * to use as a loop cursor. * @n: another type * to use as temporary storage * @head: the head for your list. * @member: the name of the list_struct within the struct. * * Iterate over list of given type from current point, safe against * removal of list entry. */ #define list_for_each_entry_safe_from(pos, n, head, member) \ for (n = list_entry(pos->member.next, typeof(*pos), member); \ &pos->member != (head); \ pos = n, n = list_entry(n->member.next, typeof(*n), member)) /** * list_for_each_entry_safe_reverse * @pos: the type * to use as a loop cursor. * @n: another type * to use as temporary storage * @head: the head for your list. * @member: the name of the list_struct within the struct. * * Iterate backwards over list of given type, safe against removal * of list entry. */ #define list_for_each_entry_safe_reverse(pos, n, head, member) \ for (pos = list_entry((head)->prev, typeof(*pos), member), \ n = list_entry(pos->member.prev, typeof(*pos), member); \ &pos->member != (head); \ pos = n, n = list_entry(n->member.prev, typeof(*n), member)) #endif

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-M8VFnglD-1662859888636)(data:image/gif;base64,R0lGODlhAQABAPABAP///wAAACH5BAEKAAAALAAAAAABAAEAAAICRAEAOw==)]

如何使用list.h创建单向链表并实现链表的基本操作？

以下代码将为你展示如何创建单向链表，及实现单向链表的基本操作：创建、添加、查找、修改、删除等。

复制/****************************************************************** 本文件借助linux_list.h实现【单向链表】的基本操作： 创建、添加、查找、修改、删除、销毁、打印等 ******************************************************************/ #include #include #include #include #include “linux_list.h” /** 查找链表的方向 */ #define LIST_FROM_HEAD_TO_TAIL 1 #define LIST_FROM_TAIL_TO_HEAD 0 /** 链表节点中存储的实际内容 */ typedef struct _data_node_t { int index; char msg[128]; } node_data_t; /** 链表节点的对外数据类型定义 */ typedef struct _my_list_node_t { node_data_t data; struct list_head list; } my_list_node_t ; /** 定义链表的表头 */ static my_list_node_t g_list_head; /** 定义链表当前的节点个数 */ static int g_list_node_cnt = 0; /** 链表创建 */ int my_list_create(void) { INIT_LIST_HEAD(&g_list_head.list); return 0; } /** 链表增加节点 */ int my_list_add_node(const node_data_t *data) { my_list_node_t *node; node = (my_list_node_t *)malloc(sizeof(my_list_node_t)); if (!node) { printf(“memory error !\n”); return -1; } node->data.index = data->index; snprintf(node->data.msg, sizeof(node->data.msg), “%s”, data->msg); list_add_tail(&node->list, &g_list_head.list); g_list_node_cnt ++; return 0; } /** 链表查找节点 */ my_list_node_t * my_list_query_node(const node_data_t *data) { struct list_head *pos,*n; my_list_node_t *p; list_for_each_safe(pos, n, &g_list_head.list) { p = list_entry(pos, my_list_node_t, list); if((p->data.index == data->index) && (!strcmp((char*)p->data.msg, data->msg))) { //printf(“found index=%d, msg=%s\n”, data->index, data->msg); return p; } } return NULL; } /** 链表将一个节点的内容进行修改 */ int my_list_modify_node(const node_data_t *old_data, const node_data_t *new_data) { my_list_node_t *p = my_list_query_node(old_data); if (p) { p->data.index = new_data->index; snprintf(p->data.msg, sizeof(p->data.msg), “%s”, new_data->msg); return 0; } else { printf(“Node index=%d, msg=%s, not found !\n”, old_data->index, old_data->msg); return -1; } } /** 链表删除一个节点 */ int my_list_delete_node(const node_data_t *data) { my_list_node_t *p = my_list_query_node(data); if (p) { struct list_head *pos = &p->list; list_del(pos); free(p); g_list_node_cnt –; return 0; } else { printf(“Node index=%d, msg=%s, not found !\n”, data->index, data->msg); return -1; } } /** 链表删除所有节点 */ int my_list_delete_all_node(void) { struct list_head *pos,*n; my_list_node_t *p; list_for_each_safe(pos, n, &g_list_head.list) { p = list_entry(pos, my_list_node_t, list); list_del(pos); free(p); } g_list_node_cnt = 0; return 0; } /** 链表销毁 */ int my_list_destory(void) { /** do nothing here ! */ return 0; } /** 链表内容打印 */ int my_list_print(int print_index) { int i = 1; struct list_head * pos,*n; my_list_node_t * node; printf(“==================== %d ===========================\n”, print_index); printf(“cur list data : g_list_node_cnt = %d \n”, g_list_node_cnt); list_for_each_safe(pos, n, &g_list_head.list) //调用linux_list.h中的list_for_each函数进行遍历 { node = list_entry(pos, my_list_node_t, list); //调用list_entry函数得到相对应的节点 printf(“Node %2ds : index=%-3d, msg=%-20s\n”, i++, node->data.index, node->data.msg); } printf(“==================================================\n”); return 0; } int main(int argc, const char *argv[]) { int retval = -1; my_list_node_t *p; const node_data_t data1 = {1, “a1bcde”}; const node_data_t data2 = {2, “ab2cde”}; const node_data_t data3 = {3, “abc3de”}; const node_data_t data4 = {4, “abcd4e”}; const node_data_t data5 = {5, “abcde5”}; const node_data_t data6 = {6, “abcde5666”}; // 定义一个不添加到链表的节点信息 const node_data_t data7 = {7, “abcde5777”}; // 定义一个被修改的节点信息 const node_data_t data8 = {8, “abcde5888”}; // 定义一个修改后的节点信息 /** 创建一个空链表 */ retval = my_list_create(); if (!retval) { printf(“list create ok !!!\n”); } printf(“\n\n\n”); /** 往链表的尾部添加6个节点 */ retval = my_list_add_node(&data1); if (!retval) { printf(“node1 add ok !\n”); } retval = my_list_add_node(&data2); if (!retval) { printf(“node2 add ok !\n”); } retval = my_list_add_node(&data3); if (!retval) { printf(“node3 add ok !\n”); } retval = my_list_add_node(&data4); if (!retval) { printf(“node4 add ok !\n”); } retval = my_list_add_node(&data5); if (!retval) { printf(“node5 add ok !\n”); } retval = my_list_add_node(&data7); if (!retval) { printf(“node7 add ok !\n”); } printf(“\n\n\n”); /** 分别查询刚刚添加的前5个节点 */ p = my_list_query_node(&data1); if (p) { printf(“node %d,%s, found !!!\n”, data1.index, data1.msg); } p = my_list_query_node(&data2); if (p) { printf(“node %d,%s, found !!!\n”, data2.index, data2.msg); } p = my_list_query_node(&data3); if (p) { printf(“node %d,%s, found !!!\n”, data3.index, data3.msg); } p = my_list_query_node(&data4); if (p) { printf(“node %d,%s, found !!!\n”, data4.index, data4.msg); } p = my_list_query_node(&data5); if (p) { printf(“node %d,%s, found !!!\n”, data5.index, data5.msg); } /** 查询一个没有添加到链表中的节点，即不存在的节点 */ p = my_list_query_node(&data6); if (!p) { printf(“node %d,%s, found fail !!!\n”, data6.index, data6.msg); } /** 打印当前链表的节点信息 */ printf(“\n\n\n”); my_list_print(1); printf(“\n\n\n”); /** 将data7的信息修改为data8的内容 */ retval = my_list_modify_node(&data7, &data8); if (!retval) { printf(“node %d,%s => %d,%s, modify ok !!!\n”, data7.index, data7.msg, data8.index, data8.msg); } else { printf(“node %d,%s => %d,%s, modify fail !!!\n”, data7.index, data7.msg, data8.index, data8.msg); } /** 查询刚刚被修改了的节点data7，即不存在的节点 */ p = my_list_query_node(&data7); if (!p) { printf(“node %d,%s, found fail !!!\n”, data7.index, data7.msg); } /** 查询刚刚被修改后的节点data8，即存在的节点 */ p = my_list_query_node(&data8); if (p) { printf(“node %d,%s, found ok !!!\n”, data8.index, data8.msg); } /** 打印当前链表的节点信息 */ printf(“\n\n\n”); my_list_print(2); printf(“\n\n\n”); /** 删除一个存在于链表中的节点 */ retval = my_list_delete_node(&data4); if (!retval) { printf(“node %d,%s, delete ok !!!\n”, data4.index, data4.msg); } printf(“\n\n\n”); /** 再次查询刚刚已删除的节点 */ p = my_list_query_node(&data4); if (p) { printf(“node %d,%s, found ok !!!\n”, data4.index, data4.msg); } else { printf(“node %d,%s, found fail !!!\n”, data4.index, data4.msg); } printf(“\n\n\n”); /** 删除一个不存在于链表中的节点 */ retval = my_list_delete_node(&data6); if (retval) { printf(“node %d,%s, delete fail !!!\n”, data6.index, data6.msg); } /** 打印当前链表的节点信息 */ printf(“\n\n\n”); my_list_print(3); printf(“\n\n\n”); /** 删除链表的所有节点 */ retval = my_list_delete_all_node(); if (!retval) { printf(“all list notes delete done !\n”); } /** 打印当前链表的节点信息 */ printf(“\n\n\n”); my_list_print(4); printf(“\n\n\n”); /** 销毁链表 */ retval = my_list_destory(); if (!retval) { printf(“list destory done !\n”); } /** 打印当前链表的节点信息 */ printf(“\n\n\n”); my_list_print(5); printf(“\n\n\n”); return retval; }

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-7r1QKtXf-1662859888641)(data:image/gif;base64,R0lGODlhAQABAPABAP///wAAACH5BAEKAAAALAAAAAABAAEAAAICRAEAOw==)]

示例代码比较简单，相关代码都有详尽注释，我们整理下main函数里面的操作：

先创建一个空的链表，接着往链表添加6个节点，接着查询前5个节点，查询一个不存在的节点，将最后一个节点的信息做修改，查找刚刚被修改前的节点及被修改后的节点，删除一个存在于链表的节点，接着查询这个被删除的节点，删除一个不存在于链表中的节点，删除所有节点，销毁链表。期间有打印各个时间段的链表节点情况，可供参考。

跑出的结果如下：

复制root@liluchang-ubuntu:/share/llc/linux_list# ./linux_list list create ok !!! node1 add ok ! node2 add ok ! node3 add ok ! node4 add ok ! node5 add ok ! node7 add ok ! node 1,a1bcde, found !!! node 2,ab2cde, found !!! node 3,abc3de, found !!! node 4,abcd4e, found !!! node 5,abcde5, found !!! node 6,abcde5666, found fail !!! ==================== 1 =========================== cur list data : g_list_node_cnt = 6 Node 1s : index=1 , msg=a1bcde Node 2s : index=2 , msg=ab2cde Node 3s : index=3 , msg=abc3de Node 4s : index=4 , msg=abcd4e Node 5s : index=5 , msg=abcde5 Node 6s : index=7 , msg=abcde5777 ================================================== node 7,abcde5777 => 8,abcde5888, modify ok !!! node 7,abcde5777, found fail !!! node 8,abcde5888, found ok !!! ==================== 2 =========================== cur list data : g_list_node_cnt = 6 Node 1s : index=1 , msg=a1bcde Node 2s : index=2 , msg=ab2cde Node 3s : index=3 , msg=abc3de Node 4s : index=4 , msg=abcd4e Node 5s : index=5 , msg=abcde5 Node 6s : index=8 , msg=abcde5888 ================================================== node 4,abcd4e, delete ok !!! node 4,abcd4e, found fail !!! Node index=6, msg=abcde5666, not found ! node 6,abcde5666, delete fail !!! ==================== 3 =========================== cur list data : g_list_node_cnt = 5 Node 1s : index=1 , msg=a1bcde Node 2s : index=2 , msg=ab2cde Node 3s : index=3 , msg=abc3de Node 4s : index=5 , msg=abcde5 Node 5s : index=8 , msg=abcde5888 ================================================== all list notes delete done ! ==================== 4 =========================== cur list data : g_list_node_cnt = 0 ================================================== list destory done ! ==================== 5 =========================== cur list data : g_list_node_cnt = 0 ==================================================

从测试的结果看，所有链表的操作均得到了正确的结果。

好了，本次关于Linux内核的list.h在单向链表中的应用，就介绍到这里，如果有疑问，欢迎在评论席提出。感谢您的阅读。