linux kernel에서 쓰이는 자료구조.(double linked list and tree)

프로그래밍/C 2013. 4. 19. 00:13

linux kernel에서 쓰이는 자료구조.(double linked list and tree)

회사에서 C언어와 자료구조에 대한 강의를 보내주게 되어서 듣게 되었는데,

강의 내용이 기본적인 내용들이라 블로깅을 정리하는 시간을 가져 보았습니다.ㅎㅎ

그렇다구 수업시간과 전혀 상관없는 딴짓은 아니구요^^;

수업과 상관있는 실제로 쓰이고 있는 자료구조가 오늘의 주제 입니다.

평소에 후배들이 저에게 질문하는 것이 있는데,

"과연 지금 학교에서 배우고 있는 것들이 현업에서 어떻게 쓰이는지 모르겠다.." 라는 것 입니다.

학교에서 학부생때 배우는 과정들은 실제로 현업에서 아주 중요한 기본(Base)가 된다는 것임을 알려드리고 싶습니다.

제가 아직 회사에서도 신입이기에 후배들에게 현업이 이렇다 저렇다라고는 감히(?) 말하기 애매하기에

저의 주관이 아닌 linux kernel code를 빌려서 이야기 하도록 하겠습니다.

아래는 linux kernel의 최신버전인 3.3의 Source중 일부 입니다.

리눅스 커널 최신 소스는 www.kernel.org 에서 받을 수 있으며 최근에 들어 빠른 속도로 stable 버전이 올라오고 있죠.

정말 오픈소스의 위력을 잘 느끼고 있습니다. ㅎㅎㅎ

이렇게 리눅스 커널 소스는 모든 사람들에게 공개되어 있으므로 공부하기에 가장 좋은 자료가 아닐까 합니다.

그럼 오늘의 주제는 실제로 쓰이고 있는 자료구조이기에 수 많은 커널 소스중에서 일부를 보도록 하겠습니다.

아래는 linux-3.3.3\linux-3.3.3\include\linux\list.h 의 내용입니다.

#ifndef _LINUX_LIST_H
#define _LINUX_LIST_H
 
#include <LINUX types.h>
#include <LINUX stddef.h>
#include <LINUX poison.h>
#include <LINUX const.h>
 
/*
 * Simple doubly linked list implementation.
 *
 * Some of the internal functions ("__xxx") are useful when
 * manipulating whole lists rather than single entries, as
 * sometimes we already know the next/prev entries and we can
 * generate better code by using them directly rather than
 * using the generic single-entry routines.
 */
 
#define LIST_HEAD_INIT(name) { &(name), &(name) }
 
#define LIST_HEAD(name) \
    struct list_head name = LIST_HEAD_INIT(name)
 
static inline void INIT_LIST_HEAD(struct list_head *list)
{
    list->next = list;
    list->prev = list;
}
 
/*
 * Insert a new entry between two known consecutive entries.
 *
 * This is only for internal list manipulation where we know
 * the prev/next entries already!
 */
#ifndef CONFIG_DEBUG_LIST
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;
}
#else
extern void __list_add(struct list_head *new,
                  struct list_head *prev,
                  struct list_head *next);
#endif
 
/**
 * 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);
}
 
/*
 * Delete a list entry by making the prev/next entries
 * point to each other.
 *
 * This is only for internal list manipulation where we know
 * the prev/next entries already!
 */
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_entry(struct list_head *entry)
{
    __list_del(entry->prev, entry->next);
}
 
static inline void list_del(struct list_head *entry)
{
    __list_del(entry->prev, entry->next);
    entry->next = LIST_POISON1;
    entry->prev = LIST_POISON2;
}
#else
extern void __list_del_entry(struct list_head *entry);
extern void list_del(struct list_head *entry);
#endif
 
/**
 * list_replace - replace old entry by new one
 * @old : the element to be replaced
 * @new : the new element to insert
 *
 * If @old was empty, it will be overwritten.
 */
static inline void list_replace(struct list_head *old,
                struct list_head *new)
{
    new->next = old->next;
    new->next->prev = new;
    new->prev = old->prev;
    new->prev->next = new;
}
 
static inline void list_replace_init(struct list_head *old,
                    struct list_head *new)
{
    list_replace(old, new);
    INIT_LIST_HEAD(old);
}
 
/**
 * list_del_init - deletes entry from list and reinitialize it.
 * @entry: the element to delete from the list.
 */
static inline void list_del_init(struct list_head *entry)
{
    __list_del_entry(entry);
    INIT_LIST_HEAD(entry);
}
 
/**
 * list_move - delete from one list and add as another's head
 * @list: the entry to move
 * @head: the head that will precede our entry
 */
static inline void list_move(struct list_head *list, struct list_head *head)
{
    __list_del_entry(list);
    list_add(list, head);
}
 
/**
 * list_move_tail - delete from one list and add as another's tail
 * @list: the entry to move
 * @head: the head that will follow our entry
 */
static inline void list_move_tail(struct list_head *list,
                  struct list_head *head)
{
    __list_del_entry(list);
    list_add_tail(list, head);
}
 
