队列与堆栈

队列

只允许在队列的前端(front,队头)进行删除操作,而在队列的后端(rear,队尾)进行插入操作。当队列中没有元素时,即front=rear,称为空队列。在队列中插入一个队列元素称为入队,从队列中删除一个队列元素称为出队。队列符合先进先出(FIFO—first in first out)原则

堆栈

栈:又名堆栈,只允许在栈顶插入和删除元素。栈顶是低位,栈底是高位。栈中没有元素时称为空栈,栈符合先进后出原则(LIFO,last in first out)。
操作: push入栈、pop出栈

6.2.1 kfifo入队列和出队列

 

 

(1)空的kfifo

(2)推入一个buffer后

(3)摘取一个buffer后,出口偏移(out)加上摘取的元素数目

(4)当此时put的buffer长度超出in到末尾长度时,则将剩下的移到头部去

参考:https://zhuanlan.zhihu.com/p/548021636

 

 

6.2.2 创建队列

struct __kfifo {
    unsigned int    in;   // 队列头,删除操作
    unsigned int    out;  // 队列尾,插入操作
    unsigned int    mask; // 缓存区大小,byte
    unsigned int    esize; // 缓存区元素占用的字节数,比如char时,eszie为1,int时esize为4
    void        *data;    // 存放数据的缓存区地址
};

kfifo_alloc由内核调用kmalloc_array函数来申请内存空间


int __kfifo_alloc(struct __kfifo *fifo, unsigned int size,
        size_t esize, gfp_t gfp_mask)
{
    /* 向上对齐到2的幂 */
    size = roundup_pow_of_two(size);

    fifo->in = 0;
    fifo->out = 0;
    fifo->esize = esize;

    if (size < 2) {
        fifo->data = NULL;
        fifo->mask = 0;
        return -EINVAL;
    }

    fifo->data = kmalloc_array(esize, size, gfp_mask);

    if (!fifo->data) {
        fifo->mask = 0;
        return -ENOMEM;
    }
    fifo->mask = size – 1;

    return 0;
}

 用户申请好一个buffer,再使用kfifo_init初始化为kfifo队列

int __kfifo_init(struct __kfifo *fifo, void *buffer,
        unsigned int size, size_t esize)
{
    size /= esize;

    if (!is_power_of_2(size))
        size = rounddown_pow_of_two(size);

    fifo->in = 0;
    fifo->out = 0;
    fifo->esize = esize;
    fifo->data = buffer;

    if (size < 2) {
        fifo->mask = 0;
        return -EINVAL;
    }
    fifo->mask = size - 1;

    return 0;
}

 

6.2.7队列使用举例

(1)kfifo_in推入数据(0-31)

 

 (2)kfifo_out_peek读取第0位置的元素,但不删除,out不增加

 

(3)kfifo_out从出口偏移(out)拷贝出一个4byte

 

原文地址:http://www.cnblogs.com/cai-zi/p/16887612.html

1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长! 2. 分享目的仅供大家学习和交流,请务用于商业用途! 3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入! 4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解! 5. 如有链接无法下载、失效或广告,请联系管理员处理! 6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需! 7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员! 8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载 声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性