本文共 24387 字，大约阅读时间需要 81 分钟。

（转自：）

摘要：将内核链表移植到应用程序中，实现创建，添加节点，遍历，删除的操作。

    

    首先复习一下内核链表中经常使用的几个函数，在/include/linux/list.h中。

    

    创建链表：

 

1. <span style="font-size:18px;">INIT_LIST_HEAD（）

2. staticinline void INIT_LIST_HEAD(struct list_head *list)

3. {

4. list->next = list;

5. list->prev = list;

6. }</span>

 

    插入节点：

 

1. <span style="font-size:18px;">list_add（）在链表头插入

2. list_add_tail()在链表尾插入

3. staticinline void list_add(struct list_head *new, struct list_head *head)

4. {

5. __list_add(new, head, head->next);

6. }

7. staticinline void list_add_tail(struct list_head *new, struct list_head *head)

8. {

9. __list_add(new, head->prev, head);

10. }</span>

 

    删除节点：

 

1. <span style="font-size:18px;">list_del()

2. staticinline void list_del(struct list_head *entry)

3. {

4. __list_del(entry->prev, entry->next);

5. entry->next = LIST_POISON1;

6. entry->prev = LIST_POISON2;

7. }</span>

 

    遍历链表：

 

1. <span style="font-size:18px;">list_for_each()

2. #definelist_for_each(pos, head) \

3. for(pos = (head)->next; prefetch(pos->next), pos != (head); \

4. pos = pos->next)</span>

 

    取出节点：

 

1. <span style="font-size:18px;">list_entry()

2. #definelist_entry(ptr, type, member) \

3. container_of(ptr,type, member)</span>

 

    移植过程中用到的其他函数：

    1.malloc

    函数原型：extern void *malloc(unsigned int num_bytes);

   功能：分配字节长度为num_bytes内存，如果成功则返回指向内存起始地址的指针，否则返回null。

    说明：这里声明为void *表示未确定类型的指针，这样使用的时候就可以强制转换为其他我们需要的任何类型的指针。

    2.memset

    函数原型：void *memset(void *s,int ch,seze_t n);

    功能：将s指向的某一块内存中的前n个字节的内容全部填充为ch。一般用来对新申请的内存做初始化工作，ch一般都是填充0。我们在使用较大的结构体和数组的时候，都会使用其对分配到的内存清零。

    3.sprintf

    函数原型：int sprintf(char *buffer,const char *format，[arugument]…);

    功能：把格式化的数据写入某个字符串中，返回值是字符串的长度。

 

    移植步骤：

    1.创建list.h

    因为我们要写成一个app，里面用到很多内核链表的函数，都在list.h里面声明的，一开始这里我就偷懒把内核里面的list.h拷贝一份，放到我当前的工作目录下，命名为list.h，后来编译的时候提示找不到list.h里面加进去的那三个头文件，于是我又把position.h,这三个头文件注释掉了，但是提示LIST_POSITION1和LIST_POSITION2没有定义还有别的错误，于是利用grep查找，到源码目录下，把这部分拷贝到我们的list.h前面部分里面来就可以了。完整的list.c附在最后。

 

1. <span style="font-size:18px;">#ifndef _LINUX_LIST_H

2. #define _LINUX_LIST_H

3.  
4.  

5. #include <linux/stddef.h>

6.  

7. #ifndef ARCH_HAS_PREFETCH

8. #define ARCH_HAS_PREFETCH

9. static inline void prefetch(const void *x){;}

10. #endif

11.  

12. #define LIST_POISON1 ((void *) 0x0)

13. #define LIST_POISON2 ((void *) 0x0)

14.  

15. #define container_of(ptr ,type,member)({ \

16. const typeof( ((type *)0)->member ) *__mptr = (ptr); \

17. (type *)( (char *)__mptr - offsetof(type,member) );})</span>

 

    2.创建listapp.c添加头文件

    这里我命名为listapp.c，因为我们要用到很多头文件，这里都添加进去，我添加的如下;

 