/**
 * list_is_last - tests whether @list is the last entry in list @head
 * @list: the entry to test
 * @head: the head of the list
 */
static inline int list_is_last(const struct list_head *list,
                const struct list_head *head)
{
    return list->next == head;
}
 
/**
 * list_empty - tests whether a list is empty
 * @head: the list to test.
 */
static inline int list_empty(const struct list_head *head)
{
    return head->next == head;
}
 
/**
 * list_empty_careful - tests whether a list is empty and not being modified
 * @head: the list to test
 *
 * Description:
 * tests whether a list is empty _and_ checks that no other CPU might be
 * in the process of modifying either member (next or prev)
 *
 * NOTE: using list_empty_careful() without synchronization
 * can only be safe if the only activity that can happen
 * to the list entry is list_del_init(). Eg. it cannot be used
 * if another CPU could re-list_add() it.
 */
static inline int list_empty_careful(const struct list_head *head)
{
    struct list_head *next = head->next;
    return (next == head) && (next == head->prev);
}
 
/**
 * list_rotate_left - rotate the list to the left
 * @head: the head of the list
 */
static inline void list_rotate_left(struct list_head *head)
{
    struct list_head *first;
 
    if (!list_empty(head)) {
        first = head->next;
        list_move_tail(first, head);
    }
}
 
/**
 * list_is_singular - tests whether a list has just one entry.
 * @head: the list to test.
 */
static inline int list_is_singular(const struct list_head *head)
{
    return !list_empty(head) && (head->next == head->prev);
}
 
static inline void __list_cut_position(struct list_head *list,
        struct list_head *head, struct list_head *entry)
{
    struct list_head *new_first = entry->next;
    list->next = head->next;
    list->next->prev = list;
    list->prev = entry;
    entry->next = list;
    head->next = new_first;
    new_first->prev = head;
}
 
/**
 * list_cut_position - cut a list into two
 * @list: a new list to add all removed entries
 * @head: a list with entries
 * @entry: an entry within head, could be the head itself
 *  and if so we won't cut the list
 *
 * This helper moves the initial part of @head, up to and
 * including @entry, from @head to @list. You should
 * pass on @entry an element you know is on @head. @list
 * should be an empty list or a list you do not care about
 * losing its data.
 *
 */
static inline void list_cut_position(struct list_head *list,
        struct list_head *head, struct list_head *entry)
{
    if (list_empty(head))
        return;
    if (list_is_singular(head) &&
        (head->next != entry && head != entry))
        return;
    if (entry == head)
        INIT_LIST_HEAD(list);
    else
        __list_cut_position(list, head, entry);
}
 
static inline void __list_splice(const struct list_head *list,
                 struct list_head *prev,
                 struct list_head *next)
{
    struct list_head *first = list->next;
    struct list_head *last = list->prev;
 
    first->prev = prev;
    prev->next = first;
 
    last->next = next;
    next->prev = last;
}
 
/**
 * list_splice - join two lists, this is designed for stacks
 * @list: the new list to add.
 * @head: the place to add it in the first list.
 */
static inline void list_splice(const struct list_head *list,
                struct list_head *head)
{
    if (!list_empty(list))
        __list_splice(list, head, head->next);
}
 
/**
 * list_splice_tail - join two lists, each list being a queue
 * @list: the new list to add.
 * @head: the place to add it in the first list.
 */
static inline void list_splice_tail(struct list_head *list,
                struct list_head *head)
{
    if (!list_empty(list))
        __list_splice(list, head->prev, head);
}
 
/**
 * list_splice_init - join two lists and reinitialise the emptied list.
 * @list: the new list to add.
 * @head: the place to add it in the first list.
 *
 * The list at @list is reinitialised
 */
static inline void list_splice_init(struct list_head *list,
                    struct list_head *head)
{
    if (!list_empty(list)) {
        __list_splice(list, head, head->next);
        INIT_LIST_HEAD(list);
    }
}
 
/**
 * list_splice_tail_init - join two lists and reinitialise the emptied list
 * @list: the new list to add.
 * @head: the place to add it in the first list.
 *
 * Each of the lists is a queue.
 * The list at @list is reinitialised
 */
static inline void list_splice_tail_init(struct list_head *list,
                     struct list_head *head)
{
    if (!list_empty(list)) {
        __list_splice(list, head->prev, head);
        INIT_LIST_HEAD(list);
    }
}
 
/**
 * list_entry - get the struct for this entry
 * @ptr:    the &struct list_head pointer.
 * @type:   the type of the struct this is embedded in.
 * @member: the name of the list_struct within the struct.
 */
#define list_entry(ptr, type, member) \
    container_of(ptr, type, member)
 
/**
 * list_first_entry - get the first element from a list
 * @ptr:    the list head to take the element from.
 * @type:   the type of the struct this is embedded in.
 * @member: the name of the list_struct within the struct.
 *
 * Note, that list is expected to be not empty.
 */
#define list_first_entry(ptr, type, member) \
    list_entry((ptr)->next, type, member)
 
/**
 * list_for_each    -   iterate over a list
 * @pos:    the &struct list_head to use as a loop cursor.
 * @head:   the head for your list.
 */
