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

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

# 0. 环境说明 #

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

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

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

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

#ifndef _LIST_H
    #define _LIST_H
    /* /usr/src/linux-headers-4.8.0-36-generic/include/linux/stddef.h */
    
    //求偏移量
    #define offsetof(TYPE, MEMBER)  ((size_t)&((TYPE *)0)->MEMBER)
    
    
    /* /usr/src/linux-headers-4.8.0-36-generic/include/linux/kernel.h */
    /** * 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. * */
    
    //小指针转大指针
    #define container_of(ptr, type, member) ({          \
        const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
        (type *)( (char *)__mptr - offsetof(type,member) );})
    
    
    /* /usr/src/linux-headers-4.8.0-36-generic/include/linux/types.h */
    struct list_head {
        struct list_head *next, *prev;
    };
    
    /* /usr/src/linux-headers-4.8.0-36-generic/include/linux/list.h */
    
    #define LIST_HEAD_INIT(name) { &(name), &(name) }
    
    
    //以下这个宏用来定义并且初始化头结点
    #define LIST_HEAD(name) \
        struct list_head name = LIST_HEAD_INIT(name)
    
    //这个函数不知道内核里面有没有，我自己加的
    static inline void node_init(struct list_head *node)
    {
        node->next = node;
        node->prev = node;
    }
    
    /* kernel 3.14 */
    static inline void __list_add(struct list_head *new,
                      struct list_head *prev,
                      struct list_head *next)
    {
        next->prev = new;
        new->next = next;
        new->prev = prev;
        prev->next = new;      // kernel 4.8中 这句话是 WRITE_ONCE(prev->next, new);
    }   
    
    
    /** * 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. */
    static inline void list_add(struct list_head *new, struct list_head *head)
    {
        __list_add(new, head, head->next); //头插
    }
    
    
    /** * 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. */
    static inline void list_add_tail(struct list_head *new, struct list_head *head)
    {
        __list_add(new, head->prev, head); //尾插
    }
    
    
    
    /* * 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! */
    static inline void __list_del(struct list_head * prev, struct list_head * next)
    {
        next->prev = prev;
        prev->next = next;       //WRITE_ONCE(prev->next, next);
    }
    
    
    static inline void list_del(struct list_head *entry)
    {
        __list_del(entry->prev, entry->next);
        node_init(entry); //add by me
        //entry->next = LIST_POISON1;
        //entry->prev = LIST_POISON2;
    }
    
    
    /** * list_empty - tests whether a list is empty * @head: the list to test. */
    static inline int list_empty(const struct list_head *head)
    {
        return head->next == head;
        //return READ_ONCE(head->next) == head;
    }   
    
    
    
    /** * list_for_each - iterate over a list * @pos: the &struct list_head to use as a loop cursor. * @head: the head for your list. */
    #define list_for_each(pos, head) \
        for (pos = (head)->next; pos != (head); pos = pos->next)
    
    
    
    
    /** * 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. */
    #define list_for_each_safe(pos, n, head) \
        for (pos = (head)->next, n = pos->next; pos != (head); \
            pos = n, n = pos->next)
    
    
    
    /** * 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. */
    #define list_entry(ptr, type, member) \
        container_of(ptr, type, member)
    
    /** * 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. */
    #define list_first_entry(ptr, type, member) \
        list_entry((ptr)->next, type, member)
    
    
    
    /** * list_next_entry - get the next element in list * @pos: the type * to cursor * @member: the name of the list_head within the struct. */
    #define list_next_entry(pos, member) \
        list_entry((pos)->member.next, typeof(*(pos)), member)
    
    /** * 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. */
    #define list_for_each_entry(pos, head, member)              \
        for (pos = list_first_entry(head, typeof(*pos), member);    \
             &pos->member != (head);                    \
             pos = list_next_entry(pos, member))    
    
    
    /** * 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. */
    #define list_for_each_entry_safe(pos, n, head, member)          \
        for (pos = list_first_entry(head, typeof(*pos), member),    \
            n = list_next_entry(pos, member);           \
             &pos->member != (head);                    \
             pos = n, n = list_next_entry(n, member))
    
    
    
    /** * 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. */
    
    //从pos指向的结构体开始遍历
    #define list_for_each_entry_from(pos, head, member)             \
        for (; &pos->member != (head);                  \
             pos = list_next_entry(pos, member))    
    
    
    
    /** * 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. */
    #define list_for_each_entry_safe_from(pos, n, head, member)             \
        for (n = list_next_entry(pos, member);                  \
             &pos->member != (head);                        \
             pos = n, n = list_next_entry(n, member))   
    
    
    
    /** * 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. */
    
    //从pos的下一个开始遍历
    #define list_for_each_entry_continue(pos, head, member)         \
        for (pos = list_next_entry(pos, member);            \
             &pos->member != (head);                    \
             pos = list_next_entry(pos, member))
    
    /** * 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. */
    #define list_for_each_entry_safe_continue(pos, n, head, member)         \
        for (pos = list_next_entry(pos, member),                \
            n = list_next_entry(pos, member);               \
             &pos->member != (head);                        \
             pos = n, n = list_next_entry(n, member))
    
    
    #endif

