caijizhuo

发表于 更新于 分类于
本文字数： 381 阅读时长 ≈ 1 分钟 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#ifndef LST_TIMER
#define LST_TIMER

#include <time.h>
#define BUFFER_SIZE 64
class util_timer;

struct client_data {
    sockaddr_in address;
    int sockfd;
    char buf[BUFFER_SIZE];
    util_timer* timer;    
};

class util_timer {
public:
    util_timer() : prev(NULL), next(NULL){}
    time_t expire;
    void (*cb_func)(client_data*);
    client_data* user_data;
    util_timer* prev;
    util_timer* next;
};

class sort_timer_lst
{
public:
    sort_timer_lst() : head(NULL), tail(NULL) {}
    ~sort_timer_lst() {
        util_timer* tmp = head;
        while (tmp) {
            head = tmp->next;
            delete tmp;
            tmp = head;
        }
    }

    void add_timer(util_timer* timer) {
        if (!timer) {
            return;
        }
        if (!head) {
            head = tail = timer;
            return;
        }

        if (timer->expire < head->expire) {
            timer->next = head;
            head->prev = timer;
            head = timer;
            return;
        }
        add_timer(timer, head);
    }

    void adjust_timer(util_timer* timer) {
        if (!timer) {
            return;
        }
        util_timer* tmp = timer->next;
        if (!tmp || (timer->expire < tmp->expire)) {
            return;
        }
        if (timer == head) {
            head = head->next;
            head->prev = NULL;
            timer->next = NULL;
            add_timer(timer, head);
        } else {
            timer->prev->next = timer->next;
            timer->next->prev = timer->prev;
            add_timer(timer, timer->next);
        }
    }

    void del_timer(util_timer* timer) {
        if (!timer) {
            return;
        }
        if ((timer == head) && (timer == tail)) {
            delete timer;
            head = NULL;
            tail = NULL;
            return;
        }

        if (timer == head) {
            head = head->next;
            head->prev = NULL;
            delete timer;
            return;
        }

        if (timer == tail) {
            tail = tail->prev;
            tail->next = NULL;
            delete timer;
            return;
        }

        timer->prev->next = timer->next;
        timer->next->prev = timer->prev;
        delete timer;
    }

    void tick() {
        if (!head) {
            return;
        }
        printf("timer tick\n");
        time_t cur = time(NULL);
        util_timer* tmp = head;

        while (tmp) {
            if (cur < tmp->expire) {
                break;
            }
            tmp->cb_func(tmp->user_data);
            head = tmp->next;
            if (head) {
                head->prev = NULL;
            }
            delete tmp;
            tmp = head;
        }
    }
private:
    void add_timer(util_timer* timer, util_timer* lst_head) {
        util_timer* prev = lst_head;
        util_timer* tmp = prev->next;
        while (tmp) {
            if (timer->expire < tmp->expire) {
                prev->next = timer;
                timer->next = tmp;
                tmp->prev = timer;
                timer->prev = prev;
                break;
            }
            prev = tmp;
            tmp = tmp->next;
        }

        if (!tmp) {
            prev->next = timer;
            timer->prev = prev;
            timer->next = NULL;
            tail = timer;
        }
    }

    util_timer* head;
    util_timer* tail;
};

#endif /* LST_TIMER end */

此文件被包含在头文件中以便方便使用。tick为心跳函数，每隔一段时间执行一次。判断任务到期为定时器expire参数小于当前系统时间。
执行时间复杂度：
添加O(n)O(n),删除O(1)O(1)，执行任务O(1)O(1)

reference:
Linux高性能服务器编程——游双

发表于 更新于 分类于
本文字数： 501 阅读时长 ≈ 2 分钟

带外数据

带外数据用于迅速告知对方本端发生的重要的事件。它比普通的数据（带内数据）拥有更高的优先级，不论发送缓冲区中是否有排队等待发送的数据，它总是被立即发送。带外数据的传输可以使用一条独立的传输层连接，也可以映射到传输普通数据的连接中。

SIGURG信号的作用

在linux环境下，内核通知应用程序带外数据到达的方式有两种：

  1. 一种就是利用I/Ｏ复用技术的系统调用（如select）在接受到带外数据时将返回，并向应用程序报告socket上的异常事件。
  2. 另一种方法就是使用SIGURG信号。（下面代码）

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <sys/socket.h>
#include <netinet/in.h>
#include <arpa/inet.h>
#include <assert.h>
#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <errno.h>
#include <string.h>
#include <signal.h>
#include <fcntl.h>

#define BUF_SIZE 1024

static int connfd;

