Ring Buffer (circular Buffer)环形缓冲区简介

关于环形缓冲区的知识，请看这里

http://en.wikipedia.org/wiki/Circular_buffer 

上面这个网址已经介绍得非常详细了。

下面这个网址有 RingBuffer的C代码实现， 其实是一个C的开源库   liblcthw 里实现的。

http://c.learncodethehardway.org/book/ex44.html

开源库 liblcthw的网址为     https://github.com/zedshaw/liblcthw，  用C代码实现了一些常用的数据结构，list，map，tree，字符串函数，ring buffer等，学习C语言的人值得看看。

boost 库里也有环形缓冲区的实现， 具体使用的例子如下：

   #include <boost/circular_buffer.hpp>

   int main(int /*argc*/, char* /*argv*/[]) {

      // 创建一个环形缓冲区来存放三个int类型的数据
      boost::circular_buffer<int> cb(3);

      //插入元素
      cb.push_back(1);
      cb.push_back(2);
      cb.push_back(3);

      int a = cb[0];  // a == 1
      int b = cb[1];  // b == 2
      int c = cb[2];  // c == 3

      //环形缓冲区现在已经满了，继续插入元素将会覆盖掉最前面的元素

      cb.push_back(4);  // 用4覆盖了1
      cb.push_back(5);  // 用5覆盖了2

      //环形缓冲区现在包含元素 3, 4 和 5.

      a = cb[0];  // a == 3
      b = cb[1];  // b == 4
      c = cb[2];  // c == 5

      //元素能够被从后面取出也可从前面取出

      cb.pop_back();  // 5 被取出
      cb.pop_front(); // 3 被取出

      int d = cb[0];  // d == 4

      return 0;
   }

有兴趣的同学还可以看看下面的这个例子。

   #include <boost/circular_buffer.hpp>
   #include <numeric>
   #include <assert.h>

   int main(int /*argc*/, char* /*argv*/[])
   {
      //创建一个容量为3的环形缓冲区
      boost::circular_buffer<int> cb(3);

      //插入2个元素进入环形缓冲区
      cb.push_back(1);
      cb.push_back(2);

      // assertions
      assert(cb[0] == 1);
      assert(cb[1] == 2);
      assert(!cb.full());
      assert(cb.size() == 2);
      assert(cb.capacity() == 3);

      //再插入2个元素
      cb.push_back(3);
      cb.push_back(4);

      //计算容器里所有元素之和
      int sum = std::accumulate(cb.begin(), cb.end(), 0);

      //断言
      assert(cb[0] == 2);
      assert(cb[1] == 3);
      assert(cb[2] == 4);
      assert(*cb.begin() == 2);
      assert(cb.front() == 2);
      assert(cb.back() == 4);
      assert(sum == 9);
      assert(cb.full());
      assert(cb.size() == 3);
      assert(cb.capacity() == 3);

      return 0;
   }

还有一种特殊的环形缓冲区叫 边界缓冲区，边界缓冲区是一个典型的生产者消费者模式，生产者生产和存储元素，消费者取出元素，然后进行处理。边界缓冲区有个特别的地方，就是缓冲区满了的时候， 生产者保证不会进行插入元素的工作， 一直要到有空闲空间的时候，才会插入新元素。

边界缓冲区的实现如下所示 ：

   #include <boost/circular_buffer.hpp>
   #include <boost/thread/mutex.hpp>
   #include <boost/thread/condition.hpp>
   #include <boost/thread/thread.hpp>
   #include <boost/call_traits.hpp>
   #include <boost/progress.hpp>
   #include <boost/bind.hpp>

   template <class T>
   class bounded_buffer {
   public:

      typedef boost::circular_buffer<T> container_type;
      typedef typename container_type::size_type size_type;
      typedef typename container_type::value_type value_type;
      typedef typename boost::call_traits<value_type>::param_type param_type;

      explicit bounded_buffer(size_type capacity) : m_unread(0), m_container(capacity) {}

      void push_front(boost::call_traits<value_type>::param_type item) {
         // param_type represents the "best" way to pass a parameter of type value_type to a method

         boost::mutex::scoped_lock lock(m_mutex);
         m_not_full.wait(lock, boost::bind(&bounded_buffer<value_type>::is_not_full, this));
         m_container.push_front(item);
         ++m_unread;
         lock.unlock();
         m_not_empty.notify_one();
      }

      void pop_back(value_type* pItem) {
         boost::mutex::scoped_lock lock(m_mutex);
         m_not_empty.wait(lock, boost::bind(&bounded_buffer<value_type>::is_not_empty, this));
         *pItem = m_container[--m_unread];
         lock.unlock();
         m_not_full.notify_one();
      }

   private:
      bounded_buffer(const bounded_buffer&);              // Disabled copy constructor
      bounded_buffer& operator = (const bounded_buffer&); // Disabled assign operator

      bool is_not_empty() const { return m_unread > 0; }
      bool is_not_full() const { return m_unread < m_container.capacity(); }

      size_type m_unread;
      container_type m_container;
      boost::mutex m_mutex;
      boost::condition m_not_empty;
      boost::condition m_not_full;
   };

1.  push_front() 方法被生产者线程调用，目的是插入新元素到buffer中。这个方法会锁住mutex，一直等到有新空间可以插入新元素。 (Mutex锁在等待期间是没有锁住的，只有条件满足的时候才会把锁锁上) 假如在buffer中有一个可用的空间，执行就会继续，该方法就会插入元素进入到环形缓冲区的末尾。 然后未读元素的数量就会增加，然后自动解锁。 (在例子中，Mutex锁解锁是会抛出一个异常，锁会在scoped_lock对象的析构函数中自动被打开). 最后，这个方法会通知其中的一个消费者线程，告诉他们，有一个新的元素插入了缓冲区。