#define list_for_each(pos, head) \
    for (pos = (head)->next; pos != (head); pos = pos->next)
 
/**
 * __list_for_each  -   iterate over a list
 * @pos:    the &struct list_head to use as a loop cursor.
 * @head:   the head for your list.
 *
 * This variant doesn't differ from list_for_each() any more.
 * We don't do prefetching in either case.
 */
#define __list_for_each(pos, head) \
    for (pos = (head)->next; pos != (head); pos = pos->next)
 
/**
 * list_for_each_prev   -   iterate over a list backwards
 * @pos:    the &struct list_head to use as a loop cursor.
 * @head:   the head for your list.
 */
#define list_for_each_prev(pos, head) \
    for (pos = (head)->prev; pos != (head); pos = pos->prev)
 
/**
 * list_for_each_safe - iterate over a list safe against removal of list entry
 * @pos:    the &struct list_head to use as a loop cursor.
 * @n:      another &struct list_head to use as temporary storage
 * @head:   the head for your list.
 */
#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_prev_safe - iterate over a list backwards safe against removal of list entry
 * @pos:    the &struct list_head to use as a loop cursor.
 * @n:      another &struct list_head to use as temporary storage
 * @head:   the head for your list.
 */
#define list_for_each_prev_safe(pos, n, head) \
    for (pos = (head)->prev, n = pos->prev; \
         pos != (head); \
         pos = n, n = pos->prev)
 
/**
 * list_for_each_entry  -   iterate over list of given type
 * @pos:    the type * to use as a loop cursor.
 * @head:   the head for your list.
 * @member: the name of the list_struct within the struct.
 */
#define list_for_each_entry(pos, head, member)              \
    for (pos = list_entry((head)->next, typeof(*pos), member);   \
         &pos->member != (head);     \
         pos = list_entry(pos->member.next, typeof(*pos), member))
 
/**
 * list_for_each_entry_reverse - iterate backwards over list of given type.
 * @pos:    the type * to use as a loop cursor.
 * @head:   the head for your list.
 * @member: the name of the list_struct within the struct.
 */
#define list_for_each_entry_reverse(pos, head, member)          \
    for (pos = list_entry((head)->prev, typeof(*pos), member);   \
         &pos->member != (head);     \
         pos = list_entry(pos->member.prev, typeof(*pos), member))
 
/**
 * list_prepare_entry - prepare a pos entry for use in list_for_each_entry_continue()
 * @pos:    the type * to use as a start point
 * @head:   the head of the list
 * @member: the name of the list_struct within the struct.
 *
 * Prepares a pos entry for use as a start point in list_for_each_entry_continue().
 */
#define list_prepare_entry(pos, head, member) \
    ((pos) ? : list_entry(head, typeof(*pos), member))
 
/**
 * list_for_each_entry_continue - continue iteration over list of given type
 * @pos:    the type * to use as a loop cursor.
 * @head:   the head for your list.
 * @member: the name of the list_struct within the struct.
 *
 * Continue to iterate over list of given type, continuing after
 * the current position.
 */
#define list_for_each_entry_continue(pos, head, member)         \
    for (pos = list_entry(pos->member.next, typeof(*pos), member);   \
         &pos->member != (head); \
         pos = list_entry(pos->member.next, typeof(*pos), member))
 
/**
 * list_for_each_entry_continue_reverse - iterate backwards from the given point
 * @pos:    the type * to use as a loop cursor.
 * @head:   the head for your list.
 * @member: the name of the list_struct within the struct.
 *
 * Start to iterate over list of given type backwards, continuing after
 * the current position.
 */
#define list_for_each_entry_continue_reverse(pos, head, member)     \
    for (pos = list_entry(pos->member.prev, typeof(*pos), member);   \
         &pos->member != (head); \
         pos = list_entry(pos->member.prev, typeof(*pos), member))
 
/**
 * list_for_each_entry_from - iterate over list of given type from the current point
 * @pos:    the type * to use as a loop cursor.
 * @head:   the head for your list.
 * @member: the name of the list_struct within the struct.
 *
 * Iterate over list of given type, continuing from current position.
 */
#define list_for_each_entry_from(pos, head, member)             \
    for (; &pos->member != (head);   \
         pos = list_entry(pos->member.next, typeof(*pos), member))
 
/**
 * 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_continue - continue list iteration safe against removal
 * @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 over list of given type, continuing after current point,
 * safe against removal of list entry.
 */
