Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Correct way to join two double linked list

In the Linux kernel source, the list_splice is implemented with __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;
}

Isn't the list already pointing to the head of a linked list? Why do we need to fetch list->next instead?

like image 312
satoru Avatar asked Nov 22 '15 02:11

satoru


People also ask

How do I combine two doubly linked lists?

The function merge_list() modify the two list, which are passed as arguments to it, as it resets the next and prev pointers of the lists node in order to merge them. So, after this function call, both the lists passed as arguments to it are no more valid. Set their head and tail pointer to NULL .

How do you join two linked lists?

(1) Create a new head pointer to an empty linked list. (2) Check the first value of both linked lists. (3) Whichever node from L1 or L2 is smaller, append it to the new list and move the pointer to the next node. (4) Continue this process until you reach the end of a linked list.

Why is a double linked list two way?

DLLs are an extension of basic linked lists with only one difference: A doubly linked list contains a pointer to the next node as well as the previous node. This ensures that the list can be traversed in both directions.


1 Answers

The double linked list API in the Linux kernel is implemented as an abstraction of circular list. In that simple scheme the HEAD node does not contain any payload (data) and used explicitly to keep starting point of the list. Due to such design it's really simple to a) check if the list is empty, and b) debug list because unused nodes have been assigned to the so called POISON — magic number specific only to the list pointers in the entire kernel.

1) non-initialized list

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

2) empty list

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

3) list with one element

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

4) two items in the list

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

In the lock less algorithm there is a guarantee only for next pointer to be consistent. The guarantee wasn't always the case. The commit 2f073848c3cc introduces it.

like image 54
0andriy Avatar answered Sep 30 '22 00:09

0andriy