.\" 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
.\"
.\" hch, 2002-03-25
.\"
.\" Traducido por Miguel Pérez Ibars <mpi79470@alu.um.es> el 9-agosto-2004
.\"
.Dd 24 enero, 1994
.Dt QUEUE 3
.Os BSD 4
.Sh NOMBRE
.Nm LIST_ENTRY ,
.Nm LIST_HEAD ,
.Nm LIST_INIT ,
.Nm LIST_INSERT_AFTER ,
.Nm LIST_INSERT_HEAD ,
.Nm LIST_REMOVE ,
.Nm TAILQ_ENTRY ,
.Nm TAILQ_HEAD ,
.Nm TAILQ_INIT ,
.Nm TAILQ_INSERT_AFTER ,
.Nm TAILQ_INSERT_HEAD ,
.Nm TAILQ_INSERT_TAIL ,
.Nm TAILQ_REMOVE ,
.Nm CIRCLEQ_ENTRY ,
.Nm CIRCLEQ_HEAD ,
.Nm CIRCLEQ_INIT ,
.Nm CIRCLEQ_INSERT_AFTER ,
.Nm CIRCLEQ_INSERT_BEFORE ,
.Nm CIRCLEQ_INSERT_HEAD ,
.Nm CIRCLEQ_INSERT_TAIL ,
.Nm CIRCLEQ_REMOVE
.Nd implementación de listas, colas, y colas circulares
.Sh SINOPSIS
.Fd #include <sys/queue.h>
.\"
.Fn LIST_ENTRY "TYPE"
.Fn LIST_HEAD "HEADNAME" "TYPE"
.Fn LIST_INIT "LIST_HEAD *head"
.Fn LIST_INSERT_AFTER "LIST_ENTRY *listelm" "TYPE *elm" "LIST_ENTRY NAME"
.Fn LIST_INSERT_HEAD "LIST_HEAD *head" "TYPE *elm" "LIST_ENTRY NAME"
.Fn LIST_REMOVE "TYPE *elm" "LIST_ENTRY NAME"
.\"
.Fn TAILQ_ENTRY "TYPE"
.Fn TAILQ_HEAD "HEADNAME" "TYPE"
.Fn TAILQ_INIT "TAILQ_HEAD *head"
.Fn TAILQ_INSERT_AFTER "TAILQ_HEAD *head" "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_REMOVE "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
.\"
.Fn CIRCLEQ_ENTRY "TYPE"
.Fn CIRCLEQ_HEAD "HEADNAME" "TYPE"
.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_REMOVE "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
.Sh DESCRIPCIÓN
Estas macros definen y operan sobre tres tipos de estructuras de datos:
listas, colas, y colas circulares.
Las tres estructuras soportan la siguiente funcionalidad:
.Bl -enum -compact -offset indent
.It
Inserción de una nueva entrada en la cabeza de la lista.
.It
Inserción de una nueva entrada después de cualquier elemento de la lista.
.It
Eliminación de cualquier entrada en la lista.
.It
Recorrido hacia delante de la lista.
.El
.Pp
Las listas son las más simples de las tres estructuras de datos y
soportan sólo la funcionalidad descrita arriba.
.Pp
Las colas añaden la siguiente funcionalidad:
.Bl -enum -compact -offset indent
.It
Las entradas pueden ser añadidas al final de una lista.
.El
Sin embargo:
.Bl -enum -compact -offset indent
.It
Todas las inserciones y eliminaciones en la lista deben especificar
la cabeza de la lista.
.It
Cada entrada de cabecera requiere dos punteros en lugar de uno.
.It
El tamaño del código es aproximadamente un 15% más grande y las
operaciones se ejecutan sobre un 20% más lentas que en las listas.
.El
.Pp
Las colas circulares añaden la siguiente funcionalidad:
.Bl -enum -compact -offset indent
.It
Las entradas pueden ser añadidas al final de una lista.
.It
Las entradas pueden ser añadidas antes de cualquier entrada.
.It
Pueden ser recorridas hacia atrás, desde la cola hasta la cabeza.
.El
Sin embargo:
.Bl -enum -compact -offset indent
.It
Todas las inserciones y eliminaciones en la lista deben especificar
la cabeza de la lista.
.It
Cada entrada de cabecera requiere dos punteros en lugar de uno.
.It
La condición de terminación para el recorrido es más compleja.
.It
El tamaño del código es aproximadamente un 40% más grande y las
operaciones se ejecutan sobre un 45% más lentas que en las listas.
.El
.Pp
En las definiciones de las macros,
.Fa TYPE
es el nombre de una estructura definida por el usuario,
que debe contener un campo de tipo
.Li LIST_ENTRY ,
.Li TAILQ_ENTRY ,
o
.Li CIRCLEQ_ENTRY ,
con nombre
.Fa NAME .
El argumento
.Fa HEADNAME
es el nombre de una estructura definida por el usuario que debe
ser declarada usando las macros
.Li LIST_HEAD ,
.Li TAILQ_HEAD ,
o
.Li CIRCLEQ_HEAD .
Vea los ejemplos más abajo para una explicación más detallada sobre
cómo se usan estas macros.
.Sh LISTAS
Una lista es encabezada por una estructura definida por la macro
.Nm LIST_HEAD.
Esta estructura contiene un sólo puntero al primer elemento de la lista.
Los elementos están doblemente enlazados por lo que puede eliminarse
un elemento arbitrario sin recorrer la lista.
Nuevos elementos pueden ser añadidos a la lista después de un elemento
existente o en la cabeza de la lista.
Una estructura
.Fa LIST_HEAD
es declarada como sigue:
.Bd -literal -offset indent
LIST_HEAD(HEADNAME, TYPE) head;
.Ed
.Pp
donde
.Fa HEADNAME
es el nombre de la estructura a ser definida, y
.Fa TYPE
es el tipo de elementos que serán enlazados en la lista.
Un puntero a la cabeza de la lista puede ser declarado después como:
.Bd -literal -offset indent
struct HEADNAME *headp;
.Ed
.Pp
(Los nombres
.Li head
y
.Li headp
son seleccionables por el usuario.)
.Pp
La macro
.Nm LIST_ENTRY
declara una estructura que conecta los elementos en 
la lista.
.Pp
La macro
.Nm LIST_INIT
inicializa la lista referenciada por
.Fa head .
.Pp
La macro
.Nm LIST_INSERT_HEAD
inserta el nuevo elemento
.Fa elm
en la cabeza de la lista.
.Pp
La macro
.Nm LIST_INSERT_AFTER
inserta el nuevo elemento
.Fa elm
después del elemento
.Fa listelm .
.Pp
La macro
.Nm LIST_REMOVE
elimina el elemento
.Fa elm
de la lista.
.Sh EJEMPLO DE LISTA
.Bd -literal
LIST_HEAD(listhead, entry) head;
struct listhead *headp;		/* Cabeza de la lista. */
struct entry {
	...
	LIST_ENTRY(entry) entries;	/* Lista. */
	...
} *n1, *n2, *np;

