Linked List : Delete Front
==========================

.. tab-set::

    .. tab-item:: Linked List : Delete Front

        * In this program, you are going to learn

        .. panels::
                :container: container pb-4
                :column: col-lg-12 p-2
                :card: shadow

                * How to Delete the elments to the front end of the linked list ?

        .. panels::
                :container: container pb-4
                :column: col-lg-12 p-2
                :card: shadow

                * How to use the below API's ?

                        * `INIT_LIST_HEAD <https://elixir.bootlin.com/linux/v6.2/source/tools/include/linux/list.h#L25>`_

                        * `list_add_tail <https://elixir.bootlin.com/linux/v6.2/source/tools/include/linux/list.h#L75>`_

                        * `list_for_each_entry <https://elixir.bootlin.com/linux/v6.2/source/include/linux/list.h#L673>`_

                        * `list_for_each_entry_safe <https://elixir.bootlin.com/linux/v6.2/source/tools/include/linux/list.h#L531>`_
                        
                        * `list_del <https://elixir.bootlin.com/linux/v6.2/source/tools/include/linux/list.h#L113>`_

                        * `list_empty <https://elixir.bootlin.com/linux/latest/source/include/linux/list.h#L290>`_

                        * `list_entry <https://elixir.bootlin.com/linux/latest/source/tools/include/linux/list.h#L351>`_
              

.. panels::
        :container: container pb-4
        :column: col-lg-12 p-2
        :card: shadow

        Topics in this section,

                * :ref:`Explanation of Program part by part <delete_front_4>`

                    * :ref:`List of headers <delete_front_5>`

                    * :ref:`Modules macro <delete_front_6>`

                    * :ref:`Initialize function and variables <delete_front_7>`

                    * :ref:`Module init function <delete_front_8>`

                    * :ref:`Module exit function <delete_front_9>`

                    * :ref:`Linked list APIs <delete_front_10>`

                    * :ref:`Mention init and exit function <delete_front_11>`

                * :ref:`See the full program below <delete_front_0>`
                
                * :ref:`Makefile <delete_front_1>`

                * :ref:`Compile and Load <delete_front_2>`

                * :ref:`Summary of Linked List APIs <delete_front_3>`


.. _delete_front_4:

