Chinaunix首页 | 论坛 | 博客
  • 博客访问: 248630
  • 博文数量: 34
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 961
  • 用 户 组: 普通用户
  • 注册时间: 2013-07-11 17:19
个人简介

没有最好的语言,只有最适合的语言。

文章分类

全部博文(34)

文章存档

2016年(2)

2013年(32)

我的朋友

分类: LINUX

2013-09-17 20:05:20

linux 内核中的库文件里面对双链表的操作的算法都是很经典的
这几天专门阅读了里面的代码。为了加深对代码的理解程度,所以打算在用户态下
对里面的内容进行一些实现
因为我只是初步的测试一下里面的一些操作,所以我创建了一个list.h文件,在里面放入部分的的代码
我的list.h文件的代码如下所示:

点击(此处)折叠或打开

  1. /*
  2.  * 下面这些代码都是从文件中复制过来的,
  3.  * 只是复制了一些我下面用到的
  4.  *
  5.  */

  6. #define LIST_POISON1 ((void *) 0x00100100)
  7. #define LIST_POISON2 ((void *) 0x00200200)


  8. #define list_for_each(pos, head) \
  9.     for (pos = (head)->next; pos != (head); pos = pos->next)


  10. #define list_entry(ptr, type, member) \
  11.     ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
  12. #define list_for_each_safe(pos, n, head) \
  13.     for (pos = (head)->next, n = pos->next; pos != (head); \
  14.         pos = n, n = pos->next)


  15. struct list_head{
  16.     struct list_head *next,*prev;
  17. };


  18. void __list_add(struct list_head *new, struct list_head *prev, struct list_head *next)
  19. {
  20.     next->prev = new;
  21.     new->next = next;
  22.     new->prev = prev;
  23.     prev->next = new;
  24.  }


  25.  void INIT_LIST_HEAD(struct list_head *list)
  26.  {
  27.      list->next = list;
  28.      list->prev = list;
  29.  }


  30. void list_add_tail(struct list_head *new, struct list_head *head)
  31. {
  32.     __list_add(new, head->prev, head);
  33. }

  34. void __list_del(struct list_head * prev,struct list_head * next)
  35. {
  36.     next->prev=prev;
  37.     prev->next=next;
  38. }
  39. void list_del(struct list_head *entry)
  40. {
  41.     __list_del(entry->prev, entry->next);
  42.     entry->next = LIST_POISON1;
  43.     entry->prev = LIST_POISON2;
  44. }


下面的test_list.c代码是测试使用list.h中的一些操作

点击(此处)折叠或打开

  1. /*
  2.  * description: This program is test how to use
  3.  * the list.h
  4.  *
  5.  * author:chenshuanglin
  6.  * Date:2013/9/17
  7.  */

  8. #include <stdio.h>
  9. #include <stdlib.h>
  10. #include "list.h"
  11. #define N 10 //链表节点数

  12. typedef struct numlist{
  13.     int num; //数据
  14.     struct list_head list; //指向双链表前后结点的指针
  15. }NumNode;

  16. /*
  17.  * author:chenshuanglin
  18.  * description:This function is create a doubleList
  19.  *
  20.  */
  21. void createList(NumNode * head)
  22. {
  23.     int i;
  24.     NumNode * newNode; //每次申请链表结点时所使用的指针
  25.     printf("Please input 10 number: ");
  26.     for(i = 0 ; i < N ; i++)
  27.     {
  28.         newNode = (NumNode *)malloc(sizeof(NumNode));
  29.         scanf("%d",&newNode->num);
  30.         list_add_tail(&newNode->list,&head->list); //调用list.h中的添加节点的函数list_add_tail
  31.     }    
  32. }

  33. /*
  34.  * author:chenshuanglin
  35.  * description: Print this doubleList
  36.  */
  37. void printDoubleList(NumNode *head)
  38. {
  39.     int    i=1;
  40.     struct list_head * pos;
  41.     NumNode * num;
  42.     list_for_each(pos,&head->list) //调用list.h中的list_for_each函数进行遍历
  43.     {
  44.         num = list_entry(pos,NumNode,list); //调用list_entry函数得到相对应的节点
  45.         printf("Node %d's data: %d\n", i , num->num);
  46.         i++;
  47.     }
  48. }

  49. /*
  50.  * author:chenshuanglin
  51.  * description: delete number we want
  52.  *
  53.  */
  54. void deleteNum(NumNode * head,int number)
  55. {
  56.     struct list_head *pos,*n;
  57.     NumNode *p;
  58.     int i=1;
  59.     int judge = 0;
  60.     list_for_each_safe(pos,n,&head->list)
  61.     {
  62.         p = list_entry(pos,NumNode,list);
  63.         if(p->num == number)
  64.         {
  65.             judge = 1 ;
  66.             list_del(pos);
  67.             free(p);
  68.             printf("this node %d has removed from the doublelist...\n",i);
  69.         }
  70.         i++;
  71.     }
  72.     if(judge == 0 )
  73.     {
  74.         printf("NO FOUND!\n");
  75.     }

  76. }
  77. /*
  78.  * test Main()
  79.  */
  80. int main(void)
  81. {
  82.     NumNode head;
  83.     int number;
  84.     INIT_LIST_HEAD(&head.list);
  85.     createList(&head);
  86.     printDoubleList(&head);
  87.     printf("Please input the number you want to delete: ");
  88.     scanf("%d",&number);
  89.     deleteNum(&head,number);
  90.     printDoubleList(&head);
  91.     return 1;
  92. }

这个小例子可以方便大家学习list.h中的内容
阅读(8937) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~