1. <span style="font-size:18px;">#include"list.h"//内核链表操作函数

2. #include<malloc.h>//使用malloc分配内存

3. #include<stdio.h>//sprintf和printf

4. #include<string.h>//memset</span><span style="font-size:14px; font-family: Arial, Helvetica, sans-serif; background-color: rgb(255, 255, 255);">                </span>

   

     3.创建球员信息结构体

 

1. <span style="font-size:18px;"> structmember

2. {

3. charname[10];

4. intnum;

5. intscore;

6. intassists;

7. structlist_head list;

8. };</span>

    4.main函数

    主要思想是创建链表，分配内存，插入节点，遍历输出，删除节点。

    编译成功后运行出现如下信息;

   

    可以看到我们的链表操作是成功了，输出信息也与期望值一样，但是最后free的时候出现了core dump，这个问题查了下有几种解释，这里大概是数组操作越界，或者我们修改了mem区的指针信息，导致free释放内存的时候，释放到别的地方去了，这里不做深究了，留待之后结局。

    最后附上list.h和listapp.c的代码，结束，如有不正确的地方还请指出，大家共同进步。

    

list.h如下

1. <span style="font-size:14px;">#ifndef _LINUX_LIST_H

2. #define _LINUX_LIST_H

3.  
4.  

5. #include <linux/stddef.h>

6.  

7. #ifndef ARCH_HAS_PREFETCH

8. #define ARCH_HAS_PREFETCH

9. static inline void prefetch(const void *x) {;}

10. #endif

11.  

12. #define LIST_POISON1 ((void *) 0x0)

13. #define LIST_POISON2 ((void *) 0x0)

14.  

15. #define container_of(ptr ,type,member) ({ \

16. const typeof( ((type *)0)->member ) *__mptr = (ptr); \

17. (type *)( (char *)__mptr - offsetof(type,member) );})

18.  
19.  

20. /*

21. * Simple doubly linked list implementation.

22. *

23. * Some of the internal functions ("__xxx") are useful when

24. * manipulating whole lists rather than single entries, as

25. * sometimes we already know the next/prev entries and we can

26. * generate better code by using them directly rather than

27. * using the generic single-entry routines.

28. */

29.  

30. struct list_head {

31. struct list_head *next, *prev;

32. };

33.  

34. #define LIST_HEAD_INIT(name) { &(name), &(name) }

35.  

36. #define LIST_HEAD(name) \

37. struct list_head name = LIST_HEAD_INIT(name)

38.  

39. static inline void INIT_LIST_HEAD(struct list_head *list)

40. {

41. list->next = list;

42. list->prev = list;

43. }

44.  

45. /*

46. * Insert a new entry between two known consecutive entries.

47. *

48. * This is only for internal list manipulation where we know

49. * the prev/next entries already!

50. */

51. #ifndef CONFIG_DEBUG_LIST

52. static inline void __list_add(struct list_head *new,

53. struct list_head *prev,

54. struct list_head *next)

55. {

56. next->prev = new;

57. new->next = next;

58. new->prev = prev;

59. prev->next = new;

60. }

61. #else

62. extern void __list_add(struct list_head *new,

63. struct list_head *prev,

64. struct list_head *next);

65. #endif

66.  

67. /**

68. * list_add - add a new entry

69. * @new: new entry to be added

70. * @head: list head to add it after

71. *

72. * Insert a new entry after the specified head.

73. * This is good for implementing stacks.

74. */

75. static inline void list_add(struct list_head *new, struct list_head *head)

76. {

77. __list_add(new, head, head->next);

78. }

79.  
80.  

81. /**

82. * list_add_tail - add a new entry

83. * @new: new entry to be added

84. * @head: list head to add it before

85. *

86. * Insert a new entry before the specified head.

87. * This is useful for implementing queues.

88. */

89. static inline void list_add_tail(struct list_head *new, struct list_head *head)

