1 background
Circular buffer(CB) must be
created to be able to save(receive) binary data from network or other
thread(say writer thread), and another thread can read the received
data.
One of the usage is accepting network video continuously, a consumer thread read frames from CB
and display it on screen.
2 Necessary data structure to represent the circular buffer
const int MAX_BUFFER_SIZE =
2<<24; //
const int MAX_READABLE_SIZE = MAX_BUFFER_SIZE-1;
precondition: a
pre-allocated array of unsigned char
uchar *buffer
= new uchar[MAX_BUFFER_SIZE];
Identifier
recv_pos: the position
from which the netwrok data is to be saved next time
read_pos: the position
from which the reader thread to read next time (include read_pos)
If CB is full,
the writer thread cannot write data into it, must wait until there is
available free space
If CB is empty,
the reader thread cannot read data from it, must wait until there is
avaiable data
full
condition: recv_pos == read_pos (just one of the implementation)
empty
condition: (recv_pos+1)%MAX_BUFFER_SIZE == read_pos
For
example: let MAX_BUFFER_SIZE = 10
3 possible situations of the circular buffer:
In the
following, green grids represent the effective data bytes can be read and white girds mean free spaces.
1 Empty buffer:
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
Green grids contain received bytes, White space grids can be used to received new data
2 Full buffer:
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
3 Non-full and non-empty buffer:
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
When
next time writer begin to write data into buffer, recv_pos will also be used, so when the
buffer is full, the effective size of
data can be read is MAX_BUFFER_SIZE – 1.
4 Pseudo code
bool
isBufferEmpty() {
return recv_pos == nextReadPos;
}
bool
isBufferFull() {
//this also works when nextRecPos reaches the end of buffer
return ( recv_pos
+1)%MAX_BUFFER_SIZE == read_pos;
}
Implementation
1
supposing the receiving thread can save more bytes to first position of the buffer(ie to position: recv_pos...N-1, 0,...X)
//get
the size of effective data received
int
effectiveSize() {
int ef_size = 0;
if (read_pos < recv_pos) {
ef_size = recv_pos – read_pos;
}
if (read_pos > recv_pos) {
ef_size = (MAX_BUFFER_SIZE – read_pos) + recv_pos;
}
return ef_size;
}
//get
the free space
int
freeSpace() {
int free_size = MAX_BUFFER_SIZE – 1;
if (read_pos < recv_pos) {
free_size = MAX_BUFFER_SIZE - recv_pos + read_pos - 1;
}
if (read_pos > recv_posv) {
free_size = read_pos – recv_pos – 1;
}
return free_size;
}
//or
receive, may wrap around
void
write(uchar* src, int len) {
while
(free_space() < len) wait(); //wait until there is enough free
space to save data
if
(len > MAX_B UFFER_SIZE – recv_pos) {
memcpy(&buffer[recv_pos], src, MAX_BUFFER_SIZE – recv_posv);
len -= (MAX_BUFFER_SIZE – recv_pos);
memcpy(&buffer[0], &src[ MAX_BUFFER_SIZE – recv_pos], len);
recv_pos = len;
} else {
memcpy(&buffer[recv_posv], src, len);
recv_pos = (recv_pos + len) % MAX_BUFFER_SIZE;
}
}
//read
the specified len data, may block
int
readFull(uchar* dst, int len) {
if
(len > MAX_READABLE_SIZE) return -1;
while
(effectiveSize() < len) wait();
if
(read_pos < recv_pos) {
memcpy(dst, &buffer[read_pos], len);
read_pos += len;
}
else if (read_pos > recv_pos) {
if
(MAX_BUFF_SIZE – read_pos < len) {
memcpy(dst, &buffer[read_pos],
MAX_BUFF_SIZE – read_pos);
len
-= ( MAX_BUFF_SIZE – read_pos);
memcpy(&dst[ MAX_BUFF_SIZE – read_pos], buffer, len);
read_pos = len;
}
else {
memcpy(dst,
&buffer[read_pos], len);
read_pos = (read_pos + len) % MAX_BUFF_SIZE);
}
}
return
len;
}
//read
with, won't block.
int
read(uchar* dst, int len) {
if
(len > MAX_READABLE_SIZE) return -1;
if
(len > effectiveSize()) len = effectiveSize();
return
readFull(dst, len);
}
Implementation
2
supposing the receiving thread can only save data to the end of buffer each time
//get
the size of effective data received
int ef_size = 0;
if (read_pos < recv_pos) {
ef_size = recv_pos – read_pos;
}
if (read_pos > recv_pos) {
ef_size = (MAX_BUFFER_SIZE – read_pos) + recv_pos;
}
return ef_size;
}
//get
the free space
int free_size = MAX_BUFFER_SIZE - recv_pos – 1;
if (read_pos > recv_pos) {
free_size = read_pos – recv_pos – 1;
} else {
if (read_pos > 0) {
free_size = MAX_BUFFER_SIZE – recv_pos;
}
}
return free_size;
}
//or
receive, can
not wrap around each time,
void
writeNoWrap(uchar* src, int len) {
//while
(isBufferFull() ) wait();
while (freeSpace() <=
0) wait();
if
(len > freeSpace()) len = freeSpace();
memcpy(&buffer[recv_pos],
src, len); //recv_pos the receive offset;
recv_pos = (recv_pos + len) % MAX_BUFFER_SIZE;
}
//read the specified len data, may block
int
readFull(uchar* dst, int len) {
if
(len > MAX_READABLE_SIZE) return -1;
while
(effectiveSize() < len) wait();
if
(read_pos < recv_pos) {
memcpy(dst, &buffer[read_pos], len);
read_pos += len;
}
else if (read_pos > recv_pos) {
if
(MAX_BUFF_SIZE – read_pos < len) {
memcpy(dst, &buffer[read_pos],
MAX_BUFF_SIZE – read_pos);
len
-= ( MAX_BUFF_SIZE – read_pos);
memcpy(&dst[ MAX_BUFF_SIZE – read_pos], buffer, len);
read_pos = len;
}
else {
memcpy(dst,
&buffer[read_pos], len);
read_pos = (read_pos+len) % MAX_BUFF_SIZE);
}
}
return
len;
}
//read
with, won't block.
int
read(uchar* dst, int len) {
if
(len > MAX_READABLE_SIZE) return -1;
if
(len > effectiveSize()) len = effectiveSize();
return
readFull(dst, len);
}
