ToRapture's Blog

A Programmer

0%

Posted on Edited on Disqus:

基本TCP客户端与服务器

Server

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
#include <cstdio>
#include <cstring>

#include <string>
#include <vector>

#include <unistd.h>
#include <arpa/inet.h>
#include <sys/errno.h>
#include <sys/socket.h>
#include <netinet/in.h>
#include <string>

using namespace std;

const int BUF_SIZE = 1024;

string addr_to_string(const sockaddr_in *addr) {
    char addr_str[INET_ADDRSTRLEN];
    const char *addr_str_ptr = inet_ntop(AF_INET, &addr->sin_addr, addr_str, sizeof(addr_str));
    if (addr_str_ptr == NULL) {
        fprintf(stderr, "inet_ntop failed\n");
        return "";
    }
    return string(addr_str_ptr) + ":" + to_string(ntohs(addr->sin_port));
}

string get_sockname_string(int sockfd) {
    sockaddr_in addr;
    socklen_t len = sizeof(addr);
    if (getsockname(sockfd, (sockaddr *) &addr, &len) == -1) {
        fprintf(stderr, "getsockname failed\n");
        return "";
    }
    return addr_to_string(&addr);
}

string get_peername_string(int sockfd) {
    sockaddr_in addr;
    socklen_t len = sizeof(addr);
    if (getpeername(sockfd, (sockaddr *) &addr, &len) == -1) {
        fprintf(stderr, "getpeername failed, errno: %d, str: %s\n", errno, strerror(errno));
        return "";
    }
    return addr_to_string(&addr);
}


int init_server(int type, const sockaddr *addr, socklen_t alen, int qlen) {
    int fd;
    if ((fd = socket(addr->sa_family, type, 0)) == -1) {
        fprintf(stderr, "create socket failed, errno: %d, str: %s\n", errno, strerror(errno));
        return -1;
    }
    printf("create socket fd: %d, sock_name: %s, peer_name: %s\n", fd, get_sockname_string(fd).c_str(), get_peername_string(fd).c_str());

    if (bind(fd, addr, alen) == -1) {
        fprintf(stderr, "bind failed, errno: %d, str: %s\n", errno, strerror(errno));
        close(fd);
        return -1;
    }
    printf("bind socket fd: %d, sock_name: %s, peer_name: %s\n", fd, get_sockname_string(fd).c_str(), get_peername_string(fd).c_str());

    if (type == SOCK_STREAM || type == SOCK_SEQPACKET) {
        if (listen(fd, qlen) == -1) {
            fprintf(stderr, "listen failed, errno: %d, str: %s\n", errno, strerror(errno));
            close(fd);
            return -1;
        }
        printf("listen fd: %d, sock_name: %s, peer_name: %s\n", fd, get_sockname_string(fd).c_str(), get_peername_string(fd).c_str());
    }
    return fd;
}

int main(int argc, char **argv) {
    int sleep_before_recv = 0;
    int sleep_after_listen = 0;
    int qlen = 0;
    int port = 27015;
    char *ip = "0.0.0.0";

    for (int i = 1; i < argc;) {
        if (argv[i] == string("--port")) {
            port = atoi(argv[i + 1]);
            i += 2;
            continue;
        }
        if (argv[i] == string("--qlen")) {
            qlen = atoi(argv[i + 1]);
            i += 2;
            continue;
        }
        if (argv[i] == string("--sleep-before-recv")) {
            sleep_before_recv = atoi(argv[i + 1]);
            i += 2;
            continue;
        }
        if (argv[i] == string("--sleep-after-listen")) {
            sleep_after_listen = atoi(argv[i + 1]);
            i += 2;
            continue;
        }
        if (argv[i] == string("--ip")) {
            ip = argv[i + 1];
            i += 2;
            continue;
        }
        i++;
    }

    printf("port: %d, qlen: %d, sleep-before-recv: %d, sleep-after-listen: %d\n", port, qlen, sleep_before_recv, sleep_after_listen);

    sockaddr_in addr;
    bzero(&addr, sizeof(addr)); // APUE 16.3.2 其中成员sin_zero为填充字段，应该全部被置为0
    addr.sin_family = AF_INET;
    inet_pton(addr.sin_family, ip, &addr.sin_addr);
    addr.sin_port = htons(port);

    int sockfd = init_server(SOCK_STREAM, (sockaddr *) &addr, sizeof(addr), qlen);
    if (sockfd == -1) return -1;

    sleep(sleep_after_listen);

    while (true) {
        int clfd, n;
        sockaddr_in accepted_addr;
        socklen_t len = sizeof(accepted_addr);

        if ((clfd = accept(sockfd, (sockaddr *) &accepted_addr, &len)) == -1) {
            fprintf(stderr, "accept failed, errno: %d, str: %s\n", errno, strerror(errno));
            continue;
        }
        printf("after accept sockfd: %d, sock_name: %s, peer_name: %s\n",
               sockfd, get_sockname_string(sockfd).c_str(), get_peername_string(sockfd).c_str());
        printf("accepted fd: %d, sock_name: %s, peer_name: %s, addr: %s\n",
               clfd, get_sockname_string(clfd).c_str(), get_peername_string(clfd).c_str(), addr_to_string(&accepted_addr).c_str());

        sleep(sleep_before_recv);
        char buf[BUF_SIZE];
        if ((n = recv(clfd, buf, BUF_SIZE - 1, 0)) == -1) {
            fprintf(stderr, "recv failed, errno: %d, str: %s\n", errno, strerror(errno));
            close(clfd);
            continue;
        }
        buf[n] = '\0';
        printf("read %d bytes from fd: %d, buf: %s\n", n, clfd, buf);
        close(clfd);
    }

    return 0;
}

如果调用getsockname时没有地址绑定到传入的套接字，则其结果是未定义的。1

Client

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
#include <cstdio>
#include <cstring>

#include <vector>
#include <string>

#include <unistd.h>
#include <arpa/inet.h>
#include <sys/errno.h>
#include <sys/socket.h>
#include <netinet/in.h>

using namespace std;

const int BUF_SIZE = 1024;

string addr_to_string(const sockaddr_in *addr) {
    char addr_str[INET_ADDRSTRLEN];
    const char *addr_str_ptr = inet_ntop(AF_INET, &addr->sin_addr, addr_str, sizeof(addr_str));
    if (addr_str_ptr == NULL) {
        fprintf(stderr, "inet_ntop failed\n");
        return "";
    }
    return string(addr_str_ptr) + ":" + to_string(ntohs(addr->sin_port));
}

string get_sockname_string(int sockfd) {
    sockaddr_in addr;
    socklen_t len = sizeof(addr);
    if (getsockname(sockfd, (sockaddr *) &addr, &len) == -1) {
        fprintf(stderr, "getsockname failed\n");
        return "";
    }
    return addr_to_string(&addr);
}

string get_peername_string(int sockfd) {
    sockaddr_in addr;
    socklen_t len = sizeof(addr);
    if (getpeername(sockfd, (sockaddr *) &addr, &len) == -1) {
        fprintf(stderr, "getpeername failed, errno: %d, str: %s\n", errno, strerror(errno));
        return "";
    }
    return addr_to_string(&addr);
}

