# 2024q1 Homework1 (lab0)
contributed by < `EisEisHet` >

## Development Environment

$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0

$ lscpu
Architecture:        	x86_64
  CPU op-mode(s):    	32-bit, 64-bit
  Address sizes:     	48 bits physical, 48 bits virtual
  Byte Order:        	Little Endian
CPU(s):              	4
  On-line CPU(s) list:   0-3
Vendor ID:           	AuthenticAMD
  Model name:        	AMD Ryzen 7 5800H with Radeon Graphics
	CPU family:      	25
	Model:           	80
	Thread(s) per core:  1
	Core(s) per socket:  4
	Socket(s):       	1
	Stepping:        	0
	BogoMIPS:        	6387.97

## Queue operations and improvement process

:::danger
The task is not simply to build APIs for queue operations, but rather to execute the fundamental operations adhering to the specified queue interface. Pay attention to how you express this.
:::

:::danger
To ensure this report is both informative and flows well, it's important to start by outlining the motivation, considerations, and examples for the suggested functions before compiling a list of code snippets.

$\to$ [Guide to Technical Report Writing](https://www.sussex.ac.uk/ei/internal/forstudents/engineeringdesign/studyguides/techreportwriting)
:::

### q_new()
:::danger
Address your motivations and considerations here.
:::

The objective of this function is quite simple, which is to initialize a new node for the queue.

To implement this operation, a block of memory needs to be allocated (```malloc```) to ```head``` and point both ```prev``` and ```next``` to itself.

struct list_head *q_new(){
    struct list_head *head = 
        (struct list_head *) malloc(sizeof(struct list_head));

    head->next = head;
    head->prev = head;
    return head;
}

According to 「[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/YA7RMqd6RE2UL8OmmjU9PQ?both)」, the function ```INIT_LIST_HEAD()``` that is already defined in the header file `queue.h`, is defined as the following:

#define LIST_HEAD(head) struct list_head head = {&(head), &(head)}

static inline void INIT_LIST_HEAD(struct list_head *head) {
    head->next = head;
    head->prev = head;
}

Therefore, to make the code efficient and concise, I modified the code to the following:

struct list_head *q_new(){
    struct list_head *head = 
        (struct list_head *) malloc(sizeof(struct list_head));

+    if(!head)
+      return NULL;
+    INIT_LIST_HEAD(head);
-    head->next = head;
-    -head->prev = head;
    return head;
}

Things to consider:
1. Why is `if(!head) {return NULL};` needed?
Answer: This if statement is for error handling purposes. In the event that a memory block cannot be allocated to the `head`, a NULL pointer will be returned to signify the `malloc` operation has failed.

### q_free()

This operation requires the iteration of every node in the queue, and freeing the memory allocated to that node, repeating this until every node in the queue is freed.

**Considerations:**

:::danger
English!
:::

Referring to 「[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/YA7RMqd6RE2UL8OmmjU9PQ?both)」, there are two functions that can iterate over a linked list: `list_for_each_entry` and `list_for_each_entry_safe`. `list_for_each_entry` visits every entry of the linked list containing `struct list_head`, but the `node` and `head` cannot be modified or unpredictable behavior can occur.

> ~~走訪包含 struct list_head 的另外一個結構之 entry。node 和 head 不能在迴圈中被更改，否則行為不可預期。~~
> Visit the entry of another structure containing struct list_head. Node and head cannot be changed inside the loop, otherwise the behavior will be unpredictable.

On the other hand, the function `list_for_each_entry_safe` iterates over every entry in the list that has the type `struct list_head`. Through the `safe` variable, it records the next node from the current node it is operating on, thus the current node can be removed.

> ~~透過額外的 safe 紀錄每個迭代 (iteration) 所操作的節點的下一個節點，因此目前的節點可允許被移走，其他操作則同為不可預期行為。~~
> Through an additional 'safe, the next node of the node operated in each iteration is recorded, so the current node can be allowed to be removed, but other operations will also have unpredictable behavior.

Therefore I used `list_for_each_entry_safe` in the `q_free()` operation:

void q_free(struct list_head *l)
{
    if (!l)
        return;

    element_t *current, *safe = NULL;
    list_for_each_entry_safe (current, safe, l, list) {
+    if(current->value)
+           free(current->value);
     free(current);
    }

    free(l);
}

> After some testing, I found that the above code did not free every memory blocks allocated, which resulted in the following error:

$ ./qtest
cmd> new
l = []
cmd> ih test
l = [test]
cmd> free
l = NULL
ERROR: There is no queue, but 1 blocks are still allocated
cmd> quit
Freeing queue
ERROR: Freed queue, but 1 blocks are still allocated

>I have modified the code above to also free any memory blocks allocated to `value` variables, which fixed the error.

### q_insert_head() and q_insert_tail()

:::danger
Address your motivations and considerations here.
:::

This operation

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;

    element_t *new_node_element = (element_t *) malloc(sizeof(element_t));
    if (!new_node_element)
        return false;

    new_node_element->value = malloc(strlen(s) + 1);
    strncpy(new_node_element->value, s, strlen(s) + 1);
    if (!new_node_element->value) {
        free(new_node_element);
        return false;
    }
    list_add(&new_node_element->list, head);
    return true;
}

bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head)
        return false;

    element_t *new_node_tail = (element_t *) malloc(sizeof(element_t));
    new_node_tail->value = malloc(strlen(s) + 1);
    strncpy(new_node_tail->value, s, strlen(s) + 1);
    if (!new_node_tail){
    	free(new_node_tail);
    	return false;
    }
    
    list_add_tail(&new_node_tail->list, head);
    return true;
}

### q_remove_head and q_remove_tail

:::danger
Address your motivations and considerations here.
:::

 if (!head || list_empty(head))
        return NULL;

    element_t *temp = list_first_entry(head, element_t, list);

    if (sp && temp) {
        strncpy(sp, temp->value, bufsize);
        sp[bufsize - 1] = '\0';
    }

    list_del(&temp->list);
    return temp;

if (!head || list_empty(head))
        return NULL;

    element_t *temp = list_last_entry(head, element_t, list);
    if (temp && sp) {
        strncpy(sp, temp->value, bufsize);
        sp[bufsize - 1] = '\0';
    }

    list_del(&temp->list);
    return temp;

### q_size

:::danger
Address your motivations and considerations here.
:::

if (!head)
        return 0;
    int len = 0;
    struct list_head *count;
    list_for_each (count, head)
        len++;
    return len;

### q_delete_mid

:::danger
Address your motivations and considerations here.
:::

if (!head || list_empty(head))
        return false;  // if queue is empty or NULL

    struct list_head *slow = head->next, *fast = head->next->next;
    // check queue until the very last entry
    // using Tortoise and Hare algo
    while (fast != head && fast->next != head) {
        slow = slow->next;
        fast = fast->next->next;
    }

    element_t *middle_node = list_entry(slow, element_t, list);
    list_del(slow);
    free(middle_node->value);
    free(middle_node);
    return true;

### q_swap

### q_ascend

### q_descend

### q_reverse

### q_reverseK