#define list_for_each_entry_safe_continue(pos, n, head, member)         \
    for (pos = list_entry(pos->member.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_from - iterate over list from current point safe against removal
 * @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 over list of given type from current point, safe against
 * removal of list entry.
 */
#define list_for_each_entry_safe_from(pos, n, head, member)             \
    for (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 - iterate backwards over list safe against removal
 * @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))
 
/**
 * list_safe_reset_next - reset a stale list_for_each_entry_safe loop
 * @pos:    the loop cursor used in the list_for_each_entry_safe loop
 * @n:      temporary storage used in list_for_each_entry_safe
 * @member: the name of the list_struct within the struct.
 *
 * list_safe_reset_next is not safe to use in general if the list may be
 * modified concurrently (eg. the lock is dropped in the loop body). An
 * exception to this is if the cursor element (pos) is pinned in the list,
 * and list_safe_reset_next is called after re-taking the lock and before
 * completing the current iteration of the loop body.
 */
#define list_safe_reset_next(pos, n, member)                \
    n = list_entry(pos->member.next, typeof(*pos), member)
 
/*
 * Double linked lists with a single pointer list head.
 * Mostly useful for hash tables where the two pointer list head is
 * too wasteful.
 * You lose the ability to access the tail in O(1).
 */
 
#define HLIST_HEAD_INIT { .first = NULL }
#define HLIST_HEAD(name) struct hlist_head name = {  .first = NULL }
#define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
static inline void INIT_HLIST_NODE(struct hlist_node *h)
{
    h->next = NULL;
    h->pprev = NULL;
}
 
static inline int hlist_unhashed(const struct hlist_node *h)
{
    return !h->pprev;
}
 
static inline int hlist_empty(const struct hlist_head *h)
{
    return !h->first;
}
 
static inline void __hlist_del(struct hlist_node *n)
{
    struct hlist_node *next = n->next;
    struct hlist_node **pprev = n->pprev;
    *pprev = next;
    if (next)
        next->pprev = pprev;
}
 
static inline void hlist_del(struct hlist_node *n)
{
    __hlist_del(n);
    n->next = LIST_POISON1;
    n->pprev = LIST_POISON2;
}
 
static inline void hlist_del_init(struct hlist_node *n)
{
    if (!hlist_unhashed(n)) {
        __hlist_del(n);
        INIT_HLIST_NODE(n);
    }
}
 
static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
{
    struct hlist_node *first = h->first;
    n->next = first;
    if (first)
        first->pprev = &n->next;
    h->first = n;
    n->pprev = &h->first;
}
 
/* next must be != NULL */
static inline void hlist_add_before(struct hlist_node *n,
                    struct hlist_node *next)
{
    n->pprev = next->pprev;
    n->next = next;
    next->pprev = &n->next;
    *(n->pprev) = n;
}
 
static inline void hlist_add_after(struct hlist_node *n,
                    struct hlist_node *next)
{
    next->next = n->next;
    n->next = next;
    next->pprev = &n->next;
 
    if(next->next)
        next->next->pprev  = &next->next;
}
 
/* after that we'll appear to be on some hlist and hlist_del will work */
static inline void hlist_add_fake(struct hlist_node *n)
{
    n->pprev = &n->next;
}
 
/*
 * Move a list from one list head to another. Fixup the pprev
 * reference of the first entry if it exists.
 */
static inline void hlist_move_list(struct hlist_head *old,
                   struct hlist_head *new)
{
    new->first = old->first;
    if (new->first)
        new->first->pprev = &new->first;
    old->first = NULL;
}
 
#define hlist_entry(ptr, type, member) container_of(ptr,type,member)
 
#define hlist_for_each(pos, head) \
    for (pos = (head)->first; pos ; pos = pos->next)
 
#define hlist_for_each_safe(pos, n, head) \
    for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
         pos = n)
 
/**
 * hlist_for_each_entry - iterate over list of given type
 * @tpos:   the type * to use as a loop cursor.
 * @pos:    the &struct hlist_node to use as a loop cursor.
 * @head:   the head for your list.
 * @member: the name of the hlist_node within the struct.
 */
#define hlist_for_each_entry(tpos, pos, head, member)            \
    for (pos = (head)->first;                     \
         pos &&                          \
        ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
         pos = pos->next)
 
/**
 * hlist_for_each_entry_continue - iterate over a hlist continuing after current point
 * @tpos:   the type * to use as a loop cursor.
 * @pos:    the &struct hlist_node to use as a loop cursor.
 * @member: the name of the hlist_node within the struct.
 */
#define hlist_for_each_entry_continue(tpos, pos, member)         \
    for (pos = (pos)->next;                       \
         pos &&                          \
        ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
         pos = pos->next)
 
/**
 * hlist_for_each_entry_from - iterate over a hlist continuing from current point
 * @tpos:   the type * to use as a loop cursor.
 * @pos:    the &struct hlist_node to use as a loop cursor.
 * @member: the name of the hlist_node within the struct.
 */
#define hlist_for_each_entry_from(tpos, pos, member)             \
    for (; pos &&                            \
        ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
         pos = pos->next)
 
/**
 * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
 * @tpos:   the type * to use as a loop cursor.
 * @pos:    the &struct hlist_node to use as a loop cursor.
 * @n:      another &struct hlist_node to use as temporary storage
 * @head:   the head for your list.
 * @member: the name of the hlist_node within the struct.
 */
#define hlist_for_each_entry_safe(tpos, pos, n, head, member)        \
    for (pos = (head)->first;                     \
         pos && ({ n = pos->next; 1; }) &&                \
        ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
         pos = n)

허걱... 무려 721라인이나 되는군요..@_@;

사실 너무나 많은 소스파일 때문에 겁부터 먹으셨는지 모르겠습니다..

