CIRCLEQ_INSERT_BEFORE(3)

スポンサーリンク

QUEUE(3) FreeBSD ライブラリ関数マニュアル QUEUE(3)

名称

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;

(名前 head と headp は、ユーザが選べます。)

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

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

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

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

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

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

マクロ 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;

(名前 head と headp は、ユーザが選べます。)

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

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

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

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

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

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

マクロ 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;

(名前 head と headp は、ユーザが選べます。)

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

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

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

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

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

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

マクロ 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;

(名前 head と headp は、ユーザが選べます。)

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

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

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

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

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

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

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

マクロ 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;

(名前 head と headp は、ユーザが選べます。)

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

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

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

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

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

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

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

マクロ 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 関数は 4.4BSD ではじめて登場しました。

FreeBSD 10.0 January 24, 1994 FreeBSD 10.0
スポンサーリンク