GtkTextBuffer の BTree

GtkTextBuffer は、 段落のシーケンス木で、 段落はさらに文字列のリストになっています。段落を構成する一つ一つの文字列をセグメントと呼びます。 段落のシーケンス木は、 BTree による索引になっており、 行番号・文字位置・ピクセル Y 座標で段落を探せるようになっています。 この BTree のデータ構造を Ruby に翻訳して備忘録にしておきます。

この BTree のキーは部分木中の行数、文字数、ピクセル高さです。 B 木にありがちなページ構造体を使わず、 2-3-4 木のようなキー付き 2 分木のような形になっています。 横のつながりが、 1 ページ分で、 終端は NULL になっています。 縦のつながりが、 親ページ中のセルと子ページの関係になっています。 根も Node で、 これには木全体の行数・文字数・ピクセル高さを記録します。 Node には葉から根へ向けてレベルを書き込んであります。 Line のすぐ上の Node はレベル 0 で、 上がるにつれて一つずつレベルを増やします。

Node と Line は親ノードへの参照をもっています。 親ページではなく、 親ノードです。 ページ中のリストになっているノードを参照します。 根の親ノードの参照は NULL とします。

初期状態では、 空の行が 2 行登録してあります。

初期状態

root |Node|                  レベル 0
      ↓
     |Line|→|Line|

Line をたくさん挿入した後の状態

root |Node|                                              レベル 2
      ↓
     |Node|→|Node|→|Node|→|Node|→|Node|→|Node|      レベル 1
      ↓
     |Node|→|Node|→|Node|→|Node|→|Node|→|Node|      レベル 0
      ↓
     |Line|→|Line|→|Line|→|Line|→|Line|→|Line|

ここでは簡単にするため、 セグメントはリストではなく文字列とします。 また、 行単位での挿入・削除だけを考えることにします。 初期化すると、 上の初期状態を作ります。 ピクセル高さは省略します。

class TextBTree
  MAX_CHILD = 4
  MIN_CHILD = 2
  Node = Struct.new(:parent, :level, :nchild, :nline, :nchar, :child, :forw)
  Line = Struct.new(:parent, :nchild, :nline, :nchar, :segment, :forw)

  attr_accessor :root

  def initialize
    @root = Node.new(nil, 0, 2, 2, 2, nil, nil)
    line = Line.new(@root, 1, 1, 1, "\n", nil)
    line2 = Line.new(@root, 1, 1, 1, "\n", nil)
    @root.child = line
    line.forw = line2
  end

#@<行探し@>
#@<文字位置探し@>
#@<行挿入@>
#@<行削除@>

end

行探しは、 B+ シーケンス木と同じです。 ページの左から部分木のページ数を引いていきます。 Line のリストでは 1 行ずつ引いていきます。

#@<行探し@>=
  def line_at(n)
    n = [[n < 0 ? @root.nline + n : n, 0].max, @root.nline - 1].min
    node = @root
    while node.level > 0
      node = node.child
      while node.nline <= n
        n -= node.nline
        node = node.forw
      end
    end
    line = node.child
    while n > 0
      n -= 1
      line = line.forw
    end
    line
  end

文字位置探しは Line でも文字数を引いていくところが異なっています。 GtkTextBTree では文字位置をカプセル化したイテレータを返しますが、 ここでは簡略にして Line 構造体とその中での相対位置のペアを返します。

#@<文字位置探し@>=
  def char_at(n)
    n = [[n < 0 ? @root.nchar + n : n, 0].max, @root.nchar - 1].min
    node = @root
    while node.level > 0
      node = node.child
      while node.nchar <= n
        n -= node.nchar
        node = node.forw
      end
    end
    line = node.child
    while line.nchar <= n
      n -= line.nchar
      line = line.forw
    end
    [line, n]
  end

Line 構造体の後に 1 行分の文字列を挿入します。 新しい行を Line の前に挿入するのですが、 Line 同士は単方向リストなので、 Line の後に Line 構造体を新しく挿入してから、 Line の内容をそちらへコピーするやりかたを GtkTextBTree は採用しています。 ここでも同じようにふるまうようにしました。 親ノードへのリンクがあるので、 挿入した行数と文字数を根まで足し込むのは簡単です。

#@<行挿入@>=
  def insert_line(line, str)
    cur = line.dup
    line.nchild = line.nline = 1
    line.nchar = str.size
    line.segment = str
    line.forw = cur
    node = line.parent
    while not node.nil?
      node.nline += 1
      node.nchar += str.size
      node = node.parent
    end
    left_node = line
    while true
      left_node.parent.nchild += 1
      left_node = left_node.parent
      break if left_node.nchild <= MAX_CHILD
      if left_node.parent.nil?
        @root = Node.new
        @root.level = left_node.level + 1
        @root.parent = @root.forw = nil
        @root.child = left_node
        recompute_node_count(@root)
      end
      right_node = Node.new
      right_node.level = left_node.level
      right_node.parent = left_node.parent
      right_node.forw = left_node.forw
      left_node.forw = right_node
      overflow(left_node, right_node)
    end
    self
  end

#@<オーバーフロー@>
#@<カウント情報の更新@>

ページに相当する部分のノード数がリミットを越えると、 リストを 2 つに分割します。 分割する左側が MIN_CHILD になるようにリストを切り分けます。

#@<オーバーフロー@>=
  def overflow(left_node, right_node)
    child = left_node.child
    (MIN_CHILD - 1).times { child = child.forw }
    right_node.child = child.forw
    child.forw = nil
    recompute_node_count(left_node)
    recompute_node_count(right_node)
  end

ノードの挿入が生じると、 行数・文字数等を更新する必要が生じます。 子のノード数・行数・文字数を数え直して親ノードを更新します。

  def recompute_node_count(node)
    node.nchild = node.nline = node.nchar = 0
    child = node.child
    while not child.nil?
      child.parent = node
      node.nchild += 1
      node.nline += child.nline
      node.nchar += child.nchar
      child = child.forw
    end
    node
  end

行の削除は、 Line 構造体が単方向リンク・リストなので、 先頭を特別扱いし、 以後は望みの位置でリストを切断します。 ページ内のノード数が減りすぎたら、 隣のノードからリストを融通してもらって、 1 本に連結するか、 2 本のままでノード数のバランスを取るかのどちらかをおこないます。

  def delete_line(line)
    node = line.parent
    if node.child.equal?(line)
      node.child = line.forw
    else
      child = find_left(node.child) {|c| c.equal?(line) }
      child.forw = line.forw
    end
    node = line.parent
    while not node.nil?
      node.nline -= 1
      node.nchar -= line.segment.size
      node = node.parent
    end
    left_node = line
    while true
      left_node.parent.nchild -= 1
      left_node = left_node.parent
      break if left_node.nchild >= MIN_CHILD
      if left_node.parent.nil?
        if left_node.nchild == 1 and Node === left_node.child
          @root = left_node.child
        end
        break
      end
      right_node = left_node.forw
      if right_node.nil?
        right_node = left_node
        left_node = find_left(right_node.parent.child) {|c| c.equal?(right_node) }
      end
      child = find_left(left_node.child) {|c| c.nil? }
      child.forw = right_node.child
      recompute_node_count(left_node)
      if left_node.nchild <= MAX_CHILD
        left_node.forw = right_node.forw
      else
        overflow(left_node, right_node)
        break
      end
    end
    self
  end

削除時に、 単方向リストの切断等のための場所を探すため、 補助メソッドを使います。

  def find_left(node)
    while not node.nil? and not yield(node.forw)
      node= node.forw
    end
    node
  end