#ifndef __BUFFER_H__ #define __BUFFER_H__ #include <stdint.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 { uint32_t write_index; uint32_t read_index; uint32_t capacity; uint8_t * data; } buffer_t; buffer_t *buffer_create( uint32_t capacity ); void buffer_delete( buffer_t *buffer ); void buffer_init( buffer_t *buffer, uint8_t * data, uint32_t capacity ); void buffer_clear( buffer_t *buffer ); uint32_t buffer_readable( buffer_t *buffer ); uint32_t buffer_writable( buffer_t *buffer ); uint32_t buffer_full( buffer_t *buffer ); uint32_t buffer_empty( buffer_t *buffer ); void buffer_flush( buffer_t *buffer, uint32_t bytes ); void buffer_read( buffer_t *buffer, uint8_t *data, uint32_t length ); void buffer_write( buffer_t *buffer, const uint8_t *data, uint32_t length ); uint32_t buffer_write_ex( buffer_t *buffer, const uint8_t *data, uint32_t length ); uint32_t buffer_read_ex( buffer_t *buffer, uint8_t *data, uint32_t length ); #endif /* __BUFFER_H__ */ #include "buffer.h" #include <stdlib.h> #include <string.h> void buffer_delete( buffer_t *buffer ) { free( buffer ); } // capacity = 2^n :: struct : buffer[ capacity ] buffer_t *buffer_create( uint32_t capacity ) { void * p = malloc( sizeof(buffer_t) + capacity ); buffer_t *buffer = (buffer_t *) p; if ( buffer == NULL ) return NULL; buffer->capacity = capacity; buffer_clear( buffer ); return buffer; // buffer_init( buffer, ( (uint8_t *)buffer ) + sizeof(buffer_t), capacity ) } // capacity = 2^n void buffer_init( buffer_t *buffer, uint8_t * data, uint32_t capacity ) { buffer->data = data; buffer->capacity = capacity; buffer_clear( buffer ); } void buffer_clear( buffer_t *buffer ) { buffer->read_index = buffer->write_index = 0; } uint32_t buffer_empty( buffer_t *buffer ) { return buffer->read_index == buffer->write_index; } uint32_t buffer_full( buffer_t *buffer ) { return buffer->capacity == ( buffer->read_index ^ buffer->write_index ); } uint32_t buffer_readable( buffer_t *buffer ) { if ( buffer->write_index >= buffer->read_index ) return buffer->write_index - buffer->read_index; else return buffer->capacity + buffer->write_index - buffer->read_index; } uint32_t buffer_writable( buffer_t *buffer ) { if ( buffer->write_index >= buffer->read_index ) return buffer->capacity - ( buffer->write_index - buffer->read_index ); else return buffer->read_index - buffer->write_index; } void buffer_flush( buffer_t *buffer, uint32_t bytes ) { // we can't flush more bytes than there are uint32_t flushable = buffer_readable( buffer ); if ( bytes > flushable ) bytes = flushable; buffer->read_index = ( buffer->read_index + bytes ) & ( 2 * buffer->capacity - 1 ); } void buffer_read( buffer_t *buffer, uint8_t *data, uint32_t length ) { // clear MSB uint32_t read_index = buffer->read_index & ( buffer->capacity - 1 ); if ( read_index + length <= buffer->capacity ) memcpy( data, buffer->data + read_index, length ); else { uint32_t upper = buffer->capacity - read_index; uint32_t lower = length - upper; memcpy( data, buffer->data + read_index, upper ); memcpy( data + upper, buffer->data, lower ); } buffer->read_index = ( buffer->read_index + length ) & ( 2 * buffer->capacity - 1 ); } void buffer_write( buffer_t *buffer, const uint8_t *data, uint32_t length ) { // clear MSB uint32_t write_index = buffer->write_index & ( buffer->capacity - 1 ); if ( write_index + length <= buffer->capacity ) memcpy( buffer->data + write_index, data, length ); else { uint32_t upper = buffer->capacity - write_index; uint32_t lower = length - upper; memcpy( buffer->data + write_index, data, upper ); memcpy( buffer->data, data + upper, lower ); } buffer->write_index = ( buffer->write_index + length ) & ( 2 * buffer->capacity - 1 ); } uint32_t buffer_read_ex( buffer_t *buffer, uint8_t *data, uint32_t length ) { uint32_t readable = buffer_readable( buffer ); if ( length > readable ) length = readable; if ( length > 0 ) buffer_read( buffer, data, length ); return length; } uint32_t buffer_write_ex( buffer_t *buffer, const uint8_t *data, uint32_t length ) { uint32_t writable = buffer_writable( buffer ); if ( length > writable ) length = writable; if ( length > 0 ) buffer_write( buffer, data, length ); return length; }

循环缓冲实现（ringbuffer/circularbuffer)

http://www.haogongju.net/art/2689660

