Try   HackMD

2024q1 Homework1 (lab0)

contributed by < brian049 >

Modify queue.[ch]

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

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.

/* 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.

/* 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.

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.
    • Does not check for buffer overflows.
    • 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.
    • Does not check for buffer overflows.
    • 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 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 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.

/* 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.

Show me the proof!

Valgrind detection and code revision

I choose Valgrind to detect this segmentation fault.

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

Show the evidence with effective tools.

Got it. Supplemented with using valgrind.

/* 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.

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.

Can you do better with circular doubly-linked lists?

/* 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.

list_move is not a macro.

Got it. Revised.

/* 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.

/* 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.

/* 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.
???

/* 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

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.

/* 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.

???