C语言实现FIFO

小咪咪 2022-12-27 02:00 133阅读 0赞

1.  private\_info.c

//
    // Created by oceanstar on 2020/12/7.
    //
    
    #include "acl_fifo.h"
    #include <stdlib.h>
    #include <assert.h>
    
    
    static void *fifo_iter_head(ACL_ITER *iter, struct ACL_FIFO *fifo){
        
        ACL_FIFO_INFO *ptr;
    
        iter->dlen = -1;
        iter->klen = -1;
        iter->key = NULL;
        iter->i = 0;
        iter->size = fifo->cnt;
    
        iter->ptr = ptr = fifo->head;
        iter->data = ptr ? ptr->data : NULL;
        return (iter->ptr);
    }
    
    
    static void *fifo_iter_next(ACL_ITER *iter, struct ACL_FIFO *fifo){
        
        ACL_FIFO_INFO  *ptr;
    
        ptr = (ACL_FIFO_INFO *) iter->ptr;
        iter->ptr = ptr = ptr ? ptr->next : NULL;
        if (ptr){
        
            iter->data = ptr->data;
            iter->i++;
        }else{
        
            iter->data = NULL;
        }
    
        return ptr;
    }
    
    static void *fifo_iter_tail(ACL_ITER *iter, struct ACL_FIFO *fifo){
        
        ACL_FIFO_INFO  *ptr;
    
        iter->dlen = -1;
        iter->key = NULL;
        iter->klen = -1;
        iter->size = fifo->cnt;
    
        iter->i = fifo->cnt - 1;
        iter->ptr = ptr = fifo->tail;
        iter->data = ptr ? ptr->data: NULL;
    
        return iter;
    }
    
    static void *fifo_iter_prev(ACL_ITER *iter, struct ACL_FIFO *fifo){
        
        ACL_FIFO_INFO  *ptr;
    
        ptr = iter->ptr;  // 当前指针指向的条目
        iter->ptr = ptr ? ptr->prev : NULL;  // 如果当前指针不为NULL， 拿到当前指针的前一项
        if(ptr){
          // 前一项不为NULL
            iter->data = ptr->data;
            iter->i--;
        }else{
        
            iter->data = NULL;
        }
    
        return ptr;
    }
    static ACL_FIFO_INFO *fifo_iter_info(ACL_ITER *iter, struct ACL_FIFO *fifo)
    {
        
        return (iter->ptr ? (ACL_FIFO_INFO*) iter->ptr : NULL);
    }
    
    void private_fifo_init(ACL_FIFO *fifo)
    {
        
        fifo->head = NULL;
        fifo->tail = NULL;
        fifo->cnt = 0;
    
        fifo->iter_head = fifo_iter_head;
        fifo->iter_next = fifo_iter_next;
        fifo->iter_tail = fifo_iter_tail;
        fifo->iter_prev = fifo_iter_prev;
        fifo->iter_info = fifo_iter_info;
    }
    
    ACL_FIFO *private_fifo_new(void){
        
        ACL_FIFO *fifo;
    
        fifo = (ACL_FIFO *) malloc(sizeof(*fifo));
        fifo->head = NULL;
        fifo->tail = NULL;
        fifo->cnt = 0;
    
        fifo->iter_head = fifo_iter_head;
        fifo->iter_next = fifo_iter_next;
        fifo->iter_tail = fifo_iter_tail;
        fifo->iter_prev = fifo_iter_prev;
    
    
        return (fifo);
    }
    
    // 尾插
    ACL_FIFO_INFO *private_fifo_push(ACL_FIFO *fifo, void *data){
        
        assert(fifo != NULL);
    
        // 1. 构造填充条目
        ACL_FIFO_INFO *info;
    
        info = (ACL_FIFO_INFO *) malloc(sizeof(*info));
        info->data = data;
    
        //2.指定链接
        if(fifo->tail == NULL){
        
            info->prev = info->next = NULL;
            fifo->head = fifo->tail = info;
        }else{
        
            fifo->tail->next = info;
            info->prev = fifo->tail;
            info->next = NULL;
            fifo->tail = info;
        }
    
        fifo->cnt++;
        return (info);
    }
    
    // 弹出头部
    void *private_fifo_pop(ACL_FIFO *fifo)
    {
        
        ACL_FIFO_INFO *info;
        void *data;
    
        if (fifo->head == NULL)
            return (NULL);
    
        info = fifo->head;
        if (fifo->head->next) {
        
            fifo->head->next->prev = NULL;
            fifo->head = fifo->head->next;
        } else {
        
            fifo->head = fifo->tail = NULL;
        }
        data = info->data;
        free(info);
        fifo->cnt--;
        return (data);
    }
    
    void private_fifo_free(ACL_FIFO *fifo, void (*free_fn)(void *))
    {
        
        void *data;
    
        while ((data = private_fifo_pop(fifo)) != NULL) {
        
            if (free_fn)
                free_fn(data);
        }
        free(fifo);
    }
    void private_delete_info(ACL_FIFO *fifo, ACL_FIFO_INFO *info){
        
        assert(fifo != NULL && info != NULL);
    
        //1. 将这个info上面的指针都断掉
        if(info->prev){
        
            info->prev->next = info->next;
        }else{
             //前面没有info，说明是头指针。
            fifo->head = info->next;  //那么只需要将fifo.head指向当前info的next即可
        }
    
        if(info->next){
        
            info->next->prev = info->prev;
        }else{
        
            fifo->tail = info->prev;
        }
    
        //2. 释放info
        free(info);
        fifo->cnt--;
    }
    
    
    void *private_fifo_head(ACL_FIFO *fifo)
    {
        
        if (fifo->head)
            return (fifo->head->data);
        else
            return (NULL);
    }
    
    void *private_fifo_tail(ACL_FIFO *fifo)
    {
        
        if (fifo->tail)
            return (fifo->tail->data);
        else
            return (NULL);
    }
    
    int private_fifo_size(ACL_FIFO *fifo)
    {
        
        if (fifo)
            return (fifo->cnt);
        else
            return (0);
    }

