링크 ux 커 널 학습 - list 링크

링크 사용 기초:
링크 는 Liux 커 널 에서 가장 간단 하고 보편적 인 데이터 구조 이다.커 널 을 처음 접 한 사람 은 Liux 의 링크 작업 에 익숙 하지 않 을 수 있 습 니 다.커 널 링크 는 여러분 이 평소에 사용 하 는 링크 와 달리 데이터 구 조 를 링크 에 넣 는 것 이 아니 라 링크 노드 를 데이터 구조 에 넣 는 것 입 니 다.Liux 커 널 의 링크 코드 는 < linux/list. h > 에서 설명 합 니 다.
링크 코드 는 헤더 파일 < linux/list. h > 에서 설명 합 니 다. 데이터 구 조 는 매우 간단 합 니 다.
struct list_head{
    struct list_head *next;
    struct list_head *prev;
}

next 지침 은 다음 링크 노드 를 가리 키 고 prev 는 앞 을 가리킨다.여기 서 알 수 있 듯 이 list 링크 는 양 방향 링크 입 니 다.그러나 링크 에 저 장 된 구체 적 인 내용 은 무엇 입 니까?그 관건 은 list 를 이해 하 는 것 이다.헤드 구 조 는 어떻게 사용 되 었 습 니까?
struct fox{
unsigned long tail_length;
unsigned long weight;
bool          is_fantastic;
struct list_head list;       //  fox       
}
container 사용of () 매크로 는 링크 포인터 에서 부모 구조 에 포 함 된 모든 변 수 를 편리 하 게 찾 을 수 있 습 니 다. 이것 은 C 언어 에서 주어진 구조의 변수 가 컴 파일 할 때 주소 가 ABI 에 의 해 고정 되 기 때 문 입 니 다.
현재 fox 의 변 수 를 방문 하려 면 이 struct fox 구조 체 의 주 소 를 먼저 가 져 와 야 합 니 다. 다음 과 같 습 니 다.
struct fox *one = ***;
struct fox *another;
struct list_head *p = &one->list;//만약 우리 가 구조 체 중의 변수 주 소 를 이미 알 고 있다 면
다른 = containerof (p, struct fox, list) 는 이 구조 체 의 지침 을 얻 은 후에 우 리 는 구조 체 의 임 의 구성원 에 게 접근 할 수 있다.
커 널 에 포 함 된of () 매크로 의 실현:
#define container_of(ptr, type, member)({              \
        const typeof( ((type *)0)->member ) *__mptr = (ptr);   \
        (type *)( (char*)__mtr - offsetof(type, member) );})

#define list_entry(ptr, type, member) \
        container_of(ptr, type, member)


매개 변수 ptr 는 구조 체 의 특정한 변수의 주소 이 고 type 은 이 구조 체 유형 이 며 member 는 이 구조 체 유형 에서 포인터 p 에 대응 하 는 구성원 변수 입 니 다.
커 널 안의 링크 는 머리 노드 를 가 진 양 방향 순환 링크 로 실현 된다.그래서 우 리 는 하나의 링크 를 정의 할 때 하나의 체인 헤더 가 있어 야 합 니 다. 위의 예 를 계속 들 어 우 리 는 fox 에 관 한 링크 를 정의 하고 초기 화 합 니 다.
list_head fox_list;
static LIST_HEAD(fox_list);     //체인 헤더 도 listhead 형식
링크 작업:
링크 작업 은 증가, 삭제, 옮 겨 다 니 는 것 이 아니 라 하나씩 소개 합 니 다.
링크 에 노드 추가:
list_add(struct list_head *new, struct list_head *head)
이 함 수 는 링크 의 head 노드 를 지정 한 후에 new 노드 를 삽입 합 니 다. 사실은 new 노드 를 링크 요소 의 첫 번 째 위치 에 두 었 습 니 다 (머리 노드 는 데 이 터 를 포함 하지 않 습 니 다).
만약 우리 가 새로운 struct fox 노드 를 만 들 고 그것 을 fox 에 넣는다 면list, 그럼 우 리 는 이렇게 합 니 다.
struct fox f;
list_add(&f->list, &fox_list);
링크 끝 에 노드 를 추가 하려 면 다음 함 수 를 사용 할 수 있 습 니 다.
list_add_tail(struct list_head *new, struct list_head *head)
이 함 수 는 링크 의 head 노드 를 지정 하기 전에 new 노드 를 삽입 합 니 다.
커 널 의 실현 을 살 펴 보 자.
/*
 * Insert a new entry between two known consecutive entries.
 *
 * This is only for internal list manipulation where we know
 * the prev/next entries already!
 */
static inline void __list_add(struct list_head *new,
                  struct list_head *prev, struct list_head *next)
{
    next->prev = new;
    new->next = next;
    new->prev = prev;
    prev->next = new;
}

/**
 * list_add - add a new entry
 * @new: new entry to be added
 * @head: list head to add it after
 *
 * Insert a new entry after the specified head.
 * This is good for implementing stacks.
 */