LIST_INIT(&head);			/* Inicializa la lista. */

n1 = malloc(sizeof(struct entry));	/* Inserta en la cabeza. */
LIST_INSERT_HEAD(&head, n1, entries);

n2 = malloc(sizeof(struct entry));	/* Inserta después. */
LIST_INSERT_AFTER(n1, n2, entries);
					/* Recorrido hacia delante. */
for (np = head.lh_first; np != NULL; np = np->entries.le_next)
	np-> ...

while (head.lh_first != NULL)		/* Eliminar. */
	LIST_REMOVE(head.lh_first, entries);
.Ed
.Sh COLAS
Una cola es encabezada por una estructura definida por la
macro
.Nm TAILQ_HEAD.
Esta estructura contiene un par de punteros,
uno al primer elemento en la cola y el otro al
último elemento en la cola.
Los elementos están doblemente enlazadas por lo que puede eliminarse
un elemento arbitrario sin recorrer la cola.
Nuevos elementos pueden añadirse a la cola después de un elemento existente,
en la cabeza de la cola, o en el final de la cola.
Una estructura
.Fa TAILQ_HEAD
se declara como sigue:
.Bd -literal -offset indent
TAILQ_HEAD(HEADNAME, TYPE) head;
.Ed
.Pp
donde
.Li HEADNAME
es el nombre de la estructura a ser definida, y
.Li TYPE
es el tipo de los elementos que serán enlazados en la cola.
Un puntero a la cabeza de la cola puede ser declarado después como:
.Bd -literal -offset indent
struct HEADNAME *headp;
.Ed
.Pp
(Los nombres
.Li head
y
.Li headp
son seleccionables por el usuario.)
.Pp
La macro
.Nm TAILQ_ENTRY
declara una estructura que conecta los elementos en la cola.
.Pp
La macro
.Nm TAILQ_INIT
inicializa la cola referenciada por
.Fa head .
.Pp
La macro
.Nm TAILQ_INSERT_HEAD
inserta el nuevo elemento
.Fa elm
en la cabeza de la cola.
.Pp
La macro
.Nm TAILQ_INSERT_TAIL
inserta el nuevo elemento
.Fa elm
en el final de la cola.
.Pp
La macro
.Nm TAILQ_INSERT_AFTER
inserta el nuevo elemento
.Fa elm
después del elemento
.Fa listelm .
.Pp
La macro
.Nm TAILQ_REMOVE
elimina el elemento
.Fa elm
de la cola.
.Sh EJEMPLO DE COLA
.Bd -literal
TAILQ_HEAD(tailhead, entry) head;
struct tailhead *headp;		/* Cabeza de la cola. */
struct entry {
	...
	TAILQ_ENTRY(entry) entries;	/* Cola. */
	...
} *n1, *n2, *np;

