2019q1 Homework1 (lab0)

contributed by < york56 >

tags: System-Software-2019 GUTS

Preparation

Installation of Lubuntu 18.04

Done. Yet to documentate the installation process.

Environment

$ uname -a # username, all
Linux york-X450JF 4.15.0-45-generic #48-Ubuntu SMP Tue Jan 29 16:28:13 UTC 2019 x86_64 x86_64 x86_64 GNU/Linux
$ gcc --version
gcc (Ubuntu 7.3.0-27ubuntu1~18.04) 7.3.0

git, github(ssh key), commit message format

Done. Done. Done.

TODO: installation of input method for Mandarin

TODO: WiFi driver and Bluetooth driver

Study Linked lists

https://people.engr.ncsu.edu/efg/210/s99/Notes/LinkedList.1.html

• linked list
  a list consisting of items in which each item knows the location of the next item.

• node(element)
  an item in a linked list. Each node contains a piece of list data and the location of the next node (item).

• link
  (of a node) the location of the next node.

• head node
  first node in a linked list

• head pointer

• points to the head node

• The last node has a reference to null.

  • null meams: adj.無效的；無價值的；【數】零的 / n.【數】零 / vt.使無效

Try to read queue.h

I can't understand this:

/* Linked list element (You shouldn't need to change this) */
typedef struct ELE {
    /* Pointer to array holding string.
       This array needs to be explicitly allocated and freed */
    char *value;
    struct ELE *next;
} list_ele_t;

/* Queue structure */
typedef struct {
    list_ele_t *head; /* Linked list of elements */
                      /*
                        You will need to add more fields to this structure
                       to efficiently implement q_size and q_insert_tail
                      */
} queue_t;

Try to understand type struct

Now I understood the it by this.
[C,C++] typedef struct 用法說明 - 李山姆的部落格 - 痞客邦

Try to understand char *value

Now I understood the it by this.
C語言: 超好懂的指標，初學者請進～

Try to understand 【This array needs to be explicitly allocated and freed】

Allocateed

Being in a status where the memory for the datum is prepared.

Being freed?

??? ??? ??? ??? ???

Try to interpret the fist few lines of queue.h

/* This is a node/element inside a linked-list. */
struct ELE{
    char *value;               // Delare a pointer variable call 'value', which points to sth belonging to type-char
    struct ELE *next;          // Delare a pointer variable call 'next', which points to sth belonging to ELE, a type-struct thing defined by us
                               // It points toward the next element, not this node itself!!!
};
typedef struct ELE list_ele_t; // Define the struct (called ELE) as a kind of type called "list_ele_t"

/* A queue is a linked-list containing elements. */
typedef struct {
    list_ele_t *head; // head is a pointer pointing to sth belonging to list_ele_t
} queue_t;

Why not use list_ele_t instead of struct ELE

, since we have already typedefined it, resulting

typedef struct ELE {
    char *value;
    list_ele_t *next;
} list_ele_t;

.

Why there is no need to write:

typedef struct some_kind_of_name {
    bla bla bla
} queue_t;

in the second part, but has the need to writ:

typedef struct ELE {
    bla bla bla
} list_ele_t;

in the first part.

Try to complete the declare of queue structure

According to Prof. Jserv, it is

typedef struct {
    list_ele_t *head; // the head pointer
    list_ele_t *tail; // the tail pointer
    int size;
} queue_t;

.
I can't understand it.
I thought a queue is something like:

.
So it should be something like:

typedef struct {
    list_ele_t{}; // as head
    list_ele_t{}  // as body
    .
    .
    .
    list_ele_t{}; // as body
    list_ele_t{}; // as tail
    int size;
} queue_t;

, but after reading
https://www.interviewbit.com/courses/programming/topics/linked-lists/

I realize we merely have to hold two pointers in hands (one pointing to the beginning element and the other to the ending element), letting every element floating elsewhere.

Also it seems like we have to calculate the size of the queue in advance and store it.

How to get the nth node?

If the queue_t data only has head pointer, tail pointer, and queue size, how to get the nth element?
Count along the queue?

Try to complete the function q_new

It seems like

queue_t *q_new();

is enough to the task

Create empty queue.
Return NULL if could not allocate space.

, but I don't know why.
QwQ QwQ QwQ

I interpret the code as:

define a pointer q_new pointing toward something of type-queue_t.

I thought we should declare a queue_t variable and let the pointer inside point to a null.

queue_t an_empty_queue{
    list_ele_t *head = &null;
    list_ele_t *tail = &null;
    int size = 0;
}

Don't know how to let a pointer point to a null

Try to complete the function q_free