90. {

91. __list_add(new, head->prev, head);

92. }

93.  

94. /*

95. * Delete a list entry by making the prev/next entries

96. * point to each other.

97. *

98. * This is only for internal list manipulation where we know

99. * the prev/next entries already!

100. */

101. static inline void __list_del(struct list_head * prev, struct list_head * next)

102. {

103. next->prev = prev;

104. prev->next = next;

105. }

106.  

107. /**

108. * list_del - deletes entry from list.

109. * @entry: the element to delete from the list.

110. * Note: list_empty() on entry does not return true after this, the entry is

111. * in an undefined state.

112. */

113. #ifndef CONFIG_DEBUG_LIST

114. static inline void list_del(struct list_head *entry)

115. {

116. __list_del(entry->prev, entry->next);

117. entry->next = LIST_POISON1;

118. entry->prev = LIST_POISON2;

119. }

120. #else

121. extern void list_del(struct list_head *entry);

122. #endif

123.  

124. /**

125. * list_replace - replace old entry by new one

126. * @old : the element to be replaced

127. * @new : the new element to insert

128. *

129. * If @old was empty, it will be overwritten.

130. */

131. static inline void list_replace(struct list_head *old,

132. struct list_head *new)

133. {

134. new->next = old->next;

135. new->next->prev = new;

136. new->prev = old->prev;

137. new->prev->next = new;

138. }

139.  

140. static inline void list_replace_init(struct list_head *old,

141. struct list_head *new)

142. {

143. list_replace(old, new);

144. INIT_LIST_HEAD(old);

145. }

146.  

147. /**

148. * list_del_init - deletes entry from list and reinitialize it.

149. * @entry: the element to delete from the list.

150. */

151. static inline void list_del_init(struct list_head *entry)

152. {

153. __list_del(entry->prev, entry->next);

154. INIT_LIST_HEAD(entry);

155. }

156.  

157. /**

158. * list_move - delete from one list and add as another's head

159. * @list: the entry to move

160. * @head: the head that will precede our entry

161. */

162. static inline void list_move(struct list_head *list, struct list_head *head)

163. {

164. __list_del(list->prev, list->next);

165. list_add(list, head);

166. }

167.  

168. /**

169. * list_move_tail - delete from one list and add as another's tail

170. * @list: the entry to move

171. * @head: the head that will follow our entry

172. */

173. static inline void list_move_tail(struct list_head *list,

174. struct list_head *head)

175. {

176. __list_del(list->prev, list->next);

177. list_add_tail(list, head);

178. }

179.  

180. /**

181. * list_is_last - tests whether @list is the last entry in list @head

182. * @list: the entry to test

183. * @head: the head of the list

184. */

185. static inline int list_is_last(const struct list_head *list,

186. const struct list_head *head)

187. {

188. return list->next == head;

189. }

190.  

191. /**

192. * list_empty - tests whether a list is empty

193. * @head: the list to test.

194. */

195. static inline int list_empty(const struct list_head *head)

196. {

197. return head->next == head;

198. }

199.  

200. /**

201. * list_empty_careful - tests whether a list is empty and not being modified

202. * @head: the list to test

203. *

204. * Description:

205. * tests whether a list is empty _and_ checks that no other CPU might be

206. * in the process of modifying either member (next or prev)

207. *

208. * NOTE: using list_empty_careful() without synchronization

209. * can only be safe if the only activity that can happen

210. * to the list entry is list_del_init(). Eg. it cannot be used

211. * if another CPU could re-list_add() it.

212. */

213. static inline int list_empty_careful(const struct list_head *head)

214. {

215. struct list_head *next = head->next;

216. return (next == head) && (next == head->prev);

217. }

218.  

219. /**

220. * list_is_singular - tests whether a list has just one entry.

221. * @head: the list to test.

222. */

223. static inline int list_is_singular(const struct list_head *head)

224. {

225. return !list_empty(head) && (head->next == head->prev);

226. }

227.  

