藝術(shù)培訓(xùn)學(xué)校系統(tǒng)網(wǎng)站怎么做惠州企業(yè)網(wǎng)站建設(shè)
基于數(shù)組實(shí)現(xiàn)的環(huán)形緩沖區(qū):
優(yōu)點(diǎn)
使用固定大小的連續(xù)空間做用戶態(tài)緩沖區(qū),利用了內(nèi)存訪問(wèn)的局部性,可以提高緩存命中率,提高程序性能,在處理大量數(shù)據(jù)時(shí),緩存的利用率對(duì)性能有著很大的影響
正是基于性能的考慮,使用數(shù)組做用戶態(tài)緩沖區(qū),同時(shí)由于固定的空間大小,在使用數(shù)組時(shí)需要精妙的存取方式,另外,可以使用stl的vacotr的設(shè)計(jì)思路,動(dòng)態(tài)增長(zhǎng)數(shù)組的大小,這里暫不做實(shí)現(xiàn)
先總結(jié)一下環(huán)形緩沖區(qū)(ringbuffer)的優(yōu)點(diǎn):
-
高效的內(nèi)存管理: 環(huán)形緩沖區(qū)是由一塊連續(xù)的內(nèi)存區(qū)域組成的,這樣可以減少內(nèi)存碎片和內(nèi)存分配的開(kāi)銷,提高內(nèi)存管理的效率。
-
預(yù)先分配的內(nèi)存: 因?yàn)榄h(huán)形緩沖區(qū)的大小是固定的,所以可以在系統(tǒng)啟動(dòng)時(shí)或者初始化時(shí)預(yù)先分配所需的內(nèi)存,而不需要?jiǎng)討B(tài)分配內(nèi)存。這可以避免動(dòng)態(tài)內(nèi)存分配帶來(lái)的性能開(kāi)銷和內(nèi)存碎片問(wèn)題。
-
簡(jiǎn)單的索引計(jì)算: 由于環(huán)形緩沖區(qū)的內(nèi)存布局是連續(xù)的,所以索引計(jì)算非常簡(jiǎn)單和高效。相比之下,可變長(zhǎng)鏈表等數(shù)據(jù)結(jié)構(gòu)可能需要更復(fù)雜的指針操作和內(nèi)存訪問(wèn)。
-
更好的緩存性能: 環(huán)形緩沖區(qū)的連續(xù)內(nèi)存布局可以提高緩存的命中率,因?yàn)樗?strong>利用了局部性原理,使得相關(guān)的數(shù)據(jù)項(xiàng)在內(nèi)存中更可能是相鄰存放的。
代碼實(shí)現(xiàn)
環(huán)形緩沖區(qū)結(jié)構(gòu)體:
typedef struct ringbuffer_s {uint32_t size; // 緩沖區(qū)數(shù)組的大小uint32_t tail; // 尾部索引,即當(dāng)前可用的數(shù)組位置索引uint32_t head; // 頭部索引,當(dāng)前已使用的空間的起始位置索引uint8_t * buf; // 實(shí)際緩沖區(qū)數(shù)組地址
} buffer_t;
其中 tail和head索引的設(shè)計(jì) 考慮到需要確定當(dāng)前數(shù)組的空閑位置以及已使用的位置,便于添加新數(shù)據(jù)和取出數(shù)據(jù)
創(chuàng)建一個(gè)緩沖區(qū):
buffer_t * buffer_new(uint32_t sz) { // 結(jié)構(gòu)體和其成員的空間一起分配而不分別分配的原 因是 --> 利用局部性原理提高性能buffer_t * buf = (buffer_t *)malloc(sizeof(buffer_t) + sz); // 結(jié)構(gòu)體 + 緩沖區(qū)if (!buf) {return NULL;}buf->size = sz;buf->head = buf->tail = 0;buf->buf = (uint8_t *)(buf + 1); // 可用緩沖區(qū)在結(jié)構(gòu)體地址后return buf;
}
一個(gè)緩沖區(qū)的初始tail和head索引都是位于數(shù)組首部的
一些輔助函數(shù):
static uint32_t
rb_isempty(buffer_t *r) { // 緩沖區(qū)是否為空return r->head == r->tail;
}static uint32_t rb_isfull(buffer_t *r) { // 緩沖區(qū)是否已滿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;
}
向緩沖區(qū)內(nèi)添加數(shù)據(jù):
int buffer_add(buffer_t *r, const void *data, uint32_t sz) {if (sz > rb_remain(r)) // 如果剩余空間不足,添加失敗 return -1;// 如果tail到數(shù)組尾部的空間不足以容納該數(shù)據(jù),分段添加到尾部和頭部uint32_t i;i = min(sz, r->size - (r->tail & (r->size - 1))); // 計(jì)算將填入尾部的空間,最大是實(shí)際剩余空間// 如果需要分兩次填入,一部分填入尾部,一部分填入頭部memcpy(r->buf + (r->tail & (r->size - 1)), data, i);memcpy(r->buf, data+i, sz-i);r->tail = (r->tail + sz) % r->size; // 更新tail索引,可能移動(dòng)到數(shù)組頭部return 0;
}
環(huán)形緩沖區(qū)的添加操作使用了環(huán)繞索引,最大限度地利用有限的數(shù)組空間
從緩沖區(qū)中取出數(shù)據(jù)
int buffer_remove(buffer_t *r, void *data, uint32_t sz) {assert(!rb_isempty(r)); // 緩沖區(qū)為空,則移除失敗uint32_t i;sz = min(sz, r->tail - r->head); // 確保要移除的長(zhǎng)度不超過(guò)已使用的空間// 根據(jù)長(zhǎng)度分次從尾部、頭部移除i = min(sz, r->size - (r->head & (r->size - 1)));memcpy(data, r->buf+(r->head & (r->size - 1)), i);memcpy(data+i, r->buf, sz-i);r->head = (r->head + actual_sz) % r->size; // 更新head,可能移動(dòng)到數(shù)組頭部return sz;
}
更新head的索引也用到了環(huán)繞的方法
刪除一段數(shù)據(jù):
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; // 更新索引,使用環(huán)繞的方法return sz;
}
獲取當(dāng)前最大可用空間的長(zhǎng)度:
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函數(shù)邏輯
- 如果
tail
在head
之前(即tail < head
),則從tail
到head
之間的空間是可寫的,大小為head - tail - 1
。 - 如果
tail
在head
之后(即tail >= head
),則從tail
到緩沖區(qū)末尾的空間以及從緩沖區(qū)頭部到head
之間的空間都是可寫的,需要分兩段來(lái)計(jì)算最大可寫空間,返回first_chunk + second_chunk - 1
。
head
之前(即tail < head
),則從tail
到head
之間的空間是可寫的,大小為head - tail - 1
。 - 如果
tail
在head
之后(即tail >= head
),則從tail
到緩沖區(qū)末尾的空間以及從緩沖區(qū)頭部到head
之間的空間都是可寫的,需要分兩段來(lái)計(jì)算最大可寫空間,返回first_chunk + second_chunk - 1
。
至此,已經(jīng)實(shí)現(xiàn)了環(huán)形緩沖區(qū)的創(chuàng)建、添加、刪除操作
推薦學(xué)習(xí) https://xxetb.xetslk.com/s/p5Ibb