【原创】ARM Linux中链表使用实例
0赞
发表于 2015/5/21 17:04:58
阅读（3544）
链表是一种常见的重要数据结构，它可以动态地进行存储分配，根据需要开辟内存单元，还可以方便地实现数据的增加和删除。链表中的每个元素都由两部分组成：数据域和指针域。
其中，数据域用于存储数据元素的信息，指针域用于存储该元素的直接后继元素的位置。
在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中链表的使用非常方便灵活，后续会有更多的介绍，谢谢大家。