228. static inline void __list_cut_position(struct list_head *list,

229. struct list_head *head, struct list_head *entry)

230. {

231. struct list_head *new_first = entry->next;

232. list->next = head->next;

233. list->next->prev = list;

234. list->prev = entry;

235. entry->next = list;

236. head->next = new_first;

237. new_first->prev = head;

238. }

239.  

240. /**

241. * list_cut_position - cut a list into two

242. * @list: a new list to add all removed entries

243. * @head: a list with entries

244. * @entry: an entry within head, could be the head itself

245. * and if so we won't cut the list

246. *

247. * This helper moves the initial part of @head, up to and

248. * including @entry, from @head to @list. You should

249. * pass on @entry an element you know is on @head. @list

250. * should be an empty list or a list you do not care about

251. * losing its data.

252. *

253. */

254. static inline void list_cut_position(struct list_head *list,

255. struct list_head *head, struct list_head *entry)

256. {

257. if (list_empty(head))

258. return;

259. if (list_is_singular(head) &&

260. (head->next != entry && head != entry))

261. return;

262. if (entry == head)

263. INIT_LIST_HEAD(list);

264. else

265. __list_cut_position(list, head, entry);

266. }

267.  

268. static inline void __list_splice(const struct list_head *list,

269. struct list_head *prev,

270. struct list_head *next)

271. {

272. struct list_head *first = list->next;

273. struct list_head *last = list->prev;

274.  

275. first->prev = prev;

276. prev->next = first;

277.  

278. last->next = next;

279. next->prev = last;

280. }

281.  

282. /**

283. * list_splice - join two lists, this is designed for stacks

284. * @list: the new list to add.

285. * @head: the place to add it in the first list.

286. */

287. static inline void list_splice(const struct list_head *list,

288. struct list_head *head)

289. {

290. if (!list_empty(list))

291. __list_splice(list, head, head->next);

292. }

293.  

294. /**

295. * list_splice_tail - join two lists, each list being a queue

296. * @list: the new list to add.

297. * @head: the place to add it in the first list.

298. */

299. static inline void list_splice_tail(struct list_head *list,

300. struct list_head *head)

301. {

302. if (!list_empty(list))

303. __list_splice(list, head->prev, head);

304. }

305.  

306. /**

307. * list_splice_init - join two lists and reinitialise the emptied list.

308. * @list: the new list to add.

309. * @head: the place to add it in the first list.

310. *

311. * The list at @list is reinitialised

312. */

313. static inline void list_splice_init(struct list_head *list,

314. struct list_head *head)

315. {

316. if (!list_empty(list)) {

317. __list_splice(list, head, head->next);

318. INIT_LIST_HEAD(list);

319. }

320. }

321.  

322. /**

323. * list_splice_tail_init - join two lists and reinitialise the emptied list

324. * @list: the new list to add.

325. * @head: the place to add it in the first list.

326. *

327. * Each of the lists is a queue.

328. * The list at @list is reinitialised

329. */

330. static inline void list_splice_tail_init(struct list_head *list,

331. struct list_head *head)

332. {

333. if (!list_empty(list)) {

334. __list_splice(list, head->prev, head);

335. INIT_LIST_HEAD(list);

336. }

337. }

338.  

339. /**

340. * list_entry - get the struct for this entry

341. * @ptr: the &struct list_head pointer.

342. * @type: the type of the struct this is embedded in.

343. * @member: the name of the list_struct within the struct.

344. */

345. #define list_entry(ptr, type, member) \

346. container_of(ptr, type, member)

347.  

348. /**

349. * list_first_entry - get the first element from a list

350. * @ptr: the list head to take the element from.

351. * @type: the type of the struct this is embedded in.

352. * @member: the name of the list_struct within the struct.

353. *

354. * Note, that list is expected to be not empty.

355. */

356. #define list_first_entry(ptr, type, member) \

357. list_entry((ptr)->next, type, member)

358.  

