megaOS - 3. Double linked list

megaOS는 자료 관리를 위하여 double linked list를 사용한다.  megaOS의 동작을 이해하기 위해서는 반드시 double linked list가 어떻게 동작되는지 정확히 알고 있어야 한다.

따라서 이번 글에서는 본격적으로 megaOS 코드를 구현하기 전에 앞서서 megaOS에서 사용하는 double linked list에 대한 설명을 하기로 하겠다.

os.h 파일에 다음과 같은 구조체를 선언한다.

/*------------------------------------------------------------------------------ * Base types and Macros *----------------------------------------------------------------------------*/ typedef uint8_t bool; enum { false, true }; /*------------------------------------------------------------------------------ * Double linked list *----------------------------------------------------------------------------*/ struct link { struct link *next, *prev; void *item; struct list *list; }; struct list { struct link link; uint8_t count; };

4~9는 list 구조와는 관계없는 내용이지만, list API중에 return 값으로 boolean 값을 넘겨주는것이 있어서 미리 선언한것이다.

Double linked list를 만들기 위해서 두개의 구조체를 정의하였다.  하나는 link 구조체이고, 또 다른 하나는 list 구조체이다.

Double linked list가 실제로 적용된 모습을 그림으로 표현하면 다음과 같은 모양이 된다.

다소 복잡하게 보이겠지만 색깔별 화살표가 어디를 가리키고 있는지를 잘 보면 그렇게 어려운 내용은 아니다.  위의 그림은 n개의 link가 list header에 포인터로 연결되어 있는것을 표현한 것이다.  이렇게 복잡한 연결을 시키는 목적은 궁극적으로 각 link 구조체에 있는 item 포인터가 가리키고 있는 초록색 박스로 표시된 item 들을 효과적으로 관리하기 위한 것이다.

그림의 가장 왼쪽에 보이는 것이 list 구조체의 모습이다.  link 구조체에 count 필드가 하나더 추가되어 있는 것을 알 수 있다.

맨 처음에는 list만 존재하고 있게 된다.  이 상태에서 link 0이 추가되면 list의 next 포인터는 새로 추가된 link 0을 가리키게 되고, link 0의 prev는 list를 가리키게 된다.  link 0은 어떤 list에 연결되어 있는지 기억하고 있어야 한다.  물론, link 0은 관리하고자 하는 item 0의 주소를 가지고 있는 상태이다.

이 상태에서 새로운 link 1이 추가되면, link 1은 link 0 뒤에 연결되게 된다.  계속해서 link 들이 추가 되면 가장 끝에 놓이게 된다.

만약 list에 연결된 link에서 자료 하나를 사용하게 되면 link 0이 선택되어 item 0을 이용하게 되고, link 0은 이제 더 이상 list에 연결될 필요가 없게 되므로 list에서 제거가 된다.  그렇게 되면 link 1이 이제는 list의 첫번째 link가 된다.

따라서 새로 추가되는 link는 항상 list의 맨 뒤에 연결되고, list에서 link를 하나 뽑을 때는 가장 앞에 있는 link를 뽑아 낸다는 것을 알 수 있다.  이렇듯 먼저 들어온 것을 먼저 사용하는것을 FIFO(First In, First Out) 혹은 Queue 라고 한다.  이와 대비대는 방법은 LIFO(Last In, First Out) 혹은 Stack이라는 것이 있다.  가장 나중에 들어온 순서대로 먼저 빼가는 방법이다.

link가 list에 추가되고, 제거 될 때마다 list의 count값이 변경되게 된다.  그러므로 list의 count 값만 참조하게 되면 현재 list에는 몇개의 item 들이 연결되어 있는지 알 수 있게 된다.

위의 그림에서 빨간색 화살표들은 모두 다음에 오는 link의 주소를 가리키게 된다.  파란색 화살표는 반대로 앞에 놓여 있는 link의 주소를 가리키고 있다.  초록색 화살표는  item들의 주소를 가리킨다.  보라색 화살표는 모두 list를 가리키고 있는 것을 알수 있다.

Double linked list가 어떻게 동작되는지 감을 잡을거라 생각하고 list API들을 하나씩 설명해보도록 하겠다.  만약 위의 그림만으로 double linked list의 동작 원리가 제대로 이해가 되지 않더라도 API 코드를 분석하면 확실하게 이해가 될 것이다.

list.c 파일에 필요한 API들을 하나씩 추가해 보도록 하겠다.

struct list *list_init(struct list *list) { list->link.next = &list->link; list->link.prev = &list->link; list->link.item = NULL; list->link.list = NULL; list->count = 0; return list; }

첫번째로 만들 API는 list_init() 이다.

list_init()은 list 구조체로 선언된 변수의 포인터를 입력으로 받아서 구조체 필드들을 초기화 시키는 동작을 수행한다.

list의 next와 prev 포인터는 list 자신을 가리킨다.  link가 추가되면 next와 prev포인터를 새로 들어온 link 주소를 가리키게 된다.

