HackMD
2023q1 Homework1 (quiz1)
contributed by < KHLee529 >
測驗 1
作答結果
AAA:struct itemBBB:listCCC:list_for_each_entry_safeDDD:list_move_tailEEE:list_move_tailFFF:list_splice_tail
程式碼
#include <stdint.h>
#include "list.h"
struct item {
uint16_t i;
struct list_head list;
};
static inline int cmpint(const void *p1, const void *p2)
{
const uint16_t *i1 = (const uint16_t *) p1;
const uint16_t *i2 = (const uint16_t *) p2;
return *i1 - *i2;
}
static void list_sort(struct list_head *head)
{
if (list_empty(head) || list_is_singular(head))
return;
struct list_head list_less, list_greater;
INIT_LIST_HEAD(&list_less);
INIT_LIST_HEAD(&list_greater);
struct item *pivot = list_first_entry(head, struct item, list);
list_del(&pivot->list);
struct item *itm = NULL, *is = NULL;
list_for_each_entry_safe (itm, is, head, list) {
if (cmpint(&itm->i, &pivot->i) < 0)
list_move_tail (&itm->list, &list_less);
else
list_move_tail (&itm->list, &list_greater);
}
list_sort(&list_less);
list_sort(&list_greater);
list_add(&pivot->list, head);
list_splice(&list_less, head);
list_splice_tail(&list_greater, head);
}
程式運作原理
首先以一個長度為 5 的串列進行演算法的演示如下所示。
首先選擇第一個節點作為 pivot，用於將剩餘的節點做大小分類。
接著逐一走過每一個節點，按照與 pivot 節點的值大小比較分成 list_greater 與 list_less 兩條。之後遞迴的對於這兩個串列再進行排序。
注意: 由於需要確保 stable sorting 的性質，必須維持原先的順序，故 DDD 與 EEE 需使用 list_move_tail 而非 list_move。
最後依序將排序好的 list_less、pivot、排序好的 list_greater 接回原本的串列便完成整個串列的排序。
測驗 2
作答結果
GGGG:list_for_each_entry_safeHHHH:list_add_tailIIII:&stack[++top]JJJJ:&stack[++top]KKKK:&stack[top--]
程式碼
#define MAX_DEPTH 512
static void list_sort_nr(struct list_head *head)
{
if (list_empty(head) || list_is_singular(head))
return;
struct list_head stack[MAX_DEPTH];
for (int i = 0; i < MAX_DEPTH; i++)
INIT_LIST_HEAD(&stack[i]);
int top = -1;
/* add the origin list into stack */
list_splice_init(head, &stack[++top]);
struct list_head partition;
INIT_LIST_HEAD(&partition);
/* process while stack are not empty */
while (top >= 0) {
INIT_LIST_HEAD(&partition);
/* take the first list in stack to process */
list_splice_init(&stack[top--], &partition);
if (!list_empty(&partition) && !list_is_singular(&partition)) {
struct list_head list_less, list_greater;
INIT_LIST_HEAD(&list_less);
INIT_LIST_HEAD(&list_greater);
struct item *pivot =
list_first_entry(&partition, struct item, list);
list_del(&pivot->list);
INIT_LIST_HEAD(&pivot->list);
struct item *itm = NULL, *is = NULL;
/* separate list into greater and less comparing to pivot */
list_for_each_entry_safe (itm, is, &partition, list) {
list_del(&itm->list);
if (cmpint(&itm->i, &pivot->i) < 0)
list_move(&itm->list, &list_less);
else
list_move(&itm->list, &list_greater);
}
list_add_tail (&pivot->list, &list_less);
if (!list_empty(&list_greater))
list_splice_tail(&list_greater, &stack[++top]);
if (!list_empty(&list_less))
list_splice_tail(&list_less, &stack[++top]);
} else {
/* if partition is empty or singular */
top++;
list_splice_tail(&partition, &stack[top]);
while (top >= 0 && list_is_singular(&stack[top])) {
struct item *tmp =
list_first_entry(&stack[top], struct item, list);
list_del(&tmp->list);
INIT_LIST_HEAD(&stack[top--]);
list_add_tail(&tmp->list, head);
}
}
}
}
程式運作原理
以一個六個節點的串列進行演示。
首先將整個串列加入堆疊 (stack) 的頂端，如下圖所示，開始進行迭代式的快速排序。
取出位在堆疊頂部的串列，並取第一個節點作為 pivot 後，將整個串列根據其值與 pivot 的先後關係分成 list_greater 與 list_less。
接著將 pivot 接上 list_less 的最後端後將 list_greater 與 list_less 分別推入堆疊中。
接著進入下一次迭代，再將原先在堆疊頂端的串列取出，進行與前述相同的操作後放回堆疊。
再進行一次相同的流程。
此時由於堆疊頂端的串列僅有一個元素，此時依序將只有一個元素的串列接上 head。
對剩下來的串列再做一次上述的拆分流程。
最後當堆疊清空時迭代結束，完成排序。
程式實作缺失
- 在拆分為
pivot、list_greater、list_less的三個部份後，由於已經確定list_less的所有節點值都小於pivot，應將pivot節點單獨推入堆疊中，否則會增加所需要的比較次數以及操作次數，修改如下
diff --git a/origin.c b/modified.c
index 62b862c..b056693 100644
--- a/origin.c
+++ b/modified.c
@@ -36,9 +36,9 @@ static void list_sort_nr(struct list_head *head) {
list_move(&itm->list, &list_greater);
}
- list_add_tail(&pivot->list, &list_less);
if (!list_empty(&list_greater))
list_splice_tail(&list_greater, &stack[++top]);
+ list_add(&pivot->list, &stack[++top]);
if (!list_empty(&list_less))
list_splice_tail(&list_less, &stack[++top]);
} else {
測驗 3
作答結果
LLLL:(uintptr_t) (a) ^ (uintptr_t) (b)MMMM:nodePPPP:real_next->cmp
程式碼
#include <assert.h>
#include <errno.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
typedef struct _xorlist_node {
struct _xorlist_node *cmp;
} xor_node_t;
typedef struct _xor_list_struct {
xor_node_t head, tail;
uint32_t count;
} xor_list_t;
#define XOR_COMP(a, b) ((xor_node_t *) ((uintptr_t) a ^ (uintptr_t) b))
static inline xor_node_t *address_of(xor_node_t *n1, xor_node_t *n2)
{
assert(n1 && n2);
return XOR_COMP(n1, n2);
}
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
#define xorlist_for_each(node, rp, rn, list) \
for (rp = &(list)->head, node = rp->cmp; node != &(list)->tail; \
rn = address_of(rp, node->cmp), rp = node, node = rn)
#define xorlist_for_each_prev(node, rp, rn, list) \
for (rp = &(list)->tail, node = rp->cmp; node != &(list)->head; \
rn = address_of(rp, node->cmp), rp = node, node = rn)
#define xorlist_for_each_from(node, pos1, pos2, rp, rn, list) \
for (rp = pos2, node = pos1; node != &(list)->tail; \
rn = address_of(rp, node->cmp), rp = node, node = rn)
#define xorlist_for_each_from_prev(node, pos1, pos2, rp, rn, list) \
for (rp = pos1, node = pos2; node != &(list)->head; \
rn = address_of(rp, node->cmp), rp = node, node = rn)
/* Note that when the delete function success is must return 0. */
#define xorlist_delete_prototype(name, node) \
int _xorlist_delete_##name(xor_node_t *node)
#define xorlist_delete_call(name) _xorlist_delete_##name
static inline xor_node_t *xornode_init(xor_node_t *n)
{
assert(n);
n->cmp = NULL;
return n;
}
#define XORNODE_INIT(n) \
do { \
(n).cmp = NULL; \
} while (0)
#define XORLIST_INIT(h) \
do { \
(h).head.cmp = &(h).tail; \
(h).tail.cmp = &(h).head; \
(h).count = 0; \
} while (0)
int xorlist_add(xor_list_t *list, xor_node_t *n)
{
xor_node_t *real_next;
if (!n)
return ENOMEM;
xor_node_t *real_prev = &list->head;
xor_node_t *node = real_prev->cmp;
if (node == &list->tail)
real_next = node;
else
real_next = node;
real_prev->cmp = n;
n->cmp = XOR_COMP(real_prev, real_next);
real_next->cmp = XOR_COMP(n, XOR_COMP(real_prev, real_next->cmp);
list->count++;
return 0;
}
int xorlist_del(xor_list_t *list,
xor_node_t *n,
xor_node_t *target,
int (*delete_func)(xor_node_t *))
{
assert(list && n && target && delete_func);
assert(&list->head != target && &list->tail != target);
xor_node_t *nn = address_of(target, n->cmp);
xor_node_t *an = address_of(n, target->cmp);
xor_node_t *ana = address_of(target, an->cmp);
n->cmp = XOR_COMP(nn, an);
an->cmp = XOR_COMP(n, ana);
delete_func(target);
list->count--;
return 0;
}
int xorlist_destroy(xor_list_t *list, int (*delete_func)(xor_node_t *))
{
assert(delete_func);
xor_node_t *real_prev = &list->head;
xor_node_t *node = real_prev->cmp;
xor_node_t *real_next = address_of(real_prev, node->cmp);
xor_node_t *tmp = real_prev;
real_prev = node;
node = real_next;
while (node != &list->tail) {
real_next = address_of(real_prev, node->cmp);
tmp = real_prev;
real_prev = node;
node = real_next;
if (delete_func(tmp) != 0)
perror("delete function failed");
}
return 0;
}
struct test_node {
int value;
xor_node_t xornode;
};
xorlist_delete_prototype(test_delete, _node)
{
struct test_node *node = container_of(_node, struct test_node, xornode);
free(node);
return 0;
}
int main(void)
{
xor_list_t list;
xor_node_t *p1, *p2;
XORLIST_INIT(list);
for (int i = 0; i < 1000; i++) {
struct test_node *new = malloc(sizeof(struct test_node));
xornode_init(&new->xornode);
new->value = i;
xorlist_add(&list, &new->xornode);
if (i == 5)
p1 = &new->xornode;
if (i == 6)
p2 = &new->xornode;
}
xor_node_t *real_prev, *real_next, *node;
int i = 0;
printf("xorlist_for_each test\n");
xorlist_for_each(node, real_prev, real_next, &list)
{
printf("node [%d] %d\n", i++,
container_of(node, struct test_node, xornode)->value);
}
i = 0;
printf("xorlist_for_from test\n");
xorlist_for_each_from(node, p1, p2, real_prev, real_next, &list)
{
printf("node %d\n",
container_of(node, struct test_node, xornode)->value);
}
i = 0;
printf("xorlist_for_each_from_prev test\n");
xorlist_for_each_from_prev(node, p1, p2, real_prev, real_next, &list)
{
printf("node [%d] %d\n", i++,
container_of(node, struct test_node, xornode)->value);
}
i = 0;
printf("xorlist_for_each_prev test\n");
xorlist_for_each_prev(node, real_prev, real_next, &list)
{
printf("node [%d] %d\n", i++,
container_of(node, struct test_node, xornode)->value);
}
printf("xorlist_del test\n");
xorlist_del(&list, p2, p1, xorlist_delete_call(test_delete));
i = 0;
xorlist_for_each(node, real_prev, real_next, &list)
{
printf("node [%d] %d\n", i++,
container_of(node, struct test_node, xornode)->value);
}
xorlist_destroy(&list, xorlist_delete_call(test_delete));
return 0;
}
程式運作原理
以下示意圖表示實作的 Xorlist 在包含 0, 1, 2 個節點時分別的狀況。
當零個節點時，頭尾兩個成員分別在 cmp 持有對方的位址。
當一個節點時，頭尾兩個成員分別紀錄唯一的一個節點的位址。由此透過比對頭尾成員保存的位址是否相同，便可知道是否為長度為 1 的串列。
而此時唯一的成員 node1 的 cmp 成員紀錄 head 與 tail 兩個串列成員的位址進行 xor 運算後的結果。
當串列包含兩個節點時的狀況如下，除了 head、tail 成員以外的節點均紀錄其前後節點的地址 xor 運算結果。
程式實作缺失
在加入節點的程式碼當中並不需要根據