359. /**

360. * list_for_each - iterate over a list

361. * @pos: the &struct list_head to use as a loop cursor.

362. * @head: the head for your list.

363. */

364. #define list_for_each(pos, head) \

365. for (pos = (head)->next; prefetch(pos->next), pos != (head); \

366. pos = pos->next)

367.  

368. /**

369. * __list_for_each - iterate over a list

370. * @pos: the &struct list_head to use as a loop cursor.

371. * @head: the head for your list.

372. *

373. * This variant differs from list_for_each() in that it's the

374. * simplest possible list iteration code, no prefetching is done.

375. * Use this for code that knows the list to be very short (empty

376. * or 1 entry) most of the time.

377. */

378. #define __list_for_each(pos, head) \

379. for (pos = (head)->next; pos != (head); pos = pos->next)

380.  

381. /**

382. * list_for_each_prev - iterate over a list backwards

383. * @pos: the &struct list_head to use as a loop cursor.

384. * @head: the head for your list.

385. */

386. #define list_for_each_prev(pos, head) \

387. for (pos = (head)->prev; prefetch(pos->prev), pos != (head); \

388. pos = pos->prev)

389.  

390. /**

391. * list_for_each_safe - iterate over a list safe against removal of list entry

392. * @pos: the &struct list_head to use as a loop cursor.

393. * @n: another &struct list_head to use as temporary storage

394. * @head: the head for your list.

395. */

396. #define list_for_each_safe(pos, n, head) \

397. for (pos = (head)->next, n = pos->next; pos != (head); \

398. pos = n, n = pos->next)

399.  

400. /**

401. * list_for_each_prev_safe - iterate over a list backwards safe against removal of list entry

402. * @pos: the &struct list_head to use as a loop cursor.

403. * @n: another &struct list_head to use as temporary storage

404. * @head: the head for your list.

405. */

406. #define list_for_each_prev_safe(pos, n, head) \

407. for (pos = (head)->prev, n = pos->prev; \

408. prefetch(pos->prev), pos != (head); \

409. pos = n, n = pos->prev)

410.  

411. /**

412. * list_for_each_entry - iterate over list of given type

413. * @pos: the type * to use as a loop cursor.

414. * @head: the head for your list.

415. * @member: the name of the list_struct within the struct.

416. */

417. #define list_for_each_entry(pos, head, member) \

418. for (pos = list_entry((head)->next, typeof(*pos), member); \

419. prefetch(pos->member.next), &pos->member != (head); \

420. pos = list_entry(pos->member.next, typeof(*pos), member))

421.  

422. /**

423. * list_for_each_entry_reverse - iterate backwards over list of given type.

424. * @pos: the type * to use as a loop cursor.

425. * @head: the head for your list.

426. * @member: the name of the list_struct within the struct.

427. */

428. #define list_for_each_entry_reverse(pos, head, member) \

429. for (pos = list_entry((head)->prev, typeof(*pos), member); \

430. prefetch(pos->member.prev), &pos->member != (head); \

431. pos = list_entry(pos->member.prev, typeof(*pos), member))

432.  

433. /**

434. * list_prepare_entry - prepare a pos entry for use in list_for_each_entry_continue()

435. * @pos: the type * to use as a start point

436. * @head: the head of the list

437. * @member: the name of the list_struct within the struct.

438. *

439. * Prepares a pos entry for use as a start point in list_for_each_entry_continue().

440. */

441. #define list_prepare_entry(pos, head, member) \

442. ((pos) ? : list_entry(head, typeof(*pos), member))

443.  

444. /**

445. * list_for_each_entry_continue - continue iteration over list of given type

446. * @pos: the type * to use as a loop cursor.

447. * @head: the head for your list.

448. * @member: the name of the list_struct within the struct.

449. *

450. * Continue to iterate over list of given type, continuing after

451. * the current position.

452. */

453. #define list_for_each_entry_continue(pos, head, member) \

