list_entry定义
/*** 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) / ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
在Linux内核中，函数list_entry()用来获取节点地址.
其不难理解为:从一个结构的成员指针找到其容器的指针。
- ptr是找容器的那个变量的指针，把它减去自己在容器中的偏移量的值就应该 得到容器的指针。（容器就是包含自己的那个结构）。
- 指针的加减要注意类型，用(char*)ptr是为了计算字节偏移。
- ((type *)0)->member是一个小技巧。
- 前面的（type *）再转回容器的类型。
#define list_entry(ptr, type, member) / ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member))
- ptr是指向list_head类型链表的指针
- type为一个结构
- 而member为结构type中的一个域，类型为list_head
- 这个宏返回指向type结构的指针
在内核代码中大量引用了这个宏，因此，搞清楚这个宏的含义和用法非常重要。
设有如下结构体定义：
typedef struct xxx{ ……（结构体中其他域，令其总大小为size1） type1 member; ……（结构体中其他域）}type; 定义变量：
type a;type * b;type1 * ptr;
执行：
ptr=&(a.member);b=list_entry(ptr,type,member);
这样就使b指向a，得到了a的地址。
如何做到的呢？
&((type *)0)->member
把“0”强制转化为指针类型，则该指针一定指向“0”（数据段基址）。
因为指针是“type *”型的，所以可取到以“0”为基地址的一个type型变量member域的地址。
那么这个地址也就等于member域到结构体基地址的偏移字节数。
((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
(char *)(ptr)使得指针的加减操作步长为一字节，(unsigned long)(&((type *)0)->member)等于ptr指向的member到该member所在结构体基地址的偏移字节数。二者一减便得出该结构体的地址。转换为 (type *)型的指针，便大功告成。
list.h注释
每一个熟悉内核的程序员，写出来的程序会更加优美和高效，因为内核代码本身就是优美和高效的，我们可以加以借荐；
但是内核的庞大程度与复杂的各种结构使很多人望而生畏，因此我把经常使用的内核链表核心文件给加了注释，以方便使用。
1 //################ 注释：By 成鹏致远 ################// 2 //################ net ：infodown.tap.cn ################// 3 //################ time：2013-7-30 ################// 4 5 6 #ifndef __DLIST_H 7 #define __DLIST_H 8 9 /* This file is from Linux Kernel (include/linux/list.h) //————————>位置 10 * and modified by simply removing hardware prefetching of list items. //————————>在预处理阶段对链表项进行替换 11 * Here by copyright, credits attributed to wherever they belong. 12 * Kulesh Shanmugasundaram (kulesh [squiggly] isis.poly.edu) 13 */ 14 15 /* 16 * Simple doubly linked list implementation. //————————>简单的双向链表实现 17 * 18 * Some of the internal functions (“__xxx”) are useful when 19 * manipulating whole lists rather than single entries, as //————————>最好对整个链表进行操作 20 * sometimes we already know the next/prev entries and we can 21 * generate better code by using them directly rather than 22 * using the generic single-entry routines. 23 */ 24 25 26 //################ 通过内部结构指针返回外部容器指针 ################// 27 /** 28 * container_of - cast a member of a structure out to the containing structure //————————>container_of：从一个结构的成员指针找到其容器的指针 29 * 30 * @ptr: the pointer to the member. //————————>ptr：指向menber的指针，即找容器的那个变量的指针 31 * @type: the type of the container struct this is embedded in. //————————>type：容器的类型 32 * @member: the name of the member within the struct. //————————>member：容器中struct类型成员 33 * 34 */ 35 #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER) //————————>offsetof：TYPE结构类型中MEMBER结构指针与TYPE结构指针的偏移量 36 37 #define container_of(ptr, type, member) ({ \ //————————>container_of：从一个结构的成员指针找到其容器的指针 38 const typeof( ((type *)0)->member ) *__mptr = (ptr); \ //————————>ptr：指向menber的指针，即找容器的那个变量的指针 39 (type *)( (char *)__mptr - offsetof(type,member) );}) //————————>type：容器的类型 40 //————————>member：容器中struct类型成员 41 42 43 44 45 46 //################ 链表初始化 ################// 47 /* 48 * These are non-NULL pointers that will result in page faults //————————>野指针会导致页面出错 49 * under normal circumstances, used to verify that nobody uses //————————>以下初始化方法保证了不会出现野指针（确认没有空指针传入） 50 * non-initialized list entries. 51 */ 52 #define LIST_POISON1 ((void *) 0x00100100) 53 #define LIST_POISON2 ((void *) 0x00200 54 55 struct list_head { //————————>内核链表结构 56 struct list_head *next, *prev; 57 }; 58 59 #define LIST_HEAD_INIT(name) { &(name), &(name) } //————————>LIST_HEAD_INIT(name)：用name来初始化链表 60 61 #define LIST_HEAD(name) \ //————————>LIST_HEAD(name)：间接用LIST_HEAD_INIT(name)来初始化链表，本质：LIST_HEAD(name)用来定义+初始化 62 struct list_head name = LIST_HEAD_INIT(name) 63 64 #define INIT_LIST_HEAD(ptr) do { \ //————————>运行时初始化，功能相同：初始化 65 (ptr)->next = (ptr); (ptr)->prev = (ptr); \ 66 } while (0) 67 68 69 70 71 72 73 //################ 链表插入算法 ################// 74 /* 75 * Insert a new entry between two known consecutive entries. //————————>在两个连续的结点间插入新的结点 76 * 77 * This is only for internal list manipulation where we know //————————>只能用于操作已知prev和next指针的内部链表 78 * the prev/next entries already! 79 */ 80 static inline void __list_add(struct list_head *new, //————————>__list_add：内联静态函数 81 struct list_head *prev, //————————>参数：三个指向list_head的结构体指针（新结点，前向结点，后向结点） 82 struct list_head *next) 83 { 84 next->prev = new; //————————>双向链表中插入new结点 85 new->next = next; 86 new->prev = prev; 87 prev->next = new; 88 } 89 90 /** 91 * list_add – add a new entry //————————>list_add：头插法增加新节点 92 * @new: new entry to be added //————————>new：新节点指针 93 * @head: list head to add it after //————————>head：链表头结点指针，在之后插入 94 * 95 * Insert a new entry after the specified head. //————————>头插法 96 * This is good for implementing stacks. //————————>符合栈操作 97 */ 98 static inline void list_add(struct list_head *new, struct list_head *head) //————————>list_add：在head后面插入new 99 { //————————>new：新节点指针100 __list_add(new, head, head->next); //————————>head：链表头结点指针101 }102 103 /**104 * list_add_tail – add a new entry //————————>list_add_tail ：尾插法增加新节点105 * @new: new entry to be added //————————>new：新节点指针106 * @head: list head to add it beforer //————————>head：链表头结点指针，在之前插入107 *108 * Insert a new entry before the specified head.109 * This is useful for implementing queues. //————————>符合队列操作110 */111 static inline void list_add_tail(struct list_head *new, struct list_head *head) //————————>list_add_tail ：在head前面插入new112 {113 __list_add(new, head->prev, head);114 }115 116 117 118 //################ 链表删除算法 ################//119 /*120 * Delete a list entry by making the prev/next entries //————————>通过改变prev和next的指向来删除节点121 * point to each other.122 *123 * This is only for internal list manipulation where we know //————————>同样只能用于操作已知prev和next指针的内部链表124 * the prev/next entries already!125 */126 static inline void __list_del(struct list_head *prev, struct list_head *next) //————————>__list_del：删除结点127 { //————————>prev：待删除结点的前向指针128 next->prev = prev; //————————>next：待删除结点的后向指针129 prev->next = next;130 }131 132 /**133 * list_del – deletes entry from list. //————————>list_del：删除节点134 * @entry: the element to delete from the list. //————————>entry：要删除的结点135 * Note: list_empty on entry does not return true after this, the entry is in an undefined state. //————————>操作后调用list_empty则返回随机值136 */137 static inline void list_del(struct list_head *entry) //————————>删除entry结点138 {139 __list_del(entry->prev, entry->next);140 entry->next = (void *) 0; //————————>置空141 entry->prev = (void *) 0;142 }143 144 /**145 * list_del_init – deletes entry from list and reinitialize it. //————————>list_del_init：删除并初始化节点146 * @entry: the element to delete from the list.147 */148 static inline void list_del_init(struct list_head *entry) //————————>删除并初始化entry指向的结点149 {150 __list_del(entry->prev, entry->next); //————————>删除151 INIT_LIST_HEAD(entry); //————————>然后初始化152 }153 154 155 156 //################ 链表移动算法 ################//157 /**158 * list_move – delete from one list and add as another’s head //————————>list_move：从链表中删除一个节点并添加到另一个链表头部159 * @list: the entry to move //————————>list：要移动的节点160 * @head: the head that will precede our entry //————————>head：目标链表的头结点161 */162 static inline void list_move(struct list_head *list, //————————>list_move：从链表中删除list并添加到head后面163 struct list_head *head)164 {165 __list_del(list->prev, list->next); //————————>先删除166 list_add(list, head); //————————>然后在head后面添加list167 }168 169 /**170 * list_move_tail – delete from one list and add as another’s tail //————————>list_move_tail：从链表中删除一个节点并添加到另一个链表尾部171 * @list: the entry to move172 * @head: the head that will follow our entry173 */174 static inline void list_move_tail(struct list_head *list, //————————>list_move_tail：从链表中删除list并添加到head前部175 struct list_head *head)176 {177 __list_del(list->prev, list->next); //————————>先删除178 list_add_tail(list, head); //————————>然后在head前面添加list179 }180 181 182 //################ 判断链表空状态 ################//183 /**184 * list_empty – tests whether a list is empty185 * @head: the list to test.186 */187 static inline int list_empty(struct list_head *head) //————————>list_empty：判断head指向的链表是否为空188 {189 return head->next == head; //————————>只有一个头结点190 }191 192 193 //################ 链表合并算法 ################//194 195 static inline void __list_splice(struct list_head *list, //————————>__list_splice：将list链表合并到head链表上196 struct list_head *head)197 {198 struct list_head *first = list->next; //————————>list的首结点199 struct list_head *last = list->prev; //————————>list的尾结点200 struct list_head *at = head->next; //————————>head的首结点201 //————————>将list所以结点链接到head的后面202 first->prev = head; //————————>list首结点向前指向head203 head->next = first; //————————>head向后指向list的首结点204 205 last->next = at; //————————>list的尾结点向后指向head的首结点206 at->prev = last; //————————>head的首结点向前指向list的尾结点207 }208 209 /**210 * list_splice – join two lists //————————>list_splice：合并两个链表211 * @list: the new list to add. //————————>list：要合并的链表212 * @head: the place to add it in the first list. //————————>目标链表213 */214 static inline void list_splice(struct list_head *list, struct list_head *head) //————————>list_splice：将list合并到head后面215 {216 if (!list_empty(list)) //————————>条件：list链表不为空217 __list_splice(list, head);218 }219 220 /**221 * list_splice_init – join two lists and reinitialise the emptied list. //————————>list_splice_init：合并两个链表并重新初始化被链接的链表2013-7-30222 * @list: the new list to add. //————————>list：要合并的链表223 * @head: the place to add it in the first list. //————————>目标链表224 *225 * The list at @list is reinitialised //————————>list：被重新初始化226 */227 static inline void list_splice_init(struct list_head *list, //————————>list_splice_init：将list合并到head，并重新初始化list228 struct list_head *head)229 {230 if (!list_empty(list)) { //————————>条件：list链表不为空231 __list_splice(list, head);232 INIT_LIST_HEAD(list);233 }234 }235 236 237 //################ 通过内部结构指针返回外部容器指针 ################//238 /**239 * list_entry – get the struct for this entry //————————>list_entry：得到结点的外部结构地址240 * @ptr: the &struct list_head pointer. //————————>ptr：指向struct list_head类型链表的指针241 * @type: the type of the struct this is embedded in. //————————>type：包含结点的结构体类型242 * @member: the name of the list_struct within the struct. //————————>member：type结构中的结点类型243 */244 #define list_entry(ptr, type, member) \ //————————>list_entry：得到type结构的指针245 ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member))) //————————>ptr：指向struct list_head类型链表的指针246 //————————>type：包含结点的结构体类型247 //————————>member：type结构中的结点类型248 249 250 251 //################ 链表遍历算法 ################//252 /**253 * list_for_each - iterate over a list //————————>list_for_each：迭代一个链表254 * @pos: the &struct list_head to use as a loop counter. //————————>pos：循环计数器，struct list_head类型255 * @head: the head for your list. //————————>遍历链表头指针256 */257 #define list_for_each(pos, head) \ //————————>list_for_each：利用for循环迭代head指向的链表258 for (pos = (head)->next; pos != (head); \259 pos = pos->next) //————————>通过next指针逐项后移260 261 /**262 * list_for_each_prev - iterate over a list backwards //————————>list_for_each_prev：反向迭代一个链表263 * @pos: the &struct list_head to use as a loop counter. //————————>pos：循环计数器，struct list_head类型264 * @head: the head for your list. //————————>遍历链表头指针265 */266 #define list_for_each_prev(pos, head) \ //————————>list_for_each_prev：利用for循环反向迭代head指向的链表267 for (pos = (head)->prev; pos != (head); \268 pos = pos->prev) //————————>也是通过next指针逐项后移269 270 /**271 * list_for_each_safe - iterate over a list safe against removal of list entry //————————>list_for_each_safe：迭代一个链表272 * @pos: the &struct list_head to use as a loop counter.273 * @n: another &struct list_head to use as temporary storage //————————>多用一个临时辅助变量进行迭代274 * @head: the head for your list.275 */276 #define list_for_each_safe(pos, n, head) \277 for (pos = (head)->next, n = pos->next; pos != (head); \278 pos = n, n = pos->next)279 280 /**281 * list_for_each_entry - iterate over list of given type //————————>list_for_each_entry：遍历链表中的内核链表容器结构282 * @pos: the type * to use as a loop counter. //————————>数据项结构指针类型，指向外部结构体283 * @head: the head for your list. //————————>遍历链表头指针284 * @member: the name of the list_struct within the struct. //————————>链表中结构成员的名字285 */286 #define list_for_each_entry(pos, head, member) \ //————————>list_for_each_entry：遍历head指向的链表的容器结构（外部结构体）287 for (pos = list_entry((head)->next, typeof(*pos), member); \288 &pos->member != (head); \289 pos = list_entry(pos->member.next, typeof(*pos), member)) //————————>通过list_entry传入next来遍历外部结构290 291 /**292 * list_for_each_entry_safe – iterate over list of given type safe against removal of list entry //————————>llist_for_each_entry_safe：遍历链表中的内核链表容器结构293 * @pos: the type * to use as a loop counter.294 * @n: another type * to use as temporary storage //————————>多用一个临时辅助变量进行迭代295 * @head: the head for your list.296 * @member: the name of the list_struct within the struct.297 */298 #define list_for_each_entry_safe(pos, n, head, member) \ //————————>list_for_each_entry_safe：遍历head指向的链表的容器结构（外部结构体）299 for (pos = list_entry((head)->next, typeof(*pos), member), \300 n = list_entry(pos->member.next, typeof(*pos), member); \301 &pos->member != (head); \302 pos = n, n = list_entry(n->member.next, typeof(*n), member))303 304 #endif