[数据结构][LINUX内核编程]学习笔记（二）
浏览数：12 /
时间：2015年06月20日
linux内核————队列
定义：
- struct __kfifo{
- unsigned int in; //入队偏移，写索引
- unsigned int out; //出队偏移，读索引
- unsigned int mask;
- unsigned int esize;
- void *data;
- }
使用：
创建一个队列，该函数创建并初始化一个大小为size的kfifo：
- 38 int __kfifo_alloc(struct __kfifo *fifo, unsigned int size,
- 39 size_t esize, gfp_t gfp_mask)
- 40 {
- 45 size = roundup_pow_of_two(size);
- 46
- 47 fifo->in = 0;
- 48 fifo->out = 0;
- 49 fifo->esize = esize;
- 50
- 51 if (size < 2) {
- 52 fifo->data = NULL;
- 53 fifo->mask = 0;
- 54 return -EINVAL;
- 55 }
- 56
- 57 fifo->data = kmalloc(size * esize, gfp_mask);
- 58
- 59 if (!fifo->data) {
- 60 fifo->mask = 0;
- 61 return -ENOMEM;
- 62 }
- 63 fifo->mask = size - 1;
- 64
- 65 return 0;
- 66 }
判断一个整数是否是2的整数次幂
- static inline int is_power_of_2(unsigned long long n)
- {
- return (n!=0 &&(n&(n-1)==0))
- }
推入数据到队列的方法是kfifo_in()函数
- 102 static void kfifo_copy_in(struct __kfifo *fifo, const void *src,
- 103 unsigned int len, unsigned int off)
- 104 {
- 105 unsigned int size = fifo->mask + 1;
- 106 unsigned int esize = fifo->esize;
- 107 unsigned int l;
- 108
- 109 off &= fifo->mask; //该操作从数学角度将就是对长度fifo->mask的取模运算
- 110 if (esize != 1) {
- 111 off *= esize;
- 112 size *= esize;
- 113 len *= esize;
- 114 }
- 115 l = min(len, size - off); //size-off代表的含义是当前in到缓冲区尾的大小，
- 116 /*
- 先从buffer中拷贝l字节到缓冲区剩余空间，l<=len，也<=从real_in开始到缓冲区结尾的空间
- 所以这个copy可能没拷贝完，但是不会造成缓冲区越界
- */
- 117 memcpy(fifo->data + off, src, l);
- /*
- len > l时，拷贝buffer中剩余的内容，其实地址当然为buffer + l，而剩余的大小为len - l
- 当len == l时，下面的memcpy啥都不干
- */
- 118 memcpy(fifo->data, src + l, len - l);
- 123 smp_wmb();
- 124 }
- 125
- 126 unsigned int __kfifo_in(struct __kfifo *fifo,
- 127 const void *buf, unsigned int len) //buf指向的是请求入队的缓冲区，len表示的是请求写入的大小
- 128 {
- 129 unsigned int l;
- 131 l = kfifo_unused(fifo);//计算队列中剩余空间的大小，fifo->size-(fifo->in-fifo->out)
- 132 if (len > l)
- 133 len = l;
- 135 kfifo_copy_in(fifo, buf, len, fifo->in);
- 136 fifo->in += len;
- 137 return len;
- 138 }
kfifo的巧妙之处在于in和out定义为无符号类型，在put和get时，in和out都是增加，当达到最大值时，产生溢出，使得从0开始，进行循环使用
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
