网站定制论坛,关键词搜索爱站网,符合网络营销网站建设,evernote wordpress基于数组实现的环形缓冲区#xff1a;
优点
使用固定大小的连续空间做用户态缓冲区#xff0c;利用了内存访问的局部性#xff0c;可以提高缓存命中率#xff0c;提高程序性能#xff0c;在处理大量数据时#xff0c;缓存的利用率对性能有着很大的影响
正是基于性能的…基于数组实现的环形缓冲区
优点
使用固定大小的连续空间做用户态缓冲区利用了内存访问的局部性可以提高缓存命中率提高程序性能在处理大量数据时缓存的利用率对性能有着很大的影响
正是基于性能的考虑使用数组做用户态缓冲区同时由于固定的空间大小在使用数组时需要精妙的存取方式另外可以使用stl的vacotr的设计思路动态增长数组的大小这里暂不做实现
先总结一下环形缓冲区ringbuffer的优点 高效的内存管理 环形缓冲区是由一块连续的内存区域组成的这样可以减少内存碎片和内存分配的开销提高内存管理的效率。 预先分配的内存 因为环形缓冲区的大小是固定的所以可以在系统启动时或者初始化时预先分配所需的内存而不需要动态分配内存。这可以避免动态内存分配带来的性能开销和内存碎片问题。 简单的索引计算 由于环形缓冲区的内存布局是连续的所以索引计算非常简单和高效。相比之下可变长链表等数据结构可能需要更复杂的指针操作和内存访问。 更好的缓存性能 环形缓冲区的连续内存布局可以提高缓存的命中率因为它利用了局部性原理使得相关的数据项在内存中更可能是相邻存放的。
代码实现
环形缓冲区结构体
typedef struct ringbuffer_s {uint32_t size; // 缓冲区数组的大小uint32_t tail; // 尾部索引即当前可用的数组位置索引uint32_t head; // 头部索引当前已使用的空间的起始位置索引uint8_t * buf; // 实际缓冲区数组地址
} buffer_t;其中 tail和head索引的设计 考虑到需要确定当前数组的空闲位置以及已使用的位置便于添加新数据和取出数据
创建一个缓冲区
buffer_t * buffer_new(uint32_t sz) { // 结构体和其成员的空间一起分配而不分别分配的原 因是 -- 利用局部性原理提高性能buffer_t * buf (buffer_t *)malloc(sizeof(buffer_t) sz); // 结构体 缓冲区if (!buf) {return NULL;}buf-size sz;buf-head buf-tail 0;buf-buf (uint8_t *)(buf 1); // 可用缓冲区在结构体地址后return buf;
}一个缓冲区的初始tail和head索引都是位于数组首部的
一些辅助函数
static uint32_t
rb_isempty(buffer_t *r) { // 缓冲区是否为空return r-head r-tail;
}static uint32_t rb_isfull(buffer_t *r) { // 缓冲区是否已满return r-size (r-tail - r-head);
}static uint32_t rb_len(buffer_t *r) { // 已使用空间return r-tail - r-head;
}static uint32_t rb_remain(buffer_t *r) { // 剩余空间return r-size - r-tail r-head;
}向缓冲区内添加数据
int buffer_add(buffer_t *r, const void *data, uint32_t sz) {if (sz rb_remain(r)) // 如果剩余空间不足添加失败 return -1;// 如果tail到数组尾部的空间不足以容纳该数据分段添加到尾部和头部uint32_t i;i min(sz, r-size - (r-tail (r-size - 1))); // 计算将填入尾部的空间最大是实际剩余空间// 如果需要分两次填入一部分填入尾部一部分填入头部memcpy(r-buf (r-tail (r-size - 1)), data, i);memcpy(r-buf, datai, sz-i);r-tail (r-tail sz) % r-size; // 更新tail索引可能移动到数组头部return 0;
}环形缓冲区的添加操作使用了环绕索引最大限度地利用有限的数组空间
从缓冲区中取出数据
int buffer_remove(buffer_t *r, void *data, uint32_t sz) {assert(!rb_isempty(r)); // 缓冲区为空则移除失败uint32_t i;sz min(sz, r-tail - r-head); // 确保要移除的长度不超过已使用的空间// 根据长度分次从尾部、头部移除i min(sz, r-size - (r-head (r-size - 1)));memcpy(data, r-buf(r-head (r-size - 1)), i);memcpy(datai, r-buf, sz-i);r-head (r-head actual_sz) % r-size; // 更新head可能移动到数组头部return sz;
}更新head的索引也用到了环绕的方法
删除一段数据
int buffer_drain(buffer_t *r, uint32_t sz) {if (sz rb_len(r)) // 最多全部删除sz rb_len(r);r-head (r-head sz) % r-size; // 更新索引使用环绕的方法return sz;
}获取当前最大可用空间的长度
uint8_t *buffer_write_atmost(buffer_t *r) {uint32_t wpos r-tail;uint32_t rpos r-head;if (wpos rpos) {// Case 1: tail is ahead of or equal to headuint32_t first_chunk r-size - wpos; // Space from tail to end of bufferuint32_t second_chunk rpos; // Space from start of buffer to headreturn r-buf wpos;} else {// Case 2: head is ahead of tailreturn r-buf wpos;}}buffer_write_atmost函数逻辑
如果 tail 在 head 之前即 tail head则从 tail 到 head 之间的空间是可写的大小为 head - tail - 1。如果 tail 在 head 之后即 tail head则从 tail 到缓冲区末尾的空间以及从缓冲区头部到 head 之间的空间都是可写的需要分两段来计算最大可写空间返回 first_chunk second_chunk - 1。 head 之前即 tail head则从 tail 到 head 之间的空间是可写的大小为 head - tail - 1。如果 tail 在 head 之后即 tail head则从 tail 到缓冲区末尾的空间以及从缓冲区头部到 head 之间的空间都是可写的需要分两段来计算最大可写空间返回 first_chunk second_chunk - 1。
至此已经实现了环形缓冲区的创建、添加、删除操作
推荐学习 https://xxetb.xetslk.com/s/p5Ibb
