生活随笔
收集整理的這篇文章主要介紹了
linux内核中链表代码分析---list.h头文件分析（二）【转】
小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
轉(zhuǎn)自：http://blog.chinaunix.net/uid-30254565-id-5637598.html
linux內(nèi)核中鏈表代碼分析---list.h頭文件分析（二） 16年2月28日16:59:55 分析完container_of()宏以后，繼續(xù)分析list.h文件： （1）list_entry 它就是一個(gè)container_of宏，都是得到ptr所指地址的這個(gè)結(jié)構(gòu)體的首地址 #define list_entry(ptr, type, member) \ ????container_of(ptr, type, member) （2） list_first_entry #define list_first_entry(ptr, type, member) \ ????list_entry((ptr)->next, type, member) 這里的ptr是一個(gè)鏈表的頭節(jié)點(diǎn),這個(gè)宏就是取得這個(gè)鏈表第一元素的所指結(jié)構(gòu)體的首地址。 （3） list_for_each #define list_for_each(pos, head) \ ????for (pos = (head)->next; pos != (head); pos = pos->next) 它實(shí)際上就是一個(gè)for循環(huán)，從頭到尾遍歷鏈表，但是看代碼發(fā)現(xiàn)，遍歷鏈表需要一個(gè)head參數(shù)即可，這個(gè)pos參數(shù)好像沒什么用啊。。。 然后就在內(nèi)核中g(shù)rep了一番，稍微總結(jié)出來一點(diǎn)： 這是一個(gè)for循環(huán)，我們通過這個(gè)for循環(huán)總得做點(diǎn)什么事情吧，以下面這個(gè)為例， 源文件在/driver/input/serio/hil_mlc.c中： static LIST_HEAD(hil_mlcs); static void hil_mlcs_process(unsigned long unused) { ????struct list_head *tmp; ????read_lock(&hil_mlcs_lock); ????list_for_each(tmp, &hil_mlcs) { ????????struct hil_mlc *mlc = list_entry(tmp, hil_mlc, list); ????????.... } 可以看到，它通過這個(gè)list_for_each函數(shù)，將hil_mlcs鏈表中的每一個(gè)成員地址一一賦給了tmp變量，這樣，在后面的語句中，就可以通過list_entry這個(gè)宏根據(jù)tmp變量和list鏈表頭來找到包含他們的整個(gè)結(jié)構(gòu)體hil_mlc的首地址，然后就可以對這個(gè)結(jié)構(gòu)體里面其他的成員變量進(jìn)行操作了～～～ 這一塊涉及到linux中，比如對于每一個(gè)子設(shè)備，都建立一個(gè)結(jié)構(gòu)體，然后將這些子設(shè)備通過一個(gè)鏈表鏈接起來，操作的時(shí)候需要遍歷鏈表中的每一項(xiàng)進(jìn)行操作，所以就是這個(gè)函數(shù)存在的意義。 后面那個(gè) __list_for_each和list_for_each相同，以前這兩個(gè)函數(shù)是不同的，它有一個(gè)prefetch預(yù)取的操作，我們不再考慮。 （4）list_for_each_prev #define list_for_each_prev(pos, head) \ ????for (pos = (head)->prev; pos != (head); pos = pos->prev) 與list_for_each相似，只是它是從尾到頭遍歷鏈表，將鏈表中的每一項(xiàng)都取出來操作。 （5）list_for_each_safe #define list_for_each_safe(pos, n, head) \ ????for (pos = (head)->next, n = pos->next; pos != (head); \ ????????pos = n, n = pos->next) 這個(gè)實(shí)際上就是一個(gè)for循環(huán),從頭到尾遍歷鏈表。這里使用了n來記錄pos的下一個(gè),這樣處理完一 個(gè)流程之后再賦給pos,避免了刪除pos結(jié)點(diǎn)造成的問題。這個(gè)函數(shù)是 專門為刪除結(jié)點(diǎn)是準(zhǔn)備的。 注:list_for_each(pos, head)和list_for_each_safe(pos, n, head)都是從頭至尾遍歷鏈表的,但是對于前者 來說當(dāng)操作中沒有刪除結(jié)點(diǎn)的時(shí)候使用,但是如果操作中有刪除結(jié)點(diǎn)的操作的時(shí)候就使用后者,對于后面帶safe的一般都是這個(gè)目的。 （6） list_for_each_prev_safe #define list_for_each_prev_safe(pos, n, head) \ ????for (pos = (head)->prev, n = pos->prev; \ ???? pos != (head); \ ???? pos = n, n = pos->prev) 同理，這個(gè)函數(shù)與 list_for_each_prev相似。 /* 注意上面的幾個(gè)函數(shù)，他們的行參里面有pos與下面函數(shù)行參里面的pos不同，上面函數(shù)的操作都是pos = (head)->next等等的操作，所以pos是list_head類型的，下面函數(shù)的操作是pos = list_entry()等等的操作，所以他們是list_head結(jié)構(gòu)體所嵌入的結(jié)構(gòu)體的指針形式的，我們稱之為宿主結(jié)構(gòu)體。 */ （7） list_for_each_entry #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)) 第一個(gè)參數(shù)為傳入的遍歷指針,指向宿主數(shù)據(jù)結(jié)構(gòu),第二個(gè)參數(shù)為鏈表頭,為list_head結(jié)構(gòu),第三 個(gè)參數(shù)為list_head結(jié)構(gòu)在宿主結(jié)構(gòu)中的成員名。 這個(gè)函數(shù)是根據(jù)member成員遍歷head鏈表（member成員一般都嵌入在宿主結(jié)構(gòu)體中）,并且將每個(gè)結(jié)構(gòu)體的首地址賦值給pos,這樣的話,我們就 可以在循環(huán)體里面通過pos來訪問該宿主結(jié)構(gòu)體變量的其他成員了。 下面用最近分析的V4L2里面的一段代碼來舉例說明，代碼位于v4l2-device.c中： int v4l2_device_register_subdev_nodes(struct v4l2_device *v4l2_dev) { ????struct video_device *vdev; ????struct v4l2_subdev *sd; ????list_for_each_entry(sd, &v4l2_dev->subdevs, list) { ????????if (!(sd->flags & V4L2_SUBDEV_FL_HAS_DEVNODE)) ????????????continue; ????。。。。 } 可以分析出來， v4l2_device結(jié)構(gòu)體里面含有這個(gè) subdevs鏈表頭，sd是指向v4l2_subdev結(jié)構(gòu)體的指針，list是一個(gè)list_head結(jié)構(gòu)，在之前的代碼中，肯定有操作已經(jīng)將各個(gè)子設(shè)備結(jié)構(gòu)體v4l2_subdev全部鏈接進(jìn) v4l2_device結(jié)構(gòu)體里面的 subdevs鏈表里面，這時(shí)候需要做的就是從這個(gè)v4l2_device結(jié)構(gòu)體里面的 subdevs鏈表里一一取出各個(gè)子設(shè)備結(jié)構(gòu)體v4l2_subdev，然后操作它的各個(gè)成員變量。上述代碼就是完成這個(gè)工作。 （8） list_for_each_entry_reverse #define list_for_each_entry_reverse(pos, head, member)????????????\ ????for (pos = list_entry((head)->prev, typeof(*pos), member);????\ ???? &pos->member != (head); ????\ ???? pos = list_entry(pos->member.prev, typeof(*pos), member)) 與上面那個(gè)函數(shù)類似，反向遍歷鏈表。 （9） list_prepare_entry #define list_prepare_entry(pos, head, member) \ ????((pos) ? : list_entry(head, typeof(*pos), member)) 第一個(gè)參數(shù)為傳入的遍歷指針,指向宿主數(shù)據(jù)結(jié)構(gòu),第二個(gè)參數(shù)為鏈表頭,為list_head結(jié)構(gòu),第三 個(gè)參數(shù)為list_head結(jié)構(gòu)在宿主結(jié)構(gòu)中的成員名。 這個(gè)函數(shù)的功能就是如果pos非空,那么pos的值就為其本身,如果pos為空,那么就從鏈表頭強(qiáng)制擴(kuò)展一 個(gè)虛pos指針,這個(gè)宏定義是為了在list_for_each_entry_continue()中使用做準(zhǔn)備的。 （10）list_for_each_entry_continue #define list_for_each_entry_continue(pos, head, member) ????????\ ????for (pos = list_entry(pos->member.next, typeof(*pos), member);????\ ???? &pos->member != (head);????\ ???? pos = list_entry(pos->member.next, typeof(*pos), member)) 這個(gè)函數(shù)與list_for_each_entry很相似，但是肯定是不同的，它是從pos所在的宿主結(jié)構(gòu)體的下一個(gè)開始遍歷鏈表，并不是從鏈表的頭部開始遍歷，從它的名字可以看出來。主要的區(qū)別就是我標(biāo)紅的位置。 （11）list_for_each_entry_continue_reverse #define list_for_each_entry_continue_reverse(pos, head, member)????????\ ????for (pos = list_entry(pos->member.prev, typeof(*pos), member);????\ ???? &pos->member != (head);????\ ???? pos = list_entry(pos->member.prev, typeof(*pos), member)) 與上一個(gè)函數(shù)類似，從pos位于的宿主結(jié)構(gòu)體的上一個(gè)開始反向變量鏈表。 （12）list_for_each_entry_from #define list_for_each_entry_from(pos, head, member) ????????????\ ????for (; &pos->member != (head);????\ ???? pos = list_entry(pos->member.next, typeof(*pos), member)) 從當(dāng)前pos所位于的宿主結(jié)構(gòu)體開始遍歷鏈表。 （13）后面的幾個(gè)函數(shù)帶safe的函數(shù)，他們與上面講的函數(shù)都很相似，只是保存了pos的下一個(gè)宿主結(jié)構(gòu)體，這些函數(shù)是專門為刪除結(jié)點(diǎn)是準(zhǔn)備的。就不分析他們了。 至此，對于普通鏈表的操作我們就分析完了，這個(gè)list.h中后面的代碼主要是為了哈西表設(shè)計(jì)的，就暫時(shí)先不分析，等到學(xué)了哈西表再分析他們^o^~
linux內(nèi)核中鏈表代碼分析---list.h頭文件分析（二） 16年2月28日16:59:55 分析完container_of()宏以后，繼續(xù)分析list.h文件： （1）list_entry 它就是一個(gè)container_of宏，都是得到ptr所指地址的這個(gè)結(jié)構(gòu)體的首地址 #define list_entry(ptr, type, member) \ ????container_of(ptr, type, member) （2） list_first_entry #define list_first_entry(ptr, type, member) \ ????list_entry((ptr)->next, type, member) 這里的ptr是一個(gè)鏈表的頭節(jié)點(diǎn),這個(gè)宏就是取得這個(gè)鏈表第一元素的所指結(jié)構(gòu)體的首地址。 （3） list_for_each #define list_for_each(pos, head) \ ????for (pos = (head)->next; pos != (head); pos = pos->next) 它實(shí)際上就是一個(gè)for循環(huán)，從頭到尾遍歷鏈表，但是看代碼發(fā)現(xiàn)，遍歷鏈表需要一個(gè)head參數(shù)即可，這個(gè)pos參數(shù)好像沒什么用啊。。。 然后就在內(nèi)核中g(shù)rep了一番，稍微總結(jié)出來一點(diǎn)： 這是一個(gè)for循環(huán)，我們通過這個(gè)for循環(huán)總得做點(diǎn)什么事情吧，以下面這個(gè)為例， 源文件在/driver/input/serio/hil_mlc.c中： static LIST_HEAD(hil_mlcs); static void hil_mlcs_process(unsigned long unused) { ????struct list_head *tmp; ????read_lock(&hil_mlcs_lock); ????list_for_each(tmp, &hil_mlcs) { ????????struct hil_mlc *mlc = list_entry(tmp, hil_mlc, list); ????????.... } 可以看到，它通過這個(gè)list_for_each函數(shù)，將hil_mlcs鏈表中的每一個(gè)成員地址一一賦給了tmp變量，這樣，在后面的語句中，就可以通過list_entry這個(gè)宏根據(jù)tmp變量和list鏈表頭來找到包含他們的整個(gè)結(jié)構(gòu)體hil_mlc的首地址，然后就可以對這個(gè)結(jié)構(gòu)體里面其他的成員變量進(jìn)行操作了～～～ 這一塊涉及到linux中，比如對于每一個(gè)子設(shè)備，都建立一個(gè)結(jié)構(gòu)體，然后將這些子設(shè)備通過一個(gè)鏈表鏈接起來，操作的時(shí)候需要遍歷鏈表中的每一項(xiàng)進(jìn)行操作，所以就是這個(gè)函數(shù)存在的意義。 后面那個(gè) __list_for_each和list_for_each相同，以前這兩個(gè)函數(shù)是不同的，它有一個(gè)prefetch預(yù)取的操作，我們不再考慮。 （4）list_for_each_prev #define list_for_each_prev(pos, head) \ ????for (pos = (head)->prev; pos != (head); pos = pos->prev) 與list_for_each相似，只是它是從尾到頭遍歷鏈表，將鏈表中的每一項(xiàng)都取出來操作。 （5）list_for_each_safe #define list_for_each_safe(pos, n, head) \ ????for (pos = (head)->next, n = pos->next; pos != (head); \ ????????pos = n, n = pos->next) 這個(gè)實(shí)際上就是一個(gè)for循環(huán),從頭到尾遍歷鏈表。這里使用了n來記錄pos的下一個(gè),這樣處理完一 個(gè)流程之后再賦給pos,避免了刪除pos結(jié)點(diǎn)造成的問題。這個(gè)函數(shù)是 專門為刪除結(jié)點(diǎn)是準(zhǔn)備的。 注:list_for_each(pos, head)和list_for_each_safe(pos, n, head)都是從頭至尾遍歷鏈表的,但是對于前者 來說當(dāng)操作中沒有刪除結(jié)點(diǎn)的時(shí)候使用,但是如果操作中有刪除結(jié)點(diǎn)的操作的時(shí)候就使用后者,對于后面帶safe的一般都是這個(gè)目的。 （6） list_for_each_prev_safe #define list_for_each_prev_safe(pos, n, head) \ ????for (pos = (head)->prev, n = pos->prev; \ ???? pos != (head); \ ???? pos = n, n = pos->prev) 同理，這個(gè)函數(shù)與 list_for_each_prev相似。 /* 注意上面的幾個(gè)函數(shù)，他們的行參里面有pos與下面函數(shù)行參里面的pos不同，上面函數(shù)的操作都是pos = (head)->next等等的操作，所以pos是list_head類型的，下面函數(shù)的操作是pos = list_entry()等等的操作，所以他們是list_head結(jié)構(gòu)體所嵌入的結(jié)構(gòu)體的指針形式的，我們稱之為宿主結(jié)構(gòu)體。 */ （7） list_for_each_entry #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)) 第一個(gè)參數(shù)為傳入的遍歷指針,指向宿主數(shù)據(jù)結(jié)構(gòu),第二個(gè)參數(shù)為鏈表頭,為list_head結(jié)構(gòu),第三 個(gè)參數(shù)為list_head結(jié)構(gòu)在宿主結(jié)構(gòu)中的成員名。 這個(gè)函數(shù)是根據(jù)member成員遍歷head鏈表（member成員一般都嵌入在宿主結(jié)構(gòu)體中）,并且將每個(gè)結(jié)構(gòu)體的首地址賦值給pos,這樣的話,我們就 可以在循環(huán)體里面通過pos來訪問該宿主結(jié)構(gòu)體變量的其他成員了。 下面用最近分析的V4L2里面的一段代碼來舉例說明，代碼位于v4l2-device.c中： int v4l2_device_register_subdev_nodes(struct v4l2_device *v4l2_dev) { ????struct video_device *vdev; ????struct v4l2_subdev *sd; ????list_for_each_entry(sd, &v4l2_dev->subdevs, list) { ????????if (!(sd->flags & V4L2_SUBDEV_FL_HAS_DEVNODE)) ????????????continue; ????。。。。 } 可以分析出來， v4l2_device結(jié)構(gòu)體里面含有這個(gè) subdevs鏈表頭，sd是指向v4l2_subdev結(jié)構(gòu)體的指針，list是一個(gè)list_head結(jié)構(gòu)，在之前的代碼中，肯定有操作已經(jīng)將各個(gè)子設(shè)備結(jié)構(gòu)體v4l2_subdev全部鏈接進(jìn) v4l2_device結(jié)構(gòu)體里面的 subdevs鏈表里面，這時(shí)候需要做的就是從這個(gè)v4l2_device結(jié)構(gòu)體里面的 subdevs鏈表里一一取出各個(gè)子設(shè)備結(jié)構(gòu)體v4l2_subdev，然后操作它的各個(gè)成員變量。上述代碼就是完成這個(gè)工作。 （8） list_for_each_entry_reverse #define list_for_each_entry_reverse(pos, head, member)????????????\ ????for (pos = list_entry((head)->prev, typeof(*pos), member);????\ ???? &pos->member != (head); ????\ ???? pos = list_entry(pos->member.prev, typeof(*pos), member)) 與上面那個(gè)函數(shù)類似，反向遍歷鏈表。 （9） list_prepare_entry #define list_prepare_entry(pos, head, member) \ ????((pos) ? : list_entry(head, typeof(*pos), member)) 第一個(gè)參數(shù)為傳入的遍歷指針,指向宿主數(shù)據(jù)結(jié)構(gòu),第二個(gè)參數(shù)為鏈表頭,為list_head結(jié)構(gòu),第三 個(gè)參數(shù)為list_head結(jié)構(gòu)在宿主結(jié)構(gòu)中的成員名。 這個(gè)函數(shù)的功能就是如果pos非空,那么pos的值就為其本身,如果pos為空,那么就從鏈表頭強(qiáng)制擴(kuò)展一 個(gè)虛pos指針,這個(gè)宏定義是為了在list_for_each_entry_continue()中使用做準(zhǔn)備的。 （10）list_for_each_entry_continue #define list_for_each_entry_continue(pos, head, member) ????????\ ????for (pos = list_entry(pos->member.next, typeof(*pos), member);????\ ???? &pos->member != (head);????\ ???? pos = list_entry(pos->member.next, typeof(*pos), member)) 這個(gè)函數(shù)與list_for_each_entry很相似，但是肯定是不同的，它是從pos所在的宿主結(jié)構(gòu)體的下一個(gè)開始遍歷鏈表，并不是從鏈表的頭部開始遍歷，從它的名字可以看出來。主要的區(qū)別就是我標(biāo)紅的位置。 （11）list_for_each_entry_continue_reverse #define list_for_each_entry_continue_reverse(pos, head, member)????????\ ????for (pos = list_entry(pos->member.prev, typeof(*pos), member);????\ ???? &pos->member != (head);????\ ???? pos = list_entry(pos->member.prev, typeof(*pos), member)) 與上一個(gè)函數(shù)類似，從pos位于的宿主結(jié)構(gòu)體的上一個(gè)開始反向變量鏈表。 （12）list_for_each_entry_from #define list_for_each_entry_from(pos, head, member) ????????????\ ????for (; &pos->member != (head);????\ ???? pos = list_entry(pos->member.next, typeof(*pos), member)) 從當(dāng)前pos所位于的宿主結(jié)構(gòu)體開始遍歷鏈表。 （13）后面的幾個(gè)函數(shù)帶safe的函數(shù)，他們與上面講的函數(shù)都很相似，只是保存了pos的下一個(gè)宿主結(jié)構(gòu)體，這些函數(shù)是專門為刪除結(jié)點(diǎn)是準(zhǔn)備的。就不分析他們了。 至此，對于普通鏈表的操作我們就分析完了，這個(gè)list.h中后面的代碼主要是為了哈西表設(shè)計(jì)的，就暫時(shí)先不分析，等到學(xué)了哈西表再分析他們^o^~
總結(jié)
以上是生活随笔 為你收集整理的linux内核中链表代码分析---list.h头文件分析（二）【转】 的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔 網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔 推薦給好友。