list는 item을 관리하지 않으므로 NULL값으로 초기화 하고, list 필드도 사용하지 않으므로 NULL로 초기화 한다.

list에 아직 link가 연결되어 있지 않으므로 count값을 0으로 초기화 한다.

초기화가 끝나면 초기화가 완료된 list 주소값을 돌려준다.

list_init()의 예제 코드는 다음과 같다.

struct list dsr_list; list_init(&dsr_list);

struct link *link_init(void *item, struct link *link) { link->next = NULL; link->prev = NULL; link->list = NULL; link->item = item; return link; }

link를 초기화하는 link_init() 함수이다.  함수의 입력 인자로 item이라는 포인터와 초기화하고자 하는 link 구조체 변수에 대한 포인터 주소이다.

위의 그림에서 볼 수 있듯이 링크는 관리하고자 하는 대상인 item을 가리키고 있다.  link_init()에 들어오는 item 포인터를 기록하는 동작을 수행하고, 나머지 필드들은 모두 NULL 값으로 초기화 한다.

struct os_interrupt *intr = os_alloc(sizeof(struct os_interrupt)); link_init(intr, &intr->dsr_link);

link_init()의 사용 예제는 위와 같다.

void list_put(struct list *list, struct link *link) { if (link->list) return; link->next = &list->link; link->prev = list->link.prev; link->list = list; list->link.prev->next = link; list->link.prev = link; list->count++; }

link를 list에 추가하기 위하여 list_put()을 사용한다.  이 함수의 인자로는 list와 link이다.

3번줄은 link가 현재 다른 list에 등록되어 있는 경우라면 새로운 list에 추가 하지 않도록 하는것이다.  link는 반드시 하나의 list에만 등록될 수 있으므로 이러한 오동작 방지 코드를 추가해 놓는 것이다.

6~8까지는 link의 필드를 업데이트하는 코드이다.  link의 next는 반드시 list가 된다.  그 이유는 새로 추가하는 link는 그 list의 맨 마지막 link가 될 것이므로 마지막 link의 next는 list를 가리킬 수 밖에 없다.  추가되는 link의 앞은 link가 추가되기전 list의 맨 마지막 link가 될 것이므로 list->prev가 될 것이다.  8번줄은 추가되는 link가 이제 list에 속해 있음을 기록해 둔다.

10~12는 list를 업데이트 하는 코드이다.

10번줄은 새로 추가되는 link가 list의 맨 마지막에 위치하여야 하므로 기존에 있던 맨 마지막 link의 next를 추가되는 link를 가리키도록 하는것이다.

11번줄은 list의 prev를 새로추가되는 link를 가리키도록 한다. 

12번줄은 link가 하나 추가 되었으므로 list의 count 값을 하나 증가 시키는 것이다.

list_put의 사용은 다음과 같이 하면 된다.

list_put(&dsr_list, &intr->dsr_link);

void list_put_first(list_t *list, link_t *link) { if (link->list) return; link->next = list->link.next; link->prev = &list->link; link->list = list; list->link.next->prev = link; list->link.next = link; list->count++; }

Double linked list는 기본적으로 FIFO 구조이므로 새로 추가되는 link는 list의 가장 끝에 연결되어야 하지만, 때로는 가장 첫번째 위치에 연결 시킬 필요가 있게 된다.

이러할 때에 사용하는 것이 list_put_first()이다.  사용방법과 동작 원리는 list_put과 비슷하고 단지 놓이는 위치만 다르기 때문에 코드는 비슷한 모습을 보인다.  list_put과 list_put_first가 어떻게 다른지 꼼꼼히 비교해 보기 바란다.

void *list_get(struct list *list) { void *item = NULL; if (list->count) { struct link *link = list->link.next; item = link->item; list->link.next = link->next; link->next->prev = &list->link; list->count--; link->list = NULL; } return item; }

list에서 첫번째 link에 있는 item을 가지고 올때 사용하는 함수가 list_get()이다.  인자로는 list를 사용한다.

5번줄은 list의 count값이 0인 경우에는 연결된 link가 없다는 뜻이므로 NULL을 return 하도록한다.  count값이 0이 아니라면 적어도 하나 이상의 link가 연결되어 있다는 뜻이므로, 첫번째 link를 찾을 수 있게 된다.

7번줄에서와 같이 첫번째 link는 list의 next가 가리키는 곳에서 찾을수 있다.

8번줄은 찾은 첫번째 link가 기록하고 있는 item이 있는 주소를 가지고 오는 코드이다.

이제 첫번째 link는 더이상 쓸모가 없게 되었으므로 list의 연결에서 제거해야 한다.

9번줄은 list의 next를 link의 next가 가리키고 있는곳을 가리키게 되는 것이다.

10번줄은 link의 next, 즉, 2번째에 있던 link의 prev를 list를 가리키게 한다. 이 말은 이제 두번째에 있던 link가 첫번째 link가 됨을 의미하는 것이다.

