2022q1 Homework1 (lab0)

contributed by < Shawn5141 >

Homework Requirement

Quiz1 Answer and Discussion

2022q1-quiz1

Function Requirement

queue_new:

Create a new, empty queue. Because it's empty queue, initilize empty list will suffice the requirement here.

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

struct list_head *q_new()
{
    struct list_head *l = malloc(sizeof(struct list_head));
    if (l == NULL)
        return NULL;
    INIT_LIST_HEAD(l);    
    return &l;
}

After allocating queue memory (element_t), use linux/list.h macro INIT_LIST_HEAD to initialize list_head member element.

Time complexity:
Space complexity:

queue_free:

Free all storage used by a queue.

Use list_for_each_safe to iterate through queue and call list_del to remove list entry. Comparison for list_for_each vs list_for_each_safe. If there is char array in element_t, those memory also need bo be freed. After char array is cleaned, element would be freed entirely.
















 /* Free all storage used by queue */
void q_free(struct list_head *l) {
    if (!l)
        return;
    if (list_empty(l)){
        free(l);
        return;
    }
    element_t* element, *n;
    list_for_each_entry_safe(element, n, l, list) {
        if (element->value)
           free(element->value);
        free(element);
	}
    free(l);
}

Time complexity:
Space complexity:

queue_insert_head

Attempt to insert a new element at the head of the queue (LIFO discipline).

Allocate memory for element_t and char array through self-defined function q_ele_new (described latter).
Use linux list_add macr to add newly allocated element's list_head to head of list.

/*
 * Attempt to insert element at head of queue.
 * Return true if successful.
 * Return false if q is NULL or could not allocate space.
 * Argument s points to the string to be stored.
 * The function must explicitly allocate space and copy the string into it.
 */
bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *ele = NULL;
    if (!q_ele_new(&ele, s)) {
        return false;
    }
    list_add(&(ele->list), head);
    return true;
}

Time complexity:
Space complexity:

queue_insert_tail

Attempt to insert a new element at the tail of the queue (FIFO discipline).
1. Allocate memory for element_t and char array through self-defined function q_ele_new (described latter).
2. Use linux list_add_tail macr to add newly allocated element's list_head to end of list.

/*
 * Attempt to insert element at tail of queue.
 * Return true if successful.
 * Return false if q is NULL or could not allocate space.
 * Argument s points to the string to be stored.
 * The function must explicitly allocate space and copy the string into it.
 */
bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *ele = NULL;
    if (!q_ele_new(&ele, s)) {
        return false;
    }
    list_add_tail(&(ele->list), head);
    return true;
}

Time complexity:
Space complexity:

q_remove_head

Refering to self-defined function __q_remove. By providing pointer to first list_head element. It would

Retrieve first element using list_entry.
Utilize list_del to remove first element's list_head without delete it.

/*
 * Attempt to remove element from head of queue.
 * Return target element.
 * Return NULL if queue is NULL or empty.
 * If sp is non-NULL and an element is removed, copy the removed string to *sp
 * (up to a maximum of bufsize-1 characters, plus a null terminator.)
 *
 * NOTE: "remove" is different from "delete"
 * The space used by the list element and the string should not be freed.
 * The only thing "remove" need to do is unlink it.
 *
 * REF:
 * https://english.stackexchange.com/questions/52508/difference-between-delete-and-remove
 */
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head)
        return NULL;
    return __q_remove(head->next, sp, bufsize);
}

q_remove_tail

Refering to self-defined function __q_remove. By providing pointer to last list_head element. It would

Retrieve last element using list_entry.
Utilize list_del to remove first element's list_head without deleting it.

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head)
        return NULL;
    return __q_remove(head->prev, sp, bufsize);
}

q_delete_mid

Use slow-fast pointer technique to find out middle point (Refers to helper function __q_ele_mid)

/*
 * Delete the middle node in list.
 * The middle node of a linked list of size n is the
 * ⌊n / 2⌋th node from the start using 0-based indexing.
 * If there're six element, the third member should be return.
 * Return NULL if list is NULL or empty.
 */
bool q_delete_mid(struct list_head *head)
{
    // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
    element_t *element = __q_ele_mid(head);
    if (element == NULL)
        return NULL;

    list_del_init(&element->list);
    q_release_element(element);
    return true;
}

q_delete_dup

Initilize left and right pointer.

Proceed to while loop when both left and right value are same

