list_머리 상세 설명

/* 2012.11.27 광 공 대 에서 정리 */
Liux 커 널 에서 대량의 데이터 구 조 는 프로 세 스, 파일, 모듈, 페이지 등 이중 순환 링크 를 사용 해 야 합 니 다.만약 에 쌍 순환 링크 의 전통 적 인 실현 방식 을 사용 하려 면 이런 데이터 구 조 를 위해 각자 의 링크 를 유지 하고 모든 링크 에 삽입, 삭제 등 조작 함 수 를 설계 해 야 한다.링크 를 유지 하 는 next 와 prev 포인터 가 대응 하 는 유형의 대상 을 가리 키 기 때문에 데이터 구조의 링크 조작 함 수 는 다른 데이터 구 조 를 조작 하 는 링크 에 사용 할 수 없습니다.따라서 Linux 소스 코드 트 리 의 include/linux/list. h 파일 에 서 는 (데이터 구조) 형식 과 무관 한 이중 순환 링크 구현 방식 을 사용 합 니 다.그 사상 은 포인터 prev 와 next 를 구체 적 인 데이터 구조 에서 추출 처리 하여 통용 되 는 '더 블 링크' 데이터 구조 list 를 구성 하 는 것 이다.head, listhead 는 지퍼 의 데이터 구조 (숙주 데이터 구조 라 고 함) 에 구성원 으로 삽입 되 어 있 습 니 다.이렇게 하면 통용 되 는 링크 조작 함수 한 세트 만 있 으 면 list헤드 구성원 은 '연결 부품' 으로 숙주 데이터 구 조 를 연결한다.
 링크 ux 커 널 의 링크 정의 가 비교적 간단 합 니 다.

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

 list_head 구 조 는 두 개의 지향 list 를 포함한다.head 구조의 지침 은 더 블 체인 시계 입 니 다.그러나 listhead 에 데이터 필드 가 없습니다. 링크 ux 커 널 링크 에 데 이 터 를 포함 하 는 것 이 아니 라 데이터 구조 에 링크 노드 list 를 포함 합 니 다.head.
 링크 노드 에서 데이터 항목 변 수 는 list 를 통 해entry (ptr, type, member) 매크로 가 이 루어 집 니 다. ptr 는 이 데이터 항목 을 가리 키 는 list헤드 멤버 의 지침, type 은 데이터 항목 의 형식 입 니 다. member 는 데이터 구조 에서 list헤드 멤버,
 이중 순환 링크 구현 방식 에서:  1. 링크 구 조 는 하나의 구성원 으로 숙주 데이터 구조 에 삽 입 됩 니 다.  2. 링크 구 조 를 숙주 구조 안의 어느 곳 에 나 놓 을 수 있다.  3. 링크 구조 에 모든 이름 을 지 을 수 있 습 니 다.  4. 숙주 구 조 는 여러 개의 링크 구 조 를 가 질 수 있다.