저도 다 분석하려 생각하니 눈앞이 깜깜해지는 군요..ㅎㄷㄷ

하지만 모든 코드를 분석하는 것이 아니라 우리가 알고 있는 자료구조가 어떻게 쓰였는가에 대해 알아볼 참이기 때문에 핵심만 간단하게 간추려서 보도록 하겠습니다.

우선 각 함수들의 이름과 목적을 간추려 보도록 하죠.

간단하게 구분하기 위해서 매크로함수는 붉은색으로 static inline함수는 원형으로 표시하도록 하겠습니다.

※ static inline은 매크로함수로 컴파일 되기 전 시점에 함수를 호출하는 함수가 자동으로 코드로 치환되어 집니다. 그러므로 일반함수의 메커니즘에 비해 상대적으로 빠르다고 할 수 있습니다. 일반함수는 함수의 프로토타입만을 기억하고 있다가 함수 호출시 메모리를 참조하는 방식입니다.

LIST_HEAD_INIT(name)

LIST_HEAD(name)

static inline void INIT_LIST_HEAD(struct list_head *list)

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)

static inline void __list_del(struct list_head * prev, struct list_head * next)

static inline void list_replace(struct list_head *old, struct list_head *new)

static inline void list_replace_init(struct list_head *old, struct list_head *new)

static inline void list_del_init(struct list_head *entry)

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)

static inline int list_is_last(const struct list_head *list, const struct list_head *head)

static inline int list_empty(const struct list_head *head)

static inline int list_empty_careful(const struct list_head *head)

static inline void list_rotate_left(struct list_head *head)

static inline int list_is_singular(const struct list_head *head)

static inline void __list_cut_position(struct list_head *list, struct list_head *head, struct list_head *entry)

static inline void list_cut_position(struct list_head *list, struct list_head *head, struct list_head *entry)

static inline void __list_splice(const struct list_head *list, struct list_head *prev, struct list_head *next)

static inline void list_splice(const struct list_head *list, struct list_head *head)

static inline void list_splice_tail(struct list_head *list, struct list_head *head)

static inline void list_splice_init(struct list_head *list, struct list_head *head)

static inline void list_splice_tail_init(struct list_head *list, struct list_head *head)

list_entry(ptr, type, member)

list_first_entry(ptr, type, member)

list_for_each(pos, head)

__list_for_each(pos, head)

list_for_each_prev(pos, head)

list_for_each_safe(pos, n, head)

list_for_each_prev_safe(pos, n, head)

list_for_each_entry(pos, head, member)

list_for_each_entry_reverse(pos, head, member)

list_prepare_entry(pos, head, member)

list_for_each_entry_continue(pos, head, member)

list_for_each_entry_continue_reverse(pos, head, member)

list_for_each_entry_from(pos, head, member)

list_for_each_entry_safe(pos, n, head, member)

list_for_each_entry_safe_continue(pos, n, head, member)

list_for_each_entry_safe_from(pos, n, head, member)

list_for_each_entry_safe_reverse(pos, n, head, member)

list_safe_reset_next(pos, n, member)

HLIST_HEAD_INIT

HLIST_HEAD(name)

INIT_HLIST_HEAD(ptr)

static inline void INIT_HLIST_NODE(struct hlist_node *h)

static inline int hlist_unhashed(const struct hlist_node *h)

static inline int hlist_empty(const struct hlist_head *h)

static inline void __hlist_del(struct hlist_node *n)

static inline void hlist_del(struct hlist_node *n)

static inline void hlist_del_init(struct hlist_node *n)

static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)

static inline void hlist_add_before(struct hlist_node *n, struct hlist_node *next)

static inline void hlist_add_after(struct hlist_node *n, struct hlist_node *next)

static inline void hlist_add_fake(struct hlist_node *n)

static inline void hlist_move_list(struct hlist_head *old, struct hlist_head *new)

hlist_entry(ptr, type, member)

hlist_for_each(pos, head)

hlist_for_each_safe(pos, n, head)

hlist_for_each_entry(tpos, pos, head, member)

hlist_for_each_entry_continue(tpos, pos, member)

hlist_for_each_entry_from(tpos, pos, member)

hlist_for_each_entry_safe(tpos, pos, n, head, member)

일단 위의 소스 중 prev와 next를 보아하니 linux_kernel에서는 이중 연결리스트가 사용되고 있음을 알 수가 있습니다.

사실 이쯤되면 이중연결리스트에 왜 이렇게 많은 코드가 쓰였을까하는 의문이 드실 수 있습니다. 만약 의문이 드신 분이 있다면 뛰어난 통찰력을 가졌다고 감히 말씀드리겠습니다.ㅎㅎ

위의 소스는 기본인 개념이 중복되는 코드가 많으며 각 특수한 목적에 맞게 자료구조를 각 상황에 알맞게 튜닝하였기에 코드가 불어난 것이죠. 잘 보시면 복잡한 위의 코드도 기본적인 뼈대는 아래와 같습니다.

코드는 linux-3.3.3\linux-3.3.3\tools\firewire\list.h를 참조하였습니다.

