tail head cat sleep
QR code linking to this page

manページ  — QUEUE

名称

SLIST_EMPTY, SLIST_ENTRY, SLIST_FIRST, SLIST_FOREACH, SLIST_HEAD, SLIST_HEAD_INITIALIZER, SLIST_INIT, SLIST_INSERT_AFTER, SLIST_INSERT_HEAD, SLIST_NEXT, SLIST_REMOVE_HEAD, SLIST_REMOVE, STAILQ_EMPTY, STAILQ_ENTRY, STAILQ_FIRST, STAILQ_FOREACH, STAILQ_HEAD, STAILQ_HEAD_INITIALIZER, STAILQ_INIT, STAILQ_INSERT_AFTER, STAILQ_INSERT_HEAD, STAILQ_INSERT_TAIL, STAILQ_LAST, STAILQ_NEXT, STAILQ_REMOVE_HEAD, STAILQ_REMOVE, LIST_EMPTY, LIST_ENTRY, LIST_FIRST, LIST_FOREACH, LIST_HEAD, LIST_HEAD_INITIALIZER, LIST_INIT, LIST_INSERT_AFTER, LIST_INSERT_BEFORE, LIST_INSERT_HEAD, LIST_NEXT, LIST_REMOVE, TAILQ_EMPTY, TAILQ_ENTRY, TAILQ_FIRST, TAILQ_FOREACH, TAILQ_FOREACH_REVERSE, TAILQ_HEAD, TAILQ_HEAD_INITIALIZER, TAILQ_INIT, TAILQ_INSERT_AFTER, TAILQ_INSERT_BEFORE, TAILQ_INSERT_HEAD, TAILQ_INSERT_TAIL, TAILQ_LAST, TAILQ_NEXT, TAILQ_PREV, TAILQ_REMOVE, CIRCLEQ_EMPTY, CIRCLEQ_ENTRY, CIRCLEQ_FIRST, CIRCLEQ_FOREACH, CIRCLEQ_FOREACH_REVERSE, CIRCLEQ_HEAD, CIRCLEQ_HEAD_INITIALIZER, CIRCLEQ_INIT, CIRCLEQ_INSERT_AFTER, CIRCLEQ_INSERT_BEFORE, CIRCLEQ_INSERT_HEAD, CIRCLEQ_INSERT_TAIL, CIRCLE_LAST, CIRCLE_NEXT, CIRCLE_PREV, CIRCLEQ_REMOVE – 単一リンクリスト、単一リンクテールキュー、リスト、テールキュー、 循環キューの実装

内容

書式

#include <sys/queue.h>

SLIST_EMPTY(SLIST_HEAD *head);

SLIST_ENTRY(TYPE);

SLIST_FIRST(SLIST_HEAD *head);

SLIST_FOREACH(TYPE *var, SLIST_HEAD *head, SLIST_ENTRY NAME);

SLIST_HEAD(HEADNAME, TYPE);

SLIST_HEAD_INITIALIZER(SLIST_HEAD head);

SLIST_INIT(SLIST_HEAD *head);

SLIST_INSERT_AFTER(TYPE *listelm, TYPE *elm, SLIST_ENTRY NAME);

SLIST_INSERT_HEAD(SLIST_HEAD *head, TYPE *elm, SLIST_ENTRY NAME);

SLIST_NEXT(TYPE *elm, SLIST_ENTRY NAME);

SLIST_REMOVE_HEAD(SLIST_HEAD *head, SLIST_ENTRY NAME);

SLIST_REMOVE(SLIST_HEAD *head, TYPE *elm, TYPE, SLIST_ENTRY NAME);

STAILQ_EMPTY(STAILQ_HEAD *head);

STAILQ_ENTRY(TYPE);

STAILQ_FIRST(STAILQ_HEAD *head);

STAILQ_FOREACH(TYPE *var, STAILQ_HEAD *head, STAILQ_ENTRY NAME);

STAILQ_HEAD(HEADNAME, TYPE);

STAILQ_HEAD_INITIALIZER(STAILQ_HEAD head);

