一:概述
實際學習和工作中,我們經常會遇到讀寫大量數據的情況,這個時候我們可能就用到了循環緩沖區。
循環緩沖區在處理大量數據的時候有很大的優點,循環緩沖區在一些競爭問題上提供了一種免鎖的機制,免鎖的前提是,生產者和消費都只有一個的情況下,否則也要加鎖。
二:循環緩沖區的實現理論如下圖
三:實現代碼如下所示:
//CRecycleQueue.h
#include<iostream>
//循環緩沖區類模板
template<class T>
class CRecycleQueue{
private:
//循環緩沖區地址指針
T **_queue;
//循環緩沖區讀游標 (讀的位置)
int _read;
//循環緩沖區寫游標 (寫的位置)
int _write;
//循環緩沖區的大小
int _size;
//我們姑且稱這個變量為掩碼,接下來用來作位&運算,從而實現循環緩沖
int _mask;
public:
CRecycleQueue(){
_queue = NULL;
_read = 0;
_write = 0;
_size = 0;
_mask = 0;
}
//初始化循環緩沖區
bool InitRecycleQueue(int exp){
if(0 > exp){
return false;
}
_read = 0;
_write = 0;
//傳進來一個整數,對1進行位移操作
//比如exp = 4
//_size的二進制表示:1000
_size = 1 << exp;
//_mask的二進制表示:0111
_mask = _size - 1;
//分配緩沖區空間
_queue = (T **)new char[sizeof (T *) * _size];
if(NULL == _queue){
return false;
}
return true;
}
/*
* size = 1000 mask = 0111
* write或read同mask 作&運算,可以實現循環緩沖區的功能
* 也許你會問這裡為什麼不使用 % 運算實現循環的循環功能呢?
* 答案是系統 & 運算效率要比 % 運算效率高
*
* Push:
* write = 0;
* 0000 & 0111 = 0; write++ (寫入緩沖隊列的第0位置)
* write = 1;
* 0001 & 0111 = 1; write++ (寫入緩沖隊列的第1位置)
* write = 2;
* 0010 & 0111 = 2; write++
* write = 3;
* 0011 & 0111 = 3; write++
* ...
* write = 8;
* 1000 & 0111 = 0; write++
* write = 9;
* 1001 & 0111 = 1; write++
* ...
*
* Pop:
* read = 0;
* 0000 & 0111 = 0; read++ (讀取緩沖隊列的第0位置的數據)
* read = 1;
* 0001 & 0111 = 1; read++ (讀取緩沖隊列的第1位置的數據)
* read = 2;
* 0010 & 0111 = 2; read++
* read = 3
* 0011 & 0111 = 3; read++
* ...
* read = 8;
* 1000 & 0111 = 0; read++
* ...
* */
bool Push(T *type){
if(NULL == type){
return false;
}
//當條件不滿足的時候,說明緩沖區已滿,Push進來的數據就會丟失
if(_write < _read + _size){
//我們這裡存入的是type指針,這個指針指向了一個我們分配的內存空間或者類
_queue[_write & _mask] = type;
_write++;
return true;
}
return false;
}
T *Pop(){
T *tmp = NULL;
//當條件不滿足的時候說明緩沖區已經沒有數據
if(_read < _write){
//取出隊列的數據
tmp = _queue[_read & _mask];
_read++;
}
return tmp;
}
int GetRemainSize(){
return (_write - _read);
}
};
下面是簡單的測試代碼:
//main.cpp
#include <iostream>
#include <pthread.h>
#include "CRecycleQueue.h"
using namespace std;
class UserInfo{
private :
int _num;
public:
UserInfo(int num){
_num = num;
}
int getUserNum(){
return _num;
}
};
CRecycleQueue<UserInfo> *queue = new CRecycleQueue<UserInfo>;
void *write_func(void *args){
int num = 0;
while(1){
//UserInfo裡可以封裝你自己想要的數據
//這裡僅僅是一個簡單的測試用例
UserInfo *info = new UserInfo(num++);
if(!queue->Push(info)){
//Push失敗 刪除手動分配的內存空間
delete info;
}
sleep(1);
}
}
void *read_func(void *args){
while(1){
UserInfo *info = NULL;
if(info = queue->Pop()){
cout<<info->getUserNum()<<endl;
delete info;
}
sleep(1);
}
}
int
main(){
queue->InitRecycleQueue(8);
pthread_t pid1;
pthread_t pid2;
//這種生產者和消費者都只有一個的情況下,這個循環緩沖區為競爭問題提供了免鎖,大大提高了程序的處理效率
pthread_create(&pid1,NULL,read_func,NULL);
pthread_create(&pid2,NULL,write_func,NULL);
pthread_join(pid1,NULL);
pthread_join(pid2,NULL);
return 0;
}
編譯:g++ main.cpp -lpthread -o test
這個循環緩沖隊列大體的功能已經實現,其中循環緩沖隊列一些其他操作並沒有去實現,只是描述了一些核心的操作!
如果有錯誤和其他意見,提出來大家一起相互討論和學習!