11번줄은 이제 list에서 link하나를 제거하였으므로 count값을 하나 감소하는 코드이다.

12번줄은 list에서 빠진 link는 이제 더이상 어느 list에도 속하지 않게 되었으므로 list 포인터를 NULL로 초기화 시켜 어디에도 속해 있지 않음을 알려주게 된다.

15번 줄은 첫번째였던 link에 있던 item 주소를 리턴해 주는 코드이다.

struct os_interrupt *intr = list_get(&dsr_list);

list_get()의 사용 방법은 위와 같다.

void *list_rotate(struct list *list) { if (list->count == 0) return NULL; if (list->count == 1) return list->link.next->item; struct link *link = list->link.next; list->link.next = link->next; link->next->prev = &list->link; link->next = &list->link; link->prev = list->link.prev; list->link.prev->next = link; list->link.prev = link; return list->link.next->item; }

list_rotate()는 list에 있던 첫번째 link를 제일 끝으로 옮기는 기능을 수행하고, 그런다음 새로 첫번째로 위치하게된 link가 가지고 있는 item 주소를 return 해주는 코드이다.

3번줄은 만약 list의 count가 0인 경우, 즉, link가 하나도 연결되어 있지 않은 경우에는 NULL을 return하고 함수를 끝내게 되는 코드이다.

6번줄은 count의 값이 1인 경우, 즉, 하나의 link만 연결되어 있는 경우 굳이 rotate를 시킬 필요가 없으므로 그냥 link의 item값을 return 하는 코드이다.

9번줄부터는 최소 두개 이상의 link가 연결되어 있는 경우 실행되는 코드이다.

list_rotate()는 list_get()과 list_put() 두개를 연달아 호출하는 코드와 동일한 기능을 수행하므로 이들 두개의 코드와 비교하여 분석해 보기 바란다.

void *list_peek(struct list *list) { return list->link.next->item; }

list_peek()은 단순히 첫번째 link의 item 주소를 가지고 오는 기능만을 수행한다.  list_get()의 경우 link를 list에서 삭제하는 동작을 수행하지만, list_peek()은 link를 유지 시켜준다.

uint8_t list_count(struct list *list) { return list->count; }

list_count()는 현재 연결된 link의 개수를 조회하는 함수이다.

bool list_empty(struct list *list) { return !(list->count); }

list_empty()는 list에 link가 연결되어 있는지 없는지 확인하기 위한 함수이다.  Empty를 체크하는 함수이므로 count가 0인경우 True를 return 하고, count가 0이 아니면, 즉, 하나 이상의 link가 연결되어 있으면 False를 return 하도록 되어 있다.

지금까지는 list와 관련된 API들을 설명하였고, 다음 순서로는 link와 관련된 API들을 설명하도록 하겠다.

void *link_insert(struct link *old_link, struct link *new_link) { if (old_link->list == NULL || new_link->list) return NULL; new_link->next = old_link; new_link->prev = old_link->prev; new_link->list = old_link->list; old_link->prev->next = new_link; old_link->prev = new_link; old_link->list->count++; return new_link->item; }

link_insert()는 인자로 들어오는 new_link를 old_link 앞에 연결 시켜주고 new_link의 item 포인터를 return 값으로 넘겨주는 함수이다.

3번줄은 old_list가 list 포인터가 NULL은 아닌지, 그리고 new_link가 현재 어떤 list에 연결되어 있는 상태는 아닌지 검사하는 코드이다.

6~8은 new_link의 정보를 업데이트 해주는 코드이다.

10번줄은 old_link의 앞에 있는 link의 next를 new_link를 가리키도록 수정하는 코드이다.

11번줄은 이제 old_link의 prev가 new_link임을 알려주는 코드이다.

13번줄은 list에 new_link가 추가 되었으므로 count값을 하나 증가 시켜준다.

15번 줄은 모든 link 정보 업데이트를 수행한 후 new_link가 가지고 있는 item을 찾아서 return 해준다.

void *link_remove(struct link *link) { void *item = NULL; if (link && link->list) { link->prev->next = link->next; link->next->prev = link->prev; link->list->count--; link->list = NULL; item = link->item; } return item; }

link_remove()는 인자로 들어온 link를 list에서 제거하는 함수이다.

이 함수의 동작 원리는 앞에 나온 설명들을 참고하여 직접 분석해 보기 바란다.

void *link_prev(struct link *link) { return link->prev->item; } void *link_next(struct link *link) { return link->next->item; }

link_prev()와 link_next()는 인자로 들어온 link를 기준으로 앞과 뒤에 연결된 link의 item 포인터값을 return 해주는 함수들이다.

이로써 megaOS에서 사용하게될 double linked list 함수들을 모두 만들어 보았다.

시작 부분에서도 얘기하였지만, megaOS를 이해하기 위해서는 반드시 double linked list가 어떻게 동작되는지 반드시 이해하고 넘어가야 한다.

list.c

os.h

심화 과정 목차