void q_free(queue_t *q) is enough??

Try to complete q_insert_head

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.

I have no idea.
I refer to < DyclexiaS >. https://hackmd.io/s/Byjnik5F7

The conditions causing failures include:

1. No queue, which means q (a pointer) is NULL.
   (??? Can an element have a NULL info part and a not-NULL link part?)
2. No new element.
3. ???

bool q_insert_head(queue_t *q, char *s)
{
    if (q == NULL)
        return false;
    list_ele_t *newh;
    
    /* What should you do if the q is NULL? */
    newh = malloc(sizeof(list_ele_t));
    if (newh == NULL)
        return false;
    
    /* Don't forget to allocate space for the string and copy it */
    /* What if either call to malloc returns NULL? */
    newh->value = strdup(s);
    if (newh->value == NULL) {
        free(newh);
        return false;
    }
    if (q->head == NULL)
        q->tail = newh;
    newh->next = q->head;
    q->head = newh;                                                   
    ++q->q_size;
    return true;
}

What is the 8th line newh = malloc(sizeof(list_ele_t))

去開記憶體，開給 list_ele_t 這種 datatype。然後把開出來的記憶體的address指派給newh
我不懂的的是我以為list_ele_t的大小是固定的，為什麼要一直重算？
去要記憶體，如果發生newh == NULL，也就是要不到，就回傳false。

typedef struct ELE {
     char *value;
     struct ELE *next;
 } list_ele_t;

而且我以為list_ele_t的宣告不論怎樣都會被執行，newh有機會是NULL嗎？

sizeof()

This operator gives the byte size of the inputted operator.
https://www.geeksforgeeks.org/sizeof-operator-c/

malloc()

The C library function void *malloc(size_t size) allocates the requested memory and returns a pointer to it.
https://en.cppreference.com/w/c/memory/malloc

動態配置

https://openhome.cc/Gossip/CGossip/MallocFree.html

allocate space for the string and copy it

/* Don't forget to allocate space for the string and copy it */
/* What if either call to malloc returns NULL? */

newh->value = strdup(s); // value是個pointer // char *value 
if (newh->value == NULL){
    free(newh); 
    return false; 
}
if (q->head == NULL)
    q->tail = newh;
    
newh->next = q->head;
q->head = newh;                                                   
++q->q_size;
return true;

再造一個 pointer ( 其指向 s 這個 pointer 指向的 char )
並 assign 給 value (其為 newh 這個 pointer 指向的 struct 裡面的 pointer )，
但這個 assigning 也有可能失敗。(會什麼會失敗啊???)
失敗了的話就把 newh 清掉然後回傳 false 。

->

http://squall.cs.ntou.edu.tw/cprog/content/12 struct and other datatypes_bw.pdf

char * strdup(const char *str1);

Returns a pointer to a null-terminated byte string, which is a duplicate of the string pointed to by str1. The returned pointer must be passed to free to avoid a memory leak.

char * strdup(const char *str1);的輸入如果是NULL會發生什麼？

a null-terminated byte string

In computer programming, a null-terminated string is a character string stored as an array containing the characters and terminated with a null character.
https://en.wikipedia.org/wiki/Null-terminated_string

什麼是 Memory Leak ?

???

void free( void* ptr );

Deallocates the space previously allocated by malloc(), calloc(), aligned_alloc, (since C11) or realloc().
If ptr is a null pointer, the function does nothing.

null pointer ???

???

檢查完各種例外，真的要把新的頭放進去了喔

但如果放之前是空的，頭尾都要這個指向新加進去的元素。

if (q->head == NULL)
    q->tail = newh;

如上，假如 head 裡面沒東西(所以是空的 queue )就讓 把 newh 指派給 tail 。然後等一下把 newh 也指派給 head ，這樣頭尾都指向同一個 element ，所以就從空的長大成有一個元素的，合理。

無論 head 是不是 NULL 我們都要做以下。

newh->next = q->head;
    q->head = newh;                                                   
    ++q->q_size;
    return true;

讓 newh 的 next 指向 原本的第一個 element ，也就是
把 q 裡面的 head 指派給 newh (我們要加進去的 element 的 pointer ) 的 next 。
我們都是靠 q 來知道頭尾在哪裡的，讓 q 的 head 指向整顆 newh 。
把 q 裡面的 q_size 加一。

這樣我們應該就完成了。

但是回頭一看 我又不懂了

為什麼以下是分兩步

    list_ele_t *newh;
    newh = malloc(sizeof(list_ele_t));

不是一步

    list_ele_t *newh;
    newh = malloc(sizeof(list_ele_t));