454. for (pos = list_entry(pos->member.next, typeof(*pos), member); \

455. prefetch(pos->member.next), &pos->member != (head); \

456. pos = list_entry(pos->member.next, typeof(*pos), member))

457.  

458. /**

459. * list_for_each_entry_continue_reverse - iterate backwards from the given point

460. * @pos: the type * to use as a loop cursor.

461. * @head: the head for your list.

462. * @member: the name of the list_struct within the struct.

463. *

464. * Start to iterate over list of given type backwards, continuing after

465. * the current position.

466. */

467. #define list_for_each_entry_continue_reverse(pos, head, member) \

468. for (pos = list_entry(pos->member.prev, typeof(*pos), member); \

469. prefetch(pos->member.prev), &pos->member != (head); \

470. pos = list_entry(pos->member.prev, typeof(*pos), member))

471.  

472. /**

473. * list_for_each_entry_from - iterate over list of given type from the current point

474. * @pos: the type * to use as a loop cursor.

475. * @head: the head for your list.

476. * @member: the name of the list_struct within the struct.

477. *

478. * Iterate over list of given type, continuing from current position.

479. */

480. #define list_for_each_entry_from(pos, head, member) \

481. for (; prefetch(pos->member.next), &pos->member != (head); \

482. pos = list_entry(pos->member.next, typeof(*pos), member))

483.  

484. /**

485. * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry

486. * @pos: the type * to use as a loop cursor.

487. * @n: another type * to use as temporary storage

488. * @head: the head for your list.

489. * @member: the name of the list_struct within the struct.

490. */

491. #define list_for_each_entry_safe(pos, n, head, member) \

492. for (pos = list_entry((head)->next, typeof(*pos), member), \

493. n = list_entry(pos->member.next, typeof(*pos), member); \

494. &pos->member != (head); \

495. pos = n, n = list_entry(n->member.next, typeof(*n), member))

496.  

497. /**

498. * list_for_each_entry_safe_continue

499. * @pos: the type * to use as a loop cursor.

500. * @n: another type * to use as temporary storage

501. * @head: the head for your list.

502. * @member: the name of the list_struct within the struct.

503. *

504. * Iterate over list of given type, continuing after current point,

505. * safe against removal of list entry.

506. */

507. #define list_for_each_entry_safe_continue(pos, n, head, member) \

508. for (pos = list_entry(pos->member.next, typeof(*pos), member), \

509. n = list_entry(pos->member.next, typeof(*pos), member); \

510. &pos->member != (head); \

511. pos = n, n = list_entry(n->member.next, typeof(*n), member))

512.  

513. /**

514. * list_for_each_entry_safe_from

515. * @pos: the type * to use as a loop cursor.

516. * @n: another type * to use as temporary storage

517. * @head: the head for your list.

518. * @member: the name of the list_struct within the struct.

519. *

520. * Iterate over list of given type from current point, safe against

521. * removal of list entry.

522. */

523. #define list_for_each_entry_safe_from(pos, n, head, member) \

524. for (n = list_entry(pos->member.next, typeof(*pos), member); \

525. &pos->member != (head); \

526. pos = n, n = list_entry(n->member.next, typeof(*n), member))

527.  

528. /**

529. * list_for_each_entry_safe_reverse

530. * @pos: the type * to use as a loop cursor.

531. * @n: another type * to use as temporary storage

532. * @head: the head for your list.

533. * @member: the name of the list_struct within the struct.

534. *

535. * Iterate backwards over list of given type, safe against removal

536. * of list entry.

537. */

538. #define list_for_each_entry_safe_reverse(pos, n, head, member) \

539. for (pos = list_entry((head)->prev, typeof(*pos), member), \

540. n = list_entry(pos->member.prev, typeof(*pos), member); \

541. &pos->member != (head); \

542. pos = n, n = list_entry(n->member.prev, typeof(*n), member))

543.  

544. /*

545. * Double linked lists with a single pointer list head.

546. * Mostly useful for hash tables where the two pointer list head is

547. * too wasteful.

548. * You lose the ability to access the tail in O(1).

549. */

