HackMD
2021q1 Homework1 (lab0)
contributed by < hankluo6 >
環境
$ gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 1
On-line CPU(s) list: 0
Thread(s) per core: 1
Core(s) per socket: 1
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 158
Model name: Intel(R) Core(TM) i5-8300H CPU @ 2.30GHz
Stepping: 10
CPU MHz: 2304.002
BogoMIPS: 4608.00
Hypervisor vendor: KVM
Virtualization type: full
L1d cache: 32K
L1i cache: 32K
L2 cache: 256K
L3 cache: 8192K
NUMA node0 CPU(s): 0
Queue implementation
q_new
struct list_head *q_new()
{
struct list_head *q = malloc(sizeof(struct list_head));
if (!q)
return NULL;
INIT_LIST_HEAD(q);
return q;
}
利用 INIT_LIST_HEAD 初始化 list_head 當作 queue 的 head。
q_insert_head
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *e = malloc(sizeof(element_t));
if (!e)
return false;
e->value = strdup(s);
if (!e->value) {
free(e);
return false;
}
list_add(&e->list, head);
return true;
}
分配 element_t 的空間並將字串存入，再與 queue 連接。
q_insert_tail
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *e = malloc(sizeof(element_t));
if (!e)
return false;
e->value = strdup(s);
if (!e->value) {
free(e);
return false;
}
list_add_tail(&e->list, head);
return true;
}
同 q_insert_head。
q_remove_head
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *e = list_entry(head->next, element_t, list);
list_del(head->next);
if (sp) {
strncpy(sp, e->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
return e;
}
利用 list_entry 取得第一個 element，並把資料放入 sp。
q_remove_tail
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
return q_remove_head(head->prev->prev, sp, bufsize);
}
取得 tail 的前一個元素，便能利用 q_remove_head 來移除。
q_size
int q_size(struct list_head *head)
{
if (!head)
return 0;
int len = 0;
struct list_head *li;
list_for_each (li, head)
len++;
return len;
}
q_delete_mid
bool q_delete_mid(struct list_head *head)
{
// https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
if (!head || list_empty(head))
return false;
struct list_head *fast = head->next;
struct list_head *slow = head->next;
while (fast != head && fast->next != head) {
fast = fast->next->next;
slow = slow->next;
}
list_del(slow);
q_release_element(list_entry(slow, element_t, list));
return true;
}
運用 Floyd's Algorithm 的 fast and slow pointer 的方法找出中間元素，再移除即可。
q_delete_dup
bool q_delete_dup(struct list_head *head)
{
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
if (!head || list_empty(head))
return false;
struct list_head *e;
list_for_each (e, head) {
struct list_head *next = e->next;
bool dup = false;
while (next != head &&
!strcmp(list_entry(e, element_t, list)->value,
list_entry(next, element_t, list)->value)) {
list_del(e);
q_release_element(list_entry(e, element_t, list));
e = next;
next = e->next;
dup = true;
}
if (dup) {
list_del(e);
q_release_element(list_entry(e, element_t, list));
e = next;
}
}
return true;
}
遍歷整個 queue，並再迴圈中檢查當前元素與下一個元素是否相同，並持續移除下個元素，最後把當前元素也移除便能刪除所有相同的元素。
q_swap
void q_swap(struct list_head *head)
{
// https://leetcode.com/problems/swap-nodes-in-pairs/
if (!head || list_empty(head))
return;
struct list_head *e;
list_for_each (e, head) {
if (e->next == head)
break;
struct list_head *next = e->next;
list_del(e);
list_add(e, next);
}
}
遍歷 queue 時兩兩交換即可。
q_reverse
void q_reverse(struct list_head *head)
{
if (!head || list_empty(head))
return;
struct list_head *prev, *iter, *rear;
for (prev = head, iter = head->next, rear = iter->next; iter != head;) {
iter->prev = rear;
iter->next = prev;
prev = iter;
iter = rear;
rear = rear->next;
}
head->next = prev;
head->prev = rear;
}
利用三個 pointer 分別指向 prev, current, next 元素，在遍歷時持續更改指標指向。
q_sort
void merge_sort(struct list_head **head)
{
if (!(*head) || !(*head)->next)
return;
struct list_head *fast = (*head)->next;
struct list_head *slow = *head;
while (fast && fast->next) {
fast = fast->next->next;
slow = slow->next;
}
fast = slow->next;
slow->next = NULL;
struct list_head **front = head;
struct list_head **back = &fast;
merge_sort(front);
merge_sort(back);
struct list_head *newh = NULL;
struct list_head **tmp = &newh;
while (*front && *back) {
element_t *f = list_entry(*front, element_t, list);
element_t *b = list_entry(*back, element_t, list);
if (strcmp(f->value, b->value) < 0) {
*tmp = *front;
*front = (*front)->next;
} else {
*tmp = *back;
*back = (*back)->next;
}
tmp = &((*tmp)->next);
}
if (*front)
*tmp = *front;
else if (*back)
*tmp = *back;
*head = newh;
}
void q_sort(struct list_head *head)
{
if (q_size(head) < 2)
return;
head->next->prev = NULL;
head->prev->next = NULL;
merge_sort(&head->next);
struct list_head *e, *prev;
for (e = head->next, prev = head;; prev = e, e = e->next) {
if (!e) {
head->prev = prev;
prev->next = head;
break;
}
e->prev = prev;
}
}
使用 merge sort 作為排序，使用 pointer to pointer 可以避免 merge 完需要回傳 node，在 merge 過程只有建立 next 連接，故在 q_sort 內需重新設定 prev 指標。
Queue Shuffle
void q_shuffle(struct list_head *head)
{
int len = q_size(head);
if (len <= 1)
return;
struct list_head *node, *tmp, *last = head->prev;
while (--len) {
int r = rand() % (len + 1);
list_for_each(node, head) {
if (!r)
break;
r--;
}
tmp = node->prev;
list_del(node);
list_add(node, last);
list_del(last);
list_add(last, tmp);
last = node->prev;
}
}
Web Implementatiton
先前方法使用 cmd_select 接收資料，需要將 linenoise 關閉，且 cmd_select 似乎專門用於 source 讀檔專用，故改採用更改 linenoise 讀取的方式來接收 web 傳來的訊息。
static int linenoiseEdit(...)
{
...
linenoiseHistoryAdd("");
if (write(l.ofd, prompt, l.plen) == -1)
return -1;
while (1) {
signed char c;
int nread;
char seq[3];
+ if (listenfd != -1) {
+ fd_set set;
+ FD_ZERO(&set);
+ FD_SET(listenfd, &set);
+ FD_SET(stdin_fd, &set);
+ int rv = select(listenfd + 1, &set, NULL, NULL, NULL);
+ struct sockaddr_in clientaddr;
+ socklen_t clientlen = sizeof clientaddr;
+ int connfd;
+
+ switch (rv) {
+ case -1:
+ perror("select"); /* an error occurred */
+ continue;
+ case 0:
+ printf("timeout occurred\n"); /* a timeout occurred */
+ continue;
+ default:
+ if (FD_ISSET(listenfd, &set)) {
+ connfd = accept(listenfd,(SA *) &clientaddr, &clientlen);
+ char *p = process(connfd, &clientaddr);
+ strncpy(buf, p, strlen(p) + 1);
+ close(connfd);
+ free(p);
+ return strlen(p);
+ } else if (FD_ISSET(stdin_fd, &set)) {
+ nread = read(l.ifd, &c, 1);
+ if (nread <= 0)
+ return l.len;
+ }
+ break;
+ }
+ } else {
nread = read(l.ifd, &c, 1);
if (nread <= 0)
return l.len;
+ }
...
}
}
將 web 使用的 filedescription 以及 stdin 使用的 file desciption 都加到 set 當中，便能使用 select 判斷目前接收到的資料來源，FD_ISSET 判斷哪個 fd 被設置，如果為 listenfd 表示收到 web 端傳來的資料，如果為 stdin_fd 則表示為使用者輸入端傳來的資料。
TODO Coroutine
termios
TODO
