行の折り返し表示 その 3 - キャッシュ

行の書記素クラスタの開始配列 Line、 行の折り返し配置情報 Grid の両方ともキャッシュで最近使ったものを保持しています。 キャッシュに保持可能な項目数は、 キャッシュ・オブジェクト生成時に指定し、 以後、 保持可能項目数を変更することはできません。

Line も Grid をキャッシュ中から探すには、 ユーザ座標 loc を指定して、 loc が含まれているものを取り出します。 Line と Grid は両方共、 first と last 欄を持ち、 first ... last に loc が含まれているかどうかを判定できるようになっています。 例外は、 first がバッファ末尾のときで、 first と last が同じ値になっています。 この場合に限り、 loc がバッファ末尾ならば選択します。

class RangeLocationCache < Cache
  def lookup(loc, end_of_loc)
    each do |e|
      r = e.value
      if r.first <= loc && (loc < r.last || r.first == end_of_loc)
        touch(e)
        return r
      end
    end
    nil
  end

#@<unshift@>
end

キャッシュのキーは first ... last の範囲です。 新しく付け加えようとしている項目と範囲が重複している項目が既にあるならば、 それらをあらかじめ削除しておきます。

#@<unshift@>=
  def unshift(value)
    each do |e|
      if e.value.last >= value.first && value.last > e.value.first
        delete(e)
      end
    end
    super(value)
  end

Cache は LRU Hash のリング部分を抜き出したものです。 使用中リストを直接操作するために、 ふるまいを少し変更しています。 キャッシュ中の値を読み書きする側で値の入っている項目を touch することで、 使用中リストの先頭へ移動します。 新しく値を追加するために shift しても、 やはり先頭へ追加します。 shift するとき、 既に保持可能項目数に達しているときは、 末尾の項目の内容を捨てて、 それを先頭へ移動してから値を入れ替えます。

キャッシュは使用中リストと未使用リストの 2 本の双方向リストの両端をつないだリングになっています。 リストの間にはダミー項目を挟み、 一方のダミー項目を top が指し、 もう一方を bot が指します。

        top                                   bot              top
         v                                     v                v
... <-> [ ] <-> [先頭] <-> ... <-> [末尾] <-> [ ] <-> free <-> [ ] <-> [先頭] <-> ...
                使用中リスト

top の次が使用中リストの先頭で、 使用中リストの末尾の次が bot です。 bot の前が使用中リストの末尾項目だと言い換えることができます。 bot の次から top の前までが未使用リストで、 未使用リスト内の項目の順番は意味をもちません。 使用中リストが空の場合、 top の次が bot になります。 未使用リストが空のときは、 bot の次が top になります。 リングの初期化では、 まず、 top と bot の 2 つのダミー項目しかないリングを作ります。 続いて、 top の直前に指定個数分の空き項目を挿入します。

class Cache
  include Enumerable

  Item = Struct.new(:forw, :back, :value)

  def initialize(limit=8)
    @limit = [limit, 8].max
    @top = Item.new(nil, nil, nil)
    @bot = Item.new(nil, nil, nil)
    @top.forw = @top.back = @bot
    @bot.forw = @bot.back = @top
    @limit.times {
      item = Item.new(@top, @top.back, nil)
      item.back.forw = item
      item.forw.back = item
    }
  end

#@<unshift@>
#@<touch@>
#@<each@>
#@<delete@>
#@<clear@>
#@<move_after@>
end

unshift で新しい値をキャッシュに付け加えます。 空き項目があるときはそれを使い、 ないときは使用中リストの末尾項目の内容を捨ててそれを使います。 空き項目があるときは、 bot の次につながっています。 空きリストが空の場合、 bot の次が top になっています。 そのとき、 使用中リストは満杯になっていて末尾項目が必ず存在します。 その末尾項目は bot の前につながっています。

#@<unshift@>=
  def unshift(value)
    item = @bot.forw
    if @top.equal?(item)
      item = @bot.back
    end
    item.value = value
    touch(item)
  end

キャッシュから項目を参照したり更新するときに touch することで、 その項目を使用中リストの先頭へ移動します。

#@<touch@>=
  def touch(item)
    move_after(@top, item)
    self
  end

each は、 top と bot の間の使用中リストの項目を順にブロックへ渡していきます。 渡したい項目よりも一つ先に進んでから、 一つ前の項目を yield しているのは、 LRU Hash の each と同じ理由で、 each 中に、 yield した項目を削除できるようにするためのちょっとした工夫です。

#@<each@>=
  def each()
    block_given? or return to_enum(:each)
    item = @top.forw
    while ! @bot.equal?(item)
      item = item.forw
      yield item.back
    end
    self
  end

delete は指定項目を空きリストへ移動します。

#@<delete@>=
  def delete(item)
    item.value = nil
    move_after(@top.back, item)
    self
  end