int main(int argc, char **argv) {
    int port = 27015;
    char *ip = "0.0.0.0";
    for (int i = 1; i < argc;) {
        if (argv[i] == string("--port")) {
            port = atoi(argv[i + 1]);
            i += 2;
            continue;
        }
        if (argv[i] == string("--ip")) {
            ip = argv[i + 1];
            i += 2;
            continue;
        }
        i++;
    }


    sockaddr_in addr;
    bzero(&addr, sizeof(addr));
    addr.sin_family = AF_INET;
    addr.sin_port = htons(port);
    if (inet_pton(addr.sin_family, ip, &addr.sin_addr) <= 0) {
        fprintf(stderr, "inet_pton failed\n");
        return -1;
    }

    int sockfd = socket(addr.sin_family, SOCK_STREAM, 0);
    if (sockfd == -1) {
        fprintf(stderr, "create socket failed, errno: %d, str: %s\n", errno, strerror(errno));
        return -1;
    }
    printf("fd: %d, sock_name: %s, peer_name: %s\n", sockfd, get_sockname_string(sockfd).c_str(), get_peername_string(sockfd).c_str());

    if (connect(sockfd, (sockaddr *) &addr, sizeof(addr)) == -1) {
        fprintf(stderr, "connect failed, errno: %d, str: %s\n", errno, strerror(errno));
        close(sockfd);
        return -1;
    }
    printf("fd: %d, sock_name: %s, peer_name: %s\n", sockfd, get_sockname_string(sockfd).c_str(), get_peername_string(sockfd).c_str());

    vector<string> msgs = {"hello", "world", "cpp"};
    for (const auto &msg : msgs) {
        int n = send(sockfd, msg.c_str(), msg.size(), 0);
        if (n == -1) {
            fprintf(stderr, "send failed, errno: %d, str: %s\n", errno, strerror(errno));
            break;
        }
        printf("fd: %d, send %d bytes\n", sockfd, n);
    }
    close(sockfd);

    return 0;
}

Read

建连后客户端调用三次send，服务端在recv之前sleep 0秒

server: 

1
2
3
4
5
6
7
8
9
10
11
12
13
$ ./server --sleep-before-recv 0
port: 27015, qlen: 0, sleep-before-recv: 0, sleep-after-listen: 0
getpeername failed, errno: 57, str: Socket is not connected
create socket fd: 3, sock_name: 0.0.0.0:0, peer_name:
getpeername failed, errno: 57, str: Socket is not connected
bind socket fd: 3, sock_name: 0.0.0.0:27015, peer_name:
getpeername failed, errno: 57, str: Socket is not connected
listen fd: 3, sock_name: 0.0.0.0:27015, peer_name:
getpeername failed, errno: 57, str: Socket is not connected
after accept sockfd: 3, sock_name: 0.0.0.0:27015, peer_name:
accepted fd: 4, sock_name: 127.0.0.1:27015, peer_name: 127.0.0.1:59932, addr: 127.0.0.1:59932
read 5 bytes from fd: 4, buf: hello
^C

client: 

1
2
3
4
5
6
7
$ ./client
getpeername failed, errno: 57, str: Socket is not connected
fd: 3, sock_name: 0.0.0.0:0, peer_name:
fd: 3, sock_name: 127.0.0.1:59932, peer_name: 127.0.0.1:27015
fd: 3, send 5 bytes
fd: 3, send 5 bytes
fd: 3, send 3 bytes

建连后客户端调用三次send，服务端在recv之前sleep 5秒

server: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
$ ./server --sleep-before-recv 5
port: 27015, qlen: 0, sleep-before-recv: 5, sleep-after-listen: 0
getpeername failed, errno: 57, str: Socket is not connected
create socket fd: 3, sock_name: 0.0.0.0:0, peer_name:
getpeername failed, errno: 57, str: Socket is not connected
bind socket fd: 3, sock_name: 0.0.0.0:27015, peer_name:
getpeername failed, errno: 57, str: Socket is not connected
listen fd: 3, sock_name: 0.0.0.0:27015, peer_name:
getpeername failed, errno: 57, str: Socket is not connected
after accept sockfd: 3, sock_name: 0.0.0.0:27015, peer_name:
accepted fd: 4, sock_name: 127.0.0.1:27015, peer_name: 127.0.0.1:60018, addr: 127.0.0.1:60018
# 五秒后
read 13 bytes from fd: 4, buf: helloworldcpp
^C

client: 先执行服务端，再执行客户端，客服端执行完三次send后未等服务端read就已返回 

1
2
3
4
5
6
7
$ ./client
getpeername failed, errno: 57, str: Socket is not connected
fd: 3, sock_name: 0.0.0.0:0, peer_name:
fd: 3, sock_name: 127.0.0.1:60018, peer_name: 127.0.0.1:27015
fd: 3, send 5 bytes
fd: 3, send 5 bytes
fd: 3, send 3 bytes

Listen Backlog

backlog传2

server: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
$ ./server --sleep-after-listen 10 --qlen 2
port: 27015, qlen: 2, sleep-before-recv: 0, sleep-after-listen: 10
getpeername failed, errno: 57, str: Socket is not connected
create socket fd: 3, sock_name: 0.0.0.0:0, peer_name:
getpeername failed, errno: 57, str: Socket is not connected
bind socket fd: 3, sock_name: 0.0.0.0:27015, peer_name:
getpeername failed, errno: 57, str: Socket is not connected
listen fd: 3, sock_name: 0.0.0.0:27015, peer_name:
# sleep here
getpeername failed, errno: 57, str: Socket is not connected
after accept sockfd: 3, sock_name: 0.0.0.0:27015, peer_name:
accepted fd: 4, sock_name: 127.0.0.1:27015, peer_name: 127.0.0.1:63689, addr: 127.0.0.1:63689
read 13 bytes from fd: 4, buf: helloworldcpp
getpeername failed, errno: 57, str: Socket is not connected
after accept sockfd: 3, sock_name: 0.0.0.0:27015, peer_name:
accepted fd: 4, sock_name: 127.0.0.1:27015, peer_name: 127.0.0.1:63690, addr: 127.0.0.1:63690
read 13 bytes from fd: 4, buf: helloworldcpp
getpeername failed, errno: 57, str: Socket is not connected
after accept sockfd: 3, sock_name: 0.0.0.0:27015, peer_name:
accepted fd: 4, sock_name: 127.0.0.1:27015, peer_name: 127.0.0.1:63691, addr: 127.0.0.1:63691
read 13 bytes from fd: 4, buf: helloworldcpp
^C

client: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
$ ./client
getpeername failed, errno: 57, str: Socket is not connected
fd: 3, sock_name: 0.0.0.0:0, peer_name:
fd: 3, sock_name: 127.0.0.1:63689, peer_name: 127.0.0.1:27015
fd: 3, send 5 bytes
fd: 3, send 5 bytes
fd: 3, send 3 bytes
$ ./client
getpeername failed, errno: 57, str: Socket is not connected
fd: 3, sock_name: 0.0.0.0:0, peer_name:
fd: 3, sock_name: 127.0.0.1:63690, peer_name: 127.0.0.1:27015
fd: 3, send 5 bytes
fd: 3, send 5 bytes
fd: 3, send 3 bytes
$ ./client
getpeername failed, errno: 57, str: Socket is not connected
fd: 3, sock_name: 0.0.0.0:0, peer_name:
# block here
fd: 3, sock_name: 127.0.0.1:63691, peer_name: 127.0.0.1:27015
fd: 3, send 5 bytes
fd: 3, send 5 bytes
fd: 3, send 3 bytes

backlog传0

参数backlog提供了一个提示，提示系统该进程所要入队的未完成连接请求数量。其实际值由系统决定。具体的最大值取决于每个协议的实现。对于TCP，其默认值为128。2 通过下面的脚本，在macOs上测试，验证了TCP的默认值为128。

run-server.sh 

1
2
3
4
5
6
7
#!/bin/bash

for i in {1..256}; do
    echo "do $i"
    ./client 1>/dev/null 2>&1
    echo "$i finished"
done

