Chinaunix首页 | 论坛 | 博客
  • 博客访问: 720157
  • 博文数量: 77
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 1173
  • 用 户 组: 普通用户
  • 注册时间: 2014-05-16 11:20
个人简介

将技术做到极致...

文章分类

全部博文(77)

文章存档

2019年(3)

2015年(27)

2014年(47)

分类: LINUX

2014-05-29 11:31:11

原文地址:linux下双向链表的实现 作者:andyhzw

操作系统:ubuntu10.04


前言:
    在开发中,经常需要使用到链表,因此参考linux内核的链表的实现。

一,源码

点击(此处)折叠或打开

  1. #ifndef __LIST_H__
  2. #define __LIST_H__

  3. #ifdef __cplusplus
  4. extern "C" {
  5. #endif

  6. /* Define to prevent recursive inclusion
  7. -------------------------------------*/
  8. #include "types.h"


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


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

  11. #define    LIST_HEAD(name) \
  12.     struct list_head name = LIST_HEAD_INIT(name)

  13. static    inline void    INIT_LIST_HEAD(struct list_head *list)
  14. {
  15.     list->next = list;
  16.     list->prev = list;
  17. }


  18. /*
  19.  * Insert a new entry between two known consecutive entries.
  20.  *
  21.  * This is only for internal list manipulation where we know
  22.  * the prev/next entries
  23.  */
  24. /* prev <=> new <=> next */
  25. static    inline void    __list_add(struct list_head *new,
  26.                             struct list_head *prev,
  27.                             struct list_head *next)
  28. {
  29.     next->prev = new;
  30.     new->next = next;
  31.     new->prev = prev;
  32.     prev->next = new;
  33. }



  34. /**
  35.  * list_add - add a new entry
  36.  * @new: new entry to be added
  37.  * @head: list head to add it after
  38.  *
  39.  * Insert a new entry after the specified head.
  40.  * This is good for implementing stacks.
  41.  */
  42.  /* head <=> lastest <=> ... <=> third <=> second <=> first */
  43. static    inline void    list_add(struct list_head *new,
  44.                             struct list_head *head)
  45. {
  46.     __list_add(new,head,head->next);
  47. }



  48. /**
  49.  * list_add_tail - add a new entry
  50.  * @new: new entry to be added
  51.  * @head: list head to add it before
  52.  *
  53.  * Insert a new entry before the specified head.
  54.  * This is useful for implementing queues.
  55.  */
  56.  /* first <=> second <=> third <=> ... <=> lastest <=> head */
  57. static    inline void    list_add_tail(struct list_head *new,
  58.                                 struct list_head *head)
  59. {
  60.     __list_add(new,head->prev,head);    
  61. }




  62. #define LIST_POISON1 ((void *) 0x00100100)
  63. #define LIST_POISON2 ((void *) 0x00200200)


  64. /*
  65.  * Delete a list entry by making the prev/next entries
  66.  * point to each other.
  67.  *
  68.  * This is only for internal list manipulation where we know
  69.  * the prev/next entries
  70.  */
  71. static    inline void    __list_del(struct list_head *prev,
  72.                             struct list_head *next)
  73. {
  74.     next->prev = prev;
  75.     prev->next = next;
  76. }


  77. /**
  78.  * list_del - deletes entry from list.
  79.  * @entry: the element to delete from the list.
  80.  * Note: list_empty() on entry does not return true after this, the entry is
  81.  * in an undefined state.
  82.  */
  83. static    inline void    list_del(struct list_head *entry)
  84. {

  85.     __list_del(entry->prev,entry->next);
  86.     entry->next = LIST_POISON1;
  87.     entry->prev = LIST_POISON2;
  88. }




  89. /**
  90.  * list_is_last - tests whether @list is the last entry in list @head
  91.  * @list: the entry to test
  92.  * @head: the head of the list
  93.  */
  94. static    inline int        list_is_last(const struct list_head *list,
  95.                             const struct list_head *head)
  96. {
  97.     return (list->next == head);
  98. }



  99. /**
  100.  * list_empty - tests whether a list is empty
  101.  * @head: the list to test.
  102.  */
  103. static    inline int        list_empty(const struct list_head *head)
  104. {
  105.     return (head->next == head);
  106. }


  107. /**
  108.  * container_of - cast a member of a structure out to the containing structure
  109.  * @ptr:    the pointer to the member.
  110.  * @type:    the type of the container struct this is embedded in.
  111.  * @member:    the name of the member within the struct.
  112.  *
  113.  */
  114. #define    offsetof(TYPE,MEMBER)    ((size_t)&((TYPE*)0)->MEMBER)
  115. #define    container_of(ptr,type,member)     ({ \
  116.             const typeof(((type *)0)->member) *__mptr = (ptr);\
  117.             (type*)((char *)__mptr - offsetof(type,member));})


  118. /**
  119.  * list_entry - get the struct for this entry
  120.  * @ptr:    the &struct list_head pointer.
  121.  * @type:    the type of the struct this is embedded in.
  122.  * @member:    the name of the list_struct within the struct.
  123.  */
  124. #define    list_entry(ptr, type, member) \
  125.             container_of(ptr,type,member)


  126. /**
  127.  * list_first_entry - get the first element from a list
  128.  * @ptr:    the list head to take the element from.
  129.  * @type:    the type of the struct this is embedded in.
  130.  * @member:    the name of the list_struct within the struct.
  131.  *
  132.  * Note, that list is expected to be not empty.
  133.  */
  134. #define    list_first_entry(ptr, type, member) \
  135.             list_entry((ptr)->next, type, member)




  136. /**
  137.  * list_for_each    -    iterate over a list
  138.  * @pos:    the &struct list_head to use as a loop cursor.
  139.  * @head:    the head for your list.
  140.  *
  141.  * This variant differs from list_for_each() in that it's the
  142.  * simplest possible list iteration code, no prefetching is done.
  143.  * Use this for code that knows the list to be very short (empty
  144.  * or 1 entry) most of the time.
  145.  */
  146. #define    list_for_each(pos,head) \
  147.     for(pos = (head)->next; pos != (head); pos = pos->next)



  148. /**
  149.  * list_for_each_prev    -    iterate over a list backwards
  150.  * @pos:    the &struct list_head to use as a loop cursor.
  151.  * @head:    the head for your list.
  152.  */
  153. #define    list_for_each_prev(pos, head) \
  154.     for(pos = (head)->prev; pos != (head); pos = pos->prev)



  155. /**
  156.  * list_for_each_safe - iterate over a list safe against removal of list entry
  157.  * @pos:    the &struct list_head to use as a loop cursor.
  158.  * @n:        another &struct list_head to use as temporary storage
  159.  * @head:    the head for your list.
  160.  */
  161. #define list_for_each_safe(pos, n, head) \
  162.     for (pos = (head)->next, n = pos->next; pos != (head); \
  163.         pos = n, n = pos->next)

  164.     


  165. /**
  166.  * list_for_each_entry    -    iterate over list of given type
  167.  * @pos:    the type * to use as a loop cursor.
  168.  * @head:    the head for your list.
  169.  * @member:    the name of the list_struct within the struct.
  170.  */
  171. #define list_for_each_entry(pos, head, member)                \
  172.     for (pos = list_entry((head)->next, typeof(*pos), member);    \
  173.      &pos->member != (head);     \
  174.      pos = list_entry(pos->member.next, typeof(*pos), member))




  175. #ifdef __cplusplus
  176. }
  177. #endif

  178. #endif