static inline void list_add(struct list_head *new, struct list_head *head)
{
    __list_add(new, head, head->next);
}

/**
 * list_add_tail - add a new entry
 * @new: new entry to be added
 * @head: list head to add it before
 *
 * Insert a new entry before the specified head.
 * This is useful for implementing queues.
 */
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
    __list_add(new, head->prev, head);
}

링크 에 노드 삭제 하기:
list_del(struct list_head *entry)
이 함 수 는 링크 에서 entry 함 수 를 삭제 하지만 entry 를 방출 하거나 entry 를 포함 한 데이터 구조 체 잠 금 이 사용 하 는 메모 리 를 방출 하지 않 습 니 다. 이 함 수 는 entry 요 소 를 링크 에서 가 져 가 는 것 일 뿐 메모리 가 필요 하 다 면 따로 조작 해 야 합 니 다.
커 널 코드 구현:
static inline void __list_del(struct list_head *prev, struct list_head *next)
{
	next->prev = prev;
	prev->next = next;
}

/**
 * list_del - deletes entry from list.
 * @entry: the element to delete from the list.
 * Note: list_empty() on entry does not return true after this, the entry is
 * in an undefined state.
 */
#ifndef CONFIG_DEBUG_LIST
static inline void list_del(struct list_head *entry)
{
	__list_del(entry->prev, entry->next);
	entry->next = (void *)0xDEADBEEF;
	entry->prev = (void *)0xBEEFDEAD;
} 

이동 및 병합 링크 노드:
노드 를 하나의 링크 에서 다른 링크 로 이동 합 니 다.
list_move(struct list_head *list, struct list_head *head)
이 함 수 는 하나의 링크 에서 list 항목 을 제거 한 다음 다른 링크 의 head 노드 뒤에 넣 고 다른 링크 의 끝 으로 이동 하려 면 다음 함 수 를 사용 합 니 다.
list_move_tail(struct list_head *list, struct list_head *head)
연결 되 지 않 은 링크 두 개 를 합 칩 니 다:
list_splice(struct list_head *list, struct list_head *head)
list 가 가리 키 는 링크 를 지정 한 링크 의 head 요소 뒤에 삽입 합 니 다.
전체 링크 옮 겨 다 니 기:
링크 를 옮 겨 다 니 며 방문 하 는 것 은 링크 작업 에서 매우 중요 한 작업 이자 자주 사용 하 는 것 이다.우리 가 링크 를 만 드 는 목적 은 링크 의 데 이 터 를 방문 하기 위해 서 이다.
링크 접근 방법 은 다음 과 같 습 니 다.
struct list_head *p; struct fox *f; list_for_each(p, fox_list){         f = list_entry(p, struct fox, list); //p. 링크 의 요 소 를 가리킨다.       /* 요 소 를 방문 하기 시작 합 니 다 */} 링크 를 옮 겨 다 니 는 데 더 편리 한 용법 이 있 습 니 다: listfor_each_entry (pos, head, member) 위의 예 도 이렇게 접근 할 수 있 습 니 다: struct fox * f;list_for_each_entry(f, &fox_list, list){        /* 요소 접근 시작 */}
역방향 스 트 리밍 링크: listfor_each_entry_reverse (pos, head, member) 를 옮 겨 다 니 면서 삭제 합 니 다. 표준 링크 를 옮 겨 다 니 는 방법 은 링크 를 옮 겨 다 니 는 동시에 노드 를 삭제 하려 면 안 됩 니 다. 구체 적 인 원인 은 커 널 소스 코드 에 따라 스스로 생각해 보 세 요.Liux 커 널 은 다음 과 같은 조작 방법 을 제공 합 니 다.
list_for_each_entry_safe(pos, next, head, member)
list_for_each_entry_safe_reverse (pos, next, head, member) 중 next 와 pos 는 같은 유형 이자 listhead 포인터, 커 널 실현:
/**
 * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
 * @pos:	the type * to use as a loop cursor.
 * @n:		another type * to use as temporary storage
 * @head:	the head for your list.
 * @member:	the name of the list_struct within the struct.
 */
#define list_for_each_entry_safe(pos, n, head, member)			\
	for (pos = list_entry((head)->next, typeof(*pos), member),	\
		n = list_entry(pos->member.next, typeof(*pos), member);	\
	     &pos->member != (head); 					\
	     pos = n, n = list_entry(n->member.next, typeof(*n), member))

/**
 * list_for_each_entry_safe_reverse
 * @pos:    the type * to use as a loop cursor.
 * @n:        another type * to use as temporary storage
 * @head:    the head for your list.
 * @member:    the name of the list_struct within the struct.
 *
 * Iterate backwards over list of given type, safe against removal
 * of list entry.
 */
#define list_for_each_entry_safe_reverse(pos, n, head, member)        \
    for (pos = list_entry((head)->prev, typeof(*pos), member),    \
        n = list_entry(pos->member.prev, typeof(*pos), member);    \
         &pos->member != (head);                     \
         pos = n, n = list_entry(n->member.prev, typeof(*n), member)) 

좋은 웹페이지 즐겨찾기