用C代碼實現了一些常用的數據結構，list，map，tree，字符串函數，ring buffer等，學習C語言的人值得看看。
boost 庫裡也有環形緩沖區的實現， 具體使用的例子如下：
[cpp]
#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>
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;
}
上面的例子很簡單， 可以讓我們對使用方法做一個簡單的理解。
有興趣的同學還可以看看下面的這個例子。
[cpp]
#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 <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;
}
還有一種特殊的環形緩沖區叫 邊界緩沖區，邊界緩沖區是一個典型的生產者消費者模式，生產者生產和存儲元素，消費者取出元素，然後進行處理。邊界緩沖區有個特別的地方，就是緩沖區滿了的時候， 生產者保證不會進行插入元素的工作， 一直要到有空閒空間的時候，才會插入新元素。
邊界緩沖區的實現如下所示 ：
[cpp]
#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;
};
#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++ 實現，可以用來處理二進制數據，改天有空了翻譯一下，方便大家閱讀。
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.