550.  

551. struct hlist_head {

552. struct hlist_node *first;

553. };

554.  

555. struct hlist_node {

556. struct hlist_node *next, **pprev;

557. };

558.  

559. #define HLIST_HEAD_INIT { .first = NULL }

560. #define HLIST_HEAD(name) struct hlist_head name = { .first = NULL }

561. #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)

562.  

563. static inline void INIT_HLIST_NODE(struct hlist_node *h)

564. {

565. h->next = NULL;

566. h->pprev = NULL;

567. }

568.  

569. static inline int hlist_unhashed(const struct hlist_node *h)

570. {

571. return !h->pprev;

572. }

573.  

574. static inline int hlist_empty(const struct hlist_head *h)

575. {

576. return !h->first;

577. }

578.  

579. static inline void __hlist_del(struct hlist_node *n)

580. {

581. struct hlist_node *next = n->next;

582. struct hlist_node **pprev = n->pprev;

583. *pprev = next;

584. if (next)

585. next->pprev = pprev;

586. }

587.  

588. static inline void hlist_del(struct hlist_node *n)

589. {

590. __hlist_del(n);

591. n->next = LIST_POISON1;

592. n->pprev = LIST_POISON2;

593. }

594.  

595. static inline void hlist_del_init(struct hlist_node *n)

596. {

597. if (!hlist_unhashed(n)) {

598. __hlist_del(n);

599. INIT_HLIST_NODE(n);

600. }

601. }

602.  

603. static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)

604. {

605. struct hlist_node *first = h->first;

606. n->next = first;

607. if (first)

608. first->pprev = &n->next;

609. h->first = n;

610. n->pprev = &h->first;

611. }

612.  

613. /* next must be != NULL */

614. static inline void hlist_add_before(struct hlist_node *n,

615. struct hlist_node *next)

616. {

617. n->pprev = next->pprev;

618. n->next = next;

619. next->pprev = &n->next;

620. *(n->pprev) = n;

621. }

622.  

623. static inline void hlist_add_after(struct hlist_node *n,

624. struct hlist_node *next)

625. {

626. next->next = n->next;

627. n->next = next;

628. next->pprev = &n->next;

629.  

630. if(next->next)

631. next->next->pprev = &next->next;

632. }

633.  

634. /*

635. * Move a list from one list head to another. Fixup the pprev

636. * reference of the first entry if it exists.

637. */

638. static inline void hlist_move_list(struct hlist_head *old,

639. struct hlist_head *new)

640. {

641. new->first = old->first;

642. if (new->first)

643. new->first->pprev = &new->first;

644. old->first = NULL;

645. }

646.  

647. #define hlist_entry(ptr, type, member) container_of(ptr,type,member)

648.  

649. #define hlist_for_each(pos, head) \

650. for (pos = (head)->first; pos && ({ prefetch(pos->next); 1; }); \

651. pos = pos->next)

652.  

653. #define hlist_for_each_safe(pos, n, head) \

654. for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \

655. pos = n)

656.  

657. /**

658. * hlist_for_each_entry - iterate over list of given type

659. * @tpos: the type * to use as a loop cursor.

660. * @pos: the &struct hlist_node to use as a loop cursor.

661. * @head: the head for your list.

662. * @member: the name of the hlist_node within the struct.

663. */

664. #define hlist_for_each_entry(tpos, pos, head, member) \

665. for (pos = (head)->first; \

666. pos && ({ prefetch(pos->next); 1;}) && \

667. ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \

668. pos = pos->next)

669.  

670. /**

671. * hlist_for_each_entry_continue - iterate over a hlist continuing after current point

672. * @tpos: the type * to use as a loop cursor.

673. * @pos: the &struct hlist_node to use as a loop cursor.

674. * @member: the name of the hlist_node within the struct.

675. */

676. #define hlist_for_each_entry_continue(tpos, pos, member) \