list_head 의 일부 상용 작업 (커 널 은 이미 완전한 자체 테이프):
 덧붙이다 커 널 의 모든 링크 (추가, 삭제, 이동, 연결 등 포함) 작업 은 데이터 구조 list헤드 진행.
 링크 에 대한 추가 작업 은 두 가지 가 있 습 니 다. 헤더 추가 와 표 끝 추가 입 니 다. Linux 더 블 순환 링크 에 체인 헤더 가 있 습 니 다. 헤더 추 가 는 체인 헤더 에 추 가 된 다음 에 표 꼬리 추 가 는 체인 에 추 가 된 것 을 말 합 니 다. 표 두 의 prev 가 가리 키 는 링크 노드 (빈 링크 라면 이 링크 노드 는 체인 헤드 자체) 이후 입 니 다.
 Linux 는 이 를 위해 두 개의 인 터 페 이 스 를 제공 합 니 다. static inline void list_add(struct list_head *new, struct list_head *head);  static inline void list_add_tail(struct list_head *new, struct list_head *head);  상기 인 터 페 이 스 는 모두 호출list_add 완성 static inline void __list_add(struct list_head *new, struct list_head *prev, struct list_head *next);
 
 삭제 링크 에서 링크 노드 를 삭제 하려 면 list 를 호출 할 수 있 습 니 다.del 또는 listdel_init.    static inline void list_del(struct list_head *entry);  static inline void list_del_init(struct list_head *entry);    둘 다 호출list_del 노드 를 링크 에서 꺼 낸 후 listdel 은 노드 를 삭제 할 prev 와 next 지침 을 모두 NULL 로 설정 합 니 다. 이 노드 를 통 해 접근 할 수 없 음 을 보증 합 니 다. 그리고 listdel 은 LIST 호출INIT_HEAD () 는 삭 제 된 노드 를 링크 헤드 로 새로운 쌍 순환 링크 를 구축 합 니 다.
 주의: 상기 조작 은 모두 노드 를 쌍 순환 링크 에서 제거 하 는 것 일 뿐 사용 자 는 이 노드 에 대응 하 는 데이터 구조 가 차지 하 는 공간 을 스스로 방출 해 야 합 니 다. 이 공간 은 원래 사용자 가 분배 한 것 이다.
 
 이동 하 다. 리 눅 스 는 두 개의 이동 조작 도 제공 했다. listmove 와 listmove_tail.    전 자 는 지정 한 노드 를 링크 에서 꺼 내 다른 링크 의 머리 에 추가 합 니 다. 후 자 는 꺼 낸 후 새 링크 의 꼬리 부분 에 추가 했다.
 static inline void list_move(struct list_head *list, struct list_head *head);  static inline void list_move_tail(struct list_head *list, struct list_head *head);
 
 조립 하 다 Linux 는 두 개의 링크 의 연결 을 지원 합 니 다. 구체 적 인 함 수 는 list 입 니 다.splice 와 listsplice_init:    static inline void list_splice(struct list_head *list, struct list_head *head);  static inline void list_splice_init(struct list_head *list, struct list_head *head);    두 함수 모두 하나의 링크 의 모든 노드 를 다른 링크 의 머리 에 순서대로 추가 하고 새로운 링크 는 원래 링크 의 첫 번 째 노드 를 첫 번 째 노드 로 한다. 꼬리 부분 은 변 하지 않 는 다.
 차이 점 은 전자, 원 체인 헤더 의 next 와 prev 가 여전히 원래 의 곳 을 가리 키 는 것 이다. 후자 호출 INITLIST_HEAD () 는 원본 체인 헤더 에 빈 이중 순환 링크 를 초기 화 합 니 다.
 
 두루 이중 순환 링크 의 기본 동작 입 니 다. 이 를 위해 리 눅 스 는 매크로 를 정의 합 니 다. list_for_each 링크 를 옮 겨 다 니 는 모든 listhead 노드 는 숙주 구조 에 대한 처리 와 관련 이 없습니다.
 list_for_each 는 실제 for 순환 으로 들 어 오 는 지향 list헤드 구조의 바늘 은 순환 변수 로 체인 헤드 부터 (체인 헤드 를 건 너 뛰 기), 다시 체인 헤더 로 돌아 갈 때 까지 바늘 을 뒤로 이동 합 니 다.스 트 리밍 속 도 를 높이 기 위해 프 리 캐 스 트 도 사용 했다.   #define list_for_each(pos, head)\  for (pos = (head)->next, prefetch(pos->next); pos != (head);\   pos = pos->next, prefetch(pos->next))      반대로 list 를 옮 겨 다 닐 필요 가 있다 면head 링크, list 사용 가능for_each_prev 매크로.   #define list_for_each_prev(pos, head)\  for (pos = (head)->prev, prefetch(pos->prev); pos != (head);\   pos = pos->prev, prefetch(pos->prev))      상기 두 동작 은 모두 이동 (list head 구 조 를 가리 키 는) 지침 을 통 해 옮 겨 다 니 는 목적 을 달성 합 니 다.단, 옮 겨 다 니 는 과정 에서 삭제 나 이동 이 포함 되 어 있 습 니 다. 현재 링크 노드 의 작업 은 옮 겨 다 니 는 지침 을 수정 하기 때문에 옮 겨 다 니 는 중단 을 초래 할 수 있 습 니 다.이 경우 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)
 이에 리 눅 스 는 list 를 제공 합 니 다.for_each_entry () 매크로, 첫 번 째 매개 변 수 는 들 어 오 는 옮 겨 다 니 는 포인터 이 고 숙주 데이터 구 조 를 가리 키 며 두 번 째 매개 변 수 는 체인 헤더 입 니 다. 위 listhead 구조, 세 번 째 매개 변 수 는 list헤드 구조 가 숙주 구조 에 있 는 구성원 명.   #define list_for_each_entry(pos, head, member)\  for (pos = list_entry((head)->next, typeof(*pos), member),\   prefetch(pos->member.next);\    &pos->member != (head); \     pos = list_entry(pos->member.next, typeof(*pos), member),\      prefetch(pos->member.next))
 실현 방법 은: #define list_entry(ptr, type, member)\                           container_of(ptr, type, member)                             Linux 는 이 를 위해 list 를 제공 합 니 다.entry () 매크로, 현재 list 획득head 링크 노드 가 있 는 숙주 구조 항목.   그 중 에 설 계 된 containerof (ptr, type, member) 구성원, containerof 분석 은 다음 과 같다. ptr 는 구성원 변수의 지침 입 니 다. type 은 구조 체 의 유형 을 말 합 니 다. member 는 구성원 변수의 이름 입 니 다.
 container_of 의 역할 은 하나의 구조 체 변수 중의 한 도 메 인 구성원 변수의 지침 에 따라 전체 구조 체 변 수 를 가리 키 는 지침 을 얻 는 것 이다.
 사용 방법:

 struct demo_struct { 
  type1 member1; 
  type2 member2;
  type3 member3; 
  type4 member4; 
 };

 type: 3 유형의 멤버 member 3 의 지침 을 획득 하여 container 를 통과 할 수 있 습 니 다.of 전체 구조 체 의 지침 획득
 struct demo_struct *demop =             container_of(memp, struct demo_struct, member3);  
 container 에 대하 여of 의 더 자세 한 소 개 는 제 다른 글 을 보십시오.
 