Assign right pointer to tmp pointer
Move right pointer to it's next
Delete right pointer

If dup_flag is on, delete left pointer

Move right pointer to it's next and terminate while loop when right pointer is point to head

On the other hand, if there is no duplicate element in sorted list, the left pointer and right pointer will just continue proceed to next til right pointer point to head.

/*
 * Version 2
 * Delete all nodes that have duplicate string,
 * leaving only distinct strings from the original list.
 * Return true if successful.
 * Return false if list is NULL.
 *
 * Note: this function always be called after sorting, in other words,
 * list is guaranteed to be sorted in ascending order.
 */
bool q_delete_dup(struct list_head *head)
{
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
    if (!head || list_empty(head))
        return false;
    if (list_is_singular(head))
        return true;
    // Use two pointer to iterate through list
    struct list_head *left = head->next;
    struct list_head *right = head->next->next;
    bool dup_flag = false;
    while (1) {
        // If left value is equal to right value, entering inner while loop
        while (right != head &&
               !strcmp(
                   // cppcheck-suppress nullPointer
                   list_entry(left, element_t, list)->value,
                   // cppcheck-suppress nullPointer
                   list_entry(right, element_t, list)->value)) {
            list_del(left);
            // cppcheck-suppress nullPointer
            q_release_element(list_entry(left, element_t, list));
            left = right;
            right = right->next;
            dup_flag = true;
        }
        if (dup_flag) {
            dup_flag = false;
            list_del(left);
            // cppcheck-suppress nullPointer
            q_release_element(list_entry(left, element_t, list));
        }

        if (right == head)
            break;
        left = right;
        right = right->next;
    }

    return true;
}

Shorten the above code snip by effective techniques.

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

Verson2:
Still require dup_flag. But release left pointer instead of right one. Need to come up with more effective techniques latter.

q_swap

Move node in front of fack node and proceed node two step further

/*
 * Attempt to 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) || list_is_singular(head))
        return;

    for (struct list_head *node = head->next->next;
         node != head && node != head->next; node = node->next->next->next) {
        // Move node in front of fack node and proceed node two step further
        struct list_head *fake_head = node->prev->prev;
        list_move(node, fake_head);
    }
}

q_reverse

Create prev_node and next_node pointer pointing to head.

Create curr_node pointer pointing to next list_head in list.

Iterate through list while curr_node is not equal to head

Assign next_node as next list_head of curr_node.

Make curr_node pointing it's next pointer to prev_node.

Make prev_node point it's prev pointer to curr_node.
Let head point it's next to curr_node while point curr_node's prev to head. So that the cycle is closed.

Make head eqaul to prev_node.

/*
 * Reverse elements in queue
 * No effect if q is NULL or empty
 * This function should not allocate or free any list elements
 * (e.g., by calling q_insert_head, q_insert_tail, or q_remove_head).
 * It should rearrange the existing ones.
 */
void q_reverse(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return ;

    struct list_head *prev_node = head;
    struct list_head *next_node = head;
    struct list_head *curr_node = prev_node->next;

    prev_node->prev = prev_node;
    prev_node->next = prev_node;

    while (curr_node != head) {
        next_node = curr_node->next;
        curr_node->next = prev_node;
        prev_node->prev = curr_node;

        head->next = curr_node;
        curr_node->prev = head;
        prev_node = curr_node;
        curr_node = next_node;
    }
    head = prev_node;
}

q_sort

Developing about iterative merge sort:

Problem:

How to intialize pointer to list_head array with default value of empty head.
Unable to figure out how to do merge circular sorted list. So decide to turn circular list into normal linked list and convert it back after sorting.





























/*
 * Sort elements of queue in ascending order
 * No effect if q is NULL or empty. In addition, if q has only one
 * element, do nothing.
 */
void q_sort(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;

    struct list_head *node = head->next, *ptr;

    // Make it not cicular
    head->prev->next = NULL;
    head->next = NULL;

    node = __mergesort(node);

    // Make sure every list's prev and next is pointing to right place
    ptr = head;
    ptr->next = node;
    while (ptr->next) {
        ptr->next->prev = ptr;
        ptr = ptr->next;
    }
    // Connect last node'next to head and head's prev to ndoe
    ptr->next = head;
    head->prev = ptr;
}



















struct list_head *__mergesort(struct list_head *head)
{
    if (!head->next)
        return head;

