Forma correcta de unir dos listas de doble enlace

2 minutos de lectura

En el código fuente del kernel de Linux, el list_splice se implementa con __list_splice:

static inline void __list_splice(const struct list_head *list,
                                 struct list_head *prev,
                                 struct list_head *next)
{
        struct list_head *first = list->next; // Why?
        struct list_head *last = list->prev;

        first->prev = prev;
        prev->next = first;

        last->next = next;
        next->prev = last;
}

¿No es el list ya apuntando al encabezado de una lista enlazada? ¿Por qué tenemos que buscar list->next ¿en lugar de?

  • Si se usa así, entonces el encabezado de la lista probablemente no sea un nodo de lista real.

    – Coronel Treinta y Dos

    22 de noviembre de 2015 a las 2:34

Forma correcta de unir dos listas de doble enlace
0andriy

La API de lista doble enlazada en el kernel de Linux se implementa como una abstracción de lista circular. En ese esquema simple, el nodo HEAD no contienen cualquier carga útil (datos) y se usan explícitamente para mantener el punto de partida de la lista. Debido a este diseño, es realmente sencillo a) verificar si la lista está vacía yb) depurar la lista porque los nodos no utilizados se han asignado a los llamados VENENO — número mágico específico solo para los punteros de lista en todo el núcleo.

1) lista no inicializada

+-------------+
|    HEAD     |
| prev | next |
|POISON POISON|
+-------------+

2) lista vacía

+----------+-----------+
|          |           |
|          |           |
|   +------v------+    |
|   |    HEAD     |    |
+---+ prev | next +----+
    | HEAD   HEAD |
    +-------------+

3) lista con un elemento

+--------------+--------------+
|              |              |
|              |              |
|       +------v------+       |
|       |    HEAD     |       |
|   +---+ prev | next +--+    |
|   |   |ITEM1   ITEM1|  |    |
|   |   +-------------+  |    |
|   +--------------------+    |
|              |              |
|       +------v------+       |
|       |    ITEM1    |       |
+-------+ prev | next +-------+
        |    DATA1    |
        +-------------+

4) dos elementos en la lista

      +----------+
      |          |
      |          |
      |   +------v------+
      |   |    HEAD     |
   +------+ prev | next +----+
   |  |   |ITEM2   ITEM1|    |
   |  |   +-------------+    |
+----------------------------+
|  |  |          |
|  |  |   +------v------+
|  |  |   |    ITEM1    |
|  |  +---+ prev | next +----+
|  |  |   |    DATA1    |    |
|  |  |   +-------------+    |
|  +-------------------------+
|     |          |
|     |   +------v------+
|     |   |    ITEM2    |
+---------+ prev | next +----+
      |   |    DATA2    |    |
      |   +-------------+    |
      |                      |
      +----------------------+

En el algoritmo lockless hay una garantía solo para próximo puntero para ser consistente. La garantía no siempre fue así. el compromiso 2f073848c3cc lo presenta

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad