Listas vinculadas de forma y doble

  • Artículo

Listas vinculadas singly

El sistema operativo proporciona compatibilidad integrada con listas vinculadas singly que usan estructuras SINGLE_LIST_ENTRY . Una lista vinculada singly consta de un encabezado de lista más un número de entradas de lista. (El número de entradas de lista es cero si la lista está vacía). Cada entrada de lista se representa como una estructura de SINGLE_LIST_ENTRY . El encabezado de lista también se representa como una estructura de SINGLE_LIST_ENTRY .

Cada estructura SINGLE_LIST_ENTRY contiene un miembro Next que apunta a otra estructura de SINGLE_LIST_ENTRY . En la estructura SINGLE_LIST_ENTRY que representa el encabezado de lista, el miembro Next apunta a la primera entrada de la lista o es NULL si la lista está vacía. En la estructura SINGLE_LIST_ENTRY que representa una entrada de la lista, el miembro Next apunta a la siguiente entrada de la lista o es NULL si esta entrada es la última de la lista.

Las rutinas que manipulan una lista vinculada singly toman un puntero a un SINGLE_LIST_ENTRY que representa el encabezado de lista. Actualizan el puntero Siguiente para que apunte a la primera entrada de la lista después de la operación.

Supongamos que la variable ListHead es un puntero a la estructura SINGLE_LIST_ENTRY que representa el encabezado de lista. Un controlador manipula ListHead de la siguiente manera:

  • Para inicializar la lista como vacía, establezca ListHead-Next> en NULL.

  • Para agregar una nueva entrada a la lista, asigne un SINGLE_LIST_ENTRY para representar la nueva entrada y, a continuación, llame a PushEntryList para agregar la entrada al principio de la lista.

  • Desactive la primera entrada de la lista mediante PopEntryList.

Un SINGLE_LIST_ENTRY, por sí solo, tiene un miembro Next . Para almacenar sus propios datos en las listas, inserte el SINGLE_LIST_ENTRY como miembro de la estructura que describe la entrada de lista, como se indica a continuación.

typedef struct {
  // driver-defined members
  .
  .
  .
  SINGLE_LIST_ENTRY SingleListEntry;
 
  // other driver-defined members
  .
  .
  .
} XXX_ENTRY;

Para agregar una nueva entrada a la lista, asigne una estructura de XXX_ENTRY y, a continuación, pase un puntero al miembro SingleListEntry a PushEntryList. Para convertir un puntero al SINGLE_LIST_ENTRY de nuevo en un XXX_ENTRY, use CONTAINING_RECORD. Este es un ejemplo de rutinas que insertan y quitan entradas definidas por el controlador de una lista vinculada singly.

typedef struct {
  PVOID DriverData1;
  SINGLE_LIST_ENTRY SingleListEntry;
  ULONG DriverData2;
} XXX_ENTRY, *PXXX_ENTRY;

void
PushXxxEntry(PSINGLE_LIST_ENTRY ListHead, PXXX_ENTRY Entry)
{
    PushEntryList(ListHead, &(Entry->SingleListEntry));
}

PXXX_ENTRY
PopXxxEntry(PSINGLE_LIST_ENTRY ListHead)
{
    PSINGLE_LIST_ENTRY SingleListEntry;
    SingleListEntry = PopEntryList(ListHead);
    return CONTAINING_RECORD(SingleListEntry, XXX_ENTRY, SingleListEntry);
}

El sistema también proporciona versiones atómicas de las operaciones de lista, ExInterlockedPopEntryList y ExInterlockedPushEntryList. Cada uno toma un parámetro de bloqueo de número adicional. La rutina adquiere el bloqueo de número antes de actualizar la lista y, a continuación, la rutina libera el bloqueo de número una vez completada la operación. Mientras se mantiene el bloqueo, las interrupciones están deshabilitadas. Cada operación de la lista debe usar el mismo bloqueo de número para asegurarse de que cada operación de dicha lista se sincronice con todas las demás operaciones. Debe usar el bloqueo de número solo con estas rutinas exInterlockedXxxList . No utilice el bloqueo de número para ningún otro propósito. Los controladores pueden usar el mismo bloqueo para varias listas, pero este comportamiento aumenta la contención de bloqueo, por lo que los controladores deben evitarlo.

Por ejemplo, las rutinas ExInterlockedPopEntryList y ExInterlockedPushEntryList pueden admitir el uso compartido de una lista vinculada singly por un subproceso de controlador que se ejecuta en IRQL = PASSIVE_LEVEL y un ISR que se ejecuta en DIRQL. Estas rutinas deshabilitan las interrupciones cuando se mantiene el bloqueo de número. Por lo tanto, el ISR y el subproceso del controlador pueden usar de forma segura el mismo bloqueo de giro en sus llamadas a estas rutinas de listaXxxde ExInterlocked sin arriesgar un interbloqueo.

