[알고리즘] 리스트자료구조 (linux내의 list.h 이용) 예제

리스트 자료구조를 간단히 테스트해본다.

• 예제코드
• 간단 활용 코드예제

예제코드

리눅스의 list.h 이다. 해당 헤더를 이용하여 리스트구조를 작성해보자.

#ifndef _LINUX_LIST_H 
#define _LINUX_LIST_H 

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

#define LIST_HEAD_INIT(name) { &(name), &(name) } 

#define LIST_HEAD(name) \ 
struct list_head name = LIST_HEAD_INIT(name) 

#define INIT_LIST_HEAD(ptr) do { \ 
    (ptr)->next = (ptr); (ptr)->prev = (ptr); \ 
} while (0) 

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; 
} 

    void list_add(struct list_head *new, struct list_head *head) 
{ 
    __list_add(new, head, head->next); 
} 

    void list_add_tail(struct list_head *new, struct list_head *head) 
{ 
    __list_add(new, head->prev, head); 
} 

    void __list_del(struct list_head *prev, struct list_head *next) 
{ 
    next->prev = prev; 
    prev->next = next; 
} 

    void list_del(struct list_head *entry) 
{ 
    __list_del(entry->prev, entry->next); 
    entry->next = (void *) 0; 
    entry->prev = (void *) 0; 
} 

    void list_del_init(struct list_head *entry) 
{ 
    __list_del(entry->prev, entry->next); 
    INIT_LIST_HEAD(entry); 
} 

    void list_move(struct list_head *list, struct list_head *head) 
{ 
    __list_del(list->prev, list->next); 
    list_add(list, head); 
} 

    void list_move_tail(struct list_head *list, 
                                    struct list_head *head) 
{ 
    __list_del(list->prev, list->next); 
    list_add_tail(list, head); 
} 

    int list_empty(struct list_head *head) 
{ 
    return head->next == head; 
} 

    void __list_splice(struct list_head *list, 
                                    struct list_head *head) 
{ 
    struct list_head *first = list->next; 
    struct list_head *last = list->prev; 
    struct list_head *at = head->next; 

    first->prev = head; 
    head->next = first; 

    last->next = at; 
    at->prev = last; 
} 

    void list_splice(struct list_head *list, struct list_head *head) 
{ 
    if (!list_empty(list)) 
        __list_splice(list, head); 
} 

    void list_splice_init(struct list_head *list, 
                                    struct list_head *head) 
{ 
    if (!list_empty(list)) { 
        __list_splice(list, head); 
        INIT_LIST_HEAD(list); 
    } 
} 

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

#define list_for_each(pos, head) \ 
    for (pos = (head)->next; pos != (head); \ 
pos = pos->next) 

#define list_for_each_prev(pos, head) \ 
    for (pos = (head)->prev; pos != (head); \ 
pos = pos->prev) 

#define list_for_each_safe(pos, n, head) \ 
    for (pos = (head)->next, n = pos->next; pos != (head); \ 
pos = n, n = pos->next) 

#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)  \ 
) 

#endif 

간단 활용 코드예제

위의 를 이용한 예제코드

#include <stdio.h>
#include "list.h" 

struct people 
{ 
    int age; 
    char name[20]; 
    struct list_head list; 
}; 

#if 0 
int main() 
{ 
    struct people p1 = { 34, "kim", }; 

    printf("%d\n", &((struct people*)0)->list ); 

    printf("name:%s\n", 
    ((struct people*) 
    ((char *)&p1.list - (int)&((struct people*)0)->list))->name); 

    printf("name:%s\n", 
        list_entry(&p1.list, struct people, list)->name ); 

    return 0; 
} 
#endif 


int main() 
{ 
    //struct list_head head = { &head, &head }; 
    LIST_HEAD(head); 
    struct people p1 = { 34, "kim", }; 
    struct people p2 = { 22, "park", }; 
    struct list_head *temp; 
    struct people *p; 

    list_add( &p1.list , &head ); 
    list_add( &p2.list , &head ); 


    //for( temp = head.prev; temp != &head; temp = temp->prev ) 
    list_for_each( temp, &head ) 
    { 
        p = list_entry( temp, struct people, list); 
        printf("name:%s, age:%d\n", p->name, p->age ); 
    } 

    return 0; 
}