Linux内核中双向链表的经典实现

(08). 遍历节点

#define list_for_each(pos, head) 
    for (pos = (head)->next; pos != (head); pos = pos->next)

#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(pos, head)和list_for_each_safe(pos, n, head)的作用都是遍历链表。但是它们的用途不一样！

list_for_each(pos, head)通常用于获取节点，而不能用到删除节点的场景。

list_for_each_safe(pos, n, head)通常删除节点的场景。

3. Linux中双向链表的使用示例

双向链表代码(list.h)

  1 #ifndef _LIST_HEAD_H
  2 #define _LIST_HEAD_H
  3 
  4 // 双向链表节点
  5 struct list_head {
  6     struct list_head *next, *prev;
  7 };
  8 
  9 // 初始化节点：设置name节点的前继节点和后继节点都是指向name本身。
 10 #define LIST_HEAD_INIT(name) { &(name), &(name) }
 11 
 12 // 定义表头(节点)：新建双向链表表头name，并设置name的前继节点和后继节点都是指向name本身。
 13 #define LIST_HEAD(name) 
 14     struct list_head name = LIST_HEAD_INIT(name)
 15 
 16 // 初始化节点：将list节点的前继节点和后继节点都是指向list本身。
 17 static inline void INIT_LIST_HEAD(struct list_head *list)
 18 {
 19     list->next = list;
 20     list->prev = list;
 21 }
 22 
 23 // 添加节点：将new插入到prev和next之间。
 24 static inline void __list_add(struct list_head *new,
 25                   struct list_head *prev,
 26                   struct list_head *next)
 27 {
 28     next->prev = new;
 29     new->next = next;
 30     new->prev = prev;
 31     prev->next = new;
 32 }
 33 
 34 // 添加new节点：将new添加到head之后，是new称为head的后继节点。
 35 static inline void list_add(struct list_head *new, struct list_head *head)
 36 {
 37     __list_add(new, head, head->next);
 38 }
 39 
 40 // 添加new节点：将new添加到head之前，即将new添加到双链表的末尾。
 41 static inline void list_add_tail(struct list_head *new, struct list_head *head)
 42 {
 43     __list_add(new, head->prev, head);
 44 }
 45 
 46 // 从双链表中删除entry节点。
 47 static inline void __list_del(struct list_head * prev, struct list_head * next)
 48 {
 49     next->prev = prev;
 50     prev->next = next;
 51 }
 52 
 53 // 从双链表中删除entry节点。
 54 static inline void list_del(struct list_head *entry)
 55 {
 56     __list_del(entry->prev, entry->next);
 57 }
 58 
 59 // 从双链表中删除entry节点。
 60 static inline void __list_del_entry(struct list_head *entry)
 61 {
 62     __list_del(entry->prev, entry->next);
 63 }
 64 
 65 // 从双链表中删除entry节点，并将entry节点的前继节点和后继节点都指向entry本身。
 66 static inline void list_del_init(struct list_head *entry)
 67 {
 68     __list_del_entry(entry);
 69     INIT_LIST_HEAD(entry);
 70 }
 71 
 72 // 用new节点取代old节点
 73 static inline void list_replace(struct list_head *old,
 74                 struct list_head *new)
 75 {
 76     new->next = old->next;
 77     new->next->prev = new;
 78     new->prev = old->prev;
 79     new->prev->next = new;
 80 }
 81 
 82 // 双链表是否为空
 83 static inline int list_empty(const struct list_head *head)
 84 {
 85     return head->next == head;
 86 }
 87 
 88 // 获取"MEMBER成员"在"结构体TYPE"中的位置偏移
 89 #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
 90 
 91 // 根据"结构体(type)变量"中的"域成员变量(member)的指针(ptr)"来获取指向整个结构体变量的指针
 92 #define container_of(ptr, type, member) ({          
 93     const typeof( ((type *)0)->member ) *__mptr = (ptr);    
 94     (type *)( (char *)__mptr - offsetof(type,member) );})
 95 
 96 // 遍历双向链表
 97 #define list_for_each(pos, head) 
 98     for (pos = (head)->next; pos != (head); pos = pos->next)
 99 
100 #define list_for_each_safe(pos, n, head) 
101     for (pos = (head)->next, n = pos->next; pos != (head); 
102         pos = n, n = pos->next)
103 
104 #define list_entry(ptr, type, member) 
105     container_of(ptr, type, member)
106 
107 #endif

双向链表测试代码(test.c)

 1 #include <stdio.h> 
 2 #include <stdlib.h>
 3 #include <string.h>
 4 #include "list.h" 
 5 
 6 struct person 
 7 { 
 8     int age; 
 9     char name[20];
10     struct list_head list; 
11 };
12 
13 void main(int argc, char* argv[]) 
14 { 
15     struct person *pperson; 
16     struct person person_head; 
17     struct list_head *pos, *next; 
18     int i;
19 
20     // 初始化双链表的表头 
21     INIT_LIST_HEAD(&person_head.list); 
22 
23     // 添加节点
24     for (i=0; i<5; i++)
25     {
26         pperson = (struct person*)malloc(sizeof(struct person));
27         pperson->age = (i+1)*10;
28         sprintf(pperson->name, "%d", i+1);
29         // 将节点链接到链表的末尾 
30         // 如果想把节点链接到链表的表头后面，则使用 list_add
31         list_add_tail(&(pperson->list), &(person_head.list));
32     }
33 
34     // 遍历链表
35     printf("==== 1st iterator d-link ====n"); 
36     list_for_each(pos, &person_head.list) 
37     { 
38         pperson = list_entry(pos, struct person, list); 
39         printf("name:%-2s, age:%dn", pperson->name, pperson->age); 
40     } 
41 
42     // 删除节点age为20的节点
43     printf("==== delete node(age:20) ====n");
44     list_for_each_safe(pos, next, &person_head.list)
45     {
46         pperson = list_entry(pos, struct person, list);
47         if(pperson->age == 20)
48         {
49             list_del_init(pos);
50             free(pperson);
51         }
52     }
53 
54     // 再次遍历链表
55     printf("==== 2nd iterator d-link ====n");
56     list_for_each(pos, &person_head.list)
57     {
58         pperson = list_entry(pos, struct person, list);
59         printf("name:%-2s, age:%dn", pperson->name, pperson->age);
60     }
61 
62     // 释放资源
63     list_for_each_safe(pos, next, &person_head.list)
64     {
65         pperson = list_entry(pos, struct person, list); 
66         list_del_init(pos); 
67         free(pperson); 
68     }
69      
70 }

（编辑：佛山站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!