Try   HackMD

2018q3 Homework1

contributed by < ofAlpaca >

tags: CSIE5006 HW

為什麼要深入學習 C 語言？

為什麼不探討 C++

  • C 與 C++ 已經漸行漸遠，已經可以當成是兩種不同的語言。
  • C++ 改版速度神速。
  • 當初 C 語言的目的就是為了撰寫 UNIX。
  • 第一個C編譯器怎麼來 ?
    • 先使用組合語言編寫一個 C 的子集編譯器，再透過子集語言去編寫較難一點的 C 語言子集編譯器，一步一步堆疊成完整的 C 語言編譯器。
    • 由於最簡單功能的 C 語言子集編譯器可以直接用組合語言寫出來，所以不用編譯。
    • C0 -> C1 -> C2-> . . . -> CN -> 完整的 C 語言，可以看成像這樣一步一步疊上去完成第一個 C 語言編譯器。

ISO/IEC 9899

  • object : 在執行環境下有資料儲存空間，其內容可以表示值。

    C99 [3.14] Region of data storage in the execution environment, the contents of which can represent values.

  • & 在非 bitwise operator 時，應念 "address of" ，表示運算元的位址。

    C99 [6.5.3.2] The unary & operator yields the address of its operand.

  • * 應念成 "value of" 或是 "dereference of" ，* 的運算元應該要是 pointer type，表示運算元所指向的值。

    C99 [6.5.3.2] The operand of the unary * operator shall have pointer type.

  • char * 與 void * 是可以互換的。

    C99 [6.2.5.27] A pointer to void shall have the same representation and alignment requirements as a pointer to a character type.

你所不知道的 C 語言：指標篇

C 語言規格書

  • Incomplete type : 已宣告但未給予記憶體空間的 type ，因尚未有空間，故非 object type。

    C99[6.2.5] Types are partitioned into object types (types that fully describe objects), function types (types that describe functions), and incomplete types (types that describe objects but lack information needed to determine their sizes).

    • 型別可分為三， object type 、 function type 、 incomplete type 。



struct Strt ;
struct Strt x ; // incomplete type
char y[]; // incomplete type
  • Incomplete type 可以宣告為 pointer type 但不可存取其記憶體空間。
  • pointer 的大小取決於架構的 address 。
  • Array, function, pointer 都是 derived declarator type 。

void * 之謎

  • void * (pointer to void) 無法確定其大小。
  • 對指標進行加減運算(source)












#include <stdio.h>

int main() {
  int intvar = 1;
  int intarr[] = {1,2,3,4,5};
  printf("address of intvar = %p\n", (void *)(&intvar));
  printf("address of intvar - 1 = %p\n",(&intvar - 1));
  printf("address of intvar + 1 = %p\n", (void *)(&intvar + 1));

  printf("address of intarr[0] = %p\n", (void *)(&intarr));
  printf("address of intarr[1] = %p\n", (void *)(&intarr + 1));
}
  • 從結果可以得知，每次加減1的單位是以前面指標的型別來決定的。如果前是 int 則單位是 4 bytes，如果前面是 array of int ，則單位是 4 * 5 = 20 bytes，並非 4 bytes 。






$ ./test
address of intvar = 0x7fff2a78552c
address of intvar - 1 = 0x7fff2a785528
address of intvar + 1 = 0x7fff2a785530
address of intarr[0] = 0x7fff2a785510
address of intarr[1] = 0x7fff2a785524
  • void * 與 char * 可以互換表示法。
  • 存在這種用法 *(int32_t * const) (0x67a9) = 0xaa6;

Pointer to a pointer

  • C語言只有call-by-value !
  • ptrA 不會被改變到的原因是參數 p 只是個副本，而改變副本的值並不會影響到 ptrA 。









int B = 2;
void func(int *p) { p = &B; }
int main() {
    int A = 1, C = 3;
    int *ptrA = &A;
    func(ptrA);
    printf("%d\n", *ptrA); // print 1
    return 0;
}
  • 如果不使用「指標的指標」來改變傳入的變數， memcpy() 也是個方法。











