2023q1 Homework1 (lab0)

contributed by < EdwardCKC >

開發環境

gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0

$ lscpu
Architecture:          x86_64
CPU op-mode(s):        32-bit, 64-bit
Address sizes:         39 bits physical, 48 bits virtual
Byte Order:            Little Endian
CPU(s):                12
On-line CPU(s) list:   0-11
Vendor ID:             GenuineIntel
Model name:            12th Gen Intel(R) Core(TM) i5-12400
CPU family:            6
Model:                 151
Thread(s) per core:    2
Core(s) per socket:    6
Socket(s):             1
Stepping:              2
CPU max MHz:           5600.0000
CPU min MHz:           800.0000
BogoMIPS:              4992.00
Virtualization:        VT-x
L1d:                   288 KiB (6 instances)
L1i:                   192 KiB (6 instances)
L2:                    7.5 MiB (6 instances)
L3:                    18 MiB (1 instance)   
NUMA node0 CPU(s):     0-11

開發過程

說好的進度呢？

jserv

q_insert_head & q_insert_tail

一開始如下:
malloc 的 + 1 是要補 \0 在 string 的尾端 ，不然會有 overflow 的問題

{
    if (!head || !s)
        return false;

    element_t *new_node = malloc(sizeof(element_t));

    if (!new_node)
        return false;

    new_node->value = (char *) malloc(sizeof(char) * strlen(s) + 1);

    if (!new_node->value) {
        free(new_node);
        return false;
    }

    strncpy(new_node->value, s, strlen(s) + 1);
    list_add(&new_node->list, head);
    free(s);
    return true;
}

之後發現 free() 不能釋放不是malloc() / calloc() 的記憶體空間

改進漢語表達。

jserv

cmd> ih 1
ERROR: Attempted to free unallocated block.  Address = 0x55e0a6498020
ERROR: Attempted to free unallocated or corrupted block.  Address = 0x55e0a6498020
ERROR: Corruption detected in block with address 0x55e0a6498020 when attempting to free it
l = [1]

為了加強自己對指標的了解，把 element_t *value 和 *s 印了出來

cmd> ih 1

-------- ptr value 

&new_node->value: 0x563781585000 
new_node->value: 0x563781585050 
*new_node->value: 85 

-------- ptr s 

&s: 0x7ffda928e478 
s: 0x563781585ba0 
*s: 49 

-------- after strncpy

-------- ptr value 

&new_node->value: 0x563781585000 
new_node->value: 0x563781585050 
*new_node->value: 49 

-------- ptr s 

&s: 0x7ffda928e478 
s: 0x563781585ba0 
*s: 49 
l = [1]

-----------------------------

cmd> ih 1

-------- ptr value 

&new_node->value: 0x5637815850b0 
new_node->value: 0x563781585100 
*new_node->value: 85 

-------- ptr s 

&s: 0x7ffda928e478 
s: 0x563781584f30 
*s: 49 

-------- after strncpy

-------- ptr value 

&new_node->value: 0x5637815850b0 
new_node->value: 0x563781585100 
*new_node->value: 49 

-------- ptr s 

&s: 0x7ffda928e478 
s: 0x563781584f30 
*s: 49 
l = [1 1]

結果發現:
我錯誤以為 strncopy() 是在複製 pointer s 指向數值的地址去 pointer value，所以根本不用 free(s) / s=NULL 去節省記憶體空間或防止更改 s 會改到 value 的值

C99 7.21.2.4 The strncpy function

Description
The strncpy function copies not more than n characters (characters that follow a null character are not copied) from the array pointed to by s2 to the array pointed to by s1.

If copying takes place between objects that overlap, the behavior is undefined.

If the array pointed to by s2 is a string that is shorter than n characters, null characters are appended to the copy in the array pointed to by s1, until n characters in all have been written.

NAME
       strcpy, strncpy - copy a string

SYNOPSIS
       #include <string.h>

       char *strcpy(char *dest, const char *src);

       char *strncpy(char *dest, const char *src, size_t n);

