当前位置: 首页 > 我的程序代码 > 正文

整理一个双向链表list.h

一直觉得Linux内核的双向链表是十分巧妙的设计,它的实现方式与数据结构课程上讲的完全不同。内核list实现依赖于GCC的扩展,在其它平台不一定能正常运行。在内核中,一般是结构体中使用链表成员,而不是像数据结构课那样在链表结构体中使用数据域。C++中将lsit作为模板,能应用于各种类型数据上,但Linux内核无法使用,因而使用其它手段实现,方便扩展。事实上,内核大量结构体都使用了list。网上有很多关于此方面的介绍,就不展开说了。

最近在研究hostapd,里面用到了双向链表,但与内核实现的有些许不同。就将其抽出,并修改了一下。

完整的list.h头文件如下:

/*
 * Doubly linked list
 * Copyright (c) 2016 Late Lee <latelee@163.com>
 *
 * for C&C++, M$ or GNU
 *
 */

#ifndef LL__LIST_H
#define LL__LIST_H

#ifdef __cplusplus
extern "C" {
#endif

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

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

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

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

static inline void list_add_head(struct list_head *item,
                    struct list_head *head)
{
    __list_add(item, head, head->next);
}

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

static inline void list_add_prev(struct list_head *item,
                    struct list_head *head)
{
    __list_add(item, head->prev, head);
}

static inline void list_del(struct list_head *item)
{
    item->next->prev = item->prev;
    item->prev->next = item->next;
    item->next = NULL;
    item->prev = NULL;
}

static inline int list_empty(struct list_head *list)
{
    return list->next == list;
}

static inline unsigned int list_length(struct list_head *list)
{
    struct list_head *item;
    int count = 0;
    for (item = list->next; item != list; item = item->next)
        count++;
    return count;
}

#ifndef offsetof
#define offsetof(type, member) ((long) &((type *) 0)->member)
#endif

#ifndef container_of
#define container_of(ptr, type, member) \
    ((type *) ((char *) ptr - offsetof(type, member)))
#endif

#define list_entry container_of

#define list_first_entry(list, type, member) \
    (list_empty((list)) ? NULL : \
     list_entry((list)->next, type, member))

#define list_last_entry(list, type, member) \
    (list_empty((list)) ? NULL : \
     list_entry((list)->prev, type, member))

#define list_entry_prev list_last_entry

#define list_entry_next list_first_entry

#define list_for_each(item, list, type, member) \
    for (item = list_entry((list)->next, type, member); \
         &item->member != (list); \
         item = list_entry(item->member.next, type, member))

#define list_for_each_safe(item, n, list, type, member) \
    for (item = list_entry((list)->next,type, member), \
             n = list_entry(item->member.next, type, member); \
         &item->member != (list); \
         item = n, n = list_entry(n->member.next, type, member))

#define llist_for_each_reverse(item, list, type, member) \
    for (item = list_entry((list)->prev, type, member); \
         &item->member != (list); \
         item = list_entry(item->member.prev, type, member))

#ifdef __cplusplus
}
#endif

#endif /* LL__LIST_H */

使用用示例如下(具体见测试代码实现):

1、定义链表:

LIST_HEAD(my_list);

2、插入:

list_add_tail(&devinfo->list, &my_list);

3、删除:

list_del(&devinfo->list);

注意,list_del只是将要删除的结点的指针置为空,该结点还没有被删除,所以要自行释放。

4、遍历:

list_for_each_safe(tdev, tmpdev, &my_list, struct i2c_devinfo, list)

在遍历时使用的list_for_each_safe和内核版本的list_for_each_entry_safe有不同:list_for_each_entry_safe(tdev, tmpdev, &my_list, list)。内核版本list少了结构体的类型struct i2c_devinfo,这是因为使用了typeof关键字,这个关键字有些编译器不支持,所以上面的实现就让使用者明式传递结构体类型。

5、获取链表数据项

list_entry(my_list.prev, struct i2c_devinfo, list);

list_entry(my_list.next, struct i2c_devinfo, list);

my_list的prev指针即为最后一个结点,而next是第一个结点。list_first_entry和list_last_entry就是如此实现的。

上述代码基本上实现了链表的插入(包含前插入、后插入 ^_^)、删除、遍历。为了避免使用typeof,个别函数实现与内核的list多了参数,但能在GCC和MS的VS2010环境下编译通过,运行效果一致,达到跨平台的目标。