void sig_urg(int sig)
{
    int save_errno = errno;
    char buffer[BUF_SIZE];
    memset(buffer, '\0', BUF_SIZE);
    int ret = recv(connfd, buffer, BUF_SIZE - 1, MSG_OOB); // 接收带外数据
    printf("got %d bytes of oob data '%s\n' ", ret, buffer);
    errno = save_errno;
}

void addsig (int sig, void (* sig_handler) (int))
{
    struct sigaction sa;
    memset(&sa, '\0', sizeof(sa));
    sa.sa_handler = sig_handler;
    sa.sa_flags |= SA_RESTART;
    sigfillset(&sa.sa_mask);
    assert(sigaction(sig, &sa, NULL) != -1);
}

int main(int argc, char* argv[])
{
    if (argc <= 2)
    {
        printf("usage: %s ip_address port_number\n", basename(argv[0]));
        return 1;
    }
    const char* ip = argv[1];
    int port = atoi(argv[2]);

    struct sockaddr_in address;
    bzero(&address, sizeof(address));
    address.sin_family = AF_INET;
    inet_pton(AF_INET, ip, &address.sin_addr);
    address.sin_port = htons(port);

    int sock = socket(PF_INET, SOCK_STREAM, 0);
    assert(socket >= 0);

    int ret = bind(sock, (struct sockaddr*)&address, sizeof(address));
    assert(ret != -1);

    ret = listen(sock, 5);
    assert(ret != -1);

    struct sockaddr_in client;
    socklen_t client_addrlength = sizeof(client);
    connfd = accept(sock, (struct sockaddr*)&client, &client_addrlength);
    if (connfd < 0) {
        printf("errno is: %d\n", errno);
    } else {
        addsig(SIGURG, sig_urg);
        fcntl(connfd, F_SETOWN, getpid()); // 设置SIGURG信号之前，我们必须设置socket的宿主进程或进程组

        char buffer[BUF_SIZE];
        while (1) {
            memset(buffer, '\0', BUF_SIZE);
            ret = recv(connfd, buffer, BUF_SIZE - 1, 0);
            if (ret <= 0) {
                break;
            }
            printf("got %d bytes of normal data '%s\n", ret, buffer);
        }
        close(connfd);
    }
    close(sock);
    return 0;
}

客户端（本机模拟发送SIGURG）
1

服务端反应
2

reference：
linux高性能服务器编程——游双

发表于 更新于 分类于
本文字数： 710 阅读时长 ≈ 3 分钟

关于什么是快速幂：快速幂代码
现在回想下问题斐波那契数列：f(1)=1,f(2)=1f(1) = 1, f(2) = 1。在n>2n > 2时， f(n)=f(n−1)+f(n−2)f(n) = f(n - 1) + f (n - 2)。求f(n)f(n)。
朴素动态规划解法：

1
2
3
4
5
6
7
8
int fib(int n) {
    int dp[n];
    dp[0] = 1, dp[1] = 1;
    for (int i = 2; i < n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n - 1];
}

现在考虑FnF_{n}是由Fn−1F_{n-1}和Fn−2F_{n-2}线性变换得出。则有：

[Fn   Fn−1]=[Fn−1   Fn−2]×[1110][F_{n} \ \ \ F_{n-1}] = [F_{n-1}\ \ \ F_{n-2}] \times \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}

设矩阵[1110]\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}为PP。
则有

[Fn+1   Fn]=[Fn   Fn−1]×[1110]=[Fn−1   Fn−2]×[1110]2=[Fn−1   Fn−2]×P2[F_{n+1}\ \ \ F_{n}] = [F_{n} \ \ \ F_{n-1}] \times \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} = [F_{n-1}\ \ \ F_{n-2}] \times\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^2 = [F_{n-1}\ \ \ F_{n-2}] \times P^2

因为矩阵乘法满足结合律，所以我们可以直接用矩阵PP的幂来得到FnF_n的值。而求矩阵PnP^n的时间复杂度为O(log(n))O(log(n))。
C++代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
const int maxn = 105;
struct Matrix{
    int n, m;
    int v[maxn][maxn];
    Matrix(int n, int m) : n(n), m(m) {}

    void init() {
        memset(v, 0, sizeof(v));  
    }

    Matrix operator* (const Matrix B) const {
        Matrix ans(n, B.m); // for ans
        ans.init();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < B.m; j++) {
                for (int k = 0; k < m; k++) {
                    ans.v[i][j] = ans.v[i][j] + v[i][k] * B.v[k][j];
                }
            }
        }
        return ans;
    }

    void print() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                cout << v[i][j] << " ";
            }
            cout << endl;
        }
    }
};

