go

聊聊ringbuffer

文章目录

  1. 1. 计数法实现
  2. 2. 镜像指示位实现

ringbuffer，是环形缓存区, 或叫环形队列。

不同于一般常见的队列，环形队列收尾相连，通过移动指针来控制队列中内容的读写。

这样做有什么好处呢？

最大的好处是环形队列出队（读取）后，不需要对后续队列内容进行搬移，可以后续由入队（写入）覆盖。

下面来看下一种常见的实现方式， 通过读写指针计数来实现环形队列

计数法实现

先过一遍代码，后边会有图解版说明，方便理解

代码参考自鸟窝无限缓存 channel-chanx

数据结构如下：

1
2
3
4
5
6
7
8
type T interface{}
type RingBuffer struct {
 buf         []T // 队列
 initialSize int // 初始容量
 size        int // 当前容量
 r           int // 读指针计数
 w           int // 写指针计数
}

读取时：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 读写指针相遇为空
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
}

写入时：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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()
 }
}

具体扩容：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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

大意就是在计数可以允许绕两圈（2n-1），假定写指针一圈后和读指针相遇

原来绕一圈归零后相遇（r == w）为队列已满。

现在绕一圈后（未归零）相遇（w == (r + n)）为队列已满。

如下图：

mirror solution

而且如果队列长度刚好是 2 的幂，则可以利用位运算来判断差值是否为n：

1
2
3
4
5
func (r *RingBuffer) IsFull() bool {
 // r.r > size: r.r-size
 // r.r < size: r.r+size
 return (r.r ^ r.size) == r.w
}

然后读写指针的位置获取和偏移也可以按位与来替代取模运算

1
2
3
4
5
6
7
// 位置
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， 感兴趣可以去尝试下。

如有疑问，请文末留言交流或邮件：newbvirgil@gmail.com 本文链接 : https://newbmiao.github.io/2021/09/01/how-to-build-ringbuffer.html