modo corretto di unire due doppia lista collegata

Question

nei sorgenti del kernel di Linux, il list_splice è implementato 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; 
} 

Non è la list già che punta alla testa di una lista collegata? Perché dobbiamo recuperare lo list->next?

Answer 1

La doppia API dell'elenco collegato nel kernel Linux viene implementata come un'astrazione dell'elenco circolare . In tale schema semplice il nodo HEAD non contiene contiene alcun payload (dati) e viene utilizzato esplicitamente per mantenere il punto di partenza dell'elenco. A causa di tale progettazione è davvero semplice a) controllare se la lista è vuota, e b) lista di debug perché i nodi inutilizzati sono stati assegnati al cosiddetto POISON - numero magico specifico solo per i puntatori delle liste nell'intero kernel.

1) elenco non inizializzato

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

2) elenco vuoto

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

3) elenco con un elemento

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

4) due elementi nell'elenco

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

Nell'algoritmo di blocco inferiore esiste una garanzia solo per accanto al puntatore per essere coerenti. La garanzia non è sempre stata così. Lo introduce commit 41071d65e11b.