STAILQ_INIT(STAILQ_HEAD *head);

STAILQ_INSERT_AFTER(STAILQ_HEAD *head, TYPE *listelm, TYPE *elm, STAILQ_ENTRY NAME);

STAILQ_INSERT_HEAD(STAILQ_HEAD *head, TYPE *elm, STAILQ_ENTRY NAME);

STAILQ_INSERT_TAIL(STAILQ_HEAD *head, TYPE *elm, STAILQ_ENTRY NAME);

STAILQ_LAST(STAILQ_HEAD *head, TYPE, STAILQ_ENTRY NAME);

STAILQ_NEXT(TYPE *elm, STAILQ_ENTRY NAME);

STAILQ_REMOVE_HEAD(STAILQ_HEAD *head, STAILQ_ENTRY NAME);

STAILQ_REMOVE(STAILQ_HEAD *head, TYPE *elm, TYPE, STAILQ_ENTRY NAME);

LIST_EMPTY(LIST_HEAD *head);

LIST_ENTRY(TYPE);

LIST_FIRST(LIST_HEAD *head);

LIST_FOREACH(TYPE *var, LIST_HEAD *head, LIST_ENTRY NAME);

LIST_HEAD(HEADNAME, TYPE);

LIST_HEAD_INITIALIZER(LIST_HEAD head);

LIST_INIT(LIST_HEAD *head);

LIST_INSERT_AFTER(TYPE *listelm, TYPE *elm, LIST_ENTRY NAME);

LIST_INSERT_BEFORE(TYPE *listelm, TYPE *elm, LIST_ENTRY NAME);

LIST_INSERT_HEAD(LIST_HEAD *head, TYPE *elm, LIST_ENTRY NAME);

LIST_NEXT(TYPE *elm, LIST_ENTRY NAME);

LIST_REMOVE(TYPE *elm, LIST_ENTRY NAME);

TAILQ_EMPTY(TAILQ_HEAD *head);

TAILQ_ENTRY(TYPE);

TAILQ_FIRST(TAILQ_HEAD *head);

TAILQ_FOREACH(TYPE *var, TAILQ_HEAD *head, TAILQ_ENTRY NAME);

TAILQ_FOREACH_REVERSE(TYPE *var, TAILQ_HEAD *head, HEADNAME, TAILQ_ENTRY NAME);

TAILQ_HEAD(HEADNAME, TYPE);

TAILQ_HEAD_INITIALIZER(TAILQ_HEAD head);

TAILQ_INIT(TAILQ_HEAD *head);

TAILQ_INSERT_AFTER(TAILQ_HEAD *head, TYPE *listelm, TYPE *elm, TAILQ_ENTRY NAME);

TAILQ_INSERT_BEFORE(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_LAST(TAILQ_HEAD *head, HEADNAME);

TAILQ_NEXT(TYPE *elm, TAILQ_ENTRY NAME);

TAILQ_PREV(TYPE *elm, HEADNAME, TAILQ_ENTRY NAME);

TAILQ_REMOVE(TAILQ_HEAD *head, TYPE *elm, TAILQ_ENTRY NAME);

CIRCLEQ_EMPTY(CIRCLEQ_HEAD *head);

CIRCLEQ_ENTRY(TYPE);

CIRCLEQ_FIRST(CIRCLEQ_HEAD *head);

CIRCLEQ_FOREACH(TYPE *var, CIRCLEQ_HEAD *head, CIRCLEQ_ENTRY NAME);

CIRCLEQ_FOREACH_REVERSE(TYPE *var, CIRCLEQ_HEAD *head, CIRCLEQ_ENTRY NAME);

CIRCLEQ_HEAD(HEADNAME, TYPE);

CIRCLEQ_HEAD_INITIALIZER(CIRCLEQ_HEAD head);

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_LAST(CIRCLEQ_HEAD *head);

CIRCLEQ_NEXT(TYPE *elm, CIRCLEQ_ENTRY NAME);

CIRCLE_PREV(TYPE *elm, CIRCLEQ_ENTRY NAME);

CIRCLEQ_REMOVE(CIRCLEQ_HEAD *head, TYPE *elm, CIRCLEQ_ENTRY NAME);

解説

このマクロは、単一リンクリスト、単一リンクテールキュー、リスト、 テールキュー、循環キューという、5 種類のデータ構造を定義してそこで動作します。 5 つのデータ構造はすべて、以下の機能をサポートします。
  1. リストの先頭に新しいエントリを挿入する。
  2. リストに存在する任意の要素の後ろに新しいエントリを挿入する。
  3. リストの先頭からエントリを O(1) 削除する。
  4. リストの任意のエントリを O(n) 削除する。
  5. リストを前から走査する。

単一リンクリストは、5 つのデータ構造の中で最も単純で、上の 5つの機能し かサポートしません。 単一リンクリストは、 データセットが大きく、削除がほとんどない、もしくは、全くないアプリケーション、 または LIFO キューの実装に理想的です。

単一リンクテールキューには以下の機能もあります。

  1. リストの末尾にエントリを追加する。
しかし以下に注意してください。
  1. リストの挿入では、リストのヘッドを必ず指定する必要がある。
  2. 各ヘッドエントリでは、1 つではなく 2 つのポインタが必要である。
  3. 単一リンクリストより、コードサイズは約 15% 大きく、動作は約 20% 遅い。

単一リンクテールキューは、 データセットが大きく、削除がほとんどない、もしくは、全くないアプリケーション、 または FIFO キューの実装に理想的です。

二重リンクタイプのすべてのデータ構造 (リスト、テールキュー、循環キュー) には 以下の機能もあります。

  1. リストに存在する任意の要素の前に新しいエントリを挿入する。
  2. リストの任意のエントリを O(1) 削除する。
しかし以下に注意してください。
  1. 各要素には、1 つではなく 2 つのポインタが必要である。
  2. 単一リンクデータ構造より、コードサイズと実行時間 (削除は除く) が約 2 倍に なる。

リンクリストは、二重リンクデータ構造の中で最も単純で、単一リンクリストの 機能に加えて上の機能しかサポートしません。

テールキューには以下の機能もあります。

  1. リストの末尾にエントリを追加する。
  2. 末尾から先頭へと逆に走査する。
しかし以下に注意してください。
  1. リストの挿入と削除では、リストのヘッドを必ず指定する必要がある。
  2. 各ヘッドエントリでは、1 つではなく 2 つのポインタが必要である。
  3. 単一リンクリストより、コードサイズは約 15% 大きく、処理時間は約 20% 長い。

循環キューには以下の機能もあります。

  1. リストの末尾にエントリを追加する。
  2. 末尾から先頭へと逆に走査する。
しかし以下に注意してください。
  1. リストの挿入と削除では、リストのヘッドを必ず指定する必要がある。
  2. 各ヘッドエントリでは、1 つではなく 2 つのポインタが必要である。
  3. 走査の終了条件がより複雑である。
  4. リストより、コードサイズは約 40% 大きく、処理時間は約 45% 長い。

マクロ定義では、 TYPE はユーザが定義した構造体の名前です。この構造体には、 NAME という名前が付いた、 SLIST_ENTRY, STAILQ_ENTRY, LIST_ENTRY, TAILQ_ENTRY, CIRCLEQ_ENTRY という型のフィールドを含める必要があります。 引数 HEADNAME は マクロ SLIST_HEAD, STAILQ_HEAD, LIST_HEAD, TAILQ_HEAD, CIRCLEQ_HEAD で宣言する必要のある、ユーザが定義した構造体の名前です。 このマクロの使用法の詳細については、以下の使用例を参照してください。

単一リンクリスト

単一リンクリストの最初には、 SLIST_HEAD マクロで定義される構造体が付きます。 この構造体には、リストの先頭の要素を指すポインタが 1 つ含まれます。 要素は、任意の要素の O(n) 削除を犠牲にして、 スペースとポインタ操作のオーバヘッドが最小になるように単一リンクされます。 新しい要素は、既存の要素の後ろ、リストの先頭でリストに追加できます。 SLIST_HEAD 構造体は以下のように宣言されます。
SLIST_HEAD(HEADNAME, TYPE) head;

ここで HEADNAME は定義する構造体の名前で、 TYPE はリストにリンクする要素の型です。 リストのヘッドのポインタは、後で以下のように宣言できます。

struct HEADNAME *headp;

(名前 headheadp は、ユーザが選べます。)

マクロ SLIST_HEAD_INITIALIZER はリストの head を初期化します。

マクロ SLIST_EMPTY はリストに要素がない場合に真になります。

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

マクロ SLIST_FIRST はリストの先頭の要素を、リストが空なら NULL を返します。

マクロ SLIST_FOREACHhead で参照されるリストを、各要素を順に var に割り当てて順方向に走査します。

マクロ SLIST_INIThead が参照するリストを初期化します。

マクロ SLIST_INSERT_HEAD は新しい要素 elm をリストの先頭に挿入します。

マクロ SLIST_INSERT_AFTER は要素 listelm の後ろに新しい要素 elm を挿入します。

マクロ SLIST_NEXT はリストの次の要素を返します。

マクロ SLIST_REMOVE_HEAD はリストの先頭から要素 elm を削除します。 最適な効率を得るために、リストの先頭から要素を削除する場合には 一般的な SLIST_REMOVE マクロの代わりにこのマクロを明示的に使用すべきです。

マクロ SLIST_REMOVE はリストから要素 elm を削除します。

単一リンクリストの使用例

SLIST_HEAD(slisthead, entry) head =
    SLIST_HEAD_INITIALIZER(head);
struct slisthead *headp;                /* 単一リンクリストヘッド */
struct entry {
        ...
        SLIST_ENTRY(entry) entries;     /* 単一リンクリスト */
        ...
} *n1, *n2, *n3, *np;

SLIST_INIT(&head);                      /* リストを初期化 */

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

n2 = malloc(sizeof(struct entry));      /* 後ろに挿入 */ SLIST_INSERT_AFTER(n1, n2, entries);

SLIST_REMOVE(&head, n2, entry, entries);/* 削除 */ free(n2);

n3 = SLIST_FIRST(&head); SLIST_REMOVE_HEAD(&head, entries);      /* 先頭から削除 */ free(n3);                                         /* 順走査 */ SLIST_FOREACH(np, &head, entries)         np-> ...

while (!SLIST_EMPTY(&head)) {           /* リストの削除 */         n1 = SLIST_FIRST(&head);         SLIST_REMOVE_HEAD(&head, entries);         free(n1); }

単一リンクテールキュー

単一リンクテールキューの最初には、 STAILQ_HEAD マクロで定義される構造体がつきます。 この構造体にはテールキューの先頭の要素を指すポインタと テールキューの末尾の要素を指すポインタの 2 つが含まれます。 要素は、任意の要素の O(n) 削除を犠牲にして、 スペースとポインタ操作のオーバヘッドが最小になるように単一リンクされます。 新しい要素は、既存の要素の後ろ、テールキューの先頭、テールキューの末尾で テールキューに追加できます。 STAILQ_HEAD 構造体は以下のように宣言されます。
STAILQ_HEAD(HEADNAME, TYPE) head;

ここで HEADNAME は定義する構造体の名前で、 TYPE はテールキューにリンクする要素の型です。 テールキューのヘッドのポインタは、後で以下のように宣言できます。

struct HEADNAME *headp;

(名前 headheadp は、ユーザが選べます。)

マクロ STAILQ_HEAD_INITIALIZER はテールキューの head を初期化します。

マクロ STAILQ_EMPTY はテールキューに要素がない場合に真になります。

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

マクロ STAILQ_FIRST はテールキューの先頭の要素を、テールキューが空なら NULL を返します。

マクロ STAILQ_FOREACHhead で参照されるテールキューを、各要素を順に var に割り当てて順方向に走査します。

マクロ STAILQ_INIThead が参照するテールキューを初期化します。

マクロ STAILQ_INSERT_HEAD は新しい要素 elm をテールキューの先頭に挿入します。

マクロ STAILQ_INSERT_TAIL は新しい要素 elm をテールキューの末尾に挿入します。

マクロ STAILQ_INSERT_AFTER は新しい要素 elm を要素 listelm の後ろに挿入します。

マクロ STAILQ_LAST はテールキューの末尾の要素を返します。 テールキューが空なら、戻り値は未定義です。

マクロ STAILQ_NEXT はテールキューの次の要素を、この要素が末尾なら NULL を返します。

マクロ STAILQ_REMOVE_HEAD はテールキューの先頭から要素 を削除します。 最適な効率を得るために、テールキューの先頭から要素を削除する場合には 一般的な STAILQ_REMOVE マクロよりもこのマクロを明示的に使用すべきです。

マクロ STAILQ_REMOVE はテールキューから要素 elm を削除します。

単一リンクテールキューの使用例

STAILQ_HEAD(stailhead, entry) head =
    STAILQ_HEAD_INITIALIZER(head);
struct stailhead *headp;                /* 単一リンクテールキューヘッド */
struct entry {
        ...
        STAILQ_ENTRY(entry) entries;    /* テールキュー */
        ...
} *n1, *n2, *n3, *np;

STAILQ_INIT(&head);                     /* キューを初期化 */

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

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

n2 = malloc(sizeof(struct entry));      /* 後ろに挿入 */ STAILQ_INSERT_AFTER(&head, n1, n2, entries);                                         /* 削除 */ STAILQ_REMOVE(&head, n2, entry, entries); free(n2);                                         /* 先頭から削除 */ n3 = STAILQ_FIRST(&head); STAILQ_REMOVE_HEAD(&head, entries); free(n3);                                         /* 順走査 */ STAILQ_FOREACH(np, &head, entries)         np-> ...                                         /* テールキューの削除 */ while (!STAILQ_EMPTY(&head)) {         n1 = STAILQ_FIRST(&head);         STAILQ_REMOVE_HEAD(&head, entries);         free(n1); }                                         /* テールキューの高速な削除 */ n1 = STAILQ_FIRST(&head); while (n1 != NULL) {         n2 = STAILQ_NEXT(n1, entries);         free(n1);         n1 = n2; } STAILQ_INIT(&head);

リスト

リストの最初には、 LIST_HEAD マクロで定義される構造体が付きます。 この構造体には、リストの先頭の要素を指すポインタが 1 つ含まれます。 要素は二重にリンクされているので、リストを走査せずに任意の要素を削除できます。 新しい要素は、既存の要素の前、既存の要素の後、リストの先頭で リストに追加できます。 LIST_HEAD 構造体は、以下のように宣言されます。
LIST_HEAD(HEADNAME, TYPE) head;

ここで HEADNAME は定義する構造体の名前で、 TYPE はリストにリンクする要素の型です。 リストのヘッドのポインタは、後で以下のように宣言できます。

struct HEADNAME *headp;

(名前 headheadp は、ユーザが選べます。)

マクロ LIST_HEAD_INITIALIZER はリストの head を初期化します。

マクロ LIST_EMPTY はリストに要素がない場合に真になります。

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

マクロ LIST_FIRST はリストの最初の要素を、リストが空なら NULL を返します。

マクロ LIST_FOREACHhead で参照されるリストを、各要素を順に var に割り当てて順方向に走査します。

マクロ LIST_INIThead が参照するリストを初期化します。

マクロ LIST_INSERT_HEAD は新しい要素 elm をリストの先頭に挿入します。

マクロ LIST_INSERT_AFTER は新しい要素 elm を要素 listelm の後ろに挿入します。

マクロ LIST_INSERT_BEFORE は新しい要素 elm を要素 listelm の前に挿入します。

マクロ LIST_NEXT はリストの次の要素を、この要素が末尾なら NULL を返します。

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

リストの使用例

LIST_HEAD(listhead, entry) head =
    LIST_HEAD_INITIALIZER(head);
struct listhead *headp;                 /* リストヘッド */
struct entry {
        ...
        LIST_ENTRY(entry) entries;      /* リスト */
        ...
} *n1, *n2, *n3, *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);