完整的测试代码如下:

 /**
双向链表示例。演示创建、遍历、删除等操作。
g++ 5.8.4 & VS2010 测试通过

Late Lee <latelee@163.com> http://www.latelee.org

由hostapd的list源码修改而成 

结构示意图:

list_head
   prev ----------------------------------------------- 
      |                                                |
      -<-                                              |
   next |    node1          node2           node3      |
   ^|   |                                              |
   ||   |   data...         data...         data...    |
   ||   --- prev <--------- prev <--------- prev <-----|
   ||-----> next ---------> next ---------> next ------
   |        data...         data...         data...    |
   |-----<----------------------------------------------
   
头结点不使用,无法用list_entry拿到实际数据
list_head的prev指向最后一个结点,next指向第一个结点。
如果一直用next可遍历并循环到开始处,prev亦然。

注:list_add本身在“结点”后添加,如在list_haed“后”添加,则变成在整个链表开头。
如果在node1“后”添加,则在整个链表的node1后新加结点。

运行结果:
show info in the list.
[0] busnum: 10, slave: 0
[1] busnum: 11, slave: 2
[2] busnum: 12, slave: 4
[3] busnum: 13, slave: 6
[4] busnum: 14, slave: 8
prev entry: 14
next entry: 10
first entry: 10
last entry: 14
show info in the list.
[0] busnum: 1, slave: 25
[1] busnum: 10, slave: 0
[2] busnum: 250, slave: 25
[3] busnum: 11, slave: 2
[4] busnum: 250, slave: 25
[5] busnum: 12, slave: 4
[6] busnum: 14, slave: 8
[7] busnum: 65535, slave: 25
after delete...
list empty, nothing to show.
next1 entry: 1
next2 entry: 2
next3 entry: 0(0x0)
next4 entry: 1
next5 entry: 2


*/

#include <stdio.h>
#include <stdlib.h>

#include "list.h"

struct i2c_devinfo
{
	struct list_head list;
	int busnum;
    int slave;
};

// 定义链表
LIST_HEAD(my_list);

void init(int busnum, int slave)
{
    struct i2c_devinfo* devinfo;
    // 分配空间
    devinfo = (struct i2c_devinfo*)malloc(sizeof(struct i2c_devinfo));
    if (devinfo == NULL) return;

    // 赋值
    devinfo->busnum = busnum;
    devinfo->slave = slave;

    // 添加到链接中
    list_add_tail(&devinfo->list, &my_list);
}

void show(void)
{
    struct i2c_devinfo *devinfo;
    int i = 0;

    if (list_empty(&my_list))
    {
        printf("list empty, nothing to show.\n");
        return;
    }
    printf("show info in the list.\n");
    // 解释:从全局链表my_list中拿到devinfo信息,其中list为devinfo类型的一个成员变量
    //list_for_each(devinfo, &my_list, struct i2c_devinfo, list)
    list_for_each(devinfo, &my_list, struct i2c_devinfo, list)
    {
        printf("[%d] busnum: %d, slave: %d\n", i++, devinfo->busnum, devinfo->slave);
	}
}

void delete_list(void)
{
    struct i2c_devinfo *devinfo, *tdev;
    // 注:当要删除链表数据时,要使用*_safe,同时要额外增加一个临时变量
    list_for_each_safe(devinfo, tdev, &my_list, struct i2c_devinfo, list)
    {
        list_del(&devinfo->list);
        free(devinfo);
	}
}

