首页 > 其他 > 详细

代码片段----内核链表使用一例

时间：2014-03-06 22:25:43      阅读：464      评论：0      收藏：0      [点我收藏+]

 

Makefile

bubuko.com,布布扣
CC=gcc


main:main.o


clean:
    $(RM) *.o main

.PHONY:clean
bubuko.com,布布扣

 

main.c

bubuko.com,布布扣
#include "list.h"
#include <stdio.h>


typedef struct 
{
    unsigned long gp;  // (group<<3)|(pnum&0x7)
    unsigned long on;  // on or off
    unsigned long delay;
    unsigned long count;
    struct  list_head p;
}GPIO_NODE;

int main(int argc, const char *argv[])
{

    GPIO_NODE *a1;
    GPIO_NODE *a2;
    GPIO_NODE *a3;
    GPIO_NODE *a4;
    struct list_head *q = NULL;
    struct list_head *q1 = NULL;
    GPIO_NODE *a5;

    LIST_HEAD(gpio_list);

    a1 = (GPIO_NODE *)malloc(sizeof(GPIO_NODE));
    a2 = (GPIO_NODE *)malloc(sizeof(GPIO_NODE));
    a3 = (GPIO_NODE *)malloc(sizeof(GPIO_NODE));
    a4 = (GPIO_NODE *)malloc(sizeof(GPIO_NODE));

    a1->gp = 1;
    a1->on = 1;
    a1->delay = 1;
    a1->count = 1;

    a2->gp = 2;
    a2->on = 2;
    a2->delay = 2;
    a2->count = 2;

    a3->gp = 3;
    a3->on = 3;
    a3->delay = 3;
    a3->count = 3;


    a4->gp = 4;
    a4->on = 4;
    a4->delay = 4;
    a4->count = 4;

    list_add_tail(&(a1->p), &gpio_list);
    list_add_tail(&(a2->p), &gpio_list);
    list_add_tail(&(a3->p), &gpio_list);
    list_add_tail(&(a4->p), &gpio_list);

    list_for_each_safe(q, q1, &gpio_list) {
        a5 = list_entry(q, GPIO_NODE, p); 
        if(a5->gp > 3)
        {
            printf("a5->gp = %d\n", a5->gp);
            printf("a5->on = %d\n", a5->on);
            printf("a5->delay = %d\n", a5->delay);
            printf("a5->count = %d\n", a5->count);

            if (!list_empty(&gpio_list))
            {
                list_del(q);
                printf("free node %d\n", a5->gp);
                free(a5);
            }
        }
    }

    list_for_each_safe(q, q1, &gpio_list)
    {
        a5 = list_entry(q, GPIO_NODE, p);

        printf("a5->gp = %d\n", a5->gp);
        printf("a5->on = %d\n", a5->on);
        printf("a5->delay = %d\n", a5->delay);
        printf("a5->count = %d\n", a5->count);

        if (!list_empty(&gpio_list))
        {
            list_del(q);
            printf("free node %d\n", a5->gp);
            free(a5);
        }
    }


    return 0;
}
bubuko.com,布布扣

 

list.h

http://files.cnblogs.com/pengdonglin137/list.rar

 

参考：http://blog.csdn.net/xnwyd/article/details/7359373

Linux内核链表的核心思想是：在用户自定义的结构A中声明list_head类型的成员p，这样每个结构类型为A的变量a中，都拥有同样的成员p，如下：

struct A{

int property;

struct list_head p;

}

其中，list_head结构类型定义如下：

struct list_head {

struct list_head *next,*prev;

};

list_head拥有两个指针成员，其类型都为list_head，分别为前驱指针prev和后驱指针next。

假设：

（1）多个结构类型为A的变量a1...an，其list_head结构类型的成员为p1...pn

（2）一个list_head结构类型的变量head，代表头节点

使：

（1）head.next= p1 ; head.prev = pn

（2）p1.prev = head，p1.next = p2;

（3）p2.prev= p1 , p2.next = p3;

…

（n）pn.prev= pn-1 , pn.next = head

以上，则构成了一个循环链表。

因p是嵌入到a中的，p与a的地址偏移量可知，又因为head的地址可知，所以每个结构类型为A的链表节点a1...an的地址也是可以计算出的，从而可实现链表的遍历，在此基础上，则可以实现链表的各种操作。

下面是从linux内核中移植出来的简单链表，list.h和list.c:

list.h:

[cpp] view plaincopy
  1. #ifndef _INIT_LIST_H_  
  2. #define _INIT_LIST_H_  
  3.   
  4. #ifndef offsetof  
  5. /* Offset of member MEMBER in a struct of type TYPE. */  
  6. #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)  
  7. #endif  
  8.   
  9. struct listnode  
  10. {  
  11.     struct listnode *next;  
  12.     struct listnode *prev;  
  13. };  
  14.   
  15. #define node_to_item(node, container, member) \  
  16.     (container *) (((char*) (node)) - offsetof(container, member))  
  17.   
  18. #define list_declare(name) \  
  19.     struct listnode name = { \  
  20.         .next = &name, \  
  21.         .prev = &name, \  
  22.     }  
  23.   
  24. #define list_for_each(node, list) \  
  25.     for (node = (list)->next; node != (list); node = node->next)  
  26.   
  27. #define list_for_each_reverse(node, list) \  
  28.     for (node = (list)->prev; node != (list); node = node->prev)  
  29.   
  30. void list_init(struct listnode *list);  
  31. void list_add_tail(struct listnode *list, struct listnode *item);  
  32. void list_remove(struct listnode *item);  
  33.   
  34. #define list_empty(list) ((list) == (list)->next)  
  35. #define list_head(list) ((list)->next)  
  36. #define list_tail(list) ((list)->prev)  
  37.   
  38. #endif  