/**************************************************************************************************** * buf : 存放数据的缓冲区地址 * size: 缓冲区的大小(必须是2的幂) * in ：写指针下标 * out ：读指针下标 * 缓冲区模型如下：size固定大小，in的值始终大于等于out的值 * 先从ringbuf->in到缓冲区末端写数据，如果还没写完，再从缓冲区头开始写入剩下的，从而实现了循环缓冲。 * +--------------+(in)-----------------+(size) * +-----+(out)-------------------------+ * 那么可用的缓冲空间大小就是(size - in + out)* * 所以写数据时 * 1.先从length和(ringbuf->size - ringbuf->in + ringbuf->out)之间取一个较小的值赋给length * 2.再判断缓冲区的末端(buffer->size - (buffer->in & (buffer->size - 1)))大小是否够保存length的数据给len * 3.拷贝len长度的数据到缓冲区的末端 memcpy(buffer->buf + (buffer->in & (buffer->size - 1)), data, len); * 4.再拷贝剩下的数据到缓冲区的前端 memcpy(buffer->buf, data + len, length - len); 如果length - len为0则无操作。 * 5.写指针的下标增加length长度。 * 6.返回实际写入缓冲区的长度。 * * 读取数据：* * 1.数据量的大小由(buffer->in - buffer->out)决定 * amount和(buffer->in - buffer->out)取小值给amount，作为一次读取的数据大小 * 2.尾部缓冲数据大小由(buffer->size - (buffer->out & (buffer->size - 1)))决定 * 判断尾部数据和总需求数据大小，取小值给len * 3.先拷贝尾部缓冲的数据到目的memcpy(target, buffer->buf + (buffer->out & (buffer->size - 1)), len); * 4.再拷贝头部缓冲数据 memcpy(target + len, buffer->buf, amount - len); amount - len为0则无操作。 * 5.读指针的下标增加amount大小 * 6.返回实际读取的数据大小。* * 注意: * 当(ringbuf->in == ringbuf->out + ringbuf->size)时，表示缓冲区已满. * 此时得到的较小值一定是0，后面实际写入的字节数也全为0。 * * 既然ringbuf->size是2的幂，那么(ringbuf->size-1)也就是一个除最高位为0，其余二进制位都为1的一个数值 * 也就能保证(ringbuf->in & (ringbuf->size - 1))不会超过(ringbuf->size - 1)，和(ringbuf->in)%(ringbuf->size - 1)的效果一样 * 从上面可以看出，ringbuf->in的值可以从0变化到超过fifo->size的数值* * ringbuf->out也如此，但它们的差不会超过ringbuf->size。 ****************************************************************************************************/ typedef struct cycle_buffer { unsigned char* buf; unsigned int size; unsigned int in; unsigned int out; } RingBuffer; RingBuffer *RingBuffer_create( int length ); void RingBuffer_destroy( RingBuffer *buffer ); int RingBuffer_read( RingBuffer *buffer, char *target, int amount ); int RingBuffer_write( RingBuffer *buffer, char *data, int length ); int RingBuffer_empty( RingBuffer *buffer ); int RingBuffer_Reset( RingBuffer *buffer ); #define min(x, y) ((x) < (y) ? (x) : (y)) #define ROUND_UP_2(num) (((num)+1)&~1) #define DEFAULT_BUF_SIZE (2*1024*1024) RingBuffer *RingBuffer_create( int length ) { unsigned int size = ROUND_UP_2( length ); if ( ( size & ( size - 1 ) ) || ( size < DEFAULT_BUF_SIZE ) ) { size = DEFAULT_BUF_SIZE; } RingBuffer *buffer = (RingBuffer *) malloc( sizeof(RingBuffer) ); if ( !buffer ) { return NULL; } memset( buffer, 0, sizeof(RingBuffer) ); buffer->size = size; buffer->in = 0; buffer->out = 0; buffer->buf = (unsigned char *) malloc( size ); if ( !buffer->buf ) { free( buffer ); return NULL; } memset( buffer->buf, 0, size ); return buffer; }void RingBuffer_destroy( RingBuffer *buffer ) { if ( buffer ) { free( buffer->buf ); free( buffer ); } } int RingBuffer_Reset( RingBuffer *buffer ) { if ( buffer == NULL ) { return -1; } buffer->in = 0; buffer->out = 0; memset( buffer->buf, 0, buffer->size ); return 0; } int RingBuffer_empty( RingBuffer *buffer ) { return buffer->in == buffer->out; } int RingBuffer_write( RingBuffer *buffer, char *data, int length ) { unsigned int len = 0; length = min( length, buffer->size - buffer->in + buffer->out ); len = min( length, buffer->size - ( buffer->in & ( buffer->size - 1 ) ) ); memcpy( buffer->buf + ( buffer->in & ( buffer->size - 1 ) ), data, len ); memcpy( buffer->buf, data + len, length - len ); buffer->in += length; return length; } int RingBuffer_read( RingBuffer *buffer, char *target, int amount ) { unsigned int len = 0; amount = min( amount, buffer->in - buffer->out ); len = min( amount, buffer->size - ( buffer->out & ( buffer->size - 1 ) ) ); memcpy( target, buffer->buf + ( buffer->out & ( buffer->size - 1 ) ), len ); memcpy( target + len, buffer->buf, amount - len ); buffer->out += amount; return amount; }

 

 

转载于:https://www.cnblogs.com/shangdawei/archive/2013/04/25/3042416.html

相关资源：数据结构—成绩单生成器