Matrix q_pow (Matrix& A, int b) {
    Matrix ret(A.n, A.m);

    ret.init();
    for (int i = 0; i < ret.n; i++) { // 初始化E
        ret.v[i][i] = 1;
    }

    while (b) {
        if (b & 1) {
            ret = ret * A;
        }
        A = A * A;
        b >>= 1;
    }
    return ret;
}

完整代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <iostream>  
#include <cstdio>
#include <cstring>
using namespace std;
using ll = long long;
const int maxn = 105;
struct Matrix{
    int n, m;
    int v[maxn][maxn];
    Matrix(int n, int m) : n(n), m(m) {}

    void init() {
        memset(v, 0, sizeof(v));  
    }

    Matrix operator* (const Matrix B) const {
        Matrix ans(n, B.m); // for ans
        ans.init();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < B.m; j++) {
                for (int k = 0; k < m; k++) {
                    ans.v[i][j] = ans.v[i][j] + v[i][k] * B.v[k][j];
                }
            }
        }
        return ans;
    }

    void print() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                cout << v[i][j] << " ";
            }
            cout << endl;
        }
    }
};

Matrix q_pow (Matrix& A, int b) {
    Matrix ret(A.n, A.m);

    ret.init();
    for (int i = 0; i < ret.n; i++) { // 初始化E
        ret.v[i][i] = 1;
    }

    while (b) {
        if (b & 1) {
            ret = ret * A;
        }
        A = A * A;
        b >>= 1;
    }
    return ret;
}

int fib(int n) {
    int dp[n];
    dp[0] = 1, dp[1] = 1;
    for (int i = 2; i < n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n - 1];
}

int main()
{
    int n = 44;
    clock_t startTime, endTime;
    startTime = clock(); // cpu clock time
    cout << fib(n) << endl;
    endTime = clock();
    cout << (endTime - startTime) << endl;
    // [F(n)  F(n - 1)] = [F(n - 1)  F(n - 2)] * [1 1]
    //                                           [1 0]
    Matrix start = Matrix(1, 2);
    start.v[0][0] = 1;
    start.v[0][1] = 1;

    Matrix P = Matrix(2, 2);
    P.v[0][0] = 1;
    P.v[0][1] = 1;
    P.v[1][0] = 1;
    P.v[1][1] = 0;

    startTime = clock(); // cpu clock time
    Matrix ret = start * q_pow(P, n - 1);
    endTime = clock();
    cout << (endTime - startTime) << endl;
    ret.print();
}

这里暂且不考虑溢出问题。当nn足够大的时候，可以看到快速幂需要的时钟周期明显缩短。

发表于 更新于 分类于
本文字数： 491 阅读时长 ≈ 2 分钟

基础问题：求数字 aa 的 nn 次方。
最基本的想法，就是一次一次相乘，时间复杂度为 O(n)O(n)。
代码如下：

1
2
3
4
5
6
7
8
9
using ll = long long;
ll pow(ll a, ll n)
{
    ll ret = 1;
    for (ll i = 0; i < n; i++) {
        ret *= a;
    }
    return ret;
}

稍微思考一下便可得知，计算一个数的nn次方并不需要相乘 nn 次。我们如果知道 aa 的 n/2n/2 次方，便可以用两个 an/2a^{n/2} 相乘，获得 ana^n。顺着这个思想往下想，可以考虑把 nn 拆成二进制的形式，这样只要把对应的二进制位数得到的幂相乘起来就可以得出答案了。举例：当 nn 为 7 时，我们要 676^7。77 按照二进制可以拆成 0000011100000111。那我们只要知道 616^1，626^2 和 646^4，再把他们相乘就可以了。
代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
ll qpow(ll a, ll n)
{
    if (n == 0) {
        return 1;
    } else if (n % 2 == 1) {
        return qpow(a, n - 1) * a;
    } else {
        ll ret = qpow(a, n / 2);
        return ret * ret;
    }
}

ll qpow2(ll a, ll n)
{
    ll ret = 1;
    while (n) {
        if (n & 1) {
            ret *= a;
        }
        a *= a;
        n >>= 1;
    }
    return ret;
}

一为递归的方式，二为迭代的方式。考虑到调用栈切换，方式二会快一些。这种把幂拆成二进制的方法，就被称为快速幂。
完整代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <time.h>
using namespace std;
using ll = long long;
ll pow(ll a, ll n)
{
    ll ret = 1;
    for (ll i = 0; i < n; i++) {
        ret *= a;
    }
    return ret;
}

ll qpow(ll a, ll n)
{
    if (n == 0) {
        return 1;
    } else if (n % 2 == 1) {
        return qpow(a, n - 1) * a;
    } else {
        ll ret = qpow(a, n / 2);
        return ret * ret;
    }
}

