Provided by: manpages-ja-dev_0.5.0.0.20210215+dfsg-1_all bug

名前

       LIST_ENTRY,   LIST_HEAD,   LIST_INIT,  LIST_INSERT_AFTER,  LIST_INSERT_HEAD,  LIST_REMOVE,
       TAILQ_ENTRY,    TAILQ_HEAD,     TAILQ_INIT,     TAILQ_INSERT_AFTER,     TAILQ_INSERT_HEAD,
       TAILQ_INSERT_TAIL,     TAILQ_REMOVE,     CIRCLEQ_ENTRY,     CIRCLEQ_HEAD,    CIRCLEQ_INIT,
       CIRCLEQ_INSERT_AFTER,  CIRCLEQ_INSERT_BEFORE,  CIRCLEQ_INSERT_HEAD,   CIRCLEQ_INSERT_TAIL,
       CIRCLEQ_REMOVE - リスト・テール (tail) キュー・循環キューの実装

書式

       #include <sys/queue.h>

       LIST_ENTRY(TYPE);
       LIST_HEAD(HEADNAME, TYPE);
       LIST_INIT(LIST_HEAD *head);
       LIST_INSERT_AFTER(LIST_ENTRY *listelm,
                       TYPE *elm, LIST_ENTRY NAME);
       LIST_INSERT_HEAD(LIST_HEAD *head,
                       TYPE *elm, LIST_ENTRY NAME);
       LIST_REMOVE(TYPE *elm, LIST_ENTRY NAME);

       TAILQ_ENTRY(TYPE);
       TAILQ_HEAD(HEADNAME, TYPE);
       TAILQ_INIT(TAILQ_HEAD *head);
       TAILQ_INSERT_AFTER(TAILQ_HEAD *head, TYPE *listelm,
                       TYPE *elm, TAILQ_ENTRY NAME);
       TAILQ_INSERT_HEAD(TAILQ_HEAD *head,
                       TYPE *elm, TAILQ_ENTRY NAME);
       TAILQ_INSERT_TAIL(TAILQ_HEAD *head,
                       TYPE *elm, TAILQ_ENTRY NAME);
       TAILQ_REMOVE(TAILQ_HEAD *head, TYPE *elm, TAILQ_ENTRY NAME);

       CIRCLEQ_ENTRY(TYPE);
       CIRCLEQ_HEAD(HEADNAME, TYPE);
       CIRCLEQ_INIT(CIRCLEQ_HEAD *head);
       CIRCLEQ_INSERT_AFTER(CIRCLEQ_HEAD *head, TYPE *listelm,
                       TYPE *elm, CIRCLEQ_ENTRY NAME);
       CIRCLEQ_INSERT_BEFORE(CIRCLEQ_HEAD *head, TYPE *listelm,
                       TYPE *elm, CIRCLEQ_ENTRY NAME);
       CIRCLEQ_INSERT_HEAD(CIRCLEQ_HEAD *head,
                       TYPE *elm, CIRCLEQ_ENTRY NAME);
       CIRCLEQ_INSERT_TAIL(CIRCLEQ_HEAD *head,
                       TYPE *elm, CIRCLEQ_ENTRY NAME);
       CIRCLEQ_REMOVE(CIRCLEQ_HEAD *head,
                       TYPE *elm, CIRCLEQ_ENTRY NAME);

