#ifndef __CIRCLE_BUFFER_H__
#define __CIRCLE_BUFFER_H__
/*
* http://en.wikipedia.org/wiki/Circular_buffer : Mirroring
*
* The capacity of circle buffer must be a power of two !
*
* The source and sink of data can implement independent policies for dealing
* with a full buffer and overrun while adhering to the rule that
*
* only the source of data modifies the write index and
* only the sink of data modifies the read index.
*
* This can result in elegant and robust circular buffer implementations
* even in multi-threaded environments.
*
* |<------- CAPACITY ------------>|<---- Writable + Readable ---->|
* | MSB = 0 | MSB = 1 |
* +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
* | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
* +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
* ^ ^
* R ---- R^W == CAPACITY -------- W ---- FULL : R.MSB != W.MSB
* W ---- R^W == 0 ---------------------- EMPTY : R.MSB == W.MSB
*
* W >= R : W - R = Readable
* W < R : R - W = Writable
*
* Emyty : W ^ R == 0 : Readable == 0
* Full : W ^ R == CAPACITY : Writable == 0
*/
typedef struct
{
unsigned char *
buffer;
unsigned int capacity;
unsigned int read_index;
unsigned int write_index;
} circle_buffer_t;
circle_buffer_t *circle_buffer_create( unsigned
int capacity );
void circle_buffer_delete( circle_buffer_t *
circle_buffer );
void circle_buffer_init( circle_buffer_t *circle_buffer, unsigned
char *
buffer,
unsigned int capacity );
void circle_buffer_clear( circle_buffer_t *
circle_buffer );
unsigned int circle_buffer_readable( circle_buffer_t *
circle_buffer );
unsigned int circle_buffer_writable( circle_buffer_t *
circle_buffer );
void circle_buffer_flush( circle_buffer_t *circle_buffer, unsigned
int bytes );
unsigned int circle_buffer_read( circle_buffer_t *
circle_buffer,
unsigned char *data, unsigned
int length );
unsigned int circle_buffer_write( circle_buffer_t *
circle_buffer,
const unsigned
char *data, unsigned
int length );
unsigned int circle_buffer_full( circle_buffer_t *
circle_buffer );
unsigned int circle_buffer_empty( circle_buffer_t *
circle_buffer );
#endif /* __CIRCLE_BUFFER_H__ */
#include
"circle_buffer.h"
#include <stdlib.h>
#include <
string.h>
void circle_buffer_clear( circle_buffer_t *
circle_buffer )
{
circle_buffer->read_index = circle_buffer->write_index =
0;
// any value
}
void circle_buffer_init( circle_buffer_t *circle_buffer, unsigned
char *
buffer,
unsigned int capacity )
{
circle_buffer->buffer =
buffer;
circle_buffer->capacity =
capacity;
circle_buffer_clear( circle_buffer );
}
// capacity = 2^n :: struct : buffer[ capacity ]
circle_buffer_t *circle_buffer_create( unsigned
int capacity )
{
void * p = malloc(
sizeof(circle_buffer_t) +
capacity );
circle_buffer_t *circle_buffer = (circle_buffer_t *
) p;
if ( circle_buffer ==
NULL )
return NULL;
circle_buffer->capacity =
capacity;
circle_buffer_clear( circle_buffer );
return circle_buffer;
// circle_buffer_init( circle_buffer,
// ( (unsigned char *)circle_buffer )+sizeof(circle_buffer_t), capacity )
}
void circle_buffer_delete( circle_buffer_t *
circle_buffer )
{
free( circle_buffer );
}
unsigned int circle_buffer_empty( circle_buffer_t *
circle_buffer )
{
return circle_buffer->read_index == circle_buffer->
write_index;
}
unsigned int circle_buffer_full( circle_buffer_t *
circle_buffer )
{
return circle_buffer->
capacity
== ( circle_buffer->read_index ^ circle_buffer->
write_index );
}
unsigned int circle_buffer_readable( circle_buffer_t *
circle_buffer )
{
if ( circle_buffer->write_index >= circle_buffer->
read_index )
return circle_buffer->write_index - circle_buffer->
read_index;
else
return circle_buffer->capacity + circle_buffer->
write_index
- circle_buffer->
read_index;
}
unsigned int circle_buffer_writable( circle_buffer_t *
circle_buffer )
{
if ( circle_buffer->write_index >= circle_buffer->
read_index )
return circle_buffer->
capacity
- ( circle_buffer->write_index - circle_buffer->
read_index );
else
return circle_buffer->read_index - circle_buffer->
write_index;
}
void circle_buffer_flush( circle_buffer_t *circle_buffer, unsigned
int bytes )
{
// we can't flush more bytes than there are
unsigned
int flushable =
circle_buffer_readable( circle_buffer );
if ( bytes >
flushable )
bytes =
flushable;
circle_buffer->read_index = ( circle_buffer->read_index +
bytes )
& (
2 * circle_buffer->capacity -
1 );
}
unsigned int circle_buffer_read( circle_buffer_t *
circle_buffer,
unsigned char *data, unsigned
int length )
{
unsigned int buffer_readable =
circle_buffer_readable( circle_buffer );
if ( length >
buffer_readable )
length =
buffer_readable;
if ( length ==
0 )
return 0;
unsigned int read_index = circle_buffer->
read_index
& ( circle_buffer->capacity -
1 );
// clear MSB
if ( read_index + length <= circle_buffer->
capacity )
memcpy( data, circle_buffer->buffer +
read_index, length );
else
{
unsigned int upper = circle_buffer->capacity -
read_index;
unsigned int lower = length -
upper;
memcpy( data, circle_buffer->buffer +
read_index, upper );
memcpy( data + upper, circle_buffer->
buffer, lower );
}
circle_buffer->read_index = ( circle_buffer->read_index +
length )
& (
2 * circle_buffer->capacity -
1 );
return length;
}
unsigned int circle_buffer_write( circle_buffer_t *
circle_buffer,
const unsigned
char *data, unsigned
int length )
{
unsigned int buffer_writable =
circle_buffer_writable( circle_buffer );
if ( length >
buffer_writable )
length =
buffer_writable;
if ( length ==
0 )
return 0;
unsigned int write_index = circle_buffer->
write_index
& ( circle_buffer->capacity -
1 );
// clear MSB
if ( write_index + length <= circle_buffer->
capacity )
memcpy( circle_buffer->buffer +
write_index, data, length );
else
{
unsigned int upper = circle_buffer->capacity -
write_index;
unsigned int lower = length -
upper;
memcpy( circle_buffer->buffer +
write_index, data, upper );
memcpy( circle_buffer->buffer, data +
upper, lower );
}
circle_buffer->write_index = ( circle_buffer->write_index +
length )
& (
2 * circle_buffer->capacity -
1 );
return length;
}
转载于:https://www.cnblogs.com/shangdawei/archive/2013/04/14/3019804.html
相关资源：数据结构—成绩单生成器
