# LinkedList in Chromium

baseディレクトリのコンテナを読もうシリーズ。
今回は[LinkedList](https://source.chromium.org/chromium/chromium/src/+/main:base/containers/linked_list.h)。

## 使い方
LinkedListを実際に使用している[WaylandWindow](https://source.chromium.org/chromium/chromium/src/+/main:ui/ozone/platform/wayland/host/wayland_window.h;drc=db30749cfac300a23a5337987613aaf6cddb973e)と[WaylandSubsurface](https://source.chromium.org/chromium/chromium/src/+/main:ui/ozone/platform/wayland/host/wayland_subsurface.h)を見てみる。

まずNodeになるものは以下のように`base::LinkNode<自分自身>`を継承する。

class WaylandSubsurface : public base::LinkNode<WaylandSubsurface> {
  ...;
}

そのNodeを要素として持つlistを以下のように宣言して保持する。

base::LinkedList<WaylandSubsurface> subsurface_stack_committed_;

このコードではsubsurfaceをスタックで持つためにLinkedListを使用している。

void WaylandSubsurface::CreateSubsurface() {
  ...;
  parent_->subsurface_stack_committed()->Append(this);
  ...;
}

(直上にstd::listがあるが、多分historical reason?)

Appendの他にもInsertBeforeで好きな要素の後ろに挿入することもできる。

list.Append(n1);
list.Append(n3);
n2->InsertBefore(n3);

また、next, previousで移動でき、headやtailで先頭・最後尾にアクセスできる。

## 実装
実装には大きく2パートある。ノードと、それを格納するList。

### Node
まずはLinkNodeを見る。[LinkNode](https://source.chromium.org/chromium/chromium/src/+/main:base/containers/linked_list.h;l=121;drc=e4622aaeccea84652488d1822c28c78b7115684f)がノードの型をtemplate引数として受け取り、LinkedListに使えるNodeのインスタンスを定義する。
その内部実装が[LinkNodeBase](https://source.chromium.org/chromium/chromium/src/+/main:base/containers/linked_list.h;l=88;drc=e4622aaeccea84652488d1822c28c78b7115684f)なのでこちらを見る。

LinkNodeBase() = default;
LinkNodeBase(LinkNodeBase* previous, LinkNodeBase* next)
  : previous_(previous), next_(next) {}

各Nodeは`previous_`と`next_`を持ち、双方向リストのノードとして使える。
Nodeクラスが持つメソッドはInsertBeforeBaseとInserAfterBase。

void LinkNodeBase::InsertBeforeBase(LinkNodeBase* e) {
  CHECK_EQ(previous_, nullptr);
  CHECK_EQ(next_, nullptr);
  next_ = e;
  previous_ = e->previous_;
  e->previous_->next_ = this;
  e->previous_ = this;
}

自身の`previous_`と`next_`を置き換えてくれる。
これのCallerであるLinkNodeのInserBeforeやInserAfterはpublicで実装されており、外からも呼べるようになっている。
また要素を削除したい場合は[LinkNodeBase::RemoveFromList](https://source.chromium.org/chromium/chromium/src/+/main:base/containers/linked_list.cc;l=32;drc=eef4762779d05708d5dfc7d5fe4ea16288069a35)を呼べばprevious_とnext_をがっちゃんこしてくれる。

Nodeに格納されている値はvalue()で取れる。

LinkNodeクラスに直接実装を書かずにLinkedNodeBaseクラスを噛ませているのはおそらく可読性やheaderファイルのサイズなどのためだと思う。
LinkNodeはtemplateクラスなのでheaderファイルでがちゃがちゃ実装を書かないといけない。LinkedNodeBaseを継承させることでtemplateを外すことができlinked_list.ccの中で実装することができた。

### List
[LinkedList](https://source.chromium.org/chromium/chromium/src/+/main:base/containers/linked_list.h;l=157;drc=e4622aaeccea84652488d1822c28c78b7115684f)がリストの実装。

リストが保持しているデータは初期化時から保持する最初のノードの`root_`だけ。
ここで最初と言ったが、これは「最初からある」というだけの意味で、リストの先頭や末尾ということではない。
どういうことかは実装を見てみよう。

LinkedListのctorの中では一見変なことをしている。

LinkedList() : root_(&root_, &root_) {}
LinkedNode<T> root_;

先のセクションで見たとおりLinkNodeのctorの第一引数と第二引数は`previous`と`next`。
これはつまり`root_`の前も後ろも`root_`というcircular listになっている。

まずLinkedListに値を入れるには[Append](https://source.chromium.org/chromium/chromium/src/+/main:base/containers/linked_list.h;l=167;drc=e4622aaeccea84652488d1822c28c78b7115684f)を呼ぶ。

void Append(LinkNode<T>* e) {
  e->InsertBefore(&root_);
}

Appendという行為は`root_`の直前に挿入している。
InsertBeforeでは上で説明した関数なので、当てはめると
root_->e->root_
というcircular listである。

このように、LinkedListは実は内部的にはroot_を起点としたcircular listで、`head`は`root_.next()`、`tail`は`root_previous()`となっている。
またiterationの終点となる`end`には自分自身の`root_`となる。
emptyチェックは`head == end`で良い。

## std::listとの違い
連結リストは標準ライブラリにも[std::list](https://cpprefjp.github.io/reference/list/list.html)という名前で実装されている。
Chromiumの自前実装であるLinkedListは何が違うのだろうか？

一言で言えばLinkedListのほうがパフォーマンスが良い。
パフォーマンスを気にする場合はLinkedListを使ったほうがいいようだ。

std::listで要素を削除する際O(n)かかる。
なぜなら消す要素のイテレータを最初からなめて探す必要があるから。
一方LinkedListではNodeそのものを持つデザインなので、そいつに対してRemoveFromListを呼べばO(1)で消してくれる。

またLinkedListは挿入時にヒープのアロケーションが絶対起きない。これは普通にインスタンスを事前に用意した上でAppendしたりするだけで、Appendではpointerの繋ぎ変えしかしないので新しくheapをがめることはないって話だと思う。
std::listの実装を見ていないので比較はできないがおそらくしているのだろう？

パフォーマンスを気にしない場合はやはり標準ライブラリのほうがメソッドが充実していたり可読性が高かったりするのでstd::listのほうがいいかもしれない。
が別にLinkedListも可読性高いので、常にLinkedList優先で良さそうな気がする。ただしNodeになるクラスをLinkNode継承させないといけないので、ちょっとめんどい。