説明

       これらのマクロは、次の   3   つのデータ構造を定義して操作する:  リスト・テールキュー・循環
       キュー。 3 つのデータ構造すべてにおいて以下の機能がサポートされている:

           *   新たなエントリーをリストの先頭に挿入する。
           *   新たなエントリーをリストのどの要素よりも後に挿入する。
           *   リストの任意のエントリーを削除する。
           *   リストを順方向に辿る。

       リストは 3 つのデータ構造の中で最も単純であり、 上記の機能のみをサポートする。

       テールキューは以下の機能を追加する:

           *   エントリーをリストの最後に追加できる。

       ただし:

           1.  全てのリスト挿入と削除において、リストの先頭を指定しなければならない。
           2.  各先頭エントリーは 1 つではなく 2 つのポインターを必要とする。
           3.  リストと比べて、コードサイズは 15% 大きくなり、操作は 20% 遅くなる。

       循環キューは以下の機能を追加する:

           *   エントリーをリストの最後に追加できる。
           *   エントリーを他のエントリーの前に追加できる。
           *   逆方向に末尾から先頭へ辿ることができる。

       ただし:

           1.  全てのリスト挿入と削除において、リストの先頭を指定しなければならない。
           2.  各先頭エントリーは 1 つではなく 2 つのポインターを必要とする。
           3.  辿る際の終了条件がより複雑である。
           4.  リストと比べて、コードサイズは 40% 大きくなり、操作は 45% 遅くなる。

       マクロ定義において  TYPE   はユーザー定義構造体の名前であり、   LIST_ENTRY,   TAILQ_ENTRY,
       CIRCLEQ_ENTRY  の何れか型のフィールドと  指定された  NAME  を含まなければならない。 引き数
       HEADNAME はユーザー定義構造体の名前であり、 マクロ LIST_HEAD, TAILQ_HEAD, CIRCLEQ_HEAD  を
       用いて宣言されなければならない。  これらのマクロがどのように使われるかについての更なる説明
       は、 以下の例を参照すること。

   リスト
       リストの先頭には、 LIST_HEAD マクロで定義される構造体が置かれる。 この構造体はリストの最初
       の要素へのポインターを 1 つ含む。 要素は 2 重にリンクされており、 任意の要素はリストを辿ら
       ずに削除できる。 新しい要素は既存の要素の後またはリストの先頭に追加できる。 LIST_HEAD 構造
       体は以下のように宣言されている:

           LIST_HEAD(HEADNAME, TYPE) head;

       ここで HEADNAME は定義される構造体の名前であり、 TYPE はリンク内でリンクされる要素の型であ
       る。 リストの先頭へのポインターは、その後で次のように宣言される:

           struct HEADNAME *headp;

       (名前 headheadp はユーザーが選択できる。)

       マクロ LIST_ENTRY はリストの要素を接続する構造体を宣言する。

       マクロ LIST_INIThead で参照されるリストを初期化する。

       マクロ LIST_INSERT_HEAD は新たな要素 elm をリストの先頭に挿入する。

       マクロ LIST_INSERT_AFTER は新たな要素 elm を要素 listelm の後に挿入する。

       マクロ LIST_REMOVE は要素 elm をリストから削除する。

   リストの例
       LIST_HEAD(listhead, entry) head;
       struct listhead *headp;                 /* リストの先頭。*/
       struct entry {
           ...
           LIST_ENTRY(entry) entries;          /* リスト。 */
           ...
       } *n1, *n2, *np;

       LIST_INIT(&head);                       /* リストを初期化する。*/

       n1 = malloc(sizeof(struct entry));      /* 先頭に挿入する。*/
       LIST_INSERT_HEAD(&head, n1, entries);

       n2 = malloc(sizeof(struct entry));      /* 後ろに挿入する。*/
       LIST_INSERT_AFTER(n1, n2, entries);
                                               /* 順方向に辿る。*/
       for (np = head.lh_first; np != NULL; np = np->entries.le_next)
           np-> ...

       while (head.lh_first != NULL)           /* 削除する。*/
           LIST_REMOVE(head.lh_first, entries);

   テールキュー
       テールキューの先頭には TAILQ_HEAD マクロで定義される構造体が置かれる。 この構造体は 1 組の
       ポインターを含んでいる。  1 つはテールキューの最初の要素へのポインターであり、 もう 1 つは
       テールキューの最後の要素へのポインターである。 要素は 2 重にリンクされており、  任意の要素
       はテールキューを辿らずに削除できる。  新しい要素は既存の要素の後またはテールキューの先頭ま
       たは末尾に追加できる。 TAILQ_HEAD 構造体は以下のように定義されている:

           TAILQ_HEAD(HEADNAME, TYPE) head;

       ここで HEADNAME は定義される構造体の名前であり、 TYPE はテールキュー内でリンクされる要素の
       型である。 テールキューの先頭へのポインターは、その後で次のように宣言される:

           struct HEADNAME *headp;

       (名前 headheadp はユーザーが選択できる。)

       マクロ TAILQ_ENTRY はテールキューの要素を接続する構造体を宣言する。

       マクロ TAILQ_INIThead で参照されるテールキューを初期化する。

       マクロ TAILQ_INSERT_HEAD は新たな要素 elm をテールキューの先頭に挿入する。

       マクロ TAILQ_INSERT_TAIL は新たな要素 elm をテールキューの末尾に挿入する。

       マクロ TAILQ_INSERT_AFTER は新たな要素 elm を要素 listelm の後に挿入する。

       マクロ TAILQ_REMOVE は要素 elm をテールキューから削除する。

   テールキューの例
       TAILQ_HEAD(tailhead, entry) head;
       struct tailhead *headp;                 /* テールキューの先頭。*/
       struct entry {
           ...
           TAILQ_ENTRY(entry) entries;         /* テールキュー。*/
           ...
       } *n1, *n2, *np;

       TAILQ_INIT(&head);                      /* キューを初期化する。*/

       n1 = malloc(sizeof(struct entry));      /* 先頭に挿入する。*/
       TAILQ_INSERT_HEAD(&head, n1, entries);

       n1 = malloc(sizeof(struct entry));      /* 末尾に挿入する。*/
       TAILQ_INSERT_TAIL(&head, n1, entries);

       n2 = malloc(sizeof(struct entry));      /* 後ろに挿入する。*/
       TAILQ_INSERT_AFTER(&head, n1, n2, entries);
                                               /* 順方向に辿る。*/
       for (np = head.tqh_first; np != NULL; np = np->entries.tqe_next)
           np-> ...
                                               /* 削除する。*/
       while (head.tqh_first != NULL)
           TAILQ_REMOVE(&head, head.tqh_first, entries);

   循環キュー
       循環キューの先頭には CIRCLEQ_HEAD マクロで定義される構造体が置かれる。 この構造体は 1 組の
       ポインターを含んでいる。 1 つは循環キューの最初の要素へのポインターであり、 もう 1  つは循
       環キューの最後の要素へのポインターである。  要素は  2  重にリンクされており、 任意の要素は
       キューを辿らずに削除できる。  新しい要素は、既存の要素の後または前、またはキューの先頭また
       は末尾に追加できる。 A CIRCLEQ_HEAD 構造体は以下のように定義されている:

           CIRCLEQ_HEAD(HEADNAME, TYPE) head;

       ここで HEADNAME は定義される構造体の名前であり、 TYPE は循環キュー内でリンクされる要素の型
       である。 循環キューの先頭へのポインターは、その後で次のように宣言される:

           struct HEADNAME *headp;

       (名前 headheadp はユーザーが選択できる。)

       マクロ CIRCLEQ_ENTRY は循環キューの要素を接続する構造体を宣言する。

       マクロ CIRCLEQ_INIThead で参照される循環キューを初期化する。

       マクロ CIRCLEQ_INSERT_HEAD は新たな要素 elm を循環キューの先頭に挿入する。

       マクロ CIRCLEQ_INSERT_TAIL は新たな要素 elm を循環キューの末尾に挿入する。

       マクロ CIRCLEQ_INSERT_AFTER は新たな要素 elm を要素 listelm の後に挿入する。

       マクロ CIRCLEQ_INSERT_AFTER は新たな要素 elm を要素 listelm の前に挿入する。

       マクロ CIRCLEQ_REMOVE は要素 elm を循環キューから削除する。

   循環キューの例
       CIRCLEQ_HEAD(circleq, entry) head;
       struct circleq *headp;                  /* 循環キューの先頭。*/
       struct entry {
           ...
           CIRCLEQ_ENTRY(entry) entries;       /* 循環キュー。*/
           ...
       } *n1, *n2, *np;

       CIRCLEQ_INIT(&head);                    /* 循環キューを初期化する。*/

       n1 = malloc(sizeof(struct entry));      /* 先頭に挿入する。*/
       CIRCLEQ_INSERT_HEAD(&head, n1, entries);

       n1 = malloc(sizeof(struct entry));      /* 末尾に挿入する。*/
       CIRCLEQ_INSERT_TAIL(&head, n1, entries);

       n2 = malloc(sizeof(struct entry));      /* 後ろに挿入する。*/
       CIRCLEQ_INSERT_AFTER(&head, n1, n2, entries);

       n2 = malloc(sizeof(struct entry));      /* 前に挿入する。*/
       CIRCLEQ_INSERT_BEFORE(&head, n1, n2, entries);
                                               /* 順方向に辿る。*/
       for (np = head.cqh_first; np != (void *)&head; np = np->entries.cqe_next)
           np-> ...
                                               /* 逆方向に辿る。*/
       for (np = head.cqh_last; np != (void *)&head; np = np->entries.cqe_prev)
           np-> ...
                                               /* 削除する。*/
       while (head.cqh_first != (void *)&head)
           CIRCLEQ_REMOVE(&head, head.cqh_first, entries);

準拠

       POSIX.1-2001 にはない。 BSD 系に存在する。 queue 関数は 4.4BSD で初めて登場した。

この文書について

       この man ページは Linux man-pages プロジェクトのリリース 3.79 の一部  である。プロジェクト
       の説明とバグ報告に関する情報は http://www.kernel.org/doc/man-pages/ に書かれている。