int B = 2;
void func(int * p) {
    memcpy(p,&B,sizeof(B));
}
int main() {
    int A = 1, C = 3;
    int *ptrA = &A;
    func(ptrA);
    printf("%d\n", *ptrA); // print 2
    return 0;
}

Pointers vs. Arrays

  1. C語言中沒有真正陣列/矩陣，只有 array subscripting!
  2. extern char x[] 無法轉為 pointer。
    註:extern意思是指此變數會在其他地方被定義
  3. char x[10] 不能轉為 pointer ，但 char x[] 可以，因為它不是 object 而是 incomplete type 。
  4. func(char x[])會被轉為func(char *x) ，但僅限於函式的參數， array argument 是不存在於C語言的。
  5. In expression, array 與 pointer 可以互換。



int a[3];
*a = 5; // a[0] = 5
*(a+1) = 5; // a[1] = 5
  1. x[i] 會被編譯器改寫為 *(x + i) ， x[i] == (*((x)+(i))) 。
  2. x[i] 、 *(x + i) 、 *(i + x) 、 i[x] 這四者是等價的。
  3. int x[i][j] 意思是 x 是有 i 個 object 的陣列，每個 object 都是有 j 個 int 的陣列。此作法稱為 array subscripting。
  4. char * newargv[]; 的結構如下，提醒自己用:
    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 →
    • char* s[] 與 char **s 是相同的。
    • 要注意的是 char *s[] 與 char (*s)[] 是不同的，前者是 an array of pointer to char ，後者是 a pointer to an array 。 (根據 C99 [A.2.1] ， [] 是優先於 * )
  5. int *ptr, value; ptr 為 pointer to int ， value 為 int ，此手法容易搞混，不宜使用。
  6. 使用 ptr + 1 時，每次 +1 的單位取決於 ptr 的 type 。
    ex. pointer to int (4 bytes)、pointer to array of int(4 * i bytes)
  7. 可以透過 pointer 來改變存取記憶體的方式。
double : 0x00000000 0x3ff00000 // double 長度為 8 bytes ， 但 int 長度為 4 bytes。
(int *): 0x00000000            // 轉型後只能取到前 4 bytes
  1. 變數宣告的順序不等於記憶體中的順序。
  2. char *r = malloc(strlen(s) + strlen(t) + 1); 最後的+1為NULL的空間。
  3. memcpy() 、 malloc() 並不會自動配上最後的 terminated null byte ，在處理 char * 時要記得自己保留空間。
  4. strdup() 會使用 malloc() 配置足夠的記憶體空間來存放字串，也包含了最後的 terminated null byte ('\0')。

Function pointer

  • *(uint32 * const) (0x601020) = 0x601080 左手邊是 Lvalue，指的是 locator value ，並非 left 。

  • Lvalue 是指除了 void 型別以外，有著 object type 或 incomplete type 的表達式。ex. obj , *ptr , ptr[i] , and ++x。

    C99 [6.3.2.1] An lvalue is an expression with an object type or an incomplete type other than void;

  • 有著回傳型別的 function designator 會被轉為 pointer to returning type 。 ex. int test(); 會被轉為 pointer to function return int ， 型別為 int (*)() 。就像陣列這兩者互換的關係，char a[] 與 char * a。

    C99 [6.3.2.1] A function designator with type ‘‘function returning type’’ is converted to an expression that has type ‘‘pointer to function returning type’’.

  • 若在 pointer to function 使用 deference operator(*) ， 則會被轉為 function designator 。

  • 此程式碼可以運作的原因是 put() 是個 function designator ，而 function designator 會被轉成 pointer to function ，在經過數次的 dereference 後仍然是 function designator，所以不影響結果。

int main() { return (********puts)("Hello"); }
  • char *s="Hello world" 此為string literal，和 char s[]="Hello world" 不同，前者存於read-only data section ，後者則是 stack 的 local variable。
    • func1() 中 p 指向的 Hellow 是存於 static storage 裡，故 return 後 Hellow 還在 static storage 中；但是 func2() 中的 p 指向的 Hellow 是存於 stack 裡， return 後的 Hellow 已經不在 stack 中了。