.. tab-set::

    .. tab-item:: Explanation of program part by part

        * In this example, we are going to delete the elements in the front end.

        .. _delete_front_5: 

        .. tab-set::

            .. tab-item:: List of headers

                * Add the list of header files to refer the APIs used in this program.

                .. code-block:: c

                    #include <linux/init.h>
                    #include <linux/module.h>
                    #include <linux/kernel.h>
                    #include <linux/list.h>
                    #include <linux/slab.h>

        .. _delete_front_6:
        
        .. tab-set::

            .. tab-item:: Modules macro

                * Add the modules macro which lists the information about the license, author and description.

                .. code-block:: c

                    MODULE_LICENSE("GPL");
                    MODULE_AUTHOR("linux_usr");
                    MODULE_DESCRIPTION("Linked List");

        .. _delete_front_7:

        .. tab-set::

            .. tab-item:: Initialize function and variables
       
                * In this example, we are going to delete the elements in the rear end.

                * ``list_head`` is used to initialize the list.

                .. code-block:: c
        
                    static struct list_head my_list;

                * ``INIT_LIST_HEAD`` is used to initialize a list_head structure.

                .. code-block:: c
                                
                    INIT_LIST_HEAD(&my_list);

                    INIT_LIST_HEAD(&new_node->list);

        .. _delete_front_8:

        .. tab-set::

            .. tab-item:: Module init function

                * Add the module init function to execute the function once when the module is loaded to the linux kernel.

                .. code-block:: c
					
                    static int __init linkedlist_init(void)
                    {
                        pr_info("Driver loaded\n");

                        INIT_LIST_HEAD(&my_list);

                        insert_rear(0);
                        insert_rear(1);
                        insert_rear(2);
                        insert_rear(3);
                        insert_rear(4);

                        pr_info("Linked list after insertion : \n");
                        display();

                        delete_front();

                        pr_info("Linked list after deletion : \n");
                        display();

                        return 0;
                    }

        .. _delete_front_9:

        .. tab-set::

            .. tab-item:: Module exit function

                * Add module exit function which is executed once the module is unloaded from the kernel.

                .. code-block:: c

						static void __exit linkedlist_exit(void)
						{
							struct list_node *ptr, *next;

							list_for_each_entry_safe(ptr, next, &my_list, list) {
								list_del(&ptr->list);
								kfree(ptr);
							}

							pr_info("Driver unloaded\n");
						}

        .. _delete_front_10:

        .. tab-set::

            .. tab-item:: Linked List APIs

                * ``insert_rear`` function inserts a new node at the end with the given ``value`` into the linked list.

                .. code-block:: c

                    void insert_rear(int value)
                    {
                        struct list_node * new_node;
                                       
                        new_node = kmalloc(sizeof(struct list_node), GFP_KERNEL);

                        if (!new_node) {
                                pr_err("Memory allocation failed\n");

                                return;
                        }
                                
                        new_node->data = value;
                        INIT_LIST_HEAD(&new_node->list);
                        list_add_tail(&new_node->list, &my_list);
                    }

                * ``delete_front`` function deletes the first node from the linked list.

                .. code-block:: c

                    void delete_front(void)
                    {
                        struct list_node * front;

                        if (list_empty(&my_list)) {
                                pr_err("List is empty, cannot delete rear");

                                return;
                        }

                        front = list_entry(my_list.next, struct list_node, list);
                        list_del(&front->list);
                        kfree(front);
                    }
                
                * ``display`` function iterates through the linked list using ``list_for_each_entry``. It prints the data in each node to the kernel log.

                .. code-block:: c

                    void display(void)
                    {
                        struct list_node * ptr;
                                        
                        pr_info("Linked list: ");
                        list_for_each_entry(ptr, &my_list, list) {
                                printk(KERN_CONT "%d -> ", ptr->data);
                        }

                        printk(KERN_CONT "NULL\n");
                    }

        .. _delete_front_11:

        .. tab-set::

            .. tab-item:: Mention init and exit functions

                * Add the module init and exit which is called when the module is loaded and unloaded.

                .. code-block:: c

                    module_init(linkedlist_init);
                    module_exit(linkedlist_exit);

.. _delete_front_0:

.. tab-set::

    .. tab-item:: See the full program below

        .. tab-set::

            .. tab-item:: delete.c
	
                .. literalinclude:: delete_front/delete.c
	                :language: c
        	        :linenos:

.. _delete_front_1:

.. tab-set::

    .. tab-item:: Makefile

	.. literalinclude:: delete_front/Makefile
		:language: c
		:linenos:

.. _delete_front_2:

