ccan list の仕組み

[[Feature #9632]](https://bugs.ruby-lang.org/issues/9632) からCRubyの内部実装のlinked listに使われている ccan http://ccodearchive.net/ の ccan/list/list.h についてのメモ。

ccan の最新版ではなくて、CRuby 3.0時点にコミットされている古い ccan を眺めている。

途中で疲れたので書きかけなのだが、そのうち書き足すつもりで残している。

## データ構造
```c
struct list_head
{
	struct list_node n;
};

struct list_node
{
	struct list_node *next, *prev;
};
```

## list_head_init
```c 
struct list_head list;
list_head_init(&list);
```

ccan list を使う時はまず `struct list_head` な変数を用意し、そのアドレスを `list_head_init` に渡して初期化しておく必要がある。これは何をしているかというと、

```c
static inline void list_head_init(struct list_head *h)
{
	h->n.next = h->n.prev = &h->n;
}
```

ここで、`struct list_head` は `struct list_node` だけを持つ構造体のため、`h` と `&h->n` は同じ値である。ただし `struct list_head` のままでは `next` と `prev` と型が合わないので `&h->n` を使っている。

従って、初期化後は以下のように、`n.next` と `n.prev` は両方 `struct list_head` 自身のアドレスを格納していることになる。

```c
struct list_head { // => 0x7fff90ba4510
    struct list_node {
        struct list_node *next = 0x7fff90ba4510;
        struct list_node *prev = 0x7fff90ba4510;
    }
}
```

## LIST_HEAD_INIT
```c 
struct list_head list = LIST_HEAD_INIT(list);
```

宣言後に `list_head_init` を呼ぶかわりに、`struct list_head` を宣言する変数名を `LIST_HEAD_INIT` で囲うことで宣言時に初期化することができる。

これは以下のような実装になっている。

```c 
#define LIST_HEAD_INIT(name) { { &(name).n, &(name).n } }
```

そのため、展開するとこのようになっている。

```c
struct list_head list = { { &(list).n, &(list).n } };
```

宣言中の変数名を参照して循環参照することってできるんだな、と思った。

## list_add_tail
```c
struct list_head list = LIST_HEAD_INIT(list);
struct list_node node;
list_add_tail(&list, &node);
```

`list_add` という先頭に足すバージョンもあるけど、僕が使っているのがたまたま `list_add_tail` の方なので…。これは以下のような実装になっている。

```c 
#define list_add_tail(h, n) list_add_tail_(h, n, LIST_LOC)
static inline void list_add_tail_(struct list_head *h,
				  struct list_node *n,
				  const char *abortstr)
{
	list_add_before_(h, &h->n, n, abortstr);
}

static inline void list_add_before_(struct list_head *h,
				    struct list_node *p,
				    struct list_node *n,
				    const char *abortstr)
{
	n->next = p;
	n->prev = p->prev;
	p->prev->next = n;
	p->prev = n;
	(void)list_debug(h, abortstr);
}

#define LIST_LOC __FILE__  ":" stringify(__LINE__)
#define list_debug(h, loc) ((void)loc, h)
```

`list_debug` は何か書き換えるとデバッグできて便利みたいな感じぽいので無視してよさそう。

`struct list_head` の `struct list_node n` はリストが空でも存在している入れ物なので、`&h->n` は実際のリストの一部ではなく、listのheadおよびtailを持つように作られているのではないかと推察できる。
すると、tailに追加したいpが `h->n.prev` (tail) にセットされるようにして残りの辻褄を合わせると良いはずで、読むと実際そのようになっている。

なお、`struct list_head` の値は常に終端の値として使われるようで、headにあたるlist_nodeのprevとtailにあたるlist_nodeのnextは常に `struct list_head` のアドレスになっているように見える。

## list_del
```c
struct list_head list = LIST_HEAD_INIT(list);
struct list_node node;
list_add_tail(&list, &node);
list_del(&node);
```

実装は以下のようになっている。

```c 
#define list_del(n) list_del_(n, LIST_LOC)
static inline void list_del_(struct list_node *n, const char* abortstr)
{
	(void)list_debug_node(n, abortstr);
	n->next->prev = n->prev;
	n->prev->next = n->next;
#ifdef CCAN_LIST_DEBUG
	/* Catch use-after-del. */
	n->next = n->prev = NULL;
#endif
}
```

流石にこっちは単純なのであまり話すことはない。が、`struct list_head` の参照を終端として持つデザインなおかげで、リストのポインタを渡さずともノードのポインタを渡すだけでいいのは綺麗なデザインになっていると思う。

## list_for_each
```c 
struct list_head list = LIST_HEAD_INIT(list);
struct list_unit {
    int id;
    struct list_node unode;
};
struct list_unit unit1 = { .id = 1 }, unit2 = { .id = 2 };
list_add_tail(&list, &unit1.unode);
list_add_tail(&list, &unit2.unode);

struct list_unit *unit = NULL;
list_for_each(&list, unit, unode) {
    printf("id: %d\n", unit->id);
}
```

一見かっこいいが、最後の引数が変数名じゃなくてstructのメンバ名なところがわかりにくい。実装は以下のようになっている。

```c 
#define list_for_each(h, i, member)					\
	list_for_each_off(h, i, list_off_var_(i, member))

#define list_off_var_(var, member)			\
	(container_off_var(var, member) +		\
	 check_type(var->member, struct list_node))

#define check_type(expr, type)					\
	BUILD_ASSERT_OR_ZERO(sizeof(expr) == sizeof(type))
#define BUILD_ASSERT_OR_ZERO(cond) \
	(sizeof(char [1 - 2*!(cond)]) - 1)

#define container_off_var(var, member)			\
	((const char *)&(var)->member - (const char *)(var))

#define list_for_each_off(h, i, off)                                    \
	list_for_each_off_dir_((h),(i),(off),next)

// TODO...
```

container_offのところは理解したけど、ループする側のコードが階層が深すぎて読む気が失せてきたのでここまで。

## list_for_each_safe
書きたかったけどそのうち。