队列的C语言实现（通过内核链表）

朱雀 2022-06-08 08:13 309阅读 0赞

0. 环境说明

本文的实验环境是：
win7操作系统+Keil 5 IDE.
非常适合嵌入式软件开发

1. 打造自己的“list.h”

在单片机程序开发中，有时候会用到队列。能否设计一个通用的队列呢？我想，可以把内核链表用起来。

以下代码是我从内核里面扒拉出来的，再稍微改改，就可以在工程中使用了。

  1. #ifndef _LIST_H
  2. #define _LIST_H
  3. /* /usr/src/linux-headers-4.8.0-36-generic/include/linux/stddef.h */
  5. //求偏移量
  6. #define offsetof(TYPE, MEMBER)  ((size_t)&((TYPE *)0)->MEMBER)
  9. /* /usr/src/linux-headers-4.8.0-36-generic/include/linux/kernel.h */
  10. /** * container_of - cast a member of a structure out to the containing structure * @ptr: the pointer to the member. * @type: the type of the container struct this is embedded in. * @member: the name of the member within the struct. * */
  12. //小指针转大指针
  13. #define container_of(ptr, type, member) ({          \
  14.     const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
  15.     (type *)( (char *)__mptr - offsetof(type,member) );})
  18. /* /usr/src/linux-headers-4.8.0-36-generic/include/linux/types.h */
  19. struct list_head {
  20.     struct list_head *next, *prev;
  21. };
  23. /* /usr/src/linux-headers-4.8.0-36-generic/include/linux/list.h */
  25. #define LIST_HEAD_INIT(name) { &(name), &(name) }
  28. //以下这个宏用来定义并且初始化头结点
  29. #define LIST_HEAD(name) \
  30.     struct list_head name = LIST_HEAD_INIT(name)
  32. //这个函数不知道内核里面有没有，我自己加的
  33. static inline void node_init(struct list_head *node)
  34. {
  35.     node->next = node;
  36.     node->prev = node;
  37. }
  39. /* kernel 3.14 */
  40. static inline void __list_add(struct list_head *new,
  41.                   struct list_head *prev,
  42.                   struct list_head *next)
  43. {
  44.     next->prev = new;
  45.     new->next = next;
  46.     new->prev = prev;
  47.     prev->next = new;      // kernel 4.8中 这句话是 WRITE_ONCE(prev->next, new);
  48. }   
  51. /** * list_add - add a new entry * @new: new entry to be added * @head: list head to add it after * * Insert a new entry after the specified head. * This is good for implementing stacks. */
  52. static inline void list_add(struct list_head *new, struct list_head *head)
  53. {
  54.     __list_add(new, head, head->next); //头插
  55. }
  58. /** * list_add_tail - add a new entry * @new: new entry to be added * @head: list head to add it before * * Insert a new entry before the specified head. * This is useful for implementing queues. */
  59. static inline void list_add_tail(struct list_head *new, struct list_head *head)
  60. {
  61.     __list_add(new, head->prev, head); //尾插
  62. }
  66. /* * Delete a list entry by making the prev/next entries * point to each other. * * This is only for internal list manipulation where we know * the prev/next entries already! */
  67. static inline void __list_del(struct list_head * prev, struct list_head * next)
  68. {
  69.     next->prev = prev;
  70.     prev->next = next;       //WRITE_ONCE(prev->next, next);
  71. }
  74. static inline void list_del(struct list_head *entry)
  75. {
  76.     __list_del(entry->prev, entry->next);
  77.     node_init(entry); //add by me
  78.     //entry->next = LIST_POISON1;
  79.     //entry->prev = LIST_POISON2;
  80. }
  83. /** * list_empty - tests whether a list is empty * @head: the list to test. */
  84. static inline int list_empty(const struct list_head *head)
  85. {
  86.     return head->next == head;
  87.     //return READ_ONCE(head->next) == head;
  88. }   
  92. /** * list_for_each - iterate over a list * @pos: the &struct list_head to use as a loop cursor. * @head: the head for your list. */
  93. #define list_for_each(pos, head) \
  94.     for (pos = (head)->next; pos != (head); pos = pos->next)
  99. /** * list_for_each_safe - iterate over a list safe against removal of list entry * @pos: the &struct list_head to use as a loop cursor. * @n: another &struct list_head to use as temporary storage * @head: the head for your list. */
  100. #define list_for_each_safe(pos, n, head) \
  101.     for (pos = (head)->next, n = pos->next; pos != (head); \
  102.         pos = n, n = pos->next)
  106. /** * list_entry - get the struct for this entry * @ptr: the &struct list_head pointer. * @type: the type of the struct this is embedded in. * @member: the name of the list_head within the struct. */
  107. #define list_entry(ptr, type, member) \
  108.     container_of(ptr, type, member)
  110. /** * list_first_entry - get the first element from a list * @ptr: the list head to take the element from. * @type: the type of the struct this is embedded in. * @member: the name of the list_head within the struct. * * Note, that list is expected to be not empty. */
  111. #define list_first_entry(ptr, type, member) \
  112.     list_entry((ptr)->next, type, member)
  116. /** * list_next_entry - get the next element in list * @pos: the type * to cursor * @member: the name of the list_head within the struct. */
  117. #define list_next_entry(pos, member) \
  118.     list_entry((pos)->member.next, typeof(*(pos)), member)
  120. /** * list_for_each_entry - iterate over list of given type * @pos: the type * to use as a loop cursor. * @head: the head for your list. * @member: the name of the list_head within the struct. */
  121. #define list_for_each_entry(pos, head, member)              \
  122.     for (pos = list_first_entry(head, typeof(*pos), member);    \
  123.          &pos->member != (head);                    \
  124.          pos = list_next_entry(pos, member))    
  127. /** * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry * @pos: the type * to use as a loop cursor. * @n: another type * to use as temporary storage * @head: the head for your list. * @member: the name of the list_head within the struct. */
  128. #define list_for_each_entry_safe(pos, n, head, member)          \
  129.     for (pos = list_first_entry(head, typeof(*pos), member),    \
  130.         n = list_next_entry(pos, member);           \
  131.          &pos->member != (head);                    \
  132.          pos = n, n = list_next_entry(n, member))
  136. /** * list_for_each_entry_from - iterate over list of given type from the current point * @pos: the type * to use as a loop cursor. * @head: the head for your list. * @member: the name of the list_head within the struct. * * Iterate over list of given type, continuing from current position. */
  138. //从pos指向的结构体开始遍历
  139. #define list_for_each_entry_from(pos, head, member)             \
  140.     for (; &pos->member != (head);                  \
  141.          pos = list_next_entry(pos, member))    
  145. /** * list_for_each_entry_safe_from - iterate over list from current point safe against removal * @pos: the type * to use as a loop cursor. * @n: another type * to use as temporary storage * @head: the head for your list. * @member: the name of the list_head within the struct. * * Iterate over list of given type from current point, safe against * removal of list entry. */
  146. #define list_for_each_entry_safe_from(pos, n, head, member)             \
  147.     for (n = list_next_entry(pos, member);                  \
  148.          &pos->member != (head);                        \
  149.          pos = n, n = list_next_entry(n, member))   
  153. /** * list_for_each_entry_continue - continue iteration over list of given type * @pos: the type * to use as a loop cursor. * @head: the head for your list. * @member: the name of the list_head within the struct. * * Continue to iterate over list of given type, continuing after * the current position. */
  155. //从pos的下一个开始遍历
  156. #define list_for_each_entry_continue(pos, head, member)         \
  157.     for (pos = list_next_entry(pos, member);            \
  158.          &pos->member != (head);                    \
  159.          pos = list_next_entry(pos, member))
  161. /** * list_for_each_entry_safe_continue - continue list iteration safe against removal * @pos: the type * to use as a loop cursor. * @n: another type * to use as temporary storage * @head: the head for your list. * @member: the name of the list_head within the struct. * * Iterate over list of given type, continuing after current point, * safe against removal of list entry. */
  162. #define list_for_each_entry_safe_continue(pos, n, head, member)         \
  163.     for (pos = list_next_entry(pos, member),                \
  164.         n = list_next_entry(pos, member);               \
  165.          &pos->member != (head);                        \
  166.          pos = n, n = list_next_entry(n, member))
  169. #endif