    struct list_head *fast = head, *slow = head, *mid;
    while (true) {
        if (!fast->next || !fast->next->next)
            break;
        fast = fast->next->next;
        slow = slow->next;
    }

    mid = slow->next;
    slow->next = NULL;

    struct list_head *left = __mergesort(head), *right = __mergesort(mid);
    return __merge_two_lists(left, right);
}





















/*
 * Merge to sorted linked list
 * Inspired by https://hackmd.io/@sysprog/c-linked-list
 */
struct list_head *__merge_two_lists(struct list_head *left,
                                    struct list_head *right)
{
    struct list_head *head = NULL, **ptr = &head, **node;

    for (node = NULL; left && right; *node = (*node)->next) {
        // cppcheck-suppress nullPointer
        char *val1 = list_entry(left, element_t, list)->value;
        // cppcheck-suppress nullPointer
        char *val2 = list_entry(right, element_t, list)->value;
        node = (strcmp(val1, val2) < 0) ? &left : &right;
        *ptr = *node;
        ptr = &(*ptr)->next;
    }
    *ptr = (struct list_head *) ((uintptr_t) left | (uintptr_t) right);
    return head;
}

Performance comparsion with linux/lib/list_sort.c

q_shuffle

Fisher–Yates shuffle

Pusedo code

-- To shuffle an array a of n elements (indices 0..n-1):
for i from n−1 downto 1 do
     j ← random integer such that 0 ≤ j ≤ i
     exchange a[j] and a[i]

This algorithm create true randomness given to the fact that the probablity of chosen number place to each position are same.