ll qpow2(ll a, ll n)
{
    ll ret = 1;
    while (n) {
        if (n & 1) {
            ret *= a;
        }
        a *= a;
        n >>= 1;
    }
    return ret;
}
int main()
{
    ll a = 7, n = 16;
    clock_t startTime, endTime;
    startTime = clock(); // cpu clock time
    cout << pow(a, n) << endl;
    endTime = clock();
    cout << (endTime - startTime) << endl;

    startTime = clock(); // cpu clock time
    cout << qpow(a, n) << endl;
    endTime = clock();
    cout << (endTime - startTime) << endl;

    startTime = clock(); // cpu clock time
    cout << qpow2(a, n) << endl;
    endTime = clock();
    cout << (endTime - startTime) << endl;
}

可以看到后面两种cpu周期普遍低于前一种。

发表于 更新于 分类于
本文字数： 679 阅读时长 ≈ 2 分钟

priority_queue是C++的一种STL容器，实现为堆。在leetcode刷题中非常常用。有些时候我们需要塞入自定义的数据结构。这样就需要对其的排序方式做一个重新定义。
假设有以下数据结构

1
2
3
4
struct node {
    int x;
    int y;
};

对比方式为只看x的大小。把x的值大的放在堆顶。
则对比函数cmp写法如下：

1. 仿函数（函数对象）

用这种方式，需要显示的定义优先队列的容器类型（vector）以及比较函数（cmp）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>
#include<queue>
using namespace std;
//函数对象类
template <typename T>
class cmp {
public:
    //重载 () 运算符
    bool operator()(T a, T b) {
        return a.x < b.x;
    }
};
struct node {
    int x;
    int y;
};
int main() {
    node a = {1,2};
    node b = {0,2};
    node c = {1,3};
    node d = {2,5};
    node e = {3,6};
    priority_queue<node, vector<node>, cmp<node>> pq; // 显式指定容器类型和比较函数
    pq.push(a);
    pq.push(b);
    pq.push(c);
    pq.push(d);
    pq.push(e);
    while (!pq.empty()) {
        cout << pq.top().x << "," << pq.top().y << endl;
        pq.pop();
    }
    return 0;
}

结果：

1
2
3
4
5
6
@└────> # ./pq
3,6
2,5
1,3
1,2
0,2

2. 使用自定义类型比较关系

重载需要比较类型的<<符号，之后在类型直接写类型名称即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<iostream>
#include<queue>
using namespace std;
struct node {
    int x;
    int y;
    bool operator < (node b) const { // 这里后面的const必须加
        return this->x < b.x;
    }
};
int main() {
    node a = {1,2};
    node b = {0,2};
    node c = {1,3};
    node d = {2,5};
    node e = {3,6};
    priority_queue<node> pq; // 只写类型名称即可
    pq.push(a);
    pq.push(b);
    pq.push(c);
    pq.push(d);
    pq.push(e);
    while (!pq.empty()) {
        cout << pq.top().x << "," << pq.top().y << endl;
        pq.pop();
    }
    return 0;
}

结果：

1
2
3
4
5
6
@└────> # ./pq
3,6
2,5
1,3
1,2
0,2

3. 使用lambda表达式

使用lambda表达式需要在pq对象构造的时候，将lambda表达式作为参数传入其中。即pq(cmp)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<iostream>
#include<queue>
#include<functional>
using namespace std;

struct node {
    int x;
    int y;
};
int main() {
    auto cmp = [](node x, node y) {
        return x.x < y.x;
    };
    node a = {1,2};
    node b = {0,2};
    node c = {1,3};
    node d = {2,5};
    node e = {3,6};
    priority_queue<node, vector<node>, decltype(cmp)> pq(cmp); // 需要在pq对象创建的时候将lambda表达式作为参数传入
    // priority_queue<node, vector<node>, function<bool(node, node)> > pq(cmp); // 和上面的效果相同，但是用function需要包含头文件functional
    pq.push(a);
    pq.push(b);
    pq.push(c);
    pq.push(d);
    pq.push(e);
    while (!pq.empty()) {
        cout << pq.top().x << "," << pq.top().y << endl;
        pq.pop();
    }
    return 0;
}

结果：

1
2
3
4
5
6
@└────> # ./pq
3,6
2,5
1,3
1,2
0,2

4. 函数指针（和上面的相比有些多余，刷题不是很实用）

这种方式和lambda表达式的方式很类似。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<iostream>
#include<queue>
#include<functional>
using namespace std;

struct node {
    int x;
    int y;
};
bool cmp(node x, node y) {
    return x.x < y.x;
}
int main() {
    node a = {1,2};
    node b = {0,2};
    node c = {1,3};
    node d = {2,5};
    node e = {3,6};
    bool (*funcp)(node x, node y) = cmp;
    priority_queue<node, vector<node>, decltype(*funcp)> pq(*funcp);
    pq.push(a);
    pq.push(b);
    pq.push(c);
    pq.push(d);
    pq.push(e);
    while (!pq.empty()) {
        cout << pq.top().x << "," << pq.top().y << endl;
        pq.pop();
    }
    return 0;
}