2. 接口设计

  1. #ifndef _QUEUE_H
  2. #define _QUEUE_H
  3. #include "list.h"
  5. struct queue_info {
  6.     struct list_head *head;
  7.     void (*push)(struct queue_info *info, struct list_head *new_node);
  8.     struct list_head *(*top)(struct queue_info *info);
  9.     struct list_head *(*pop)(struct queue_info *info);
  10.     int (*for_each)(struct queue_info *info, void (*todo)(struct list_head *node));
  11.     int (*is_empty)(struct queue_info *info);
  12. };
  14. void queue_init(struct queue_info *info,struct list_head * head);
  15. void queue_destroy(struct queue_info *info);
  17. #endif

struct queue_info中，首先有一个struct list_head *head，这是一个指针，指向链表的头结点。这个头结点需要用户分配空间；其次是队列具有的方法（指向函数的指针）。

  • void (*push)(struct queue_info *info, struct list_head *new_node);
    入队操作
  • struct list_head *(*top)(struct queue_info *info);
    得到队列的首元素（有别于出队）
  • struct list_head *(*pop)(struct queue_info *info);
    出队
  • int (*for_each)(struct queue_info *info, void (*todo)(struct list_head *node));
    遍历队列，todo由用户实现
  • int (*is_empty)(struct queue_info *info);
    判断队列是否为空

3. 具体实现

3.1 入队

  1. static void queue_push (struct queue_info *info, struct list_head *new_node)
  2. {
  3.     list_add_tail(new_node,info->head);
  4. }

直接调用内核链表的尾插函数list_add_tail就行。

3.2 得到队首的元素

  1. struct list_head *queue_top(struct queue_info *info)
  2. {
  3.     if (queue_is_empty(info)) {
  4.         return NULL; //队列为空
  5.     }
  6.     else{
  7.         return info->head->next;
  8.     }   
  9. }