.. tab-set::

    .. tab-item:: Compile and Load
        
        * Run Make to compile the module.

        .. code-block:: shell

            $make
            make -C /lib/modules/5.4.0-150-generic/build M=$HOME/kernel_delete modules
            make[1]: Entering directory '/usr/src/linux-headers-5.4.0-150-generic'
              CC [M]  $HOME/kernel_delete/delete.o
              Building modules, stage 2.
              MODPOST 1 modules
              CC [M]  $HOME/kernel_delete/delete.mod.o
              LD [M]  $HOME/kernel_delete/delete.ko
            make[1]: Leaving directory '/usr/src/linux-headers-5.4.0-150-generic'

        * Run ls to check if delete.ko is generated or not.

        .. code-block:: shell

            $ ls -l
            total 36
            -rw-rw-r-- 1 test test  154 Feb 26 13:18 Makefile
            -rw-rw-r-- 1 test test   47 Feb 26 13:18 modules.order
            -rw-rw-r-- 1 test test    0 Feb 26 13:18 Module.symvers
            -rw-rw-r-- 1 test test  820 Feb 26 13:18 delete.c
            -rw-rw-r-- 1 test test 5880 Feb 26 13:18 delete.ko
            -rw-rw-r-- 1 test test   47 Feb 26 13:18 delete.mod
            -rw-rw-r-- 1 test test  919 Feb 26 13:18 delete.mod.c
            -rw-rw-r-- 1 test test 3448 Feb 26 13:18 delete.mod.o
            -rw-rw-r-- 1 test test 3320 Feb 26 13:18 delete.o

        * Run insmod to load the module.

        .. code-block:: shell

            $ sudo insmod ./delete.ko

        * Check the kernel messages to see if the kernel module is loaded or not.

        .. code-block:: shell

            $ dmesg
            [12045.072071] Driver loaded
            [12045.072073] Linked list after insertion :
            [12045.072073] Linked list: 0 -> 1 -> 2 -> 3 -> 4 -> NULL
            [12045.072076] Linked list after deletion :
            [12045.072076] Linked list: 1 -> 2 -> 3 -> 4 -> NULL

        * Run rmmod to unload the module.

        .. code-block:: shell

            $ sudo rmmod delete

        * Check dmesg to see if the module is unloaded from kernel.

        .. code-block:: shell

            $ dmesg
            [12045.072071] Driver loaded
            [12045.072073] Linked list after insertion :
            [12045.072073] Linked list: 0 -> 1 -> 2 -> 3 -> 4 -> NULL
            [12045.072076] Linked list after deletion :
            [12045.072076] Linked list: 1 -> 2 -> 3 -> 4 -> NULL
            [12050.629679] Driver unloaded

.. _delete_front_3:

.. tab-set::

    .. tab-item:: Summary of Linked list APIs

        =============================== ======================================================================
        API                             Learning
        =============================== ======================================================================
        INIT_LIST_HEAD                  To  initialize a list_head structure
        list_head                       To initialize the list
        list_for_each_entry             To iterate over list of given type
        list_for_each_entry_safe        To iterate over list of given type safe against removal of list entry
        list_add_tail                   To insert a new entry before the specified head
        list_del                        To delete entry from list   
        list_empty                      To test whether a list is empty 
        list_entry                      To get the struct for this entry
        =============================== ======================================================================


.. card:: See Also

        * Previous Chapters

                * :doc:`../chapter1_basics/chapter1_basics`

                * :doc:`../chapter2_kthreads/chapter2_kthreads`

                * :doc:`../chapter3_tasklets/chapter3_tasklets`

                * :doc:`../chapter4_workqueue/chapter4_workqueue`        

                * :doc:`../chapter5_timer/chapter5_timer`

     
        * Other Linked List topics

                * :doc:`insert_rear`

                * :doc:`insert_front`

                * :doc:`insert_at_pos`

                * :doc:`delete_rear`

                * :doc:`delete_at_pos`

                * :doc:`list_splice`

                * :doc:`list_splice_init`

                * :doc:`list_splice_tail`

                * :doc:`list_splice_tail_init`

                * :doc:`list_cut_position`

                * :doc:`list_del_init`

                * :doc:`list_first`

                * :doc:`list_first_entry_or_null`

                * :doc:`list_for_each`

                * :doc:`list_for_each_entry_continue`

                * :doc:`list_for_each_entry_continue_reverse`

                * :doc:`list_for_each_entry_safe_reverse`

                * :doc:`list_is_singular`

                * :doc:`list_last`

                * :doc:`list_move`

                * :doc:`list_move_tail`

                * :doc:`list_replace`

                * :doc:`list_replace_init`


        * Next Chapter

                * :doc:`../chapter9_fileSystem/chapter9_fileSystem`


        * Other Chapter
                
                * :doc:`../chapter10_netlink/chapter10_netlink`