# 環形緩衝區

（重定向自圆形缓冲区

## 圆形缓冲区工作机制

### 读指针与写指针

• 在内存中实际开始位置；
• 在内存中实际结束位置，也可以用缓冲区长度代替；
• 存储在缓冲区中的有效数据的开始位置（读指针）；
• 存储在缓冲区中的有效数据的结尾位置（写指针）。

### 区分缓冲区满或者空

#### 镜像指示位

// This approach adds one bit to end and start pointers
// Circular buffer object
typedef struct {
int size; // maximum number of elements
int start; // index of oldest element
int end; // index at which to write new element
ElemType *elems; // vector of elements
} CircularBuffer;

void cbInit(CircularBuffer *cb, int size) {
cb->size = size;
cb->start = 0;
cb->end = 0;
cb->elems = (ElemType *)calloc(cb->size, sizeof(ElemType));
}

void cbPrint(CircularBuffer *cb) {
printf("size = 0x%x, start = %d, end = %d\n", cb->size, cb->start, cb->end);
}

int cbIsFull(CircularBuffer *cb) {
return cb->end == (cb->start ^ cb->size); // This inverts the most significant bit of start before comparison
}

int cbIsEmpty(CircularBuffer *cb) {
return cb->end == cb->start;
}

int cbIncr(CircularBuffer *cb, int p) {
return (p + 1) & (2 * cb->size - 1); // start and end pointers incrementation is done modulo 2*size
}

void cbWrite(CircularBuffer *cb, ElemType *elem) {
cb->elems[cb->end & (cb->size - 1)] = *elem;
if (cbIsFull(cb)) // full, overwrite moves start pointer
cb->start = cbIncr(cb, cb->start);
cb->end = cbIncr(cb, cb->end);
}

void cbRead(CircularBuffer *cb, ElemType *elem) {
*elem = cb->elems[cb->start & (cb->size - 1)];
cb->start = cbIncr(cb, cb->start);
}


### POSIX优化实现

#include <sys/mman.h>
#include <stdlib.h>
#include <unistd.h>

#define report_exceptional_condition() abort ()

struct ring_buffer {
unsigned long count_bytes;
unsigned long write_offset_bytes;
};

// Warning order should be at least 12 for Linux
void ring_buffer_create (struct ring_buffer *buffer, unsigned long order) {
char path[] = "/dev/shm/ring-buffer-XXXXXX";
int file_descriptor;
int status;
file_descriptor = mkstemp(path);
if (file_descriptor < 0)
report_exceptional_condition();
if (status)
report_exceptional_condition();
buffer->count_bytes = 1UL << order;
buffer->write_offset_bytes = 0;
status = ftruncate(file_descriptor, buffer->count_bytes);
if (status)
report_exceptional_condition();
buffer->address = mmap (NULL, buffer->count_bytes << 1, PROT_NONE,
MAP_ANONYMOUS | MAP_PRIVATE, -1, 0);
report_exceptional_condition();
MAP_FIXED | MAP_SHARED, file_descriptor, 0);
report_exceptional_condition();
MAP_FIXED | MAP_SHARED, file_descriptor, 0);
report_exceptional_condition();
status = close(file_descriptor);
if (status)
report_exceptional_condition();
}

void ring_buffer_free(struct ring_buffer *buffer) {
int status;
status = munmap(buffer->address, buffer->count_bytes << 1);
if (status)
report_exceptional_condition ();
}

// void pointer arithmetic is a constraint violation.
}

void ring_buffer_write_advance(struct ring_buffer *buffer, unsigned long count_bytes) {
buffer->write_offset_bytes += count_bytes;
}

}

// 如果读指针大于等于缓冲区长度，那些读写指针同时折返回[0, buffer_size]范围内
buffer->write_offset_bytes -= buffer->count_bytes;
}
}

unsigned long ring_buffer_count_bytes(struct ring_buffer *buffer) {
}

unsigned long ring_buffer_count_free_bytes(struct ring_buffer *buffer) {
return buffer->count_bytes - ring_buffer_count_bytes (buffer);
}

void ring_buffer_clear(struct ring_buffer *buffer) {
buffer->write_offset_bytes = 0;
}

/*  Note, that initial anonymous mmap() can be avoided - after initial mmap() for descriptor fd,
you can try mmap() with hinted address as (buffer->address + buffer->count_bytes) and if it fails -
Make sure MAP_FIXED is not used in such case, as under certain situations it could end with segfault.
The advantage of such approach is, that it avoids requirement to map twice the amount you need initially
(especially useful e.g. if you want to use hugetlbfs and the allowed amount is limited)
and in context of gcc/glibc - you can avoid certain feature macros
(MAP_ANONYMOUS usually requires one of: _BSD_SOURCE, _SVID_SOURCE or _GNU_SOURCE). */


### Linux内核的kfifo

len = min{待写入数据长度, 缓冲区长度 - （写指针 - 读指针）}