総合手引 | セクション 3 | English | オプション |
#include <sys/queue.h>
単一リンクリストは、5 つのデータ構造の中で最も単純で、上の 5つの機能し かサポートしません。 単一リンクリストは、 データセットが大きく、削除がほとんどない、もしくは、全くないアプリケーション、 または LIFO キューの実装に理想的です。
単一リンクテールキューには以下の機能もあります。
単一リンクテールキューは、 データセットが大きく、削除がほとんどない、もしくは、全くないアプリケーション、 または FIFO キューの実装に理想的です。
二重リンクタイプのすべてのデータ構造 (リスト、テールキュー、循環キュー) には 以下の機能もあります。
リンクリストは、二重リンクデータ構造の中で最も単純で、単一リンクリストの 機能に加えて上の機能しかサポートしません。
テールキューには以下の機能もあります。
循環キューには以下の機能もあります。
マクロ定義では、 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(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(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(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(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(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 (3) | January 24, 1994 |
総合手引 | セクション 3 | English | オプション |
このマニュアルページサービスについてのご意見は Ben Bullock にお知らせください。 Privacy policy.
“ | If you have any trouble sounding condescending, find a Unix user to show you how it's done. | ” |
— Scott Adams |