struct list {
    struct list *next, *prev;
};
 
static inline void
list_init(struct list *list)
{
    list->next = list;
    list->prev = list;
}
 
static inline int
list_empty(struct list *list)
{
    return list->next == list;
}
 
static inline void
list_insert(struct list *link, struct list *new_link)
{
    new_link->prev       = link->prev;
    new_link->next       = link;
    new_link->prev->next  = new_link;
    new_link->next->prev  = new_link;
}
 
static inline void
list_append(struct list *list, struct list *new_link)
{
    list_insert((struct list *)list, new_link);
}
 
static inline void
list_prepend(struct list *list, struct list *new_link)
{
    list_insert(list->next, new_link);
}
 
static inline void
list_remove(struct list *link)
{
    link->prev->next = link->next;
    link->next->prev = link->prev;
}
 
#define list_entry(link, type, member) \
    ((type *)((char *)(link)-(unsigned long)(&((type *)0)->member)))
 
#define list_head(list, type, member)       \
    list_entry((list)->next, type, member)
 
#define list_tail(list, type, member)       \
    list_entry((list)->prev, type, member)
 
#define list_next(elm, member)                  \
    list_entry((elm)->member.next, typeof(*elm), member)
 
#define list_for_each_entry(pos, list, member)          \
    for (pos = list_head(list, typeof(*pos), member);   \
         &pos->member != (list);             \
         pos = list_next(pos, member))

무언가 확~ 줄은 느낌이죠? 우리는 오늘 리눅스 커널에서 자료구조를 이해하기 위해 커널을 보는 것이니 살살 접근하도록 하겠습니다. ㅎㅎ 처음부터 빡시게하면 힘들어져요^^;

일단 위의 코드에서 나오는 이중 연결리스트에 대한 기본적인 설명은 학과과정 중 기본에 속하는 내용이므로 자세한 설명은 패스하도록 하겠습니다. 그림으로 보자면 아래와 같겠지요. 먼가 복잡하게 보일지 모르겠지만 그냥 앞과 뒤가 순차적으로 연결되어 있는 리스트라고 생각하시면 됩니다.

지금부터 위의 리눅스 커널 소스을 가지고 샘플코드를 구현하면서 설명을 할 참입니다. Step by Step으로 넘어갈테니 천천히 잘 따라오시기 바랍니다. 우선 Linked list에 대해 잘 숙지하고 계셔야 이해가 가실거라는걸 미리 말씀드립니다. 이래서 흔히 부모님이 뭐든 기본이 중요하다는 애기를 입이 닳도록 했었나 봅니다. ㅎㅎ

아무튼 아래는 마지막에 소개드린 list.h를 가지고 구현한 간단한 샘플코드 입니다.

※ 참고로 윈도우 환경에서 테스트를 하였습니다. typeof() 연산자가 visual C 컴파일시 문제가 되었는데요. 때문에 샘플에서는 C표준이 아닌 gcc에서 확장으로 지원하는 typeof() 연산자 대신 같은 의미를 가지는 임의의 구조체 타입으로 치환하였다는 것을 미리 말씀드립니다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
typedef struct list {
    struct list *next, *prev;
}NODE;
 
typedef struct star
{
    char name[10];
    int vote;
    NODE list;
}STAR;
 
static inline void
list_init(struct list *list)
{
    list->next = list;
    list->prev = list;
}
 
static inline int
list_empty(struct list *list)
{
    return list->next == list;
}
 
static inline void
list_insert(struct list *link, struct list *new_link)
{
    new_link->prev       = link->prev;
    new_link->next       = link;
    new_link->prev->next  = new_link;
    new_link->next->prev  = new_link;
}
 
static inline void
list_append(struct list *list, struct list *new_link)
{
    list_insert((struct list *)list, new_link);
}
 
static inline void
list_prepend(struct list *list, struct list *new_link)
{
    list_insert(list->next, new_link);
}
 
static inline void
list_remove(struct list *link)
{
    link->prev->next = link->next;
    link->next->prev = link->prev;
}
 
#define list_entry(link, type, member) \
    ((type *)((char *)(link)-(unsigned long)(&((type *)0)->member)))
 
#define list_head(list, type, member)       \
    list_entry((list)->next, type, member)
 
#define list_tail(list, type, member)       \
    list_entry((list)->prev, type, member)
 
#define list_next(elm, member)                  \
    list_entry((elm)->member.next, STAR, member)
 
#define list_for_each_entry(pos, list, member)\
for (pos = list_head(list, STAR, member);\
         &pos->member != (list);\
         pos = list_next(pos, member))
 
 
void display(NODE *head)
{
    STAR *p;
    system("cls");
    printf("[head]<->");
     
    list_for_each_entry( p, head, list )
    {       
        printf("[%s,%d]<->", p->name, p->vote );
    }
    getchar();
}
 