结果：

1
2
3
4
5
6
@└────> # ./pq
3,6
2,5
1,3
1,2
0,2

reference：

https://blog.csdn.net/Strengthennn/article/details/119078911

发表于 更新于 分类于
本文字数： 993 阅读时长 ≈ 4 分钟

客户端：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#define _GNU_SOURCE 1
#include <sys/types.h>
#include <sys/socket.h>
#include <netinet/in.h>
#include <arpa/inet.h>
#include <assert.h>
#include <stdio.h>
#include <unistd.h>
#include <string.h>
#include <stdlib.h>
#include <poll.h>
#include <fcntl.h>

#define BUFFER_SIZE 64

int main(int argc, char* argv[]) {
    if (argc <= 2) {
        printf("usage: %s ip_address port_number\n", basename(argv[0]));
        return 1;
    }
    const char* ip = argv[1];
    int port = atoi(argv[2]);

    struct sockaddr_in server_address;
    bzero(&server_address, sizeof(server_address));
    server_address.sin_family = AF_INET;
    inet_pton(AF_INET, ip, &server_address.sin_addr);
    server_address.sin_port = htons(port);

    int sockfd = socket(PF_INET, SOCK_STREAM, 0);
    assert(sockfd >= 0);
    if (connect(sockfd, (struct sockaddr*)&server_address, sizeof(server_address)) < 0) {
        printf("connection failed!\n");
        close(sockfd);
        return 1;
    }

    pollfd fds[2];
    // 0文件描述符为标准输入 注册可读事件POLLIN
    fds[0].fd = 0;
    fds[0].events = POLLIN;
    fds[0].revents = 0;

    // sockfd文件描述符为监听的端口 注册可读事件POLLIN和对方关闭连接事件POLLRDHUP
    fds[1].fd = sockfd;
    fds[1].events = POLLIN | POLLRDHUP;
    fds[1].revents = 0;

    char read_buf[BUFFER_SIZE];
    int pipefd[2];
    int ret = pipe(pipefd);
    assert(ret != -1);

    while (1) {
        ret = poll(fds, 2, -1);
        if (ret < 0) {
            printf("poll failure\n");
            break;
        }

        if (fds[1].revents & POLLRDHUP) {
            printf("server close the connection");
            break;
        } else if (fds[1].revents & POLLIN) {
            memset(read_buf, '\0', BUFFER_SIZE);
            recv(fds[1].fd, read_buf, BUFFER_SIZE - 1, 0);
            printf("%s\n", read_buf);
        }

        if (fds[0].revents & POLLIN) {
            // 零拷贝 0 -> sockfd
            ret = splice(0, NULL, pipefd[1], NULL, 32768, SPLICE_F_MORE | SPLICE_F_MOVE);
            ret = splice(pipefd[0], NULL, sockfd, NULL, 32768, SPLICE_F_MORE | SPLICE_F_MOVE);
        }
    }
    close(sockfd);
    return 0;
}

服务器：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
#define _GNU_SOURCE 1
#include <sys/types.h>
#include <sys/socket.h>
#include <netinet/in.h>
#include <arpa/inet.h>
#include <assert.h>
#include <stdio.h>
#include <unistd.h>
#include <errno.h>
#include <string.h>
#include <fcntl.h>
#include <stdlib.h>
#include <poll.h>

#define USER_LIMIT 5
#define BUFFER_SIZE 64
#define FD_LIMIT 65535

struct client_data
{
    sockaddr_in address;
    char* write_buf;
    char buf[BUFFER_SIZE];
};

int setnonblocking(int fd)
{
    int old_option = fcntl(fd, F_GETFL);
    int new_option = old_option | O_NONBLOCK;
    fcntl(fd, F_SETFL, new_option);
    return old_option;
}

