| queue.3 (70515) | queue.3 (74270) |
|---|---|
| 1.\" Copyright (c) 1993 2.\" The Regents of the University of California. All rights reserved. 3.\" 4.\" Redistribution and use in source and binary forms, with or without 5.\" modification, are permitted provided that the following conditions 6.\" are met: 7.\" 1. Redistributions of source code must retain the above copyright 8.\" notice, this list of conditions and the following disclaimer. --- 16 unchanged lines hidden (view full) --- 25.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 26.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 27.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 28.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 29.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 30.\" SUCH DAMAGE. 31.\" 32.\" @(#)queue.3 8.2 (Berkeley) 1/24/94 | 1.\" Copyright (c) 1993 2.\" The Regents of the University of California. All rights reserved. 3.\" 4.\" Redistribution and use in source and binary forms, with or without 5.\" modification, are permitted provided that the following conditions 6.\" are met: 7.\" 1. Redistributions of source code must retain the above copyright 8.\" notice, this list of conditions and the following disclaimer. --- 16 unchanged lines hidden (view full) --- 25.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 26.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 27.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 28.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 29.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 30.\" SUCH DAMAGE. 31.\" 32.\" @(#)queue.3 8.2 (Berkeley) 1/24/94 |
| 33.\" $FreeBSD: head/share/man/man3/queue.3 70515 2000-12-30 18:58:15Z ben $ | 33.\" $FreeBSD: head/share/man/man3/queue.3 74270 2001-03-15 02:08:44Z dd $ |
| 34.\" 35.Dd January 24, 1994 36.Dt QUEUE 3 37.Os BSD 4 38.Sh NAME 39.Nm SLIST_EMPTY , 40.Nm SLIST_ENTRY , 41.Nm SLIST_FIRST , --- 107 unchanged lines hidden (view full) --- 149.Fn TAILQ_INSERT_HEAD "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME" 150.Fn TAILQ_INSERT_TAIL "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME" 151.Fn TAILQ_LAST "TAILQ_HEAD *head" "HEADNAME" 152.Fn TAILQ_NEXT "TYPE *elm" "TAILQ_ENTRY NAME" 153.Fn TAILQ_PREV "TYPE *elm" "HEADNAME" "TAILQ_ENTRY NAME" 154.Fn TAILQ_REMOVE "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME" 155.\" 156.Sh DESCRIPTION | 34.\" 35.Dd January 24, 1994 36.Dt QUEUE 3 37.Os BSD 4 38.Sh NAME 39.Nm SLIST_EMPTY , 40.Nm SLIST_ENTRY , 41.Nm SLIST_FIRST , --- 107 unchanged lines hidden (view full) --- 149.Fn TAILQ_INSERT_HEAD "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME" 150.Fn TAILQ_INSERT_TAIL "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME" 151.Fn TAILQ_LAST "TAILQ_HEAD *head" "HEADNAME" 152.Fn TAILQ_NEXT "TYPE *elm" "TAILQ_ENTRY NAME" 153.Fn TAILQ_PREV "TYPE *elm" "HEADNAME" "TAILQ_ENTRY NAME" 154.Fn TAILQ_REMOVE "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME" 155.\" 156.Sh DESCRIPTION |
| 157These macros define and operate on five types of data structures: 158singly-linked lists, singly-linked tail queues, lists, tail queues, 159and circular queues. 160All five structures support the following functionality: | 157These macros define and operate on four types of data structures: 158singly-linked lists, singly-linked tail queues, lists, and tail queues. 159All four structures support the following functionality: |
| 161.Bl -enum -compact -offset indent 162.It 163Insertion of a new entry at the head of the list. 164.It 165Insertion of a new entry after any element in the list. 166.It 167O(1) removal of an entry from the head of the list. 168.It --- 23 unchanged lines hidden (view full) --- 192Code size is about 15% greater and operations run about 20% slower 193than singly-linked lists. 194.El 195.Pp 196Singly-linked tailqs are ideal for applications with large datasets and 197few or no removals, 198or for implementing a FIFO queue. 199.Pp | 160.Bl -enum -compact -offset indent 161.It 162Insertion of a new entry at the head of the list. 163.It 164Insertion of a new entry after any element in the list. 165.It 166O(1) removal of an entry from the head of the list. 167.It --- 23 unchanged lines hidden (view full) --- 191Code size is about 15% greater and operations run about 20% slower 192than singly-linked lists. 193.El 194.Pp 195Singly-linked tailqs are ideal for applications with large datasets and 196few or no removals, 197or for implementing a FIFO queue. 198.Pp |
| 200All doubly linked types of data structures (lists, tail queues, and circle 201queues) additionally allow: | 199All doubly linked types of data structures (lists and tail queues) 200additionally allow: |
| 202.Bl -enum -compact -offset indent 203.It 204Insertion of a new entry before any element in the list. 205.It 206O(1) removal of any entry in the list. 207.El 208However: 209.Bl -enum -compact -offset indent --- 643 unchanged lines hidden --- | 201.Bl -enum -compact -offset indent 202.It 203Insertion of a new entry before any element in the list. 204.It 205O(1) removal of any entry in the list. 206.El 207However: 208.Bl -enum -compact -offset indent --- 643 unchanged lines hidden --- |