queue

Autres langues

Langue: es

Autres versions - même langue

Version: 123948 (mandriva - 01/05/08)

Section: 3 (Bibliothèques de fonctions)

Sommaire


BSD mandoc
BSD 4

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 - implementación de listas, colas, y colas circulares

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

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:
  1. Inserción de una nueva entrada en la cabeza de la lista.
  2. Inserción de una nueva entrada después de cualquier elemento de la lista.
  3. Eliminación de cualquier entrada en la lista.
  4. 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:

  1. Las entradas pueden ser añadidas al final de una lista.

Sin embargo:

  1. Todas las inserciones y eliminaciones en la lista deben especificar la cabeza de la lista.
  2. Cada entrada de cabecera requiere dos punteros en lugar de uno.
  3. 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:

  1. Las entradas pueden ser añadidas al final de una lista.
  2. Las entradas pueden ser añadidas antes de cualquier entrada.
  3. Pueden ser recorridas hacia atrás, desde la cola hasta la cabeza.

Sin embargo:

  1. Todas las inserciones y eliminaciones en la lista deben especificar la cabeza de la lista.
  2. Cada entrada de cabecera requiere dos punteros en lugar de uno.
  3. La condición de terminación para el recorrido es más compleja.
  4. 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, Fa 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 Fa NAME . El argumento Fa 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 macro 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: 
 LIST_HEAD(HEADNAME, TYPE) head;

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:

 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 Fa head .

La macro LIST_INSERT_HEAD inserta el nuevo elemento Fa elm en la cabeza de la lista.

La macro LIST_INSERT_AFTER inserta el nuevo elemento Fa elm después del elemento Fa listelm .

La macro LIST_REMOVE elimina el elemento Fa 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 macro 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: 
 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 Fa head .

La macro TAILQ_INSERT_HEAD inserta el nuevo elemento Fa elm en la cabeza de la cola.

La macro TAILQ_INSERT_TAIL inserta el nuevo elemento Fa elm en el final de la cola.

La macro TAILQ_INSERT_AFTER inserta el nuevo elemento Fa elm después del elemento Fa listelm .

La macro TAILQ_REMOVE elimina el elemento Fa 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 macro 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: 
 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 Fa head .

La macro CIRCLEQ_INSERT_HEAD inserta el nuevo elemento Fa elm en la cabeza de la cola circular.

La macro CIRCLEQ_INSERT_TAIL inserta el nuevo elemento Fa elm en el final de la cola circular.

La macro CIRCLEQ_INSERT_AFTER inserta el nuevo elemento Fa elm después del elemento Fa listelm .

La macro CIRCLEQ_INSERT_BEFORE inserta el nuevo elemento Fa elm antes del elemento Fa listelm .

La macro CIRCLEQ_REMOVE elimina el elemento Fa 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 funciones queue aparecieron por primera vez en BSD 4.4