前两天看到一位朋友转发了公众号：嵌入式Linux 作者发哥的一篇C语言环形队列文章：C语言，环形队列，写的非常好。做过实际项目的朋友大概率都用到过队列，它可用于解决生产者和消费者产出和消费不平衡的问题，举两个我之前项目中遇到的案例：
1） 我需要在一块屏幕上显示多种事件，而事件的来源很多、触发时间也很快，但是屏幕由于资源限制，没法把所有事件都同步显示。这时就可以使用队列，将事件插入到队列中，显示程序读取队列中的事件逐条显示。
2） 我在之前文章：一个蓝牙实战项目的掏肺总结 里提到的那个蓝牙收发器，蓝牙芯片一方面接收手机发过来的数据，另一方面要把该数据通过USB 发送出去，但是USB发送数据的间隔又要求比较长，这也可以通过队列来解决。
C++里有现成的队列函数，但是C语言需要自己来实现，我之前项目里用到了Github上的一个代码，https://github.com/kuaileguyu... ，简洁好用。那时就是用，因为大概知道原理，就没有认真的去分析代码的实现细节，这次刚好看到发哥文章下有很多关于环形队列的留言讨论，我就详细的去看了一下之前用的代码，发现收获还是不小的，在此分享给大家。
先上代码：
ringbuffer.h
#include <inttypes.h>
/**
* @file
* Prototypes and structures for the ring buffer module.
*/
#ifndef RINGBUFFER_H
#define RINGBUFFER_H
/**
* The size of a ring buffer.
* Due to the design only <tt> RING_BUFFER_SIZE-1 </tt> items
* can be contained in the buffer.
* The buffer size must be a power of two.
*/
#define RING_BUFFER_SIZE 128
#if (RING_BUFFER_SIZE & (RING_BUFFER_SIZE - 1)) != 0
#error "RING_BUFFER_SIZE must be a power of two"
#endif
/**
* The type which is used to hold the size
* and the indicies of the buffer.
* Must be able to fit \c RING_BUFFER_SIZE .
*/
typedef uint8_t ring_buffer_size_t;
/**
* Used as a modulo operator
* as <tt> a % b = (a & (b − 1)) </tt>
* where \c a is a positive index in the buffer and
* \c b is the (power of two) size of the buffer.
*/
#define RING_BUFFER_MASK (RING_BUFFER_SIZE-1)
/**
* Simplifies the use of <tt>struct ring_buffer_t</tt>.
*/
typedef struct ring_buffer_t ring_buffer_t;
/**
* Structure which holds a ring buffer.
* The buffer contains a buffer array
* as well as metadata for the ring buffer.
*/
struct ring_buffer_t {
/** Buffer memory. */
char buffer[RING_BUFFER_SIZE];
/** Index of tail. */
ring_buffer_size_t tail_index;
/** Index of head. */
ring_buffer_size_t head_index;
};
/**
* Initializes the ring buffer pointed to by <em>buffer</em>.
* This function can also be used to empty/reset the buffer.
* @param buffer The ring buffer to initialize.
*/
void ring_buffer_init(ring_buffer_t *buffer);
/**
* Adds a byte to a ring buffer.
* @param buffer The buffer in which the data should be placed.
* @param data The byte to place.
*/
void ring_buffer_queue(ring_buffer_t *buffer, char data);
/**
* Adds an array of bytes to a ring buffer.
* @param buffer The buffer in which the data should be placed.
* @param data A pointer to the array of bytes to place in the queue.
* @param size The size of the array.
*/
void ring_buffer_queue_arr(ring_buffer_t *buffer, const char *data, ring_buffer_size_t size);
/**
* Returns the oldest byte in a ring buffer.
* @param buffer The buffer from which the data should be returned.
* @param data A pointer to the location at which the data should be placed.
* @return 1 if data was returned; 0 otherwise.
*/
uint8_t ring_buffer_dequeue(ring_buffer_t *buffer, char *data);
/**
* Returns the <em>len</em> oldest bytes in a ring buffer.
* @param buffer The buffer from which the data should be returned.
* @param data A pointer to the array at which the data should be placed.
* @param len The maximum number of bytes to return.
* @return The number of bytes returned.
*/
uint8_t ring_buffer_dequeue_arr(ring_buffer_t *buffer, char *data, ring_buffer_size_t len);
/**
* Peeks a ring buffer, i.e. returns an element without removing it.
* @param buffer The buffer from which the data should be returned.
* @param data A pointer to the location at which the data should be placed.
* @param index The index to peek.
* @return 1 if data was returned; 0 otherwise.
*/
uint8_t ring_buffer_peek(ring_buffer_t *buffer, char *data, ring_buffer_size_t index);
/**
* Returns whether a ring buffer is empty.
* @param buffer The buffer for which it should be returned whether it is empty.
* @return 1 if empty; 0 otherwise.
*/
inline uint8_t ring_buffer_is_empty(ring_buffer_t *buffer) {
return (buffer->head_index == buffer->tail_index);
}
/**
* Returns whether a ring buffer is full.
* @param buffer The buffer for which it should be returned whether it is full.
* @return 1 if full; 0 otherwise.
*/
inline uint8_t ring_buffer_is_full(ring_buffer_t *buffer) {
return ((buffer->head_index - buffer->tail_index) & RING_BUFFER_MASK) == RING_BUFFER_MASK;
}
/**
* Returns the number of items in a ring buffer.
* @param buffer The buffer for which the number of items should be returned.
* @return The number of items in the ring buffer.
*/
inline ring_buffer_size_t ring_buffer_num_items(ring_buffer_t *buffer) {
return ((buffer->head_index - buffer->tail_index) & RING_BUFFER_MASK);
}
#endif /* RINGBUFFER_H */ringbuffer.c
#include "ringbuffer.h"
/**
* @file
* Implementation of ring buffer functions.
*/
void ring_buffer_init(ring_buffer_t *buffer) {
buffer->tail_index = 0;
buffer->head_index = 0;
}
void ring_buffer_queue(ring_buffer_t *buffer, char data) {
/* Is buffer full? */
if(ring_buffer_is_full(buffer)) {
/* Is going to overwrite the oldest byte */
/* Increase tail index */
buffer->tail_index = ((buffer->tail_index + 1) & RING_BUFFER_MASK);
}
/* Place data in buffer */
buffer->buffer[buffer->head_index] = data;
buffer->head_index = ((buffer->head_index + 1) & RING_BUFFER_MASK);
}
void ring_buffer_queue_arr(ring_buffer_t *buffer, const char *data, ring_buffer_size_t size) {
/* Add bytes; one by one */
ring_buffer_size_t i;
for(i = 0; i < size; i++) {
ring_buffer_queue(buffer, data[i]);
}
}
ring_buffer_size_t ring_buffer_dequeue(ring_buffer_t *buffer, char *data) {
if(ring_buffer_is_empty(buffer)) {
/* No items */
return 0;
}
*data = buffer->buffer[buffer->tail_index];
buffer->tail_index = ((buffer->tail_index + 1) & RING_BUFFER_MASK);
return 1;
}
ring_buffer_size_t ring_buffer_dequeue_arr(ring_buffer_t *buffer, char *data, ring_buffer_size_t len) {
if(ring_buffer_is_empty(buffer)) {
/* No items */
return 0;
}
char *data_ptr = data;
ring_buffer_size_t cnt = 0;
while((cnt < len) && ring_buffer_dequeue(buffer, data_ptr)) {
cnt++;
data_ptr++;
}
return cnt;
}
ring_buffer_size_t ring_buffer_peek(ring_buffer_t *buffer, char *data, ring_buffer_size_t index) {
if(index >= ring_buffer_num_items(buffer)) {
/* No items at index */
return 0;
}
/* Add index to pointer */
ring_buffer_size_t data_index = ((buffer->tail_index + index) & RING_BUFFER_MASK);
*data = buffer->buffer[data_index];
return 1;
}
extern inline uint8_t ring_buffer_is_empty(ring_buffer_t *buffer);
extern inline uint8_t ring_buffer_is_full(ring_buffer_t *buffer);
extern inline uint8_t ring_buffer_num_items(ring_buffer_t *buffer);代码加起来只有200行，我就不逐条的去分析了，结合以下几个具体的问题重点讲解下。
问题1：如何初始化环形队列？
回答：只要定义一个ring_buffer_t类型的结构体，然后调用ring_buffer_init()函数初始化即可。
ring_buffer_t ring_buffer;
ring_buffer_init(&ring_buffer);问题2：队列长度如何设置？
回答：在ringbuffer.h中下述宏定义设置，注意长度修改时要确认ring_buffer_size_t的类型uint8_t是否可以满足，否则应该修改此类型。
#define RING_BUFFER_SIZE 128问题3：为什么环形队列长度必须是2的n次方？
回答：因为在判断队列是否为满的时候，用到了RING_BUFFER_MASK，而RING_BUFFER_MASK的值为RING_BUFFER_SIZE-1，这个MASK为二进制全1，所以长度是2的n次方。
inline uint8_t ring_buffer_is_full(ring_buffer_t *buffer) {
return ((buffer->head_index - buffer->tail_index) & RING_BUFFER_MASK) == RING_BUFFER_MASK;
}问题4：代码是如何判断队列为满的？满了以后会怎么样？
回答：在ring_buffer_is_full函数中，用head_index减去tail_index，根据这个值来判断。
head_index 的值是一直++的，从0一直加到RING_BUFFER_MASK，然后再回到0继续加(形成一个环形)。只在调用ring_buffer_queue()函数入队列的时候它才会变化，buffer->head_index = ((buffer->head_index + 1) & RING_BUFFER_MASK);
tail_index则不同，在调用ring_buffer_dequeue()函数出队列的时候会++，buffer->tail_index = ((buffer->tail_index + 1) & RING_BUFFER_MASK); 注意：在ring_buffer_queue()函数里，当判断队列为满的时候，它也会加。
if(ring_buffer_is_full(buffer)) {
/* Is going to overwrite the oldest byte */
/* Increase tail index */
buffer->tail_index = ((buffer->tail_index + 1) & RING_BUFFER_MASK);
}这个怎么理解呢？也就是说在入队列的时候，当判断到队列已满，head_index即将又回到tail_index位置时，这时就会把tail_index向前推一下，这样的效果是最初进入队列的那个数据被新入队列的数据覆盖掉了，再也没有机会被取出来了。
回过头再来看判断是否为满的这条语句，
return ((buffer->head_index - buffer->tail_index) & RING_BUFFER_MASK) == RING_BUFFER_MASK;
可以体会到它的写法之高妙，head_index 是可能比 tail_index大，也可能比tail_index小的，
以一个长度为4的队列为例，假设一直入队列，没有出队列，整个过程如下：
可以看到当head_index =3、tail_index =0或head_index =0、tail_index =1或head_index =1、tail_index =2或head_index =2、tail_index =3 这几种情况，都是队列为满的状态。
END
作者：wuyage
来源：https://mp.weixin.qq.com/s/v4DagsffP1nCOYlCk_1NXQ
推荐阅读
更多芯片嵌入式电子技术分享请关注Topsemic嵌入式极术专栏
