# [2020q3](http://wiki.csie.ncku.edu.tw/sysprog/schedule) 第 18 週測驗題
###### tags: `sysprog2020`

:::info
目的: 引導學員學習 regular expression 及 socket 程式設計
:::

==[作答表單](https://docs.google.com/forms/d/e/1FAIpQLSePkfc8lQ4GSc_BjY31cYqbqHF2dzspprMgEAb6ZOQZAKcDnA/viewform)==

---

### 測驗 `1`

LeetCode [10. Regular Expression Matching](https://leetcode.com/problems/regular-expression-matching/) 要求判定給定兩個字串 `s` 與 `p` 是否匹配 (match)，要考慮到特殊符號 `.` 與 `*`:
* 符號 `.` 可對應各種字元
* 符號 `*` 代表前方字元可使用各種數量 (包含 0 個)，例如 `p = "a*";`，則無論 `s` 為空字串或者任意個 `'a'` 組成，均可傳回 `true`

比對樣式的每個字元作為一個狀態 (包含 `.` 任何字元)，串接為成單一路線的狀態，最後是結束狀態。
> $\uparrow$ `ab.d` 所建立的狀態機

輸入字串從起始狀態開始判斷，沿著路線走到結束狀態，每個狀態從輸入字串取一個字元跟該狀態的字元比較，若不匹配則 `isMatch` 直接判斷失敗，若符合則消耗該字元，把剩下的輸入字串丟到下一個狀態繼續比較。若成功走到結束狀態，且輸入字串已全部被消耗完，則 `isMatch` 判斷成功
> $\uparrow$ 狀態機消耗輸入字串 s 的示意圖，只有在最上面的狀況，消耗所有的輸入字串字元，才算 `isMatch` = true

考慮到 `*` 符號，包含零個或是多個字元，在這個狀態中不一定只消耗單一字元，因此需要特別處理，根據可輸入字串的資料，消耗一個到多個該狀態處理的字元，剩下的輸入字串移送到下個狀態再比較。
> $\uparrow$ 考慮 `*` 符號的特別處理，進入到 'c' 狀態的輸入字串為 'ccc'，考慮消耗各種可能，將 'ccc', 'cc', 'c', 及 '∅' 移送到下個狀態進行判斷

以下程式碼為 LeetCode [10. Regular Expression Matching](https://leetcode.com/problems/regular-expression-matching/) 的一個可能實作:

#include <stdbool.h>
bool isMatch(char *s, char *p)
{
    if (!p || !*p)
        return !s || !*s;

    if (!s || !*s) {                         
        char *str = p;
        while (*str && str[1]) {
            if (str[1] != '*')
                return false;
            str += 2;
        }
        return !*str;
    }

    if (p[1] == '*')
        return isMatch(s, p + 2) ||
               p && *p && (s[0] == p[0] || p[0] == '.') && isMatch(s + 1, p);
    return p && *p && (s[0] == p[0] || p[0] == '.') && isMatch(s + 1, p + 1);
}

透過動態規劃，重寫為不需要遞迴呼叫的實作:

#include <stdbool.h>
bool isMatch(char *s, char *p)
{
    if (!p || !*p)
        return !s || !*s;

    int len = strlen(s);
    bool m[len + 1];
    memset(m, 0, sizeof(m));
    m[0] = true;

    for (; *p; p++) {
        if (*(p + 1) == '*')
            continue;
        if (*p == '*') {                   
            char c = *(p - 1);
            for (int i = 1; i <= len; i++)
                m[i] = EXP1;
        } else {
            char c = *p;
            for (int i = len; i > 0; i--)
                m[i] = EXP2;
            m[0] = false;
        }
    }

    return m[len];
}

請補完程式碼，使得其執行符合 LeetCode 預期並通過給定的測試資料。

==作答區==

EXP1 = ?
* `(a)` `m[i] && (s[i] == c || c == '.')`
* `(b)` `m[i - 1] && (s[i - 1] == c || c == '.')`
* `(c)` `m[i - 1] && (s[i] == c || c == '.')`
* `(d)` `m[i] || (m[i - 1] && (s[i - 1] == c || c == '.'))`

EXP2 = ?
* `(a)` `m[i] && (s[i] == c || c == '.')`
* `(b)` `m[i - 1] && (s[i - 1] == c || c == '.')`
* `(c)` `m[i - 1] && (s[i] == c || c == '.')`
* `(d)` `m[i] || (m[i - 1] && (s[i - 1] == c || c == '.'))`

---

### 測驗 `2`

請詳閱 LeetCode [468. Validate IP Address](https://leetcode.com/problems/validate-ip-address/) 題目要求，再考慮以下可能的實作:

#include <ctype.h>
#include <stdlib.h>

static int checkIPversion(char *s)
{
    for (int count = 0; *s; s++) {
        if (*s == '.') return 4;
        if (*s == ':') return 6;
        if (++count >= 5) break;
    }
    return -1;
}

static bool checkV4(char *IP)
{
    int size = 0;
    char *walker = IP, *runner = IP;
    while (*runner) {
        if (runner - walker > 3) return false;
        if (*runner != '.' && !isdigit(*runner)) return false;
        if (*runner == '.') {
            if (walker == runner) return false;
            *runner = '\0';
            int tmp = atoi(walker);
            if (tmp < 0 || tmp > 255) return false;
            if (runner - walker > 1 && *walker == '0') return false;
            size++;
            walker = ++runner;
            if (size > 3) return false;
        } else
            ++runner;
    }
    if (walker == runner) return false;
    int tmp = atoi(walker);
    if (tmp < 0 || tmp > 255) return false;
    if (runner - walker > 1 && *walker == '0') return false;
    return size == 3;
}

static bool checkV6(char *IP)
{
    int size = 0;
    char *walker = IP, *runner = IP;
    while (*runner) {
        if (COND1)
            return false;
        *runner = toupper(*runner);
        if (*runner != ':' &&
            (!isdigit(*runner) && (*runner < 'A' || *runner > 'F')))
            return false;
        if (*runner == ':') {
            if (walker == runner)
                return false;
            size++;
            walker = ++runner;
            if (COND2)
                return false;
        } else
            ++runner;
    }
    return walker != runner && COND3 && COND4;
}

char *validIPAddress(char *IP)
{
    switch (checkIPversion(IP)) {
    case 4:
        if (checkV4(IP))
            return "IPv4";
    case 6:
        if (checkV6(IP))
            return "IPv6";
    }
    return "Neither";
}

請補完程式碼，使得執行符合 LeetCode 預期並通過給定的測試資料。

==作答區==

COND1 =
* `(a)` `runner - walker > 4`
* `(b)` `runner - walker > 5`
* `(c)` `runner - walker > 6`
* `(d)` `runner - walker > 7`

COND2 =
* `(a)` `size > 4`
* `(b)` `size > 5`
* `(c)` `size > 6`
* `(d)` `size > 7`

COND3 =
* `(a)` `runner - walker <= 4`
* `(b)` `runner - walker <= 5`
* `(c)` `runner - walker <= 6`
* `(d)` `runner - walker <= 7`

COND4 = ?
* `(a)` `size == 4`
* `(b)` `size == 5`
* `(c)` `size == 6`
* `(d)` `size == 7`

:::success
延伸題目:
* 閱讀 [Leetcode Challenge: Validate IP Address](https://medium.com/@ryanyang1221/leetcode-challenge-validate-ip-address-6-16-d9e1f368b8ed)，理解 regular expression 的實作方式
* 不使用 regex，實作更有效率的 C 程式碼
:::

---

### 測驗 `3`

給定檔案 `index.html`，其內容如下:

<html><head></head><body><h1> HELLO WORLD </h1></body></html>

今有一個 Linux 環境之下的 C 程式 (`server.c`) 可讀取 `index.html` 的內容，並傾聽 port 55688，待網頁瀏覽器連線後，顯示 `index.html` 的內容。

程式碼如下:

#include <errno.h>
#include <fcntl.h>
#include <netdb.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/epoll.h>
#include <sys/sendfile.h>
#include <sys/socket.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <unistd.h>

#define PORT "55688"
#define MAX_EVENTS 5

static int lfd, efd;
static struct epoll_event events[MAX_EVENTS];
static void set_socket_non_blocking(int sfd);
static char buf[512];

static void send_response(int sfd)
{
    int cfd = open("index.html", O_RDONLY, 0777);
    if (cfd < 0)
        perror("open:");

    struct stat stats_buf;
    int byte_to_send = fstat(cfd, &stats_buf);
    if (byte_to_send < 0)
        perror("fstats");

    char good_response[1024] = {"HTTP/1.1 200 OK\r\n\r\n"};
    send(sfd, good_response, strlen(good_response), 0);
    int ret = sendfile(sfd, cfd, NULL, stats_buf.st_size);
    if (ret < 0)
        perror("send file/response\r\n");
    close(sfd);
}

static void handle_client(int cfd)
{
    int count = read(cfd, buf, 512);
    if (count < 0)
        perror("Nothing to read");
    struct epoll_event event = {.data.fd = cfd, .events = EPOLLOUT | EPOLLET};
    if (epoll_ctl(efd, EPOLL_CTL_MOD, cfd, &event) < 0)
        perror("epoll_ctl");
}

static void accept_connection()
{
    struct sockaddr addr;
    socklen_t addr_len;
    int conn_fd = accept(lfd, &addr, &addr_len);

    if (conn_fd < 0)
        perror("accept connection");
    set_socket_non_blocking(conn_fd);

    struct epoll_event event = {.data.fd = conn_fd,
                                .events = EPOLLIN | EPOLLET};

    if (epoll_ctl(efd, EPOLL_CTL_ADD, conn_fd, &event) < 0) {
        close(conn_fd);
        perror("epoll_ctl");
    }
}

void serve()
{
    memset(&events, 0, MAX_EVENTS * sizeof(struct epoll_event));
    int evt_list = epoll_wait(efd, events, MAX_EVENTS, -1);

    if (evt_list < 0) {
        fprintf(stdin, "EPOLL WAIT: efd %d %s\n", evt_list, strerror(errno));
        abort();
    }
    for (int i = 0; i < evt_list; i++) {
        if (events[i].events & (EPOLLERR | EPOLLHUP | EPOLLRDHUP)) {
            printf("event [%d]: errno %d\n", i, events[i].events);
            close(events[i].data.fd);
            perror("closing socket");
        } else {
            if (events[i].data.fd == lfd)
                ACT1;
            else if (events[i].events & EPOLLIN)
                ACT2;
            else
                ACT3;
        }
    }
}

static void set_socket_non_blocking(int sfd)
{
    int flags = fcntl(sfd, F_GETFL);
    if (flags < 0)
        perror("fcntl");

    flags |= O_NONBLOCK;
    if (fcntl(sfd, F_SETFL, flags) < 0)
        perror("fcntl");
}

static int create_socket_listener(char *port)
{
    struct addrinfo hints, *result, *r_ptr;
    memset(&hints, 0, sizeof(struct addrinfo));
    hints.ai_family = AF_UNSPEC;
    hints.ai_socktype = SOCK_STREAM;
    hints.ai_protocol = 0;
    hints.ai_flags = AI_PASSIVE;

    int s = getaddrinfo(NULL, port, &hints, &result);
    if (s != 0) {
        fprintf(stderr, "getaddrinfo: %s\n", gai_strerror(s));
        exit(EXIT_FAILURE);
    }

    int sfd;
    for (r_ptr = result; r_ptr != NULL; r_ptr = r_ptr->ai_next) {
        sfd = socket(r_ptr->ai_family, r_ptr->ai_socktype, r_ptr->ai_protocol);
        if (sfd < 0)
            continue;
        s = setsockopt(sfd, SOL_SOCKET, SO_REUSEADDR, &s, sizeof(int));
        if (s < 0) {
            perror("setsockopt");
            exit(EXIT_FAILURE);
        }
        if (bind(sfd, r_ptr->ai_addr, r_ptr->ai_addrlen) == 0)
            break;
        close(sfd);
    }

    if (!r_ptr) {
        perror("Could not bind\n");
        freeaddrinfo(result);
        exit(EXIT_FAILURE);
    }
    freeaddrinfo(result);
    return sfd;
}

int main()
{
    lfd = create_socket_listener(PORT);
    set_socket_non_blocking(lfd);

    /* SOMAXCONN = 128 backlogs */
    if (listen(lfd, SOMAXCONN) < 0) {
        perror("listen");
        exit(EXIT_FAILURE);
    }

    if ((efd = epoll_create(NUM)) < 0) {
        close(lfd);
        perror("epoll_create");
    }

    struct epoll_event event = {.data.fd = lfd, .events = EPOLLIN | EPOLLET};
    if (epoll_ctl(efd, EPOLL_CTL_ADD, lfd, &event) < 0) {
        close(lfd);
        perror("epoll_ctl add");
        exit(EXIT_FAILURE);
    }

    for (;;)
        serve();

    return 0;
}

請補完程式碼。

==作答區==

ACT1 = ?
* `(a)` `send_response(events[i].data.fd)`
* `(b)` `accept_connection()`
* `(c)` `handle_client(events[i].data.fd)`

ACT2 = ?
* `(a)` `send_response(events[i].data.fd)`
* `(b)` `accept_connection()`
* `(c)` `handle_client(events[i].data.fd)`

ACT3 = ?
* `(a)` `send_response(events[i].data.fd)`
* `(b)` `accept_connection()`
* `(c)` `handle_client(events[i].data.fd)`

NUM = ?
* `(a)` `1`
* `(b)` `0`
* `(c)` `-1`

---