.\" Copyright (c) 1993 .\" The Regents of the University of California. All rights reserved. .\" .\" Redistribution and use in source and binary forms, with or without .\" modification, are permitted provided that the following conditions .\" are met: .\" 1. Redistributions of source code must retain the above copyright .\" notice, this list of conditions and the following disclaimer. .\" 2. Redistributions in binary form must reproduce the above copyright .\" notice, this list of conditions and the following disclaimer in the .\" documentation and/or other materials provided with the distribution. .\" 3. All advertising materials mentioning features or use of this software .\" must display the following acknowledgement: .\" This product includes software developed by the University of .\" California, Berkeley and its contributors. .\" 4. Neither the name of the University nor the names of its contributors .\" may be used to endorse or promote products derived from this software .\" without specific prior written permission. .\" .\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND .\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE .\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE .\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE .\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL .\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS .\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) .\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT .\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY .\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF .\" SUCH DAMAGE. .\" .\" @(#) queue. 3 8.2 (Berkeley) 1/24/94 .\" %FreeBSD: src/share/man/man3/queue. 3, v 1.15. 2.7 2001/12/18 10:09:02 ru Exp % .\" $FreeBSD: doc/ja_JP.eucJP/man/man3/queue. 3, v 1.5 2002/05/18 07:12:56 horikawa Exp $ .\" .Dd January 24, 1994 .Dt QUEUE 3 .Os .Sh 명칭 .Nm SLIST_EMPTY , .Nm SLIST_ENTRY , .Nm SLIST_FIRST , .Nm SLIST_FOREACH , .Nm SLIST_HEAD , .Nm SLIST_HEAD_INITIALIZER , .Nm SLIST_INIT , .Nm SLIST_INSERT_AFTER , .Nm SLIST_INSERT_HEAD , .Nm SLIST_NEXT , .Nm SLIST_REMOVE_HEAD , .Nm SLIST_REMOVE , .Nm STAILQ_EMPTY , .Nm STAILQ_ENTRY , .Nm STAILQ_FIRST , .Nm STAILQ_FOREACH , .Nm STAILQ_HEAD , .Nm STAILQ_HEAD_INITIALIZER , .Nm STAILQ_INIT , .Nm STAILQ_INSERT_AFTER , .Nm STAILQ_INSERT_HEAD , .Nm STAILQ_INSERT_TAIL , .Nm STAILQ_LAST , .Nm STAILQ_NEXT , .Nm STAILQ_REMOVE_HEAD , .Nm STAILQ_REMOVE , .Nm LIST_EMPTY , .Nm LIST_ENTRY , .Nm LIST_FIRST , .Nm LIST_FOREACH , .Nm LIST_HEAD , .Nm LIST_HEAD_INITIALIZER , .Nm LIST_INIT , .Nm LIST_INSERT_AFTER , .Nm LIST_INSERT_BEFORE , .Nm LIST_INSERT_HEAD , .Nm LIST_NEXT , .Nm LIST_REMOVE , .Nm TAILQ_EMPTY , .Nm TAILQ_ENTRY , .Nm TAILQ_FIRST , .Nm TAILQ_FOREACH , .Nm TAILQ_FOREACH_REVERSE , .Nm TAILQ_HEAD , .Nm TAILQ_HEAD_INITIALIZER , .Nm TAILQ_INIT , .Nm TAILQ_INSERT_AFTER , .Nm TAILQ_INSERT_BEFORE , .Nm TAILQ_INSERT_HEAD , .Nm TAILQ_INSERT_TAIL , .Nm TAILQ_LAST , .Nm TAILQ_NEXT , .Nm TAILQ_PREV , .Nm TAILQ_REMOVE , .Nm CIRCLEQ_EMPTY , .Nm CIRCLEQ_ENTRY , .Nm CIRCLEQ_FIRST , .Nm CIRCLEQ_FOREACH , .Nm CIRCLEQ_FOREACH_REVERSE , .Nm CIRCLEQ_HEAD , .Nm CIRCLEQ_HEAD_INITIALIZER , .Nm CIRCLEQ_INIT , .Nm CIRCLEQ_INSERT_AFTER , .Nm CIRCLEQ_INSERT_BEFORE , .Nm CIRCLEQ_INSERT_HEAD , .Nm CIRCLEQ_INSERT_TAIL , .Nm CIRCLE_LAST , .Nm CIRCLE_NEXT , .Nm CIRCLE_PREV , .Nm CIRCLEQ_REMOVE .Nd 단일 링크 리스트, 단일 링크 테일 큐, 리스트, 테일 큐, 순환 큐의 실장 .Sh 서식 .In sys/queue.h .\" .Fn SLIST_EMPTY "SLIST_HEAD *head" .Fn SLIST_ENTRY "TYPE" .Fn SLIST_FIRST "SLIST_HEAD *head" .Fn SLIST_FOREACH "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" .Fn SLIST_HEAD "HEADNAME" "TYPE" .Fn SLIST_HEAD_INITIALIZER "SLIST_HEAD head" .Fn SLIST_INIT "SLIST_HEAD *head" .Fn SLIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "SLIST_ENTRY NAME" .Fn SLIST_INSERT_HEAD "SLIST_HEAD *head" "TYPE *elm" "SLIST_ENTRY NAME" .Fn SLIST_NEXT "TYPE *elm" "SLIST_ENTRY NAME" .Fn SLIST_REMOVE_HEAD "SLIST_HEAD *head" "SLIST_ENTRY NAME" .Fn SLIST_REMOVE "SLIST_HEAD *head" "TYPE *elm" "TYPE" "SLIST_ENTRY NAME" .\" .Fn STAILQ_EMPTY "STAILQ_HEAD *head" .Fn STAILQ_ENTRY "TYPE" .Fn STAILQ_FIRST "STAILQ_HEAD *head" .Fn STAILQ_FOREACH "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" .Fn STAILQ_HEAD "HEADNAME" "TYPE" .Fn STAILQ_HEAD_INITIALIZER "STAILQ_HEAD head" .Fn STAILQ_INIT "STAILQ_HEAD *head" .Fn STAILQ_INSERT_AFTER "STAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "STAILQ_ENTRY NAME" .Fn STAILQ_INSERT_HEAD "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME" .Fn STAILQ_INSERT_TAIL "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME" .Fn STAILQ_LAST "STAILQ_HEAD *head" "TYPE" "STAILQ_ENTRY NAME" .Fn STAILQ_NEXT "TYPE *elm" "STAILQ_ENTRY NAME" .Fn STAILQ_REMOVE_HEAD "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" .Fn STAILQ_REMOVE "STAILQ_HEAD *head" "TYPE *elm" "TYPE" "STAILQ_ENTRY NAME" .\" .Fn LIST_EMPTY "LIST_HEAD *head" .Fn LIST_ENTRY "TYPE" .Fn LIST_FIRST "LIST_HEAD *head" .Fn LIST_FOREACH "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME" .Fn LIST_HEAD "HEADNAME" "TYPE" .Fn LIST_HEAD_INITIALIZER "LIST_HEAD head" .Fn LIST_INIT "LIST_HEAD *head" .Fn LIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME" .Fn LIST_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME" .Fn LIST_INSERT_HEAD "LIST_HEAD *head" "TYPE *elm" "LIST_ENTRY NAME" .Fn LIST_NEXT "TYPE *elm" "LIST_ENTRY NAME" .Fn LIST_REMOVE "TYPE *elm" "LIST_ENTRY NAME" .\" .Fn TAILQ_EMPTY "TAILQ_HEAD *head" .Fn TAILQ_ENTRY "TYPE" .Fn TAILQ_FIRST "TAILQ_HEAD *head" .Fn TAILQ_FOREACH "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME" .Fn TAILQ_FOREACH_REVERSE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME" .Fn TAILQ_HEAD "HEADNAME" "TYPE" .Fn TAILQ_HEAD_INITIALIZER "TAILQ_HEAD head" .Fn TAILQ_INIT "TAILQ_HEAD *head" .Fn TAILQ_INSERT_AFTER "TAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME" .Fn TAILQ_INSERT_BEFORE "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_LAST "TAILQ_HEAD *head" "HEADNAME" .Fn TAILQ_NEXT "TYPE *elm" "TAILQ_ENTRY NAME" .Fn TAILQ_PREV "TYPE *elm" "HEADNAME" "TAILQ_ENTRY NAME" .Fn TAILQ_REMOVE "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME" .\" .Fn CIRCLEQ_EMPTY "CIRCLEQ_HEAD *head" .Fn CIRCLEQ_ENTRY "TYPE" .Fn CIRCLEQ_FIRST "CIRCLEQ_HEAD *head" .Fn CIRCLEQ_FOREACH "TYPE *var" "CIRCLEQ_HEAD *head" "CIRCLEQ_ENTRY NAME" .Fn CIRCLEQ_FOREACH_REVERSE "TYPE *var" "CIRCLEQ_HEAD *head" "CIRCLEQ_ENTRY NAME" .Fn CIRCLEQ_HEAD "HEADNAME" "TYPE" .Fn CIRCLEQ_HEAD_INITIALIZER "CIRCLEQ_HEAD head" .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_LAST "CIRCLEQ_HEAD *head" .Fn CIRCLEQ_NEXT "TYPE *elm" "CIRCLEQ_ENTRY NAME" .Fn CIRCLE_PREV "TYPE *elm" "CIRCLEQ_ENTRY NAME" .Fn CIRCLEQ_REMOVE "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME" .Sh 해설 이 매크로는, 단일 링크 리스트, 단일 링크 테일 큐, 리스트, 테일 큐, 순환 큐라고 하는, 5 종류의 데이터 구조를 정의해 거기서 동작합니다. 5 개의 데이터 구조는 모두, 이하의 기능을 서포트합니다. .Bl -enum -compact -offset indent .It 리스트의 선두에 새로운 엔트리를 삽입한다. .It 리스트에 존재하는 임의의 요소의 뒤로 새로운 엔트리를 삽입한다. .It 리스트의 선두로부터 엔트리를 O(1) 삭제한다. .It 리스트의 임의의 엔트리를 O(n) 삭제한다. .It 리스트를 전부터 주사 한다. .El .Pp 단일 링크 리스트는, 5 개의 데이터 구조 중(안)에서 가장 단순해, 위의 5개의 기능해 인가 서포트하지 않습니다. 단일 링크 리스트는, 데이터 세트가 크고, 삭제가 거의 없는, 혹은, 전혀 없는 어플리케이션, 또는 LIFO 큐의 실장에 이상적입니다. .Pp 단일 링크 테일 큐에는 이하의 기능도 있습니다. .Bl -enum -compact -offset indent .It 리스트의 말미에 엔트리를 추가한다. .El 그러나 이하에 주의해 주세요. .Bl -enum -compact -offset indent .It 리스트의 삽입에서는, 리스트의 헤드를 반드시 지정할 필요가 있다. .It 각 헤드 엔트리에서는, 1 개(살)은 아니고 2 개의 포인터가 필요하다. .It 단일 링크 리스트보다, 코드 사이즈는 약 15% 크고, 동작은 약 20% 늦다. .El .Pp 단일 링크 테일 큐는, 데이터 세트가 크고, 삭제가 거의 없는, 혹은, 전혀 없는 어플리케이션, 또는 FIFO 큐의 실장에 이상적입니다. .Pp 이중 링크 타입의 모든 데이터 구조 (리스트, 테일 큐, 순환 큐)에는 이하의 기능도 있습니다. .Bl -enum -compact -offset indent .It 리스트에 존재하는 임의의 요소의 전에 새로운 엔트리를 삽입한다. .It 리스트의 임의의 엔트리를 O(1) 삭제한다. .El 그러나 이하에 주의해 주세요. .Bl -enum -compact -offset indent .It 각 요소에는, 1 개(살)은 아니고 2 개의 포인터가 필요하다. .It 단일 링크 데이터 구조보다, 코드 사이즈와 실행 시간 (삭제는 제외하다)이 약 2 배에 된다. .El .Pp 링크 리스트는, 이중 링크 데이터 구조 중(안)에서 가장 단순해, 단일 링크 리스트의 기능에 가세해 위의 기능 밖에 서포트하지 않습니다. .Pp 테일 큐에는 이하의 기능도 있습니다. .Bl -enum -compact -offset indent .It 리스트의 말미에 엔트리를 추가한다. .It 말미로부터 선두로 반대로 주사 한다. .El 그러나 이하에 주의해 주세요. .Bl -enum -compact -offset indent .It 리스트의 삽입과 삭제에서는, 리스트의 헤드를 반드시 지정할 필요가 있다. .It 각 헤드 엔트리에서는, 1 개(살)은 아니고 2 개의 포인터가 필요하다. .It 단일 링크 리스트보다, 코드 사이즈는 약 15% 크고, 처리 시간은 약 20% 길다. .El .Pp 순환 큐에는 이하의 기능도 있습니다. .Bl -enum -compact -offset indent .It 리스트의 말미에 엔트리를 추가한다. .It 말미로부터 선두로 반대로 주사 한다. .El 그러나 이하에 주의해 주세요. .Bl -enum -compact -offset indent .It 리스트의 삽입과 삭제에서는, 리스트의 헤드를 반드시 지정할 필요가 있다. .It 각 헤드 엔트리에서는, 1 개(살)은 아니고 2 개의 포인터가 필요하다. .It 주사의 종료 조건이 보다 복잡하다. .It 리스트보다, 코드 사이즈는 약 40% 크고, 처리 시간은 약 45% 길다. .El .Pp 매크로 정의에서는, .Fa TYPE (은)는 유저가 정의한 구조체의 이름입니다. 이 구조체에는, .Fa NAME (이)라는 이름이 붙은, .Li SLIST_ENTRY , .Li STAILQ_ENTRY , .Li LIST_ENTRY , .Li TAILQ_ENTRY , .Li CIRCLEQ_ENTRY 그렇다고 하는 형태의 필드를 포함할 필요가 있습니다. 인수 .Fa HEADNAME 하 매크로 .Li SLIST_HEAD , .Li STAILQ_HEAD , .Li LIST_HEAD , .Li TAILQ_HEAD , .Li CIRCLEQ_HEAD 그리고 선언할 필요가 있는, 유저가 정의한 구조체의 이름입니다. 이 매크로의 사용법의 상세한 것에 대하여는, 이하의 사용예를 참조해 주세요. .Sh 단일 링크 리스트 단일 링크 리스트의 최초로는, .Nm SLIST_HEAD 매크로로 정의되는 구조체가 붙습니다. 이 구조체에는, 리스트의 선두의 요소를 가리키는 포인터가 1 개 포함됩니다. 요소는, 임의의 요소의 O(n) 삭제를 희생해, 스페이스와 포인터 조작의 오버헤드가 최소가 되도록(듯이) 단일 링크 됩니다. 새로운 요소는, 기존의 요소의 뒤, 리스트의 선두에서 리스트에 추가할 수 있습니다. .Fa SLIST_HEAD 구조체는 이하와 같이 선언됩니다. .Bd -literal -offset indent SLIST_HEAD(HEADNAME, TYPE) head; .Ed .Pp 여기서 .Fa HEADNAME (은)는 정의하는 구조체의 이름으로, .Fa TYPE (은)는 리스트에 링크 하는 요소의 형태입니다. 리스트의 헤드의 포인터는, 다음에 이하와 같이 선언할 수 있습니다. .Bd -literal -offset indent struct HEADNAME *headp; .Ed .Pp (이름 .Li head (와)과 .Li headp (은)는, 유저가 선택할 수 있습니다. ) .Pp 매크로 .Nm SLIST_HEAD_INITIALIZER (은)는 리스트의 .Fa head (을)를 초기화합니다. .Pp 매크로 .Nm SLIST_EMPTY (은)는 리스트에 요소가 없는 경우에 실로 됩니다. .Pp 매크로 .Nm SLIST_ENTRY (은)는 리스트의 요소를 접속하는 구조체를 선언합니다. .Pp 매크로 .Nm SLIST_FIRST (은)는 리스트의 선두의 요소를, 리스트가 하늘이라면 NULL 를 돌려줍니다. .Pp 매크로 .Nm SLIST_FOREACH 하 .Fa head 그리고 참조되는 리스트를, 각 요소를 순서에 .Fa var 에 할당해 순서 방향으로 주사 합니다. .Pp 매크로 .Nm SLIST_INIT 하 .Fa head 하지만 참조하는 리스트를 초기화합니다. .Pp 매크로 .Nm SLIST_INSERT_HEAD (은)는 새로운 요소 .Fa elm (을)를 리스트의 선두에 삽입합니다. .Pp 매크로 .Nm SLIST_INSERT_AFTER (은)는 요소 .Fa listelm 의 뒤로 새로운 요소 .Fa elm (을)를 삽입합니다. .Pp 매크로 .Nm SLIST_NEXT (은)는 리스트의 다음의 요소를 돌려줍니다. .Pp 매크로 .Nm SLIST_REMOVE_HEAD (은)는 리스트의 선두로부터 요소 .Fa elm (을)를 삭제합니다. 최적인 효율을 얻기 위해서(때문에), 리스트의 선두로부터 요소를 삭제하는 경우에는 일반적인 .Fa SLIST_REMOVE 매크로 대신에 이 매크로를 명시적으로 사용해야 합니다. .Pp 매크로 .Nm SLIST_REMOVE (은)는 리스트로부터 요소 .Fa elm (을)를 삭제합니다. .Sh 단일 링크 리스트의 사용예 .Bd -literal 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); } .Ed .Sh 단일 링크 테일 큐 단일 링크 테일 큐의 최초로는, .Nm STAILQ_HEAD 매크로로 정의되는 구조체가 다합니다. 이 구조체에는 테일 큐의 선두의 요소를 가리키는 포인터와 테일 큐의 말미의 요소를 가리키는 포인터의 2 개가 포함됩니다. 요소는, 임의의 요소의 O(n) 삭제를 희생해, 스페이스와 포인터 조작의 오버헤드가 최소가 되도록(듯이) 단일 링크 됩니다. 새로운 요소는, 기존의 요소의 뒤, 테일 큐의 선두, 테일 큐의 말미로 테일 큐에 추가할 수 있습니다. .Fa STAILQ_HEAD 구조체는 이하와 같이 선언됩니다. .Bd -literal -offset indent STAILQ_HEAD(HEADNAME, TYPE) head; .Ed .Pp 여기서 .Li HEADNAME (은)는 정의하는 구조체의 이름으로, .Li TYPE (은)는 테일 큐에 링크 하는 요소의 형태입니다. 테일 큐의 헤드의 포인터는, 다음에 이하와 같이 선언할 수 있습니다. .Bd -literal -offset indent struct HEADNAME *headp; .Ed .Pp (이름 .Li head (와)과 .Li headp (은)는, 유저가 선택할 수 있습니다. ) .Pp 매크로 .Nm STAILQ_HEAD_INITIALIZER (은)는 테일 큐의 .Fa head (을)를 초기화합니다. .Pp 매크로 .Nm STAILQ_EMPTY (은)는 테일 큐에 요소가 없는 경우에 실로 됩니다. .Pp 매크로 .Nm STAILQ_ENTRY (은)는 테일 큐의 요소를 접속하는 구조체를 선언합니다. .Pp 매크로 .Nm STAILQ_FIRST (은)는 테일 큐의 선두의 요소를, 테일 큐가 하늘이라면 NULL 를 돌려줍니다. .Pp 매크로 .Nm STAILQ_FOREACH 하 .Fa head 그리고 참조되는 테일 큐를, 각 요소를 순서에 .Fa var 에 할당해 순서 방향으로 주사 합니다. .Pp 매크로 .Nm STAILQ_INIT 하 .Fa head 하지만 참조하는 테일 큐를 초기화합니다. .Pp 매크로 .Nm STAILQ_INSERT_HEAD (은)는 새로운 요소 .Fa elm (을)를 테일 큐의 선두에 삽입합니다. .Pp 매크로 .Nm STAILQ_INSERT_TAIL (은)는 새로운 요소 .Fa elm (을)를 테일 큐의 말미에 삽입합니다. .Pp 매크로 .Nm STAILQ_INSERT_AFTER (은)는 새로운 요소 .Fa elm (을)를 요소 .Fa listelm 의 뒤로 삽입합니다. .Pp 매크로 .Nm STAILQ_LAST (은)는 테일 큐의 말미의 요소를 돌려줍니다. 테일 큐가 하늘이라면, 반환값은 미정도리입니다. .Pp 매크로 .Nm STAILQ_NEXT (은)는 테일 큐의 다음의 요소를, 이 요소가 말미라면 NULL 를 돌려줍니다. .Pp 매크로 .Nm STAILQ_REMOVE_HEAD (은)는 테일 큐의 선두로부터 요소 (을)를 삭제합니다. 최적인 효율을 얻기 위해서(때문에), 테일 큐의 선두로부터 요소를 삭제하는 경우에는 일반적인 .Fa STAILQ_REMOVE 매크로보다 이 매크로를 명시적으로 사용해야 합니다. .Pp 매크로 .Nm STAILQ_REMOVE (은)는 테일 큐로부터 요소 .Fa elm (을)를 삭제합니다. .Sh 단일 링크 테일 큐의 사용예 .Bd -literal 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); .Ed .Sh 리스트 리스트의 최초로는, .Nm LIST_HEAD 매크로로 정의되는 구조체가 붙습니다. 이 구조체에는, 리스트의 선두의 요소를 가리키는 포인터가 1 개 포함됩니다. 요소는 이중으로 링크 되고 있으므로, 리스트를 주사 하지 않고 임의의 요소를 삭제할 수 있습니다. 새로운 요소는, 기존의 요소의 전, 기존의 요소의 뒤, 리스트의 선두에서 리스트에 추가할 수 있습니다. .Fa LIST_HEAD 구조체는, 이하와 같이 선언됩니다. .Bd -literal -offset indent LIST_HEAD(HEADNAME, TYPE) head; .Ed .Pp 여기서 .Fa HEADNAME (은)는 정의하는 구조체의 이름으로, .Fa TYPE (은)는 리스트에 링크 하는 요소의 형태입니다. 리스트의 헤드의 포인터는, 다음에 이하와 같이 선언할 수 있습니다. .Bd -literal -offset indent struct HEADNAME *headp; .Ed .Pp (이름 .Li head (와)과 .Li headp (은)는, 유저가 선택할 수 있습니다. ) .Pp 매크로 .Nm LIST_HEAD_INITIALIZER (은)는 리스트의 .Fa head (을)를 초기화합니다. .Pp 매크로 .Nm LIST_EMPTY (은)는 리스트에 요소가 없는 경우에 실로 됩니다. .Pp 매크로 .Nm LIST_ENTRY (은)는 리스트의 요소를 접속하는 구조체를 선언합니다. .Pp 매크로 .Nm LIST_FIRST (은)는 리스트의 최초의 요소를, 리스트가 하늘이라면 NULL 를 돌려줍니다. .Pp 매크로 .Nm LIST_FOREACH 하 .Fa head 그리고 참조되는 리스트를, 각 요소를 순서에 .Fa var 에 할당해 순서 방향으로 주사 합니다. .Pp 매크로 .Nm LIST_INIT 하 .Fa head 하지만 참조하는 리스트를 초기화합니다. .Pp 매크로 .Nm LIST_INSERT_HEAD (은)는 새로운 요소 .Fa elm (을)를 리스트의 선두에 삽입합니다. .Pp 매크로 .Nm LIST_INSERT_AFTER (은)는 새로운 요소 .Fa elm (을)를 요소 .Fa listelm 의 뒤로 삽입합니다. .Pp 매크로 .Nm LIST_INSERT_BEFORE (은)는 새로운 요소 .Fa elm (을)를 요소 .Fa listelm 의 전에 삽입합니다. .Pp 매크로 .Nm LIST_NEXT (은)는 리스트의 다음의 요소를, 이 요소가 말미라면 NULL 를 돌려줍니다. .Pp 매크로 .Nm LIST_REMOVE (은)는 요소 .Fa elm (을)를 리스트로부터 삭제합니다. .Sh 리스트의 사용예 .Bd -literal 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); .Ed .Sh 테일 큐 테일 큐의 최초로는, .Nm TAILQ_HEAD 매크로로 정의되는 구조체가 붙습니다. 이 구조체에는, 테일 큐의 최초의 요소를 가리키는 포인터와 테일 큐의 선두의 요소를 가리키는 포인터의 2 개가 포함됩니다. 요소는 이중으로 링크 되고 있으므로, 테일 큐를 주사 하지 않고 임의의 요소를 삭제할 수 있습니다. 새로운 요소는, 기존의 요소의 전, 기존의 요소의 뒤, 테일 큐의 선두, 테일 큐의 말미로 테일 큐에 추가할 수 있습니다. .Fa TAILQ_HEAD 구조체는, 이하와 같이 선언되고 있습니다. .Bd -literal -offset indent TAILQ_HEAD(HEADNAME, TYPE) head; .Ed .Pp 여기서 .Li HEADNAME (은)는 정의하는 구조체의 이름으로, .Li TYPE (은)는 테일 큐에 링크 하는 요소의 형태입니다. 테일 큐의 헤드의 포인터는, 다음에 이하와 같이 선언됩니다. .Bd -literal -offset indent struct HEADNAME *headp; .Ed .Pp (이름 .Li head (와)과 .Li headp (은)는, 유저가 선택할 수 있습니다. ) .Pp 매크로 .Nm TAILQ_HEAD_INITIALIZER (은)는 테일 큐의 .Fa head (을)를 초기화합니다. .Pp 매크로 .Nm TAILQ_EMPTY (은)는 테일 큐에 요소가 없는 경우에 실로 됩니다. .Pp 매크로 .Nm TAILQ_ENTRY (은)는 테일 큐의 요소를 접속하는 구조체를 선언합니다. .Pp 매크로 .Nm TAILQ_FIRST (은)는 테일 큐의 최초의 요소를, 테일 큐가 하늘이라면 NULL 를 돌려줍니다. .Pp 매크로 .Nm TAILQ_FOREACH 하 .Fa head 그리고 참조되는 테일 큐를, 각 요소를 순서에 .Fa var 에 할당해 순서 방향으로 주사 합니다. .Pp 매크로 .Nm TAILQ_FOREACH_REVERSE 하 .Fa head 그리고 참조되는 테일 큐를, 각 요소를 순서에 .Fa var 에 할당해 역방향으로 주사 합니다. .Pp 매크로 .Nm TAILQ_INIT 하 .Fa head 하지만 참조하는 테일 큐를 초기화합니다. .Pp 매크로 .Nm TAILQ_INSERT_HEAD (은)는 새로운 요소 .Fa elm (을)를 테일 큐의 선두에 삽입합니다. .Pp 매크로 .Nm TAILQ_INSERT_TAIL (은)는 새로운 요소 .Fa elm (을)를 테일 큐의 말미에 삽입합니다. .Pp 매크로 .Nm TAILQ_INSERT_AFTER (은)는 새로운 요소 .Fa elm (을)를 요소 .Fa listelm 의 뒤로 삽입합니다. .Pp 매크로 .Nm TAILQ_INSERT_BEFORE (은)는 새로운 요소 .Fa elm (을)를 요소 .Fa listelm 의 전에 삽입합니다. .Pp 매크로 .Nm TAILQ_LAST (은)는 테일 큐의 말미의 요소를 돌려줍니다. 테일 큐가 하늘의 경우, 반환값은 미정도리입니다. .Pp 매크로 .Nm TAILQ_NEXT (은)는 테일 큐의 다음의 요소를, 그 요소가 말미의 경우는 NULL 를 돌려줍니다. .Pp 매크로 .Nm TAILQ_PREV (은)는 테일 큐의 전의 요소를, 그 요소가 선두의 경우는 NULL 를 돌려줍니다. .Pp 매크로 .Nm TAILQ_REMOVE (은)는 요소 .Fa elm (을)를 테일 큐로부터 삭제합니다. .Sh 테일 큐의 사용예 .Bd -literal 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); .Ed .Sh 순환 큐 순환 큐의 최초로는, .Nm CIRCLEQ_HEAD 매크로로 정의되는 구조체가 붙습니다. 이 구조체에는, 순환 큐의 선두의 요소를 가리키는 포인터와 순환 큐의 말미의 요소를 가리키는 포인터의 2 개가 포함됩니다. 요소는 이중으로 링크 되고 있으므로, 큐를 주사 하지 않고 임의의 요소를 삭제할 수 있습니다. 새로운 요소는, 기존의 요소의 전, 기존의 요소의 뒤, 순환 큐의 선두, 순환 큐의 말미로 순환 큐에 추가할 수 있습니다. .Fa CIRCLEQ_HEAD 구조체는 이하와 같이 선언됩니다. .Bd -literal -offset indent CIRCLEQ_HEAD(HEADNAME, TYPE) head; .Ed .Pp 여기서 .Li HEADNAME (은)는 정의하는 구조체의 이름으로, .Li TYPE (은)는 순환 큐에 링크 하는 요소의 형태입니다. 순환 큐의 헤드의 포인터는, 다음에 이하와 같이 선언할 수 있습니다. .Bd -literal -offset indent struct HEADNAME *headp; .Ed .Pp (이름 .Li head (와)과 .Li headp (은)는, 유저가 선택할 수 있습니다. ) .Pp 매크로 .Nm CIRCLEQ_HEAD_INITIALIZER (은)는 순환 큐의 .Fa head (을)를 초기화합니다. .Pp 매크로 .Nm CIRCLEQ_EMPTY (은)는 순환 큐에 요소가 없는 경우에 실로 됩니다. .Pp 매크로 .Nm CIRCLEQ_ENTRY (은)는 순환 큐의 요소를 접속하는 구조체를 선언합니다. .Pp 매크로 .Nm CIRCLEQ_FIRST (은)는 순환 큐의 선두의 요소를 돌려줍니다. .Pp 매크로 .Nm CICRLEQ_FOREACH 하 .Fa head 그리고 참조되는 순환 큐를, 각 요소를 순서에 .Fa var 에 할당해 순서 방향으로 주사 합니다. .Pp 매크로 .Nm CICRLEQ_FOREACH_REVERSE 하 .Fa head 그리고 참조되는 순환 큐를, 각 요소를 순서에 .Fa var 에 할당해 역방향으로 주사 합니다. .Pp 매크로 .Nm CIRCLEQ_INIT 하 .Fa head 하지만 참조하는 순환 큐를 초기화합니다. .Pp 매크로 .Nm CIRCLEQ_INSERT_HEAD (은)는 새로운 요소 .Fa elm (을)를 순환 큐의 선두에 삽입합니다. .Pp 매크로 .Nm CIRCLEQ_INSERT_TAIL (은)는 새로운 요소 .Fa elm (을)를 순환 큐의 말미에 삽입합니다. .Pp 매크로 .Nm CIRCLEQ_INSERT_AFTER (은)는 새로운 요소 .Fa elm (을)를 요소 .Fa listelm 의 뒤로 삽입합니다. .Pp 매크로 .Nm CIRCLEQ_INSERT_BEFORE (은)는 새로운 요소 .Fa elm (을)를 요소 .Fa listelm 의 전에 삽입합니다. .Pp 매크로 .Nm CIRCLEQ_LAST (은)는 순환 큐의 말미의 요소를 돌려줍니다. .Pp 매크로 .Nm CIRCLEQ_NEXT (은)는 순환 큐의 다음의 요소를 돌려줍니다. .Pp 매크로 .Nm CIRCLEQ_PREV (은)는 순환 큐의 전의 요소를 돌려줍니다. .Pp 매크로 .Nm CIRCLEQ_REMOVE (은)는 요소 .Fa elm (을)를 순환 큐로부터 삭제합니다. .Sh 순환 큐의 사용예 .Bd -literal 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); .Ed .Sh 역사 .Nm queue 함수는 .Bx 4.4 그리고 처음 등장했습니다.