Linked List : Insert at Position

  • In this program, you are going to learn

  • How to insert the elment at position ?

Topics in this section,

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

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

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

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

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

  • list_head is used to initialize the list.

static struct list_head my_list;

  • INIT_LIST_HEAD is used to initialize a list_head structure.

INIT_LIST_HEAD(&my_list);

INIT_LIST_HEAD(&new_node->list);

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

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;
}

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

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_rear function inserts a new node at the end with the given value into the linked list.

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.

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.

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

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

module_init(linkedlist_init);
module_exit(linkedlist_exit);

  1#include <linux/init.h>
  2#include <linux/module.h>
  3#include <linux/kernel.h>
  4#include <linux/list.h>
  5#include <linux/slab.h>
  6
  7MODULE_LICENSE("GPL");
  8MODULE_AUTHOR("linux_usr");
  9MODULE_DESCRIPTION("Linked List");
 10
 11struct list_node {
 12	int data;
 13	struct list_head list;
 14};
 15
 16static struct list_head my_list;
 17
 18void insert_rear(int value)
 19{
 20	struct list_node *new_node;
 21
 22	new_node = kmalloc(sizeof(struct list_node), GFP_KERNEL);
 23	
 24	if (!new_node) {
 25		pr_err("Memory allocation failed\n");
 26		return;
 27	}
 28
 29	new_node->data = value;
 30	INIT_LIST_HEAD(&new_node->list);
 31	list_add_tail(&new_node->list, &my_list);
 32}
 33
 34void insert_at_pos(int value, int position)
 35{
 36	struct list_node *new_node;
 37	struct list_head *pos;
 38	int i = 0;
 39
 40	new_node = kmalloc(sizeof(struct list_node), GFP_KERNEL);
 41
 42	if (!new_node) {
 43		pr_err("Memory allocation failed\n");
 44		return;
 45	}
 46
 47	new_node->data = value;
 48	INIT_LIST_HEAD(&new_node->list);
 49
 50	pos = &my_list;
 51	while (i < position && pos->next != &my_list) {
 52		pos = pos->next;
 53		i++;
 54	}
 55
 56	list_add(&new_node->list, pos);
 57}
 58
 59void display(void)
 60{
 61	struct list_node *ptr;
 62
 63	pr_info("Linked list: ");
 64	list_for_each_entry(ptr, &my_list, list) {
 65		printk(KERN_CONT "%d -> ", ptr->data);
 66	}
 67
 68	printk(KERN_CONT "NULL\n");
 69}
 70
 71
 72static int __init linkedlist_init(void)
 73{
 74	pr_info("Driver loaded\n");
 75	
 76	INIT_LIST_HEAD(&my_list);
 77
 78	insert_rear(0);
 79	insert_rear(2);
 80	insert_rear(3);
 81	insert_rear(4);
 82	insert_rear(5);
 83
 84	pr_info("Linked list after insertion : \n");
 85        display();
 86
 87	insert_at_pos(1, 1);
 88
 89	pr_info("Linked list after inserting atspecific position : \n");
 90	display();
 91
 92	return 0;
 93}
 94
 95static void __exit linkedlist_exit(void)
 96{
 97	struct list_node *ptr, *next;
 98
 99	list_for_each_entry_safe(ptr, next, &my_list, list) {
100		list_del(&ptr->list);
101		kfree(ptr);
102	}
103
104	pr_info("Driver unloaded\n");
105}
106
107module_init(linkedlist_init);
108module_exit(linkedlist_exit);

1obj-m += insert.o
2all:
3	make -C /lib/modules/$(shell uname -r)/build M=$(PWD) modules
4clean:
5	make -C /lib/modules/$(shell uname -r)/build M=$(PWD) clean

  • Run Make to compile the module.

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

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

$ sudo insmod ./insert.ko

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

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

$ sudo rmmod insert

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

$ 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

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
See Also