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