char* func1(){ 
    char *p = "Hellow";
    return p;
}
char* func2(){ 
    char p[] = "Hellow";
    return p;
}
int main() 
{ 
    printf("%s\n",func1()); // print Hellow
    printf("%s\n",func2()); // NULL
    return 0; 
}
  • strlen() 不能接受 null pointer ，會造成未定義的行為。
  • Compound Literal initialization :



struct S {int a, b;};
struct S x = {1,2};
struct S y = {2,1};

Null pointer

  • NULL 是使用 MACRO 定義的空指標常數( null pointer constant ):
    #define NULL ((void *)0) // 一般C編譯器常見的寫法




#define **offsetof**(st, m) **((size_t)&(((st *)0)->m))**
#define container_of(ptr, type, member) ({ \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member) );})
  • offset : st 代表的是 struct type ，((st *)0)->m 意思是將 0 轉型為 pointer to st ，並指向 m 這個 member 的位址。在此獲得相對位置。
  • container_of : mptr 是 member 的 pointer to type ，並 assign 為 ptr 。記憶體中的絕對位址 - 相對位址，可以得到原 struct 的起始位址。
  • typeof : 和 sizeof 一樣都是 operator ，用於回傳資料的型別，但 typeof 是 gcc 的 extension。

你所不知道的 C 語言：函式呼叫篇

Nested function

  • C 語言不支援 nested function，其目的為簡化編譯器設計。







void f() {
  // declaration of function g
  void g();
  g();
  // once exit the function, function g() 
  // is out of scope.
}

Process 和 C 程式的關聯

  • Memeory 架構 : (source)
  • Stack : 由高位址長至低位址，儲存函式呼叫時個別 stack frame 的 local variables 與 return address 等。
  • Heap : 由低位址長至高位址，動態記憶體配置。
  • BSS segement: Block Started by Symbol ，尚未初始化的變數。
  • Data segement : 已經被初始化後的變數。
  • Text segement : 存放使用者程式的 binary code 。

Object File

  • File Format :
    • 每個 OS 所使用的 object 檔格式不盡相同， Linux 使用的是 ELF (Executable and Linkable Format)，Windows 使用的是 PE (Portable Executable)。
    • 可用於紀錄 executable file、object file、share object、core dump。
    • .o 檔 (object file) 是介於 compiling 和 linking 的檔案，經過編譯但還未連結為可執行檔。
  • MMU(memory management unit) : 負責處理 CPU 對記憶體的存取請求，例如虛擬位址到實體位址的轉換。
  • File Content :
    1. .text section : 程式碼的部分。
    2. .data section : 宣告並且有賦值的變數。
    3. .bss section : 只有宣告，尚未初始化的變數。
  • Compilation and Linking
    • 原始 .c 檔與 .h 檔經過編譯成為 .object 檔，最後再與其他 .object 檔或是 static lib 進行 linking 產生 .out 。
  • Symbol
    • Symbol name 包含 function name 、 variable name。
    • 每個 .object 檔都有個 symbol table ，存放 symbol value 。

Static linking

  • Methods :
    1. Accumulate : 所有 section 依序排放在一起。
    2. Merge similar section : 根據 .text 、 .data 、 .bss section 同類的放在一起。
  • .a 檔 : object 檔的彙集，可以透過 linker 來與其他 object 檔做連結，ex. libc.a 。

Dynamic linking

  • .so 檔 : 為 Dynamic Shared Objects ， dynamic loader 會在程式的執行期間讀入 .so 檔至記憶體，並做 relocation 。
  • 較省空間，(.so file in linux)，當需要使用到其他的 lib 時才會 load 進 memory 。
  • Program1 與 Program2 在執行期間才動態連結 dynamic shared lib 。

Parameter vs Argument

  • 兩者為形式上的不同，但都可稱為參數
  • formal parameter 為型別與符號 ex. int x 。
  • actual argument 為數值 ex. 5 。

reference: C 程式語言 page 4-5