1.  private\_info.h

#pragma once
    
    #include "acl_fifo.h"
    
    void private_fifo_init(ACL_FIFO *fifo);
    ACL_FIFO *private_fifo_new(void);
    void private_fifo_free(ACL_FIFO *fifo, void (*free_fn)(void *));
    ACL_FIFO_INFO *private_fifo_push(ACL_FIFO *fifo, void *data);
    void *private_fifo_pop(ACL_FIFO *fifo);
    void private_delete_info(ACL_FIFO *fifo, ACL_FIFO_INFO *info);
    void *private_fifo_head(ACL_FIFO *fifo);
    void *private_fifo_tail(ACL_FIFO *fifo);
    int private_fifo_size(ACL_FIFO *fifo);

1.  acl\_fifo.h

#pragma once
    
    #include "acl_iterator.h"
    
    typedef struct ACL_FIFO_INFO ACL_FIFO_INFO;
    typedef struct ACL_FIFO ACL_FIFO;
    
    struct ACL_FIFO_INFO {
        
        void *data;
        ACL_FIFO_INFO *prev;
        ACL_FIFO_INFO *next;
    };
    
    
    struct ACL_FIFO {
        
        ACL_FIFO_INFO *head;
        ACL_FIFO_INFO *tail;
        int   cnt;
    
        /* 添加及弹出 */
    
        /* 向队列尾部添加动态对象 */
        void  (*push_back)(struct ACL_FIFO*, void*);
        /* 向队列头部添加动态对象 */
        void  (*push_front)(struct ACL_FIFO*, void*);
        /* 弹出队列尾部动态对象 */
        void *(*pop_back)(struct ACL_FIFO*);
        /* 弹出队列头部动态对象 */
        void *(*pop_front)(struct ACL_FIFO*);
    
        /* for acl_iterator */
    
        /* 取迭代器头函数 */
        void *(*iter_head)(ACL_ITER*, struct ACL_FIFO*);
        /* 取迭代器下一个函数 */
        void *(*iter_next)(ACL_ITER*, struct ACL_FIFO*);
        /* 取迭代器尾函数 */
        void *(*iter_tail)(ACL_ITER*, struct ACL_FIFO*);
        /* 取迭代器上一个函数 */
        void *(*iter_prev)(ACL_ITER*, struct ACL_FIFO*);
        /* 取迭代器关联的当前容器成员结构对象 */
        ACL_FIFO_INFO *(*iter_info)(ACL_ITER*, struct ACL_FIFO*);
    };
    
    
    typedef struct ACL_FIFO_ITER ACL_FIFO_ITER;
    struct ACL_FIFO_ITER {
        
        ACL_FIFO_INFO *ptr;
    };
    /**
     * 遍历 ACL_FIFO
     * @param iter {ACL_FIFO_ITER}
     * @param fifo {ACL_FIFO}
     * */
    #define	ACL_FIFO_FOREACH(iter, fifo_ptr) \
    	for ((iter).ptr = (fifo_ptr)->head; (iter).ptr; (iter).ptr = (iter).ptr->next)
    #define	acl_fifo_foreach	ACL_FIFO_FOREACH
    
    #define	ACL_FIFO_FOREACH_REVERSE(iter, fifo_ptr) \
    	for ((iter).ptr = (fifo_ptr)->tail; (iter).ptr; (iter).ptr = (iter).ptr->prev)
    #define	acl_fifo_foreach_reverse	ACL_FIFO_FOREACH_REVERSE
    
    /**
     * 获得当前 iter 所包含的对象地址
     * @param iter {ACL_FIFO_ITER}
     */
    #define	ACL_FIFO_ITER_VALUE(iter)	((iter).ptr->data)
    #define	acl_fifo_iter_value		ACL_FIFO_ITER_VALUE

