Linux 内核通用链表学习小结

山谷间花丛 發表於 2023-8-21 00:00:00

<p>
<strong>描述</strong></p>
<p>
在linux内核中封装了一个通用的双向链表库，这个通用的链表库有很好的扩展性和封装性，它给我们提供了一个固定的指针域结构体，我们在使用的时候，只需要在我们定义的数据域结构体中包含这个指针域结构体就可以了，具体的实现、链接并不需要我们关心，只要调用提供给我们的相关接口就可以完成了。</p>
<p>
传统的链表结构</p>
<div class="jb51code">
<div>
<div class="syntaxhighlightercpp" id="highlighter_195706">
<div class="toolbar">
<span>?</span>
</div>
<table border="0" cellpadding="0" cellspacing="0"><tbody><tr>
<td class="gutter">
<div class="line number1 index0 alt2">
1</div>
<div class="line number2 index1 alt1">
2</div>
<div class="line number3 index2 alt2">
3</div>
<div class="line number4 index3 alt1">
4</div>
<div class="line number5 index4 alt2">
5</div>
<div class="line number6 index5 alt1">
6</div>
</td>
<td class="code">
<div class="container">
<div class="line number1 index0 alt2">
<code class="cpp keyword bold">struct</code> <code class="cpp plain">node{</code>
</div>
<div class="line number2 index1 alt1">
<code class="cpp spaces">  </code><code class="cpp color1 bold">int</code> <code class="cpp plain">key;</code>
</div>
<div class="line number3 index2 alt2">
<code class="cpp spaces">  </code><code class="cpp color1 bold">int</code> <code class="cpp plain">val;</code>
</div>
<div class="line number4 index3 alt1">
<code class="cpp spaces">  </code><code class="cpp plain">node* prev;</code>
</div>
<div class="line number5 index4 alt2">
<code class="cpp spaces">  </code><code class="cpp plain">node* next;</code>
</div>
<div class="line number6 index5 alt1">
<code class="cpp spaces"> </code><code class="cpp plain">}</code>
</div>
</div>
</td>
</tr></tbody></table>
</div>
</div>
</div>
<p>
<strong>linux 内核通用链表库结构</strong></p>
<p>
提供给我们的指针域结构体：</p>
<div class="jb51code">
<div>
<div class="syntaxhighlightercpp" id="highlighter_988010">
<div class="toolbar">
<span>?</span>
</div>
<table border="0" cellpadding="0" cellspacing="0"><tbody><tr>
<td class="gutter">
<div class="line number1 index0 alt2">
1</div>
<div class="line number2 index1 alt1">
2</div>
<div class="line number3 index2 alt2">
3</div>
</td>
<td class="code">
<div class="container">
<div class="line number1 index0 alt2">
<code class="cpp keyword bold">struct</code> <code class="cpp plain">list_head {</code>
</div>
<div class="line number2 index1 alt1">
<code class="cpp spaces">  </code><code class="cpp keyword bold">struct</code> <code class="cpp plain">list_head *next, *prev;</code>
</div>
<div class="line number3 index2 alt2">
<code class="cpp plain">};</code>
</div>
</div>
</td>
</tr></tbody></table>
</div>
</div>
</div>
<p>
我们只需要包含它就可以：</p>
<div class="jb51code">
<div>
<div class="syntaxhighlightercpp" id="highlighter_172458">
<div class="toolbar">
<span>?</span>
</div>
<table border="0" cellpadding="0" cellspacing="0"><tbody><tr>
<td class="gutter">
<div class="line number1 index0 alt2">
1</div>
<div class="line number2 index1 alt1">
2</div>
<div class="line number3 index2 alt2">
3</div>
<div class="line number4 index3 alt1">
4</div>
<div class="line number5 index4 alt2">
5</div>
</td>
<td class="code">
<div class="container">
<div class="line number1 index0 alt2">
<code class="cpp keyword bold">struct</code> <code class="cpp plain">node{</code>
</div>
<div class="line number2 index1 alt1">
<code class="cpp spaces">  </code><code class="cpp color1 bold">int</code> <code class="cpp plain">val;</code>
</div>
<div class="line number3 index2 alt2">
<code class="cpp spaces">  </code><code class="cpp color1 bold">int</code> <code class="cpp plain">key;</code>
</div>
<div class="line number4 index3 alt1">
<code class="cpp spaces">  </code><code class="cpp keyword bold">struct</code> <code class="cpp plain">list_head* head;</code>
</div>
<div class="line number5 index4 alt2">
<code class="cpp plain">}</code>
</div>
</div>
</td>
</tr></tbody></table>
</div>
</div>
</div>
<p>
可以看到通过这个 list_head 结构就把我们的数据层跟驱动层分开了，而内核提供的各种操作方法接口也只关心 list_head 这个结构，也就是具体链接的时候也只链接这个list_head 结构，并不关心你数据层定义了什么类型.</p>
<p>
一些接口宏定义</p>
<div class="jb51code">
<div>
<div class="syntaxhighlightercpp" id="highlighter_910480">
<div class="toolbar">
<span>?</span>
</div>
<table border="0" cellpadding="0" cellspacing="0"><tbody><tr>
<td class="gutter">
<div class="line number1 index0 alt2">
1</div>
<div class="line number2 index1 alt1">
2</div>
<div class="line number3 index2 alt2">
3</div>
<div class="line number4 index3 alt1">
4</div>
<div class="line number5 index4 alt2">
5</div>
<div class="line number6 index5 alt1">
6</div>
<div class="line number7 index6 alt2">
7</div>
<div class="line number8 index7 alt1">
8</div>
<div class="line number9 index8 alt2">
9</div>
<div class="line number10 index9 alt1">
10</div>
<div class="line number11 index10 alt2">
11</div>
<div class="line number12 index11 alt1">
12</div>
<div class="line number13 index12 alt2">
13</div>
<div class="line number14 index13 alt1">
14</div>
<div class="line number15 index14 alt2">
15</div>
<div class="line number16 index15 alt1">
16</div>
<div class="line number17 index16 alt2">
17</div>
<div class="line number18 index17 alt1">
18</div>
<div class="line number19 index18 alt2">
19</div>
<div class="line number20 index19 alt1">
20</div>
<div class="line number21 index20 alt2">
21</div>
<div class="line number22 index21 alt1">
22</div>
</td>
<td class="code">
<div class="container">
<div class="line number1 index0 alt2">
<code class="cpp comments">//初始化头指针</code>
</div>
<div class="line number2 index1 alt1">
<code class="cpp preprocessor">#define list_head_init(name) { &(name), &(name) }</code>
</div>
<div class="line number3 index2 alt2">
</div>
<div class="line number4 index3 alt1">
<code class="cpp preprocessor">#define list_head(name) \</code>
</div>
<div class="line number5 index4 alt2">
<code class="cpp spaces">  </code><code class="cpp keyword bold">struct</code> <code class="cpp plain">list_head name = list_head_init(name)</code>
</div>
<div class="line number6 index5 alt1">
</div>
<div class="line number7 index6 alt2">
<code class="cpp comments">//遍历链表</code>
</div>
<div class="line number8 index7 alt1">
<code class="cpp preprocessor">#define __list_for_each(pos, head) \</code>
</div>
<div class="line number9 index8 alt2">
<code class="cpp spaces">  </code><code class="cpp keyword bold">for</code> <code class="cpp plain">(pos = (head)->next; pos != (head); pos = pos->next)</code>
</div>
<div class="line number10 index9 alt1">
</div>
<div class="line number11 index10 alt2">
<code class="cpp comments">//获取节点首地址(不是list_head地址，是数据层节点首地址)</code>
</div>
<div class="line number12 index11 alt1">
<code class="cpp preprocessor">#define list_entry(ptr, type, member) \</code>
</div>
<div class="line number13 index12 alt2">
<code class="cpp spaces">  </code><code class="cpp plain">container_of(ptr, type, member)</code>
</div>
<div class="line number14 index13 alt1">
</div>
<div class="line number15 index14 alt2">
<code class="cpp comments">//container_of在linux内核中是一个常用的宏，用于从包含在某个</code>
</div>
<div class="line number16 index15 alt1">
<code class="cpp comments">//结构中的指针获得结构本身的指针，通俗地讲就是通过结构体变</code>
</div>
<div class="line number17 index16 alt2">
<code class="cpp comments">//量中某个成员的首地址进而获得整个结构体变量的首地址</code>
</div>
<div class="line number18 index17 alt1">
<code class="cpp preprocessor">#define container_of(ptr, type, member) ({     \</code>
</div>
<div class="line number19 index18 alt2">
<code class="cpp spaces">    </code><code class="cpp keyword bold">const</code> <code class="cpp plain">typeof( ((type *)0)->member ) *__mptr = (ptr); \</code>
</div>
<div class="line number20 index19 alt1">
<code class="cpp spaces">    </code><code class="cpp plain">(type *)( (</code><code class="cpp color1 bold">char</code> <code class="cpp plain">*)__mptr - offsetof(type,member) );})</code>
</div>
<div class="line number21 index20 alt2">
</div>
<div class="line number22 index21 alt1">
<code class="cpp preprocessor">#define offsetof(s,m) (size_t)&(((s *)0)->m)</code>
</div>
</div>
</td>
</tr></tbody></table>
</div>
</div>
</div>
<p>
使用方式</p>
<div class="jb51code">
<div>
<div class="syntaxhighlightercpp" id="highlighter_927979">
<div class="toolbar">
<span>?</span>
</div>
<table border="0" cellpadding="0" cellspacing="0"><tbody><tr>
<td class="gutter">
<div class="line number1 index0 alt2">
1</div>
<div class="line number2 index1 alt1">
2</div>
<div class="line number3 index2 alt2">
3</div>
<div class="line number4 index3 alt1">
4</div>
<div class="line number5 index4 alt2">
5</div>
<div class="line number6 index5 alt1">
6</div>
<div class="line number7 index6 alt2">
7</div>
<div class="line number8 index7 alt1">
8</div>
<div class="line number9 index8 alt2">
9</div>
<div class="line number10 index9 alt1">
10</div>
<div class="line number11 index10 alt2">
11</div>
<div class="line number12 index11 alt1">
12</div>
<div class="line number13 index12 alt2">
13</div>
<div class="line number14 index13 alt1">
14</div>
<div class="line number15 index14 alt2">
15</div>
<div class="line number16 index15 alt1">
16</div>
<div class="line number17 index16 alt2">
17</div>
<div class="line number18 index17 alt1">
18</div>
<div class="line number19 index18 alt2">
19</div>
<div class="line number20 index19 alt1">
20</div>
<div class="line number21 index20 alt2">
21</div>
<div class="line number22 index21 alt1">
22</div>
<div class="line number23 index22 alt2">
23</div>
<div class="line number24 index23 alt1">
24</div>
<div class="line number25 index24 alt2">
25</div>
<div class="line number26 index25 alt1">
26</div>
<div class="line number27 index26 alt2">
27</div>
<div class="line number28 index27 alt1">
28</div>
<div class="line number29 index28 alt2">
29</div>
</td>
<td class="code">
<div class="container">
<div class="line number1 index0 alt2">
<code class="cpp keyword bold">typedef</code> <code class="cpp keyword bold">struct</code> <code class="cpp plain">node{</code>
</div>
<div class="line number2 index1 alt1">
<code class="cpp spaces">  </code><code class="cpp color1 bold">int</code> <code class="cpp plain">val;</code>
</div>
<div class="line number3 index2 alt2">
<code class="cpp spaces">  </code><code class="cpp color1 bold">int</code> <code class="cpp plain">key;</code>
</div>
<div class="line number4 index3 alt1">
<code class="cpp spaces">  </code><code class="cpp keyword bold">struct</code> <code class="cpp plain">list_head* list;</code>
</div>
<div class="line number5 index4 alt2">
<code class="cpp plain">}node;</code>
</div>
<div class="line number6 index5 alt1">
</div>
<div class="line number7 index6 alt2">
<code class="cpp comments">//初始化头指针</code>
</div>
<div class="line number8 index7 alt1">
<code class="cpp plain">list_head(head);</code>
</div>
<div class="line number9 index8 alt2">
</div>
<div class="line number10 index9 alt1">
<code class="cpp comments">//创建节点</code>
</div>
<div class="line number11 index10 alt2">
<code class="cpp plain">node* a = </code><code class="cpp functions bold">malloc</code><code class="cpp plain">(</code><code class="cpp keyword bold">sizeof</code><code class="cpp plain">(node));</code>
</div>
<div class="line number12 index11 alt1">
<code class="cpp plain">node* b = </code><code class="cpp functions bold">malloc</code><code class="cpp plain">(</code><code class="cpp keyword bold">sizeof</code><code class="cpp plain">(node));</code>
</div>
<div class="line number13 index12 alt2">
</div>
<div class="line number14 index13 alt1">
<code class="cpp comments">//插入链表方式一</code>
</div>
<div class="line number15 index14 alt2">
<code class="cpp plain">list_add(&a->list,&head);</code>
</div>
<div class="line number16 index15 alt1">
<code class="cpp plain">list_add(&b->list,&head);</code>
</div>
<div class="line number17 index16 alt2">
</div>
<div class="line number18 index17 alt1">
<code class="cpp comments">//插入链表方式二</code>
</div>
<div class="line number19 index18 alt2">
<code class="cpp plain">list_add_tail(&a->list,&head);</code>
</div>
<div class="line number20 index19 alt1">
<code class="cpp plain">list_add_tail(&b->list,&head);</code>
</div>
<div class="line number21 index20 alt2">
</div>
<div class="line number22 index21 alt1">
<code class="cpp comments">//遍历链表 </code>
</div>
<div class="line number23 index22 alt2">
<code class="cpp keyword bold">struct</code> <code class="cpp plain">list_head* p;</code>
</div>
<div class="line number24 index23 alt1">
<code class="cpp keyword bold">struct</code> <code class="cpp plain">node* n;</code>
</div>
<div class="line number25 index24 alt2">
<code class="cpp plain">__list_for_each(p,head){</code>
</div>
<div class="line number26 index25 alt1">
<code class="cpp spaces">  </code><code class="cpp comments">//返回list_head地址，然后再通过list_head地址反推</code>
</div>
<div class="line number27 index26 alt2">
<code class="cpp spaces">  </code><code class="cpp comments">//节点结构体首地址.</code>
</div>
<div class="line number28 index27 alt1">
<code class="cpp spaces">  </code><code class="cpp plain">n = list_entry(pos,</code><code class="cpp keyword bold">struct</code> <code class="cpp plain">node,list);</code>
</div>
<div class="line number29 index28 alt2">
<code class="cpp plain">}</code>
</div>
</div>
</td>
</tr></tbody></table>
</div>
</div>
</div>
<p>
list_add 接口，先入后出原则，有点类似于栈</p>
<p>
<img title="Linux 内核通用链表学习小结" alt="Linux 内核通用链表学习小结" src="https://zhuji.jb51.net/uploads/img/202305/1497c4445bf55c0e9692245af5d9ba03.jpg"></p>
<p>
list_add-先入后出模式</p>
<p>
list_add_tail 接口，先入先出原则，有点类似于fifo</p>
<p>
<img title="Linux 内核通用链表学习小结" alt="Linux 内核通用链表学习小结" src="https://zhuji.jb51.net/uploads/img/202305/c9a56d250c7e92ce1889b1cc60000fa1.jpg"></p>
<p>
list_add-先入先出模式</p>
<p>
我们的链表节点，实际在内存中的展示形态</p>
<p>
<img title="Linux 内核通用链表学习小结" alt="Linux 内核通用链表学习小结" src="https://zhuji.jb51.net/uploads/img/202305/b4d8011cafb2c2a51801af20f3c9b68f.jpg"></p>
<p>
节点描述</p>
<p>
可以看到最终的形态是，通过指向每个结构体里面的 list_head 类型指针，然后把它们串联起来的</p>
<p>
list_entry 接口，通过结构体变量某个成员的地址，反推结构体首地址，就像 __list_for_each 接口只返回 list_head 地址，所以我们要通过这个成员地址在去获取它本身的结构体首地址，底层实现方法 container_of 宏</p>
<p>
<img title="Linux 内核通用链表学习小结" alt="Linux 内核通用链表学习小结" src="https://zhuji.jb51.net/uploads/img/202305/bc2ac4ee0ab69201d9d7ceb62b8de7a7.jpg"></p>
<p>
反推结构体首地址</p>
<p>
举个例子</p>
<p>
这个例子包括简单的增、删、遍历</p>
<div class="jb51code">
<div>
<div class="syntaxhighlightercpp" id="highlighter_535224">
<div class="toolbar">
<span>?</span>
</div>
<table border="0" cellpadding="0" cellspacing="0"><tbody><tr>
<td class="gutter">
<div class="line number1 index0 alt2">
1</div>
<div class="line number2 index1 alt1">
2</div>
<div class="line number3 index2 alt2">
3</div>
<div class="line number4 index3 alt1">
4</div>
<div class="line number5 index4 alt2">
5</div>
<div class="line number6 index5 alt1">
6</div>
<div class="line number7 index6 alt2">
7</div>
<div class="line number8 index7 alt1">
8</div>
<div class="line number9 index8 alt2">
9</div>
<div class="line number10 index9 alt1">
10</div>
<div class="line number11 index10 alt2">
11</div>
<div class="line number12 index11 alt1">
12</div>
<div class="line number13 index12 alt2">
13</div>
<div class="line number14 index13 alt1">
14</div>
<div class="line number15 index14 alt2">
15</div>
<div class="line number16 index15 alt1">
16</div>
<div class="line number17 index16 alt2">
17</div>
<div class="line number18 index17 alt1">
18</div>
<div class="line number19 index18 alt2">
19</div>
<div class="line number20 index19 alt1">
20</div>
<div class="line number21 index20 alt2">
21</div>
<div class="line number22 index21 alt1">
22</div>
<div class="line number23 index22 alt2">
23</div>
<div class="line number24 index23 alt1">
24</div>
<div class="line number25 index24 alt2">
25</div>
<div class="line number26 index25 alt1">
26</div>
<div class="line number27 index26 alt2">
27</div>
<div class="line number28 index27 alt1">
28</div>
<div class="line number29 index28 alt2">
29</div>
<div class="line number30 index29 alt1">
30</div>
<div class="line number31 index30 alt2">
31</div>
<div class="line number32 index31 alt1">
32</div>
<div class="line number33 index32 alt2">
33</div>
<div class="line number34 index33 alt1">
34</div>
<div class="line number35 index34 alt2">
35</div>
<div class="line number36 index35 alt1">
36</div>
<div class="line number37 index36 alt2">
37</div>
<div class="line number38 index37 alt1">
38</div>
<div class="line number39 index38 alt2">
39</div>
<div class="line number40 index39 alt1">
40</div>
<div class="line number41 index40 alt2">
41</div>
<div class="line number42 index41 alt1">
42</div>
<div class="line number43 index42 alt2">
43</div>
<div class="line number44 index43 alt1">
44</div>
<div class="line number45 index44 alt2">
45</div>
<div class="line number46 index45 alt1">
46</div>
<div class="line number47 index46 alt2">
47</div>
<div class="line number48 index47 alt1">
48</div>
<div class="line number49 index48 alt2">
49</div>
<div class="line number50 index49 alt1">
50</div>
<div class="line number51 index50 alt2">
51</div>
<div class="line number52 index51 alt1">
52</div>
<div class="line number53 index52 alt2">
53</div>
<div class="line number54 index53 alt1">
54</div>
<div class="line number55 index54 alt2">
55</div>
<div class="line number56 index55 alt1">
56</div>
<div class="line number57 index56 alt2">
57</div>
<div class="line number58 index57 alt1">
58</div>
<div class="line number59 index58 alt2">
59</div>
<div class="line number60 index59 alt1">
60</div>
<div class="line number61 index60 alt2">
61</div>
<div class="line number62 index61 alt1">
62</div>
<div class="line number63 index62 alt2">
63</div>
<div class="line number64 index63 alt1">
64</div>
<div class="line number65 index64 alt2">
65</div>
<div class="line number66 index65 alt1">
66</div>
<div class="line number67 index66 alt2">
67</div>
<div class="line number68 index67 alt1">
68</div>
<div class="line number69 index68 alt2">
69</div>
<div class="line number70 index69 alt1">
70</div>
<div class="line number71 index70 alt2">
71</div>
</td>
<td class="code">
<div class="container">
<div class="line number1 index0 alt2">
<code class="cpp preprocessor">#include <linux/kernel.h> </code>
</div>
<div class="line number2 index1 alt1">
<code class="cpp preprocessor">#include <linux/module.h> </code>
</div>
<div class="line number3 index2 alt2">
<code class="cpp preprocessor">#include <linux/init.h> </code>
</div>
<div class="line number4 index3 alt1">
<code class="cpp preprocessor">#include <linux/slab.h> </code>
</div>
<div class="line number5 index4 alt2">
<code class="cpp preprocessor">#include <linux/list.h> </code>
</div>
<div class="line number6 index5 alt1">
<code class="cpp spaces"> </code>
</div>
<div class="line number7 index6 alt2">
<code class="cpp plain">module_license(</code><code class="cpp string">"gpl"</code><code class="cpp plain">); </code>
</div>
<div class="line number8 index7 alt1">
<code class="cpp plain">module_author(</code><code class="cpp string">"david xie"</code><code class="cpp plain">); </code>
</div>
<div class="line number9 index8 alt2">
<code class="cpp plain">module_description(</code><code class="cpp string">"list module"</code><code class="cpp plain">); </code>
</div>
<div class="line number10 index9 alt1">
<code class="cpp plain">module_alias(</code><code class="cpp string">"list module"</code><code class="cpp plain">); </code>
</div>
<div class="line number11 index10 alt2">
<code class="cpp spaces"> </code>
</div>
<div class="line number12 index11 alt1">
<code class="cpp keyword bold">struct</code> <code class="cpp plain">student </code><code class="cpp comments">//代表一个实际节点的结构 </code>
</div>
<div class="line number13 index12 alt2">
<code class="cpp plain">{ </code>
</div>
<div class="line number14 index13 alt1">
<code class="cpp spaces">  </code><code class="cpp color1 bold">char</code> <code class="cpp plain">name; </code>
</div>
<div class="line number15 index14 alt2">
<code class="cpp spaces">  </code><code class="cpp color1 bold">int</code> <code class="cpp plain">num; </code>
</div>
<div class="line number16 index15 alt1">
<code class="cpp spaces">  </code><code class="cpp keyword bold">struct</code> <code class="cpp plain">list_head list; </code><code class="cpp comments">//内核链表里的节点结构 </code>
</div>
<div class="line number17 index16 alt2">
<code class="cpp plain">}; </code>
</div>
<div class="line number18 index17 alt1">
<code class="cpp spaces"> </code>
</div>
<div class="line number19 index18 alt2">
<code class="cpp keyword bold">struct</code> <code class="cpp plain">student *pstudent;    </code>
</div>
<div class="line number20 index19 alt1">
<code class="cpp keyword bold">struct</code> <code class="cpp plain">student *tmp_student; </code>
</div>
<div class="line number21 index20 alt2">
<code class="cpp keyword bold">struct</code> <code class="cpp plain">list_head student_list; </code>
</div>
<div class="line number22 index21 alt1">
<code class="cpp keyword bold">struct</code> <code class="cpp plain">list_head *pos; </code>
</div>
<div class="line number23 index22 alt2">
<code class="cpp spaces"> </code>
</div>
<div class="line number24 index23 alt1">
<code class="cpp color1 bold">int</code> <code class="cpp plain">mylist_init(</code><code class="cpp keyword bold">void</code><code class="cpp plain">) </code>
</div>
<div class="line number25 index24 alt2">
<code class="cpp plain">{ </code>
</div>
<div class="line number26 index25 alt1">
<code class="cpp spaces">  </code><code class="cpp color1 bold">int</code> <code class="cpp plain">i = 0; </code>
</div>
<div class="line number27 index26 alt2">
<code class="cpp spaces">   </code>
</div>
<div class="line number28 index27 alt1">
<code class="cpp spaces">  </code><code class="cpp comments">//初始化一个链表，其实就是把student_list的prev和next指向自身 </code>
</div>
<div class="line number29 index28 alt2">
<code class="cpp spaces">  </code><code class="cpp plain">init_list_head(&student_list); </code>
</div>
<div class="line number30 index29 alt1">
<code class="cpp spaces">   </code>
</div>
<div class="line number31 index30 alt2">
<code class="cpp spaces">  </code><code class="cpp plain">pstudent = kmalloc(</code><code class="cpp keyword bold">sizeof</code><code class="cpp plain">(</code><code class="cpp keyword bold">struct</code> <code class="cpp plain">student)*5,gfp_kernel);</code><code class="cpp comments">//向内核申请5个student结构空间 </code>
</div>
<div class="line number32 index31 alt1">
<code class="cpp spaces">  </code><code class="cpp functions bold">memset</code><code class="cpp plain">(pstudent,0,</code><code class="cpp keyword bold">sizeof</code><code class="cpp plain">(</code><code class="cpp keyword bold">struct</code> <code class="cpp plain">student)*5); </code><code class="cpp comments">//清空，这两个函数可以由kzalloc单独做到 </code>
</div>
<div class="line number33 index32 alt2">
<code class="cpp spaces">   </code>
</div>
<div class="line number34 index33 alt1">
<code class="cpp spaces">  </code><code class="cpp keyword bold">for</code><code class="cpp plain">(i=0;i<5;i++) </code>
</div>
<div class="line number35 index34 alt2">
<code class="cpp spaces">  </code><code class="cpp plain">{ </code><code class="cpp comments">//为结构体属性赋值 </code>
</div>
<div class="line number36 index35 alt1">
<code class="cpp spaces">    </code><code class="cpp functions bold">sprintf</code><code class="cpp plain">(pstudent.name,</code><code class="cpp string">"student%d"</code><code class="cpp plain">,i+1); </code>
</div>
<div class="line number37 index36 alt2">
<code class="cpp spaces">    </code><code class="cpp plain">pstudent.num = i+1; </code>
</div>
<div class="line number38 index37 alt1">
<code class="cpp spaces">    </code><code class="cpp comments">//加入链表节点，list_add的话是在表头插入，list_add_tail是在表尾插入 </code>
</div>
<div class="line number39 index38 alt2">
<code class="cpp spaces">    </code><code class="cpp plain">list_add( &(pstudent.list), &student_list);</code><code class="cpp comments">//参数1是要插入的节点地址，参数2是链表头地址 </code>
</div>
<div class="line number40 index39 alt1">
<code class="cpp spaces">  </code><code class="cpp plain">} </code>
</div>
<div class="line number41 index40 alt2">
<code class="cpp spaces">   </code>
</div>
<div class="line number42 index41 alt1">
<code class="cpp spaces">  </code><code class="cpp plain">list_for_each(pos,&student_list) </code><code class="cpp comments">//list_for_each用来遍历链表，这是个宏定义 </code>
</div>
<div class="line number43 index42 alt2">
<code class="cpp spaces">                   </code><code class="cpp comments">//pos在上面有定义 </code>
</div>
<div class="line number44 index43 alt1">
<code class="cpp spaces">  </code><code class="cpp plain">{ </code>
</div>
<div class="line number45 index44 alt2">
<code class="cpp spaces">    </code><code class="cpp comments">//list_entry用来提取出内核链表节点对应的实际结构节点，即根据struct list_head来提取struct student </code>
</div>
<div class="line number46 index45 alt1">
<code class="cpp spaces">    </code><code class="cpp comments">//第三个参数list就是student结构定义里的属性list </code>
</div>
<div class="line number47 index46 alt2">
<code class="cpp spaces">    </code><code class="cpp comments">//list_entry的原理有点复杂，也是linux内核的一个经典实现，这个在上面那篇链接文章里也有讲解 </code>
</div>
<div class="line number48 index47 alt1">
<code class="cpp spaces">    </code><code class="cpp plain">tmp_student = list_entry(pos,</code><code class="cpp keyword bold">struct</code> <code class="cpp plain">student,list); </code>
</div>
<div class="line number49 index48 alt2">
<code class="cpp spaces">    </code><code class="cpp comments">//打印一些信息，以备验证结果 </code>
</div>
<div class="line number50 index49 alt1">
<code class="cpp spaces">    </code><code class="cpp plain">printk(</code><code class="cpp string">"<0>student %d name: %s/n"</code><code class="cpp plain">,tmp_student->num,tmp_student->name); </code>
</div>
<div class="line number51 index50 alt2">
<code class="cpp spaces">  </code><code class="cpp plain">} </code>
</div>
<div class="line number52 index51 alt1">
<code class="cpp spaces">   </code>
</div>
<div class="line number53 index52 alt2">
<code class="cpp spaces">  </code><code class="cpp keyword bold">return</code> <code class="cpp plain">0; </code>
</div>
<div class="line number54 index53 alt1">
<code class="cpp plain">} </code>
</div>
<div class="line number55 index54 alt2">
<code class="cpp spaces"> </code>
</div>
<div class="line number56 index55 alt1">
<code class="cpp spaces"> </code>
</div>
<div class="line number57 index56 alt2">
<code class="cpp keyword bold">void</code> <code class="cpp plain">mylist_exit(</code><code class="cpp keyword bold">void</code><code class="cpp plain">) </code>
</div>
<div class="line number58 index57 alt1">
<code class="cpp plain">{   </code>
</div>
<div class="line number59 index58 alt2">
<code class="cpp spaces">  </code><code class="cpp color1 bold">int</code> <code class="cpp plain">i ; </code>
</div>
<div class="line number60 index59 alt1">
<code class="cpp spaces">  </code><code class="cpp comments">/* 实验：将for换成list_for_each来遍历删除结点，观察要发生的现象，并考虑解决办法 */</code>
</div>
<div class="line number61 index60 alt2">
<code class="cpp spaces">  </code><code class="cpp keyword bold">for</code><code class="cpp plain">(i=0;i<5;i++) </code>
</div>
<div class="line number62 index61 alt1">
<code class="cpp spaces">  </code><code class="cpp plain">{ </code>
</div>
<div class="line number63 index62 alt2">
<code class="cpp spaces">    </code><code class="cpp comments">//额，删除节点，只要传个内核链表节点就行了 </code>
</div>
<div class="line number64 index63 alt1">
<code class="cpp spaces">    </code><code class="cpp plain">list_del(&(pstudent.list));    </code>
</div>
<div class="line number65 index64 alt2">
<code class="cpp spaces">  </code><code class="cpp plain">} </code>
</div>
<div class="line number66 index65 alt1">
<code class="cpp spaces">  </code><code class="cpp comments">//释放空间 </code>
</div>
<div class="line number67 index66 alt2">
<code class="cpp spaces">  </code><code class="cpp plain">kfree(pstudent); </code>
</div>
<div class="line number68 index67 alt1">
<code class="cpp plain">} </code>
</div>
<div class="line number69 index68 alt2">
<code class="cpp spaces"> </code>
</div>
<div class="line number70 index69 alt1">
<code class="cpp plain">module_init(mylist_init); </code>
</div>
<div class="line number71 index70 alt2">
<code class="cpp plain">module_exit(mylist_exit); </code>
</div>
</div>
</td>
</tr></tbody></table>
</div>
</div>
</div>
<p>
<strong>结束</strong></p>
<p>
linux 内核提供的这个通用链表库里面还有很多其他的接口，这里没有详细的一一举例，有兴趣的可以自己去看看，在源码包 include/linux/list.h 文件里面，不过通过阅读一些源代码确实对我们也有很大的提高，可以看看高手是如何去设计并实现，还可以学到一些技巧以及对代码细节的掌握~~.</p>
<p>
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。</p>
<p>
原文链接：http://www.jianshu.com/p/1abba63d3f1c</p>

頁: [1]

琼殿技术论坛's Archiver

Linux 内核通用链表学习小结