n3 = malloc(sizeof(struct entry));      /* 前に挿入 */ LIST_INSERT_BEFORE(n2, n3, entries);

LIST_REMOVE(n2, entries);               /* 削除 */ free(n2);                                         /* 順走査 */ LIST_FOREACH(np, &head, entries)         np-> ...

while (!LIST_EMPTY(&head)) {            /* リストの削除 */         n1 = LIST_FIRST(&head);         LIST_REMOVE(n1, entries);         free(n1); }

n1 = LIST_FIRST(&head);                 /* リストの高速な削除 */ while (n1 != NULL) {         n2 = LIST_NEXT(n1, entries);         free(n1);         n1 = n2; } LIST_INIT(&head);

テールキュー

テールキューの最初には、 TAILQ_HEAD マクロで定義される構造体が付きます。 この構造体には、テールキューの最初の要素を指すポインタと テールキューの先頭の要素を指すポインタの 2 つが含まれます。 要素は二重にリンクされているので、テールキューを走査せずに 任意の要素を削除できます。 新しい要素は、既存の要素の前、既存の要素の後、テールキューの先頭、 テールキューの末尾でテールキューに追加できます。 TAILQ_HEAD 構造体は、以下のように宣言されています。
TAILQ_HEAD(HEADNAME, TYPE) head;

