---
tags: linux2022
---

# 2022q1 Homework1 (lab0)
contributed by < `ngokchaoho` >

# Experiment Environment

$ gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0

$ lscpu
Architecture:                    x86_64
CPU op-mode(s):                  32-bit, 64-bit
Byte Order:                      Little Endian
Address sizes:                   43 bits physical, 48 bits virtual
CPU(s):                          6
On-line CPU(s) list:             0-5
Thread(s) per core:              1
Core(s) per socket:              6
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       AuthenticAMD
CPU family:                      23
Model:                           113
Model name:                      AMD Ryzen 5 3500 6-Core Processor
Stepping:                        0
Frequency boost:                 enabled
CPU MHz:                         2199.644
CPU max MHz:                     4120.3120
CPU min MHz:                     2200.0000
BogoMIPS:                        7199.97
Virtualization:                  AMD-V
L1d cache:                       192 KiB
L1i cache:                       192 KiB
L2 cache:                        3 MiB
L3 cache:                        16 MiB
NUMA node0 CPU(s):               0-5

## Assignment Requirement
* `q_new` : Create new empty queue
* `q_free` : Release memory occupied by queue
* `q_insert_head` : Insert new node to queue head following LIFO
* `q_insert_tail` : Insert new node to queue tail following FIFO
* `q_remove_head` : Remove element from head of queue
* `q_release_element` : Release memory used by specific node
* `q_size` : Count number of node in the queue
* `q_delete_mid` : Remove the middle node of the queue [LeetCode 2095. Delete the Middle Node of a Linked List](https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/)
* `q_delete_dup` : Remove duplicated nodes in osrted queue [LeetCode 82. Remove Duplicates from Sorted List II](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/)
* `q_swap` : Swap adjacent nodes in the queue [LeetCode 24. Swap Nodes in Pairs](https://leetcode.com/problems/swap-nodes-in-pairs/)
* `q_reverse` : Reverse elements in queue; this function should not allocate or free any list elements
* `q_sort` : Sort elements of queue in ascending order

## Development

### q_new
- allocate memory for `struct list_head` in `queue.h`
- - if succeeded, use exisiting method `INIT_LIST_HEAD` to initialize the doubly-linked list (pointing its next and prev to itself).
- - return pointer to the queue which could be NULL if malloc failed.

/*
 * Create empty queue.
 * Return NULL if could not allocate space.
 */
struct list_head *q_new()
{
    struct list_head *q = malloc(sizeof(struct list_head));
    if (q != NULL) {
        INIT_LIST_HEAD(q);
    }
    return q;
}

### q_free
> this method is inspired from laneser
- if the head is NULL then nothing to do
- otherwise remove the element (whose type is element_t) and release the memory of this element
- Note that an empty list still have a `struct list-head` object as shown below, which needs to be free.

/* Free all storage used by queue */
void q_free(struct list_head *l)
{
    if (!l)
        return;
    while (list_empty(l) == false) {
        element_t *n = q_remove_head(l, NULL, 0);
        // failed to remove? stop it or it might lead to dead loop.
        if (n == NULL)
            return;
        q_release_element(n);
    }
    // release memory used by empty list, which is a struct head object 
    free(l);
}

> taken from [你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)