TAILQ のソースを読んで C のポインタをマスターする。
正月は TAILQ のソースを読んでいた。普段 C を読み書きしないので、とても勉強になった。ポインタの使い方がわかった（ような気持ちになれた）。
TAILQって？
TAILQ は C のマクロで書かれた双方向リンクリストの実装。
BSD、OSX や glibc に含まれている。
- http://freebsd.active-venture.com/FreeBSD-srctree/newsrc/sys/queue.h.html
- http://sourceware.org/git/?p=glibc.git;a=blob_plain;f=misc/sys/queue.h;hb=HEAD
基本的な使い方は以下のページが参考になった。
本記事では OSX の、
- /usr/include/sys/queue.h
を参照する。glibc のTAILQでも基本は同じ。
めまい
元々は C の勉強のつもりで tmux のソースを見ていて、何気なく queue.h を開いてめまいがした。
例えばこんな感じ。
#define TAILQ_LAST(head, headname) \ (*(((struct headname *)((head)->tqh_last))->tqh_last)) #define TAILQ_PREV(elm, headname, field) \ (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
ぜんぜん意味がわからない。
#define TAILQ_ENTRY(type) \ struct { \ struct type *tqe_next; /* next element */ \ struct type **tqe_prev; /* address of previous next element */ \ TRACEBUF \ }
なんでnextとprevで型が違うのか。こわい。コメントも何が言いたいのかわからない。前の次の要素のアドレス？prevは前の要素ではないのか。
結局、理解できたと思えるまで2日くらいかかった。
リストを作ってアドレスを出力するサンプル
サンプル
#include <stdio.h> #include <stdlib.h> #include <sys/queue.h> /* 双方向リンクリスト /usr/include/sys/queue.h の TAILQ を理解するための、 サンプルです。 */ /* リスト要素 */ struct list_item { /* ポインタがどこを指しているかわかりやすくするため、 TAILQ_ENTRYの前後にメンバー(num1,num2)を入れる。 */ int num1; /* 要素をリンクする構造体。 tqe_nextに次の要素のアドレスが設定される。 tqe_prevに前の要素のtqe_nextのアドレスが設定される。 */ TAILQ_ENTRY(list_item) links; /* ポインタがどこを指しているかわかりやすくするため、 TAILQ_ENTRYの前後にメンバー(num1,num2)を入れる。 */ int num2; }; /* リストの最初と最後を管理するヘッド構造体を宣言する。 tqh_firstに最初の要素のアドレスが設定される。 tqh_lastに最後の要素のtqe_nextを指すアドレスが設定される。 */ TAILQ_HEAD(list_head, list_item); /* 渡されたヘッドに要素を追加する。 */ void add_items(struct list_head *head) { int i = 0; struct list_item *item; for (i = 0; i < 3; i++) { item = (struct list_item*)malloc(sizeof(struct list_item)); item->num1 = i; item->num2 = 0; /* 末尾に追加する。 */ TAILQ_INSERT_TAIL(head, item, links); } } /* ヘッドのアドレスを出力する。 */ void print_head(struct list_head *head) { printf("-- HEAD\n"); printf("%p: head\n", head); printf("%p: head->tqh_first = %p\n", &(head->tqh_first), head->tqh_first); printf("%p: head->tqh_last = %p\n", &(head->tqh_last), head->tqh_last); } /* リストの各要素を出力する。 */ void print_items(struct list_head *head) { struct list_item *item; /* headが参照するリストをlinksメンバを使ってループする。要素はitemに入れる。 */ TAILQ_FOREACH(item, head, links) { printf("-- TAILQ_FOREACH %d\n", item->num1); /* itemのアドレス */ printf("%p: item\n", item); printf("%p: item->num1 = %d\n", &(item->num1), item->num1); printf("%p: item->links.tqe_next = %p\n", &(item->links.tqe_next), item->links.tqe_next); printf("%p: item->links.tqe_prev = %p\n", &(item->links.tqe_prev), item->links.tqe_prev); printf("%p: item->num2 = %d\n", &(item->num2), item->num2); /* 以下、TAILQ_PREV がどういう仕組みなのか調べるための出力。 TAILQ_PREVは、指定した要素の1つ前の要素を得るためのマクロ。 (*(((struct list_head *)(item->links.tqe_prev))->tqh_last)) のように展開される。 item->links.tqe_prev が指す先を list_headと見なし(struct list_head * にキャスト)、 構造体の2番目のメンバ(tqh_last = tqe_prev)が指す先に書かれた アドレス(tqe_next or tqh_last)が「1つ前の要素」を指している。 「2歩戻って1歩進む」 headまでいくと、tqh_lastによってNULLが返る。 ループが正順でも逆順でも、最後の要素のtqe_nextが終了条件として機能している。 */ struct list_item **prev = item->links.tqe_prev; struct list_head *prev_head = (struct list_head *)prev; printf(" prev_head = %p\n", prev_head); printf(" prev_head->tqh_last = %p\n", prev_head->tqh_last); printf(" *prev_head->tqh_last = %p\n", *prev_head->tqh_last); } } /* リスト用に確保したメモリを解放する。 */ void free_list(struct list_head *head) { printf("-- FREE\n"); /* 要素を順にリストから外して解放 */ struct list_item *item; while(!TAILQ_EMPTY(head)) { item = TAILQ_FIRST(head); printf("%p -> free\n", item); TAILQ_REMOVE(head, item, links); free(item); } /* ヘッドを解放 */ printf("%p -> free\n", head); free(head); } int main(int argc, char *argv[]) { /* mallocを使って、リストの要素とアドレスを揃える。表示をわかりやすくするため。 mallocはヒープに、ローカル変数はスタックに保存される。 */ struct list_head *head = (struct list_head*)malloc(sizeof(struct list_head)); TAILQ_INIT(head); /* リスト作成 */ add_items(head); /* 要素追加 */ print_head(head); /* ヘッド出力 */ print_items(head); /* 要素出力 */ free_list(head); /* メモリ解放 */ return 0; }
これを実行すると、
$ gcc test.c
$ ./a.out
-- HEAD
0x100100080: head
0x100100080: head->tqh_first = 0x100100090
0x100100088: head->tqh_last = 0x1001000d8
-- TAILQ_FOREACH 0
0x100100090: item
0x100100090: item->num1 = 0
0x100100098: item->links.tqe_next = 0x1001000b0
0x1001000a0: item->links.tqe_prev = 0x100100080
0x1001000a8: item->num2 = 0
prev_head = 0x100100080
prev_head->tqh_last = 0x1001000d8
*prev_head->tqh_last = 0x0
-- TAILQ_FOREACH 1
0x1001000b0: item
0x1001000b0: item->num1 = 1
0x1001000b8: item->links.tqe_next = 0x1001000d0
0x1001000c0: item->links.tqe_prev = 0x100100098
0x1001000c8: item->num2 = 0
prev_head = 0x100100098
prev_head->tqh_last = 0x100100080
*prev_head->tqh_last = 0x100100090
-- TAILQ_FOREACH 2
0x1001000d0: item
0x1001000d0: item->num1 = 2
0x1001000d8: item->links.tqe_next = 0x0
0x1001000e0: item->links.tqe_prev = 0x1001000b8
0x1001000e8: item->num2 = 0
prev_head = 0x1001000b8
prev_head->tqh_last = 0x100100098
*prev_head->tqh_last = 0x1001000b0
-- FREE
0x100100090 -> free
0x1001000b0 -> free
0x1001000d0 -> free
0x100100080 -> freeのように出力される。
左側の0x00000000: が、各構造体のメンバが格納されているアドレス。8バイトずつ、0x100100080 〜 0x1001000ef までを使っている。
num1とnum2はリスト要素のデータ。ポインタがどこを指しているか明確にするため、リンク(links)の前後に配置している。
prev_* は TAILQ_PREV がどのように機能しているか調べるための出力。
ポインタはそれぞれ何を指しているか。
おおまかなイメージは、
の図がわかりやすい。実際にはもう少し複雑にできている。上記のサンプルを実行すると、要素3つのリストが作成され、
のようにリンクされる。
TAILQ_FIRST
簡単なところから。TAILQ_FIRSTは先頭の要素を取得する。
#define TAILQ_FIRST(head) ((head)->tqh_first)
head構造体のメンバ tqh_first にはリスト先頭要素のアドレスが入っている。tqh_firstの宣言のアスタリスク(*)は1個。* は「この先struct」を意味する。
#define TAILQ_HEAD(name, type) \ struct name { \ struct type *tqh_first; /* first element */ \ struct type **tqh_last; /* addr of last next element */ \ TRACEBUF \ }
ポインタが指している先の構造体のメンバを取得するときは、アロー演算子(->)が使える。
TAILQ_NEXT
指定された要素(elm)の次の要素を取得するマクロ。
#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
たとえば上のサンプルコードだと、 マクロ引数のfieldにはlinksが指定されて、
(item)->links.tqe_next
と展開される。
最後の要素item2のtqe_nextにはNULLが設定されている。最後までいくと、TAILQ_NEXTはNULLを返す。
TAILQ_FOREACH
TAILQ_FIRSTとTAILQ_NEXTを使うと、正順のループができる。
#define TAILQ_FOREACH(var, head, field) \ for ((var) = TAILQ_FIRST((head)); \ (var); \ (var) = TAILQ_NEXT((var), field))
最後までいくと、TAILQ_NEXTがNULLを返し、ループが終了する。
TAILQ_PREV
PREVは、NEXTよりもずっと複雑になる。
#define TAILQ_PREV(elm, headname, field) \ (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
以下の図はitem2のTAILQ_PREVを取得する場合。
TAILQ_PREVをサンプルコードの変数名で展開すると、
(*(((struct head *)((item)->links.tqe_prev))->tqh_last))
となり、これを分解すると、
struct list_item **prev = item->links.tqe_prev; struct list_head *prev_head = (struct list_head *)prev; *(prev_head->tqh_last)
になる。
まず、item2のtqe_prevを取得する。tqe_prev には、item1のtqe_nextのアドレスが格納されている。
次に、キャストを使って item2 の tqe_prev が list_head を指しているものと見なす。item1 の tqe_prev を tqh_last と呼び換える。
item1の tqh_last (= tqe_prev) には、 item0 の tqe_next のアドレスが格納されている。
最後に、アスタリスク * で item0 の tqe_next に格納されたアドレスを返す。これで item1 の先頭のアドレスが得られる。
item2からitem1を得るために、
- item2->links.tqe_prev
- item1->links.tqe_next
- item1->links.tqe_prev
- item0->links.tqe_next
と辿っていく。
ポイント：
- 2個戻って1個進む。
- 正確には2個戻った先に書かれたアドレスを返す。
- コード上に、図の青矢印に相当する操作はない。
- C のキャストは、ポインタが別の型を指していることにできてしまう。
- links の構造体には名前(タグ名)はついていない。
- link_head と同じ、ポインタの2個の組なのでキャストしても平気。
- ポインタ虎の巻〜ポインタの型
char 4個の配列をintで一気に初期化する(良くない)例。
- struct list_item **tqe_prev;
- ポインタのポインタ。
- 「自分がポインタ、次もポインタ、次の次がstruct」。
- tqe_prevの次の次を辿ると自要素の先頭にたどり着く。
- /* address of previous next element */ というコメントは、previousのtqe_nextメンバという意味か。ちょっとどうかと思う。
TAILQ_PREV 先頭要素の場合。
item1 の TAILQ_PREV を得る場合も item2 と全く同じ。では、リストの先頭 item0 の前の要素を得ようとするとどうなるか。
tqh_lastの呼び換えは発生せず、そのまま最後の要素 item2 の tqe_next に飛ぶ。tqe_nextにはNULLがセットされている。
ポイント：
- item2 のtqe_next が、TAILQ_NEXTとTAILQ_PREV両方の末端を示す値として使われている。
- なんかすごい。
TAILQ_LAST
末尾の要素を得る。
#define TAILQ_PREV(elm, headname, field) \ (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last)) #define TAILQ_LAST(head, headname) \ (*(((struct headname *)((head)->tqh_last) )->tqh_last))
TAILQ_PREV と TAILQ_LAST は、ほぼ一緒。head->tqh_lastのprevのnextでリスト末尾の先頭アドレスを得る。
TAILQ_INSERT_TAIL
リストの更新処理も1つだけ見てみる。
#define TAILQ_INSERT_TAIL(head, elm, field) do { \ TAILQ_NEXT((elm), field) = NULL; \ (elm)->field.tqe_prev = (head)->tqh_last; \ *(head)->tqh_last = (elm); \ (head)->tqh_last = &TAILQ_NEXT((elm), field); \ QMD_TRACE_HEAD(head); \ QMD_TRACE_ELEM(&(elm)->field); \ } while (0)
elmが追加する要素。
do-while(0)は、マクロ展開によりセミコロンが問題を起こすのを避けるため。関数呼び出しのように使える、複数の文からなるマクロを書きたい場合は do-while(0)でラップする。
2行目。elmのtqe_nextをNULLに設定する。
3行目。elmのtqe_prevをheadのtqh_lastに設定する。現在の末尾要素のtqe_nextのアドレス。
4行目。これまでの末尾要素の tqe_next に新しく追加する要素の先頭アドレスを設定。
5行目。headのtqh_lastを、新要素のtqe_nextのアドレスに設定。
残り2行はデバッグ用。
リストが空だった場合は、tqe_prev は head の tqh_first を指す。headの初期化時にtqh_lastがtqh_firstのアドレスに初期化されている。
#define TAILQ_INIT(head) do { \ TAILQ_FIRST((head)) = NULL; \ (head)->tqh_last = &TAILQ_FIRST((head)); \ QMD_TRACE_HEAD(head); \ } while (0) #define TAILQ_FIRST(head) ((head)->tqh_first)
gdb で実行
サンプルプログラムを gdb で実行してアドレスを確認してみる。
$ gcc -g test.c
$ gdb a.out
# 132行目、リストを解放する前にブレークポイントを設定。
(gdb) break 132
# 実行。
(gdb) run
# headを表示。
(gdb) p head
$1 = (struct list_head *) 0x100100080
# headからtqh_firstのアドレス取得。
(gdb) p $1->tqh_first
$2 = (struct list_item *) 0x100100090
# tqh_firstの中身であるitem0を表示。
(gdb) p *$2
$3 = {
num1 = 0,
links = {
tqe_next = 0x1001000b0,
tqe_prev = 0x100100080
},
num2 = 0
}
# tqh_lastがlist_headを指しているものとして取得。
(gdb) p (struct list_head *)head->tqh_last
$4 = (struct list_head *) 0x1001000d8
# $4をlist_headとして表示。
(gdb) p *$4
$5 = {
tqh_first = 0x0,
tqh_last = 0x1001000b8
}
# item2のtqh_last (= tqe_prev)の先の先が、item2自身。
(gdb) p **($4->tqh_last)
$6 = {
num1 = 2,
links = {
tqe_next = 0x0,
tqe_prev = 0x1001000b8
},
num2 = 0
}
# 残りを実行して終了。
(gdb) continue
(gdb) quit