snifer

【原创】ARM Linux中链表使用实例

0
阅读(1997)
链表是一种常见的重要数据结构,它可以动态地进行存储分配,根据需要开辟内存单元,还可以方便地实现数据的增加和删除。链表中的每个元素都由两部分组成:数据域和指针域。

其中,数据域用于存储数据元素的信息,指针域用于存储该元素的直接后继元素的位置。


在ARM Linux中,链表是最为基本的数据结构,也是最为常用的数据结构。2.4内核中的链表结构和2.6并没有太大区别。二者不同之处在于2.6扩充了两种链表数据结构:链表的读拷贝更新(rcu)和HASH链表(hlist)。
链表数据结构的定义很简单:

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

在ARM Linux中,链表是最为基本的数据结构,也是最为常用的数据结构。2.4内核中的链表结构和2.6并没有太大区别。二者不同之处在于2.6扩充了两种链表数据结构:链表的读拷贝更新(rcu)和HASH链表(hlist)。
链表数据结构的定义很简单:

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


2)Linux内核链表接口
(1)声明和初始化
这里是使用LIST_HEAD()这个宏来构建的。

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

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

构建了一个空链表

static inline int list_empty(const struct list_head *head)

{ return head->next == head; }

2)Linux内核链表接口


(1)插入
对链表的插入操作有两种:在表头插入和在表尾插入。Linux为此提供了两个接口:
static inline void list_add(struct list_head *new, struct list_head *head);

static inline void list_add_tail(struct list_head *new, struct list_head *head);


}Linux内核链表接口
(1)删除
Linux中删除的代码也是类似的,通过__list_del来实现list_del接口,读者可以自行分析以下代码段:
static inline void __list_del(struct list_head * prev, struct list_head * next)
{
        next->prev = prev;
        prev->next = next;
}
}static inline void list_del(struct list_head *entry)
{
        __list_del(entry->prev, entry->next);
        entry->next = LIST_POISON1;
        entry->prev = LIST_POISON2;
}


在Linux中链表的使用非常方便灵活,后续会有更多的介绍,谢谢大家。