Stack

  • 包含了 parameter 、 local variable 、 return address 等。
  • rbp 與 rsp 都是 x86 架構的暫存器。
  • rbp (frame pointer) : 指向目前 stack frame 的起始位址。
  • rsp (stack pointer) : 指向目前 stack frame 的末端位址，會隨著 stack 增長而增加。
  • return address : 當目前的 stack frame 結束後要回去的位址。
  1. Call function，push return address 到 Stack (給 instruction pointer使用) 。
  2. Function prologue :
    a. 先 PUSH 目前 rbp 的位址。
    b. 將 rsp 複製至 rbp 。(兩者指向目前 stack frame 的起點)
    c. rsp 開始往下移動(由高位址往低位址)，保留空間給 local variables 。
  3. Function epilogue :
    a. 將目前 rbp 複製至 rsp ，之前的 local variables 也被釋放了。(兩者指向目前 stack frame 的起點)
    b. Pop 上個 rbp 的位址，讓目前的 rbp 回復成上個 stack frame 的 rbp 。
    c. Pop return address 讓 instruction pointer 指向 call function 後的下道指令。

Heap

  • free() 為釋放 pointer 所指向之記憶體空間，非 pointer 本身。
  • free() 後 pointer 不會在指向任何記憶體，如果再次 free() 就會產生 error。
  • 釋放後可將 pointer 指向 NULL，防止二次釋放。

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 →

[ Homework ] 為什麼 glibc 可以偵測出上述程式的 "double free or corruption" 呢？如何去管理

  • source : [ glibc/malloc/malloc.c] #line 344 (https://github.com/lattera/glibc/blob/master/malloc/malloc.c) 可以下關鍵字 _int_free 來看 glibc 是如何實作 free() 。
  • 講解 glibc 如何偵測 double free 前，需要先解釋幾個名詞 :
    • struct malloc_chunk : 一個 doubly linked list 的資料結構的節點，每個節點除了雙向指標外，還存有目前節點大小與前節點大小。
    • fastbins : 是個存有最近釋放掉的 malloc_chunk 的 single linked list。
    • mchunkptr : 是一個 pointer to malloc_chunk。
  • 解釋 : 當一個 pointer 被 free() 時，會先透過 mem2chunk 來找到其對應的 mchunkptr ， 接著會去 fastbins 裡比對 mchunkptr 所指向的位址是否已經存在，有則表示之前此位址已經被 free() 過了，故產生 "double free or corruption" 的 error message 。

這裡有個有趣的點，你可以嘗試看看 free 兩個 fastbin 大小的 chunk，順序：A, B, A，看看會發生什麼事
HexRabbit

memory allocator 內部實作可參照春季班課程報告: rpmalloc 探討

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

你所不知道的 C 語言：遞迴呼叫篇

遞迴種類

  • Direct recursion : 最基本的




int A() {
    ...
    A();
}
  • Indirect recursion : 要注意 calling cycle












int A(); // forward declaration
int B();

int A() {
    ...
    B(); // 
}

int B() {
    ...
    A();
}
  • Tail recursion : 尾端遞迴，函式最後執行的遞迴呼叫，且只有遞迴呼叫，不能再做其他事。
    • 尾端遞迴可以省去多餘的 stack frame。
    • 不增加新的 stack frame ，直接更新函式 argument ，此作法可稱為 Tail Call Optimization ， TCO ，尾端呼叫最佳化。

Tail recursion 實驗 ： 查看有尾端遞迴與沒尾端遞迴的差別。 (reference)











// tail_rec.c with tail recursion
int sum(int n, int total) {
    if (n == 0)
        return total;
    else
        return sum(n - 1, total + n);
}
int main() {
    sum(100,0);
}

要做 Tail Call Optimization 需要在編譯時期加上 -O2 參數來最佳化。

$ gcc tail_rec.c -o tail_rec_op -O2
$ gcc tail_rec.c -o tail_rec

接下來使用指令 objdump -d 來觀察兩者之間組語的差別。

  • 沒尾端最佳化 (0x400501)