No combine llamadas a las versiones atómicas y no atómicas de las operaciones de lista en la misma lista. Si las versiones atómicas y no atómicas se ejecutan simultáneamente en la misma lista, la estructura de datos podría dañarse y el equipo podría dejar de responder o comprobar errores (es decir, bloqueo). (No se puede adquirir el bloqueo de número al llamar a la rutina no atómica como alternativa a la combinación de llamadas a versiones atómicas y no atómicas de las operaciones de lista. No se admite el uso del bloqueo de número en este modo y puede seguir causando daños en la lista).

El sistema también proporciona una implementación alternativa de listas atómicas vinculadas de forma atómica que es más eficaz. Para obtener más información, vea Listas vinculadas de Singly secuenciadas.

Listas vinculadas doblemente

El sistema operativo proporciona compatibilidad integrada con listas vinculadas duplicadas que usan estructuras LIST_ENTRY . Una lista vinculada doble consta de un encabezado de lista más un número de entradas de lista. (El número de entradas de lista es cero si la lista está vacía). Cada entrada de lista se representa como una estructura de LIST_ENTRY . El encabezado de lista también se representa como una estructura de LIST_ENTRY .

Cada estructura LIST_ENTRY contiene un miembro Flink y un miembro Blink . Ambos miembros son punteros a LIST_ENTRY estructuras.

En la estructura LIST_ENTRY que representa el encabezado de lista, el miembro Flink apunta a la primera entrada de la lista y el miembro Blink apunta a la última entrada de la lista. Si la lista está vacía, Flink y Blink del punto principal de la lista apuntan al propio encabezado de la lista.

En la estructura LIST_ENTRY que representa una entrada de la lista, el miembro Flink apunta a la siguiente entrada de la lista y el miembro Blink apunta a la entrada anterior de la lista. (Si la entrada es la última de la lista, Flink apunta al encabezado de la lista. Del mismo modo, si la entrada es la primera de la lista, Blink apunta al encabezado de la lista).

(Aunque estas reglas pueden parecer sorprendentes a primera vista, permiten que las operaciones de inserción y eliminación de listas se implementen sin ramas de código condicional).

Las rutinas que manipulan una lista vinculada doble toman un puntero a un LIST_ENTRY que representa el encabezado de lista. Estas rutinas actualizan los miembros Flink y Blink en el encabezado de lista para que estos miembros apunten a las primeras y últimas entradas de la lista resultante.

Supongamos que la variable ListHead es un puntero a la estructura LIST_ENTRY que representa el encabezado de lista. Un controlador manipula ListHead de la siguiente manera:

  • Para inicializar la lista como vacía, use InitializeListHead, que inicializa ListHead-Flink> y ListHead-Blink> para que apunte a ListHead.

  • Para insertar una nueva entrada en el encabezado de la lista, asigne un LIST_ENTRY para representar la nueva entrada y, a continuación, llame a InsertHeadList para insertar la entrada al principio de la lista.

  • Para anexar una nueva entrada al final de la lista, asigne un LIST_ENTRY para representar la nueva entrada y, a continuación, llame a InsertTailList para insertar la entrada al final de la lista.

  • Para quitar la primera entrada de la lista, use RemoveHeadList. Esto devuelve un puntero a la entrada eliminada de la lista o a ListHead si la lista está vacía.

  • Para quitar la última entrada de la lista, use RemoveTailList. Esto devuelve un puntero a la entrada eliminada de la lista o a ListHead si la lista está vacía.

  • Para quitar una entrada especificada de la lista, use RemoveEntryList.

  • Para comprobar si una lista está vacía, use IsListEmpty.

  • Para anexar una lista al final de otra lista, use AppendTailList.

Un LIST_ENTRY, por sí mismo, solo tiene miembros Blink y Flink . Para almacenar sus propios datos en las listas, inserte el LIST_ENTRY como miembro de la estructura que describe la entrada de lista, como se indica a continuación.

typedef struct {
  // driver-defined members
  .
  .
  .
  LIST_ENTRY ListEntry;
 
  // other driver-defined members.
  .
  .
  .
} XXX_ENTRY;