ここで HEADNAME は定義する構造体の名前で、 TYPE はテールキューにリンクする要素の型です。 テールキューのヘッドのポインタは、後で以下のように宣言されます。

struct HEADNAME *headp;

(名前 headheadp は、ユーザが選べます。)

マクロ TAILQ_HEAD_INITIALIZER はテールキューの head を初期化します。

マクロ TAILQ_EMPTY はテールキューに要素がない場合に真になります。

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

マクロ TAILQ_FIRST はテールキューの最初の要素を、テールキューが空なら NULL を返します。

マクロ TAILQ_FOREACHhead で参照されるテールキューを、各要素を順に var に割り当てて順方向に走査します。

マクロ TAILQ_FOREACH_REVERSEhead で参照されるテールキューを、各要素を順に var に割り当てて逆方向に走査します。

マクロ TAILQ_INIThead が参照するテールキューを初期化します。

マクロ TAILQ_INSERT_HEAD は新しい要素 elm をテールキューの先頭に挿入します。

マクロ TAILQ_INSERT_TAIL は新しい要素 elm をテールキューの末尾に挿入します。

マクロ TAILQ_INSERT_AFTER は新しい要素 elm を要素 listelm の後ろに挿入します。

マクロ TAILQ_INSERT_BEFORE は新しい要素 elm を要素 listelm の前に挿入します。