00000000004004d6 <sum>:
  4004d6:	55                   	push   %rbp
  4004d7:	48 89 e5             	mov    %rsp,%rbp
  4004da:	48 83 ec 10          	sub    $0x10,%rsp
  4004de:	89 7d fc             	mov    %edi,-0x4(%rbp)
  4004e1:	89 75 f8             	mov    %esi,-0x8(%rbp)
  4004e4:	83 7d fc 00          	cmpl   $0x0,-0x4(%rbp)
  4004e8:	75 05                	jne    4004ef <sum+0x19>
  4004ea:	8b 45 f8             	mov    -0x8(%rbp),%eax
  4004ed:	eb 17                	jmp    400506 <sum+0x30>
  4004ef:	8b 55 f8             	mov    -0x8(%rbp),%edx
  4004f2:	8b 45 fc             	mov    -0x4(%rbp),%eax
  4004f5:	01 c2                	add    %eax,%edx
  4004f7:	8b 45 fc             	mov    -0x4(%rbp),%eax
  4004fa:	83 e8 01             	sub    $0x1,%eax
  4004fd:	89 d6                	mov    %edx,%esi
  4004ff:	89 c7                	mov    %eax,%edi
  400501:	e8 d0 ff ff ff       	callq  4004d6 <sum>
  400506:	c9                   	leaveq 
  400507:	c3                   	retq
  • 有尾端最佳化 (0x400505)
00000000004004f0 <sum>:
  4004f0:	85 ff                	test   %edi,%edi
  4004f2:	89 f0                	mov    %esi,%eax
  4004f4:	74 11                	je     400507 <sum+0x17>
  4004f6:	66 2e 0f 1f 84 00 00 	nopw   %cs:0x0(%rax,%rax,1)
  4004fd:	00 00 00 
  400500:	01 f8                	add    %edi,%eax
  400502:	83 ef 01             	sub    $0x1,%edi
  400505:	75 f9                	jne    400500 <sum+0x10>
  400507:	f3 c3                	repz retq 
  400509:	0f 1f 80 00 00 00 00 	nopl   0x0(%rax)
  • 最明顯的差別就在於前者使用 call 而後者使用 jne 。
  • 就組語來看，前者使用函式呼叫，所以會產生新的 stack frame ; 後者使用 jne 來跳至前面的位址 (0x400500)，並沒有額外呼叫函式，所以不會產生 stack frame ，進而達到 TCO　。

Logical operator

  • && 是左值優先，若左值不成立，右值就不會執行。
  • || 是左值優先，若左值成立，右值就不執行。

find

  • FILE * fopen(...) 的 pointer to FILE 為對檔案處理的抽象層，會隨著架構有所不同，為系統提供的包裝。 DIR * opendir(...) 也是同樣的道理。

你所不知道的 C 語言：前置處理器應用篇

Preprocessor

  • preprocessor 會處理的部分 :

    1. Macros ， ex #define
    2. File inclusion ， ex #include <stdio.h>
    3. Conditional compilation ， ex #if 、 #ifdef
    4. Miscellaneous directives ， ex #undef 、 #pragma

  • Stringfication : # 可以將 macro 的參數轉為字串常數。

  • Concatenation : ## 用於連接字串。

    • ex. #define CMD(NAME) {#NAME, NAME##_command}

  • Feature test macro : 就算同個 source code ，還是有可能因為 posix macro 定義不同而有不同的行為。

  • 編譯時使用 gcc -E -P 可以得到 preprocessor 的輸出結果。








#define stringify(x) #x
#define concat(x,y) x##y

int main(void){
    printf(stringify(a));
    int concat(new, var);
}
  • 測試編譯時加上 -E -P 參數，可以看到被 macro 取代掉的部分。
$ gcc -E -P  t.c
int main(void){
    printf("a");
    int newvar;
}

C11

  • _Generic : 可以從輸入的型別來決定要跑哪個函式的 macro。
#define cbrt(X) _Generic((X), 
                    default: cbrt,
                    const float: cbrtf,
                    float: cbrtf)
                (X)
  • gcc 4.9 之後才支援 _Generic ，否則會出現以下 error message 。(source)
$ gcc -std=c11 b.c
b.c: In function ‘main’:
b.c:4:31: error: expected expression before ‘default’ 
 #define cbrt(X) _Generic((X), default: cbrt, const float: cbrtf, float: cbrtf)(X)
 
$ gcc -v
gcc version 4.8.3 20140911 (Red Hat 4.8.3-7) (GCC)

