Go 實現 ringbuffer
ringbuffer
,是環形緩存區, 或叫環形隊列。
不同於一般常見的隊列,環形隊列首尾相連,通過移動指針來控制隊列中內容的讀寫。
這樣做有什麼好處呢?
最大的好處是環形隊列出隊(讀取)後,不需要對後續隊列內容進行搬移,可以後續由入隊(寫入)覆蓋。
下面來看下一種常見的實現方式, 通過讀寫指針計數來實現環形隊列
計數法實現
先過一遍代碼,後邊會有圖解版說明,方便理解
代碼參考自鳥窩無限緩存 chanx[1]
數據結構如下:
type T interface{}
type RingBuffer struct {
buf []T // 隊列
initialSize int // 初始容量
size int // 當前容量
r int // 讀指針計數
w int // 寫指針計數
}
讀取時:
// 讀寫指針相遇爲空
func (r *RingBuffer) IsEmpty() bool {
return r.r == r.w
}
func (r *RingBuffer) Read() (T, error) {
if r.IsEmpty() {
return nil, ErrIsEmpty
}
// 讀取指針處獲取,並向後移動一位
v := r.buf[r.r]
r.r++
// 繞一圈後重置歸零
if r.r == r.size {
r.r = 0
}
return v, nil
}
寫入時:
func (r *RingBuffer) Write(v T) {
// 從寫指針處獲取,並加一偏移
r.buf[r.w] = v
r.w++
// 繞一圈後重置歸零
if r.w == r.size {
r.w = 0
}
// 當寫入後,寫指針遇到讀指針,即隊列已寫滿
if r.w == r.r {
// 自動擴容
r.grow()
}
}
具體擴容:
func (r *RingBuffer) grow() {
var size int
if r.size < 1024 {
// 2倍增長
size = r.size * 2
} else {
// 1.25倍增長
size = r.size + r.size/4
}
buf := make([]T, size)
// 拷貝讀指針 後 待讀取內容
copy(buf[0:], r.buf[r.r:])
// 拷貝讀指針 前 待讀取內容
copy(buf[r.size-r.r:], r.buf[0:r.r])
// 拷貝後讀指針爲頭部
r.r = 0
// 寫指針爲尾部(原隊列大小)
r.w = r.size
r.size = size
r.buf = buf
}
爲方便理解,具體舉例如下圖所示,對照看應該很容易理解:
ringbuffer
除此外,還有一種鏡像指示位方法實現環形隊列
鏡像指示位實現
緩衝區的長度如果是 n,邏輯地址空間則爲 0 至 n-1;那麼,規定 n 至 2n-1 爲鏡像邏輯地址空間。本策略規定讀寫指針的地址空間爲 0 至 2n-1,其中低半部分對應於常規的邏輯地址空間,高半部分對應於鏡像邏輯地址空間。當指針值大於等於 2n 時,使其折返(wrapped)到 ptr-2n。使用一位表示寫指針或讀指針是否進入了虛擬的鏡像存儲區:置位表示進入,不置位表示沒進入還在基本存儲區。from wiki[2]
大意就是在計數可以允許繞兩圈(2n-1
),假定寫指針一圈後和讀指針相遇
原來繞一圈歸零後相遇(r == w
)爲隊列已滿。
現在繞一圈後(未歸零)相遇(w == (r + n)
)爲隊列已滿。
如下圖:
mirror solution
而且如果隊列長度剛好是 2 的冪,則可以利用位運算來判斷差值是否爲n
:
func (r *RingBuffer) IsFull() bool {
// r.r > size: r.r-size
// r.r < size: r.r+size
return (r.r ^ r.size) == r.w
}
然後讀寫指針的位置獲取和偏移也可以按位與來替代取模運算
// 位置
v := r.buf[r.r&(r.size-1)]
r.buf[r.w&(r.size-1)] = v
// 偏移
func (r *RingBuffer) incrCursor(p *int) {
*p = (*p + 1) & (2*r.size - 1)
}
代碼詳見 ringbuffer-mirror[3], 感興趣可以去嘗試下。
參考資料
[1]
鳥窩無限緩存 chanx: https://github.com/smallnest/chanx/blob/main/ringbuffer.go
[2]
wiki: https://zh.wikipedia.org/wiki/%E7%92%B0%E5%BD%A2%E7%B7%A9%E8%A1%9D%E5%8D%80#%E9%95%9C%E5%83%8F%E6%8C%87%E7%A4%BA%E4%BD%8D
[3]
ringbuffer-mirror: https://github.com/NewbMiao/algorithm-go/tree/master/ringbuffer/virtualmemory
本文由 Readfog 進行 AMP 轉碼,版權歸原作者所有。
來源:https://mp.weixin.qq.com/s/tRdb44lOSETC0EaTHBG4sg