DESCRIPTION
       The  strcpy()  function  copies the string pointed to by src, including
       the terminating null byte ('\0'), to the buffer  pointed  to  by  dest.
       The  strings  may  not overlap, and the destination string dest must be
       large enough to receive the copy.  Beware  of  buffer  overruns!   (See
       BUGS.)

       The  strncpy()  function is similar, except that at most n bytes of src
       are copied.  Warning: If there is no null byte among the first n  bytes
       of src, the string placed in dest will not be null-terminated.

       If  the  length of src is less than n, strncpy() writes additional null
       bytes to dest to ensure that a total of n bytes are written.

       A simple implementation of strncpy() might be:

           char *
           strncpy(char *dest, const char *src, size_t n)
           {
               size_t i;

               for (i = 0; i < n && src[i] != '\0'; i++)
                   dest[i] = src[i];
               for ( ; i < n; i++)
                   dest[i] = '\0';

               return dest;
           }

從 C99 7.21.2.4 The strncpy function 和 man page 可以得知 strncpy 最後要 +1 的原因

列出 C 語言規格書和 man page 相關描述，向第一手材料學習。

jserv

q_remove & q_remove_tail

remove 只是去掉 node 跟 list 的連結，所以需要 char *sp 去暫存

寫的時侯在list_del 跟 list_del_init 之間在選擇，最後選了 list_del 因為在 if 已經有考慮到 list is empty 的問題，但還是會想會不會像 sql injection 一樣使一個 empty list 可以 by pass 這個條件式，也可能只是因為我還是沒有很懂 C 跟記憶體之間的關係，所以之後還是會去找找看list_del_init 的應用情景

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

    element_t *f_node = list_first_entry(head, element_t, list);
    list_del(&f_node->list);

q_delete_mid

因為這次是 delete 也就是說需要釋放記憶體空間，所以最後會用 q_release_element

原本這樣寫想要節省記憶體空間

q_release_element(list_entry(trv_backward, element_t, list);

最後改成下面，因為這樣可讀性比較高

element_t *middle = list_entry(trv_backward, element_t, list);
q_release_element(middle);

q_reverse

一開始我是用 list_for_each_safe 作為 loop ，然後把每個 node 移到 head

list_for_each_safe(node, tmp, head) {
​   list_move(node, head);
}

然後發現第一個node的移動是多餘的
所以改成

list_for_each_safe(node, tmp, head) {
    list_move_tail(node, head);
}

但出現以下error

cmd> reverse
ERROR: Time limit exceeded.  Either you are in an infinite loop, or your code is too inefficient

看了 list_move_tail 的 code，發現會 infinite loop

static inline void list_move_tail(struct list_head *list, struct list_head *head)
{
    __list_del_entry(list);
    list_add_tail(list, head);
}

再改成逆序，原本也預期跟上面一樣是 infinite loop

list_for_each_prev_safe(node, tmp, head) {
    list_move(node, head);
}

但在編譯時出現以下 error

  CC	queue.o
queue.c: In function ‘q_reverse’:
queue.c:179:5: error: implicit declaration of function ‘list_for_each_prev_safe’ did you mean ‘list_for_each_safe’? [-Werror=implicit-function-declaration]
  179 |     list_for_each_prev_safe(node, tmp, head); {
      |     ^~~~~~~~~~~~~~~~~~~~~~~
      |     list_for_each_safe
queue.c:179:45: error: expected ‘;’ before ‘{’ token
  179 |     list_for_each_prev_safe(node, tmp, head) {
      |                                             ^~
      |                                             ;
queue.c:179:5: error: ‘node’ may be used uninitialized [-Werror=maybe-uninitialized]
  179 |     list_for_each_prev_safe(node, tmp, head); {
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
queue.c:179:5: error: ‘tmp’ may be used uninitialized [-Werror=maybe-uninitialized]
cc1: all warnings being treated as errors
make: *** [Makefile:54: queue.o] Error 1

q_sort

q_delete_dup