색다른 연결리스트들

『디버깅을 통해 배우는 리눅스 커널의 구조와 원리』 책을 보다 색다른 연결리스트들을 보게 되었다. 

 

1. 꼬리 비우기형

보통 연결리스트 라고 하면 아래의 코드를 떠올렸다.

struct list_head = {
    struct list_node *head;
    struct list_node *tail;
};

new_node->next = NULL;				
list_head->tail->next = new_node;	// 마지막 노드에 새로운 노드를 연결한다.
list_head->tail = new_node;		// 새로운 노드가 tail로 대체됨.

 

그런데 tail 맴버를 수정하면 다음과 같이 tail을 항상 비워두는 것으로 할 수 있다.

(코드를 보면 알겠지만 실제로 빈 공간이 생기는건 아님)

struct list_head = {
    struct list_node *head;
    struct list_node **tail;
};

new_node->next = NULL;				
*list_head->tail = new_node;          // 새로운 노드가 tail로 대체됨.
list_head->tail = &(new_node->next);  // tail을 새로운 노드의 next로 대체. (빈공간)

 

2. 데이터에 노드 집어넣기

보통 아래와 같은 방법으로 노드안에 데이터와 다음 노드 포인터를 만들어서 연결하는 방식을 쓰는데...

이건 정말 특이한 방법을 쓴다.

struct list_node = {
    void *data;
    struct list_node *prev;
    struct list_node *next;
};

 

노드를 데이터 안에 넣어버렸다.

 

출처 : https://bbingju.wordpress.com/2013/08/25/linux-kernel-list-h/

 

아래처럼 list_head 구조체를 만들어서 안에 넣어버린다.

list_head 구조체는 <linux/list.h>에서 볼 수 있다.

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

struct data_struct {
    void *data;
    struct list_head list;
};

간단하다!

안에 노드를 넣어버리면 굳이 노드 구조체로 만들 필요 없이 맴버변수만 추가하면 될것이다.

 

근데 이게 가능한걸까?

노드끼리는 탐색할 수 있지만 데이터가 들어있는 data_struct는 찾을 수 없지 않나?

 

아래 매크로로 data_struct를 찾을 수 있다.

맴버변수의 오프셋을 찾아서 그값만큼 앞으로 움직이는 방법이다.

#define container_of(ptr, type, member) ({				\
	void *__mptr = (void *)(ptr);					\
	BUILD_BUG_ON_MSG(!__same_type(*(ptr), ((type *)0)->member) &&	\
			 !__same_type(*(ptr), void),			\
			 "pointer type mismatch in container_of()");	\
	((type *)(__mptr - offsetof(type, member))); })

 

<linux/list.h>에서 기본 함수들을 지원한다.

사용하려면 대충 이렇게 쓰면 된다. (위 그림 처럼 아무 데이터도 없는 헤드를 만드는게 보통이다)

LIST_HEAD(data_list);

struct data_struct* a;
a = kmalloc(sizeof(*a), GFP_KERNEL);

list_add(&a->list, &data_list);

 

 

순회 기능도 있다.

p = 이터레이션 변수

data_list = 연결리스트의 헤드

list = data_struct 구조체에서 list_head가 들어있는 맴버변수 이름

struct data_struct *p;

list_for_each_entry(p, &data_list, list) {
	p->data
    ....
}

 

커널 코드에서 이 방식을 많이 쓰는 것 같다.