1.  acl\_iterator.h

#pragma once
    
    
    typedef struct ACL_ITER ACL_ITER;
    
    
    typedef struct ACL_ITER ACL_ITER;
    
    /**
     * ACL 库中数据结构用的通用迭代器结构定义
     */
    struct ACL_ITER {
        
        void *ptr;		/**< 迭代器指针, 与容器相关 */
        void *data;		/**< 用户数据指针 */
        int   dlen;		/**< 用户数据长度, 实现者可设置此值也可不设置 */
        const char *key;	/**< 若为哈希表的迭代器, 则为哈希键值地址 */
        int   klen;		/**< 若为ACL_BINHASH迭代器, 则为键长度 */
        int   i;		/**< 当前迭代器在容器中的位置索引 */
        int   size;		/**< 当前容器中元素总个数 */
    };
    
    /**
     * 正向遍历容器中元素
     * @param iter {ACL_ITER}
     * @param container {void*} 容器地址
     * @examples: samples/iterator/
     */
    #define	ACL_FOREACH(iter, container)  \
            for ((container)->iter_head(&(iter), (container));  \
                 (iter).ptr;  \
                 (container)->iter_next(&(iter), (container)))
    
    /**
     * 反向遍历容器中元素
     * @param iter {ACL_ITER}
     * @param container {void*} 容器地址
     * @examples: samples/iterator/
     */
    #define	ACL_FOREACH_REVERSE(iter, container)  \
            for ((container)->iter_tail(&(iter), (container));  \
                 (iter).ptr;  \
                 (container)->iter_prev(&(iter), (container)))
    
    /**
     * 获得当前迭代指针与某容器关联的成员结构类型对象
     * @param iter {ACL_ITER}
     * @param container {void*} 容器地址
     */
    #define	ACL_ITER_INFO(iter, container)  \
    	(container)->iter_info(&(iter), (container))
    
    #define	acl_foreach_reverse	ACL_FOREACH_REVERSE
    #define	acl_foreach		ACL_FOREACH
    #define	acl_iter_info		ACL_ITER_INFO

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]

使用：