int main(int argc, char* argv[])
{
    if (argc <= 2) {
        printf("usage: %s ip_address portnumber\n", basename(argv[0]));
        return 1;
    }
    const char* ip = argv[1];
    int port = atoi(argv[2]);

    int ret = 0;
    struct sockaddr_in address;
    bzero(&address, sizeof(address));
    address.sin_family = AF_INET;
    inet_pton(AF_INET, ip, &address.sin_addr);
    address.sin_port = htons(port);

    int listenfd = socket(PF_INET, SOCK_STREAM, 0);
    assert(listenfd >= 0);

    ret = bind(listenfd, (struct sockaddr*)&address, sizeof(address));
    assert(ret != 1);

    ret = listen(listenfd, 5);
    assert(ret != -1);

    client_data* users = new client_data[FD_LIMIT];

    pollfd fds[USER_LIMIT + 1];
    int user_counter = 0;
    for (int i = 1; i <= USER_LIMIT; i++) {
        fds[i].fd = -1;
        fds[i].events = 0;
    }
    // 注册事件：监听端口是否可读或者出现错误
    fds[0].fd = listenfd;
    fds[0].events = POLLIN | POLLERR;
    fds[0].revents = 0;

    while (1) {
        ret = poll(fds, user_counter + 1, -1);
        if (ret < 0) {
            printf("poll failure\n");
            break;
        }

        for (int i = 0; i < user_counter + 1; i++) {
            if ((fds[i].fd == listenfd) && (fds[i].revents & POLLIN)) {
                struct sockaddr_in client_address;
                socklen_t client_addrlength = sizeof(client_address);
                int connfd = accept(listenfd, (struct sockaddr*)&client_address, &client_addrlength);

                if (connfd < 0) {
                    printf("errno is: %d\n", errno);
                    continue;
                }

                if (user_counter >= USER_LIMIT) {
                    const char* info = "too many users\n";
                    printf("%s", info);
                    send(connfd, info, strlen(info), 0);
                    close(connfd);
                    continue;
                }

                user_counter++;
                users[connfd].address = client_address;
                setnonblocking(connfd);
                // 用于和新连接进来的客户的交互的文件描述符connfd
                fds[user_counter].fd = connfd;
                fds[user_counter].events = POLLIN | POLLRDHUP | POLLERR;
                fds[user_counter].revents = 0;
                printf("comes a new user, now have %d users\n", user_counter);
            } else if (fds[i].revents & POLLERR) { // 某个和用户连接出错了
                printf("get an error from %d\n", fds[i].fd);
                char errors[100];
                memset(errors, '\0', 100);
                socklen_t length = sizeof(errors);
                if (getsockopt(fds[i].fd, SOL_SOCKET, SO_ERROR, &errors, &length) < 0) {
                    printf("get socket options failed]n");
                }
                continue;
            } else if (fds[i].revents & POLLRDHUP) { // 用户断开了连接
                users[fds[i].fd] = users[fds[user_counter].fd];
                close(fds[i].fd);
                fds[i] = fds[user_counter];
                i--;
                user_counter--;
                printf("a client left\n");
            } else if (fds[i].revents & POLLIN) { // 用户连接可读，表示用户发送了数据过来
                int connfd = fds[i].fd;
                memset(users[connfd].buf, '\0', BUFFER_SIZE);
                ret = recv(connfd, users[connfd].buf, BUFFER_SIZE - 1, 0);
                printf("get %d bytes of client data %s from %d\n", ret, users[connfd].buf, connfd);
                if (ret < 0) {
                    if (errno != EAGAIN) {
                        close(connfd);
                        users[fds[i].fd] = users[fds[user_counter].fd];
                        fds[i] = fds[user_counter];
                        i--;
                        user_counter--;
                    }
                } else if (ret == 0) { // 对方关闭了连接 此时有POLLHUP处理

                } else {
                    for (int j = 1; j <= user_counter; j++) {
                        if (fds[j].fd == connfd) {
                            continue;
                        }

                        fds[j].events |= ~POLLIN; // 原书这里是这样写的 目的为注销可读。但是本人认为应该是 &= ，下同。
                        fds[j].events |= POLLOUT;
                        users[fds[j].fd].write_buf = users[connfd].buf; // 其他用户的buf写上当前收到的某fd所发送的信息
                    }
                }
            } else if (fds[i].revents & POLLOUT) { // 用户连接可写，把buffer信息写进去
                int connfd = fds[i].fd;
                if (!users[connfd].write_buf) {
                    continue;
                }
                ret = send(connfd, users[connfd].write_buf, strlen(users[connfd].write_buf), 0);
                users[connfd].write_buf = NULL;
                fds[i].events |= ~POLLOUT;
                fds[i].events |= POLLIN;
            }
        }
    }
    delete[] users;
    close(listenfd);
    return 0;

}

演示结果：
服务器：
在这里插入图片描述

客户端1:
客户端发送：client 1 : 1111111

客户端2:
客户端发送：client 2 : 2222222

reference：
linux高性能服务器编程——游双

发表于 更新于 分类于
本文字数： 232 阅读时长 ≈ 1 分钟

定义

假设有如下场景：函数 A 调用了函数 B。寄存器 %rbx 需要在调用 B 函数前后保持一致。

1
2
3
4
5
6
7
func A:
    ...
    call func B
    ...

