QUEUE(3) | Library Functions Manual | QUEUE(3) |
NOMBRE¶
LIST_ENTRY
, LIST_HEAD
,
LIST_INIT
, LIST_INSERT_AFTER
,
LIST_INSERT_HEAD
, LIST_REMOVE
,
TAILQ_ENTRY
, TAILQ_HEAD
,
TAILQ_INIT
,
TAILQ_INSERT_AFTER
,
TAILQ_INSERT_HEAD
,
TAILQ_INSERT_TAIL
,
TAILQ_REMOVE
, CIRCLEQ_ENTRY
,
CIRCLEQ_HEAD
, CIRCLEQ_INIT
,
CIRCLEQ_INSERT_AFTER
,
CIRCLEQ_INSERT_BEFORE
,
CIRCLEQ_INSERT_HEAD
,
CIRCLEQ_INSERT_TAIL
,
CIRCLEQ_REMOVE
—
SINOPSIS¶
#include <sys/queue.h>
LIST_ENTRY
(TYPE)
LIST_HEAD
(HEADNAME,
TYPE)
LIST_INIT
(LIST_HEAD *head)
LIST_INSERT_AFTER
(LIST_ENTRY
*listelm, TYPE *elm, LIST_ENTRY
NAME) LIST_INSERT_HEAD
(LIST_HEAD
*head, TYPE *elm, LIST_ENTRY
NAME) LIST_REMOVE
(TYPE
*elm, LIST_ENTRY NAME)
TAILQ_ENTRY
(TYPE)
TAILQ_HEAD
(HEADNAME,
TYPE)
TAILQ_INIT
(TAILQ_HEAD *head)
TAILQ_INSERT_AFTER
(TAILQ_HEAD
*head, 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_REMOVE
(TAILQ_HEAD
*head, TYPE *elm, TAILQ_ENTRY
NAME) CIRCLEQ_ENTRY
(TYPE)
CIRCLEQ_HEAD
(HEADNAME,
TYPE)
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_REMOVE
(CIRCLEQ_HEAD
*head, TYPE *elm, CIRCLEQ_ENTRY
NAME)
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:- Inserción de una nueva entrada en la cabeza de la lista.
- Inserción de una nueva entrada después de cualquier elemento de la lista.
- Eliminación de cualquier entrada en la lista.
- Recorrido hacia delante de la lista.
Las listas son las más simples de las tres estructuras de datos y soportan sólo la funcionalidad descrita arriba.
Las colas añaden la siguiente funcionalidad:
- Las entradas pueden ser añadidas al final de una lista.
- Todas las inserciones y eliminaciones en la lista deben especificar la cabeza de la lista.
- Cada entrada de cabecera requiere dos punteros en lugar de uno.
- 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.
Las colas circulares añaden la siguiente funcionalidad:
- Las entradas pueden ser añadidas al final de una lista.
- Las entradas pueden ser añadidas antes de cualquier entrada.
- Pueden ser recorridas hacia atrás, desde la cola hasta la cabeza.
- Todas las inserciones y eliminaciones en la lista deben especificar la cabeza de la lista.
- Cada entrada de cabecera requiere dos punteros en lugar de uno.
- La condición de terminación para el recorrido es más compleja.
- 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.
En las definiciones de las macros, TYPE es
el nombre de una estructura definida por el usuario, que debe contener un
campo de tipo LIST_ENTRY
,
TAILQ_ENTRY
, o
CIRCLEQ_ENTRY
, con nombre
NAME. El argumento HEADNAME es
el nombre de una estructura definida por el usuario que debe ser declarada
usando las macros LIST_HEAD
,
TAILQ_HEAD
, o CIRCLEQ_HEAD
.
Vea los ejemplos más abajo para una explicación más
detallada sobre cómo se usan estas macros.
LISTAS¶
Una lista es encabezada por una estructura definida por la macroLIST_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
LIST_HEAD es declarada como sigue:
LIST_HEAD(HEADNAME, TYPE) head;
donde HEADNAME es el nombre de la estructura a ser definida, y 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:
struct HEADNAME *headp;
(Los nombres head
y
headp
son seleccionables por el usuario.)
La macro LIST_ENTRY
declara una estructura
que conecta los elementos en la lista.
La macro LIST_INIT
inicializa la lista
referenciada por head.
La macro LIST_INSERT_HEAD
inserta el nuevo
elemento elm en la cabeza de la lista.
La macro LIST_INSERT_AFTER
inserta el
nuevo elemento elm después del elemento
listelm.
La macro LIST_REMOVE
elimina el elemento
elm de la lista.
EJEMPLO DE LISTA¶
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);
COLAS¶
Una cola es encabezada por una estructura definida por la macroTAILQ_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
TAILQ_HEAD se declara como sigue:
TAILQ_HEAD(HEADNAME, TYPE) head;
donde HEADNAME
es el nombre de la
estructura a ser definida, y 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:
struct HEADNAME *headp;
(Los nombres head
y
headp
son seleccionables por el usuario.)
La macro TAILQ_ENTRY
declara una
estructura que conecta los elementos en la cola.
La macro TAILQ_INIT
inicializa la cola
referenciada por head.
La macro TAILQ_INSERT_HEAD
inserta el
nuevo elemento elm en la cabeza de la cola.
La macro TAILQ_INSERT_TAIL
inserta el
nuevo elemento elm en el final de la cola.
La macro TAILQ_INSERT_AFTER
inserta el
nuevo elemento elm después del elemento
listelm.
La macro TAILQ_REMOVE
elimina el elemento
elm de la cola.
EJEMPLO DE COLA¶
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);
COLAS CIRCULARES¶
Una cola circular es encabezada por una estructura definida por la macroCIRCLEQ_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
CIRCLEQ_HEAD se declara como sigue:
CIRCLEQ_HEAD(HEADNAME, TYPE) head;
donde HEADNAME
es el nombre de la
estructura a ser definida, y 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:
struct HEADNAME *headp;
(Los nombres head
y
headp
son seleccionables por el usuario.)
La macro CIRCLEQ_ENTRY
declara una
estructura que conecta los elementos en la cola circular.
La macro CIRCLEQ_INIT
inicializa la cola
circular referenciada por head.
La macro CIRCLEQ_INSERT_HEAD
inserta el
nuevo elemento elm en la cabeza de la cola
circular.
La macro CIRCLEQ_INSERT_TAIL
inserta el
nuevo elemento elm en el final de la cola
circular.
La macro CIRCLEQ_INSERT_AFTER
inserta el
nuevo elemento elm después del elemento
listelm.
La macro CIRCLEQ_INSERT_BEFORE
inserta el
nuevo elemento elm antes del elemento
listelm.
La macro CIRCLEQ_REMOVE
elimina el
elemento elm de la cola circular.
EJEMPLO DE COLA CIRCULAR¶
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);
HISTORIA¶
Las funcionesqueue
aparecieron por primera vez en
4.4BSD.
24 enero, 1994 | BSD 4 |