マクロ TAILQ_LAST はテールキューの末尾の要素を返します。 テールキューが空の場合、戻り値は未定義です。

マクロ TAILQ_NEXT はテールキューの次の要素を、その要素が末尾の場合は NULL を返します。

マクロ TAILQ_PREV はテールキューの前の要素を、その要素が先頭の場合は NULL を返します。

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

テールキューの使用例

TAILQ_HEAD(tailhead, entry) head =
    TAILQ_HEAD_INITIALIZER(head);
struct tailhead *headp;                 /* テールキューヘッド */
struct entry {
        ...
        TAILQ_ENTRY(entry) entries;     /* テールキュー */
        ...
} *n1, *n2, *n3, *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);

n3 = malloc(sizeof(struct entry));      /* 前に挿入 */ TAILQ_INSERT_BEFORE(n2, n3, entries);

TAILQ_REMOVE(&head, n2, entries);       /* 削除 */ free(n2);                                         /* 順走査 */ TAILQ_FOREACH(np, &head, entries)         np-> ...                                         /* 逆走査 */ TAILQ_FOREACH_REVERSE(np, &head, tailhead, entries)         np-> ...                                         /* テールキューの削除 */ while (!TAILQ_EMPTY(&head)) {         n1 = TAILQ_FIRST(&head);         TAILQ_REMOVE(&head, n1, entries);         free(n1); }                                         /* テールキューの高速な削除 */ n1 = TAILQ_FIRST(&head); while (n1 != NULL) {         n2 = TAILQ_NEXT(n1, entries);         free(n1);         n1 = n2; } TAILQ_INIT(&head);

