L16. linux通用链表
引言
链表的实现是基于结构体与指针两者实现的，常用的链表数据结构如下：
//将int起别名ELEMTYPE，是为了方便修改链表中的数据域类型。
typedef int ELEMTYPE;
typedef struct list
{
ELEMTYPE data;
struct list *prev, *next;
struct list;
}NODE, *pLIST;
如上链表设计与本身的数据域相关性太大，很难适应不同类型数据域代码的通用。
在Linux中设计了一种适合于各种类型数据域都可以使用的通用型链表：
struct list_head {
struct list_head *prev, *next;
};
摒弃掉数据域，只保留头尾指针。
内核链表
链表的主要意义就是将分散地址的数据域通过指针排列成有序的队列。因此数据域是链表不可或缺的一部分，但是在实际使用中需要不同类型的数据域，因此也就限制了链表的通用。Linux中在声明中抛弃了数据域，也就解决掉了这一问题。
原理
Linux使用链表的方法：使用时，自定义结构体包含数据域+链表结构体。即让内部链表成员与其他链表成员构建成双链表，实现遍历寻址，然后通过链表成员找到包含该成员的结构体首地址。
链表.png
如上图所示，将结构体A、B和C中的内核结构体指针构建成双链表，这样结构体A、B和C中的链表成员就可以互相索引了。
数据结构实现:
/* Declare a user structure containing a general double-linked list */
typedef struct circle_queue {
int id;
struct list_head my_list;
}NODE;
链表初始化：
链表的通用操作，先初始化链表，然后逐个增加节点。这里具体操作不过多描述，后附代码。
/*
* Initialize a doubly linked list
*/
static inline void init_list_head(struct list_head *list)
{
list->next = list;
list->prev = list;
}
NODE* queue_init()
{
NODE *head = (NODE *)malloc(sizeof(NODE));
init_list_head(&head->my_list);
return head;
}
内部数据域访问：
在实现以上操作，就可以实现结构体A、B、C中链表成员的索引遍历了。既然能访问到结构体A、B、C内部成员，自然也可以通过地址换算得到结构体A、B、C的首地址；进而得到A、B、C的数据域成员。
linux实现地址转换:
#define list_entry(ptr, type, member) \
((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
image.png
如图所示，(unsigned long)(&((type *)0)->member)))，将0地址强制转化为struct circle_queue类型，则此时0虚拟出了本结构体首地址。(unsigned long)(&((type *)0)->member)))就为member首地址，同样也是A的大小。
因为A与B类型相同，所以A=B。pos指向的首地址减去B的大小就为结构体x的首地址。即((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))返回的是链表所在结构体的首地址。结构体首地址拿到后，其他成员的访问不在话下。
通过上述方法， 可以通过任一结构体成员获取到该结构体的首地址
其余操作
剩下的就是链表的通用操作：增、删、改、查。
增：
/*
* Insert a new entry between two known consecutive entries.
*
* This is only for internal list manipulation where we know
* the prev/next entries already!
*/
static inline void __list_add(struct list_head *new,
struct list_head *prev, struct list_head *next)
{
new->next = next;
new->prev = prev;
prev->next = new;
next->prev = new;
}
static inline void list_add(struct list_head *head, struct list_head *new)
{
__list_add(new, head, head->next);
}
-------------------------------------------------------------------------------
void queue_add(NODE *p, NODE *new)
{
list_add(&p->my_list, &new->my_list);
}
删:
/*
* Delete a list entry by making the prev/next entries
* point to each other.
*
* This is only for internal list manipulation where we know
* the prev/next entries already!
*/
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 *del)
{
__list_del(del->prev, del->next);
}
-------------------------------------------------------------------------------
/* Delete node at specified location */
void queue_del(NODE *p, int num)
{
int i = 0;
NODE *del;
struct list_head *plist;
plist = &p->my_list;
for (i = 0; i < num; i++) {
plist = plist->next;
}
del = list_entry(plist, typeof(*del), my_list);
list_del(plist);
free(del);
}
改：
/*
* Get the first address from the structure member
*/
#define list_entry(ptr, type, member) \
((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
-------------------------------------------------------------------------------
void queue_modify(NODE *p, int num, int data)
{
int i = 0;
NODE *mdfy;
struct list_head *plist;
plist = &p->my_list;
for (i = 0; i < num; i++) {
plist = plist->next;
}
mdfy = list_entry(plist, typeof(*mdfy), my_list);
mdfy->id = data;
}
查：
/*
* Get the first address from the structure member
*/
#define list_entry(ptr, type, member) \
((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
#define list_for_each_entry(pos, head, member) \
for (pos = list_entry((head)->next, typeof(*pos), member); \
&pos->member != (head); \
pos = list_entry(pos->member.next, typeof(*pos), member))
-------------------------------------------------------------------------------
/* Show all of node */
void queue_show(NODE *head)
{
NODE *pos;
printf ("id: \n");
list_for_each_entry(pos, &head->my_list, my_list) {
printf("%d ", pos->id);
}
}
测试效果：
image.png
总结
linux在整个链表的实现中，只负责链表指针的指向的接口封装。具体的实现需要自行增加，类似空间的申请与释放。最重要的是理解通过结构体成员获取到当前结构体的首地址方法（0地址上的结构体实际并不存在，只是软件虚拟出来的）。
本次编程要点：
- 指针在使用前，必须有具体的指向对象或者动态申请空间；否则不可作为函数参数或者其他运算中。
- 链表建立完毕后，链表的遍历以及其他操作需依靠指针完成。
代码位置： https://github.com/LinuxTaoist/C-Language/tree/master/doule_linked_list
参考： https://blog.csdn.net/u014453898/article/details/53741921
如有技术交流需要，请关注“开源519”公众号。
开源519.jpg
