linux内核双向循环链表实例

//list.h


#ifndef _LIST_H
#define _LIST_H
/**
 *内核里的双向循环链表
 *是一个只有指针域而没有数据域的结构
 */
struct list{
    struct list *prev, *next;
};

#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name) \
    struct list name = LIST_HEAD_INIT(name)
#define offetof(type, member) (unsigned int &((type *)0->member))
#define list_entry(ptr, type, member)({ \
    const typeof(((type *)0)->member) *__mptr = (ptr); \
    (type *)((char *)__mptr - offsetof(type, member));})
#define list_for_each(pos, head) \
    for(pos = (head)->next; pos != (head); pos=pos->next)
/**
 *初始化一个双向循环链表
 */
static inline void INIT_LIST_HEAD(struct list *list)
{
    list->next = list;
    list->prev = list;
}
/**
 *函数名：__list_add
 *插入一个new链表
 */
static inline void __list_add(struct list *new,
             struct list *prev,
             struct list *next)
{
    next->prev = new;
    new->next = next;
    new->prev = prev;
    prev->next = new;
}
/**
 *函数名：list_add_head
 *采用头插法插入一个新的链表
 */
static inline void list_add_head(struct list *new, struct list *head)
{
    __list_add(new, head, head->next);
}
/**
 *函数名：list_add_tail
 *采用尾插法插入一个新的链表
 */
static inline void list_add_tail(struct list *new, struct list *head)
{
    __list_add(new, head->prev, head);
}
/**
 *函数名：__list_del
 *删除一个链表
 */
static inline void __list_del(struct list *prev, struct list *next)
{
    prev->next = next;
    next->prev = prev;
}
/**
 *函数名：list_del
 *删除一个具体的链表
 */
static inline void list_del(struct list *entry)
{
    __list_del(entry->prev, entry->next);
}
#endif

list.c:

/*
 * Copyright (c) 2009-~ Lan Peng
 *
 * This source code is released for free distribution under the terms of the
 * GNU General Public License
 *
 * Author: Lan Peng
 * Created Time: 2009年10月29日 星期四 10时43分27秒
 * File Name: list.c
 *
 * Description:
 */

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include "list.h"
struct mylist{
    int data;
    struct list list;
};

int main(int args, char *argv[])
{
    int i,n;
    struct mylist *tmp, *task;
    struct mylist head;
    struct list *pos;
    INIT_LIST_HEAD(&head.list);
    for(i = 0; i < 10; i++){
        tmp = (struct mylist *)malloc(sizeof(struct mylist));
        tmp->data = i;
        printf("I:%d\n", i);
        list_add_tail(&(tmp->list), &(head.list));//新的链表插入尾部

    }
    printf("\n");
    list_for_each(pos, &(head.list)){//遍历链表

        task=list_entry(pos, struct mylist, list);
        printf("II:%d\n", task->data);
    }
    printf("\n");
    pos = head.list.next;
    n = 3;//删除第n个元素

    for(i = 1; i < n; i++)
        pos = pos->next;
    list_del(pos);//删除链表

    list_for_each(pos, &(head.list)){
        task=list_entry(pos, struct mylist, list);
        printf("III:%d\n", task->data);
    }
    return 0;
}