2. pop_back() 方法被消费者线程调用，目的是为了从buffer中读取下一个元素。这个方法会锁住Mutex然后等待，直到有一个未读的元素进入缓冲区。 假如至少有一个未读元素的时候，这个方法就会减少未读元素的数量，然后从circular_buffer中读取一个未读元素。然后就解锁Mutex，并通知等待中的一个生产者线程，告诉它又新的空间可以插入新元素了。

3. 这个 pop_back() 方法移除元素，元素仍然留在 circular_buffer 里，这样的话，当circular_buffer满的时候它就会被生产者线程用一个新的元素替代。这个技术比移除一个元素更有效率。

下面的网址是一个环形缓冲区的 C++ 实现，可以用来处理二进制数据，改天有空了翻译一下，方便大家阅读。

http://www.asawicki.info/news_1468_circular_buffer_of_raw_binary_data_in_c.html

Circular Buffer of Raw Binary Data in C++

Circular Buffer, Cyclic Buffer or Ring Buffer is a data structure that effectively manages a queue of some items. Items can be added at the back and removed from the front. It has limited capacity because it is based on preallocated array. Functionality is implemented using two pointers or indices - pointing to the first and past the last valid element. The Begin pointer is incremented whenever an item is popped from the front so that it "chases" the End pointer, which is incremented whenever a new item is pushed to the back. They can both wrap around the size of the array. Both operations are done very effectively - in constant time O(1) and no reallocations are needed. This makes circular buffers perfect solution for queues of some data streams, like video or audio.

It's not very sophisticated data structure, but there is one problem. Sample codes of circular buffers you can find on the Internet, just like for many other data structures, operate usually on a single object of some user-defined type. What if we need a buffer for raw binary data, stored as array of bytes? We can treat single bytes as data items, but enqueueing and dequeueing single bytes with separate function calls would not be efficient. We can, on the other hand, define some block of data (like 4096 bytes) as the type of item, but this limits us to operating on on such block at a time.

Best solution would be to write an implementation that operates on binary data in form of (const char *bytes, size_t byte_count) and allows writing and reading arbitrary amount of data in a single call, just like functions for writing and reading files do. The only problem that arises in such code is that sometimes the block of data you want to write to or read from the buffer is not in a continuous region of memory, but wraps around to the beginning of the array so we have to process it on two parts - first at the end of the array and the second at the beginning.

Here is my C++ implementation of a circular buffer for raw binary data:

#include <algorithm> // for std::min

class CircularBuffer
{
public:
  CircularBuffer(size_t capacity);
  ~CircularBuffer();

  size_t size() const { return size_; }
  size_t capacity() const { return capacity_; }
  // Return number of bytes written.
  size_t write(const char *data, size_t bytes);
  // Return number of bytes read.
  size_t read(char *data, size_t bytes);

private:
  size_t beg_index_, end_index_, size_, capacity_;
  char *data_;
};

CircularBuffer::CircularBuffer(size_t capacity)
  : beg_index_(0)
  , end_index_(0)
  , size_(0)
  , capacity_(capacity)
{
  data_ = new char[capacity];
}

CircularBuffer::~CircularBuffer()
{
  delete [] data_;
}

size_t CircularBuffer::write(const char *data, size_t bytes)
{
  if (bytes == 0) return 0;

  size_t capacity = capacity_;
  size_t bytes_to_write = std::min(bytes, capacity - size_);

  // Write in a single step
  if (bytes_to_write <= capacity - end_index_)
  {
    memcpy(data_ + end_index_, data, bytes_to_write);
    end_index_ += bytes_to_write;
    if (end_index_ == capacity) end_index_ = 0;
  }
  // Write in two steps
  else
  {
    size_t size_1 = capacity - end_index_;
    memcpy(data_ + end_index_, data, size_1);
    size_t size_2 = bytes_to_write - size_1;
    memcpy(data_, data + size_1, size_2);
    end_index_ = size_2;
  }

  size_ += bytes_to_write;
  return bytes_to_write;
}

size_t CircularBuffer::read(char *data, size_t bytes)
{
  if (bytes == 0) return 0;

  size_t capacity = capacity_;
  size_t bytes_to_read = std::min(bytes, size_);

  // Read in a single step
  if (bytes_to_read <= capacity - beg_index_)
  {
    memcpy(data, data_ + beg_index_, bytes_to_read);
    beg_index_ += bytes_to_read;
    if (beg_index_ == capacity) beg_index_ = 0;
  }
  // Read in two steps
  else
  {
    size_t size_1 = capacity - beg_index_;
    memcpy(data, data_ + beg_index_, size_1);
    size_t size_2 = bytes_to_read - size_1;
    memcpy(data + size_1, data_, size_2);
    beg_index_ = size_2;
  }

  size_ -= bytes_to_read;
  return bytes_to_read;
}  

Similar phenomenon can be observed in API of the FMOD sound library. Just like graphical textures in DirectX, sound samples in FMOD can also be "locked" to get pointer to a raw memory we can read or fill. But DirectX textures lie in the continuous memory region, so we get a single pointer. The only difficult thing in understanding locking textures is the concept of "stride", which can be greater than the width of a single row. Here in FMOD the Sound::lock() method returns two pointers and two lengths, probably because the locked region can wrap over end of internally used circular buffer like the one shown above.