int main(void)
{   
    int i;
    NODE head;
 
    // 리스트 헤드 초기화
    list_init(&head);
         
    char *p[] = {"지나","신민아","아이유","현아","이민정"};
 
    STAR *temp;
     
    display(&head);
 
    for(i=0; i<5; i++ )
    {
        temp = (STAR*)malloc( sizeof(STAR) );
        strcpy( temp->name, p[i]);
        temp->vote = (i+1)*10;
 
        list_append( &head, &temp->list );
        display(&head);
    }
 
    return 0;
}
<p></p>

일단 실행부터 시켜보면 아래와 같이 엔터를 누를때마다 리스트에 연예인 이름이 추가되는 것을 볼 수 있습니다. 후후후 제가 좋아하는 연예인리스트죠.. =_=

그런데 학과시절 자료구조를 통해서만 책을 봐오신 분들은 어떻게 이 연결리스트가 어떻게 화면에 출력 될 수 있지? 하는 의구심이 들수도 있습니다. 저도 처음엔 그랬으니깐요. ㅎㅎ 함수들을 살펴보니 삽입, 삭제등의 함수는 보이지만 각 리스트들에게 접근하는 함수는 보이지가 않으니 말이죠. 대신 이상한 메크로들만 보일뿐이니, list_entry등과 같은 매크로 함수가 바로 그 것 입니다.

그럼 의문점은 잠시 뒤로하고 어떻게 리스트가 구성되었는지 부터 따라가도록 하겟습니다.

다 아시는 내용이겠지만 main함수에서는 리스트의 헤드를 초기화하고 비어있는 리스트를 화면에 디스플레이 해 준 다음, for문에서 리스트에 5번의 삽입과 화면에 출력이 수행됩니다. 삽입 과정을 그림으로 표현하자면 아래와 같습니다.

① list_init(&head); // 헤더 초기화

② temp = (STAR*)malloc( sizeof(STAR) );
strcpy( temp->name, p[i]);
temp->vote = (i+1)*10;

list_append( &head, &temp->list ); // 리스트에 new node 삽입

③ temp = (STAR*)malloc( sizeof(STAR) );
strcpy( temp->name, p[i]);
temp->vote = (i+1)*10;

list_append( &head, &temp->list ); // 리스트에 new node 삽입

④ 계속 반복적인 작업의 결과 아래와 같은 리스트가 만들어집니다.

루프안에서 삽입 후 바로 출력이 일어납니다. 출력은 void display(NODE *head) 함수에서 수행되는데 여기서 주의깊게 보아야 할 부분은 아래 매크로입니다. 일단 list_for_each_entry라는 매크로 함수에 대해 설명하기에 앞서 이 매크로의 목적은 "리스트의 노드들을 한바퀴 순환하면서, 각 노드들을 참조하는 포인터를 시작주소 지점(entry)으로 옮기는 것" 입니다. 뭔소린지는 몰라도 일단 넘어가도록 하죠.ㅎㅎ

#define list_for_each_entry(pos, list, member)\
for (pos = list_head(list, STAR, member);\
&pos->member != (list);\
pos = list_next(pos, member))

흠.. 코드를 보고 있자니 이게 먼 소리인가 싶을 겁니다. 먼가 복잡해 보이지만 실제로 한줄 한줄 읽어보면 별거 없습니다.
일단 매크로 함수에서 매개변수로 쓰인 넘들이 뭐하는 넘들인지부터 살펴보죠.. 이자식들 다 주것써..ㅡㅡ

① pos : 리스트의 현재 위치를 저장할 position. 타입(Type)은 리스트의 구조체를 가리키는 포인터야함!

뇬석은 배열의 인덱스와 같은 넘이죠.

② list : next, prev를 member로 가지는 구조체의 포인터! 이 예제에서는 헤더!

③ member : 리스트의 구조체에서 pre와 next를 가지고 있는 구조체 변수명! (Type은 ②번의 'list')

위의 멤버들을 그림으로 보자면 아래와 같겠군요.

매개변수가 뭐하는 넘들인지 정체가 탄로났으니 이제 반복문을 살펴보겠습니다.

for문의 초기화 구문

pos = list_head(list, STAR, member) → 리스트의 헤더로 position을 초기화 하겠음!

for문의 조 건 구문

&pos->member != (list) → pos의 member라 함은 현재 pos가 가르키는 리스트 객체에서 next, prev를 멤버로 가지는 struct list 구조체를 말합니다. 그렇다면 pos->member의 주소와 list를 != 조건비교하는 것은 무슨 의미일까요? list는 아까 헤더(head)라는 것을 기억하셔야 할 겁니다. 즉 pos가 리스트의 객체를 한놈 한놈 가르키고 난뒤 한바퀴 다 돌아서 다시 헤더(head)로 오게 되는 상황이 오게 되겠죠. 이때 조건이 성립하지 않게 되면서 루프를 탈출하게 되는 것이죠.

for문의 증 감 구문

pos = list_next(pos, member) → 매크로 함수명 그대로 다음 리스트 객체를 가르키는 겁니다. ㅎㅎㅎ 쉽죠.

반복문을 살펴봤으니 반복문 속에 있는 매크로 함수로 더 깊게 파고들어 보겠습니다. 두두두두~

