queue

Autres langues

Langue: ja

Autres versions - même langue

Version: 98338 (fedora - 25/11/07)

Section: 3 (Bibliothèques de fonctions)

Sommaire


BSD mandoc
4BSD

名前

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) キュー・循環キューの実装

書式

Fd #include <sys/queue.h> Fn LIST_ENTRY TYPE Fn LIST_HEAD HEADNAME TYPE Fn LIST_INIT LIST_HEAD *head Fn LIST_INSERT_AFTER LIST_ENTRY *listelm TYPE *elm LIST_ENTRY NAME Fn LIST_INSERT_HEAD LIST_HEAD *head TYPE *elm LIST_ENTRY NAME Fn LIST_REMOVE TYPE *elm LIST_ENTRY NAME Fn TAILQ_ENTRY TYPE Fn TAILQ_HEAD HEADNAME TYPE Fn TAILQ_INIT TAILQ_HEAD *head Fn TAILQ_INSERT_AFTER TAILQ_HEAD *head TYPE *listelm TYPE *elm TAILQ_ENTRY NAME Fn TAILQ_INSERT_HEAD TAILQ_HEAD *head TYPE *elm TAILQ_ENTRY NAME Fn TAILQ_INSERT_TAIL TAILQ_HEAD *head TYPE *elm TAILQ_ENTRY NAME Fn TAILQ_REMOVE TAILQ_HEAD *head TYPE *elm TAILQ_ENTRY NAME Fn CIRCLEQ_ENTRY TYPE Fn CIRCLEQ_HEAD HEADNAME TYPE Fn CIRCLEQ_INIT CIRCLEQ_HEAD *head Fn CIRCLEQ_INSERT_AFTER CIRCLEQ_HEAD *head TYPE *listelm TYPE *elm CIRCLEQ_ENTRY NAME Fn CIRCLEQ_INSERT_BEFORE CIRCLEQ_HEAD *head TYPE *listelm TYPE *elm CIRCLEQ_ENTRY NAME Fn CIRCLEQ_INSERT_HEAD CIRCLEQ_HEAD *head TYPE *elm CIRCLEQ_ENTRY NAME Fn CIRCLEQ_INSERT_TAIL CIRCLEQ_HEAD *head TYPE *elm CIRCLEQ_ENTRY NAME Fn CIRCLEQ_REMOVE CIRCLEQ_HEAD *head TYPE *elm CIRCLEQ_ENTRY NAME

説明

これらのマクロは、次の 3 つのデータ構造を定義して操作する: リスト・テールキュー・循環キュー。 3 つのデータ構造すべてにおいて以下の機能がサポートされている:
  1. 新たなエントリをリストの先頭に挿入する。
  2. 新たなエントリをリストのどの要素よりも後に挿入する。
  3. リストの任意のエントリを削除する。
  4. リストを順方向に辿る。

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

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

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

ただし:

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

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

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

ただし:

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

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

リスト

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

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

 struct HEADNAME *headp;

(名前 head と headp はユーザが選択できる。)

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

マクロ LIST_INIT は Fa head で参照されるリストを初期化する。

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

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

マクロ LIST_REMOVE は要素 Fa 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 重にリンクされており、 任意の要素はテールキューを辿らずに削除できる。 新しい要素は既存の要素の後またはテールキューの先頭または末尾に追加できる。 Fa TAILQ_HEAD 構造体は以下のように定義されている: 
 TAILQ_HEAD(HEADNAME, TYPE) head;

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

 struct HEADNAME *headp;

(名前 head と headp はユーザが選択できる。)

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

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

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

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

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

マクロ TAILQ_REMOVE は要素 Fa 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 Fa CIRCLEQ_HEAD 構造体は以下のように定義されている: 
 CIRCLEQ_HEAD(HEADNAME, TYPE) head;

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

 struct HEADNAME *headp;

(名前 head と headp はユーザが選択できる。)

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

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

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

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

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

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

マクロ CIRCLEQ_REMOVE は要素 Fa 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 関数は BSD 4.4 で初めて登場した。