# 2. 接口设计 #

#ifndef _QUEUE_H
    #define _QUEUE_H
    #include "list.h"
    
    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));
        int (*is_empty)(struct queue_info *info);
    };
    
    void queue_init(struct queue_info *info,struct list_head * head);
    void queue_destroy(struct queue_info *info);
    
    #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 入队 ##

static void queue_push (struct queue_info *info, struct list_head *new_node)
    {
        list_add_tail(new_node,info->head);
    }

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

## 3.2 得到队首的元素 ##

struct list_head *queue_top(struct queue_info *info)
    {
        if (queue_is_empty(info)) {
            return NULL; //队列为空
        }
        else{
            return info->head->next;
        }   
    }

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

## 3.3 出队 ##

struct list_head *queue_pop(struct queue_info *info)                   
    {
        if (queue_is_empty(info)) {
            return NULL; //队列为空
        }
        else{
            struct list_head *temp = info->head->next;
            list_del(temp); //删除队列的首元素
            return temp;
        }
    }

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

## 3.4 遍历队列的每个元素 ##

static int queue_for_each(struct queue_info *info, void (*todo)(struct list_head *node))
    {
        if(queue_is_empty(info)){
            printf("the queue is empty\n");
            return -1;
        }
        else{
            struct list_head *pos = NULL;
            struct list_head *n = NULL;
            list_for_each_safe(pos, n, info->head)
                todo(pos);
            return 0;
        }
    }

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

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

## 3.5 队列的初始化 ##

void queue_init(struct queue_info *info,struct list_head * head)
    {
        info->head = head;
        node_init(head); //头结点的next和prev都指向自身
        info->push = queue_push;
        info->pop = queue_pop;
        info->top = queue_top;
        info->is_empty = queue_is_empty;
        info->for_each = queue_for_each;
    }

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

## 3.6 队列的析构 ##

void queue_destroy(struct queue_info *info)
    {
    }

我想了想，觉得此函数只能为空。理由是：  
1. 不需要回收空间，所以真的没啥可以做的；  
2. 本打算不断出队直到为空，发现出队是用户的事情，不需要越俎代庖。

# 4. 测试代码及结果 #

#include "stdio.h"
    #include "queue.h"
    
    #define NAME_MAX_LEN 20
    
    struct data_info {
        char name[NAME_MAX_LEN];
        int age;
        struct list_head list;
    };
    
    //此函数用于打印结点信息
    void  print_node(struct list_head *node)
    {
        struct data_info *pdata;
        pdata = container_of(node, struct data_info, list);
        printf("name:%s, age:%d\n",pdata->name, pdata->age);
    }
    
    int main(void)
    {
        struct data_info s[] = {
            {
       "A", 34},
            {
       "B", 42},
            {
       "C", 36},
            {
       "D", 100},
            {
       "E", 18},
        };
    
        struct list_head head;
        struct queue_info queue;
        queue_init(&queue,&head);
    
        //测试入队
        int i;
        for (i = 0; i < sizeof s/ sizeof s[0]; ++i) 
        {
            queue.push(&queue,&s[i].list);
        }
    
        //测试遍历
        queue.for_each(&queue,print_node);
    
        //测试top
        printf("top method\n");
    
        struct list_head *p_node = queue.top(&queue);
        if(p_node==NULL){
            printf("top test failed\n");
        }
        else{
            print_node(p_node);
        }
        //再次遍历，验证top并不是出队 
        queue.for_each(&queue,print_node);
    
        //测试出队
        while(!queue.is_empty(&queue)){
            p_node = queue.pop(&queue);
            printf("out queue:");
            print_node(p_node);
        }
    
        while(1);//单片机程序，没有操作系统，只能在这里死循环了 
    }

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

![这里写图片描述][SouthEast]

# 5. 需要注意的问题 #

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

![这里写图片描述][SouthEast 1]

【完】

[SouthEast]: /images/20220608/057d028697754d4eb61cd3e8324a9c6b.png
[SouthEast 1]: /images/20220608/78e2e13366d24a39a4aeab56c6d58d0e.png