通用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)

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

//链表结构
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 练习使用linux内核链表，功能包括：
 * 定义链表结构，创建链表、插入节点、删除节点、移动节点、遍历节点
 *
 *@auther Anker @date 2013-12-15
 **/
#include <stdio.h>
#include <inttypes.h>
#include <stdlib.h>
#include <errno.h>
#include "mylist.h"
//定义app_info链表结构
typedef struct application_info
{
    uint32_t  data;
    
    struct    list_head app_info_node;//链表节点
}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()
{
    //创建一个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);
    //插入三个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);
    //将第一个节点移到末尾
    printf("Move first node to tail:\n");
    list_move_tail(head->next, head);
    for_each_app(head);
    //删除最后一个节点
    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#