To create a double linked list with a seperate head node ,in the linux kernel, we can use the pre existing functions and structures defined in the file types.h.
The doubly linked list is formed of two nodes, one is the head node
The second one are the nodes used to form the linked list.
The functions and macros needed to create and use the nodes are defined in the file list.h. To initialize the the list we use the macro
Where ptr should be of the type hlist_head. This points to the head of the double linked list. As we can see this structure has only one pointer of the type hlist_node, thus the head node will point to the first node of double linked list that we want to create.
To add a node to the list we can use the function
The function has been implemented in the file list.h
The function adds the node "n" at the head of the double linked list pointed to by the head node h. It does this by
Allocate the first node of the list to a temporary node : *first = h->first Make the temporary node as the next node of the new node: n->next = first; if the list was not an empty list first will not be null: if(first) allocate the pprev pointer to the address of the node itself: first->pprev = &n->next; Update the value of head node pointer to n : WRITE_ONCE(h->first, n);
We can iterate over the list using the function
To test these functions we will create a structure
In the init function we create the required pointers.
Allocate memory for the k_list structures.
Assign values to the integer in the structure.
Initialize the hlist_head
Add the nodes at the head, so every new node gets added at the head with the other nodes moving away from the head.
The list has been formed, so now we can iterate through the list
In the code we have created and displayed the double linked list in the init funtion, thus to test the code we just need to insert the code into the kernel.
This the full code
Save the file as double_linked_list.c, and use the following makefile to compile the code.
Make and Insert the code using
To see the output execute the message dmesg , we should see the following output.
Thus we can see each node got inserted at the head so the last node inserted which was "30" is the head node.
The second one are the nodes used to form the linked list.
The functions and macros needed to create and use the nodes are defined in the file list.h. To initialize the the list we use the macro
Where ptr should be of the type hlist_head. This points to the head of the double linked list. As we can see this structure has only one pointer of the type hlist_node, thus the head node will point to the first node of double linked list that we want to create.
To add a node to the list we can use the function
The function has been implemented in the file list.h
The function adds the node "n" at the head of the double linked list pointed to by the head node h. It does this by
Allocate the first node of the list to a temporary node : *first = h->first Make the temporary node as the next node of the new node: n->next = first; if the list was not an empty list first will not be null: if(first) allocate the pprev pointer to the address of the node itself: first->pprev = &n->next; Update the value of head node pointer to n : WRITE_ONCE(h->first, n);
We can iterate over the list using the function
To test these functions we will create a structure
In the init function we create the required pointers.
Allocate memory for the k_list structures.
Assign values to the integer in the structure.
Initialize the hlist_head
Add the nodes at the head, so every new node gets added at the head with the other nodes moving away from the head.
The list has been formed, so now we can iterate through the list
In the code we have created and displayed the double linked list in the init funtion, thus to test the code we just need to insert the code into the kernel.
This the full code
Save the file as double_linked_list.c, and use the following makefile to compile the code.
Make and Insert the code using
To see the output execute the message dmesg , we should see the following output.
Thus we can see each node got inserted at the head so the last node inserted which was "30" is the head node.