server: 

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
$ ./server --sleep-after-listen 10
port: 27015, qlen: 0, sleep-before-recv: 0, sleep-after-listen: 10
getpeername failed, errno: 57, str: Socket is not connected
create socket fd: 3, sock_name: 0.0.0.0:0, peer_name:
getpeername failed, errno: 57, str: Socket is not connected
bind socket fd: 3, sock_name: 0.0.0.0:27015, peer_name:
getpeername failed, errno: 57, str: Socket is not connected
listen fd: 3, sock_name: 0.0.0.0:27015, peer_name:
# sleep here
getpeername failed, errno: 57, str: Socket is not connected
after accept sockfd: 3, sock_name: 0.0.0.0:27015, peer_name:
accepted fd: 4, sock_name: 127.0.0.1:27015, peer_name: 127.0.0.1:63789, addr: 127.0.0.1:63789
read 13 bytes from fd: 4, buf: helloworldcpp
getpeername failed, errno: 57, str: Socket is not connected
after accept sockfd: 3, sock_name: 0.0.0.0:27015, peer_name:
accepted fd: 4, sock_name: 127.0.0.1:27015, peer_name: 127.0.0.1:63790, addr: 127.0.0.1:63790
read 13 bytes from fd: 4, buf: helloworldcpp
................
getpeername failed, errno: 57, str: Socket is not connected
after accept sockfd: 3, sock_name: 0.0.0.0:27015, peer_name:
accepted fd: 4, sock_name: 127.0.0.1:27015, peer_name: 127.0.0.1:64050, addr: 127.0.0.1:64050
read 5 bytes from fd: 4, buf: hello
getpeername failed, errno: 57, str: Socket is not connected
after accept sockfd: 3, sock_name: 0.0.0.0:27015, peer_name:
accepted fd: 4, sock_name: 127.0.0.1:27015, peer_name: 127.0.0.1:64051, addr: 127.0.0.1:64051
read 13 bytes from fd: 4, buf: helloworldcpp
^C

client: 

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
$ ./run-server.sh
do 1
1 finished
do 2
2 finished
do 3
3 finished
do 4
4 finished
..................
do 126
126 finished
do 127
127 finished
do 128
128 finished
do 129
# block here
129 finished
do 130
130 finished
do 131
131 finished
do 132
132 finished
..................
do 255
255 finished
do 256
256 finished

INADDR_ANY

对于因特网域，如果指定IP地址为INADDR_ANY(<netinet/in.h>中定义的)，套接字端点可以被绑定到所有的系统网络接口上。这意味着可以接收这个系统所安装的任何一个网卡的数据包。如果调用connect或listen，但没有将地址绑定到套接字上，系统会选择一个地址绑定到套接字上。3

可以注意到下面在bind 0.0.0.0后的sockfd在getsockname后得到的ip是0.0.0.0，在accept得到的fd上getsockname后得到的ip才是127.0.0.1或other-ip，而bind other-ip后的sockfd在getsockname后得到的ip就是other-ip。

Bind 0.0.0.0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
$ ./server
$ ./server --ip 0.0.0.0
port: 27015, qlen: 0, sleep-before-recv: 0, sleep-after-listen: 0
getpeername failed, errno: 57, str: Socket is not connected
create socket fd: 3, sock_name: 0.0.0.0:0, peer_name:
getpeername failed, errno: 57, str: Socket is not connected
bind socket fd: 3, sock_name: 0.0.0.0:27015, peer_name:
getpeername failed, errno: 57, str: Socket is not connected
listen fd: 3, sock_name: 0.0.0.0:27015, peer_name:
getpeername failed, errno: 57, str: Socket is not connected
after accept sockfd: 3, sock_name: 0.0.0.0:27015, peer_name:
accepted fd: 4, sock_name: other-ip:27015, peer_name: other-ip:62771, addr: other-ip:62771
read 5 bytes from fd: 4, buf: hello
getpeername failed, errno: 57, str: Socket is not connected
after accept sockfd: 3, sock_name: 0.0.0.0:27015, peer_name:
accepted fd: 4, sock_name: 127.0.0.1:27015, peer_name: 127.0.0.1:62772, addr: 127.0.0.1:62772
read 13 bytes from fd: 4, buf: helloworldcpp
^C
1
2
3
4
5
6
7
8
9
10
11
12
13
$ ./client --ip other-ip
getpeername failed, errno: 57, str: Socket is not connected
fd: 3, sock_name: 0.0.0.0:0, peer_name:
fd: 3, sock_name: other-ip:62771, peer_name: other-ip:27015
fd: 3, send 5 bytes
fd: 3, send 5 bytes
$ ./client --ip 127.0.0.1
getpeername failed, errno: 57, str: Socket is not connected
fd: 3, sock_name: 0.0.0.0:0, peer_name:
fd: 3, sock_name: 127.0.0.1:62772, peer_name: 127.0.0.1:27015
fd: 3, send 5 bytes
fd: 3, send 5 bytes
fd: 3, send 3 bytes

Bind other-ip

1
2
3
4
5
6
7
8
9
10
11
12
13
$ ./server --ip other-ip
port: 27015, qlen: 0, sleep-before-recv: 0, sleep-after-listen: 0
getpeername failed, errno: 57, str: Socket is not connected
create socket fd: 3, sock_name: 0.0.0.0:0, peer_name:
getpeername failed, errno: 57, str: Socket is not connected
bind socket fd: 3, sock_name: other-ip:27015, peer_name:
getpeername failed, errno: 57, str: Socket is not connected
listen fd: 3, sock_name: other-ip:27015, peer_name:
getpeername failed, errno: 57, str: Socket is not connected
after accept sockfd: 3, sock_name: other-ip:27015, peer_name:
accepted fd: 4, sock_name: other-ip:27015, peer_name: other-ip:62773, addr: other-ip:62773
read 13 bytes from fd: 4, buf: helloworldcpp
^C
1
2
3
4
5
6
7
8
9
10
11
$ ./client --ip other-ip
getpeername failed, errno: 57, str: Socket is not connected
fd: 3, sock_name: 0.0.0.0:0, peer_name:
fd: 3, sock_name: other-ip:62773, peer_name: other-ip:27015
fd: 3, send 5 bytes
fd: 3, send 5 bytes
fd: 3, send 3 bytes
$ ./client --ip 127.0.0.1
getpeername failed, errno: 57, str: Socket is not connected
fd: 3, sock_name: 0.0.0.0:0, peer_name:
connect failed, errno: 61, str: Connection refused

  1. 《UNIX环境高级编程》16.3.4↩︎

  2. 《UNIX环境高级编程》16.4↩︎

  3. 《UNIX环境高级编程》16.3.4↩︎

Posted on Edited on Disqus:

在标准输入上测试select

实现参考了《UNIX环境高级编程》14.4.1和《UNIX系统编程手册》63.2.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
#include <cstdio>
#include <iostream>
#include <unistd.h>
#include <fcntl.h>
#include <sys/select.h>

using namespace std;

const int BUF_SIZE = 128;

int main(int argc, char **argv) {
    fd_set rs;
    FD_ZERO(&rs);
    FD_SET(STDIN_FILENO, &rs);

    for (int i = 0; i < 5; i++) {
        timeval tv = {.tv_sec=2, .tv_usec=0};
        fd_set rs_temp = rs;
        int ret = select(STDIN_FILENO + 1, &rs_temp, NULL, NULL, &tv);
        if (ret == -1) {
            printf("select ret: %d, errno: %d\n", ret, errno);
            return 1;
        }
        printf("select ret: %d\n", ret);
        printf("if can read data from fd: %d is %s\n", STDIN_FILENO, FD_ISSET(STDIN_FILENO, &rs_temp) ? "true" : "false");
        if (FD_ISSET(STDIN_FILENO, &rs_temp)) {
            char buf[BUF_SIZE];
            int n = read(STDIN_FILENO, buf, 5);
            if (n == -1) {
                printf("read failed, errno: %d\n", errno);
                return 1;
            }
            buf[n] = '\0';
            printf("success read %d bytes, buf: %s\n", n, buf);
        }
    }

    return 0;
}
下面运行结果中第三行的hello world是在第一次循环结果打印后，第二次调用select阻塞时输入的。 运行结果： 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
select ret: 0
if can read data from fd: 0 is false
hello world
select ret: 1
if can read data from fd: 0 is true
success read 5 bytes, buf: hello
select ret: 1
if can read data from fd: 0 is true
success read 5 bytes, buf:  worl
select ret: 1
if can read data from fd: 0 is true
success read 2 bytes, buf: d