應用

  • Metaclass : 產生模板的模板
  • Mockclass(from google mock) :
  • Macro 適用於 code generator ，善用 macro 可以有效降低 function call 成本，進而增加程式效率。
  • typeof 為 gcc extension 的 macro。
  • 練習 macro 最好的方法就是找 code 來用。
  • introsort 為 unstable sorting ，因為他是 quick sort + merge sort。
  • setjump 不可以跨越 stack ，但可跨 thread。

你所不知道的 C 語言：goto 和流程控制

MISRA C

  • 一種 C 語言的規範與要求
  • 規範不可用 goto 與 continue 。
  • 雖然 MISRA-C:2004 認為 goto 、 continute 、 multiple returns 能不使用就不使用，但是在 MISRA-C:2011 的草稿中卻說到，只要是往下 jump 不往上，就沒問題。(source)

GOTO

  • 可讓程式碼更易讀。
  • GOTO 可以有效的利用在 Error handling ，又稱「下水道風格」。





























int foo(int bar)
{
    int return_value = 0;

    allocate_resources_1();

    if (!do_something(bar))
        goto error_1;

    allocate_resources_2();

    if (!init_stuff(bar))
        goto error_2;

    allocate_resources_3();

    if (!prepare_stuff(bar))
        goto error_3;

    return_value = do_the_thing(bar);

error_3:
    cleanup_3();
error_2:
    cleanup_2();
error_1:
    cleanup_1();
    return return_value;
}

Switch-case (reference)

  • Computed goto (Labels as values): 
    ​​​​void *ptr = &&foo;
​​​​static void *array[] = { &&foo, &&bar, &&hack };
​​​​/* ... */
​​​​goto *ptr;
​​​​goto *array[i];
​​​​/* ... */
​​​​foo : // foo, the lable 
​​​​/* ... */
    • && 為 GCC extension 的特殊 operator，回傳的位址以 void * 。
    • label 必須被定義在目前的 scope 。
    • goto 後面加上 value of pointer 即得到 label 。
  • switch 之內的 switch statement (case 、 default) 都應該在同個 scope 下。

    C99 [6.8.4.2] If a switch statement has an associated case or default label within the scope of an identifier with a variably modified type, the entire switch statement shall be within the scope of that identifier.

    • line 3 與 line 5 宣告的 i 在同個 scope 下，故在編譯時期會有 redeclaration of ‘i’ with no linkage 的 error 。
    







    ​​​​switch (expr) {
​​​​    case 0: ;
​​​​        int i;
​​​​    case 1: ;
​​​​        int i;
​​​​    default:;
​​​​        break;
​​​​}

RAII

  • Resource Acquisition Is Initialisation ，是種物件導向的編程，意思是當有資源被「配置」或者「釋放」時，能夠自動初始化與釋放，透過使用 destructor 來達到資源自動管理。
  • switch-case 為 goto 之變形。
  • switch-case 的 case 只要是在同個 function scope 就可以跳得到，不會因為 if-else 而被繞過，label 也是一樣。
  • 使用 preprocessor #if 0 ... #endif 才會完全隔絕，因為已經被前置處理掉了。

Duff's device

  • 為一種 switch-case 的技巧，可以提高執行效率。
  • 範例 : (source)









int nn ;
switch(nn % 4) {
    for(; nn > 0; nn -= 4) {
        case 0:	*destp++ = *srcp++;
        case 3:	*destp++ = *srcp++;
        case 2:	*destp++ = *srcp++;
        case 1:	*destp++ = *srcp++;
    }
}
  1. 假設 nn = 7 ，當 7 mod 4 為 3 ，進入 case 3 。
  2. 接下來從 case 3 一路執行 case 2 、 case 1 至 for 迴圈的最後， nn -= 4 後判斷 nn (目前為 3) 大於 0 ，故繼續執行迴圈。
  3. 從頭到尾跑一次迴圈， 在 nn -= 4 後判斷 nn (值為 -1) 小於 0 ，故結束迴圈。
  • 就此不難發現，若按照正常想法寫 for 迴圈來跑，需要跑 7 次，但使用 Duff's device 技巧來寫，只需要 2 次，效率有差。