For example, if we randomly pick one position (let's say 3rd position) in array [0,1,2,3,4] to swap with the last position. The probablity is 1/5. And the array became [0,1,2,4,3]. Then in next round, as we choose from 1 to 3 (n-1), the probablity are still (4/5)*(1/4)=1/5 no matter which position we choose to swap the last element with.

Add command to qtest

I found this macro ADD_COMMAND added 3 weeks ago and this is align with this article Preprocessor operators.

#define ADD_COMMAND(cmd, msg) add_cmd(#cmd, do_##cmd, msg)

Stringizing operator (#): 用來將引數變成一個字串
Charizing operator (#@): 用來將引數變成一個字元
Token-pasting operator (##): 用來拼接引數











#define MAKESTR(s) #s
#define MAKECHAR(x)  #@x
#define CONS(a,b) int(a##e##b)

int main()
{
    a = MAKECHAR(b);        // a = 'b';	
    b = MAKESTR(hello)      // b = "hello";
    c = CONS(2,3);          // c = 2e3;
    return 0;
}

Add shuffle using ADD_COMMAND


ADD_COMMAND(shuffle,
                "                | Shuffle list randomly");

I need to think about a way to declare q_shuffle function since I can't modify queue.h.

Swap function for any given two node.

__q_swap

Get l2 previous node (l2_prev) and remove l2 from list.
Replace l1 by l2.
Check if l1 used to be l2->prev. We can place l1 in next node of l2, so assign l2_prev as l2.
Use list_add to add l1 as next node of l2_prev.



















/*
 * swap any given two list_head. Inspired by linux/list.h
 */
void __q_swap(struct list_head *l1, struct list_head *l2)
{
    struct list_head *l2_prev= l2->prev;
    list_del(l2);

    //replace
    l2->next = l1->next;
	l2->next->prev = l2;
	l2->prev = l1->prev;
	l2->prev->next = l2;

    if (l2_prev == l1)
        l2_prev = l2;

    list_add(l1, l2_prev);
}

Create random in range

Since void srand( unsigned seed ) is called in qtest line 967, we don't need to repeatedly called it.

Seeds the pseudo-random number generator used by rand() with the value seed. Note: The pseudo-random number generator should only be seeded once, before any calls to rand(), and the start of the program. It should not be repeatedly seeded, or reseeded every time you wish to generate a new batch of pseudo-random numbers.
Call rand() function. Need to convert it into integer.
```
int num = (int)(rand()% i);
```

Use list_head pointer array to store pointer

Using array to store pointer can greatly reduce time for traversing.



    list_for_each(node, head) {
            node_array[cnt++] = node;
    }

Final solution

Create array pointer and store each pionter into it (line 11)
Apply Fisher–Yates algorithm and call __q_swap to swap two pointer's position in list.
swap chosen pointer in array with pointer in last array position.






















void q_shuffle(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;

    int size = q_size(head);
    struct list_head *node_array[size];
    struct list_head *node;
    int cnt = 0;
    list_for_each(node, head) {
        node_array[cnt++] = node;
    }

    struct list_head *tmp;
    for (int i = size - 1; i > 0; i--) {
        int num = (int)(rand()% i);
        __q_swap(node_array[num], node_array[size-1]);
        tmp = node_array[size-1];
        node_array[size-1] = node_array[num];
        node_array[num] = tmp;
    }
}

__q_ele_new

Allocate new node and let pointer to pointer to element_t point to newly allocated address of element_t with char array initilized.

/*
 * Self-defined function: Allocate new node and let pointer to pointer to element_t point to newly allocated address
 * of element_t with char array initilized.
 */
bool __q_ele_new(element_t **pptr_element, char*s) {
    *pptr_element = malloc(sizeof(element_t));
    if (*pptr_element == NULL) {
        free(*pptr_element);
        return false;
    }
    (*pptr_element)->value = malloc(sizeof(char) * (strlen(s) + 1));
    if ((*pptr_element)->value == NULL) {
        free(*pptr_element);
        return false;
    }
    // Initilize list_head
    INIT_LIST_HEAD(&(*pptr_element)->list);
    return true;
}

Time complexity:
Space complexity:

__q_ele_remove

Created generic __q_remove function called by q_remove_head and q_remove_tail. It would remove the element from list and copy out element char array to specifed buffer (sp) with given length (bufsize).

/*
 * Self-defined function to generailize q_remove_tail and q_remove_head
 */
element_t *__q_ele_remove(struct list_head *head, char *sp, size_t bufsize)
{
    if (head == NULL || list_empty(head))
        return NULL;
    list_del_init(head);
    // cppcheck-suppress nullPointer
    element_t *element = list_entry(head, element_t, list);
    if (sp != NULL) {
        strncpy(sp, element->value, (bufsize - 1));
        sp[bufsize - 1] = '\0';
    }
    return element;
}

Tool

AddressSanitizer

Feature
- 對堆、棧和全域性記憶體的訪問越界(堆緩衝區溢位，棧緩衝區溢位，和全域性緩衝區溢位)
- UAP(Use-after-free，懸掛指標的解引用，或者說野指標)
- Use-after-return(無效的棧上記憶體，執行時標記 ASAN_OPTIONS=detect_stack_use_after_return=1)
- Use-After-Scope (作用域外訪問，clang標記-fsanitize-address-use-after-scope)
- 記憶體的重複釋放 (double-free)
- 初始化順序的BUG
- 記憶體洩漏 (memory leak)

How to use:

Attach below command in CFLAGS

-fsanitize=address -fno-omit-frame-pointer -g

Example










    #include <iostream>

    int main(int argc, char** argv)
    {
    int a[5];
    int index=6;
    int retval=a[index];
    std::cout << "Ret :" << retval << std::endl;
    return retval;
    }

result:

==2696==ERROR: AddressSanitizer: stack-buffer-overflow on address 0x7ffd6eb424c8 at pc 0x56176dbc6fa8 bp 0x7ffd6eb42460 sp 0x7ffd6eb42450
READ of size 4 at 0x7ffd6eb424c8 thread T0
    #0 0x56176dbc6fa7 in main /home/shawn/tmp/test.cpp:6
    #1 0x7fe1fb98dbf6 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x21bf6)
    #2 0x56176dbc6e09 in _start (/home/shawn/tmp/test+0xe09)

Address 0x7ffd6eb424c8 is located in stack of thread T0 at offset 56 in frame
    #0 0x56176dbc6ed4 in main /home/shawn/tmp/test.cpp:3

  This frame has 1 object(s):
    [32, 52) 'a' <== Memory access at offset 56 overflows this variable
HINT: this may be a false positive if your program uses some custom stack unwind mechanism or swapcontext
      (longjmp and C++ exceptions *are* supported)
SUMMARY: AddressSanitizer: stack-buffer-overflow /home/shawn/tmp/test.cpp:6 in main
Shadow bytes around the buggy address:
  0x10002dd60440: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10002dd60450: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10002dd60460: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10002dd60470: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10002dd60480: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x10002dd60490: 00 00 f1 f1 f1 f1 00 00 04[f2]00 00 00 00 00 00
  0x10002dd604a0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10002dd604b0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10002dd604c0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10002dd604d0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10002dd604e0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
==2696==ABORTING