Chinaunix首页 | 论坛 | 博客
  • 博客访问: 3204012
  • 博文数量: 1805
  • 博客积分: 135
  • 博客等级: 入伍新兵
  • 技术积分: 3345
  • 用 户 组: 普通用户
  • 注册时间: 2010-03-19 20:01
文章分类

全部博文(1805)

文章存档

2017年(19)

2016年(80)

2015年(341)

2014年(438)

2013年(349)

2012年(332)

2011年(248)

分类: LINUX

2014-10-15 23:19:25

原文地址:linux的数据结构---链表 作者:_ChinaUnix

    链表是一种常见的组织有序数据的数据结构,相对于数组,具有更好的动态性,可以高效的在链表的任意位置实时的插入或者删去。在linux的源代码中,大量的使用了链表。通常链表数据结构至少有两个域:数据域和指针域,数据域用于存储数据,指针域用于建立与下一个节点的联系。在数据结构中定义一个指向任意类型为

点击(此处)折叠或打开

  1. struct list
  2. {
  3.     void *data;
  4.     struct list *next;
  5. };
而在内核中,定义了一种通用的双向循环链表,链表的定义为:

点击(此处)折叠或打开

  1. struct list_head {
  2.     struct list_head *next, *prev;
  3. };
有prev和next两个指针,分别指向链表中的前一节点和后一节点。在初始化的时候,都指向自己本身。

点击(此处)折叠或打开

  1. static inline void INIT_LIST_HEAD(struct list_head *list)
  2. {
  3.     list->next = list;
  4.     list->prev = list;
  5. }
向链表中添加节点

点击(此处)折叠或打开

  1. static inline void __list_add(struct list_head *new,
  2.              struct list_head *prev, struct list_head *next)
  3. {
  4.     next->prev = new;
  5.     new->next = next;
  6.     new->prev = prev;
  7.     prev->next = new;
  8. }

  9. static inline void list_add(struct list_head *new, struct list_head *head)
  10. {
  11.     __list_add(new, head, head->next);
  12. }

  13. static inline void list_add_tail(struct list_head *new, struct list_head *head)
  14. {
  15.     __list_add(new, head->prev, head);
  16. }
list_add和list_add_tail的区别不大,linux实现两个接口,在表头插入是插入在head后,而在表尾插入是在head->prev之后,只是表明插入到该节点之后或者之前。链表中的节点删去

点击(此处)折叠或打开

  1. static inline void __list_del(struct list_head *prev, struct list_head *next)
  2. {
  3.     next->prev = prev;
  4.     prev->next = next;
  5. }

  6. static inline void list_del(struct list_head *entry)
  7. {
  8.     __list_del(entry->prev, entry->next);
  9.     entry->next = (void *)0xDEADBEEF;
  10.     entry->prev = (void *)0xBEEFDEAD;
  11. }
被删去entry删去后分别指向两个值,这个设置是为了保持不在链表中的节点项以后不会被访问。

点击(此处)折叠或打开

  1. static inline void list_del_init(struct list_head *entry)
  2. {
  3.     __list_del_entry(entry);
  4.     INIT_LIST_HEAD(entry);
  5. }
该函数将节点从链表中解下来后,调用INIT_LIST_HEAD将节点设置为空链表。

点击(此处)折叠或打开

  1. static inline void list_replace(struct list_head *old,
  2.                 struct list_head *new)
  3. {
  4.     new->next = old->next;
  5.     new->next->prev = new;
  6.     new->prev = old->prev;
  7.     new->prev->next = new;
  8. }

  9. static inline void list_replace_init(struct list_head *old,
  10.                     struct list_head *new)
  11. {
  12.     list_replace(old, new);
  13.     INIT_LIST_HEAD(old);
  14. }
list_replace是将链表中的一个老节点换乘一个新节点,从实现上来看,即使old所在链表只有一个old节点,new也可以成功替换。

点击(此处)折叠或打开

  1. static inline void list_move(struct list_head *list, struct list_head *head)
  2. {
  3.     __list_del_entry(list);
  4.     list_add(list, head);
  5. }

  6. static inline void list_move_tail(struct list_head *list,
  7.                  struct list_head *head)
  8. {
  9.     __list_del_entry(list);
  10.     list_add_tail(list, head);
  11. }
list_move的作用是把list节点从原链表中去除,并加入到新的链表中;而list_move_tail只是加入新链表。前者是加到链表的头部,而后者是加入到链表的尾部。

点击(此处)折叠或打开

  1. static inline int list_is_last(const struct list_head *list,
  2.                 const struct list_head *head)
  3. {
  4.     return list->next == head;
  5. }
上面函数主要是判断list是否处于head链表的尾部。

点击(此处)折叠或打开

  1. static inline int list_empty(const struct list_head *head)
  2. {
  3.     return head->next == head;
  4. }

  5. static inline int list_empty_careful(const struct list_head *head)
  6. {
  7.     struct list_head *next = head->next;
  8.     return (next == head) && (next == head->prev);
  9. }