select ret: 0
if can read data from fd: 0 is false

Process finished with exit code 0

非阻塞I/O

一个描述符阻塞与否并不影响select是否阻塞。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
#include <cstdio>
#include <cstring>
#include <iostream>
#include <unistd.h>
#include <fcntl.h>
#include <errno.h>

const int BUF_SIZE = 128;

using namespace std;

void set_fl(int fd, int flags) {
    int val;
    if ((val = fcntl(fd, F_GETFL, 0)) < 0) {
        fprintf(stderr, "fcntl F_GETFL error\n");
        exit(1);
    }
    val |= flags;
    if (fcntl(fd, F_SETFL, val) < 0) {
        fprintf(stderr, "fcntl F_SETFL error\n");
        exit(1);
    }
}

int main(int argc, char **argv) {
    int n;
    char buf[128];

    set_fl(STDIN_FILENO, O_NONBLOCK);
    n = read(STDIN_FILENO, buf, BUF_SIZE - 1);
    printf("n: %d, errno: %d, str: %s\n", n, errno, strerror(errno));

    fd_set rs;
    FD_ZERO(&rs);
    FD_SET(STDIN_FILENO, &rs);

    for (int i = 0; i < 5; i++) {
        fd_set rs_temp = rs;
        timeval tv = {.tv_sec=2, .tv_usec=0};
        int ret = select(STDIN_FILENO + 1, &rs_temp, NULL, NULL, &tv);
        if (ret == -1) {
            fprintf(stderr, "select ret: %d, errno: %d, str: %s\n", ret, errno, strerror(errno));
            return 1;
        }
        printf("select ret: %d\n", ret);
        printf("if can read data from fd: %d is %s\n", STDIN_FILENO, FD_ISSET(STDIN_FILENO, &rs_temp) ? "true" : "false");
    }

    return 0;
}
执行结果： 
1
2
3
4
5
6
7
8
9
10
11
12
13
n: -1, errno: 35, str: Resource temporarily unavailable
select ret: 0
if can read data from fd: 0 is false
select ret: 0
if can read data from fd: 0 is false
select ret: 0
if can read data from fd: 0 is false
select ret: 0
if can read data from fd: 0 is false
select ret: 0
if can read data from fd: 0 is false

Process finished with exit code 0
可以看到代码首先对设置了非阻塞标志的标准输入读，read函数返回-1，每次select的返回结果也是0。

select阻塞中被信号中断

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
#include <cstdio>
#include <cstring>
#include <iostream>
#include <unistd.h>
#include <fcntl.h>
#include <errno.h>
#include <sys/select.h>

using namespace std;

void handler(int sig) {
    printf("caught signal: %d, str: %s\n", sig, strsignal(sig));
}

int main(int argc, char **argv) {
    signal(SIGUSR1, handler);

    int ret = select(0, NULL, NULL, NULL, NULL);
    printf("select ret: %d\n", ret);
    if (ret == -1) {
        printf("errno: %d, str: %s\n", errno, strerror(errno));
    }

    return 0;
}

运行后给进程发SIGUSR1信号。 

1
2
3
caught signal: 30, str: User defined signal 1: 30
select ret: -1
errno: 4, str: Interrupted system call

select支持的最大数量

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
#include <cstdio>
#include <cstring>
#include <iostream>
#include <unistd.h>
#include <fcntl.h>
#include <errno.h>
#include <sys/select.h>

using namespace std;

int main(int argc, char **argv) {
    timeval tv;
    int ret;

    printf("FD_SETSIZE: %d\n", FD_SETSIZE);

    tv = {.tv_sec=0, .tv_usec=0};
    ret = select(FD_SETSIZE, NULL, NULL, NULL, &tv);
    printf("select ret: %d\n", ret);
    if (ret == -1) {
        printf("errno: %d, str: %s\n", errno, strerror(errno));
    }

    tv = {.tv_sec=0, .tv_usec=0};
    ret = select(FD_SETSIZE + 1, NULL, NULL, NULL, &tv);
    printf("select ret: %d\n", ret);
    if (ret == -1) {
        printf("errno: %d, str: %s\n", errno, strerror(errno));
    }

    return 0;
}
1
2
3
4
5
6
FD_SETSIZE: 1024
select ret: 0
select ret: -1
errno: 22, str: Invalid argument

Process finished with exit code 0

在本机的macOs上$ uname -a的结果为Darwin localhost 19.0.0 Darwin Kernel Version 19.0.0: Thu Oct 17 16:17:15 PDT 2019; root:xnu-6153.41.3~29/RELEASE_X86_64 x86_64

The behavior of these macros is undefined if a descriptor value is less than zero or greater than or equal to FD_SETSIZE, which is normally at least equal to the maximum number of descriptors supported by the system.2

  1. 《UNIX环境高级编程》14.4.1↩︎

  2. SELECT(2) BSD System Calls Manual DESCRIPTION↩︎

Posted on Edited on Disqus:

打开、创建、关闭文件

test_create.cpp: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <cstdio>

#include <unistd.h>
#include <fcntl.h>

using namespace std;

int main(int argc, char **argv) {
    // 读、写打开，若不存在则创建，若已存在则出错
    int flags = O_RDWR | O_CREAT | O_EXCL;
    // 0644
    mode_t mode = S_IRUSR | S_IWUSR | S_IRGRP | S_IROTH;

    int fd = open("test_create.txt", flags, mode);
    printf("fd: %d\n", fd);
    if (fd != -1) {
        close(fd);
    }
    return 0;
}
1
2
3
4
5
6
7
8
$ ls test_create.txt
ls: test_create.txt: No such file or directory
$ ./test_create
fd: 3
$ ls -lh test_create.txt
-rw-r--r--  1 torapture  staff     0B 11 27 20:01 test_create.txt
$ ./test_create
fd: -1
由open函数返回的文件描述符一定是最小的未用描述符取值。1

读写

rw.cpp: 

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 <cstdio>

#include <vector>
#include <string>

#include <unistd.h>
#include <fcntl.h>

using namespace std;

int main(int argc, char **argv) {
    int flags = O_RDWR | O_CREAT;
    mode_t mode = S_IRUSR | S_IWUSR | S_IRGRP | S_IROTH;

    int fd = open("rw.txt", flags, mode);
    if (fd == -1) {
        printf("open file error\n");
        return 1;
    }

    printf("file opened, fd[%d]\n", fd);
    printf("cur_pos[%d]\n", lseek(fd, 0, SEEK_CUR));
    vector<string> msgs = {"hello", "world", "cpp"};
    for (const auto &msg : msgs) {
        int n = write(fd, msg.c_str(), msg.size());
        int cur_pos = lseek(fd, 0, SEEK_CUR);
        printf("write msg[%s] to fd[%d], n[%d], cur_pos[%d]\n", msg.c_str(), fd, n, cur_pos);
    }
    close(fd);
    return 0;
}
1
2
3
4
5
6
$ ./rw
cur_pos[0]
file opened, fd[3]
write msg[hello] to fd[3], n[5], cur_pos[5]
write msg[world] to fd[3], n[5], cur_pos[10]
write msg[cpp] to fd[3], n[3], cur_pos[13]

