通用C 鏈表（linux思想）

通用 C鏈表，適合任意類型

頭文件定義Mylist.h

# define POISON_POINTER_DELTA 0

#define LIST_POISON1  ((void *) 0x00100100 + POISON_POINTER_DELTA)
#define LIST_POISON2  ((void *) 0x00200200 + POISON_POINTER_DELTA)

//計(jì)算member在type中的位置
#define offsetof(type, member)  (size_t)(&((type*)0)->member)
//根據(jù)member的地址獲取type的起始地址
#define container_of(ptr, type, member) ({          \
        const typeof(((type *)0)->member)*__mptr = (ptr);    \
    (type *)((char *)__mptr - offsetof(type, member)); })

//鏈表結(jié)構(gòu)
struct list_head
{
    struct list_head *prev;
    struct list_head *next;
};

static inline void init_list_head(struct list_head *list)
{
    list->prev = list;
    list->next = list;
}

static inline void __list_add(struct list_head *new,
    struct list_head *prev, struct list_head *next)
{
    prev->next = new;
    new->prev = prev;
    new->next = next;
    next->prev = new;
}

//從頭部添加
static inline void list_add(struct list_head *new , struct list_head *head)
{
    __list_add(new, head, head->next);
}
//從尾部添加
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
    __list_add(new, head->prev, head);
}

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

static inline void list_del(struct list_head *entry)
{
    __list_del(entry->prev, entry->next);
    entry->next = LIST_POISON1;
    entry->prev = LIST_POISON2;
}

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

static inline void list_move_tail(struct list_head *list,
                      struct list_head *head)
{
        __list_del(list->prev, list->next);
        list_add_tail(list, head);
}
#define list_entry(ptr, type, member) \
    container_of(ptr, type, member)

#define list_first_entry(ptr, type, member) \
    list_entry((ptr)->next, type, member)

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

/**@brief 練習(xí)使用linux內(nèi)核鏈表，功能包括：
 * 定義鏈表結(jié)構(gòu)，創(chuàng)建鏈表、插入節(jié)點(diǎn)、刪除節(jié)點(diǎn)、移動(dòng)節(jié)點(diǎn)、遍歷節(jié)點(diǎn)
 *
 *@auther Anker @date 2013-12-15
 **/
#include <stdio.h>
#include <inttypes.h>
#include <stdlib.h>
#include <errno.h>
#include "mylist.h"
//定義app_info鏈表結(jié)構(gòu)
typedef struct application_info
{
    uint32_t  data;
    
    struct    list_head app_info_node;//鏈表節(jié)點(diǎn)
}app_info;


app_info* get_app_info(uint32_t data)
{
    app_info *app = (app_info*)malloc(sizeof(app_info));
    if (app == NULL)
    {
    fprintf(stderr, "Failed to malloc memory, errno:%u, reason:%s\n",
        errno, strerror(errno));
    return NULL;
    }
    app->data = data;
 
    return app;
}
static void for_each_app(const struct list_head *head)
{
    struct list_head *pos;
    app_info *app;
    //遍歷鏈表
    list_for_each(pos, head)
    {
    app = list_entry(pos, app_info, app_info_node);
    printf("ap_id: %u\t\n",
        app->data);

    }
}

void destroy_app_list(struct list_head *head)
{
    struct list_head *pos = head->next;
    struct list_head *tmp = NULL;
    while (pos != head)
    {
    tmp = pos->next;
    list_del(pos);
    pos = tmp;
    }
}


int main()
{
    //創(chuàng)建一個(gè)app_info
    app_info * app_info_list = (app_info*)malloc(sizeof(app_info));
    app_info *app;
    if (app_info_list == NULL)
    {
    fprintf(stderr, "Failed to malloc memory, errno:%u, reason:%s\n",
        errno, strerror(errno));
    return -1;
    }
    //初始化鏈表頭部
    struct list_head *head = &app_info_list->app_info_node;
    init_list_head(head);
    //插入三個(gè)app_info
    app = get_app_info(1);
    list_add_tail(&app->app_info_node, head);
    app = get_app_info(2);
    list_add_tail(&app->app_info_node, head);
    app = get_app_info(3);
    list_add_tail(&app->app_info_node, head);
    printf("After insert three app_info: \n");
    for_each_app(head);
    //將第一個(gè)節(jié)點(diǎn)移到末尾
    printf("Move first node to tail:\n");
    list_move_tail(head->next, head);
    for_each_app(head);
    //刪除最后一個(gè)節(jié)點(diǎn)
    printf("Delete the last node:\n");
    list_del(head->prev);
    for_each_app(head);
    destroy_app_list(head);
    free(app_info_list);
    return 0;
}

root@ubuntu:/test/linux/20160109# ./list 
After insert three app_info: 
ap_id: 1	
ap_id: 2	
ap_id: 3	
Move first node to tail:
ap_id: 2	
ap_id: 3	
ap_id: 1	
Delete the last node:
ap_id: 2	
ap_id: 3	
root@ubuntu:/test/linux/20160109#