타입 의존성 제거 (Loose Coupling)
C언어를 사용하는 환경에서 만약 linked list 구조에 우리가 원하는 구조체를 가지는 instance를 저장하고 싶을 때는 쉽게 되지 않는다.
typedef struct _node
{
int data;
struct _node *next;
struct _node *prev;
} NODE;
typedef struct _sawon {
char name[20];
} SAWON;
void __insert_data(NODE *_temp, NODE *_prev, NODE *_next)
{
_temp->next = _next;
_temp->prev = _prev;
_prev->next = _temp;
_next->prev = _temp;
}
void insert_front(NODE *_temp, NODE *_head) {
__insert_data(_temp, _head, _head->next);
}
위 코드처럼 SAWON 이라는 구조체가 있는데, 해당 구조체를 linked list에 삽입하려고 할 때, 위 코드에서 사용되는 insert_front() 함수에 넣을 수 없는게, NODE 타입이 아니기 때문이다. 이런 타입 의존성을 제거하기 위해서 void pointer가 사용되게 된다.
Void Pointer 방식
#include <stdio.h>
#include <stdlib.h>
#define FIFO_DEPTH 2
typedef struct _node
{
void *data;
struct _node *next;
struct _node *prev;
} NODE;
typedef struct _sawon {
char name[20];
} SAWON;
void __insert_data(NODE *_temp, NODE *_prev, NODE *_next)
{
_temp->next = _next;
_prev->next = _temp;
_temp->prev = _prev;
_next->prev = _temp;
}
void insert_front(NODE *_temp, NODE *_head) {
__insert_data(_temp, _head, _head->next);
}
void insert_back(NODE *_temp, NODE *_head) {
__insert_data(_temp, _head->prev, _head);
}
void display(NODE *head)
{
NODE *temp;
SAWON *s;
system("clear");
printf("[head]");
for(temp=head->next; temp != head; temp=temp->next) {
s = (SAWON*) temp->data;
printf("<->[%s]", s->name);
}
printf("<->[head]\n");
getchar();
}
int main()
{
NODE head0 = {0,&head0, &head0};
NODE temps[FIFO_DEPTH];
SAWON s[FIFO_DEPTH] = {{"Jason"}, {"Tommy"}};
display(&head0);
for(int i=0; i<FIFO_DEPTH; i++)
{
temps[i].data = &s[i];
insert_front(temps+i, &head0);
display(&head0);
}
return 0;
}
| [head]<->[Tommy]<->[Jason]<->[head] |
결과는 위와 같이 나오게 된다.
Sizeof 방식
위에서 void pointer 방식으로 loose coupling을 구현했는데, 여기엔 두 가지 문제점이 존재한다.
1. 만약 data를 heap 영역에 저장하고, linked list를 stack에 저장 했을 때, head memory free를 하기 전에 stack에 메모리가 free 될 경우, Dangling Pointer가 발생 할 수 있다.
2. 만약 heap에 저장된 data를 free하고 난 뒤에 해당 포인터를 가지고 있는 void pointer는 해당 영역이 allocation인지 free인지를 알 수 없는 상태로 접근하게 되면 문제가 발생 할 수 있다.
따라서 할당과 해지 시점을 적절하게 관리해줘야 한다. 그렇다고 data를 linked list에 넣자니 data 의존성이 존재한다.
이를 해결하고자 하는 방법은, linked list에 data를 넣지 말고, data에 linked list를 넣는 방식이다.
typedef struct _node
{
struct _node *next;
struct _node *prev;
} NODE;
typedef struct _sawon {
char name[20];
NODE list;
} SAWON;
위 그림과 코드처럼 구조 모습과 코드 구현이 나타날 수 있다. 그럼 이런 방식으로 다시 코드 구현을 해보면 다음과 같다.
typedef struct _node
{
struct _node *next;
struct _node *prev;
} NODE;
typedef struct _sawon {
char name[20];
NODE list;
} SAWON;
void __insert_data(NODE *_temp, NODE *_prev, NODE *_next)
{
_temp->next = _next;
_prev->next = _temp;
_temp->prev = _prev;
_next->prev = _temp;
}
void insert_front(NODE *_temp, NODE *_head) {
__insert_data(_temp, _head, _head->next);
}
void display(NODE *head)
{
NODE *temp;
SAWON *s;
system("clear");
printf("[head]");
for(temp=head->next; temp != head; temp=temp->next) {
printf("<->[%p]", temp);
}
printf("<->[head]\n");
getchar();
}
int main()
{
NODE head = {&head, &head};
NODE temps[FIFO_DEPTH];
SAWON s[FIFO_DEPTH] = {{"Jason"}, {"Tommy"}};
display(&head);
for(int i=0; i<FIFO_DEPTH; i++)
{
insert_front(&s[i].list, &head);
display(&head);
}
return 0;
}
위 코드에서 display() 함수를 보면 우리가 최종적으로 접근하고자 하는 data쪽을 접근을 하지 못하는데, 이는 linked list의 시작주소 (&list)만 알 수있기 때문이다. 따라서 아래 그림과 같이 data의 크기만큼 pointer를 이동시켜야 한다.
위 그림 기준으로 pointer 값을 구하고자 하면 아래와 같은 식이 필요 할 것이다. 참고로 20을 빼는 이유는 초기에 data size를 20 bytes로 잡았기 때문이다.
SAWON *s; s = (SAWON*) ((char *)temp - 20); // list는 16 bytes기 때문에 1 byte 단위로 변경해서 연산을 수행해야 함, 이를 위해 (char *) 타입으로 캐스팅
그런데 위 코드와 같이 수정하고 동작시키면 돌아가지 않는데, 이유는 실제 구조체에 data 크기가 20 bytes보다 더 크게 잡혔기 때문이다. Machine 마다 메모리를 할당하는 방식이 다르기 때문에 이런 constant value로 해선 안되고, 아래 NODE의 크기만큼을 빼줘서 구해야 한다.
SAWON *s; s = (SAWON*) ((char *)temp - (sizeof(SAWON) - sizeof(NODE)));
위와 같이 구현하게 되면 문제 없이 원하는 data를 access 할 수 있다.
container_of 방식
SAWON 구조체를 보게 되면 1개의 list만을 가지고 있을 때만 가능하다. 만약 1개의 list가 아니라 복수개의 list를 가질 경우엔, 중간에 있는 list는 자기 자신의 크기를 빼선 처음 pointer 주소를 알 수 없다.
따라서 list1의 offset, 즉 data의 크기만큼만을 알아야지 base address를 알 수 있다. 이를 위해서 다음과 같은 코드로 구현이 가능하다.
SAWON *s; s = (SAWON*) ((char *)temp - (unsigned long)&((SAWON*)0)->list1);
위 코드는 우리가 구하고자 하는 list1 size를 상대 주소를 통해서 접근을 하는 방식이다. 상대적 주소는 맨 처음이 0이니 0을 SAWON의 pointer로 잡고 그 값을 통해 list1 멤버 구조체로 역참조한다. &(SAWON*)0->list1
사실 0번지는 말도 안되는 주소라서 실제 해당 멤버로 접근하게 되면 문제가 되지만, 우리는 단지 주소로 접근하기 때문에 문제가 안된다.&(SAWON*)0->list1 = 24
위 값은 포인터 값이기 때문에 (next+prev) 8 bytes 단위다. 따라서 연산에 사용하기 위해선 address와 직접적인 연관이 있는 long 타입으로 변환이 필요하다.
그리고 음수는 나오지 말아야하기 때문에 unsigned long을 사용해야한다.
Macro화
이런 코드를 매번 작성하기 번거로우니 macro를 작성해서 사용하면 유용하다.
#define container_of(ptr, type, member) \ (type*) ((char *)ptr - (unsigned long)&((SAWON*)0)->member); s = container_of(temp, SAWON, list1);