677. for (pos = (pos)->next; \

678. pos && ({ prefetch(pos->next); 1;}) && \

679. ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \

680. pos = pos->next)

681.  

682. /**

683. * hlist_for_each_entry_from - iterate over a hlist continuing from current point

684. * @tpos: the type * to use as a loop cursor.

685. * @pos: the &struct hlist_node to use as a loop cursor.

686. * @member: the name of the hlist_node within the struct.

687. */

688. #define hlist_for_each_entry_from(tpos, pos, member) \

689. for (; pos && ({ prefetch(pos->next); 1;}) && \

690. ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \

691. pos = pos->next)

692.  

693. /**

694. * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry

695. * @tpos: the type * to use as a loop cursor.

696. * @pos: the &struct hlist_node to use as a loop cursor.

697. * @n: another &struct hlist_node to use as temporary storage

698. * @head: the head for your list.

699. * @member: the name of the hlist_node within the struct.

700. */

701. #define hlist_for_each_entry_safe(tpos, pos, n, head, member) \

702. for (pos = (head)->first; \

703. pos && ({ n = pos->next; 1; }) && \

704. ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \

705. pos = n)

706.  

707. #endif</span>

 

listapp.c如下

 

1. <span style="font-size:14px;">#include"list.h"//内核链表操作函数

2. #include<malloc.h>//使用malloc分配内存

3. #include<stdio.h>//sprintf和printf

4. #include<string.h>//memset

5.  

6. struct member

7. {

8. char name[100];

9. int num;

10. int score;

11. struct list_head list;

12. };

13.  

14. struct list_head *pos;//遍历指针的pos，不断地指向链表中节点的指针域，需要是list_head指针类型

15. struct list_head member_list;//名为menber_list的链表

16. struct member *tmp;//存放遍历结果，为struct member类型

17. struct member *pmember;//member的成员

18.  

19. int main(void)

20. {

21. unsigned int i = 0; //循环变量的声明

22.  

23. INIT_LIST_HEAD(&member_list); //创建一个链表头，使其前向和后继指针都指向自己，传入参数必须为指针类型，所以取地址

24.  

25. pmember=malloc(sizeof(struct member)*4);

26. memset(pmember,0,sizeof(struct member)*4);//为member成员分配内存，这里分配四个成员，并且对分配到的内存清零

27.  

28. /*给球员成员命名，编号，进球数*/

29. sprintf(pmember[1].name,"player %s","xu");

30. sprintf(pmember[2].name,"player %s","zeng");

31. sprintf(pmember[3].name,"player %s","le");

32. sprintf(pmember[4].name,"player %s","suo");

33.  

34. pmember[1].num=9;

35. pmember[2].num=21;

36. pmember[3].num=10;

37. pmember[4].num=66;

38.  

39. pmember[1].score=2;

40. pmember[2].score=0;

41. pmember[3].score=1;

42. pmember[4].score=5;

43.  

44. /*插入节点，list_add第一个参数是成员内部list的指针，第二个是刚才创建的链表头，这样就插入进去了*/

45. for(i=0;i<4;i++)

46. {

47. list_add(&(pmember[i+1].list),&member_list);

48. printf("###num %d player add sucess!###\n",i+1);

49. }

50.  
51.  

52. /*遍历链表，并开始输出球员信息*/

53. printf("###start list_for_each player information###\n");

54. list_for_each(pos,&member_list)

55. {

56. tmp=list_entry(pos,struct member,list);//第一个参数为pos，第二个要给进去我们定义的球员信息结构体，最后是结构内部的list名

57. printf("play %d name %s score %d\n",tmp->num,tmp->name,tmp->score);

58. }

59.  

60. /*最后删除节点*/

61.  

62. for(i=0;i<4;i++)

63. {

64. list_del(&(pmember[i+1].list));

65. printf("### num %d has deleted###\n",i+1);

66. }

67.  

68. /*释放分配得内存*/

69. free(pmember);

70.  

71. }

72. </span>