clear は使用中リストの項目の値を開放してから、 top の次を bot に指定することで、 使用中リストを空にします。

#@<clear@>=
  def clear()
    each {|item| item.value = nil }
    @bot = @top.forw
    @bot.value = nil
    self
  end

move_after はリングの指定位置 dst の直後へ項目 src を移動します。 これは LRU Hash と同じものです。

#@<move_after@>=
  def move_after(dst, src)
    not dst.forw.equal?(src) or return
    src_back = src.back
    src_forw = src.forw
    src_forw.back = src_back
    src_back.forw = src_forw
    dst_forw = dst.forw
    dst.forw = src
    src.back = dst
    src.forw = dst_forw
    dst_forw.back = src
  end

Line と Grid は、 バッファへの文字の挿入・削除によって内容が破壊されたり、 バッファ内での位置が変わったりするため、 手当てが必要です。 そのための仕掛けが、 Buffer の window リストで、 挿入と削除によって、 window.layout のキャッシュから項目の削除もしくは変更をおこないます。

class Buffer
#@<content_insert@>
#@<content_delete@>
#@<update_cache@>
#@<update_mark@>
end

content_insert は GapEditor の insert によって、 指定したユーザ座標の後に文字列を挿入します。 それから、 window リストを辿り、 window のマーク・リスト中のマークと、 window.layout の Grid キャッシュを更新します。 もちろん、 Buffer 自身の Line キャッシュにも更新が必要です。 @revision の値をバッファへ挿入・削除するごとに増やしていきます。

#@<content_insert@>=
  def content_insert(dot, str)
    @content.insert(dot.point, str)
    count = str.size
    @window.each do |win|
      update_mark_insert(win.mark, dot, count)
      update_cache(win.layout.cache, dot, 0, count)
    end
    update_cache(@line_cache, dot, 0, count)
    dot.point += count
    @revision += 1
    self
  end

content_delete は GapEditor の delete によって、 指定した個数の文字を削除します。 それから挿入同様にマークとキャッシュの更新をおこないます。

#@<content_delete@>=
  def content_delete(dot, count)
    @content.delete(dot.point, count)
    count = count.abs
    @window.each do |win|
      update_mark_delete(win.mark, dot, count)
      update_cache(win.layout.cache, dot, count, -count)
    end
    update_cache(@line_cache, dot, count, -count)
    @revision += 1
    self
  end

キャッシュの更新は、 Line と Grid 共通で、 さらに content_insert と content_delete 共通です。 挿入では、 挿入を受けた行の項目を削除します。 削除では行の連結を考慮し、 削除を受けた行だけでなく、 行末を削除したときに次の行も削除します。 それ以外では、 挿入・削除位置以後の first と last の値をずらします。 Line も Grid も書記素クラスタのユーザ座標は first からの相対値にしているため、 first がずれると、 書記素クラスタの位置も first に合わせてずれてくれます。

#@<update_cache@>=
  # update line cache for deletion:  ! reject, = declement
  #
  #                    .                 .+c
  #  ...|\n|q|u|i|c|k| |b|r|o|w|n| |f|o|x|\n|j|u|m|p|s| |o|v|e|r|\n|...
  #  ------^--------------------------------^----------------------^
  #  ...|\n|q|u|i|c|k| |\n|j|u|m|p|s| |o|v|e|r|\n|...
  #  ------^!!!!!!!!!!!!!!^======================^==
  #
  #                    .  .+c
  #  ...|\n|q|u|i|c|k| |\n|j|u|m|p|s| |o|v|e|r|\n|t|h|e| |l|a|z|y| |d|o|g|\n|...
  #  ------^--------------^----------------------^--------------------------^---
  #  ...|\n|q|u|i|c|k| |j|u|m|p|s| |o|v|e|r|\n|t|h|e| |l|a|z|y| |d|o|g|\n|...
  #  ------^!!!!!!!!!!!^!!!!!!!!!!!!!!!!!!!!!!^==========================^===
  def update_cache(cache, dot, count1, count2)
    cache.each do |e|
      if e.value.first <= dot.point + count1 && dot.point < e.value.last
        cache.delete(e)
      elsif e.value.first > dot.point
        e.value.first += count2
        e.value.last += count2
      end
    end
  end

マークの更新は前と同じなのですが、 マークの格納場所を Buffer から Window へ変更したので、 対応しておきます。

#@<update_mark@>=
  def update_mark_insert(mark_list, dot, count)
    mark_list.each do |e|
      if e.point > dot.point
        e.point += count
        e.revision += 1
      end
    end
  end

  def update_mark_delete(mark_list, dot, count)
    mark_list.each do |e|
      if dot.point < e.point && e.point < dot.point + count
        e.point = dot.point
        e.revision += 1
      elsif dot.point + count <= e.point
        e.point -= count
        e.revision += 1
      end
    end
  end