将循环缓冲区复制到更大的缓冲区，同时保留内容和模数索引

Question

我将一个高效的循环缓冲区 buf 作为一个数组和两个总读写计数 bufRead 和 bufWrite 使得 bufRead % buf.length 和 bufWrite % buf.length 是当前操作缓冲区的正确索引。

现在我可能需要 "grow" 数组，因为缓冲区大小扩大了。所以我想用一个新的更大的数组替换 buf，但保留缓冲区的所有先前内容 ，同时保留上述模数属性 。因此，如果在旧缓冲区的 bufRead % buf.length 处我们找到元素 X，那么我希望同时再次找到该元素 X buf 更新后的索引 bufRead % buf.length。

示例：

trait Algorithm {
  var buf: Array[Double]
  var bufRead : Long  // this won't be needed in `resize`
  var bufWrite: Long  // this won't be needed in `resize`

  def resize(newLength: Int): Unit = {
    val newBuf = new Array[Double](newLength)
    ???
    buf = newBuf
  }
}

测试程序：

def test(in: Algorithm): Unit = {
  import in._
  import math.{min, random}
  val avail  = buf.length // (bufWrite - bufRead).toInt
  val data0  = Array.fill(avail)(random)
  val off0   = (bufRead % buf.length).toInt
  val chunk0 = min(avail, buf.length - off0)  
  val off1   = (off0 + chunk0) % buf.length
  val chunk1 = avail - chunk0

  System.arraycopy(data0, 0     , buf, off0, chunk0)
  System.arraycopy(data0, chunk0, buf, off1, chunk1)

  resize(avail * 2)  // arbitrary growth

  val data1  = new Array[Double](avail)
  val off2   = (bufRead % buf.length).toInt
  val chunk2 = min(avail, buf.length - off2)
  val off3   = (off2 + chunk2) % buf.length
  val chunk3 = avail - chunk2
  System.arraycopy(buf, off2, data1, 0     , chunk2)
  System.arraycopy(buf, off3, data1, chunk2, chunk3)

  assert(data0 sameElements data1)
}

Answer 1

我认为以下是正确的：

class Impl(size0: Int) extends Algorithm {
  var buf = new Array[Double](size0)
  var bufRead  = 0L
  var bufWrite = 0L   // unused here

  override def resize(newLength: Int): Unit = {
    import math.{min, max}
    val newBuf    = new Array[Double](newLength)
    val oldLength = buf.length
    val off0      = (bufRead % oldLength).toInt
    val off1      = (bufRead % newLength).toInt
    val chunk0    = min(oldLength - off0, newLength - off1)
    System.arraycopy(buf, off0, newBuf, off1, chunk0)
    val off2      = (off0 + chunk0) % oldLength
    val off3      = (off1 + chunk0) % newLength
    val chunk1    = min(oldLength - max(chunk0, off2), newLength - off3)
    System.arraycopy(buf, off2, newBuf, off3, chunk1)
    val off4      = (off2 + chunk1) % oldLength
    val off5      = (off3 + chunk1) % newLength
    val chunk2    = oldLength - (chunk0 + chunk1)
    System.arraycopy(buf, off4, newBuf, off5, chunk2)
    buf = newBuf
  }
}

测试：

for (r <- 0 until 200) {
  val a = new Impl(100)
  a.bufRead = r   // test all possible offsets
  test(a)
}

Answer 2

有两种可能的方法：

重新排序内容以适应新模数

for (i <- bufRead until bufWrite) {
    newBuf(i % newBuf.length) = buf(i % buf.length)
}

重置 read 和 write 指针以适应新数组

var j = 0
for (i <- bufRead until bufWrite) {
    newBuf(j) = buf(i % buf.length)
    j += 1
}
bufWrite -= bufRead
bufRead = 0

我不确定您是否要跟踪缓冲区曾经存储的所有元素的数量，如果是，那么第二种方法当然行不通。第一种方法，重新排序，不应该太麻烦，因为无论如何您都需要将内容从旧数组复制到新数组中。

将循环缓冲区复制到更大的缓冲区，同时保留内容和模数索引

Copying a circular buffer to a larger buffer while preserving contents and modulus indices

algorithm

scala

circular-buffer