Linked List..
send signal..

软件开发平台及语言笔记大全(超详细)

Linux Kernel: 強大又好用的list_head結構

Linux Kernel: 強大又好用的list_head結構 程式設計者在設計一個doubly linked list時，通常會在所宣告的結構裡宣告兩個結構指標，如下所示：

struct student {
    char name[16];
    int id;
    struct student *next, *prev;
};

只要經由prev與next兩個結構指標，便能取得該doubly linked list所有資訊。

然而，Linux kernel並非引用此種作法。因此，Linux kernel定義一通用結構 (struct list_head， include/linux/list.h)，用以實作doubly linked list，此結構相當簡單，如下所示：

struct list_head {
    struct list_head *next, *prev;
};

所以物件student宣告為如下：

struct student
{
    char name[16];
    int id;
    struct list_head list;
};

藉由list變數便能取得doubly linked list所有資訊。

###list_head相關Marco與Function

這裡僅介紹較常用的macro與function，如欲進一步得知其它marco請參考include/linux/list.h

LIST_HEAD(name)
struct list_head name = { &(name), &(name) };
將next與prev指到自己，意味著此list為空的。

list_empty(const struct list_head *head)
retrun head->next == head;
檢查此list是否為空的。

list_add(struct list_head *new, struct list_head *head)
head->next->prev = new;
new->next = head->next;
new->prev = head;
head->next = new;
將資料加入至doubly linked list最前端。建議自己動手畫個圖，便可瞭解這幾個指標指到何處。

list_del(struct list_head *entry)
entry->next->prev = entry->prev;
entry->prev->next = entry->next;
將某一資料從中刪除。

list_entry(ptr,type,member)
((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))

透過此函式便能算出結構的起始位址，並做結構轉型便能取得結構的資料，此計算方式相當好用啊!!!

以struct student為例，如下所示：

(unsigned long)(&((struct student *)0)->member))) ==> 計算出list成員相對位址。通常看到這一個敘述，直覺地覺得應該會記憶體區段錯誤吧 (Segmentation Fault)!? 因為該敘述用NULL的pointer存取list成員，但在(struct student *)0)->member))前面加了&符號，就不會發生記憶體區段錯誤。因為&符號，只意味著存取list的位址，而不是資料， 經由此敘述便能取得list的位移植。如下圖所示，該敘述所得之位移植值為20。

((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member))) ==> 取得位移植之後，再將list的位址減去位移植，便能取得該結構的起始位址，如下圖所示 (假設結構起始位址為x)，最後再做結構轉型變大功告成。

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

取得該doubly linked list所有資料。

  • Makefile
obj-m += list_head_ex.o

KDIR=/lib/modules/$(shell uname -r)/build

all:
	make -C $(KDIR) M=$(PWD) modules
clean:
	make -C $(KDIR) M=$(PWD) clean

-list_head_ex.c

/*
 * =============================================================================
 *
 *       Filename:  list_head_ex.c
 *
 *    Description:  Write a doubly linked list by using list_head structure
 *
 *        Version:  1.0
 *        Created:  Fri Oct 19 14:14:57 GMT 2007
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  Adrian Huang
 *        Web Site:  http://adrianhuang.blogspot.com/
 *
 * ============================================================================
 */

#include "list_head_ex.h"

int __init list_head_init(void)
{
	struct list_head	std_head, *next;
	struct student		sl[NR_STDS]; 		// student list
	struct student		*studentP; 	// student pointer
	int					idx;

	/* init std_head */
	INIT_LIST_HEAD(&std_head);

	/* Check whether the std_head is empty */
	if(list_empty(&std_head) == TRUE) {
		printk(KERN_INFO "[Adrian] std_head is NULL\n");
	}

	/* Add each element to student head (std_head) */
	for(idx=0;idx<sizeof(sl)/sizeof(struct student);idx++) {
		sprintf(sl[idx].name, "Adrian Huang");
		sl[idx].id = idx + 1;
		list_add(&sl[idx].list, &std_head);
	}

	printk(KERN_INFO "======dump all elements of the list by invoking "
					"'list_for_each'=========\n");
	/* Traverse all elements of the list */
	list_for_each(next, &std_head) {
		studentP = (struct student *) list_entry(next, struct student, list);
		printk(KERN_INFO "[Adrian] name: %s, id: %d\n",
							 studentP->name, studentP->id);
	}


	printk(KERN_INFO "\n======dump all elements of the list by invoking "
					"'list_entry'=========\n");
	/* Traverse all elements of the list and delete each of it */
	for(idx=0;idx<sizeof(sl)/sizeof(struct student);idx++) {
		studentP = (struct student *) list_entry(std_head.next,
									 struct student, list);

		printk(KERN_INFO "[Adrian] name: %s, id: %d\n",
							 studentP->name, studentP->id);

		list_del(std_head.next);
	}

	return 0;
}

void __exit list_head_exit(void)
{
	;
}

module_init(list_head_init);
module_exit(list_head_exit);
  • list_head_ex.h
/*
 * =============================================================================
 *
 *       Filename:  list_head_ex.h
 *
 *    Description: Write a doubly linked list by using list_head structure
 *
 *        Version:  1.0
 *        Created:  Fri Oct 19 14:17:58 GMT 2007
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  Adrian Huang
 *       Web Site:  http://adrianhuang.blogspot.com/
 *
 * =============================================================================
 */

#ifndef  LIST_HEAD_EX_INC
#define  LIST_HEAD_EX_INC

#include <linux/module.h>	/* Needed by all modules */
#include <linux/kernel.h>	/* Needed for KERN_INFO */
#include <linux/jiffies.h>
#include <linux/list.h>		/* list_head structure	*/

#define	NR_STDS	5

struct student {
	char				name[16];
	int					id;
	struct list_head	list;
};

typedef enum _Boolean { FALSE = 0, TRUE = 1 } LHBOOL; // list head boolean

#endif   /* ----- #ifndef LIST_HEAD_EX_INC  ----- */

code Download

书籍推荐