contributed by < brian049
>
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.
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.
Using list_for_each_entry_safe
to traverse and release all nodes in queue.
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.
Avoid referencing anything from CSDN unless you can verify its originality across the entire internet.
strcpy
strncpy
strdup
Similar to q_insert_tail
function, but using list_add_tail
macro in linux/list.h instead.
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 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.
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.
Show me the proof!
I choose Valgrind to detect this segmentation fault.
And I got the output showing below:
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.
Show the evidence with effective tools.
Got it. Supplemented with using valgrind.
Similar to q_remove_head
but using list_last_entry
macro instead.
q_size
function returns number of elements in queue by iterating over the queue with list_for_each
function.
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.
Can you do better with circular doubly-linked lists?
In this part I followed the approach of @ranvd to implement delete duplicate nodes and reduced redundant code.
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.
list_move
is not a macro.
Got it. Revised.
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.
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.
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.
???
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.
Implementation is similar to q_ascend
but with reverse way.