偏移量与文件共享

在Linux系统中，若两个进程A与B同时打开某个文件F，在/proc/[pid]/fdinfo/[fd]2中可以看到各自的文件偏移量。 dup.cpp: 

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
#include <cstdio>

#include <vector>
#include <string>

#include <unistd.h>
#include <fcntl.h>

using namespace std;

int main(int argc, char **argv) {
    int flags = O_RDWR | O_CREAT;
    mode_t mode = S_IRUSR | S_IWUSR | S_IRGRP | S_IROTH;

    int fd = open("dup.txt", flags, mode);
    if (fd == -1) {
        printf("open file error\n");
        return 1;
    }

    printf("file opened, fd[%d]\n", fd);

    int f2 = dup(fd);
    if (f2 == -1) {
        printf("dup fd[%d] failed\n", fd);
        close(fd);
        return 1;
    }

    printf("cur_pos of %d is %d\n", fd, lseek(fd, 0, SEEK_CUR));
    printf("cur_pos of %d is %d\n", f2, lseek(f2, 0, SEEK_CUR));

    vector<string> msgs = {"hello", "world", "cpp"};
    for (const auto &msg : msgs) {
        int n;
        n = write(fd, msg.c_str(), msg.size());
        printf("write msg[%s] to fd[%d], n[%d]\n", msg.c_str(), fd, n);
        printf("cur_pos of %d is %d\n", fd, lseek(fd, 0, SEEK_CUR));
        printf("cur_pos of %d is %d\n", f2, lseek(f2, 0, SEEK_CUR));

        n = write(f2, msg.c_str(), msg.size());
        printf("write msg[%s] to fd[%d], n[%d]\n", msg.c_str(), f2, n);
        printf("cur_pos of %d is %d\n", fd, lseek(fd, 0, SEEK_CUR));
        printf("cur_pos of %d is %d\n", f2, lseek(f2, 0, SEEK_CUR));
    }

    close(f2);
    close(fd);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
$ ./dup
file opened, fd[3]
cur_pos of 3 is 0
cur_pos of 4 is 0
write msg[hello] to fd[3], n[5]
cur_pos of 3 is 5
cur_pos of 4 is 5
write msg[hello] to fd[4], n[5]
cur_pos of 3 is 10
cur_pos of 4 is 10
write msg[world] to fd[3], n[5]
cur_pos of 3 is 15
cur_pos of 4 is 15
write msg[world] to fd[4], n[5]
cur_pos of 3 is 20
cur_pos of 4 is 20
write msg[cpp] to fd[3], n[3]
cur_pos of 3 is 23
cur_pos of 4 is 23
write msg[cpp] to fd[4], n[3]
cur_pos of 3 is 26
cur_pos of 4 is 26
dup函数返回的新文件描述符与参数fd共享同一个文件表项3，对文件描述符fd和f2分别写入后fd和f2的当前文件偏移量相等。

  1. 《UNIX环境高级编程》3.3↩︎

  2. proc - process information pseudo-filesystem http://man7.org/linux/man-pages/man5/proc.5.html↩︎

  3. 《UNIX环境高级编程》3.12↩︎

Posted on Edited on Disqus:

HDU 1880 

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
#include <bits/stdc++.h>
#define DBG(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

const unsigned int KEY = 137;
const int BUCKET_NUM = 120000;

struct Hash {
    vector<pair<string, string>> h[BUCKET_NUM];

    unsigned int get_hash(const string &s) {
        unsigned int hs = 0;
        for (auto c : s)
            hs = (hs * KEY + c) % BUCKET_NUM;
        return hs;
    }

    void insert(const string &k, const string &v) {
        unsigned int hs = get_hash(k);
        h[hs].push_back(make_pair(k, v));
    }

    string *get(const string &key) {
        unsigned int hs = get_hash(key);
        for (auto &kv : h[hs]) {
            if (kv.first == key)
                return &kv.second;
        }
        return nullptr;
    }
} key2val, val2key;

pair<string, string> get_kv(const string &str) {
    unsigned long pos = 0;
    for (int i = 0; i < str.size(); i++) {
        if (str[i] == ']') {
            pos = i;
            break;
        }
    }
    auto k = str.substr(1, pos - 1);
    auto v = str.substr(pos + 2, str.size() - pos - 2);
    return make_pair(k, v);
}

int main(int argc, char **argv) {
    ios::sync_with_stdio(false);
    string s;
    while (true) {
        getline(cin, s);
        if (s == "@END@") break;
        auto kv = get_kv(s);
        key2val.insert(kv.first, kv.second);
        val2key.insert(kv.second, kv.first);
    }
    int n;
    cin >> n;
    cin.get();
    for (int i = 0; i < n; i++) {
        getline(cin, s);
        if (s[0] == '[') {
            auto val = key2val.get(s.substr(1, s.size() - 2));
            if (val == nullptr) {
                cout << "what?" << "\n";
            } else {
                cout << *val << "\n";
            }
        } else {
            auto key = val2key.get(s);
            if (key == nullptr) {
                cout << "what?" << "\n";
            } else {
                cout << *key << "\n";
            }
        }
    }
    return 0;
}

/**
[expelliarmus] the disarming charm
[rictusempra] send a jet of silver light to hit the enemy
[tarantallegra] control the movement of one's legs
[serpensortia] shoot a snake out of the end of one's wand
[lumos] light the wand
[obliviate] the memory charm
[expecto patronum] send a Patronus to the dementors
[accio] the summoning charm
@END@
4
[lumos]
the summoning charm
[arha]
take me to the sky

light the wand
accio
what?
what?
*/

Posted on Edited on Disqus:

跳跃表实现简单，空间复杂度和时间复杂度也较好，Redis中使用跳表而不是红黑树。

实现参考了：

插入时的核心逻辑：

  1. 找到插入的位置
  2. 随机得到新插入节点的level
  3. 处理为了插入当前节点穿过的指针和未穿过的指针的指向和跨度

删除时的核心逻辑：

  1. 找到删除的位置
  2. 处理要删除的节点穿过的指针和未穿过的指针的指向和跨度
  3. 如果可以，减小跳跃表的level

下面两个题可以使用平衡树，这里为了练习使用跳跃表，注意根据每个题的题意特殊处理。 SPOJ ORDERSET 

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
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
#include <bits/stdc++.h>
#define DBG(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

const int MAX_LEVEL = 32;
const int MAX_N = 200000;

struct ListNode {
    struct Forward {
        int span;
        ListNode *forward;
    };
    int val;
    vector<Forward> levels;
};

namespace memory {
    ListNode nodes[MAX_N + 1 + 16];
    int cnt;

    void init() {
        cnt = 0;
    }

    ListNode *new_node(int level, int val) {
        nodes[cnt].levels.resize(level);
        for (int i = 0; i < level; i++) {
            nodes[cnt].levels[i].forward = nullptr;
            nodes[cnt].levels[i].span = 0;
        }
        nodes[cnt].val = val;
        return &nodes[cnt++];
    }
}

struct SkipList {
    ListNode *header;
    int level;
    int length;

    void init() {
        memory::init();
        srand(time(0));

        level = 1;
        length = 0;
        header = memory::new_node(MAX_LEVEL, 0);
    }

    int get_level() {
        int level = 1;
        while (rand() % 2 && level + 1 < MAX_LEVEL)
            level++;
        return level;
    }

    void insert(int x) {
        ListNode *update[MAX_LEVEL];
        int rank[MAX_LEVEL];

        ListNode *p = header;
        for (int i = level - 1; i >= 0; i--) {
            rank[i] = i == (level - 1) ? 0 : rank[i + 1];
            while (p->levels[i].forward && p->levels[i].forward->val <= x) {
                rank[i] += p->levels[i].span;
                p = p->levels[i].forward;
            }
            update[i] = p;
        }
        if (p != header && p->val == x)
            return;

        int level_of_node = get_level();
        if (level_of_node > level) {
            for (int i = level; i < level_of_node; i++) {
                header->levels[i].span = length;
                update[i] = header;
                rank[i] = 0;
            }
            level = level_of_node;
        }
        ListNode *node = memory::new_node(level_of_node, x);
        for (int i = 0; i < level_of_node; i++) {
            node->levels[i].forward = update[i]->levels[i].forward;
            node->levels[i].span = update[i]->levels[i].span - (rank[0] - rank[i]);

            update[i]->levels[i].forward = node;
            update[i]->levels[i].span = rank[0] - rank[i] + 1;
        }

        for (int i = level_of_node; i < level; i++) {
            update[i]->levels[i].span++;
        }

        length++;
    }

    void remove(int x) {
        ListNode *update[MAX_LEVEL];

        ListNode *p = header;
        for (int i = level - 1; i >= 0; i--) {
            while (p->levels[i].forward && p->levels[i].forward->val < x) {
                p = p->levels[i].forward;
            }
            update[i] = p;
        }

        p = p->levels[0].forward;
        if (!p || p->val != x)
            return;

        for (int i = level - 1; i >= 0; i--) {
            if (update[i]->levels[i].forward == p) {
                update[i]->levels[i].forward = p->levels[i].forward;
                update[i]->levels[i].span += p->levels[i].span - 1;
            } else {
                update[i]->levels[i].span--;
            }
        }

        while (level > 1 && !header->levels[level - 1].forward)
            level--;
        length--;
    }

    int kth(int k) {
        int span = 0;
        ListNode *p = header;
        for (int i = level - 1; i >= 0; i--) {
            while (p->levels[i].forward && span + p->levels[i].span <= k) {
                span += p->levels[i].span;
                p = p->levels[i].forward;
            }
        }
        return p->val;
    }

    int rank(int x) {
        int ans = 0;
        ListNode *p = header;
        for (int i = level - 1; i >= 0; i--) {
            while (p->levels[i].forward && p->levels[i].forward->val < x) {
                ans += p->levels[i].span;
                p = p->levels[i].forward;
            }
        }
        return ans;
    }

} skip_list;

int main(int argc, char **argv) {
    int n;
    while (scanf("%d", &n) != EOF) {
        skip_list.init();
        for (int i = 0; i < n; i++) {
            char op[2];
            int x;
            scanf("%s%d", op, &x);
            if (op[0] == 'I') {
                skip_list.insert(x);
            } else if (op[0] == 'D') {
                skip_list.remove(x);
            } else if (op[0] == 'K') {
                if (x > skip_list.length) {
                    puts("invalid");
                } else {
                    printf("%d\n", skip_list.kth(x));
                };
            } else if (op[0] == 'C') {
                printf("%d\n", skip_list.rank(x));
            }
        }
    }
    return 0;
}

/**
8
I -1
I -1
I 2
C 0
K 2
D -1
K 1
K 2

1
2
2
invalid
*/

HDU 4585 

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
#include <bits/stdc++.h>
#define DBG(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

const int MAX_LEVEL = 32;
const int MAX_N = 100000;

struct ListNode {
    struct Forward {
        int span;
        ListNode *forward;
    };
    pair<int, int> val;
    vector<Forward> levels;
};

namespace memory {
    ListNode nodes[MAX_N + 1 + 16];
    int cnt;

    void init() {
        cnt = 0;
    }

    ListNode *new_node(int level, pair<int, int> val) {
        nodes[cnt].levels.resize(level);
        for (int i = 0; i < level; i++) {
            nodes[cnt].levels[i].forward = nullptr;
            nodes[cnt].levels[i].span = 0;
        }
        nodes[cnt].val = val;
        return &nodes[cnt++];
    }
}

struct SkipList {
    ListNode *header;
    int level;
    int length;

    void init() {
        memory::init();
        srand(time(0));

        level = 1;
        length = 0;
        header = memory::new_node(MAX_LEVEL, make_pair(0, 0));
    }

    int get_level() {
        int level = 1;
        while (rand() % 2 && level + 1 < MAX_LEVEL)
            level++;
        return level;
    }

    void insert(pair<int, int> x) {
        ListNode *update[MAX_LEVEL];
        int rank[MAX_LEVEL];

        ListNode *p = header;
        for (int i = level - 1; i >= 0; i--) {
            rank[i] = i == (level - 1) ? 0 : rank[i + 1];
            while (p->levels[i].forward && p->levels[i].forward->val <= x) {
                rank[i] += p->levels[i].span;
                p = p->levels[i].forward;
            }
            update[i] = p;
        }
        if (p != header && p->val == x)
            return;

        int level_of_node = get_level();
        if (level_of_node > level) {
            for (int i = level; i < level_of_node; i++) {
                header->levels[i].span = length;
                update[i] = header;
                rank[i] = 0;
            }
            level = level_of_node;
        }
        ListNode *node = memory::new_node(level_of_node, x);
        for (int i = 0; i < level_of_node; i++) {
            node->levels[i].forward = update[i]->levels[i].forward;
            node->levels[i].span = update[i]->levels[i].span - (rank[0] - rank[i]);

            update[i]->levels[i].forward = node;
            update[i]->levels[i].span = rank[0] - rank[i] + 1;
        }

        for (int i = level_of_node; i < level; i++) {
            update[i]->levels[i].span++;
        }

        length++;
    }

    pair<int, int> find(pair<int, int> x) {
        ListNode *p = header;
        for (int i = level - 1; i >= 0; i--) {
            while (p->levels[i].forward && p->levels[i].forward->val < x)
                p = p->levels[i].forward;
        }

        if (p == header) {
            p = p->levels[0].forward;
            return p->val;
        }

        if (p->levels[0].forward && p->levels[0].forward->val.first - x.first < x.first - p->val.first) {
            p = p->levels[0].forward;
        }
        return p->val;
    }
} skip_list;

int main(int argc, char **argv) {
    int n;
    while (true) {
        scanf("%d", &n);
        if (n == 0) break;
        skip_list.init();
        skip_list.insert(make_pair(1000000000, 1));
        for (int i = 0; i < n; i++) {
            int k, g;
            scanf("%d%d", &k, &g);
            printf("%d %d\n", k, skip_list.find(make_pair(g, k)).second);
            skip_list.insert(make_pair(g, k));
        }
    }
    return 0;
}

/**
3
2 1
3 3
4 2
0

2 1
3 2
4 2
*/

Posted on Edited on Disqus:

[kuangbin专题] Manacher

实现参考了https://oi-wiki.org/string/manacher/。

POJ 3974 Palindrome 求字符串\(A\)的最长回文子串模板题，首先在\(A\)的第一个字符的左面和\(A\)的每个字符的后面填充不在输入范围内的字符$，得到串\(S\)，然后处理串\(S\)。 原串\(A\)长度为\(n\)，处理后的串\(S\)长度为\(m=2\times n - 1\)。 对于每个\(i \in [0, m)\)，试图计算在串\(S\)中以\(i\)为中心的最长回文子串的最大半径\(p_i\)，其中\(p_i \ge 1\)。 在对于每一个\(i-1\)计算\(p_{i-1}\)结束后，维护出一个\([l,r]\)二元组，表示\(i-1\)位置处理结束后，\(i\)位置处理之前当前得到的回文子串中右边界\(r\)最大的回文子串，并且这个回文子串\([l, r]\)是以\(r\)为右边界的最长的回文子串。

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
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <string>

using namespace std;
typedef long long LL;

const int MAX_N = 1000000 + 16;

struct Manacher {
    static const int $ = -1;
    int len_b;
    int b[2 * MAX_N + 1];
    int p[2 * MAX_N + 1];

    void init(char a[], int n) {
        len_b = 2 * n + 1;
        for (int i = 0; i < n; i++) {
            b[2 * i] = $;
            b[2 * i + 1] = a[i];
        }
        b[len_b - 1] = $;

        int l = 0;
        int r = -1;
        for (int i = 0; i < len_b; i++) {
            if (i > r) {
                p[i] = 1;
            } else {
                p[i] = min(p[r - i + l], r - i + 1);
            }
            while (i + p[i] < len_b && i - p[i] >= 0 && b[i + p[i]] == b[i - p[i]]) {
                p[i]++;
            }
            if (i + p[i] - 1 > r) {
                l = i - p[i] + 1;
                r = i + p[i] - 1;
            }
        }
    }

    int max_length() {
        int ans = 1;
        for (int i = 0; i < len_b; i++) {
            int temp = p[i];
            if (b[i] == $ && p[i] % 2 == 1) temp--;
            if (b[i] != $ && p[i] % 2 == 0) temp--;
            ans = max(ans, temp);
        }
        return ans;
    }
} manacher;

char s[MAX_N];

int main(int argc, char **argv) {
    int cas = 1;
    while (true) {
        scanf("%s", s);
        if (s == string("END")) break;
        int len = strlen(s);
        manacher.init(s, len);
        printf("Case %d: %d\n", cas++, manacher.max_length());
    }
    return 0;
}

/**
abcbabcbabcba
abacacbaaaab
END

Case 1: 13
Case 2: 6
*/

HDU 4513 最长不递减回文子串，注意扩展长度的时候比较一下大小。 

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
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <string>

using namespace std;
typedef long long LL;

const int MAX_N = 1000000 + 16;

struct Manacher {
    static const int $ = -1;
    int b[2 * MAX_N + 1];
    int len_b;
    int p[2 * MAX_N + 1];

    void init(int a[], int n) {
        len_b = 2 * n + 1;
        for (int i = 0; i < n; i++) {
            b[2 * i] = $;
            b[2 * i + 1] = a[i];
        }
        b[len_b - 1] = $;

        int l = 0;
        int r = -1;
        for (int i = 0; i < len_b; i++) {
            if (i > r) {
                p[i] = 1;
            } else {
                p[i] = min(p[l + r - i], r - i + 1);
            }
            while (0 <= i - p[i] && i + p[i] < len_b && b[i - p[i]] == b[i + p[i]]) {
                if (b[i - p[i]] != $ && i - p[i] + 2 <= i && b[i - p[i]] > b[i - p[i] + 2]) break;
                p[i]++;
            }
            if (i + p[i] - 1 > r) {
                l = i - p[i] + 1;
                r = i + p[i] - 1;
            }
        }
    }

    int max_length() {
        int ans = 0;
        for (int i = 0; i < len_b; i++)
            ans = max(ans, p[i]);
        return ans - 1;
    }
} manacher;

int a[MAX_N];

int main(int argc, char **argv) {
    int T;
    scanf("%d", &T);
    while (T--) {
        int n;
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
            scanf("%d", &a[i]);
        manacher.init(a, n);
        printf("%d\n", manacher.max_length());
    }
    return 0;
}

/**
100
3
51 52 51
4
51 52 52 51
10
1 2 3 3 3 4 4 4 4 4

3
4
*/

HDU 3294 先把原串\(A\)的每个字符再变换一下，然后输出最长回文子串。 先在\(S\)中找到最长回文子串的长度和左端点，然后再通过\(A\)来输出。 

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
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <string>

using namespace std;
typedef long long LL;

const int MAX_N = 1000000 + 16;

struct Manacher {
    static const int $ = -1;
    int b[2 * MAX_N + 1];
    int len_b;
    int p[2 * MAX_N + 1];

    void init(char a[], int n) {
        len_b = 2 * n + 1;
        for (int i = 0; i < n; i++) {
            b[2 * i] = $;
            b[2 * i + 1] = a[i];
        }
        b[len_b - 1] = $;

        int l = 0;
        int r = -1;
        for (int i = 0; i < len_b; i++) {
            if (i > r) {
                p[i] = 1;
            } else {
                p[i] = min(p[l + r - i], r - i + 1);
            }
            while (0 <= i - p[i] && i + p[i] < len_b && b[i - p[i]] == b[i + p[i]]) {
                p[i]++;
            }
            if (i + p[i] - 1 > r) {
                l = i - p[i] + 1;
                r = i + p[i] - 1;
            }
        }
    }

    pair<int, int> max_length() {
        int ans = 0;
        int l = -1;
        for (int i = 0; i < len_b; i++) {
            if (p[i] - 1 >= 2 && p[i] - 1 > ans) {
                ans = p[i] - 1;
                l = (i - p[i] + 1 + 1) / 2;
            }
        }
        return make_pair(ans, l);
    }
} manacher;

char a[MAX_N];
char c[2];

int main(int argc, char **argv) {
    while (scanf("%s", c) != EOF) {
        int delta = c[0] - 'a';
        scanf("%s", a);
        int len = strlen(a);
        for (int i = 0; i < len; i++) {
            a[i] = (a[i] - 'a' - delta + 26) % 26 + 'a';
        }
        manacher.init(a, len);
        pair<int, int> ans = manacher.max_length();
        if (ans.first < 2) puts("No solution!");
        else {
            printf("%d %d\n", ans.second, ans.second + ans.first - 1);
            for (int i = ans.second, j = 0; j < ans.first; j++) {
                printf("%c", a[i + j]);
            }
            puts("");
        }
    }
    return 0;
}

/**
b babd
a abcd

0 2
aza
No solution!
*/

LightOJ 1258 向字符串末尾添加尽量少的任意字符，使得得到的串是一个最长回文子串。 

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
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <string>

using namespace std;
typedef long long LL;

const int MAX_N = 1000000 + 16;

struct Manacher {
    static const int $ = -1;
    int b[2 * MAX_N + 1];
    int len_b;
    int p[2 * MAX_N + 1];

    void init(char a[], int n) {
        len_b = 2 * n + 1;
        for (int i = 0; i < n; i++) {
            b[2 * i] = $;
            b[2 * i + 1] = a[i];
        }
        b[len_b - 1] = $;

        int l = 0;
        int r = -1;
        for (int i = 0; i < len_b; i++) {
            if (i > r) {
                p[i] = 1;
            } else {
                p[i] = min(p[l + r - i], r - i + 1);
            }
            while (0 <= i - p[i] && i + p[i] < len_b && b[i - p[i]] == b[i + p[i]]) {
                p[i]++;
            }
            if (i + p[i] - 1 > r) {
                l = i - p[i] + 1;
                r = i + p[i] - 1;
            }
        }
    }

    int get_ans() {
        int ans = 2 * len_b - 1;
        for (int i = len_b / 2; i < len_b; i++) {
            if (i + p[i] - 1 == len_b - 1) {
                int temp = (len_b + (i - len_b / 2) * 2) / 2;
                ans = min(ans, temp);
            }
        }
        return ans;
    }
} manacher;

char a[MAX_N];

int main(int argc, char **argv) {
    int T;
    scanf("%d", &T);
    for (int cas = 1; cas <= T; cas++) {
        scanf("%s", a);
        int len = strlen(a);
        manacher.init(a, len);
        printf("Case %d: %d\n", cas, manacher.get_ans());
    }
    return 0;
}

/**
4
bababababa
pqrs
madamimadam
anncbaaababaaa

Case 1: 11
Case 2: 7
Case 3: 11
Case 4: 19
*/

Posted on Edited on Disqus:

https://hihocoder.com/problemset/problem/1093
实现参考了算法导论。 

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
#include <bits/stdc++.h>
#define DBG(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

const int MAX_N = 100000 + 16;
const int MAX_M = 1000000 + 16;
const int INF = 0x3F3F3F3F;

struct Edge {
    int u, v, c;

    Edge() {}

    Edge(int u, int v, int c) : u(u), v(v), c(c) {}
};

struct Graph {
    vector<int> g[MAX_N];
    vector<Edge> edges;
    int n;

    void init(int n) {
        this->n = n;
        for (int i = 0; i <= n; i++)
            g[i].clear();
        edges.clear();
    }

    void add(int u, int v, int c) {
        edges.push_back(Edge(u, v, c));
        g[u].push_back(edges.size() - 1);
    }
} graph;

struct BellmanFord {
    int dist[MAX_N];

    void init(int n, int s) {
        for (int i = 0; i <= n; i++)
            dist[i] = INF;
        dist[s] = 0;
    }

    void work(const Graph &g, int s) {
        init(g.n, s);
        for (int i = 1; i < g.n; i++) {
            for (const Edge &e : g.edges) {
                dist[e.v] = min(dist[e.v], dist[e.u] + e.c);
            }
        }
    }
} bellman_ford;

struct Dijkstra {
    int dist[MAX_N];
    bool vis[MAX_N];

    void init(int n, int s) {
        for (int i = 0; i <= n; i++) {
            dist[i] = INF;
            vis[i] = false;
        }
        dist[s] = 0;
    }

    int extract_min(int n) {
        int d = INF;
        int u = 0;
        for (int i = 1; i <= n; i++) {
            if (!vis[i] && dist[i] < d) {
                d = dist[i];
                u = i;
            }
        }
        return u;
    }

    void work(const Graph &g, int s) {
        init(g.n, s);
        int left = g.n;
        while (left--) {
            int u = extract_min(g.n);
            vis[u] = true;
            for (int i = 0; i < g.g[u].size(); i++) {
                const Edge &e = g.edges[g.g[u][i]];
                dist[e.v] = min(dist[e.v], dist[e.u] + e.c);
            }
        }
    }
} dijkstra;

struct DijkstraPremium {
    struct Node {
        int u, d;

        Node() {}

        Node(int u, int d) : u(u), d(d) {}

        bool operator>(const Node &rhs) const {
            return this->d > rhs.d;
        }
    };

    int dist[MAX_N];
    bool vis[MAX_N];
    priority_queue<Node, vector<Node>, greater<Node>> pq;

    void init(int n, int s) {
        for (int i = 0; i <= n; i++) {
            dist[i] = INF;
            vis[i] = false;
        }
        dist[s] = 0;
        while (!pq.empty())
            pq.pop();
        pq.push(Node(s, dist[s]));
    }

    void work(const Graph &g, int s) {
        init(g.n, s);
        while (!pq.empty()) {
            Node node = pq.top();
            pq.pop();
            int u = node.u;
            if (vis[u])
                continue;

            vis[u] = true;
            for (int i = 0; i < g.g[u].size(); i++) {
                const Edge &e = g.edges[g.g[u][i]];
                dist[e.v] = min(dist[e.v], dist[e.u] + e.c);
                pq.push(Node(e.v, dist[e.v]));
            }
        }
    }
} dijkstra_premium;

int main(int argc, char **argv) {
    int n, m, s, t;
    while (scanf("%d%d%d%d", &n, &m, &s, &t) != EOF) {
        graph.init(n);
        for (int i = 0; i < m; i++) {
            int u, v, c;
            scanf("%d%d%d", &u, &v, &c);
            graph.add(u, v, c);
            graph.add(v, u, c);
        }
        dijkstra_premium.work(graph, s);
        printf("%d\n", dijkstra_premium.dist[t]);
    }
    return 0;
}

Posted on Edited on Disqus:

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const int N = 1000000 + 16;
struct Hash {
    const unsigned long long KEY = 137;
    unsigned long long h[N], p[N];
    int len;
    void init(const int a[], int len) {
        this->len = len;
        p[0] = 1;
        for (int i = 1; i <= len; i++)
            p[i] = p[i - 1] * KEY;
        h[len] = 0;
        for (int i = len - 1; i >= 0; i--)
            h[i] = h[i + 1] * KEY + a[i];
    }
    unsigned long long get(int l, int r) {
        return h[l] - h[r + 1] * p[r - l + 1];
    }
    unsigned long long get_for_len(int l, int len) {
        return h[l] - h[l + len] * p[len];
    }
};

get方法中\(0 \le l \le r < len(a)\)，get_for_len方法中\(l \in [0, len(a))，len \in [1, len(a) - l]\)。

原理

\(p_i = k^i\)
\(h_i = \sum\limits_{j \in [i,\ len(a))} a_j \cdot k^{j - i}\)
\(get(l, r) = h_l - h_{r+1} \cdot k^{r - l + 1}\)
\(= \sum\limits_{j \in [l, len(a))} a_j \cdot k^{j - l} - \sum\limits_{j \in [r+1, len(a))} a_j \cdot k^{j-r-1} \cdot k^{r-l+1}\)
\(= \sum\limits_{j \in [l, len(a))} a_j \cdot k^{j - l} - \sum\limits_{j \in [r+1, len(a))} a_j \cdot k^{j-l}\)
\(= \sum\limits_{j \in [l, r+1)} a_j \cdot k^{j - l} + \sum\limits_{j \in [r+1, len(a))} a_j \cdot k^{j - l} - \sum\limits_{j \in [r+1, len(a))} a_j \cdot k^{j-l}\)
\(= \sum\limits_{j \in [l, r+1)} a_j \cdot k^{j - l}\)
\(= \sum\limits_{j \in [l, r]} a_j \cdot k^{j - l}\)
在实现的时候用到了unsigned long long的自然溢出，相当于\(\mod 2^{64}\)。

例题

HDU 1711 Number Sequence 

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
#include <bits/stdc++.h>
#define DBG(x) cerr << #x << " = " << x << endl

using namespace std;

const int N = 1000000 + 16;

struct Hash {
    const unsigned long long KEY = 137;
    unsigned long long h[N], p[N];
    int len;
    void init(const int a[], int len) {
        this->len = len;
        p[0] = 1;
        for (int i = 1; i <= len; i++)
            p[i] = p[i - 1] * KEY;
        h[len] = 0;
        for (int i = len - 1; i >= 0; i--)
            h[i] = h[i + 1] * KEY + a[i];
    }
    unsigned long long get(int l, int r) {
        return h[l] - h[r + 1] * p[r - l + 1];
    }
    unsigned long long get_for_len(int l, int len) {
        return h[l] - h[l + len] * p[len];
    }

} hp, hs;

int a[N];

int get_ans() {
    for (int i = 0; i + hs.len - 1 < hp.len; i++)
        if (hs.get_for_len(0, hs.len) == hp.get_for_len(i, hs.len))
            return i + 1;
    return -1;
}

int main(int argc, char **argv) {
    int T;
    scanf("%d", &T);
    while (T--) {
        int n, m;
        scanf("%d%d", &n, &m);
        for (int i = 0; i < n; i++)
            scanf("%d", &a[i]);
        hp.init(a, n);
        for (int i = 0; i < m; i++)
            scanf("%d", &a[i]);
        hs.init(a, m);
        printf("%d\n", get_ans());
    }
    return 0;
}

/**
2
13 5
1 2 1 2 3 1 2 3 1 3 2 1 2
1 2 3 1 3
13 5
1 2 1 2 3 1 2 3 1 3 2 1 2
1 2 3 2 1

6
-1
*/