TAILQ_INIT(&head);			/* Inicializa la cola. */

n1 = malloc(sizeof(struct entry));	/* Inserta en la cabeza. */
TAILQ_INSERT_HEAD(&head, n1, entries);

n1 = malloc(sizeof(struct entry));	/* Inserta en el final. */
TAILQ_INSERT_TAIL(&head, n1, entries);

n2 = malloc(sizeof(struct entry));	/* Inserta después. */
TAILQ_INSERT_AFTER(&head, n1, n2, entries);
					/* Recorrido hacia delante. */
for (np = head.tqh_first; np != NULL; np = np->entries.tqe_next)
	np-> ...
					/* Elimina. */
while (head.tqh_first != NULL)
	TAILQ_REMOVE(&head, head.tqh_first, entries);
.Ed
.Sh COLAS CIRCULARES
Una cola circular es encabezada por una estructura definida por
la macro
.Nm CIRCLEQ_HEAD.
Esta estructura contiene un par de punteros,
uno al primer elemento en la cola circular y el otro al
último elemento en la cola circular.
Los elementos están doblemente enlazadas por lo que puede eliminarse
un elemento arbitrario sin recorrer la cola.
Nuevos elementos pueden añadirse a la cola después de un elemento existente,
antes de un elemento existente, en la cabeza de la cola, o en el final de la cola.
Una estructura
.Fa CIRCLEQ_HEAD
se declara como sigue:
.Bd -literal -offset indent
CIRCLEQ_HEAD(HEADNAME, TYPE) head;
.Ed
.Pp
donde
.Li HEADNAME
es el nombre de la estructura a ser definida, y
.Li TYPE
es el tipo de los elementos que serán enlazados en la cola circular.
Un puntero a la cabeza de la cola circular puede ser declarado después como:
.Bd -literal -offset indent
struct HEADNAME *headp;
.Ed
.Pp
(Los nombres
.Li head
y
.Li headp
son seleccionables por el usuario.)
.Pp
La macro
.Nm CIRCLEQ_ENTRY
declara una estructura que conecta los elementos en la
cola circular.
.Pp
La macro
.Nm CIRCLEQ_INIT
inicializa la cola circular referenciada por
.Fa head .
.Pp
La macro
.Nm CIRCLEQ_INSERT_HEAD
inserta el nuevo elemento
.Fa elm
en la cabeza de la cola circular.
.Pp
La macro
.Nm CIRCLEQ_INSERT_TAIL
inserta el nuevo elemento
.Fa elm
en el final de la cola circular.
.Pp
La macro
.Nm CIRCLEQ_INSERT_AFTER
inserta el nuevo elemento
.Fa elm
después del elemento
.Fa listelm .
.Pp
La macro
.Nm CIRCLEQ_INSERT_BEFORE
inserta el nuevo elemento
.Fa elm
antes del elemento
.Fa listelm .
.Pp
La macro
.Nm CIRCLEQ_REMOVE
elimina el elemento
.Fa elm
de la cola circular.
.Sh EJEMPLO DE COLA CIRCULAR
.Bd -literal
CIRCLEQ_HEAD(circleq, entry) head;
struct circleq *headp;			/* Cabeza de la cola circular. */
struct entry {
	...
	CIRCLEQ_ENTRY(entry) entries;		/* Cola circular. */
	...
} *n1, *n2, *np;

CIRCLEQ_INIT(&head);			/* Inicializa la cola circular. */

n1 = malloc(sizeof(struct entry));	/* Inserta en la cabeza. */
CIRCLEQ_INSERT_HEAD(&head, n1, entries);

n1 = malloc(sizeof(struct entry));	/* Inserta en la cola. */
CIRCLEQ_INSERT_TAIL(&head, n1, entries);

n2 = malloc(sizeof(struct entry));	/* Inserta después. */
CIRCLEQ_INSERT_AFTER(&head, n1, n2, entries);

n2 = malloc(sizeof(struct entry));	/* Inserta antes. */
CIRCLEQ_INSERT_BEFORE(&head, n1, n2, entries);
					/* Recorrido hacia delante. */
for (np = head.cqh_first; np != (void *)&head; np = np->entries.cqe_next)
	np-> ...
					/* Recorrido hacia atrás. */
for (np = head.cqh_last; np != (void *)&head; np = np->entries.cqe_prev)
	np-> ...
					/* Elimina. */
while (head.cqh_first != (void *)&head)
	CIRCLEQ_REMOVE(&head, head.cqh_first, entries);
.Ed
.Sh HISTORIA
Las funciones
.Nm queue
aparecieron por primera vez en
.Bx 4.4 .