你所不知道的 C 語言：linked list 和非連續記憶體操作

  • Linus 的有品味版 delete singly-linked list 剛開始不好懂，了解後會大吃一驚。其核心概念就是， head 與 next 是一樣的，只要更新指向 target 的 pointer 就好。(下面有我嘗試的圖解)











void remove_list_node(List *list, Node *target)
{
    // The "indirect" pointer points to the *address*
    // of the thing we'll update.
    Node **indirect = &list->head;
    // Walk the list, looking for the thing that 
    // points to the node we want to remove.
    while (*indirect != target)
        indirect = &(*indirect)->next;
    *indirect = target->next;
}

  1. 一開始， indirect 指向的是 head 的位址。
  2. 假設是要刪除 node B ，經過迴圈後，新的 indirect 會指向目前節點的 next 的位址。
  3. 回到迴圈的判斷式，發現 dereference of indirect (也就是 A->next) 等於 target 故跳出迴圈。
  4. 最後再將 dereference of indirect 指向 target->next ，完成刪除 node B 。
  • 許多的 project 都對應的 framework ，不局限於程式語言本身，ex. Qt 、 GTK 、linux kernel。

Circular linked list

  • list_for_each 的缺點是如果在跑 pos 時將該節點刪除，將會導致後面的 pos = pos->next 出現錯誤； list_for_each_safe 則多出 n pointer 來保存下個節點的指標，就此避免了上述的問題。
#define list_for_each(pos, head) \
	for (pos = (head)->next; pos != (head); pos = pos->next)

#define list_for_each_safe(pos, n, head) \
	for (pos = (head)->next, n = pos->next; pos != (head); \
		pos = n, n = pos->next)

你所不知道的 C 語言：技巧篇

從矩陣操作談起

  • Designated Initializers :
    • 詳細使用見 C99 [6.7.8] 後面的 Example 。
    • 範例 :
    ​​​​// decalartion
​​​​struct point { int x, y; };
​​​​// initialization
​​​​struct point p = { .y = yvalue, .x = xvalue };
​​​​struct point p = { xvalue, yvalue }; // Compound literal style
  • 善用建立 instance 時的 Compound Literals for Structure Assignment 。
  • 在 initializer 裡的 expression 只能是 const expression. (source)
    • 範例 :
    ​​​​struct {char *p} s = {malloc(256)}; // error
​​​​struct {int x, y} w = {100, 200}; // no problem

    C99 [6.7.8] All the expressions in an initializer for an object that has static storage duration shall be constant expressions or string literals.

追蹤物件配置的記憶體

  • strdup 會呼叫 malloc 來動態配置足夠的記憶體，存於 [HEAP] ，需要手動 free 來釋放資源；但是 strdupa 則是使用 alloca 來配置記憶體，並存於 [STACK] ， STACK 會自動釋放資源。

    函式名稱 呼叫 存放位置 釋放資源
    strdup malloc Heap 手動 free
    strdupa alloca Stack 自動 free

  • alloca() 意思是配置會自動釋放的記憶體。

Gcc extension : attribute

  • __attribute__ 為 GCC extension 的定義函數屬性，可以讓編譯器在編譯時做些特殊處理或是檢查動作。
  • 可分為 Function attribute 、 Variable attribute 、 Type attribute 。
  • Smart pointer 即是利用 variable attribute 來實作。
  • Smart pointer implement :
    • macro autofree 就是個 variable attribute 。
    • 下面的 __attribute__ ((always_inline)) 則是 function attribute 。
    • inline (行內函式) 意思是將此 function 的內容整合至呼叫此函式的位置。
    ​​​​#define autofree \
​​​​    __attribute__((cleanup(free_stack)))
​​​​
​​​​__attribute__ ((always_inline))
​​​​inline void free_stack(void *ptr) { free(*(void **) ptr); }

​​​​int main(void) {
​​​​    autofree int *i = malloc(sizeof (int));
​​​​    *i = 1;
​​​​    return *i;
​​​​}
Last changed by 
 
ofAlpaca
KoNoDogeDa https://github.com/ofAlpaca http://wiki.csie.ncku.edu.tw/User/ofAlpaca
0
1310
Published on HackMD