func B:
    ...

调用者保存寄存器：\color{red}{调用者保存寄存器：}

1
2
3
4
5
6
7
8
9
func A:
    ...
    save register %rbx
    call func B
    restore register %rbx
    ...

func B:
    ...

如上图所示，寄存器 %rbx 是由函数 B 的调用者，即函数 func A 来保存并且恢复的。函数 B 感知不到这个情况，可以尽情使用寄存器 %rbx。

被调用者保存寄存器：\color{red}{被调用者保存寄存器：}

1
2
3
4
5
6
7
8
9
func A:
    ...
    call func B
    ...

func B:
    save register %rbx
    ...
    restore register %rbx

如图所示，寄存器 %rbx 是由被调用函数，即函数 B 来保存并回复的。函数 A 感知不到这个情况。

寄存器分类

不同的寄存器有不同的保存策略。
callee saved(被调用者保存）：\color{red}{callee \ saved(被调用者保存）：}

%rbx ，%rbp，%r12，%r13，%r14，%r15

caller saved(调用者保存)：\color{red}{caller \ saved(调用者保存)：}

%rax，%rdi，%rsi，%rdx，%rcx，%8，%r9，%r10，%r11

发表于 更新于 分类于
本文字数： 378 阅读时长 ≈ 1 分钟

定理内容：
aa为自然数，pp为一个质数。则有

ap≡a (mod p)a^p \equiv a\ (mod\ p)

其中 ≡\equiv 是同模符号，表示左右的数字对于p来说取模，是相等的。
证明：
数学归纳法

  1. 当a=1a = 1时， 显然成立。
  2. 当a=aa = a时，设 p∣(ap−a)p|(a^p - a)，即pp为ap−aa^p - a的约数。
  3. 则当a=a+1a = a + 1时， 尝试证明 p∣((a+1)p−(a+1))p | ((a + 1)^p - (a + 1))。
    证明如下：
    根据二项式定理，展开该项：

(a+1)p−(a+1)=∑k=0pCpkak1p−k−a−1=Cp0a01p+∑k=1p−1Cpkak1p−k+Cppap10−a−1=1+∑k=1p−1Cpkak1p−k+ap−a−1=∑k=1p−1Cpkak1p−k+ap−a\begin{aligned} (a + 1)^p - (a + 1) &= \sum_{k=0}^{p}C_p^ka^k1^{p-k} -a - 1 \\ &= C_p^0a^01^p + \sum_{k=1}^{p-1}C_p^ka^k1^{p-k} + C_p^pa^p1^0 - a - 1 \\ &= 1 + \sum_{k=1}^{p-1}C_p^ka^k1^{p-k} + a^p - a - 1 \\ &= \sum_{k=1}^{p-1}C_p^ka^k1^{p-k} + a^p - a \end{aligned}

因为Cpk=p!k!(p−k)!C_p^k = \frac{p!}{k!(p - k)!}并且pp为质数，所以pp为∑k=1p−1Cpkak1p−k\sum_{k=1}^{p-1}C_p^ka^k1^{p-k}的因数，即 p ∣∑k=1p−1Cpkak1p−kp\ | \sum_{k=1}^{p-1}C_p^ka^k1^{p-k}。
又因为由假设2可知pp为ap−aa^p - a的因数。所以pp为∑k=1p−1Cpkak1p−k+ap−a\sum_{k=1}^{p-1}C_p^ka^k1^{p-k} + a^p - a的因数，即为(a+1)p−(a+1)(a + 1)^p - (a + 1)的因数。证毕。

应用：
如果aa不是pp的倍数，那么还有

ap−1≡1 (mod p)a^{p - 1} \equiv 1\ (mod\ p)

所以可以用上式解决一些问题，如计算21002^{100}模13。
因为2不是13的倍数，则213−1≡1(mod 13)2^{13 - 1} \equiv 1 (mod \ 13)。

2100=212∗8+4 (mod 13)=(212)8∗24 (mod 13)=18∗24 (mod 13)=16 (mod 13)=3\begin{aligned} 2^{100} &= 2^{12 * 8 + 4} \ (mod \ 13)\\ &= (2^{12})^8 * 2^4\ (mod \ 13)\\ &= 1^8 * 2^4\ (mod \ 13)\\ &= 16\ (mod\ 13)\\ &= 3 \end{aligned}

reference:

  1. https://zhuanlan.zhihu.com/p/87611586
  2. https://www.cnblogs.com/-citywall123/p/10673191.html

发表于 更新于 分类于
本文字数： 528 阅读时长 ≈ 2 分钟

linux 服务器高级编程ET LT代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#include<sys/types.h>
#include<sys/socket.h>
#include<netinet/in.h>
#include<arpa/inet.h>
#include<assert.h>
#include<stdio.h>
#include<unistd.h>
#include<errno.h>
#include<string.h>
#include<fcntl.h>
#include<stdlib.h>
#include<sys/epoll.h>
#include<pthread.h>

#define MAX_EVENT_NUMBER 1024
#define BUFFER_SIZE 10

int setnonblocking(int fd) 
{
    int old_option = fcntl(fd, F_GETFL);
    int new_option = old_option | O_NONBLOCK;
    fcntl(fd, F_SETFL, new_option);
    return old_option;
}

void addfd(int epollfd, int fd, bool enable_et) //在内核事件表中为fd注册事件
{
    epoll_event event;
    event.data.fd = fd;
    event.events = EPOLLIN;
    if (enable_et)
    {
        event.events |= EPOLLET;
    }
    epoll_ctl(epollfd, EPOLL_CTL_ADD, fd, &event); // 操作内核事件表的函数
    setnonblocking(fd);
}

void lt(epoll_event* events, int number, int epollfd, int listenfd)
{
    char buf[BUFFER_SIZE];
    for (int i = 0; i < number; i++) {
        int sockfd = events[i].data.fd;
        if (sockfd == listenfd) {
            struct sockaddr_in client_address;
            socklen_t client_addrlength = sizeof(client_address);
            int connfd = accept(listenfd, (struct sockaddr*)&client_address, &client_addrlength);
            addfd(epollfd, connfd, false);
            printf("connect fd:%d listenfd=%d\n", connfd, listenfd);
        } else if (events[i].events & EPOLLIN) {
            printf("event trigger once\n");
            memset(buf, '\0', BUFFER_SIZE);
            int ret = recv(sockfd, buf, BUFFER_SIZE - 1, 0);
            printf("socket fd:%d listenfd=%d\n", sockfd, listenfd);
            if (ret < 0) {
                close(sockfd);
                continue;
            }
            printf("get %d bytes of content: %s\n", ret, buf);
        } else {
            printf("sth else happend\n");
        }
    }
}

void et(epoll_event* events, int number, int epollfd, int listenfd)
{
    char buf[BUFFER_SIZE];
    for (int i = 0 ; i < number; i++) {
        int sockfd = events[i].data.fd;
        if (sockfd == listenfd) {
            struct sockaddr_in client_address;
            socklen_t client_addrlength = sizeof(client_address);
            int connfd = accept(listenfd, (struct sockaddr*)&client_address, &client_addrlength);
            addfd(epollfd, connfd, true);
        } else if (events[i].events & EPOLLIN) {
            printf("event trigger once\n");
            while (1) {
                memset(buf, '\0', BUFFER_SIZE);
                int ret = recv(sockfd, buf, BUFFER_SIZE - 1, 0);
                if (ret < 0) {
                    if ((errno == EAGAIN) || (errno == EWOULDBLOCK)) {
                        printf("read later\n");
                        break;
                    }
                    close(sockfd);
                    break;
                } else if (ret == 0) {
                    close(sockfd);
                } else {
                    printf("get %d bytes of content:%s\n", ret, buf);
                }
            }
        } else {
            printf("nothing happend\n");
        }
    }
}

int main(int argc, char* argv[]) 
{
    if (argc <= 2) {
        printf("usage: %s ip_address port_number\n", basename(argv[0]));
        return 1;
    }
    const char* ip = argv[1];
    int port = atoi(argv[2]);

    int ret = 0;
    struct sockaddr_in address;
    bzero(&address, sizeof(address));
    address.sin_family = AF_INET;
    inet_pton(AF_INET, ip, &address.sin_addr);
    address.sin_port = htons(port);

    int listenfd = socket(PF_INET, SOCK_STREAM, 0);
    assert(listenfd >= 0);

    ret = bind(listenfd, (struct sockaddr*)&address, sizeof(address));
    assert(ret != -1);

    ret = listen(listenfd, 5);
    assert(ret != -1);

    epoll_event events[MAX_EVENT_NUMBER];
    int epollfd = epoll_create(5);
    addfd(epollfd, listenfd, true);

    while(1) {
        int ret = epoll_wait(epollfd, events, MAX_EVENT_NUMBER, -1);
        if (ret < 0) {
            printf("epoll fail\n");
            break;
        }
        // lt(events, ret, epollfd, listenfd);
        et(events, ret, epollfd, listenfd);
    }

    close(listenfd);
    return 0;
}

ET:
1
ET模式下需要一次性处理完所有数据，下次就不会加入到epoll_wait的事件中了。

LT:
2
LT模式下未处理完的事件还是会被加入到epoll_wait监听的事件中。

reference：
linux高性能服务器编程——游双P153-P157