Para agregar una nueva entrada a una lista, asigne una estructura de XXX_ENTRY y, a continuación, pase un puntero al miembro ListEntry a InsertHeadList o InsertTailList. Para convertir un puntero a un LIST_ENTRY de nuevo en un XXX_ENTRY, use CONTAINING_RECORD. Para obtener un ejemplo de esta técnica, mediante listas vinculadas singly, consulte Singly Linked Lists above.

El sistema también proporciona versiones atómicas de las operaciones de lista, ExInterlockedInsertHeadList, ExInterlockedInsertTailList y ExInterlockedRemoveHeadList. (Tenga en cuenta que no hay ninguna versión atómica de RemoveTailList o RemoveEntryList). Cada rutina toma un parámetro de bloqueo de número adicional. La rutina adquiere el bloqueo de número antes de actualizar la lista y, a continuación, libera el bloqueo de número una vez completada la operación. Mientras se mantiene el bloqueo, las interrupciones están deshabilitadas. Cada operación de la lista debe usar el mismo bloqueo de número para asegurarse de que cada operación de este tipo de la lista esté sincronizada entre sí. Debe usar el bloqueo de número solo con estas rutinas exInterlockedXxxList . No utilice el bloqueo de número para ningún otro propósito. Los controladores pueden usar el mismo bloqueo para varias listas, pero este comportamiento aumenta la contención de bloqueo, por lo que los controladores deben evitarlo.

Por ejemplo, las rutinas ExInterlockedInsertHeadList, ExInterlockedInsertTailList y ExInterlockedRemoveHeadList pueden admitir el uso compartido de una lista vinculada duplicada por un subproceso de controlador que se ejecuta en IRQL = PASSIVE_LEVEL y un ISR que se ejecuta en DIRQL. Estas rutinas deshabilitan las interrupciones cuando se mantiene el bloqueo de número. Por lo tanto, el ISR y el subproceso del controlador pueden usar de forma segura el mismo bloqueo de giro en sus llamadas a estas rutinas de listaXxxde ExInterlocked sin arriesgar un interbloqueo.

No combine llamadas a las versiones atómicas y no atómicas de las operaciones de lista en la misma lista. Si las versiones atómicas y no atómicas se ejecutan simultáneamente en la misma lista, la estructura de datos podría dañarse y el equipo podría dejar de responder o comprobar errores (es decir, bloqueo). (No puede trabajar para adquirir el bloqueo de número al llamar a la rutina no atómica para evitar mezclar llamadas a versiones atómicas y no atómicas de las operaciones de lista. No se admite el uso del bloqueo de número en este modo y puede seguir causando daños en la lista).

Listas vinculadas singly secuenciadas

Una lista vinculada secuenciada es una implementación de listas vinculadas de forma singly que admite operaciones atómicas. Es más eficaz para las operaciones atómicas que la implementación de listas vinculadas singly descritas en Listas vinculadas singly.

Una estructura de SLIST_HEADER se usa para describir el encabezado de una lista vinculada secuenciadamente, mientras que SLIST_ENTRY se usa para describir una entrada de la lista.

Un controlador manipula la lista de la siguiente manera:

Un SLIST_ENTRY, por sí solo, tiene un miembro Next . Para almacenar sus propios datos en las listas, inserte el SLIST_ENTRY como miembro de la estructura que describe la entrada de lista, como se indica a continuación.

typedef struct 
{
  // driver-defined members
  .
  .
  .
  SLIST_ENTRY SListEntry;
  // other driver-defined members
  .
  .
  .

} XXX_ENTRY;

Para agregar una nueva entrada a la lista, asigne una estructura de XXX_ENTRY y, a continuación, pase un puntero al miembro SListEntry a ExInterlockedPushEntrySList. Para convertir un puntero al SLIST_ENTRY de nuevo en un XXX_ENTRY, use CONTAINING_RECORD. Para obtener un ejemplo de esta técnica, mediante listas vinculadas sin secuencia, consulte Listas vinculadas sin secuencias.

Advertencia Para los sistemas operativos Microsoft Windows de 64 bits, las estructuras de SLIST_ENTRY deben estar alineadas con 16 bytes.

Windows XP y versiones posteriores de Windows proporcionan versiones optimizadas de las funciones de lista vinculadas secuenciadas que no están disponibles en Windows 2000. Si el controlador usa estas funciones y también debe ejecutarse con Windows 2000, el controlador debe definir la marca de _WIN2K_COMPAT_SLIST_USAGE, como se indica a continuación:

#define _WIN2K_COMPAT_SLIST_USAGE

En el caso de los procesadores basados en x86, esta marca hace que el compilador use versiones de las funciones de lista vinculadas secuenciadas que son compatibles con Windows 2000.