循環キュー

循環キューの最初には、 CIRCLEQ_HEAD マクロで定義される構造体が付きます。 この構造体には、循環キューの先頭の要素を指すポインタと 循環キューの末尾の要素を指すポインタの 2 つが含まれます。 要素は二重にリンクされているので、キューを走査せずに 任意の要素を削除できます。 新しい要素は、既存の要素の前、既存の要素の後ろ、循環キューの先頭、 循環キューの末尾で循環キューに追加できます。 CIRCLEQ_HEAD 構造体は以下のように宣言されます。
CIRCLEQ_HEAD(HEADNAME, TYPE) head;

ここで HEADNAME は定義する構造体の名前で、 TYPE は循環キューにリンクする要素の型です。 循環キューのヘッドのポインタは、後で以下のように宣言できます。

struct HEADNAME *headp;

(名前 headheadp は、ユーザが選べます。)

マクロ CIRCLEQ_HEAD_INITIALIZER は循環キューの head を初期化します。

マクロ CIRCLEQ_EMPTY は循環キューに要素がない場合に真になります。

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

マクロ CIRCLEQ_FIRST は循環キューの先頭の要素を返します。

マクロ CICRLEQ_FOREACHhead で参照される循環キューを、各要素を順に var に割り当てて順方向に走査します。

マクロ CICRLEQ_FOREACH_REVERSEhead で参照される循環キューを、各要素を順に var に割り当てて逆方向に走査します。

マクロ CIRCLEQ_INIThead が参照する循環キューを初期化します。

マクロ CIRCLEQ_INSERT_HEAD は新しい要素 elm を循環キューの先頭に挿入します。

マクロ CIRCLEQ_INSERT_TAIL は新しい要素 elm を循環キューの末尾に挿入します。

マクロ CIRCLEQ_INSERT_AFTER は新しい要素 elm を要素 listelm の後ろに挿入します。

マクロ CIRCLEQ_INSERT_BEFORE は新しい要素 elm を要素 listelm の前に挿入します。

マクロ CIRCLEQ_LAST は循環キューの末尾の要素を返します。

マクロ CIRCLEQ_NEXT は循環キューの次の要素を返します。

マクロ CIRCLEQ_PREV は循環キューの前の要素を返します。

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

循環キューの使用例

CIRCLEQ_HEAD(circlehead, entry) head =
    CIRCLEQ_HEAD_INITIALIZER(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);

CIRCLEQ_REMOVE(&head, n1, entries);     /* 削除 */ free(n1);                                         /* 順走査 */ CIRCLEQ_FOREACH(np, &head, entries)         np-> ...                                         /* 逆走査 */ CIRCLEQ_FOREACH_REVERSE(np, &head, entries)         np-> ...                                         /* 循環キューの削除 */ while (CIRCLEQ_FIRST(&head) != (void *)&head) {         n1 = CIRCLEQ_HEAD(&head);         CIRCLEQ_REMOVE(&head, n1, entries);         free(n1); }                                         /* 循環キューの高速な削除 */ n1 = CIRCLEQ_FIRST(&head); while (n1 != (void *)&head) {         n2 = CIRCLEQ_NEXT(n1, entries);         free(n1);         n1 = n2; } CIRCLEQ_INIT(&head);

歴史

queue 関数は BSD 4.4 ではじめて登場しました。

QUEUE (3) January 24, 1994

tail head cat sleep
QR code linking to this page


このマニュアルページサービスについてのご意見は Ben Bullock にお知らせください。 Privacy policy.

On two occasions I have been asked [by members of Parliament], 'Pray, Mr. Babbage, if you put into the machine wrong figures, will the right answers come out?' I am not able rightly to apprehend the kind of confusion of ideas that could provoke such a question.
— Charles Babbage