TAILQ のソースを読んで C のポインタをマスターする。

正月は TAILQ のソースを読んでいた。普段 C を読み書きしないので、とても勉強になった。ポインタの使い方がわかった（ような気持ちになれた）。

TAILQって？

TAILQ は C のマクロで書かれた双方向リンクリストの実装。

BSD、OSX や glibc に含まれている。

基本的な使い方は以下のページが参考になった。

本記事では 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