因为是通用队列，无法预测队列中元素的数据形态，所以返回指向struct list_head的指针。为了得到数据，需要用户自己转换（通过宏container_of）.

3.3 出队

  1. struct list_head *queue_pop(struct queue_info *info)                   
  2. {
  3.     if (queue_is_empty(info)) {
  4.         return NULL; //队列为空
  5.     }
  6.     else{
  7.         struct list_head *temp = info->head->next;
  8.         list_del(temp); //删除队列的首元素
  9.         return temp;
  10.     }
  11. }

注意，list_del(temp);这句话仅仅使队首元素脱离链表，队首元素的空间需要用户自己回收。

3.4 遍历队列的每个元素

  1. static int queue_for_each(struct queue_info *info, void (*todo)(struct list_head *node))
  2. {
  3.     if(queue_is_empty(info)){
  4.         printf("the queue is empty\n");
  5.         return -1;
  6.     }
  7.     else{
  8.         struct list_head *pos = NULL;
  9.         struct list_head *n = NULL;
  10.         list_for_each_safe(pos, n, info->head)
  11.             todo(pos);
  12.         return 0;
  13.     }
  14. }

如果队列为空，打印出错信息并返回-1；否则，调用用户传入的todo函数，对每个元素进行操作（list_for_each_safe是内核链表的安全遍历，用普通遍历也是可以的，因为todo函数一般不会进行删除。删除没有道理啊，我实在想不出应用场景）。

其实，我设计这个接口的初衷是为了测试，比如打印队列每个元素，看看入队顺序是否正确等。

3.5 队列的初始化

  1. void queue_init(struct queue_info *info,struct list_head * head)
  2. {
  3.     info->head = head;
  4.     node_init(head); //头结点的next和prev都指向自身
  5.     info->push = queue_push;
  6.     info->pop = queue_pop;
  7.     info->top = queue_top;
  8.     info->is_empty = queue_is_empty;
  9.     info->for_each = queue_for_each;
  10. }

此函数应该在最初调用。用户需要定义struct queue_info结构体和struct list_head结构体，然后传入二者的地址。

3.6 队列的析构

  1. void queue_destroy(struct queue_info *info)
  2. {
  3. }

我想了想，觉得此函数只能为空。理由是：

  1. 不需要回收空间，所以真的没啥可以做的；
  2. 本打算不断出队直到为空，发现出队是用户的事情，不需要越俎代庖。

4. 测试代码及结果

  1. #include "stdio.h"
  2. #include "queue.h"
  4. #define NAME_MAX_LEN 20
  6. struct data_info {
  7.     char name[NAME_MAX_LEN];
  8.     int age;
  9.     struct list_head list;
  10. };
  12. //此函数用于打印结点信息
  13. void  print_node(struct list_head *node)
  14. {
  15.     struct data_info *pdata;
  16.     pdata = container_of(node, struct data_info, list);
  17.     printf("name:%s, age:%d\n",pdata->name, pdata->age);
  18. }
  20. int main(void)
  21. {
  22.     struct data_info s[] = {
  23.         {
  24.    "A", 34},
  25.         {
  26.    "B", 42},
  27.         {
  28.    "C", 36},
  29.         {
  30.    "D", 100},
  31.         {
  32.    "E", 18},
  33.     };
  35.     struct list_head head;
  36.     struct queue_info queue;
  37.     queue_init(&queue,&head);
  39.     //测试入队
  40.     int i;
  41.     for (i = 0; i < sizeof s/ sizeof s[0]; ++i) 
  42.     {
  43.         queue.push(&queue,&s[i].list);
  44.     }
  46.     //测试遍历
  47.     queue.for_each(&queue,print_node);
  49.     //测试top
  50.     printf("top method\n");
  52.     struct list_head *p_node = queue.top(&queue);
  53.     if(p_node==NULL){
  54.         printf("top test failed\n");
  55.     }
  56.     else{
  57.         print_node(p_node);
  58.     }
  59.     //再次遍历，验证top并不是出队 
  60.     queue.for_each(&queue,print_node);
  62.     //测试出队
  63.     while(!queue.is_empty(&queue)){
  64.         p_node = queue.pop(&queue);
  65.         printf("out queue:");
  66.         print_node(p_node);
  67.     }
  69.     while(1);//单片机程序，没有操作系统，只能在这里死循环了 
  70. }

在keil5上调试（use simulator），测试结果截图如下：

这里写图片描述

5. 需要注意的问题

普通的编译器是无法编译list.h的，必须支持gnu语法才行。对于Keil，可以添加对gnu的支持，如下图，输入--gnu.

这里写图片描述

【完】

发表评论

表情：
评论列表 （有 0 条评论，309人围观）

还没有评论，来说两句吧...

相关阅读

    相关 c语言实现链队列的基本功能

    链队列，实际上是一个带有头指针和尾指针的单链表，头指针指向头节点（不存放数据），尾指针指向队尾节点，虽然用头指针可以确定一个单链表，但是插入操作是在队尾进行，如果没有尾指针，会

    秒速五厘米秒速五厘米/ 0 赞/ 269 阅读