list.c：

[cpp] view plaincopy
  1. #include "list.h"  
  2.   
  3. void list_init(struct listnode *node)  
  4. {  
  5.     node->next = node;  
  6.     node->prev = node;  
  7. }  
  8.   
  9. void list_add_tail(struct listnode *head, struct listnode *item)  
  10. {  
  11.     item->next = head;  
  12.     item->prev = head->prev;  
  13.     head->prev->next = item;  
  14.     head->prev = item;  
  15. }  
  16.   
  17. void list_remove(struct listnode *item)  
  18. {  
  19.     item->next->prev = item->prev;  
  20.     item->prev->next = item->next;  
  21. }  


测试代码list_test.c:

[cpp] view plaincopy
  1. #include<stdio.h>  
  2. #include<stdlib.h>  
  3. #include "list.h"  
  4.   
  5. #define STUDENT_FREE_MEMORY  
  6.   
  7. //声明链表节点  
  8. typedef struct {  
  9.     int id;  
  10.     char *name;  
  11.     struct listnode _list;  
  12. }student;  
  13.   
  14. //遍历函数指针  
  15. typedef void (*student_foreach_fun)(student *stu,void *data);  
  16.   
  17.   
  18. //声明链表  
  19. static list_declare(student_list);  
  20.   
  21. //添加节点  
  22. int student_add(struct listnode *list,student *stu)  
  23. {  
  24.     list_init(&stu->_list);  
  25.     list_add_tail(list,&stu->_list);   
  26. }  
  27.   
  28. //删除节点，释放节点空间  
  29. int student_del(struct listnode *list,int id)  
  30. {  
  31.     struct listnode *node;  
  32.     student *stu;  
  33.     list_for_each(node,list){  
  34.         stu = node_to_item(node,student,_list);  
  35.         if(id == stu->id){  
  36.             printf("list_del, id:%d,name:%s\n",stu->id,stu->name);  
  37.             list_remove(node);  
  38. #ifdef STUDENT_FREE_MEMORY    
  39.             //释放节点空间  
  40.             free(stu);  
  41.             stu = NULL;  
  42. #endif  
  43.             return 1;  
  44.               
  45.         }  
  46.           
  47.     }  
  48.   
  49.     return 0;  
  50. }  
  51.   
  52. //节点遍历  
  53. void student_foreach(struct listnode *list,student_foreach_fun fun,void *data)  
  54. {  
  55.     struct listnode *node;  
  56.     student *stu;  
  57.     list_for_each(node,list){  
  58.         stu = node_to_item(node,student,_list);  
  59.         fun(stu,data);  
  60.     }  
  61.   
  62. }  
  63.   
  64. //打印节点信息  
  65. void student_print(student *stu,void *data)  
  66. {  
  67.     printf("id:%d,name:%s\n",stu->id,stu->name);  
  68. }  
  69.   
  70. int main()  
  71. {  
  72.     int i,len;  
  73.     student *stu;  
  74.     char *stu_name[]={"tonny","andy","michael","leslie","john"};  
  75.       
  76.       
  77.     len = sizeof(stu_name)/sizeof(stu_name[0]);  
  78.     //添加节点  
  79.     for(i=0;i<len;i++){  
  80.         stu = calloc(1,sizeof(student));  
  81.         stu->id = i + 1;  
  82.         stu->name = stu_name[i];  
  83.   
  84.         student_add(&student_list,stu);  
  85.     }  
  86.   
  87.     //打印所有节点  
  88.     student_foreach(&student_list,student_print,(void *)0);  
  89.       
  90.     //删除节点  
  91.     student_del(&student_list,1);  
  92.     student_foreach(&student_list,student_print,(void *)0);  
  93.   
  94.     //删除节点  
  95.     student_del(&student_list,5);  
  96.     student_foreach(&student_list,student_print,(void *)0);  
  97.       
  98.     return 0;  
  99.       
  100.   
  101. }  


Makefile:

[cpp] view plaincopy
    1. TARGET=list_test  
    2. SRC=list_test.c list.c  
    3. #SRC=$(wildcard *.c)  
    4. OBJ=$(SRC:.c=.o)  
    5. CFLAGS=-g -Wall -o  
    6.   
    7. $(TARGET):$(SRC)  
    8.     gcc $(SRC) $(CFLAGS) $(TARGET)  
    9. clean:  
    10.     rm $(OBJ) $(TARGET)   

代码片段----内核链表使用一例,布布扣,bubuko.com

代码片段----内核链表使用一例

原文：http://www.cnblogs.com/pengdonglin137/p/3583896.html
踩
(0)
赞
(0)
   
举报
评论 一句话评论（0）
分享档案
更多>
2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)
最新文章
更多>
教程昨日排行
更多>
友情链接
汇智网   PHP教程   插件网  
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣，分享程序人生！