#include <stdio.h>
    #include <stdlib.h>
    #include "acl_fifo.h"
    #include "private_fifo.h"
    
    typedef struct ACL_FIFO_ITER ACL_FIFO_ITER;
    struct ACL_FIFO_ITER {
        
        ACL_FIFO_INFO *ptr;
    };
    /**
     * 遍历 ACL_FIFO
     * @param iter {ACL_FIFO_ITER}
     * @param fifo {ACL_FIFO}
     * */
    #define	ACL_FIFO_FOREACH(iter, fifo_ptr) \
    	for ((iter).ptr = (fifo_ptr)->head; (iter).ptr; (iter).ptr = (iter).ptr->next)
    #define	acl_fifo_foreach	ACL_FIFO_FOREACH
    
    #define	ACL_FIFO_FOREACH_REVERSE(iter, fifo_ptr) \
    	for ((iter).ptr = (fifo_ptr)->tail; (iter).ptr; (iter).ptr = (iter).ptr->prev)
    #define	acl_fifo_foreach_reverse	ACL_FIFO_FOREACH_REVERSE
    
    /**
     * 获得当前 iter 所包含的对象地址
     * @param iter {ACL_FIFO_ITER}
     */
    #define	ACL_FIFO_ITER_VALUE(iter)	((iter).ptr->data)
    #define	acl_fifo_iter_value		ACL_FIFO_ITER_VALUE
    
    int main(void)
    {
        
        ACL_FIFO_ITER iter;
        ACL_FIFO fifo,  *fifo_ptr = &fifo;
        char *data;
        ACL_FIFO_INFO *info;
        ACL_ITER iter2;
    
        private_fifo_init(&fifo);
    
        for(int i = 0; i < 10; i++){
        
            data = (char *) malloc(32);
            snprintf(data, 32, "data: %d", i);
            private_fifo_push(&fifo, data);
        }
    
        printf("\n>>> fifo_iter: foreach\n");
    
    
        for ((iter).ptr = (fifo_ptr)->head; (iter).ptr; (iter).ptr = (iter).ptr->next){
        
            printf("%s\n", (char*) iter.ptr->data);
        }
    
    
        printf("\n>>> fifo_iter: foreach\n");
        acl_fifo_foreach(iter, fifo_ptr) {
        
            printf("%s\n", (char*) iter.ptr->data);
        }
    
        printf("\n>>> fifo_iter: foreach\n");
                acl_fifo_foreach(iter, &fifo) {
        
            printf("%s\n", (char*) acl_fifo_iter_value(iter));
        }
    
        printf("\n>>> fifo_iter: foreach_reverse\n");
        acl_fifo_foreach_reverse(iter, &fifo) {
        
            info = iter.ptr;
            printf("%s\n", (char*) info->data);
        }
    
    
        printf("\n>>> acl_foreach for fifo:\n");
                acl_foreach(iter2, &fifo) {
        
            printf("i: %d, value: %s\n", iter2.i, (char*) iter2.data);
        }
    
        printf("\n>>> acl_foreach_reverse for fifo:\n");
                acl_foreach_reverse(iter2, &fifo) {
        
            printf("i: %d, value: %s\n", iter2.i, (char*) iter2.data);
        }
    
        while (1) {
        
            data = private_fifo_pop(&fifo);
            if (data == NULL)
                break;
            free(data);
        }
    }

#include <stdio.h>
    #include <stdlib.h>
    #include "acl_fifo.h"
    #include "private_fifo.h"
    
    
    
    int main(void)
    {
        
        ACL_FIFO_ITER iter;
        ACL_FIFO   *fifo_ptr = private_fifo_new();
        char *data;
        ACL_FIFO_INFO *info;
        ACL_ITER iter2;
    
    
    
        for(int i = 0; i < 10; i++){
        
            data = (char *) malloc(32);
            snprintf(data, 32, "data: %d", i);
            private_fifo_push(fifo_ptr, data);
        }
    
        printf("\n>>> fifo_iter: foreach\n");
    
    
        for ((iter).ptr = (fifo_ptr)->head; (iter).ptr; (iter).ptr = (iter).ptr->next){
        
            printf("%s\n", (char*) iter.ptr->data);
        }
    
    
        printf("\n>>> fifo_iter: foreach\n");
        acl_fifo_foreach(iter, fifo_ptr) {
        
            printf("%s\n", (char*) iter.ptr->data);
        }
    
        printf("\n>>> fifo_iter: foreach\n");
                acl_fifo_foreach(iter, fifo_ptr) {
        
            printf("%s\n", (char*) acl_fifo_iter_value(iter));
        }
    
        printf("\n>>> fifo_iter: foreach_reverse\n");
        acl_fifo_foreach_reverse(iter, fifo_ptr) {
        
            info = iter.ptr;
            printf("%s\n", (char*) info->data);
        }
    
    
        printf("\n>>> acl_foreach for fifo:\n");
                acl_foreach(iter2, fifo_ptr) {
        
            printf("i: %d, value: %s\n", iter2.i, (char*) iter2.data);
        }
    
        printf("\n>>> acl_foreach_reverse for fifo:\n");
                acl_foreach_reverse(iter2, fifo_ptr) {
        
            printf("i: %d, value: %s\n", iter2.i, (char*) iter2.data);
        }
    
        while (1) {
        
            data = private_fifo_pop(fifo_ptr);
            if (data == NULL)
                break;
            free(data);
        }
    
        private_fifo_free(fifo_ptr, NULL);
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 1]

1.  `private_delete_info`  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 2]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]: /images/20221120/8f11d9ce5317496589bb9b89194f25fb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 1]: /images/20221120/9fc3e289688146a7932c209719e4f50f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20201207155304928.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70