前两天看到一位朋友转发了：嵌入式Linux 作者发哥的一篇C语言环形队列文章：C语言，环形队列，写的非常好。做过实际项目的朋友大概率都用到过队列，它可用于解决生产者和消费者产出和消费不平衡的问题，举两个我之前项目中遇到的案例：
1） 我需要在一块屏幕上显示多种事件，而事件的来源很多、触发时间也很快，但是屏幕由于资源限制，没法把所有事件都同步显示。这时就可以使用队列，将事件插入到队列中，显示程序读取队列中的事件逐条显示。
2） 我在之前文章：一个蓝牙实战项目的掏肺总结 里提到的那个蓝牙收发器，蓝牙芯片一方面接收手机发过来的数据，另一方面要把该数据通过USB 发送出去，但是USB发送数据的间隔又要求比较长，这也可以通过队列来解决。
C++里有现成的队列函数，但是C语言需要自己来实现，我之前项目里用到了Github上的一个代码，https://github.com/kuaileguyue/Ring-Buffer ，简洁好用。那时就是用，因为大概知道原理，就没有认真的去分析代码的实现细节，这次刚好看到发哥文章下有很多关于环形队列的留言讨论，我就详细的去看了一下之前用的代码，发现收获还是不小的，在此分享给大家。
先上代码：
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 这几种情况，都是队列为满的状态。
觉得不错，点个赞支持一下吧！
