Linked List : Insert at Position
================================

.. tab-set::

    .. tab-item:: Linked List : Insert at Position

        * In this program, you are going to learn

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

                * How to insert the elment at position ?

        .. 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_add <https://elixir.bootlin.com/linux/latest/source/include/linux/list.h#L86>`_

                        * `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>`_


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

        Topics in this section,

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

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

                    * :ref:`Modules macro <insert_at_pos_6>`

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

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

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

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

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

                * :ref:`See the full program below <insert_at_pos_0>`
                
                * :ref:`Makefile <insert_at_pos_1>`

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

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


.. _insert_at_pos_4:

.. tab-set::

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

        * In this example, we are going to insert the elements at a position.

        .. _insert_at_pos_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>

        .. _insert_at_pos_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");

        .. _insert_at_pos_7:

        .. tab-set::

            .. tab-item:: Initialize function and variables
            
                * ``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);

        .. _insert_at_pos_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(2);
                        insert_rear(3);
                        insert_rear(4);
                        insert_rear(5);

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

                        insert_at_pos(1, 1);

                        pr_info("Linked list after inserting atspecific position : \n");
                        display();

                        return 0;
                    }

        .. _insert_at_pos_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");
                    }

        .. _insert_at_pos_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);
                    }
               
                * ``insert_at_pos`` function inserts a new node at a position.

                .. code-block:: c

                    void insert_at_pos(int value, int position)
                    {
                        struct list_node * new_node;
                        struct list_head * pos;
                        int i = 0;

                        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);
                        pos = &my_list;
                        while (i < position && pos->next != &my_list) {
                                pos = pos->next;
                                i++;
                        } 

                        list_add(&new_node->list, pos);
                    }

                * ``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");
                    }

        .. _insert_at_pos_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);

.. _insert_at_pos_0:

.. tab-set::

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

        .. tab-set::

            .. tab-item:: insert.c

                .. literalinclude:: insert_at_pos/insert.c
	                :language: c
        	        :linenos:

.. _insert_at_pos_1:

.. tab-set::

    .. tab-item:: Makefile

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


.. _insert_at_pos_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_insert modules
            make[1]: Entering directory '/usr/src/linux-headers-5.4.0-150-generic'
              CC [M]  $HOME/kernel_insert/insert.o
              Building modules, stage 2.
              MODPOST 1 modules
              CC [M]  $HOME/kernel_insert/insert.mod.o
              LD [M]  $HOME/kernel_insert/insert.ko
            make[1]: Leaving directory '/usr/src/linux-headers-5.4.0-150-generic'

        * Run ls to check if insert.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 insert.c
            -rw-rw-r-- 1 test test 5880 Feb 26 13:18 insert.ko
            -rw-rw-r-- 1 test test   47 Feb 26 13:18 insert.mod
            -rw-rw-r-- 1 test test  919 Feb 26 13:18 insert.mod.c
            -rw-rw-r-- 1 test test 3448 Feb 26 13:18 insert.mod.o
            -rw-rw-r-- 1 test test 3320 Feb 26 13:18 insert.o

        * Run insmod to load the module.

        .. code-block:: shell

            $ sudo insmod ./insert.ko

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

        .. code-block:: shell
            
            $ dmesg
            [11413.457124] Driver loaded
            [11413.457126] Linked list after insertion :
            [11413.457126] Linked list: 0 -> 2 -> 3 -> 4 -> 5 -> NULL
            [11413.457129] Linked list after inserting atspecific position :
            [11413.457130] Linked list: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL

        * Run rmmod to unload the module.

        .. code-block:: shell

            $ sudo rmmod insert

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

        .. code-block:: shell

            $ dmesg
            [11413.457124] Driver loaded
            [11413.457126] Linked list after insertion :
            [11413.457126] Linked list: 0 -> 2 -> 3 -> 4 -> 5 -> NULL
            [11413.457129] Linked list after inserting atspecific position :
            [11413.457130] Linked list: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL
            [11422.495504] Driver unloaded

.. _insert_at_pos_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_add                        To insert a new entry after the specified head
        list_del                        To delete entry from list 
        =============================== ===========================================================================================


.. 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:`delete_rear`

                * :doc:`delete_front`

                * :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`