环形队列到底是怎么回事？-阿里云开发者社区

前两天看到一位朋友转发了：嵌入式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);
  }