list_empty判断head链表是否为空,而list_empty_careful同样也是判断链表是否为空,只是多了一个检测条件。

点击(此处)折叠或打开

  1. static inline int list_is_singular(const struct list_head *head)
  2. {
  3.     return !list_empty(head) && (head->next == head->prev);
  4. }
list_is_singular判断head是否只有一个节点,在检测链表头head外是否只有一个节点。list的操作包括链表的节点添加和删去,节点从一个链表转移到另外一个链表,替换和合并,由于其数据结构中只是定义了两个指针域,没有定义数据域。那么怎么去获得数据域呢?linux中有一种新的方法来获取,通过获取一个结构体中一个成员在这个结构体中的偏移。

点击(此处)折叠或打开

  1. #define list_entry(ptr, type, member) \
  2.     container_of(ptr, type, member)
来个例子,例如

点击(此处)折叠或打开

  1. typedef struct
  2. {
  3.     int i;
  4.     int j;
  5. }ember;
这个ember结构体占用了8个字节,假设声明一个变量ember a;想知道a的地址该如果办呢?只要知道j在a中的偏移量,然后把j的地址减去这个偏移量就是a的地址。list_entry主要用于从list节点查找其内嵌的结构。

点击(此处)折叠或打开

  1. #define list_first_entry(ptr, type, member) \
  2.     list_entry((ptr)->next, type, member)
list_first_entry是将ptr看成一个链表头,取出其中第一个节点对应的结构地址。下面来看看在总线设备驱动模型中大量被使用的list_for_each,循环遍历链表中的每个节点,从链表的头部的第一个节点,一直到链表的尾部。

点击(此处)折叠或打开

  1. #define list_for_each(pos, head) \
  2.     for (pos = (head)->next; prefetch(pos->next), pos != (head); \
  3.         pos = pos->next)

点击(此处)折叠或打开

  1. #define __list_for_each(pos, head) \
  2.     for (pos = (head)->next; pos != (head); pos = pos->next)

点击(此处)折叠或打开

  1. #define list_for_each_prev(pos, head) \
  2.     for (pos = (head)->prev; prefetch(pos->prev), pos != (head); \
  3.         pos = pos->prev)
list_for_each_prev从链表的尾部逆向遍历到链表头。

点击(此处)折叠或打开

  1. #define list_for_each_entry(pos, head, member)                \
  2.     for (pos = list_entry((head)->next, typeof(*pos), member);    \
  3.      &pos->member != (head);     \
  4.      pos = list_entry(pos->member.next, typeof(*pos), member))
上面这个函数不是遍历链表的节点,而是遍历链表节点锁嵌套的结构。其等价为list_for_each加list_entry。在list_head,有以上一些通用的链表的形式,但是还有一种klist和hlist也占据了很大的一部分,hlist也就是哈希表。哈希表也是一个哈希数组,为了解决映射冲突的问题,其实哈希组的每一个项做成一个链表,哈希组的项很多,list_head的话每个链表都需要两个指针空间,就发明了hlist,一是它的链表只需要一个指针,二是它的每一项都可以找到前一个节点。

点击(此处)折叠或打开

  1. struct klist_node;
  2. struct klist {
  3.     spinlock_t        k_lock;
  4.     struct list_head    k_list;
  5.     void            (*get)(struct klist_node *);
  6.     void            (*put)(struct klist_node *);
  7. } __attribute__ ((aligned (sizeof(void *))));

  8. #define KLIST_INIT(_name, _get, _put)                    \
  9.     { .k_lock    = __SPIN_LOCK_UNLOCKED(_name.k_lock),        \
  10.      .k_list    = LIST_HEAD_INIT(_name.k_list),            \
  11.      .get        = _get,                        \
  12.      .put        = _put, }

  13. #define DEFINE_KLIST(_name, _get, _put)                    \
  14.     struct klist _name = KLIST_INIT(_name, _get, _put)

  15. extern void klist_init(struct klist *k, void (*get)(struct klist_node *),
  16.          void (*put)(struct klist_node *));

  17. struct klist_node {
  18.     void            *n_klist;    /* never access directly */
  19.     struct list_head    n_node;
  20.     struct kref        n_ref;
  21. };
可以看到,klist的链表头是一个struct klist结构,链表节点是struct klist_node结构。先看看struct klist,包含链表需要的k_list,用于加锁的k_lock,get()和put()用于对结构的引用。这样在节点的初始化调用get(),在节点删去时调用put()。
在看看struct klist_node,除了链表需要的node,一个引用计数,还有一个n_klist指针。初始化klist

点击(此处)折叠或打开

  1. void klist_init(struct klist *k, void (*get)(struct klist_node *),
  2.         void (*put)(struct klist_node *))
  3. {
  4.     INIT_LIST_HEAD(&k->k_list);
  5.     spin_lock_init(&k->k_lock);
  6.     k->get = get;
  7.     k->put = put;
  8. }


阅读(273) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~