矩阵快速幂

发表于 2022-02-26 更新于 2023-12-25 分类于 algorithm
本文字数： 710 阅读时长 ≈ 3 分钟

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

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];
}

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

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

设矩阵 $\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}$ 为 $P$ 。
则有

[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

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

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;
}

完整代码如下:

#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();
}

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

快速幂cpp代码

发表于 2022-02-26 更新于 2023-12-25 分类于 algorithm
本文字数： 491 阅读时长 ≈ 2 分钟

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

using ll = long long;
ll pow(ll a, ll n)
{
    ll ret = 1;
    for (ll i = 0; i < n; i++) {
        ret *= a;
    }
    return ret;
}

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

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;
}

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

#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周期普遍低于前一种。

cpp STL: priority_queue自定义排序函数

发表于 2022-02-25 更新于 2023-12-25 分类于 cpp
本文字数： 679 阅读时长 ≈ 2 分钟

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

struct node {
    int x;
    int y;
};

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

1. 仿函数（函数对象）

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

#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;
}

结果：

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

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

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

#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;
}

结果：

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

3. 使用lambda表达式

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

#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;
}

结果：

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

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

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

#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;
}

结果：

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

reference：

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

linux io 复用高级应用2：聊天室程序

发表于 2022-02-16 更新于 2023-12-25 分类于 socket-programming
本文字数： 993 阅读时长 ≈ 4 分钟

客户端：

#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;
}

服务器：

#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:

客户端2:

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

调用者保存寄存器和非调用者保存寄存器

发表于 2022-02-15 更新于 2023-12-25 分类于 linux
本文字数： 232 阅读时长 ≈ 1 分钟

定义

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

func A:
    ...
    call func B
    ...

func B:
    ...

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

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

func B:
    ...

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

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

func A:
    ...
    call func B
    ...

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

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

寄存器分类

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

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

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

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

费马小定理

发表于 2022-02-14 更新于 2023-12-25 分类于 algorithm
本文字数： 378 阅读时长 ≈ 1 分钟

定理内容：
$a$ 为自然数， $p$ 为一个质数。则有

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

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

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

\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}

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

应用：
如果 $a$ 不是 $p$ 的倍数，那么还有

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

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

\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:

linux 高级服务器编程ET LT

发表于 2022-02-11 更新于 2023-12-25 分类于 socket-programming
本文字数： 528 阅读时长 ≈ 2 分钟

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

#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:

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

LT:

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

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