二,测试
    1,测试代码

点击(此处)折叠或打开

  1. /*
  2.  * list begin
  3.  */

  4. typedef    struct _test_list
  5. {
  6.     char                name[20];
  7.     int                    age;
  8.     struct list_head    list;
  9. }test_list_t;

  10. struct list_head        t_list        = LIST_HEAD_INIT(t_list);

  11. static    void    _item_init(char * name,int    age)
  12. {
  13.     test_list_t    *item = (test_list_t*)malloc(sizeof(test_list_t));    

  14.     strcpy(item->name,name);
  15.     item->age = age;

  16.     list_add(&item->list,&t_list);
  17. }

  18. static    void    _item_destroy()
  19. {
  20.     test_list_t            *entry     = NULL;
  21.     struct list_head    *temp    = NULL;
  22.     struct list_head    *item    = NULL;

  23.     printf("destroy\n");
  24.     list_for_each_safe(item,temp,&t_list)
  25.     {
  26.         entry = list_entry(item, struct _test_list, list);
  27.         list_del(item);
  28.         printf("next : %p\t prev : %p\n",entry->list.next,entry->list.prev);
  29.         printf("name : %s\t age : %d\n",entry->name,entry->age);
  30.         free(entry);
  31.         printf("delete\n");
  32.         entry = NULL;
  33.     }
  34. }

  35. static    void    _item_display()
  36. {
  37.     test_list_t    *entry = NULL;

  38.     printf("display\n");
  39.     list_for_each_entry(entry, &t_list, list)
  40.     {
  41.         printf("name : %s\t age : %d\n",entry->name,entry->age);
  42.     }
  43. }

  44. static    void    list_oper(void)
  45. {
  46.     _item_init("wo",10);
  47.     _item_init("shi",20);
  48.     _item_init("zhong",30);
  49.     _item_init("guo",40);
  50.     _item_init("ren",50);

  51.     _item_display();

  52.     _item_destroy();
  53.     
  54. }

  55. void    test_list()
  56. {
  57.     list_oper();
  58. }

  59. /*
  60.  * list end
  61.  */

    2,测试结果
    

    3,注意事项
        a,在删除时,要注意指针问题。
            建议使用 list_for_each_safe,而不是 list_for_each_entry




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