--- # System prepended metadata title: Linux Kernel Project tags: [project, LinuxKernel] --- --> # Introduction - This project implement the functions of doubly linked list and additional information is available at [here](https://hackmd.io/@sysprog/linux2025-lab0/%2F%40sysprog%2Flinux2025-lab0-a#Git-Hooks-%E9%80%B2%E8%A1%8C%E8%87%AA%E5%8B%95%E7%A8%8B%E5%BC%8F%E7%A2%BC%E6%8E%92%E7%89%88%E6%AA%A2%E6%9F%A5). - This project is available at this [GitHub Repository](https://github.com/PoChuan994/lab0-c). # Implementation ## Doubly Link List Data Structure - The **doubly linked list** follows a **three-layer structure**. - The **first layer** is used to manage all lists. ```c= typedef struct { struct list_head *q; struct list_head chain; int size; int id; } queue_contex_t; ``` - The **second layer** is the fundamental structure of a **doubly linked list**, defined as bellow: ```c= struct list_head { struct list_head *prev; struct list_head *next; } ``` - The **third layer** associates a node with a **character string**, defined as follows: ```c= typedef struct { char *val; struct list_head list; }element_t; ``` ## Generic Function Implementation Pattern - Implement **memory allocation** operations when **concatenating**, **creating**, **removing**, or **rearranging** nodes using the **Linux Kernel-style API**. - By utilizing the list manipulation functions defined in the Linux kernel-style API, we can avoid redundant code, enhance reusability, and improve tracking of list operations. - Check if the **input is null** to **prevent segmentation faults** due to *null pointer dereference* in sequential statements. ```c= if (!head) return 0; // or if (!head) return; ``` - `if (!head) return 0;` or `if (!head) return;` - Return `false` if dynamic memory allocation fails. ```c= element_t *new = malloc(sizeof(element_t)); if (!new) return false; ``` - **Usage of different** `for` **loop macros** in the **Linux Kernel API**: 1. `list_for_each`: ```c= #define list_for_each(node, head) \ for (node = (head)->next; node != (head); node = node->next) ``` - Used to iterate through **every node** in a list **without removing or deleting** nodes operations. 2. `list_for_each_safe`: ```c= #define list_for_each_safe(node, safe, head) \ for (node = (head)->next, safe = node->next; node != (head); \ node = safe, safe = node->next) ``` - The `safe` node stores the reference to be **next node** before modifying the current node. - Suitable for **freeing**, **deleting**, or **reversing** nodes in a list. 3. `list_for_each_entry` 4. `list_entry` - Use the `list_entry` macro to retrieve the structure containing the list node: 5. `list_for_first_entry` ## `q_remove_head` and `q_remove_tail` - The *remove operation* breaks the links of a node from the list but does not free its memory. - The removed node should be **reinitialized** according to the [homework requirement](https://hackmd.io/@sysprog/linux2025-lab0/%2F%40sysprog%2Flinux2025-lab0-a#Git-Hooks-%E9%80%B2%E8%A1%8C%E8%87%AA%E5%8B%95%E7%A8%8B%E5%BC%8F%E7%A2%BC%E6%8E%92%E7%89%88%E6%AA%A2%E6%9F%A5). - Modify the stack pointer `sp` using the `list_entry` macro to obtain the correct memory address. - Break and reconnect links using `list_del` macro and reinitialize the removed node. ## `q_delete_mid` ::: spoiler Implementation ```c= bool q_delete_mid(struct list_head *head) { if (!head || list_empty(head)) /* input validation */ return false; struct list_head **indir = &(head->next); const struct list_head *fast = head->next; for (; fast != head && fast->next != head; fast = fast->next->next) indir = &(*indir)->next; element_t *element = list_entry(*indir, element_t, list); list_del(&element->list); q_release_element(element); return true; } ``` ::: - Unlike the *remove operation*, the *delete operation* **frees** the memory of deleted node and **reinitialze** the node similarly. - Use an indirect pointer `indir` to implement a **two pointer approach** for finding the middle node in a list. - Obtain the structure type of the node to be removed using `list_entry` macro. - Break and reconnect the list of the removed node using `list_dele` macro. - Free the allocated memory using `q_release_element`. ## `q_delete_dup` - This function aims to delete all duplicate strings from a list. - The operation concept can be introduced through implementation of singly linked list. ### Singly linked list :::spoiler Implementation ```c= struct ListNode* deleteDuplicates(struct ListNode* head) { struct ListNode **indir = &head; while (*indir) { struct ListNode *curr = *indir; if (curr->next && curr->val == curr->next->val) { while (curr->next && curr->val == curr->next->val) curr = curr->next; *indir = curr->next; } else { indir = &(*indir)->next; } } return head; } ``` ::: - The concept and implementation in a [singly linked list](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/) are shown below: - Use two pointers, `**indir`, which points to the link to be updated, and `curr`, which points to the node being checked to determine if the next node's value is equal to `curr`. - If the value of `curr` is equal to `curr->next`, iteratively check further until the next node's value is not equivalent. - Otherwise, update the `**indir` to continue checking. ### Doubly-linked list :::spoiler implementation ```c= bool q_delete_dup(struct list_head *head) { volatile struct list_head *dummy = head; (void) dummy; if (!head || list_empty(head)) /* input validation */ return false; element_t *curr_entry = list_first_entry(head, element_t, list); while (&curr_entry->list != head) { struct list_head *next = curr_entry->list.next; element_t *next_entry = list_entry(next, element_t, list); /* check if there is duplicate element */ bool check = false; while (&next_entry->list != head && !strcmp(curr_entry->value, next_entry->value)) { struct list_head *tmp = next_entry->list.next; list_del(&next_entry->list); q_release_element(next_entry); next_entry = list_entry(tmp, element_t, list); check = true; } if (check) { struct list_head *tmp = curr_entry->list.next; list_del(&curr_entry->list); q_release_element(curr_entry); curr_entry = list_entry(tmp, element_t, list); } else { curr_entry = next_entry; } } return true; } ``` ::: - In this implementation, the next node cannot be accessed directly using the indirect pointer `indir`, so the solution resorts to using only the *Two pointers approach* to traverse and manipulate the list. - The process starts by getting the first node that actually contains a character string using `list_first_entry` (line 9). - The function then traverses the list, checking for duplicates by comparing `curr_entry->value` with `next_entry->value`. - If a duplicate is found, the duplicate nodes are removed using `list_del`, and their memory is released by calling` q_release_element`. - After processing the duplicates, if any were removed, the `curr_entry` pointer is updated to skip over the duplicates, otherwise, it moves to the next node. ## `q_swap` :::spoiler Implementation ```c= struct list_head *first = head->next; struct list_head *second = first->next; for (; first != head && second !=head; first = first->next, second = first->next) { /* * break the links of first node and * reconcatenate its previous and next nodes * */ list_del(first); /* insert first node after second node */ list_add(first, second); } ``` ::: - This function swaps every two adjacent nodes. - Use the *Two Pointers approach* to traverse the list. - Remove the `first` node from the list and reinitialize it using `list_add` function. - Reinsert `first` node after `second` using `list_add` function. - The workflow of `q_swap` is shown in the following pictures. 1. The `first` pointer points to the first node, while the `second` pointer points to the next node of `first`. ![q_swap1.drawio](https://hackmd.io/_uploads/S1DR0ml6Je.png) 2. After executing `list_del(first)`, the node pointed by `first` is temporarily removed from the list and its links which adjacent nodes are broken. ![q_swap2.drawio](https://hackmd.io/_uploads/SyGf1Vxa1e.png) 3. The node originally pointed by `first` node is reinserted immediatly after the `second` using `list_add(first, second)`. ![q_swap3.drawio(2)](https://hackmd.io/_uploads/B1DZx4l6yl.png) 4. In next iteration, `first` moves to the next node in the list (previously the third node), while `second` moves to the node after `first` (previously the fourth node). ![q_swap4.drawio](https://hackmd.io/_uploads/SJ2ak4l6Jg.png) ## `q_reverse` :::spoiler Implementation ```c= void q_reverse(struct list_head *head) { struct list_head *current, *safe; list_for_each_safe (current, safe, head) list_move(current, head); } ``` ::: - This function aims to reverse a list. - Since this function does not allocate additional memory, there is no risk of memory leaks; it only reorders nodes using the Linux kernel-style API. - Avoid pointer invalidation issues when modifying the list during traversal using the`list_for_each_safe` macro. - `list_move` function do following operations: 1. Remove `current` node from a list. 2. Reinitialize `current` node. 3. Reinsert `current` node after `head` node as first node iteratively. ## `q_reverse_k` :::spoiler Implementation ```c= void q_reverseK(struct list_head *head, int k) { // https://leetcode.com/problems/reverse-nodes-in-k-group/ if (!head || head->next == head || k <= 1) return; size_t cnt = 0; struct list_head *curr = NULL, *safe = NULL, *start = head; list_for_each_safe (curr, safe, head) { cnt++; if (cnt == k) { LIST_HEAD(tmp); cnt = 0; list_cut_position(&tmp, start, curr); q_reverse(&tmp); list_splice(&tmp, start); start = safe->prev; } } } ``` ::: - Reverse every `k` nodes in a list. - When every `k` nodes are accumulated during traversal: 1. Create an empty list `tmp` to temporarily store the nodes that will be reversed. 2. Use the `list_cut_position` function to remove the `k` nodes from the list and store them in `tmp`. 3. Reverse the `tmp` list using `q_reverse`. 4. Reinsert the reversed `tmp` list back into the original position using `list_splice`. ## `q_sort` ### First Version :::spoiler Implementation ```c= void q_sort(struct list_head *head, bool descend) { if (!head || list_empty(head) || list_is_singular(head)) return; struct list_head *slow = head->next, *fast = head->next->next; while (fast != head && fast->next != head) { slow = slow->next; fast = fast->next->next; } struct list_head l, r; INIT_LIST_HEAD(&l); INIT_LIST_HEAD(&r); list_cut_position(&l, head, slow); list_splice_init(head, &r); q_sort(&l, descend); q_sort(&r, descend); merge(head, &l, &r, descend); } void merge(struct list_head *head, struct list_head *left, struct list_head *right, bool descend) { while (!list_empty(left) && !list_empty(right)) { const element_t *l = list_entry(left->next, element_t, list); const element_t *r = list_entry(right->next, element_t, list); if (((descend * 2) - 1) * strcmp(l->value, r->value) > 0) list_move_tail(left->next, head); else list_move_tail(right->next, head); } if (list_empty(head)) list_splice_tail(right, head); else list_splice_tail(left, head); } ``` ::: #### `q_sort` - Use the `fast` and `second` pointers to find the middle node `slow`. - Initialize two list `l` and `r` to store halve sub-lists. - Move nodes from`head` to `l`, cutting the list at `slow` using `list_cut_position`. - Move remaining nodes from this `head` to the list `r` using `list_splice_init` function. - Sort both sub-lists recursively using `q_sort`. - Merge the two sorted sub-list using `merge` function. #### `merge` - `while` both sub-lists are not empty, do the followings: - Extract first node in both sub-lists using `list_entry`. - Insert the selected node into tail of the list `head` according to `descend` variable. - Insert remaining nodes into the list `head`. #### Analysis - Memory leaks: - Create two sub-lists `l` and `r` to record reassignment order of list instead and move back all nodes to the list `head` without allocating new memory. - stable: - if `strcmp(l->value, r->value) == 0`, `left->next` node place to tail before `second`. ### Optimized Version ::: spoiler Implementation ```c= void q_sort(struct list_head *head, bool descend) { if (!head || head->next == head || head->prev == head->next) return; struct list_head *slow = head; const struct list_head *fast = head->next; for (; fast != head && fast->next != head; fast = fast->next->next) slow = slow->next; struct list_head left; list_cut_position(&left, head, slow); q_sort(&left, descend); q_sort(head, descend); q_merge_two(head, &left, descend); } void q_merge_two(struct list_head *first, struct list_head *second, bool descend) { if (!first || !second) return; struct list_head tmp; INIT_LIST_HEAD(&tmp); while (!list_empty(first) && !list_empty(second)) { element_t *first_top = list_first_entry(first, element_t, list); element_t *second_top = list_first_entry(second, element_t, list); const char *first_str = first_top->value, *second_str = second_top->value; bool check; if (descend) check = strcmp(first_str, second_str) > 0; else check = strcmp(first_str, second_str) < 0; element_t *add_first = check ? first_top : second_top; list_move_tail(&add_first->list, &tmp); } list_splice_tail_init(first, &tmp); list_splice_tail_init(second, &tmp); list_splice(&tmp, first); } ``` ::: #### Improvement of `q_sort` implementation - Create only one **extra** sub-list to record first halve original list. - Save time to move remaining element the second extra sub-list using `list_splice_init` and `INIT_LIST_HEAD` two times. - Seperate a list into two sub-lists `left` and `head` with same length. - Sort both sub-lists and merge them using `q_merge_two`. #### `q_merge_two` implementation - `q_merge_two` function: - `while` both sub-lists are not empty, compare their string values and appending the smaller (or larger, based on `descend`) element to the tail of `tmp`. - Appending the remaining elements from both lists to `tmp` using `list_splice_tail_init`. - Move all nodes from `tmp` back into `first` list using `list_splice`. #### Analysis - Memory leaks: - Create a `list` to record reassignment order of list instead and move back all nodes to the list `head` without allocating new memory. - stable: - if `first_str == second_str`, `first` node place to tail before `second`. # Reference - [The Linux Kernel API](https://docs.kernel.org/core-api/kernel-api.html) - [2025 年 Linux 核心設計課程作業 —— lab0 (A)](https://hackmd.io/@sysprog/linux2025-lab0/%2F%40sysprog%2Flinux2025-lab0-a#Git-Hooks-%E9%80%B2%E8%A1%8C%E8%87%AA%E5%8B%95%E7%A8%8B%E5%BC%8F%E7%A2%BC%E6%8E%92%E7%89%88%E6%AA%A2%E6%9F%A5)