void list_misc(void)
{
    struct i2c_devinfo* devinfo, *tdev, *tmpdev;

    struct i2c_devinfo* n;
    n = list_entry(my_list.prev, struct i2c_devinfo, list);
    printf("prev entry: %d\n", n->busnum);
    n = list_entry(my_list.next, struct i2c_devinfo, list);
    printf("next entry: %d\n", n->busnum);

    // 获取第一个、最后一个
    n = list_first_entry(&my_list, struct i2c_devinfo, list);
    printf("first entry: %d\n", n->busnum);
    n = list_last_entry(&my_list, struct i2c_devinfo, list);
    printf("last entry: %d\n", n->busnum);
    
    // 
    devinfo = (struct i2c_devinfo*)malloc(sizeof(struct i2c_devinfo));
    devinfo->busnum = 1;
    devinfo->slave = 25;
    list_add(&devinfo->list, &my_list); // 在my_list后添加,变成在链表的头部 // note1
    
    devinfo = (struct i2c_devinfo*)malloc(sizeof(struct i2c_devinfo));
    devinfo->busnum = 65535;
    devinfo->slave = 25;
    list_add_tail(&devinfo->list, &my_list); // 在末尾
    
    // 中途插入、删除
    //list_for_each(tdev, &my_list, struct i2c_devinfo, list)
    list_for_each_safe(tdev, tmpdev, &my_list, struct i2c_devinfo, list)
    {
        if (tdev->busnum == 10) // 在此节点后插入
        {
            devinfo = (struct i2c_devinfo*)malloc(sizeof(struct i2c_devinfo));
            devinfo->busnum = 250;
            devinfo->slave = 25;
            list_add(&devinfo->list, &tdev->list); // note2
        }
        if (tdev->busnum == 12) // 在此节点前插入
        {
            devinfo = (struct i2c_devinfo*)malloc(sizeof(struct i2c_devinfo));
            devinfo->busnum = 250;
            devinfo->slave = 25;
            list_add_prev(&devinfo->list, &tdev->list);
        }
        if (tdev->busnum == 13) // 删除此节点
        {
            list_del(&tdev->list);
        }
	}
}

// 遍历示例
void list_misc1(void)
{
    LIST_HEAD(my_list);
    struct i2c_devinfo* devinfo;
    
    devinfo = (struct i2c_devinfo*)malloc(sizeof(struct i2c_devinfo));
    devinfo->busnum = 1;
    devinfo->slave = 25;
    list_add_tail(&devinfo->list, &my_list);
    devinfo = (struct i2c_devinfo*)malloc(sizeof(struct i2c_devinfo));
    devinfo->busnum = 2;
    devinfo->slave = 25;
    list_add_tail(&devinfo->list, &my_list);
    
    
    struct i2c_devinfo* n;
    n = list_entry(my_list.next, struct i2c_devinfo, list); // 第一个结点
    printf("next1 entry: %d\n", n->busnum);
    n = list_entry(my_list.next->next, struct i2c_devinfo, list);   // 第二个结点
    printf("next2 entry: %d\n", n->busnum);
    n = list_entry(my_list.next->next->next, struct i2c_devinfo, list); // 回到my_list,此时数据无效
    printf("next3 entry: %d(0x%x)\n", n->busnum, n->busnum);
    n = list_entry(my_list.next->next->next->next, struct i2c_devinfo, list);   // 第一个结点
    printf("next4 entry: %d\n", n->busnum);
    n = list_entry(my_list.next->next->next->next->next, struct i2c_devinfo, list); // 第二个结点
    printf("next5 entry: %d\n", n->busnum);
}

int main(void)
{
    int i = 0;
    int j = 0;
    for (i = 10; i < 15; i++, j += 2)
    {
        init(i, j);
    }

    show();

    list_misc();
    show();

    printf("after delete...\n");
    delete_list();
    // 删除链表后,已经没有内容了
    show();

    list_misc1();
    return 0;
}

这里说一下note1、note2两处代码的list_add的不同表现,list_add是在链表某结点后面插入新结点,相对地,list_add_tail则是在链表最后插入新结点。在note1处,传递的结点为my_list,从上述代码图示中看出,my_list实际上是头结点,它是不包括真正有数据的结点的,在此“结点”的后面插入新结点,就变成了链表的头部数据。所以后面使用list_for_each_safe遍历时,看到新加的结点位于链表开始处,在此情况下,list_add变成了向前插入新结点。但在note2处并不是使用my_list,而是使用已经存在的链表中的一个结点,当然就是在其后插入结点了。

在函数list_misc1中,只使用next指针进行遍历,能证明my_list的确只是一个头结点。

学好数据结构十分重要,不同应用场合要选择适当的数据结构来解决问题,当熟知并掌握数据结构后,就能胸有成竹。但是,本文仅仅是本着“适用”的目的来使用list,如内核list的合并、旋转等——包括哈希链表,有待后续再研究。因为毕竟不是应试。

李迟 2016.10.19 周三 中午休息前

本文固定链接: http://www.latelee.org/my-library/my-doubly-linked-list-code.html

如无特别说明,迟思堂工作室文章均为原创,转载请注明: 整理一个双向链表list.h | 迟思堂工作室

目前暂无评论

发表评论

*

快捷键:Ctrl+Enter