# C 練習(持續更新中)
###### tags: `c` `linux`
---
**實作平台: [WSL (Windows Subsystem for Linux)](https://docs.microsoft.com/zh-tw/windows/wsl/install-win10)**
**C版本:C99**
**IDE:VS Code/vim**
**編譯器: gcc**
## 從tmp.c到tmp.exe
經過compiler(編譯器)產生object file(目地檔.o) -> 再用linker(連結器)產生exe(執行檔)
## Hello World
```
#include <stdio.h> // <stdio.h>去/usr/include目錄尋找stdio.h
int main()
{
char str1[]="Hello World"; // C語言在strings" "最後會加'\0'
char *str2 ="Hello World";
printf("str1:%s\tstr2:%s\n",str1,str2);
printf("str1 add:%p\tstr2 add:%p\n",str1,str2);
printf("str1[0]:%p\tstr2[0]:%p\n",&str1[0],&str2[0]);
printf("str1[0]:%c\tstr2[0]:%c\n",str1[0],*str2);
printf("str1+1:%p\tstr2+1:%p\n",str1+1,str2+1);
printf("str1[0]:%c\tstr2[0]:%c\n",str1[1],*(str2+1));
printf("sizeof(str1):%ld\tsizeof(str2):%ld\n",sizeof(str1),sizeof(str2));
//return 0; <-- C99已經不用加return 0
}
```
```
str1:Hello World str2:Hello World
str1 add:0x7fffe7c41aec str2 add:0x7f8a70e00868
str1[0]:0x7fffe7c41aec str2[0]:0x7f8a70e00868
str1[0]:H str2[0]:H
str1+1:0x7fffe7c41aed str2+1:0x7f8a70e00869
str1[0]:e str2[0]:e
sizeof(str1):12(11+1) sizeof(str2):8(64位元os的指標大小)
```
---
## 超基礎排序
[C 語言排序演算法實作整理：泡沫排序、快速排序等](https://blog.gtwang.org/programming/c-sorting-algorithms-implementation/)
```
#include<stdio.h>
#include<stdlib.h>
static void swap(int *a, int *b){
int tmp = *a;
*a = *b;
*b = tmp;
}
static void bubble(int *data,int length){
for(int i = 0 ; i<length ; i++){
for(int n = 0 ; n < i ; n++){
if(data[n] > data[i]){
swap(&data[n],&data[i]);
}
}
}
}
int main(){
int arr1[] = {5,4,7,6,9,1,2,3};
int len = sizeof(arr1)/sizeof(arr1[0]);
bubble(arr1,len);
for(int i=0 ; i<len ; i++){
printf("%d ",arr1[i]);
}
return 0;
}
--------------------------------------------
1 2 3 4 5 6 7 9
```
```
#include<stdio.h>
#include<stdlib.h>
static void swap(int *a, int *b){
int tmp = *a;
*a = *b;
*b = tmp;
}
static void insertion(int *data, int length){
for(int i=1 ; i<length ; i++){
int j = i;
while(data[j]<data[j-1] && j>0){
swap(&data[j-1],&data[j]);
j--;
}
}
}
int main(){
int arr1[] = {5,7,4,9,6,1,3};
int len = sizeof(arr1) / sizeof(arr1[0]);
insertion(arr1,len);
for(int i=0 ; i <len ; i++){
printf("%d ",arr1[i]);
}
return 0;
}
```
---
## Bitwise
[C語言的 Bitwise operator(位元運算子)介紹, 包含圖解及範例](https://www.youtube.com/watch?v=10sJkpoFpv0&ab_channel=Yu_PengNie)
[Practice with bit operations](https://pconrad.github.io/old_pconrad_cs16/topics/bitOps/)這裡練習
### 顯示binary & set0 set1 toggle
```
a = a | 15 // 最右側 4 位設為 1，其餘不變。
a = a & (~15) // 最右側 4 位設為 0，其餘不變。
a = a ^ 15 // 最右側 4 位執行 NOT operator，其餘不變。
```
```
#include<stdio.h>
#include<stdlib.h>
static void binary_print(int a){
for(int i=31; i>=0 ;i--){
printf("%d",a>>i & 1);
}
printf("\t -> %d\n",a);
}
int main(){
int val = 45; //signed 00101101
binary_print(val);
binary_print(val>>1); //往右移 == /2
binary_print(val<<1); //往左移 == *2
int val2 = -45;
binary_print(val2);
binary_print(val2>>1);
binary_print(val2/2);
printf(" set the 5th bit from right to 1?\n");
binary_print(val);
int mask = 1<<4;
val|=mask;
binary_print(val);
printf("set the 3th bit from right to 0?\n");
mask = ~(1<<2);
val&=mask;
binary_print(val);
printf("toggle the 3th bit from right\n");
mask = 1<<2;
val^=mask;
binary_print(val);
return 0;
}
```
```
00000000000000000000000000101101 -> 45
00000000000000000000000000010110 -> 22
00000000000000000000000001011010 -> 90
11111111111111111111111111010011 -> -45
11111111111111111111111111101001 -> -23
11111111111111111111111111101010 -> -22
set the 5th bit from right to 1?
00000000000000000000000000101101 -> 45
00000000000000000000000000111101 -> 61
set the 3th bit from right to 0?
00000000000000000000000000111001 -> 57
toggle the 3th bit from right
00000000000000000000000000111101 -> 61
```
另一種顯示binary的寫法
```
#include<stdio.h>
#include<stdlib.h>
static void binary(int data){
for(int i= 31; i>=0 ;i--){
int b = data&(1<<i);
printf("%d",b>0? 1:0);
}
printf("\t -> %d\n",data);
}
int main(){
int a = 12;
binary(a);
return 0;
}
----------------------------------
00000000000000000000000000001100 -> 12
```
**兩種寫法不同在for迴圈裡的<< or >>**
[你所不知道的 C 語言: bitwise 操作](https://hackmd.io/@sysprog/c-bitwise)
左移: x << y : x 左移 y 位元，左移出的位元會被丟棄，右側會補上 0
右移: x >> y : x 右移 y 位元，右移出的位元會被丟棄。
```
這裡為了方便以16位元表示 a為12
第一種: a>>i & 1 第二種: a & (1<<i)
0000 0000 0000 0110 0000 0000 0000 1100
0000 0000 0000 0001 0000 0000 0000 1000
---------------------- ---------------------
0000 0000 0000 0000 0000 0000 0000 1000 =>2^3=>8
0000 0000 0000 0011 0000 0000 0000 1100
0000 0000 0000 0001 0000 0000 0000 0100
---------------------- ----------------------
0000 0000 0000 0001 =>2^0=>1 0000 0000 0000 0100 =>2^2=>4
0000 0000 0000 0001
0000 0000 0000 0001 =>2^0=>1
----------------------
0000 0000 0000 0001
可以正確顯示 因為會產生8與4，如果依序print
0000 0000 0000 1100 0000 0000 0000 8400 會產這樣的結果，
所以我加入 a>0? 1:0 產生1或0
```
### 位元內有幾個1
```
#include<stdio.h>
#include<stdlib.h>
int numbers_one(int data); // 無號整數裡位元 == 1的個數
int main(void){
int a = 0xff; //dec:255 bin:1111 1111
int b = 0xc87; //dec:3201 bin:1100 1000 0111
printf("%x\t位元1的個數:%d\n",a,numbers_one(a));
printf("%x\t位元1的個數:%d\n",b,numbers_one(b));
return 0;
}
int numbers_one(int data){
int count = 0;
for(int i =31 ; i>=0 ; i--){
//i=31 是因為32位元 編號0~31有32個
if(data&(1<<i)){
count++;
}
}
return count;
}
-----------------------------------------------
ff 位元1的個數:8
c87 位元1的個數:6
```
```
Leetcode 191. Number of 1 Bits
int hammingWeight(uint32_t n) {
int count = 0;
/* while(n>0){
count += n&1;
n=n>>1;
} */
for(int i=31 ; i>=0 ;i--){
if(n & (UINT32_C(1)<<i)){
count++;
}
}
return count;
}
```
### 取出第n個bit的值
```
#include<stdio.h>
#include<stdlib.h>
#include<math.h> //pow(double , double)
static int n_bit(int data, int n);
int main(void){
int a = 0xFA; // 1111 1010
int b = 0xC87; //1100 1000 0111
int n = 3;
printf("%x\t位元的第%d個位元:%d\n",a,n,n_bit(a,n));
n = 12;
printf("%x\t位元的第%d個位元:%d\n",b,n,n_bit(b,n));
return 0;
}
static int n_bit(int data, int n){
int tmp = pow(2,n-1); // 2^n-1
return (data & tmp)>>(n-1);
}
-------------------------------
gcc -g -Wall test2.c -lm -o test2
fa 位元的第3個位元:0
c87 位元的第12個位元:1
```
```
a = 15 取第4個bit
0001 1001 => 跟2^(4-1) AND
0000 1000
----------
0000 1000 => 再>>(4-1)
0000 0001 => 第4個bit為1
```
---
## Struct的初始化宣告(C99)
```
#include<stdio.h>
typedef struct people{
char *name;
int age;
char *job;
}PEOPLE;
int main(){
PEOPLE Peter={"Peter",18,"Student"};
printf("name:%s age:%d job:%s\n",Peter.name,Peter.age,Peter.job);
PEOPLE Kevin={.age=8, .job="no job", .name="Kevin"}; //可以不按照順序
printf("name:%s age:%d job:%s\n",Kevin.name,Kevin.age,Kevin.job);
PEOPLE *Peter_ptr=&Peter;
(*Peter_ptr).age=66;
Peter_ptr->job="Teacher";
printf("name:%s age:%d job:%s\n",Peter_ptr->name,Peter_ptr->age,Peter_ptr->job);
printf("name:%s age:%d job:%s\n",Peter.name,Peter.age,Peter.job); // 原本的資料已被更改
PEOPLE human[2]={{"Joe",55,"Dead"},
{"Allen",77,"dead"}};
printf("name:%s age:%d job:%s\n",human[1].name,human[1].age,human[1].job);
PEOPLE *human_ptr=human;
human_ptr[0].name="Amy";
printf("name:%s age:%d job:%s\n",human_ptr[0].name,human_ptr[0].age,human_ptr[0].job);
printf("name:%s age:%d job:%s\n",human_ptr->name,human_ptr->age,human_ptr->job);
}
```
```
name:Peter age:18 job:Student
name:Kevin age:8 job:no job
name:Peter age:66 job:Teacher
name:Peter age:66 job:Teacher
name:Allen age:77 job:dead
name:Amy age:55 job:Dead
name:Amy age:55 job:Dead
```
---
[C语言内存操作-19.结构体字节对齐](https://www.youtube.com/watch?v=p5OXx_16K0o&ab_channel=it%E6%8A%80%E6%9C%AF%E5%AD%A6%E9%99%A2) 講得很清楚 。
[Is sizeof for a struct equal to the sum of sizeof of each member?](https://www.geeksforgeeks.org/is-sizeof-for-a-struct-equal-to-the-sum-of-sizeof-of-each-member/)
```
#include<stdio.h>
#include<stdlib.h>
typedef struct people1{
char *name;
int age;
char *profession;
}PEOPLE_1;
typedef struct people2{
char name[5];
int age;
char profession[5];
}PEOPLE_2;
typedef struct data1{
int a;
char b;
short c;
}DATA_1;
typedef struct data2{
char b;
int a;
short c;
}DATA_2;
int main(){
printf("PEOPLE_1:%ld\n",sizeof(PEOPLE_1));
printf("PEOPLE_2:%ld\n",sizeof(PEOPLE_2));
printf("DATA_1:%ld\n",sizeof(DATA_1));
printf("DATA_2:%ld\n",sizeof(DATA_2));
return 0;
};0
```
```
PEOPLE_1:24
PEOPLE_2:20
DATA_1:8
DATA_2:12
```
## 指標
```
#include<stdio.h>
int main(void){
int c[3][2][2]={ {{2,5},{7,9}},{{3,4},{6,1}},{{0,8},{11,13}} };
printf("c:%p | *c:%p | c[0]:%p | &c[0][0]:%p \n",c,*c,c[0],&c[0][0]);
printf("c:%p | *c:%p | c[1]:%p | &c[0][1]:%p \n",c,*c,c[1],&c[0][1]);
printf("c:%p | *c:%p | c[2]:%p | &c[1][0]:%p \n",c,*c,c[2],&c[1][0]);
printf("\n");
printf("*(c[0][0]+1): %d | *(c[0][0]): %d \n",*(c[0][0]+1),*(c[0][0]));
printf("*(c[0][1]+1): %d | *(c[0][1]): %d \n",*(c[0][1]+1),*(c[0][1]));
printf("*(c[1][0]+1): %d | *(c[1][0]): %d \n",*(c[1][0]+1),*(c[1][0]));
printf("*(c[1][1]+1): %d | *(c[1][1]): %d \n",*(c[1][1]+1),*(c[1][1]));
printf("*(c[2][0]+1): %d | *(c[2][0]): %d \n",*(c[2][0]+1),*(c[2][0]));
printf("*(c[2][1]+1): %d | *(c[2][1]): %d \n",*(c[2][1]+1),*(c[2][1]));
printf("\n");
printf("*(c[0]+1): %p\n",*(c[0]+1));
return 0;
}
```
```
c:0x7fffc6417680 | *c:0x7fffc6417680 | c[0]:0x7fffc6417680 | &c[0][0]:0x7fffc6417680
c:0x7fffc6417680 | *c:0x7fffc6417680 | c[1]:0x7fffc6417690 | &c[0][1]:0x7fffc6417688
c:0x7fffc6417680 | *c:0x7fffc6417680 | c[2]:0x7fffc64176a0 | &c[1][0]:0x7fffc6417690
*(c[0][0]+1): 5 | *(c[0][0]): 2
*(c[0][1]+1): 9 | *(c[0][1]): 7
*(c[1][0]+1): 4 | *(c[1][0]): 3
*(c[1][1]+1): 1 | *(c[1][1]): 6
*(c[2][0]+1): 8 | *(c[2][0]): 0
*(c[2][1]+1): 13 | *(c[2][1]): 11
*(c[0]+1): 0x7fffc6417688
```
---
```
#include<stdio.h>
int main(){
int arr[]={1,2,3,4,5,6};
int *p = arr;
*(p++)+=100; // p++ => 先取p再+1
*(++p)+=100; // ++p => 先+p再取值
for(int i=0 ;i <6;i++){
printf("%d ",arr[i]);
}
}
output: 101 2 103 4 5 6
```
---
---
## 變數範圍
C語言有3種變數範圍 **須注意variable的lifetime**
1. Global variable(全域變數)
2. Local variable(區域變數)
3. Block variable(區塊變數)
static:
* **對其他.c檔隱藏變數/函式名稱，只能在宣告它的檔案中使用。(最重要的功能)**
* static變數內容的lifetime，不會因為離開區域變數而結束。
* static變數，如果沒設定預設值為0。
extern:
* 聲明變數會在其他的位置被定義，可能是在同一份檔案中，或是在其他檔案裡。
## 常用<string.h>的函式
**在Linux系統下，有關於標準函式庫的使用，都可以command `man xxx`，會出現該函式的資料。**
或是這裡查詢[Linux man pages online](https://man7.org/linux/man-pages/index.html)。
---
* strlen - calculate the length of a string
* size_t strlen(const char *s);
* The strlen() function calculates the length of the string pointed to by s, excluding the terminating null byte ('\0').
* The strlen() function returns the number of characters in the string pointed to by s.
---
* strcpy, strncpy - copy a string
* char *strcpy(char *dest, const char *src);
* 回傳值: *dest
* strcpy是根據/0做為結束判斷的，如果dest空間不夠則會造成 buffer overflow。
* char *str**n**cpy(char *dest, const char *src, **size_t n**);
* 回傳值: *dest
* size_t n 指的是複製char的個數，且結尾不會自動加/0，需手動補上。
* 如果dest的空間>src的空間，剩下的空間都會以/0補滿。
---
* memcpy - copy memory area
* void *memcpy(void *dest, const void *src, size_t n);
* 回傳值: *dest
* **與strcpy不同，strcpy只能複製字串，而memcpy可以複製任何數據類型的對象，且不會遇到/0就停止，會完整複製n的位元組才結束。**
* void *memmove(void *dest, const void *src, size_t n);
* 回傳值: *dest
* 與memcpy不同的是。如果來源區域與目的地的某些區域重疊，這兩個函式可確保先複製重疊區域中的原始來源位元組，再進行覆寫。
---
* memset - fill memory with a constant byte
* void *memset(void *s, int c, size_t n);
* 回傳值: *s
* The memset() function fills the first n bytes of the memory area pointed to by s with the constant byte c.
* 常用在記憶體空間的初始化。
---
```
#include <string.h>
#include <stdio.h>
int main(int argc, char **argv){
char str1[]="Start stop";
int str1_len = strlen(str1);
char str2[str1_len]; //C99 允許宣告陣列用變數表示
memset(str2,'\0',str1_len); // init str2's memory area
strcpy(str2,str1);
printf("str1: %s\n",str1);
printf("str2: %s\n",str2);
memcpy(str1,str1+2,3*sizeof(char)); //str1+2 = &str1[2]
memmove(str2,str2+2,3*sizeof(char));
printf("str1: %s\n",str1);
printf("str2: %s\n",str2);
}
```
```
str1: Start stop
str2: Start stop
str1: artrt stop
str2: artrt stop
"Start stop" "Start stop"
[-] [-]
[-] [-]
有overlap的情況 無overlap的情況
```
此程式碼的memcpy 跟 memmove的結果雖然一樣，但那是因為編譯器可能會自動去處理overlap的問題，但根據編譯器的不同memcpy不能保證結果正確。範例是從[Difference between memmove and memcpy](https://www.youtube.com/watch?v=nFl1cNXk85s&ab_channel=CodeVault)修改而成的。
---
* strcat, strncat - concatenate two strings
* char *strcat(char *dest, const char *src);
* 回傳值: *dest
* char *strncat(char *dest, const char *src, size_t n);
* 回傳值: *dest
* n 決定複製幾個字元到dest尾端。
```
Source code:
char *strncat(char *dest, const char *src, size_t n)
{
size_t dest_len = strlen(dest);
size_t i;
for (i = 0 ; i < n && src[i] != '\0' ; i++)
dest[dest_len + i] = src[i];
dest[dest_len + i] = '\0';
return dest;
}
```
以上是str**n**cat的 soure code，從程式碼可以很清楚的看到strncat的處理過程，並在字串結尾會補上'\0'。
---
* strcmp, strncmp - compare two strings
* int strcmp(const char *s1, const char *s2);
* s1 == s2 回傳 0，s1 > s2 回傳一個正數，s1 < s2 回傳一個負數。
* 比較的依據是由[ASCII](https://zh.wikipedia.org/wiki/ASCII)碼去比較的。
* 遇到字串結束符'\0'，會終止比較。
* int strncmp(const char *s1, const char *s2, size_t n);
* s1 == s2 回傳 0，s1 > s2 回傳一個正數，s1 < s2 回傳一個負數。
* n是比較前n個字元。
strcmp系列的回傳值較複雜s1>s2的回傳值，根據編譯器的不同會產生1 or ASCII的差值。
* memcmp - compare memory areas
* int memcmp(const void *s1, const void *s2, size_t n);
* s1 == s2 回傳 0，s1 > s2 回傳一個正數，s1 < s2 回傳一個負數。
* memcmp不會因為遇到'\0'，而結束函式。
```
#include<stdio.h>
#include<string.h>
int main(void){
char str1[]="He is teacher";
char str2[]="He is student";
printf("strcmp: %d\n",strcmp(str1,str2));
printf("strcmp: %d\n",strncmp(str1,str2,5));
}
```
```
strcmp: 1
strncmp: 0 // 前5個字元相等 "He is"，所以回傳值為0。
```
strcmp的回傳值為**1**代表str1大於str2，雖然"teacher"與"student"都是六個字母組成，但strcmp比較的是ASCII碼，第一個不同的字元分別為str1的't'與str2的's'，'t'的ASCII碼為116，則's'的ASCII碼為115，所以t大於s，回傳值為1。
strcmp、strncmp與memcmp的不同處，有網友在[What is the difference between memcmp, strcmp and strncmp in C?](https://stackoverflow.com/questions/13095513/what-is-the-difference-between-memcmp-strcmp-and-strncmp-in-c)解釋得非常清楚。
* strcmp: compares null-terminated C strings.
* strncmp: compares at most N characters of null-terminated C strings.
* memcmp: compares binary byte buffers of N bytes.
```
const char s1[] = "atoms\0\0\0\0"; // extra null bytes at end
const char s2[] = "atoms\0abc"; // embedded null byte
const char s3[] = "atomsaaa";
---------------------------------------------------------------------
strcmp(s1, s2) == 0 // strcmp stops at null terminator
strcmp(s1, s3) != 0 // Strings are different
strncmp(s1, s3, 5) == 0 // First 5 characters of strings are the same
memcmp(s1, s3, 5) == 0 // First 5 bytes are the same
strncmp(s1, s2, 8) == 0 // Strings are the same up through the null terminator
memcmp(s1, s2, 8) != 0 // First 8 bytes are different
```
---
## <stdio.h>
* ~~sprintf~~, snprintf - formatted output conversion
* int snprintf(char *str, size_t size, const char *format, ...);
* 限制字串的長度，避免overflow。
* 比起用strncpy不會自動加\0，用snprintf會更好。
```
int buff[1024];
int num=10000;
sprintf(buff, "%d x %d = %d",num,num,num*num);
會產生 overflow
-----------------------------------------------
int buff[1024];
int num=10000;
sprintf(buff,sizeof(buff) ,"%d x %d = %d",num,num,num*num);
不會產生 overflow
```
---
## 錯誤處理
程式發生錯誤時通常會把錯誤代碼存入一個叫"errno"的全域變數，可以#include<errno.h>來顯示出對應的錯誤訊息。
* perror - print a system error message
* void perror(const char *s);
* char *strerror(int errnum);
[Linux下perror errno出錯函數](https://tw511.com/a/01/8093.html)清楚展示如何使用。
```
#include <stdio.h> //perror
#include <string.h> //strerror
#include <errno.h> //errno
#if 0
void perror(const char *s);
功能：s + ':' + '空格' + '錯誤資訊' + '\n'
char *strerror(int errnum);
功能：將錯誤碼轉換成對應錯誤資訊
errno
功能：自動記錄最後一次的錯誤碼
#endif
int main(int argc, const char *argv[])
{
FILE *fp = fopen(argv[1], "r");
if(fp == NULL)
{
printf("fopen error\n");
perror("fopen error");
printf("strerror : %s\n",strerror(errno));
return -1;
}
printf("ok\n");
return 0;
}
------------------------------------------
fopen error
fopen error: Bad address
strerror : Bad address
```
* 節制的善用goto
* 常使用在例外處理。
* [Using goto for error handling in C](https://eli.thegreenplace.net/2009/04/27/using-goto-for-error-handling-in-c) 以下兩個範例，可以清楚地看到使用goto對程式碼精簡很多，更容易去閱讀及使用。
```
int c_example()
{
int ret = 0; // return value 0 is success
FILE *f = fopen("logfile.txt", "w+");
if (!f)
return -1;
if (fputs("hello logfile!", f) == EOF)
{
ret = -2;
goto out;
}
// continue using the file resource
// ...
// Releasing resources (in reverse order)
out:
if (fclose(f) == EOF)
ret = -3;
return ret;
}
```
```
int c_example()
{
int ret = 0; // return value 0 is success
FILE *f = fopen("logfile.txt", "w+");
if (!f)
return -1;
if (fputs("hello logfile!", f) != EOF)
{
// continue using the file resource
}
else
{
ret = -2;
}
if (fclose(f) == EOF)
ret = -3;
return ret;
}
```
---
---
## 好用的標準函式
* void qsort(void *base, size_t nmemb, size_t size,int (*compar)(const void , const void *));
* qsort 並不一定是 quick sort，編譯器會根據陣列決定使用哪種演算法。
```
#include<stdio.h>
#include<stdlib.h> //qsort
int cmp(const void *a, const void *b){
return *(int*)a - *(int*)b;
}
void print_arr(int *arr,int n){
for(int i=0; i<n ;i++){
printf("%d ",*(arr+i));
}
printf("\n");
}
int main(){
int arr[]={2,5,8,9,5,4,7,85,2,100};
int n = sizeof(arr) / sizeof(int);
print_arr(arr,n);
qsort(arr,n,sizeof(int),cmp);
print_arr(arr,n);
}
-------------------------------------------------
2 5 8 9 5 4 7 85 2 100
2 2 4 5 5 7 8 9 85 100
```
---
## Process
另一篇有簡略介紹[Process](https://hackmd.io/Zp7uUl5KTpSZSviYantg8w?view#%E4%BD%9C%E6%A5%AD%E7%B3%BB%E7%B5%B1OS)。
* fork - create a child process (#include <unistd.h>)
* pid_t fork(void);
* Return Value:
* -1: no child process is created, and errno is set appropriately.
* 0 : 為child process
* 大於0 : the PID of the child process is returned in the parent
[[Linux C] fork 觀念由淺入深](https://wenyuangg.github.io/posts/linux/fork-use.html)
* 僵屍程序 (Zombie Process)：
1. 僵屍程序是指一支存活在系統中, 但是他卻沒有做任何事, 只是佔著並耗用系統資源的程序
2. 當使用 fork() 來建立子程序多工運行時, 如果子程序還沒運行結束就將父程序關閉的話, 就會有僵屍程序產生
---
## [Posix thread](https://zh.wikipedia.org/wiki/POSIX%E7%BA%BF%E7%A8%8B)
需要在程式開頭 #include<pthread.h>，在編譯時需加 -pthread參數。
[Difference between -pthread and -lpthread while compiling](https://stackoverflow.com/questions/23250863/difference-between-pthread-and-lpthread-while-compiling)
### 執行緒管理
pthread_xxxx的函式有許多種，以下僅列出較常使用的。
* pthread_self - obtain ID of the calling thread
* pthread_t pthread_self(void);
* 回傳 thread ID。
* pthread_create - create a new thread
* int pthread_create(pthread_t *thread, const pthread_attr_t *attr,
void *(*start_routine) (void *), void *arg);
* 創建成功回傳0，失敗回傳錯誤代碼。
* 第一個參數: pthread_t的變數，以pointer帶入。
* 第二個參數: thread的屬性，沒指定就填入NULL，使用預設屬性。
* 第三個參數: thread要執行的function，以pointer帶入。
* 第四個參數: function要帶入的參數，不用參數就NULL。
```
pthread_t thread;
int ret;
ret = pthread_create(&thread, NULL, start_routine, NULL);
if(!ret){
errno = ret;
perror("pthread_create:");
return -1;
}
```
* pthread_join - join with a terminated thread
* int pthread_join(pthread_t thread, void **retval);
* 成功回傳0，失敗回傳錯誤代碼。
* 第一個參數: 等待的目標thread。
* 第二個參數: 接收thread回傳的值。
* pthread_exit - terminate calling thread
* void pthread_exit(void *retval);
* thread預計會傳回的值，可在主程式由 pthread_join接收此回傳值。
範例: [C 語言 pthread 多執行緒平行化程式設計入門教學與範例](https://blog.gtwang.org/programming/pthread-multithreading-programming-in-c-tutorial/)
```
#include<stdio.h>
#include<stdlib.h>
#include<unistd.h> //sleep
#include<errno.h> //errno
#include<pthread.h>
void* child(void *data){ //子執行續
char *str = (char*)data;
for(int i=0 ;i<3;i++){
printf("%s\n",str);
sleep(1);
}
pthread_exit(NULL);
}
int main(){ //主執行續
pthread_t thread1;
int th1= pthread_create(&thread1, NULL, child, "child");
if(th1){
errno =th1;
perror("pthread_create:");
}
for(int i=0 ; i<3 ;i++){
printf("Master\n");
sleep(1);
}
pthread_join(thread1,NULL);
}
```
```
gcc -g -Wall pthread1.c -pthread -o pthread1
DESKTOP-T8T3932% ./pthread1
Master
child
child
Master
Master
child
DESKTOP-T8T3932% ./pthread1
Master
child
Master
child
Master
child
```
可以發現輸出的結果並不一定是我們預期的輪流顯示，原因是我們不能控制thread的行動，需加上一些條件才能控制thread的行動(**EX:Condition Variable, Mutex等**)。
```
#include<stdio.h>
#include<stdlib.h>
#include<errno.h>
#include<pthread.h>
void* child(void* arg){
int *input = (int*) arg;
int *result = malloc(sizeof(int)*1);
result[0] = input[0]+input[1];
pthread_exit((void*)result);
}
int main(){
pthread_t thread1;
int list[2]={1,2};
void* ret; // 子執行續的回傳值
int td1 = pthread_create(&thread1, NULL, child, list);
if(td1){
errno=td1;
perror("pthread_create:");
}
pthread_join(thread1,&ret);
int *result = (int*) ret;
printf("%d + %d = %d\n",list[0],list[1],result[0]);
free(result);
}
```
```
DESKTOP-T8T3932% gcc -g -Wall pthread2.c -pthread -o pthread2
DESKTOP-T8T3932% ./pthread2
1 + 2 = 3
這種動態配置記憶體的方法，在Thread比較不容易處理，容易寫錯造成 memory leak。
```
```
#include <stdio.h>
#include <pthread.h>
#include<errno.h>
typedef struct my_data {
int a;
int b;
int result;
} my_data;
void *child(void *arg) {
my_data *data=(my_data *) arg;
int a = data->a;
int b = data->b;
int result = a + b;
data->result = result;
pthread_exit(NULL);
}
int main() {
pthread_t t;
my_data data;
data.a = 1;
data.b = 2;
int td1 = pthread_create(&t, NULL, child, (void*) &data);
if(td1){
errno = td1;
perror("pthread_create:");
}
pthread_join(t, NULL);
printf("%d + %d = %d\n", data.a, data.b, data.result);
}
```
```
1 + 2 = 3
統一由主thread來管理記憶體空間，較malloc安全許多。
```
### [互斥鎖(Mutex)](https://zh.wikipedia.org/wiki/%E4%BA%92%E6%96%A5%E9%94%81)
**Mutex的流程: 建立mutex → 初始化mutex → 操作mutex(lock,unlock等) → 銷毀mutex**
* mutex兩種初始化:
```
1. pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER; //不需要destory mutex
2. pthread_mutex_t mutex;
pthread_mutex_init(&mutex,NULL); //第二個參數是 鎖的屬性
pthread_mutex_destory(&mutex);
```
* 操作mutex
```
int pthread_mutex_lock(pthread_mutex_t *mutex);
int pthread_mutex_trylock(pthread_mutex_t *mutex);
int pthread_mutex_unlock(pthread_mutex_t *mutex);
```
在lock和unlock之間的程式碼，只允許一個thread執行，盡可能讓互斥鎖的程式碼少點，效率才更會好。
```
此範例"未加"互斥鎖(mutex)
#include<stdio.h>
#include<stdlib.h>
#include<pthread.h>
#include<unistd.h>
int count=0; //同Process內的多個thread可以共同讀取全域變數
void *child(){
for(int i=0; i<3 ;i++){
int tmp = count;
sleep(1);
count=tmp+1;
printf("count= %d \n",count);
}
pthread_exit(NULL);
}
int main(){
pthread_t thread1,thread2;
pthread_create(&thread1,NULL,child,NULL);
pthread_create(&thread2,NULL,child,NULL);
pthread_join(thread1,NULL);
pthread_join(thread2,NULL);
}
```
```
count= 1
count= 1
count= 2
count= 2
count= 3
count= 3
```
---
```
此範例"加"互斥鎖(mutex)
#include<stdio.h>
#include<stdlib.h>
#include<pthread.h>
#include<unistd.h>
int count=0;
pthread_mutex_t mutex1 = PTHREAD_MUTEX_INITIALIZER;
void *child(){
for(int i=0; i<3 ;i++){
pthread_mutex_lock(&mutex1);
int tmp = count;
sleep(1);
count=tmp+1;
pthread_mutex_unlock(&mutex1);
printf("count= %d \n",count);
}
pthread_exit(NULL);
}
int main(){
pthread_t thread1,thread2;
pthread_create(&thread1,NULL,child,NULL);
pthread_create(&thread2,NULL,child,NULL);
pthread_join(thread1,NULL);
pthread_join(thread2,NULL);
}
```
```
count= 1
count= 2
count= 3
count= 4
count= 5
count= 6
```
### 條件變數(Condition Variable)
* Condition Variable
通常都會與mutex搭配使用
```
pthread_cond_t cond_var = PTHREAD_COND_INITIALIZER; //初始化
int pthread_cond_broadcast(pthread_cond_t* cond); //喚醒條件變數等待的"所有"執行緒
int pthread_cond_signal(pthread_cond_t* cond); //喚醒條件變數上等待的"一個"執行緒
int pthread_cond_wait(pthread_cond_t* cond); //解鎖mutex並等待條件變數觸發
```
### [旗標（Semaphore)](https://zh.wikipedia.org/wiki/%E4%BF%A1%E5%8F%B7%E9%87%8F)
使用semaphore需載入#include<semaphore.h>，semaphore本身是一個計數器。
* int sem_init(sem_t *sem, int pshared, unsigned int value);
* int sem_wait(sem_t *sem);
* sem_wait: 用來判斷是否有工作尚未完成，當工作數量大於0時，執行程序並把工作量-1，當工作量等於0時，停止此thread等待工作量大於0。
* int sem_post(sem_t *sem);
* sem_post: 可以新增工作量+1。
範例: [C 語言 pthread 多執行緒平行化程式設計入門教學與範例](https://blog.gtwang.org/programming/pthread-multithreading-programming-in-c-tutorial/)
```
#include<stdio.h>
#include<unistd.h>
#include<pthread.h>
#include<semaphore.h>
sem_t sem;
int counter = 0;
void* child(){
for(int i=0; i< 5 ;i++){
sem_wait(&sem);
printf("counter = %d\n",counter++); //先取值，再++
sleep(1);
}
pthread_exit(NULL);
}
int main(){
sem_init(&sem,0,0);
pthread_t thread;
pthread_create(&thread,NULL,child,NULL);
printf("post 2 jobs\n");
sem_post(&sem);
sem_post(&sem);
sleep(3);
printf("post 3 jobs\n");
sem_post(&sem);
sem_post(&sem);
sem_post(&sem);
pthread_join(thread,NULL);
}
```
```
DESKTOP-T8T3932% gcc -g -Wall semaphore_test1.c -pthread -o semaphore_test1
DESKTOP-T8T3932% ./semaphore_test1
post 2 jobs
counter = 0
counter = 1
post 3 jobs
counter = 2
counter = 3
counter = 4
```
---
### Producer Consumer Models
* 最簡易的consumer producer範例(兩種寫法，不同於pthread_create最後有無參數)。
```
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <unistd.h>
#include <string.h>
#define BUFFFSIZE 255
static void* producer(void* );
static void* consumer(void* );
int allnumber; // 總共有幾題
int isfound=1 ; // 還沒找到答案
char QA_buff[BUFFFSIZE] = {'\0'}; // producer 和 consumer 都要從這裡拿資料
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t cond = PTHREAD_COND_INITIALIZER;
typedef struct QA{
char *Q;
char *A;
int number;
}QA;
int main(){
srand(time(NULL));
QA test[]={ {.Q = "James", .A = "Harden", .number = 0},
{.Q = "Kevin" , .A = "Love", .number = 1},
{.Q = "Ray" , .A = "Allen", .number = 2},
{.Q = "Devin", .A = "book", .number = 3}};
allnumber = sizeof(test)/sizeof(test[0]);
printf("allnumber:%d\n",allnumber);
pthread_t prod,cons;
if((pthread_create(&prod,NULL,consumer,&test)) != 0){
perror("producer create:");
}
if((pthread_create(&cons,NULL,producer,&test)) != 0){
perror("consumer create:");
}
pthread_join(prod,NULL);
pthread_join(cons,NULL);
}
static void* producer(void *p){
QA *qa_prod = (QA*) p;
while(1){
pthread_mutex_lock(&mutex);
int i =rand() %allnumber;
snprintf(QA_buff,BUFFFSIZE,"%s",qa_prod[i].Q);
printf("Q: %s\n",QA_buff);
while(isfound > 0){
//printf("%s\n","wait");
sleep(1);
pthread_cond_wait(&cond,&mutex);
}
printf("A: %s\n",QA_buff);
isfound=1;
pthread_mutex_unlock(&mutex);
sleep(1);
}
pthread_exit(NULL);
}
static void* consumer(void *p){
QA *qa_cons = (QA*) p;
while(1){
pthread_mutex_lock(&mutex);
for(int k=0; k< allnumber ;k++)
{
if( (strcmp(QA_buff,qa_cons[k].Q)) == 0){
snprintf(QA_buff,BUFFFSIZE,"%s",qa_cons[k].A);
isfound = -1;
pthread_cond_signal (&cond);
//printf("%s\n","signal");
break;
}
}
//printf("%s\n",QA_buff);
pthread_mutex_unlock(&mutex);
sleep(1);
}
pthread_exit(NULL);
}
```
---
```
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <unistd.h>
#include <string.h>
#define BUFFFSIZE 255
static void* producer(void* );
static void* consumer(void* );
int isfound=1 ; // 還沒找到答案
char QA_buff[BUFFFSIZE] = {'\0'}; // producer 和 consumer 都要從這裡拿資料
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t cond = PTHREAD_COND_INITIALIZER;
typedef struct QA{
char *Q;
char *A;
int number;
}QA;
QA test[]={ {.Q = "James", .A = "Harden", .number = 0},
{.Q = "Kevin" , .A = "Love", .number = 1},
{.Q = "Ray" , .A = "Allen", .number = 2},
{.Q = "Devin", .A = "book", .number = 3}};
int allnumber = sizeof(test)/sizeof(test[0]);
int main(){
srand(time(NULL));
printf("allnumber:%d\n",allnumber);
pthread_t prod,cons;
if((pthread_create(&prod,NULL,consumer,NULL)) != 0){
perror("producer create:");
}
if((pthread_create(&cons,NULL,producer,NULL)) != 0){
perror("consumer create:");
}
pthread_join(prod,NULL);
pthread_join(cons,NULL);
}
static void* producer(void *p){
while(1){
pthread_mutex_lock(&mutex);
int i =rand() %allnumber;
snprintf(QA_buff,BUFFFSIZE,"%s",test[i].Q);
printf("Q: %s\n",QA_buff);
while(isfound > 0){
//printf("%s\n","wait");
sleep(1);
pthread_cond_wait(&cond,&mutex);
}
printf("A: %s\n",QA_buff);
isfound=1;
pthread_mutex_unlock(&mutex);
sleep(1);
}
pthread_exit(NULL);
}
static void* consumer(void *p){
while(1){
pthread_mutex_lock(&mutex);
for(int k=0; k< allnumber ;k++)
{
if( (strcmp(QA_buff,test[k].Q)) == 0){
snprintf(QA_buff,BUFFFSIZE,"%s",test[k].A);
isfound = -1;
pthread_cond_signal (&cond);
//printf("%s\n","signal");
break;
}
}
//printf("%s\n",QA_buff);
pthread_mutex_unlock(&mutex);
sleep(1);
}
pthread_exit(NULL);
}
```
---
```
allnumber:4
Q: James
A: Harden
Q: Devin
A: book
Q: Kevin
A: Love
Q: Ray
A: Allen
....
兩種寫法得到的結果都一樣。
1. producer會把題目放入QA_buff後，進行wait掛起。
2. consumer讀取QA_buff的題目後，搜尋問題得到對應的答案，再把答案放回QA_buff，並signal 正在wait的producer。
3. producer被喚醒重新上鎖後，顯示出QA_buff裡的答案。
```
---
```
```
```
```
---
---
## 簡易linked list練習
當初學習來源:[鏈結串列教學](https://medium.com/@racktar7743/%E8%B3%87%E6%96%99%E7%B5%90%E6%A7%8B-%E9%8F%88%E7%B5%90%E4%B8%B2%E5%88%97%E6%95%99%E5%AD%B8-1-%E6%96%B0%E5%A2%9E%E8%88%87%E5%8D%B0%E5%87%BA-bb881da97796)
```
#include<stdio.h>
#include<stdlib.h>
typedef struct node{
int val;
struct node* next;
}Node;
static void addnode(Node **node,int val);
static void insertnode(Node **node,int insert_after_val,int val);
static void deletenode(Node **node,int val);
static void printnode(Node *node);
static void freenode(Node *node);
int main(){
Node* head = NULL;
addnode(&head,10);
addnode(&head,20);
addnode(&head,30);
insertnode(&head,20,25);
insertnode(&head,30,35);
printnode(head);
deletenode(&head,10);
deletenode(&head,20);
deletenode(&head,30);
printnode(head);
freenode(head);
return 0;
}
static void addnode(Node **node,int val){
Node *newnode = malloc(sizeof(Node));
newnode->val = val;
newnode->next = NULL;
if(*node == NULL){
*node = newnode;
return;
}
else{
Node *current;
current = *node;
while(current->next != NULL){
current = current->next;
}
current->next = newnode;
return;
}
}
static void insertnode(Node **node,int insert_after_val,int val){
Node *current = *node;
while(current != NULL){
if(current->val == insert_after_val){
Node *newnode = malloc(sizeof(Node));
newnode->val = val;
newnode->next = NULL;
if(current->next == NULL){
current->next = newnode;
break;
}
else{
newnode->next = current->next;
current->next =newnode;
break;
}
}
current = current->next;
}
}
static void deletenode(Node **node,int val){
Node *tmp;
Node *current = *node;
if(current->val == val){
*node = current->next;
free(current);
return;
}
while(current != NULL){
if(current->next->val == val){
tmp = current->next;
current->next = current->next->next;
free(tmp);
return;
}
current = current->next;
}
}
static void printnode(Node *node){
while(node != NULL){
printf("%d ",node->val);
node = node->next;
}
printf("\n");
}
static void freenode(Node *node){
Node *tmp,*current;
current = node;
while(current != NULL){
tmp = current;
current = current->next;
free(tmp);
}
}
```
---
```
10 20 25 30 35
25 35
```
---
## 簡易Hash練習
當初學習來源待補:
```
#include<stdio.h>
#include<stdlib.h>
#define SIZE 20
typedef struct
{
int data;
int key;
}HASH;
HASH *hashlist[SIZE];
HASH *item;
HASH *tmp;
int hash_code(int key){
return key % SIZE;
}
void hash_insort(int key,int data){
HASH *item = malloc(sizeof(HASH));
item->data = data;
item->key = key;
int hash_index = hash_code(key);
while(hashlist[hash_index] != NULL && hashlist[hash_index]->key != -1){
hash_index++;
hash_index %=SIZE;
}
hashlist[hash_index] = item;
}
HASH *hash_delete(HASH *item){
int key = item->key;
int hash_index = hash_code(key);
while(hashlist[hash_index] != NULL){
if(hashlist[hash_index]->key == key){
HASH *temp = hashlist[hash_index];
hashlist[hash_index] = tmp;
return temp;
}
hash_index++;
hash_index %=SIZE;
}
return NULL;
}
HASH *hash_search(int key){
int hash_index = hash_code(key);
while(hashlist[hash_index] != NULL){
if(hashlist[hash_index]->key == key){
return hashlist[hash_index];
}
hash_index++;
hash_index %=SIZE;
}
return NULL;
}
void hashlist_display(){
for(int i=0 ;i<SIZE;i++){
if(hashlist[i] != NULL){
printf("(%d,%d)",hashlist[i]->key,hashlist[i]->data);
}
else{
printf("~~");
}
}
printf("\n");
}
int main(){
tmp = malloc(sizeof(HASH));
tmp->data=-1;
tmp->key =-1;
hash_insort(1,20);
hash_insort(2,70);
hash_insort(42,80);
hash_insort(4,25);
hash_insort(12,44);
hash_insort(14,32);
hash_insort(17,11);
hash_insort(13,78);
hash_insort(37,97);
hashlist_display();
item = hash_search(37);
if(item != NULL){
printf("element found:%d\n",item->data);
}
else{
printf("element not found\n");
}
hash_delete(item);
item = hash_search(37);
if(item != NULL){
printf("element found:%d\n",item->data);
}
else{
printf("element not found\n");
}
return 0;
}
```
---
```
~~(1,20)(2,70)(42,80)(4,25)~~~~~~~~~~~~~~(12,44)(13,78)(14,32)~~~~(17,11)(37,97)~~
element found:97
element not found
```
---
Sign in with Wallet
Connect another wallet