이로써 커 널 자체 list헤드 의 소 개 는 여기까지 입 니 다. 다음은 사용 실례 를 드 리 겠 습 니 다. Red Hat 에서 컴 파일 테스트 를 통 과 했 습 니 다.
 

#include <linux/module.h>
#include <linux/init.h>
#include <linux/kernel.h>
#include <linux/list.h>

#define STUDENT_NUM 10

static int del_num = 3;

module_param(del_num, int, 0);
MODULE_PARM_DESC(del_num, "delete which node");


/*              list_head */
struct student {
	char name;
	int number;
	struct list_head list;
};

/*   list_head */
struct list_head student_list;

int create_list(void)
{
	struct student *pnode = NULL;
	int cnt;

	/*    list_head， list->next = list;list->prev = list; */
	INIT_LIST_HEAD(&student_list);
	
	printk("entry %s.
",__FUNCTION__);	
	
	for(cnt = 0; cnt < STUDENT_NUM; cnt++)
	{
		pnode = (struct student *)kmalloc(sizeof(struct student), GFP_KERNEL);
		if(pnode < 0)
		{
			printk("%s:kmalloc fail.
", __FUNCTION__);
			return -ENOMEM;
		}

		pnode->name   = 'A' + cnt;
		pnode->number = cnt;

		list_add_tail(&pnode->list, &student_list);
	}
	return 1;
}



void print_list(void)
{	
	struct student *pnode = NULL;
	struct list_head *plist = NULL;

	printk("entry %s.
",__FUNCTION__);

	/* list_for_each  list_head */
	list_for_each(plist, &student_list)
	{
		/* list_entry    list_head             */
		pnode = list_entry(plist, struct student, list);
		
		printk("student name is %c, number is %d.
", pnode->name, pnode->number);
	}
}

void del_list(int del_num)
{
	struct student *pnode = NULL;
	struct list_head *plist = NULL, *pnext = NULL;

	printk("entry %s.
",__FUNCTION__);

	/*        */
	list_for_each_safe(plist, pnext, &student_list)
	{
		/* list_entry    list_head             */
		pnode = list_entry(plist, struct student, list);
		
		if(pnode->number == del_num)
		{
			list_del(plist);
			printk("delete student name is %c, number is %d.
",pnode->name, pnode->number);
			kfree(pnode);
		}
	}
}
static int __init mylist_init(void)
{
	int ret;
	
	ret = create_list();
	if(ret < 0)
	{
		printk("create list failed.
");
		return -EFAULT;
	}

	print_list();

	del_list(del_num);

	print_list();

	return 0;
}

static void __exit mylist_exit(void)
{
	printk("mylist module exit.
");
}

module_init(mylist_init);
module_exit(mylist_exit);

MODULE_LICENSE("GPL");
MODULE_DESCRIPTION("list module");