지금 살펴볼 매크로 함수는 list_head(list, STAR, member)와 list_next(pos, member) 함수 입니다. 이 두 함수의 속을 들여다 보면 똑같은 함수를 호출하고 있음을 알 수 있습니다. 바로 아래와 같은 넘이죠.

#define list_entry(link, type, member) \
((type *)((char *)(link)-(unsigned long)(&((type *)0)->member)))

헉... 이건머지? 하는 분들이 많으실 거라 생각합니다. 참으로 난감한 녀석이죠. 어떤 녀석이길래 이렇게 많은 변신(type casting)을 하는 것인지 궁금해지기 시작했습니다. 사실 이 코드의 역할은 간단합니다. 해당하는 리스트 객체의 시작주소를 얻어내는 것이죠. 기차처럼 연결된 리스트에서 각 리스트 객체의 시작주소를 안다는 것은 모든 멤버로의 접근이 가능하다는 것입니다. 사실 위에서 연예인들의 이름으로 구성된 이중연결리스트는 아까 확인한 바 있습니다.

여기서 Offset 이라는 넘이 list_entry(link, type, member) 함수의 키워드 열쇠입니다. 리스트는 다음 노드의 next, prev를 담고 있는 struct list의 시작주소(link address)를 참조하고 있습니다. 여기서 각 노드의 연예인 이름들을 출력하려면 이 주소에서 offset에 해당하는 크기의 값을 빼주어야 연예인이름을 출력할 수 있습니다. 즉 Struct star라는 노드의 시작주소로 접근해야 모든 값에 접근할 수 있는 셈인거죠. 간단하게 매크로 함수를 풀어보면 아래와 같습니다.

먼저 뺄셈 연산의 뒷부분부터 보도록 하겠습니다. 0을 (type*)로 캐스팅하여 사용자로 부터 전달받을 member의 주소를 (unsigned long)으로 캐스팅하고 있습니다. 왜 이렇게 코드를 작성했을까하는 의문이 들 수도 있는데, 이는 많은 사람들이 모든 리스트에서 공용으로 사용할 수 있는 매크로 함수로 만들어야 하기에 이와 같은 예술적인 코드가 나오게 된거라고 말씀드리겠습니다. 그럼 0에 대한 가상 구조체에 대한 의문이 풀렸다고 쳤지만, 앞의 캐스팅은 왜 해야되는지 의문이 들 수 있습니다. "(unsigned long)(&((type *)0)->member))" 는 단순히 offset으로 구하는 것이기 때문에 음수가 나올 수 없겠죠? 그렇기때문에 unsigned long으로 캐스팅하는 것 입니다.

다음은 뺄셈 연산의 앞부분을 살펴보도록 하겠습니다. link address가 int* 타입일때 임의의 숫자 4를 빼버리면 실제로 빼지는 값은 16이 빠져버립니다.(포인터 연산) 그래서 1byte씩 포인터연산을 하기 위하여 char*로 Type casting하는 것 입니다. 마지막으로 연산된 주소 값은 사용자가 정의한 Type의 Struct를 가르켜야 하기 때문에 Type*로 캐스팅하고 있습니다. 이 모든것이 start 구조체의 시작주소를 얻기 위함임을 다시한번 알려드립니다. 시작주소를 얻는다는 것은 모든 매개변수에 접근할 수 있다는 것도 잊지마세요.

※ list_entry을 언급하면서 offsetof라는 함수에 대해 말씀드리려 하는데, offsetof라는 함수는 <stddef.h>에서 표준으로 제공하고 있으며, 구조체의 멤버변수가 구조체상의 배치되어 있는 offset을 알려줍니다. 참고하세요.

그렇다면 다시 list_for_each_entry 함수로 돌아와서 이야기를 진행해보겠습니다. 이 함수의 목적은 아까 설명을 하기에 앞서 "리스트의 노드들을 한바퀴 순환하면서, 각 노드들을 참조하는 포인터를 시작주소 지점(entry)으로 옮기는 것"이라고 설명했는데 이제 이해가 가시는 가요? 결론 짓자면 샘플 프로그램에서 이 함수의 목적은 출력이라고 할 수 있습니다.

실제로 이렇게 커널에서 자료구조가 활용되고 있음을 알 수가 있습니다. 테스크 리스트, 소켓버퍼 리스트, 프로세스 리스트 등등 많은 부분에서 이 자료구조를 활용한다고 하는데 시간이 나면 실제로 활용되고 있는 부분을 분석해서 공유하도록 하겠습니다.

출처 : http://golee07.tistory.com/

'프로그래밍 > C' 카테고리의 다른 글

Visual studio가 잊어버리게 하는 개념(compile with gcc) (0)	2013.04.19
Vi 편집기 setting (0)	2013.04.19
포인터? 포인터변수? 포인터의 이해 (0)	2013.04.19
Double linked list with using array (0)	2013.04.19
함수 포인터 (0)	2013.04.19

linux kernel에서 쓰이는 자료구조.(double linked list and tree)

'프로그래밍 > C' 카테고리의 다른 글

카테고리

태그목록

최근에 올라온 글

최근에 달린 댓글

최근에 받은 트랙백

글 보관함

달력

링크

티스토리툴바