# 你所不知道的c語言
contributed by <[plusline](https://github.com/plusline)>

:::danger
你的提問呢？回顧你過去開發的程式，難道沒想到概念上有衝突或者激發出更多想法嗎？
:notes: jserv
:::
:::info
只要是宣告為指標，不論型態(int、float或是 struct)，空間裡應該都是存放一個位置，既然都是存放位置，為甚麼要在宣告為指標的時候區別型態?
:::
## 指標篇

- function pointer
定義：A function pointer, also called a subroutine pointer or procedure pointer, is a pointer that points to a function.

之前只有在C++的 sort function 看過

//qsort for c
void qsort (void* base, size_t num, size_t size,
            int (*compar)(const void*,const void*));

#### 練習：
##### 程式碼

#include <stdio.h>

void function_point(){
    printf("call function_point\n");
    return;
}

int main(){
    printf("enter main\n");
    int (*ptr)()=function_point;

    printf("ptr:%p\n",&ptr);
    printf("function_point:%p\n",&ptr);

    ptr();

    return 0;
}

##### 結果

enter main
ptr:0x7ffc3f3c81c0
function_point:0x7ffc3f3c81c0
call function_point

##### 討論
ptr 和 function_point 能呼叫同一個函式且位置相同。

---

##### 問題
- 該如何解釋 qsort(3) 的參數和設計考量呢？
qsort 的第三個參數是 funtion pointer ，目的是為了實踐不一樣的排列方式，通常在比較字串時我們會用 Alphabetical order，直接從字串首開始比較 ascii code 的大小，不過像我們作業系統中資料夾的排序，則是使用接近 Natural sort order 的方式排序。
- 為何我看到的程式碼往往寫成 `struct list **lpp;
for(lpp = &list; *lpp != NULL; lpp = &(*lpp)->next)` 呢？
宣告的時候要用指標的指標才能讓傳入函式之後的操作能夠確實的改動 link list。後面的複雜難懂的操作是為了配合宣告。

#### 練習1：
- 程式碼

#include <stdio.h>
#include <stdlib.h>

struct node{
        int data;
        struct node *next;
};
void go_through(struct node **list){
        struct node **lpp;

        for(lpp = list; *lpp != NULL; lpp = &(*lpp)->next){
                printf("data:%d\n",(*lpp)->data);
        }
}
int main(){
        struct node a,b,c;
        struct node *head=&a;
        a.data=12;
        a.next=&b;
        b.data=30;
        b.next=&c;
        c.data=64;
        c.next=NULL;

        go_through(&head);


        return 0;
}

##### 結果

data:12
data:30
data:64

##### 討論
我對於指標的指標的掌握度不高，幾乎是用 trial and error 的方式做出來了，我想應該是吃了太多 C++ 語法糖的緣故。
我之後再嘗試插入節點，這樣才看得出指標的指標的強大，不然只是要遍歷所有節點好像沒有使用的必要。

#### 練習2：

##### 程式碼

#include <stdio.h>
#include <stdlib.h>

struct node{
        int data;
        struct node *next;
        struct node *prev
};
void go_through(struct node *list){
        struct node **lpp;

        for(lpp = &list; *lpp != NULL; lpp = &(*lpp)->next){
                printf("data:%d\n",(*lpp)->data);
        }
}

void insert(struct node **n, int data){
        struct node *ptr;
        ptr=malloc(sizeof(struct node));

        ptr->data=data;
        ptr->next=(*n)->next;
        ptr->prev=*n;

        (*n)->next->prev=ptr;

        (*n)->next=ptr;

}
void insert2(struct node *n, int data){
        struct node *ptr;
        ptr=malloc(sizeof(struct node));

        ptr->data=data;
        ptr->next=n->next;
        ptr->prev=n;

        n->next->prev=ptr;
        n->next=ptr;
}

void dele(struct node **n){
        (*n)->prev->next=(*n)->next;
        (*n)->next->prev=(*n)->prev;
        *n=(*n)->next;
}
void dele2(struct node *n){
        n->prev->next=n->next;
        n->next->prev=n->prev;
        n=n->next;

}
void dele3(struct node n){
        (n).prev->next=(n).next;
        (n).next->prev=(n).prev;
}


int main(){
        struct node a,b,c;
        struct node *head=&a;
        a.data=12;
        a.prev=NULL;
        a.next=&b;

        b.data=30;
        b.next=&c;
        b.prev=&a;

        c.data=64;
        c.prev=&b;
        c.next=NULL;

        struct node *ptr=&b;
        printf("ptr:%p\n",ptr);
        insert(&ptr,99);
        printf("ptr insert 99:%p\n",ptr);
        insert(&ptr,66);
        printf("ptr insert 66:%p\n",ptr);
        insert2(ptr,88);
        printf("ptr insert2 88:%p\n",ptr);
        dele(&ptr);
        printf("ptr dele: %p\n",ptr);
        dele2(ptr);
        printf("ptr dele2: %p\n",ptr);
        dele3(*ptr);
        printf("ptr dele3: %p\n",ptr);
        go_through(head);


        return 0;
}

##### 結果

ptr:0x7ffed72b3be0
ptr insert 99:0x7ffed72b3be0
ptr insert 66:0x7ffed72b3be0
ptr insert2 88:0x7ffed72b3be0
ptr dele: 0x560e16e756b0
ptr dele2: 0x560e16e756b0
ptr dele3: 0x560e16e756b0
data:12
data:66
data:99
data:64

#####　討論
函式 dele3　傳入的只是該節點的副本，在子函數中操作完之後，並不能實際影響到 main　的實際結構。

本來 stuct 在函式間傳遞就是用位址，因此只需要用一個*就能作到指標的指標的效果，在函式dele中，我用了**顯的多此一舉。

---
- lvalue and rvalue:
> An lvalue refers to an object that persists beyond a single expression.
> An rvalue is a temporary value that does not persist beyond the expression that uses it. ---[MSDA](https://msdn.microsoft.com/en-us/library/f90831hc.aspx)

lvalue 和　rvalue　的區別是生命週期的長短，lvalue　有一個生命週期長的位置，在賦值完仍持續存在。如：

    int a;
    a=3;

在第二行執行完後 a　仍存在，3則消滅了。

---
- forward declaration
>a forward declaration is a declaration of an identifier (denoting an entity such as a type, a variable, a constant, or a function) for which the programmer has not yet given a complete definition. ---[wiki: forward declaration](https://en.wikipedia.org/wiki/Forward_declaration)

在具體定義之前先宣告，已達到函式的封閉性，也增加日後修改的彈性和可讀性。

---
##### 如何在指標中隱藏數據？
在系統中數據會有最小單位，因此所有的記憶空間為了要配合最小單位，而將地址化分成最小單位的整數倍。
假設那個最小單位為4bits，那定址的時候所有的地址將會是以00結尾。
因此我們可以在其中偷偷藏進一些資訊。像是linux kernel　的rb-tree，就在紀錄父結點的位置的最低有效位放進自己的顏色。

struct rb_node {
	unsigned long  __rb_parent_color;
	struct rb_node *rb_right;
	struct rb_node *rb_left;
} __attribute__((aligned(sizeof(long))));

[linux/rbtree.h](https://github.com/torvalds/linux/blob/6f0d349d922ba44e4348a17a78ea51b7135965b1/include/linux/rbtree.h)

在 rbtree.h 裡，有定義rb_node的結構，其中有一個unsigned long的變數，用來保存父節點和自己的顏色。

#define	RB_RED		0
#define	RB_BLACK	1

[rbtree_augmented.h](https://github.com/torvalds/linux/blob/6f0d349d922ba44e4348a17a78ea51b7135965b1/tools/include/linux/rbtree_augmented.h)

static inline void rb_set_black(struct rb_node *rb)
{
	rb->__rb_parent_color |= RB_BLACK;
}

[linux/lib/rbtree.c](https://github.com/torvalds/linux/blob/master/lib/rbtree.c)

RB_RED只有最低位為1，而父節點的位置最兩位永遠為0，所以在讀取之前，可以借用最低一位儲存顏色。

:::danger
從其他地方複製內容時，應該要附上出處。另外，需要將用語改為繁體中文和台灣地區科技術語。
RB tree 要附上 Linux 核心程式碼，再來討論
:notes: jserv
:::