linux优雅的链表

链表是每一个程序员必学的一个数据结构。理解上并不是很难，但是它却很常用。所以我们为了避免重复造轮子，所以一个好的设计就显得格外的重要了。如果在C++中我们可以很容易的想到模板编程。可是在纯C的环境下就没有什么简单了。

为了避免重复的工作，先把工作中重复的部分提取出来。比如说是循环双向链表。每一个节点包含了前一个元素指针和后一个元素的指针。为了操作的便利，我们会使用到带头节点的方式。前后指针的是每一种循环双向链表节点要包括的数据结构，所以就可以想办法把其抽离出来，这里给出了linux下的list的实现的简版。（如果你参与过window下的驱动开发，应该也会发现这种实现方式的list）

1 #include <iostream>
  2 #include <assert.h>
  3 
  4 using namespace std;
  5 
  6 struct list_head{
  7     struct list_head *next, *prev;
  8 };
  9 
 10 #define LIST_HEAD_INIT(name) { &(name), &(name) }
 11 
 12 #define LIST_HEAD(name) struct list_head name = LIST_HEAD_INIT(name)
 13 
 14 #define INIT_LIST_HEAD(ptr) do { \
 15     (ptr)->next = (ptr); (ptr)->prev = (ptr); \
 16 } while (0)
 17 
 18 //计算结构体内部成员的偏移，（求取结构体中的成员的偏移是笔试中常见题型） 
 19 #define offset_of(type , member) (size_t)(&((type *)0)->member)  
 20 
 21 //计算当前结构体的首地址 prt为member的地址, type为结构体的类型，（这个也会成为笔试题）
 22 #define container_of(ptr , type , member) \
 23         ( \
 24         (type *)( (char *)ptr - offset_of(type , member)) \
 25     )
 26 
 27 
 28 #define list_entry(ptr , type , member) \
 29     container_of(ptr , type , member)
 30 
 31 //
 32 //#define list_first_entry(ptr , type , member) \
 33 //    list_entry((ptr)->next , type , member)
 34 
 35 //
 36 #define list_for_each(pos, head) \
 37     for (pos = (head)->next; pos != (head); \
 38                 pos = pos->next)
 39 
 40 static inline int list_empty(const struct list_head *head){
 41     return head->next == head;
 42 }
 43 
 44 static inline void __list_add(struct list_head *newnode,  struct list_head *prev , struct list_head *next)
 45 {
 46     newnode->next = next;
 47     newnode->prev = prev;
 48     prev->next = newnode;
 49     next->prev = newnode;
 50 }
 51 
 52 static inline void list_add(struct list_head *newnode, struct list_head *head)
 53 {
 54     __list_add(newnode, head, head->next);
 55 }
 56 
 57 static inline void list_add_tail(struct list_head *newnode, struct list_head *head)
 58 {
 59     __list_add(newnode, head->prev, head);
 60 }
 61 
 62 static inline void __list_del(struct list_head *prev , struct list_head *next)
 63 {
 64     prev->next = next;
 65     next->prev = prev;
 66 }
 67 
 68 static inline void list_del(struct list_head *node)
 69 {
 70     __list_del(node->prev, node->next);
 71 }
 72 
 73 
 74 typedef struct my_struct{    
 75     int data;
 76     list_head list;
 77 }my_struct_t;
 78 
 79 int main()
 80 {
 81     struct list_head *p;
 82 
 83     LIST_HEAD(hd);
 84 
 85     struct my_struct *a = (struct my_struct*)malloc(sizeof(struct my_struct));
 86     a->data = 2;
 87 
 88     list_add(&a->list , &hd);
 89 
 90     a = (struct my_struct*)malloc(sizeof(struct my_struct));
 91     a->data = 1;
 92 
 93     list_add(&a->list , &hd);
 94 
 95     a = (struct my_struct*)malloc(sizeof(struct my_struct));
 96     a->data = 3;
 97     
 98     list_add_tail(&a->list , &hd);
 99 
100     cout<<offset_of( my_struct, list)<<endl;
101 
102 
103     cout<<a<<endl;
104     cout<<list_entry(&a->list, my_struct, list)<<endl;
105     list_for_each(p, &hd){
106         printf("%d ", ((my_struct_t*)list_entry(p, my_struct, list))->data );
107     }
108 
109     p = hd.next;
110     list_del(hd.next);
111     free((my_struct_t*)list_entry(p, my_struct, list));
112     
113     list_for_each(p, &hd){
114         printf("%d ", ((my_struct_t*)list_entry(p, my_struct, list))->data );
115     }
116     
117     return 0;
118 }

参考文献：

深入分析 Linux 内核链表

毕
原文链接: https://www.cnblogs.com/legendmaner/archive/2013/05/24/3096922.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