linux2024-homework1

# 2024q1 Homework1 (lab0) contributed by < `brian049` > ## Modify queue.[ch] :::danger Enhance your English writing by making the report's structure more cohesive. Start each paragraph by summarizing its motivation and purpose. > Got it. I would add additional information after I finish all parts of queue.c. > :warning: No! Before developing any C code, you should put your ideas and findings in writing. When you are fine-tuning the code, you should also include your observations. ::: ### q_new :::danger Before developing any C code, you should put your ideas and findings in writing. When you are fine-tuning the code, you should also include your observations. ::: Create a new node and initialize it. ```c /* Create an empty queue */ struct list_head *q_new() { struct list_head *new_list = malloc(sizeof(struct list_head)); if (!new_list) return NULL; INIT_LIST_HEAD(new_list); return new_list; } ``` ### q_free Using `list_for_each_entry_safe` to traverse and release all nodes in queue. ```c /* Free all storage used by queue */ void q_free(struct list_head *l) { if (!l) return; element_t *entry, *safe; list_for_each_entry_safe (entry, safe, l, list) q_release_element(entry); free(l); } ``` ### q_insert_head The purpose of the `q_insert_head` function is to insert a new node at the beginning of a linked list. This function ensures memory allocation for the new node and copies the given string into the new node's value. - Before creating space for the new node, it's essential to check if there is available memory. If memory allocation fails, the function should return false to indicate the failure. - To copy strings efficiently and safely in C, it's important to consider different functions like strcpy, strncpy, and strdup. - Inquiring about the differences and advantages of these functions from Gemini can provide valuable insights into choosing the most suitable one for the task. - strdup stands out as the safer option among the three functions mentioned, as it automatically allocates sufficient memory space for the copied string, reducing the risk of buffer overflow or memory corruption issues.  :::danger Avoid referencing anything from CSDN unless you can verify its originality across the entire internet. ::: - strcpy - Copies the entire source string to the destination string, including the null-terminating character. - <font color="red">Does not check for buffer overflows.</font> - Returns a pointer to the destination string. - strncpy - Copies at most n characters from the source string to the destination string. - Pads the destination string with null characters if the source string is shorter than n characters. - <font color="red">Does not check for buffer overflows.</font> - Returns a pointer to the destination string. - strdup - Allocates a new string on the heap and copies the source string to the new string. - Returns a pointer to the new string. ### q_insert_tail Similar to `q_insert_tail` function, but using `list_add_tail` macro in [linux/list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h) instead. ### q_remove_head The `q_remove_head` function serves the purpose of removing an element from the head of a queue implemented using a linked list. It utilizes the list_del function from [linux/list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h) to delete the element from the list. By utilizing list_first_entry, the function efficiently retrieves the first entry in the list. To understand the implementation of this function further, I examined the queue.h header file, where I found references to string copying operations using strncpy. ```c /* Remove an element from head of queue */ element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize) { if (!head || list_empty(head)) return NULL; element_t *entry = list_first_entry(head, element_t, list); strncpy(sp, entry->value, bufsize-1); sp[bufsize - 1] = '\0'; list_del(&entry->list); return entry; } ``` Unfortunately, when I ran the `make test` command, I got a error message: > segmentation fault occurred. You deferenced a NULL or invalid pointer. in trace-17-complexity. The segmentation fault is likely caused by an overflow in strncpy when copying the string. :::danger Show me the proof! ::: #### Valgrind detection and code revision I choose Valgrind to detect this segmentation fault. ```shell $ make valgrind ``` And I got the output showing below: ``` ==4249== Invalid write of size 1 ==4249== at 0x484F010: strncpy (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so) ==4249== by 0x10F98F: strncpy (string_fortified.h:95) ==4249== by 0x10F98F: q_remove_head (queue.c:89) ... ``` `Invalid write of size 1`: Attempting to write into an illegal region. This type of error often occurs when using strncpy without checking the buffer size first. This means that the input string exceeds the buffer size. So I added a judgment to determine whether the copy string plus a null character is larger than the buffer size. :::danger Show the evidence with effective tools. > Got it. Supplemented with using valgrind. ::: ```c /* Remove an element from head of queue */ element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize) { if (!head || list_empty(head)) return NULL; element_t *entry = list_first_entry(head, element_t, list); if (!entry) return NULL; if (!sp){ list_del(&entry->list); return entry; } size_t len = strlen(entry->value); if (len <= bufsize - 1) { strncpy(sp, entry->value, len); sp[len] = '\0'; } else { strncpy(sp, entry->value, bufsize - 1); sp[bufsize - 1] = '\0'; } list_del(&entry->list); return entry; } ``` ### q_remove_tail Similar to `q_remove_head` but using `list_last_entry` macro instead. ### q_size `q_size` function returns number of elements in queue by iterating over the queue with `list_for_each` function. ```c int q_size(struct list_head *head) { if (!head) return 0; int len = 0; struct list_head *li; list_for_each (li, head) len++; return len; } ``` ### q_delete_mid Using **two pointer** method to deal with this part. One for the front node and the other for the last node. Move to the middle respectively to find the middle node then remove it from list. :::danger Can you do better with circular doubly-linked lists? ::: ```c /* Delete the middle node in queue */ bool q_delete_mid(struct list_head *head) { // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/ if (!head || list_empty(head)) return NULL; element_t *entry; if (list_is_singular(head)){ entry = list_entry(head->next, element_t, list); list_del(head->next); } else { struct list_head *front = head->next, *rear = head->prev; while (front != rear && rear->next != front){ front = front->next; rear = rear->prev; } // Now the front pointer points to the middle node entry = list_entry(front, element_t, list); list_del(front); } free(entry->value); free(entry); return true; } ``` ### q_delete_dup - Stop when current pointer or the next node of current pointer is head - Determine whether current node has same value with its neighbor nodes In this part I followed the approach of @ranvd to implement delete duplicate nodes and reduced redundant code. ### q_swap This part aims at swapping position of a node and its next node. So first I use `list_move` to swap two nodes's position, then use `list_for_each_safe` to traverse the whole queue. :::warning `list_move` is not a macro. > Got it. Revised. ::: ```c /* Swap every two adjacent nodes */ void q_swap(struct list_head *head) { // https://leetcode.com/problems/swap-nodes-in-pairs/ if (!head || list_empty(head)) return; struct list_head *node = head, *iterator, *safe; // traverse queue int count = 0; list_for_each_safe (iterator, safe, head) { count++; if (!(count & 1)){ list_move(iterator, node); iterator = iterator->next; node = iterator; } } } ``` #### revision After I finished the q_reverseK part, I found that `q_swap` is just one kind of q_reverseK, so I revised the previous edition. ```diff /* Swap every two adjacent nodes */ void q_swap(struct list_head *head) { // https://leetcode.com/problems/swap-nodes-in-pairs/ if (!head || list_empty(head)) return; - struct list_head *node = head, *iterator, *safe; - // traverse queue - int count = 0; - list_for_each_safe (iterator, safe, head) { - count++; - if (!(count & 1)){ - list_move(iterator, node); - iterator = iterator->next; - node = iterator; - } - } + q_reverseK(head, 2); } ``` ### q_reverse Implementation is similar to the original edition of `q_swap`. First use `list_for_each_safe` to traverse the queue, then use `list_move` to move nodes. ```c /* Reverse elements in queue */ void q_reverse(struct list_head *head) { if (!head || list_empty(head)) return; struct list_head *iterator, *safe; list_for_each_safe (iterator, safe, head) { list_move(iterator, head); } } ``` ### q_reverseK When **counting up to k nodes**, record the position and use `list_cut_position` to cut from the original queue, then reverse the segment and add it to the ans queue. ??? ```c /* Reverse the nodes of the list k at a time */ void q_reverseK(struct list_head *head, int k) { // https://leetcode.com/problems/reverse-nodes-in-k-group/ if (!head || list_empty(head)) return; if (k < 2) return; struct list_head ans, temp; INIT_LIST_HEAD(&ans); INIT_LIST_HEAD(&temp); while (!list_empty(head)) { struct list_head *current = head->next; for (int i = 1; i < k && (current != head); i++) current = current->next; list_cut_position(&temp, head, (current == head) ? current->prev : current); if (current != head) q_reverse(&temp); list_splice_tail(&temp, &ans); } list_splice(&ans, head); } ``` ### q_ascend :::warning Always write down plain and meaningful English descriptions instead of bullets. ::: `q_ascend` function rearranges the elements of a queue in ascending order based on their values. To achieve sorting in ascending order, the function begins by reversing the queue for easier traversal. Initially, the function sets the first node as the minimum value to establish a starting point for comparison. Iterating through the queue, if a node with a value greater than the current minimum value is encountered, the function deletes that node to ensure the sequence remains sorted from smallest to largest. This approach effectively sorts the queue in ascending order while maintaining its integrity. ```c /* Remove every node which has a node with a strictly less value anywhere to * the right side of it */ int q_ascend(struct list_head *head) { // https://leetcode.com/problems/remove-nodes-from-linked-list/ if (!head || list_empty(head)) return 0; q_reverse(head); element_t *entry, *safe; element_t *min = list_first_entry(head, element_t, list); list_for_each_entry_safe (entry, safe, head, list) { if (strcmp(entry->value, min->value) > 0) { list_del(&entry->list); q_release_element(entry); } else min = entry; } q_reverse(head); return q_size(head); } ``` ### q_descend Implementation is similar to `q_ascend` but with reverse way. ## ???